Mapa de Karnaugh

Introdução

     
    Embora a representação de uma função lógica pela Tabela Verdade seja única, expressa algebricamente, ela pode aparecer em várias formas diferentes. As funções Booleanas podem ser simplificadas por métodos algébricos (Álgebra de Boole), mas esta forma de simplificação é muito penosa e não é sistemática, isto é, não há um único e seguro caminho a seguir, passo a passo, para se alcançar a melhor simplificação.

    O método do mapa fornece um procedimento simples e direto para a minimização de expressões Booleanas. O método do mapa foi inicialmente proposto por Veitch e depois modificado por Karnaugh, sendo conhecido como Diagrama de Veitch ou por Mapa de Karnaugh.

    O Mapa de Karnaugh é composto de células quadradas, dispostas em linhas e colunas, sempre em números de potências de 2 (2, 4, 8, 16, 32 células, etc), sendo esta potência igual ao número de variáveis que compõem a função lógica. Os mapas mais comuns possuem 4, 8 ou 16 células, correspondentes a funções de 2, 3 e 4 variáveis, respectivamente. Para diagramas com mais de 16 células, se torna mais difícil a visualização das possíveis simplificações.

    O Mapa de Karnaugh descreve os estados da saída de um circuito lógico tal como descrito nas Tabelas Verdade. Portanto, é possível, com facilidade, transferirem-se as informações da TV para o Mapa.
     

Mapas de Karnaugh para 2 variáveis

     
    As expressões Lógicas que estudamos até aqui, são escritas na forma de somas de produtos. Os termos de produtos são chamados mintermos, e representam a intercessão entre dois ou mais conjuntos. No mapa de Karnaugh, estes conjuntos são compostos sempre pelos termos que possuem uma certa variável com o valor 1 (V) ou variável com o valor 0 (V'). No mapa da figura 1, a primeira linha corresponde ao conjunto em que a variável A é sempre igual a 0, enquanto a segunda linha, corresponde ao conjunto em que a variável A é sempre igual a 1. A primeira coluna corresponde ao conjunto em que a variável B é sempre igual a 0, enquanto a segunda coluna, corresponde ao conjunto em que a variável B é sempre igual a 1. A interseção entre o conjunto A e o conjunto B' corresponde à célula 2, A=1, B=0, isto é, ao mintermo AB'.
     
    B'
    B
    A'
    m0
    m1
    A
    m2
    m3

     

    Agora podemos transcrever uma TV para o Mapa, escrevendo em cada célula, o estado da saída correspondente às variáveis de entrada dos respectivos mintermos. A primeira linha da tabela, A=0 B=0, corresponde a m0; a segunda linha, A=0 B=1, corresponde a m1, a terceira linha corresponde a m2 e a terceira linha corresponde a m3. Vejamos os dois exemplos seguintes.

    Exemplo 1:

    A B S
    0 0 0
    0 1 0
    1 0 0
    1 1 1

    Transcrevendo esta tabela para o mapa, obtemos:
     

     
    B'
    B
    A'
    0
    0
    A
    0
    1

    Para fazer a simplificação, devemos agrupar o maior número (2n) de células contendo 1, seguindo agrupamentos no sentido horizontal e vertical, nunca diagonal.

    Neste exemplo, só temos uma célula (20) contendo 1, e esta corresponde à intercessão dos conjuntos A e B. Portanto, podemos escrever a expressão da saída como: S = AB. Isto era esperado, visto que a TV apresentada corresponde a uma porta E de duas entradas.
     

    Exemplo 2:

    A B S
    0 0 1
    0 1 1
    1 0 0
    1 1 1

    Transcrevendo esta tabela para o mapa, obtemos:
     

     
    B'
    B
    A'
    1
    1
    A
    0
    1

    Neste exemplo, temos 3 células contendo 1, e podemos fazer dois grupos de 2 células, desde que tomemos o mintermo m2 (A=0, B=1) nos dois grupos. Na simplificação pelo Mapa de Karnaugh, podemos utilizar um mintermo em vários agrupamentos, mas não podemos deixar nenhum mintermo que tenha o valor 1 sem grupo. Se um mintermo não puder ser agrupado, devemos tomá-lo sozinho, fazendo um grupo de uma célula apenas. A figura abaixo mostra como agrupar os mintermos do mapa de Karnaugh deste exemplo.
     

     
    B'
    B
    A'
    1
    1
    A
    0
    1

     
     
    B'
    B
    A'
    1
    1
    A
    0
    1

    Vemos, portanto, que existem dois grupos de duas células cada, sendo que o primeiro (vermelho) corresponde ao conjunto dos mintermos que têm A=0 (A'), e o segundo (azul) corresponde ao conjunto dos mintermos que têm B=1 (B). Qualquer dos dois conjuntos satisfazem à condição S=1, logo podemos escrever a expressão da saída como: S = A' + B.
     
     

Exercício 1:

Verifique, através do Mapa de Karnaugh, que a tabela abaixo corresponde a uma porta NAND. Lembre de DeMorgan.
 

A B S
0 0 1
0 1 1
1 0 1
1 1 0

Na próxima aula, veremos mapas de 3 e 4 variáveis, são muito mais interessantes.