Aula 16 - Mapa de Karnaugh

 Quando trabalhamos com circuitos lógicos (ou programação com variáveis lógicas), em muitos casos é fácil construir uma tabela onde indicamos o resultado que desejamos para cada combinação das entradas. Esta tabela é chamada de tabela verdade. Uma forma de obter um circuito (ou uma função lógica) que forneça os resultados de uma forma otimizada é usando um Mapa de Karnaugh.

O Mapa de Karnaugh (também conhecido como Mapa de Veitch Karnaugh) é uma técnica gráfica que se vale da nossa capacidade de reconhecimento de padrões. É bem mais simples e menos sujeita a erros que a utilização direta das propriedades da lógica booleana.

O primeiro passo é converter a tabela verdade em uma tabela de duas dimensões, onde as linhas e colunas representam as combinações das variáveis de entrada e o conteúdo de cada célula o resultado. Para isso agrupamos as variáveis de entrada de forma que o mapa de Karnaugh seja o mais próximo possível de um quadrado, e assim por diante.

Ao colocar as combinações das variáveis em cada linha ou coluna devemos colocá-las em uma ordem onde apenas uma variável muda de uma linha/coluna para outra. Isto é o chamado Código Grey de numeração binária. Por exemplo, para números de 2 bits, o código Grey é 00, 01, 11, 10.

Vamos tomar por exemplo o caso de termos 4 variáveis de entrada (A a D) e a seguinte tabela verdade, mostrada acima.

Vamos agrupar as variáveis duas a duas (AB e CD). O Mapa de Karnaugh fica conforme mostrado ao lado.

Agora vamos agrupar as células contendo 1, marcando os maiores retângulos possíveis que não contenham 0 e que tenham um número de células que seja potência de 2 (1, 2, 4, 8, etc). Neste agrupamento devemos considerar que a primeira linha é adjacente à última, assim como a primeira e a última coluna. É permitido que os retângulos se sobreponham.

Cada um destes retângulos corresponde a um termo mínimo (mini termo) da função lógica. Um mini termo é o E lógico (AND) das entradas (eventualmente invertidas). A função lógica é o OU lógico (OR) dos mini termos.

A construção dos mini termos é feita observando os valores das variáveis de entrada nos retângulos. Se uma variável aparece no retângulo com os dois valores (0 e 1), ela não aparece no mini termo. Se uma variável aparece apenas com 1, ela entra no mini termo normalmente. Se uma variável aparece apenas com 0, ela entra no mini termo invertida.

Aplicando isto ao nosso exemplo (~ indica negação e . indica E lógico):

• Retângulo amarelo: AB=00/10, CD=00/01. A aparece com 0 e 1, B somente com 0, C somente com 0 e D com 0 e 1. Mini termo = ~B.~C.
• Retângulo azul (sobreposto ao amarelo): AB=11/10, CD=01/11. A aparece somente com 1, B com 1 e 0, C com 0 e 1, D com 1. Mini termo = A.D.
• Retângulo vermelho: AB=00/01, CD=10. A aparece somente com 0, B aparece com 0 e 1, C somente 1 e D somente 0. Mini termo = ~A.C.~D

• A função lógica fica  ~B.~C + A.D + ~A.C.~D

A técnica pode ser extendida para quando a tabela de verdade contem posições onde o valor da saída não interessa (don’t care). Estas posições costuma ser marcadas no mapa de Karnaugh com ‘x’. Ao marcar os retângulos você pode incluir ou ignorar estas posições, buscando obter o maior retângulo possível.

• Se ao invés de marcar os retângulos com valor 1 você marcar os retângulos com valor 0 você vai obter o inverso da função.
• Os resultados obtidos estão na forma de uma “soma de produtos” (OU de termos compostos usando E). Eles podem ser convertidos em “produto de somas” (E de termos compostos usando OU). 

Equação, Circuito, Tabela Verdade e Mapa de Karnaugh está disponível em: 25_01_04 Equação, Circuito, Tabela Verdade e Mapa de Karnaugh  SRG. 

© Direitos de autor. 2021: Gomes; Sinésio Raimundo. Última atualização: 01/04/2021