Mapas de Karnaugh

Os mapas de Karnaugh constituem outra representação para as funções lógicas. Têm especial utilidade por permitirem obter de forma quase totalmente sistemática, e relativamente expedita, as expressões mínimas das funções lógicas.

A minimização não é totalmente sistemática, no sentido de que há casos em que uma parte do processo de obtenção da forma mínima tem que ser feita por tentativa e erro.

O mapa de Karnaugh para uma dada função consiste num quadro com tantas células quantas os possíveis mintermos da função, em que as células são dispostas por forma a possibilitarem uma aplicação mecânica do teorema da adjacência lógica (os mintermos a que é possível aplicar o teorema da adjacência lógica ficam colocados em células 'adjacentes').

Ora pode demonstrar-se que, quando o ponto de partida é a forma canónica soma de produtos, o teorema da adjacência lógica é o único necessário para alcançar a forma mínima - assim, o mapa de Karnaugh permite a minimização através da detecção gráfica de mintermos adjacentes.
Exemplo
O mapa de Karnaugh para uma função de 3 variáveis A, B e C poderia ser:

A função é representada no mapa de Karnaugh inscrevendo um 1 nas células correspondentes aos mintermos que fazem parte da expressão da função, e inscrevendo um 0 nas células correspondentes aos mintermos que não fazem parte da expressão da função.

Seja a função cuja expressão algébrica é dada a seguir na forma canónica soma de produtos:

A sua representação no Mapa de Karnaugh acima seria:

Examinando a expressão da função pode verificar-se que é possível aplicar o teorema da adjacência aos dois últimos termos.

Observando agora o mapa de Karnaugh, verifica-se que aqueles dois termos correspondem a células geometricamente 'adjacentes' com o 1 inscrito. A simplificação pode ser assinalada "agrupando" essas células como se ilustra na figura seguinte.

A expressão simplificada resulta agora directamente do mapa de Karnaugh.
O 1 isolado, que não foi possível 'agrupar' com outro(s), corresponde ao termo enquanto o 'par' de 1s corresponde ao termo

A expressão 'simplificada', forma mínima soma de produtos, é assim:

No mapa que temos vindo a utilizar como exemplo, a correspondência entre células e mintermos é, pois, a que se ilustra a seguir:

São obviamente possíveis outras correspondências entre células e mintermos. A única condição a cumprir é a de que essa correspondência seja tal que fiquem colocados em células geometricamente 'adjacentes' mintermos aos quais seja aplicável o Teorema da Adjacência Lógica. Só deste modo será possível a aplicação 'mecânica' desse teorema.

Usando a convenção de que a uma variável negada corresponde o símbolo 0 e que a uma variável na forma directa corresponde o símbolo 1, podemos representar os mintermos por um código binário. Fazendo corresponder aos números do código binário os respectivos equivalentes decimais, podemos numerar os mintermos como se ilustra a seguir:

Duas células são adjacentes se os mintermos a elas associados forem iguais a menos da ocorrência de uma das variáveis (que aparece directa num e complementada noutro). Assim, células com um lado comum são adjacentes e células com um vértice comum não são. Células nos extremos opostos do mapa também são adjacentes. Por exemplo as células 0 e 2 do mapa acima são adjacentes.

Um mapa de Karnaugh para uma função de 3 variáveis requer 8 células, uma para cada termo desenvolvido (mintermo) possível - 2^3 = 8. Um mapa de Karnaugh para uma função de 2 variáveis terá 2^2 = 4 células, um mapa de Karnaugh para uma função de 4 variáveis terá 2^4 = 16 células, etc.