Mapas karnaugh

Mapas de karnaugh
Mapa de Karnaugh é um diagrama utilizado na minimização de funções booleanas. Chamamos a esse diagrama um mapa visto este ser um mapeamento biunívoco a partir de uma tabela verdade da função que está a ser analisada. Os diagramas foram originalmente criados por Edward Veitch (1952) e aperfeiçoados pelo engenheiro de telecomunicações Maurice Karnaugh. Karnaugh utilizou os diagramas para simplificar circuitos utilizados em telefonia. O nome completo do método é Veitch-Karnaugh em homenagem aos seus dois precursores, mas usualmente utiliza-se apenas o nome de Karnaugh para o método.
O método utiliza a tabela verdade de uma função booleana como base para as simplificações.
Um mapa de Karnaugh é uma ajuda excelente para simplificação de funções de até 6 variáveis. Para funções de mais de 6 variáveis a simplificação é mais complexa pois torna-se uma tarefa árdua identificar as células adjacentes no mapa. Para funções de mais de 6 variáveis devem ser utilizadas soluções algorítmicas computacionais.
Os valores dentro de E nos dizem quais linhas possuem saída igual a 1, e são denotados mintermos.
As variáveis de entrada podem ser combinadas em 16 diferentes formas, então o mapa de Karnaugh terá 16 posições. O arranjo mais conveniente é em uma matriz 4x4.

Mapa de Karnaugh e a expressão booleana ótima correspondente
Os bits no mapa representam a saída da função para uma dada combinação de entradas. Note que os valores são ordenados segundo um código de Gray, de forma que apenas uma variável muda de valor entre cada célula e uma adjacente.
Após o mapa de Karnaugh ter sido construído a próxima tarefa é encontrar os termos mínimos a usar na expressão final. Estes termos são encontrados agrupando conjuntos de 1's adjacentes no mapa. O agrupamento deve ser retangular e deve ter uma área igual a uma potência de 2 (i.e. 2, 4, 8, …). Os retângulos devem ser os maiores possíveis, sem conter nenhum 0. O agrupamento ótimo na figura está marcado com linhas