Como fazer um Mapa de Karnaugh

Prévia do material em texto

Mapa de Karnaugh
Joa˜o Paulo Cerquinho Cajueiro
24 de agosto de 2009
O chamado mapa de Karnaugh foi desenvolvido pelo matema´tico e f´ısico
Maurice Karnaugh1 em 1953, enquanto trabalhava no grupo de pesquisas da
empresa Bell. Este me´todo e´ uma poderosa ferramenta para circuitos lo´gicos,
pois permite simplificar equac¸o˜es booleanas apenas agrupando a´reas comuns,
o que nosso ce´rebro consegue fazer bem mais rapidamente do que aplicando
postulados e teoremas a equac¸o˜es.
1 De diagramas de Venn a Mapas de Karnaugh
Utilizar os teoremas e postulados da a´lgebra de Boole para simplificar equac¸o˜es
e´ bastante tedioso, o que faz com que seja bem prova´vel que hajam erros
no processo. Mas ja´ vimos que as equac¸o˜es da a´lgebra de Boole podem ser
visualizadas atrave´s de um diagrama de Venn. Isto e´ exemplificado na figura 1,
que apresenta um diagrama de Venn de 3 varia´veis com os respectivos mintermos
associados a cada uma das regio˜es.
a b
c
(a) Regio˜es das varia´veis
abc abc
abc
abc
abc abc
abc
abc
(b) Sub-regio˜es dos mintermos
Figura 1: Diagrama Venn com 3 varia´veis.
Utilizando os diagramas, e´ fa´cil obter a equac¸a˜o simplificada da func¸a˜o. Por
exemplo, considere-se a func¸a˜o f1 = abc + abc + abc. Desenhando esta func¸a˜o
num diagrama de Venn (figura 2), fica o´bvio que podemos simplifica´-la para
f1 = (a + c)b.
O problema aparece quando acrescentamos mais 1 varia´vel. Como fazer um
diagrama definindo todas as 16 possibilidades? A soluc¸a˜o para isto e´ desenhar
1Aparentemente ele atualmente (entre outras coisas), escreve o blog unclej0.blogspot.com.
Esta informac¸a˜o depende em se acreditar ou na˜o na wikipedia.
1
f1
Figura 2: Diagrama Venn definindo a regia˜o dada por f1 = abc + abc + abc =
(a + c)b.
as regio˜es como quadrados, e na˜o como c´ırculos, assim como foi feito na figura
3. No lado direito desta figura temos ate´ a representac¸a˜o do lado de fora do
diagrama propriamente dito de que regio˜es correspondem a que varia´veis.
abcd abcd abcdabcd
abcd abcd abcdabcd
abcd abcd abcdabcd
abcd abcd abcdabcd
a
b
c
d
abcd abcd abcdabcd
abcd abcd abcdabcd
abcd abcd abcdabcd
abcd abcd abcdabcd
Figura 3: Diagrama Venn de 4 varia´veis desenhado com regio˜es quadradas.
Este diagrama de Venn modificado ja´ e´ o pro´prio mapa de Karnaugh, onde
no mapa as regio˜es em que a func¸a˜o e´ verdadeira sa˜o marcadas com 1, e em que
a func¸a˜o e´ falsa sa˜o marcadas com 0.
2 Mapas de Karnaugh
Cada regia˜o (quadrado) em um mapa de Karnaugh corresponde a uma linha
na tabela verdade. Ou seja, cada regia˜o corresponde a um mintermo e a um
maxtermo. A figura 4 mostra os mintermos correspondentes a cada uma das
regio˜es. Nela tambe´m esta´ presente o nu´mero correspondente a cada mintermo
2
ou maxtermo.
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
abcd abcd abcdabcd
abcd abcd abcdabcd
abcd abcd abcdabcd
abcd abcd abcdabcd
Figura 4: Regio˜es correspondentes a mintermos de um mapa de Karnaugh
Note na figura 4 que os vizinhos de cada casa em um mapa de Karnaugh sa˜o
tais que apenas muda uma varia´vel de cada vez. Por exemplo, da casa 5 para
a casa 1 (acima) so´ muda o b, da 5 para a 7 (direita) so´ muda o c, da 5 para a
4 (esquerda) so´ muda o d e da 5 para a 13 (abaixo) so´ muda o a. Isto e´ va´lido
para todas as casas.
E´ poss´ıvel aplicar isto inclusive para as casas nas bordas e nas quinas, pois
podemos considerar que o mapa da´ a volta em si mesmo. Deste modo considera-
se a casa 6 como vizinha da 4 e so´ muda a varia´vel c, e a casa 10 vizinha da 2 e
so´ muda a varia´vel a.
Isto nos permite agrupar termos visualmente. Por exemplo, considere a
func¸a˜o f2 =
∑
m(3, 7, 12, 13) e seu respectivo mapa de karnaugh na figura 5.
f2 =
∑
m(3, 7, 12, 13)
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
0 0 01
0 0 01
0 0 00
1 1 00
abc
acd
Figura 5: Func¸a˜o f2 e simplificac¸a˜o por agrupamento de casas vizinhas.
Analisando a func¸a˜o f2 por a´lgebra de Boole, vemos que podemos simplifica´-
la aplicando o teorema T6. E observando no mapa de Karnaugh, os termos que
sa˜o unidos e simplificados sa˜o justamente os vizinhos.
f2 = abcd + abcd︸ ︷︷ ︸
T6
+ abcd + abcd︸ ︷︷ ︸
T6
f2 = acd + abc
3
Ou seja, o agrupamento de 2 casas vizinhas corresponde a` simplificac¸a˜o de
uma varia´vel atrave´s da aplicac¸a˜o to teorema T6. Basta ver no pro´prio mapa
quais sa˜o as varia´veis que na˜o mudam dentro do agrupamento.
Para simplificar 2 ou mais varia´veis basta aplicar o teorema repetidas vezes.
Simplifiquemos a func¸a˜o f3 (vide figura 6), por exemplo. Basta agruparmos a
func¸a˜o de duas em duas casas e 2 grupos vizinhos de duas casas viram um u´nico
grupo de 4 casas, retirando mais uma varia´vel da func¸a˜o.
f3 = abcd + abcd︸ ︷︷ ︸+ abcd + abcd︸ ︷︷ ︸
= abc + abc︸ ︷︷ ︸
f3 = ac
f3
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
0 0 00
0 0 00
1 1 00
1 1 00
⇒
f3
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
0 0 00
0 0 00
1 1 00
1 1 00
Figura 6: Agrupamento das casas da func¸a˜o f3.
Este mesmo procedimento pode ser mostrado para agrupamentos de 8 casas
(simplificando enta˜o 3 varia´veis) ou 16 casas (simplificando 4 varia´veis. A figura
7 mostra algumas possibilidades de agrupamentos de 2, 4 e 8 casas2, junto com
o produto respectivo. Claro que num mapa de Karnaugh de 4 varia´veis um
agrupamento de 16 casas seria todo o mapa e corresponderia a func¸a˜o 1.
2Exemplos utilizados tambe´m no artigo original de Karnaugh: “The map method for
synthesis of combinational logic circuits”, de 1953.
4
bcd
a
b
c
d
0 0 00
0 1 00
0 0 00
0 1 00
abd
a
b
c
d
0 1 01
0 0 00
0 0 00
0 0 00
abd
a
b
c
d
1 0 10
0 0 00
0 0 00
0 0 00
bcd
a
b
c
d
1 0 00
0 0 00
1 0 00
0 0 00
(a) agrupamentos de 2 casas
cd
a
b
c
d
0 1 00
0 1 00
0 1 00
0 1 00
ab
a
b
c
d
0 0 00
0 0 00
1 1 11
0 0 00
a d
a
b
c
d
1 0 10
1 0 10
0 0 00
0 0 00
b d
a
b
c
d
1 0 10
0 0 00
1 0 10
0 0 00
(b) Agrupamentos de 4 casas
b
a
b
c
d
0 0 00
1 1 11
0 0 00
1 1 11
d
a
b
c
d
1 0 10
1 0 10
1 0 10
1 0 10
c
a
b
c
d
0 0 11
0 0 11
0 0 11
0 0 11
b
a
b
c
d
1 1 11
0 0 00
1 1 11
0 0 00
(c) Agrupamentos de 8 casas
Figura 7: Exemplos de mapas de karnaugh com os correspondentes produtos
alge´bricos.
5
2.1 Mapas de n varia´veis
Claro que um mapa de Karnaugh pode ser feito com um nu´mero menor de
varia´veis. Para tanto basta simplesmente sair dividindo o mapa. Tem-se apenas
que lembrar que uma casa deve ter n vizinhas, ja´ que a simplificac¸a˜o de uma
varia´vel corresponde a unir uma casa com a vizinha. Isto e´ mostrado na figura
8 para mapas de 2, 3 e 4 varia´veis.
a
b
0 1
2 3
(a) Mapa de 2
varia´veis
a
b
c
0 1 3 2
4 5 7 6
(b) Mapa de 3 varia´veis
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
(c) Mapa de 4 varia´veis
Figura 8: Mapas de Karnaugh de 2, 3 e 4 varia´veis, mostrando que cada casa
tem n vizinhas.
Mas como aplicar este princ´ıpio para func¸o˜es com mais de 4 varia´veis?
E´ imposs´ıvel fazer um mapa no plano onde cada uma das regio˜es tem 5 (ou
mais) vizinhos. Uma maneira (na˜o muito pra´tica) e´ trabalhar com um mapa
tridimensional como exemplifica a figura 9 que mostra um mapa de Karnaugh
de 6 varia´veis, note que cada casa tem 6 vizinhos: 4 no plano (como no mapa
de 4 varia´veis) e 2 verticais.
Na pra´tica, um mapa de 5 varia´veis e´ desenhado como 2 de 4 varia´veis, sendo
um com uma varia´vel (em geral a mais significativa) sendo 0 e o outro com a
mesma varia´vel sendo1. Usa-se este mesmo princ´ıpio para mapas de 6 varia´veis
ou mais varia´veis, como pode ser visto na figura 10.
6
c
d
e
f
32 33 35 34
36 37 39 38
44 45 47 46
40 41 43 42
c
d
e
f
48 49 51 50
52 53 55 54
60 61 63 62
56 57 59 58
c
d
e
f
16 17 19 18
20 21 23 22
28 29 31 30
24 25 27 26
c
d
e
f
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
a
b
Figura 9: Mapa de Karnaugh tridimensional de 6 varia´veis.
b
c
d
e
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
b
c
d
e
16 17 19 18
20 21 23 22
28 29 31 30
24 25 27 26
a
(a) 5 varia´veis
c
d
e
f
32 33 35 34
36 37 39 38
44 45 47 46
40 41 43 42
c
d
e
f
48 49 51 50
52 53 55 54
60 61 63 62
56 57 59 58
c
d
e
f
16 17 19 18
20 21 23 22
28 29 31 30
24 25 27 26
c
d
e
f
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
a
b
(b) 6 varia´veis
Figura 10: Mapas de Karnaugh de 5 e 6 varia´veis.
7
3 Soma de produtos e produto de somas
Ate´ o momento trabalhamos com o mapa de Karnaugh agrupando os 1’s para
gerar func¸o˜es na forma soma de produtos, mas podemos agrupar os zeros tam-
be´m, gerando equac¸o˜es na forma produto de somas, como mostra a figura 11
para a func¸a˜of4 = ac + a(b + cd).
f4(a, b, c, d)
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
0 0 01
1 1 11
1 1 00
1 1 00
a + c
b + c + da + b + c
Figura 11: Mapa de Karnaugh com agrupamento de 0’s.
Da mesma forma que na tabela verdade, um 0 no mapa de Karnaugh cor-
responde a um maxtermo. Logo o agrupamento de 2 casas com 0 corresponde
a uma soma com n − 1 termos (onde n e´ o nu´mero de varia´veis da func¸a˜o), o
agrupamento de 4 casas equivale a uma soma de n − 2 varia´veis e assim por
diante.
No caso de agrupamento de zeros, deve-se tomar cuidado com a relac¸a˜o entre
uma regia˜o marcada e como a varia´vel aparece na equac¸a˜o. Por exemplo, na
figura 11 a regia˜o a + c ocorre onde esta´ marcado a no mapa, e na˜o onde esta´
marcado a. A explicac¸a˜o para este fenoˆmeno e´ a mesma dos maxtermos na
tabela verdade terem as varia´veis barradas em relac¸a˜o aos mintermos corres-
pondentes. Isto torna a ana´lise do mapa por agrupamento de 0’s bem menos
intuitiva.
f5
a
b
c
d
0 1 3 2
4 5 7 6
12 13 15 14
8 9 11 10
1 0 00
1 1 10
1 1 11
1 0 11
Figura 12: Exemplo de equac¸a˜o minimizada por agrupamento de 1’s e de 0’s.
A partir do mapa de Karnaugh, podemos obter a equac¸a˜o na forma produto
de somas, juntando os zeros; ou na forma soma de produtos, juntando os uns.
8
As duas formas obtidas da func¸a˜o f5 da figura 12 sa˜o mostradas abaixo e apesar
de aparentarem ser diferentes, elas sa˜o, de fato, equivalentes.
f5 = (a + b + c)
(
a + b + d
) (
a + c + d
) (
a + b + c + d
)
(1)
f5 = a b + a c + b d + c d + a b c (2)
Comec¸ando da equac¸a˜o na forma produto de somas, multiplicamos os dois
primeiros pareˆnteses e os dois u´ltimos e obtemos:
f5 =
(
a + a b + a d + b + b d + b c + a d + c d
) ·
· (a b + a c + a d + a c + b c + c d + a d + b d + c d + d) (3)
Retirando os va´rios termos redundantes, chega-se a:
f5 =
(
a + b + c d
) (
a b + a c + d + a c + b c
)
(4)
Multiplicando novamente, obteˆm-se:
f5 = a b + a c + a d + a b c + a b c + b d + a b c + a b c d + c d + a c d + b c d (5)
Onde novamente temos va´rios termos redundantes que simplificam em:
f5 = a b + a c + a d + b d + a b c + c d (6)
Note que podemos usar o teorema do consenso nos segundo, terceiro e u´ltimo
termo, retirando enta˜o o terceiro termo. Com isso, obte´m-se a equac¸a˜o (2)
obtida por soma de produtos.
Mostra-se enta˜o que a equac¸a˜o (1) e´ equivalente a` (2), q.e.d..
4 Equac¸o˜es e circuitos na˜o-completamente espe-
cificados.
E´ bastante comum a situac¸a˜o de que determinadas entradas de um circuito lo´gico
nunca ocorram. Como exemplo imagine-se uma esteira carregando uma caixa
de um lado para o outro, com sensores de fim de curso em ambas extremidades:
se do lado esquerdo e sd do lado direito. No funcionamento normal do sistema
estes dois sinais nunca sera˜o acionados ao mesmo tempo; nesta situac¸a˜o na˜o
importa qual e´ o resultado do circuito para se = sd = 1, ja´ que esta situac¸a˜o
nunca vai existir, portanto na˜o e´ necessa´rio especificar um valor de sa´ıda para
esta situac¸a˜o. Diz-se enta˜o que este circuito e´ na˜o-completamente especificado.
A tabela 1 mostra o exemplo de um sinal imagina´rio z determinado em
func¸a˜o de a, se e sd. Neste exemplo, sempre que se = sd = 1 a sa´ıda z e´ na˜o-
especificada, ou seja, z na˜o-importa nestas situac¸o˜es. Neste texto utilizaremos
a notac¸a˜o ×3 para identificar as situac¸o˜es que um sinal na˜o importa.
Pode-se descrever uma func¸a˜o lo´gica na˜o-completamente especificada na
forma soma de mintermos ou produto de maxtermos utilizando a notac¸a˜o d(· · · ),
que vem do ingleˆs don’t care. Desta forma o sinal z pode ser descrito por:
z =
∑
m
(2, 4, 6) + d(3, 7) =
∏
M
(0, 1, 5) + d(3, 7) (7)
3“dontchiquer, bicho.”
9
a se sd z
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 ×
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 ×
Tabela 1: Exemplo de uma func¸a˜o na˜o completamente especificada. As sa´ıdas
na˜o especificadas sa˜o identificadas por ×. Outras notac¸o˜es comumente usadas
sa˜o *, - ou d.
Um × na sa´ıda pode ser implementado como um 1 ou um 0, e na˜o se sabe
a princ´ıpio qual destes dois valores gerara´ uma soluc¸a˜o mais minimizada, logo
para obter o menor circuito poss´ıvel o engenheiro deveria obter as equac¸o˜es
considerando que cada × pode ser 1 ou 0 e checar qual e´ o menor circuito final.
Obviamente para problemas com muitos ×’s isto se torna impratica´vel, pois
seria necessa´rio implementar 2k circuitos, onde k e´ o nu´mero de ×’s presentes.
Felizmente o mapa de Karnaugh facilita bastante a implementac¸a˜o de circui-
tos na˜o-completamente especificados, pois podemos considerar se determinado
× e´ 1 ou 0 visualmente, na hora da implementac¸a˜o.
z
a
se
sd
0 1 3 2
4 5 7 6
1 0 1×
0 0 1×
Figura 13: Mapa de Karnaugh da func¸a˜o z.
Ao minizarmos a func¸a˜o z pelo mapa de Karnaugh (figura 13) obtemos 2
func¸o˜es:
z′ = se + sda (pelos 1’s) (8)
z′′ = sd (se + a) (pelos 0’s) (9)
Note que, neste caso, estas duas equac¸o˜es na˜o sa˜o equivalentes; ou seja, na˜o e´
poss´ıvel sair de uma delas e chegar na outra por a´lgebra de Boole, como ja´ foi
feito na sec¸a˜o 3 para f5. Isto porque na minimizac¸a˜o por soma de produtos foi
considerado que os ×’s eram 1, enquanto que em produto de somas eles foram
considerados como sendo 0.
Esta situac¸a˜o e´ bastante comum ao minimizar func¸o˜es na˜o completamente
especificadas, pore´m, apesar de estranho, na˜o causa nenhum problema, ja´ que as
diferenc¸as nas sa´ıdas ocorrem justamente quando na˜o importa o valor da sa´ıda,
seja por que aquela entrada nunca ocorre ou por outra raza˜o qualquer.
10