Mapa de Karnaugh


(Última atualização: 21 de agosto de 1997)

O Mapa de Karnaugh é uma ferramenta de auxílio à minimização de funções booleanas. O próprio nome mapa vem do fato dele ser um mapeamento biunívoco a partir de uma tabela-verdade. Vejamos como é feito este mapeamento.

Mapa de Karnaugh para 1 Variável

Considere a tabela-verdade, já vista, de uma função NOT,
A f(A) = A'

0

1

1

0

Para se fazer um Mapa de Karnaugh a partir desta tabela-verdade, realiza-se a construção ilustrada na figura abaixo,

ou seja (veja que a variável A, em verde, está indicando que a função em questão só possui uma variável independente):

  1. Acrescenta-se mais uma coluna à tabela-verdade original. Esta coluna tem por função enumerar as linhas, a partir de zero (0).

  2. Constroi-se tantos quadrículos quantas forem as linhas da tabela-verdade, enumerando-os com o número da linha correspondente no canto superior esquerdo de cada quadrículo (números em preto).

  3. Coloca-se os valores das variáveis do lado de fora de cada quadrículo (números em azul).

  4. Coloca-se os valores da função no centro de cada quadrículo, respeitando-se o número da linha correspondente (números em vermelho).

Mapa de Karnaugh para 2 Variáveis

Veja para função de duas varáveis (por exemplo, a função AND),

Mapa de Karnaugh para 3 Variáveis

Para funções de três variáveis independentes,

Mapa de Karnaugh para 4 Variáveis

Para funções de quatro variáveis independentes,

Note que, a partir do Mapa de Karnaugh para funções três ou mais variáveis independentes, há uma anotação das filas (linhas ou colunas) de quadrículos onde a variável independente não muda de valor. Também observe que, de uma fila de quadrículos para outra fila, só há uma mudança de valor nas variáveis.

Observe que a ordem de numeração das linhas e colunas, representativas de combinações de variáveis, obedece o Código de Gray (Gray Code), as vezes chamado de Código Refletido.

Exemplos de Uso

Ex.1 - Considere a seguinte função lógica de duas variáveis, F(A,B),

Do lado da equação booleana, e pelo Teorema 11 visto no tópico Álgebra de Boole, a redução é evidente. Do lado do Mapa de Karnaugh, os dois quadrículos contíguos, contendo o valor lógico 1 cada, indicam que:

  1. A variável A não muda de valor lógico nos dois quadrículos contendo o valor lógico 1 da função F (1 acima da tabela): mantenha a variável A.

  2. A variável B muda de valor lógico nos dois quadrículos contendo o valor lógico 1 da função F (0 e 1 à esquerda da tabela): elimine a variável B.

Ex.2 - Considere, agora, a função de três variáveis, F(A,B,C),

Por não ser trivial a conclusão obtida com o mapa de Karnaugh, aí segue a prova,

Como pode ser visto, o mapa de Karnaugh é uma ferramenta eficiente para simplificar funções booelanas. Uma simplificação algébrica alternativa da função acima fica como exercício. Note que no mapa de Karnaugh acima, os quatro quadrículos contíguos (linha 0 - coluna 11; linha 0 - coluna 10; linha 1 - coluna 11; linha 1 - coluna 10), contendo o valor lógico 1 cada, indicam que a variável A não muda de valor lógico nos quatro quadrículos contendo o valor lógico 1 da função F. Esta é a razão de manter-se a variável A (primeiro termo da simplificação). A variável A muda de valor lógico nos dois quadrículos contendo o valor lógico 1 da função F: elimine a variável A, mantendo B e C complementadas (segundo termo da simplificação).

Ex.3 - Considere, agora, a função lógica do exemplo 2. Faremos sua minimização através do conceito de maxtermos. Para isso, complete as lacunas com o dígito 0,

Note que, agora, estamos destacando os 0's adjacentes, e não os 1's adjacentes, como no exemplo 2. Para melhor compreensão do que isso significa, construa a tabela verdade da função F e também de sua negação, F',
A B C F F'

Mintermos

Maxtermos

0 0 0 1 0

m0=A'B'C'

M0=A+B+C

0 0 1 0 1

m1=A'B'C

M0=A+B+C'

0 1 0 0 1

m3=A'BC'

M0=A+B'+C

0 1 1 0 1

m4=A'BC

M0=A+B'+C'

1 0 0 1 0

m5=AB'C'

M0=A'+B+C

1 0 1 1 0

m6=AB'C

M0=A'+B+C'

1 1 0 1 0

m7=ABC'

M0=A'+B'+C

1 1 1 1 0

m8=ABC

M0=A'+B'+C'

Donde você pode concluir que os mintermos (ou maxtermos) que aparecem em F não aparecem em F', e vice-versa,

Significa que minimizar a função F, via mintermos, é equivalente a minimizar sua negação, F', via maxtermos. Se você minimizar F', via mapa de Karnaugh através de mintermos, e, então, calcular F (negando F'), você também resolveu o problema do exemplo 2. O mapa de Karnaugh para F' é,

Minimizando F' e calculando F ( = (F')'), tem-se,

Este artifício pode ser usado para minimizar funções com número de 0's ou 1's reduzido, usando-se uma ou outra técnica. Aprenda mais sobre Mapa de Karnaugh e simplificações de funções lógicas nos seguintes sites:


Anterior: Mintermos e Maxitermos Próxima: Famílias de Circuitos Integrados 

Retornar ao índice de assuntos

Você pode falar comigo pelo e-mail: jbosco@inf.ufsc.br