Metodo 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 B + AB = ( + 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 B | 0 | 1 | 0 | | B | 1 | A | 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 B | 0 | | 1 | 0 | | | 1 | 1 | 1 | | 1 | | | | A B | 0 | | 1 | 0 | | | | 1 | | | 1 | |
Na realidade a soma de minterms para A + B é B + A + 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 é,
B + A + AB = (B + AB) + (A + AB) = ( + A)B + A( + 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 BC