Mapa de Karnaugh

Prévia do material em texto

Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 1 
Mapa de Karnaugh 
 
1) 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. 
 
 
2) 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, 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 2 
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 
 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 3 
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 
satisfaz à condição S=1, logo podemos escrever a expressão da saída como: S = A' + B. 
 
 
3) 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 
 
 
 
 
 
Mapa de Karnaugh de 3 e de 4 variáveis 
 
 
1) Mapa de 3 variáveis 
 
Um mapa de Karnaugh de 3 variáveis é obtido dividindo-se cada célula do mapa de 2 
variáveis ao meio. Assim cada bloco divido terá uma célula correspondente à variável 
(V=1) e uma célula correspondente ao complemento da variável (V=0). Abaixo está 
representado um mapa cujas variáveis de entrada são A,B,C. 
 
 B' B 
A' C' C C C' 
A C' C C C' 
 
De outra forma podemos representar o mapa identificando as linhas e coluna 
correspondente a cada estado das variáveis e escrever estes estados no interior das células, 
na ordem ABC. 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 4 
Agora verificamos que o conjunto correspondente aos estados de cada variável são 
compostos de 4 células. 
 
O conjunto de A', isto é, onde A=0 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
O conjunto de A, isto é, onde A=1 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
O conjunto de B', isto é, onde B=0 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
O conjunto de B, isto é, onde B=1 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
O conjunto de C, isto é, onde C=1 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
O conjunto de C', isto é, onde C=0 
 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Deve-se observar o detalhe de que o bloco de quatro células correspondente a C' está 
dividido em dois blocos de 2 células, mas pode ser agrupado ao se fazer a simplificação da 
expressão booleana. 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 5 
Além dos agrupamentos em blocos de 4 células, podemos obter simplificações pelo 
agrupamento de 2 células. 
 
Bloco A'B' 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Bloco A'B 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Bloco AB' 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Bloco B'C' 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Bloco BC 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Bloco A'C 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
Bloco AC' 
 B' B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
 
Existem mais 5 blocos de 2 que o aluno deverá identificar: AB, B'C, BC', A'C' e AC. 
 
 
 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 6 
Se não for possível fazer agrupamentos, cada célula será identificada pelo produto das 
três variáveis, como no exemplo abaixo. 
 
Bloco ABC' 
 B'B 
A' 0 0 0 0 0 1 0 1 1 0 1 0 
A 1 0 0 1 0 1 1 1 1 1 1 0 
 C' C C' 
 
 
Vejamos um exemplo: Identificadores de números primos de 0 a 7. 
 
Inicialmente montaremos a Tabela Verdade. 
 
Dec Binário 
 A B C S 
0 0 0 0 0 
1 0 0 1 0 
2 0 1 0 1 
3 0 1 1 1 
4 1 0 0 0 
5 1 0 1 1 
6 1 1 0 0 
7 1 1 1 1 
 
A expressão lógica da saída, S, em função das entradas A, B, C é: 
 
S = A'B'C + A'BC + AB'C + ABC 
 
Devemos, agora, usar o mapa de Karnaugh para simplificar a expressão lógica do 
identificador de números primos: 
 
 B' B 
A' 0 0 1 1 
A 0 1 1 0 
 C' C C' 
 
Podemos formar 3 grupos de duas células, a saber: 
 
A'BC + A'BC' = A'B 
AB'C + ABC = AC 
A'BC + ABC = BC 
 
Assim podemos escrever a expressão simplificada da saída como: 
 
S = A'B + AC + BC 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 7 
 
O terceiro termo, BC, foi obtido da simplificação dos mintermos AB'C e ABC, os quais 
já estão presentes nos outros dois termos, A'B e AC, portanto BC é um termo 
desnecessário, podendo a expressão final da saída ser escrita como: 
 
S = A'B + AC. 
 
O circuito digital simplificado do identificador de números primos é o da figura abaixo. 
Faça a tabela verdade deste circuito e verifique que coincide com a primeira tabela verdade 
que foi feita neste exemplo. 
 
 
 
 
 
2) Mapa de 4 variáveis 
 
Um mapa de Karnaugh de 4 variáveis é obtido dividindo-se cada célula do mapa de 3 
variáveis ao meio. Assim cada bloco divido terá uma célula correspondente à variável 
(V=1) e uma célula correspondente ao complemento da variável (V=0). Abaixo está 
representado um mapa cujas variáveis de entrada são A,B,C,D. Os estados das variáveis são 
escritos dentro de cada célula na ordem ABCD. 
 
 C' C 
A' 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 B' 
 
 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 
A 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 B 
 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 B' 
 D' D D' 
 
Verifique que a célula ABC' foi dividida em duas novas células ABC'D' e ABC'D, 
identificadas acima como 1100 e 1101 respectivamente. As outras 14 células correspondem 
às outras 14 possíveis combinações das variáveis A, B, C, D. 
As simplificações utilizando o mapa de 4 variáveis são feitas por agrupamentos de 
células que contêm S=1 em números de 8, 4, 2 e 1 célula. Abaixo são mostrados exemplos 
de grupos de 8, 4 e 2 células. 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 8 
S = B 
 C' C 
A' 0 0 0 0 B' 
 
1 1 1 1 
A 1 1 1 1 B 
 0 0 0 0 B' 
 D' D D' 
 
S = BD + B'D' 
 C' C 
A' 1 0 0 1 B' 
 
0 1 1 0 
A 0 1 1 0 B 
 1 0 0 1 B' 
 D' D D' 
 
O grupo BD corresponde às 4 células do centro do mapa, enquanto o grupo B'D' 
corresponde às 4 células dos cantos do mapa. 
 
S = A'BD' + ACD 
 C' C 
A' 0 0 0 0 B' 
 
1 0 0 1 
A 0 0 1 0 B 
 0 0 1 0 B' 
 D' D D' 
 
 
Vejamos 3 exemplos: 
 
A B C D S1 S2 S3 
0 0 0 0 0 0 1 
0 0 0 1 1 1 0 
0 0 1 0 1 0 1 
0 0 1 1 1 1 0 
0 1 0 0 0 1 1 
0 1 0 1 1 1 1 
0 1 1 0 0 1 0 
0 1 1 1 1 1 1 
1 0 0 0 1 0 1 
1 0 0 1 1 0 1 
1 0 1 0 0 0 1 
1 0 1 1 1 1 0 
1 1 0 0 1 0 0 
1 1 0 1 1 0 0 
1 1 1 0 0 1 0 
1 1 1 1 1 0 1 
 
Sistemas Digitais – Mapa de Karnaugh 
Prof. João Giacomin – DCC - UFLA – 2007 9 
Os mapas correspondentes às saídas S1, S2, S3 são: 
 
S1 C' C 
A' 0 1 1 1 B' 
 
0 1 1 0 
A 1 1 1 0 
B 
 
1 1 1 0 B' 
 D' D D' 
 
S1 = D + AC' + A'B'C 
 
O primeiro termo, D, corresponde ao sombreado cinza. O segundo termo corresponde 
aos números verdes e o terceiro termo corresponde aos números de fundo amarelo. 
 
S2 C' C 
A' 0 1 1 0 B' 
 
1 1 1 1 
A 0 0 1 0 B 
 0 0 0 1 B' 
 D' D D' 
 
S2 = A'B + A'D + BCD 
 
Os três termos correspondem respectivamente aos grupos sombreado cinza, números 
verdes e números de fundo amarelo. 
 
 
 
 
S3 C' C 
A' 1 0 0 1 B' 
 
1 1 1 0 
A 0 0 1 0 B 
 1 1 0 1 B' 
 D' D D' 
 
S3 = B'D' + A'BC' + AB'C' + BCD 
 
Os quatro termos correspondem respectivamente aos grupos sombreado cinza, 
sombreado verde, números verdes e sombreado azul.