Subsecções


Simplificação de funções booleanas e Mapas de Karnaugh

No caso de funções booleanas com no máximo seis variáveis existem métodos gráficos para obter uma soma de produtos equivalente e que é em geral mais simples do que a soma de minterms, obtida pelo método do Teorema 1. São os chamados Mapas de Karnaugh ([AU92] Capítulo 12.6, [Dew93], Capítulo 20 e [Gri99]), que são definidos em função do número de variáveis da função booleana.

Os mapas são diagramas constituídos por quadrados cada um correspondendo a um minterm da função booleana representada. Nos diagramas dois minterms adjacentes diferem apenas no valor de um dos literais.

Vamos supor que a expressão mais simples, como soma de produtos, é a que tem um número mínimo de produtos e o menor número de literais em cada produto. Para isso usam-se propriedades booleanas, como $ \bar{A}$B + AB = ($ \bar{A}$ + A)B = B.

Duas variáveis

Existem 4 minterms para uma função booleana de duas variáveis. Então o mapa é constituído 4 quadrados.

m0 m1
m2 m3
   
A$ \setminus$ B 0 1
0 $ \bar{A}$$ \bar{B}$ $ \bar{A}$B
1 A$ \bar{B}$ AB

Uma função é representada escrevendo um 1 nos quadrados correspondentes a cada um dos minterms da sua representação como soma de minterms.

Para as funções f (A, B) = A + B e g(A, B) = AB temos os mapas:

f(A,B)=A+B     g(A,B)=AB
A$ \setminus$ B 0   1
0     1
1 1   1
   
A$ \setminus$ B 0   1
0      
1     1

Na realidade a soma de minterms para A + B é $ \bar{A}$B + A$ \bar{B}$ + AB. Agora o facto de estarem 1's adjacentes na coluna do B e na linha do A permitem que a expressão seja simplificada para a forma A + B, isto é,

$\displaystyle \bar{A}$B + A$\displaystyle \bar{B}$ + AB = ($\displaystyle \bar{A}$B + AB) + (A$\displaystyle \bar{B}$ + AB) = ($\displaystyle \bar{A}$ + A)B + A($\displaystyle \bar{B}$ + B) = B + A

Três variáveis

Como vimos, existem 8 minterms para funções booleanas de 3 variávies. Os mapas vão ter 8 quadrados. Note que a disposição dos mi não segue a ordem numérica, a regra é que dois quadrados adjacentes só diferem no valor de um literal.

m0 m1 m3 m2
m4 m5 m7 m6
   
A $ \setminus$ BC 00 01 11 10
0 $ \bar{A}$$ \bar{B}$$ \bar{C}$ $ \bar{A}$$ \bar{B}$C $ \bar{A}$BC $ \bar{A}$B$ \bar{C}$
1 A$ \bar{B}$$ \bar{C}$ A$ \bar{B}$C ABC AB$ \bar{C}$

A representação de f (A, B, C) = m0 + m2 + m4 + m7 fica

A $ \setminus$ BC 00 01 11 10
0 1     1
1 1   1  

O 1 para ABC está isolado portanto tem de aparecer no final. Supondo que os mapas são circulares, o 1 de $ \bar{A}$B$ \bar{C}$ está a dajacente ao de $ \bar{A}$$ \bar{B}$$ \bar{C}$ fazendo com que $ \bar{A}$$ \bar{C}$(B + $ \bar{B}$)= $ \bar{A}$$ \bar{C}$. De igual modo, os 1's na primeira coluna levam a que $ \bar{C}$$ \bar{B}$(A + $ \bar{A}$) = $ \bar{C}$$ \bar{B}$, e portanto a função pode simplificar para $ \bar{C}$$ \bar{B}$ + $ \bar{A}$$ \bar{C}$ + ABC.

Para estes mapas:

Claro que um mapa com tudo 1's representa 1.

Para função c(A, B, C) = m3 + m5 + m6 + m7 o mapa é

A $ \setminus$ BC 00 01 11 10
0     1  
1   1 1 1

que simplifica, por exemplo para, c(A, B, C) = AB + AC + BC

Para f (A, B, C) = m3 + m4 + m6 + m7 o mapa é

A $ \setminus$ BC 00 01 11 10
0     1  
1 1   1 1

que simplifica para f (A, B, C) = BC + A$ \bar{C}$

Exercício 1.11   Usando este método simplifique:

0) 0)
  1. f (A, B, C) = m0 + m2 + m4 + m6
  2. f (A, B, C) = m0 + m1 + m2 + m3
0) 0)
  1. f (A, B, C) = m0 + m2 + m4 + m5 + m6
  2. f (A, B, C) = m1 + m2 + m3 + m6 + m7

Quatro variáveis

Neste caso temos 16 minterms e portanto os mapas têm 16 quadrados.

m0 m1 m3 m2
m4 m5 m7 m6
m12 m13 m15 m14
m8 m9 m11 m10
   
AD $ \setminus$ BC 00 01 11 10
00 $ \bar{A}$$ \bar{D}$$ \bar{B}$$ \bar{C}$ $ \bar{A}$$ \bar{D}$$ \bar{B}$C $ \bar{A}$$ \bar{D}$BC $ \bar{A}$$ \bar{D}$B$ \bar{C}$
01 $ \bar{A}$D$ \bar{B}$$ \bar{C}$ $ \bar{A}$D$ \bar{B}$C $ \bar{A}$DBC $ \bar{A}$DB$ \bar{C}$
11 AD$ \bar{B}$$ \bar{C}$ AD$ \bar{B}$C ADBC ADB$ \bar{C}$
10 A$ \bar{D}$$ \bar{B}$$ \bar{C}$ A$ \bar{D}$$ \bar{B}$C A$ \bar{D}$BC A$ \bar{D}$B$ \bar{C}$

Para a função f (A, B, C, D) = m0 + m2 + m1 + m3 + m8 + m9 + m10,

AD $ \setminus$ BC 00 01 11 10
00 1 1 1 1
01        
11        
10 1 1   1

Note que supõe que os diagramas são toros (``donuts'') em que as extremidades superior e inferior e esquerda e direita estão ligadas.

Combinando os 1's nos quatro cantos temos $ \bar{A}$$ \bar{D}$$ \bar{B}$$ \bar{C}$ + $ \bar{A}$$ \bar{D}$B$ \bar{C}$ + A$ \bar{D}$$ \bar{B}$$ \bar{C}$ + A$ \bar{D}$B$ \bar{C}$ = $ \bar{D}$$ \bar{C}$ Analogamente, os da primeira linha dão $ \bar{A}$$ \bar{D}$. Finalmente os dois primeiros 1's da última linha podem combinar com os dois prineiros da primeira linha

$\displaystyle \bar{A}$$\displaystyle \bar{D}$$\displaystyle \bar{B}$$\displaystyle \bar{C}$ + $\displaystyle \bar{A}$$\displaystyle \bar{D}$$\displaystyle \bar{B}$C + A$\displaystyle \bar{D}$$\displaystyle \bar{B}$$\displaystyle \bar{C}$ + A$\displaystyle \bar{D}$$\displaystyle \bar{B}$C = $\displaystyle \bar{D}$$\displaystyle \bar{B}$

vem f (A, B, C, D) = $ \bar{D}$$ \bar{C}$ + $ \bar{A}$$ \bar{D}$ + $ \bar{D}$$ \bar{B}$

As combinações de quadrados que se podem escolher para n = 4 são:

Resumindo, para simplificar uma função booleana dada pelo seu mapa de Karnaugh:

  1. Começar por combinar os termos na tabela para os quais existe apenas uma possibilidade de simplificação.
  2. Verificar os quatro cantos do mapa, que podem conter 1's adjacentes
  3. Tentar encontrar o maior número de 1's adjacentes
  4. Se houver uma escolha no modo de simplificar, deve-se usar 1's que ainda não tenham sido usados para simplificar

Exercício 1.12   Simplifique b) b)
  1. f (A, B, C, D) = m9 + m10 + m11 + m12 + m13
  2. f (A, B, C, D) = m3 + m4 + + m5 + m7 + m9 + m13 + m14 + + m15

Este método torna-se impraticável para funções com mais do que 6 variávies. O método Quine-MaCluskey resolve o problema de minimização de somas de produtos para qualquer número de literais.

Nelma Moreira 2000-11-20