Mapa de Karnaugh

Mapa de Karnaugh
João Paulo Cerquinho Cajueiro
24 de agosto de 2009
O chamado mapa de Karnaugh foi desenvolvido pelo matemático e fı́sico
Maurice Karnaugh1 em 1953, enquanto trabalhava no grupo de pesquisas da
empresa Bell. Este método é uma poderosa ferramenta para circuitos lógicos,
pois permite simplificar equações booleanas apenas agrupando áreas comuns,
o que nosso cérebro consegue fazer bem mais rapidamente do que aplicando
postulados e teoremas a equações.
1
De diagramas de Venn a Mapas de Karnaugh
Utilizar os teoremas e postulados da álgebra de Boole para simplificar equações
é bastante tedioso, o que faz com que seja bem provável que hajam erros
no processo. Mas já vimos que as equações da álgebra de Boole podem ser
visualizadas através de um diagrama de Venn. Isto é exemplificado na figura 1,
que apresenta um diagrama de Venn de 3 variáveis com os respectivos mintermos
associados a cada uma das regiões.
c
abc
abc
abc
abc
a
b
abc
abc
abc
abc
(a) Regiões das variáveis
(b) Sub-regiões dos mintermos
Figura 1: Diagrama Venn com 3 variáveis.
Utilizando os diagramas, é fácil obter a equação simplificada da função. Por
exemplo, considere-se a função f1 = abc + abc + abc. Desenhando esta função
num diagrama de Venn (figura 2), fica óbvio que podemos simplificá-la para
f1 = (a + c)b.
O problema aparece quando acrescentamos mais 1 variável. Como fazer um
diagrama definindo todas as 16 possibilidades? A solução para isto é desenhar
1 Aparentemente
ele atualmente (entre outras coisas), escreve o blog unclej0.blogspot.com.
Esta informação depende em se acreditar ou não na wikipedia.
1
f1
Figura 2: Diagrama Venn definindo a região dada por f1 = abc + abc + abc =
(a + c)b.
as regiões como quadrados, e não como cı́rculos, assim como foi feito na figura
3. No lado direito desta figura temos até a representação do lado de fora do
diagrama propriamente dito de que regiões correspondem a que variáveis.
d
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
b
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
abcd
a
abcd
abcd
abcd
abcd
c
Figura 3: Diagrama Venn de 4 variáveis desenhado com regiões quadradas.
Este diagrama de Venn modificado já é o próprio mapa de Karnaugh, onde
no mapa as regiões em que a função é verdadeira são marcadas com 1, e em que
a função é falsa são marcadas com 0.
2
Mapas de Karnaugh
Cada região (quadrado) em um mapa de Karnaugh corresponde a uma linha
na tabela verdade. Ou seja, cada região corresponde a um mintermo e a um
maxtermo. A figura 4 mostra os mintermos correspondentes a cada uma das
regiões. Nela também está presente o número correspondente a cada mintermo
2
ou maxtermo.
d
abcd abcd abcd abcd
0
1
3
2
abcd abcd abcd abcd
4
5
7
6
b
abcd abcd abcd abcd
a
12
13
15
14
abcd abcd abcd abcd
8
9
11
10
c
Figura 4: Regiões correspondentes a mintermos de um mapa de Karnaugh
Note na figura 4 que os vizinhos de cada casa em um mapa de Karnaugh são
tais que apenas muda uma variável de cada vez. Por exemplo, da casa 5 para
a casa 1 (acima) só muda o b, da 5 para a 7 (direita) só muda o c, da 5 para a
4 (esquerda) só muda o d e da 5 para a 13 (abaixo) só muda o a. Isto é válido
para todas as casas.
É possı́vel aplicar isto inclusive para as casas nas bordas e nas quinas, pois
podemos considerar que o mapa dá a volta em si mesmo. Deste modo considerase a casa 6 como vizinha da 4 e só muda a variável c, e a casa 10 vizinha da 2 e
só muda a variável a.
Isto nos P
permite agrupar termos visualmente. Por exemplo, considere a
função f2 =
m (3, 7, 12, 13) e seu respectivo mapa de karnaugh na figura 5.
f2 =
P
m (3, 7, 12, 13)
d
abc
a
00
01
13
02
04
05
17
06
112
113
015
014
08
09
011
010
acd
b
c
Figura 5: Função f2 e simplificação por agrupamento de casas vizinhas.
Analisando a função f2 por álgebra de Boole, vemos que podemos simplificála aplicando o teorema T6. E observando no mapa de Karnaugh, os termos que
são unidos e simplificados são justamente os vizinhos.
f2 = abcd + abcd + abcd + abcd
|
{z
} |
{z
}
T6
T6
f2 = acd + abc
3
Ou seja, o agrupamento de 2 casas vizinhas corresponde à simplificação de
uma variável através da aplicação to teorema T6. Basta ver no próprio mapa
quais são as variáveis que não mudam dentro do agrupamento.
Para simplificar 2 ou mais variáveis basta aplicar o teorema repetidas vezes.
Simplifiquemos a função f3 (vide figura 6), por exemplo. Basta agruparmos a
função de duas em duas casas e 2 grupos vizinhos de duas casas viram um único
grupo de 4 casas, retirando mais uma variável da função.
f3 = abcd + abcd + abcd + abcd
{z
} |
{z
}
|
= abc + abc
| {z }
f3 = ac
d
f3
a
d
f3
00
01
03
02
04
05
07
06
112
113
015
014
18
19
011
010
b
⇒
a
00
01
03
02
04
05
07
06
112
113
015
014
18
19
011
010
c
b
c
Figura 6: Agrupamento das casas da função f3 .
Este mesmo procedimento pode ser mostrado para agrupamentos de 8 casas
(simplificando então 3 variáveis) ou 16 casas (simplificando 4 variá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 variáveis um
agrupamento de 16 casas seria todo o mapa e corresponderia a função 1.
2 Exemplos utilizados também no artigo original de Karnaugh: “The map method for
synthesis of combinational logic circuits”, de 1953.
4
bcd
0
0
a 0
0
d
0
1
1
0
abd
0
0
0
0
b
0
a 0
0
0
0
0
0
0
d
1
0
0
0
abd
0
1
0
0
b
0
a 0
0
0
1
0
0
0
c
d
0
0
0
0
bcd
1
1
0
0
b
0
a 0
0
1
0
0
0
0
c
d
0
0
0
0
0
0
0
0
c
0
0
b
0
0
c
(a) agrupamentos de 2 casas
cd
0
0
a 0
0
d
1
1
1
1
ab
0
0
0
0
b
0
a 0
0
1
0
0
0
0
d
0
0
0
1
ad
0
1
0
1
b
0
a 0
1
0
0
0
0
1
c
d
0
0
0
0
bd
1
1
1
0
b
0
a 0
0
1
0
0
0
0
c
d
0
0
0
0
0
0
0
0
c
1
0
b
0
1
c
(b) Agrupamentos de 4 casas
b
0
1
a 1
0
d
0
1
1
0
d
d
0
1
1
1
b
1
a 1
0
1
0
1
1
0
c
0
0
0
0
c
0
0
0
0
1
0
1
0
b
1
a 0
1
0
c
d
0
0
0
0
b
1
1
1
1
1
1
1
0
b
1
a 0
1
1
c
d
1
0
0
1
1
0
0
1
1
0
b
0
1
c
(c) Agrupamentos de 8 casas
Figura 7: Exemplos de mapas de karnaugh com os correspondentes produtos
algébricos.
5
2.1
Mapas de n variáveis
Claro que um mapa de Karnaugh pode ser feito com um número menor de
variáveis. Para tanto basta simplesmente sair dividindo o mapa. Tem-se apenas
que lembrar que uma casa deve ter n vizinhas, já que a simplificação de uma
variável corresponde a unir uma casa com a vizinha. Isto é mostrado na figura
8 para mapas de 2, 3 e 4 variáveis.
d
c
a
0
1
2
3
b
a
0
1
3
2
4
5
7
6
a
b
(a) Mapa de 2 (b) Mapa de 3 variáveis
variáveis
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
b
c
(c) Mapa de 4 variáveis
Figura 8: Mapas de Karnaugh de 2, 3 e 4 variáveis, mostrando que cada casa
tem n vizinhas.
Mas como aplicar este princı́pio para funções com mais de 4 variáveis?
É impossı́vel fazer um mapa no plano onde cada uma das regiões tem 5 (ou
mais) vizinhos. Uma maneira (não muito prática) é trabalhar com um mapa
tridimensional como exemplifica a figura 9 que mostra um mapa de Karnaugh
de 6 variáveis, note que cada casa tem 6 vizinhos: 4 no plano (como no mapa
de 4 variáveis) e 2 verticais.
Na prática, um mapa de 5 variáveis é desenhado como 2 de 4 variáveis, sendo
um com uma variável (em geral a mais significativa) sendo 0 e o outro com a
mesma variável sendo 1. Usa-se este mesmo princı́pio para mapas de 6 variáveis
ou mais variáveis, como pode ser visto na figura 10.
6
f
0
4
c
12
1
5
13
8
9
3
7
15
11
10
16
c
28
24
f
17
21
19
23
29
25
31
27
60
56
49
51
55
61
57
63
59
44
40
f
33
37
35
39
45
41
d
58
32
c
50
54
62
e
36
b
f
53
a
d
26
48
c
18
22
30
e
52
d
14
e
20
2
6
47
43
34
38
d
46
42
e
Figura 9: Mapa de Karnaugh tridimensional de 6 variáveis.
b
f
c
0
1
3
2
4
5
7
6
12 13 15 14
8
a
f
16 17 19 18
20 21 23 22
d
c
9 11 10
28 29 31 30
24 25 27 26
e
e
b
f
f
48 49 51 50
1
3
2
16 17 19 18
32 33 35 34
4
5
7
6
20 21 23 22
36 37 39 38
12 13 15 14
8
9 11 10
c
b
28 29 31 30
c
a
c
24 25 27 26
d
e
e
0
44 45 47 46
40 41 43 42
d
52 53 55 54
d
c
60 61 63 62
56 57 59 58
e
(b) 6 variáveis
(a) 5 variáveis
Figura 10: Mapas de Karnaugh de 5 e 6 variáveis.
7
d
e
d
3
Soma de produtos e produto de somas
Até o momento trabalhamos com o mapa de Karnaugh agrupando os 1’s para
gerar funções na forma soma de produtos, mas podemos agrupar os zeros também, gerando equações na forma produto de somas, como mostra a figura 11
para a funçãof4 = ac + a(b + cd).
f4 (a, b, c, d)
d
a+b+c
a
00
01
13
02
14
15
17
16
112
113
015
014
18
19
011
010
b+c+d
b
a+c
c
Figura 11: Mapa de Karnaugh com agrupamento de 0’s.
Da mesma forma que na tabela verdade, um 0 no mapa de Karnaugh corresponde a um maxtermo. Logo o agrupamento de 2 casas com 0 corresponde
a uma soma com n − 1 termos (onde n é o número de variáveis da função), o
agrupamento de 4 casas equivale a uma soma de n − 2 variáveis e assim por
diante.
No caso de agrupamento de zeros, deve-se tomar cuidado com a relação entre
uma região marcada e como a variável aparece na equação. Por exemplo, na
figura 11 a região a + c ocorre onde está marcado a no mapa, e não onde está
marcado a. A explicação para este fenômeno é a mesma dos maxtermos na
tabela verdade terem as variáveis barradas em relação aos mintermos correspondentes. Isto torna a análise do mapa por agrupamento de 0’s bem menos
intuitiva.
d
f5
1
0
0
1
1
4
1
1
7
6
1
13
1
8
2
0
0
1
0
3
5
12
a
0
1
1
15
14
1
9
b
1
11
10
c
Figura 12: Exemplo de equação minimizada por agrupamento de 1’s e de 0’s.
A partir do mapa de Karnaugh, podemos obter a equação na forma produto
de somas, juntando os zeros; ou na forma soma de produtos, juntando os uns.
8
As duas formas obtidas da função f5 da figura 12 são mostradas abaixo e apesar
de aparentarem ser diferentes, elas sã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)
Começando da equação na forma produto de somas, multiplicamos os dois
primeiros parênteses e os dois últimos e obtemos:
f5 = a + a b + a d + b + b d + b c + a d + c d · (3)
· ab + ac + ad + ac + bc + cd + ad + bd + cd + d
Retirando os vários termos redundantes, chega-se a:
f5 = a + b + c d a b + a c + d + a c + b c
(4)
Multiplicando novamente, obtê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 vá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 último
termo, retirando então o terceiro termo. Com isso, obtém-se a equação (2)
obtida por soma de produtos.
Mostra-se então que a equação (1) é equivalente à (2), q.e.d..
4
Equações e circuitos não-completamente especificados.
É bastante comum a situação de que determinadas entradas de um circuito ló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 serão acionados ao mesmo tempo; nesta situação não
importa qual é o resultado do circuito para se = sd = 1, já que esta situação
nunca vai existir, portanto não é necessário especificar um valor de saı́da para
esta situação. Diz-se então que este circuito é não-completamente especificado.
A tabela 1 mostra o exemplo de um sinal imaginário z determinado em
função de a, se e sd . Neste exemplo, sempre que se = sd = 1 a saı́da z é nãoespecificada, ou seja, z não-importa nestas situações. Neste texto utilizaremos
a notação ×3 para identificar as situações que um sinal não importa.
Pode-se descrever uma função lógica não-completamente especificada na
forma soma de mintermos ou produto de maxtermos utilizando a notação d(· · · ),
que vem do inglês don’t care. Desta forma o sinal z pode ser descrito por:
X
Y
z=
(2, 4, 6) + d(3, 7) =
(0, 1, 5) + d(3, 7)
(7)
m
3“dontchiquer,
M
bicho.”
9
a
0
0
0
0
1
1
1
1
se
0
0
1
1
0
0
1
1
sd
0
1
0
1
0
1
0
1
z
0
0
1
×
1
0
1
×
Tabela 1: Exemplo de uma função não completamente especificada. As saı́das
não especificadas são identificadas por ×. Outras notações comumente usadas
são *, - ou d.
Um × na saı́da pode ser implementado como um 1 ou um 0, e não se sabe
a princı́pio qual destes dois valores gerará uma solução mais minimizada, logo
para obter o menor circuito possı́vel o engenheiro deveria obter as equações
considerando que cada × pode ser 1 ou 0 e checar qual é o menor circuito final.
Obviamente para problemas com muitos ×’s isto se torna impraticável, pois
seria necessário implementar 2k circuitos, onde k é o número de ×’s presentes.
Felizmente o mapa de Karnaugh facilita bastante a implementação de circuitos não-completamente especificados, pois podemos considerar se determinado
× é 1 ou 0 visualmente, na hora da implementação.
sd
z
0
×
0
0
a
1
1
1
3
×
0
4
5
2
1
7
6
se
Figura 13: Mapa de Karnaugh da função z.
Ao minizarmos a função z pelo mapa de Karnaugh (figura 13) obtemos 2
funções:
z 0 = se + sd a
z 00 = sd (se + a)
(pelos 1’s)
(pelos 0’s)
(8)
(9)
Note que, neste caso, estas duas equações não são equivalentes; ou seja, não é
possı́vel sair de uma delas e chegar na outra por álgebra de Boole, como já foi
feito na seção 3 para f5 . Isto porque na minimizaçã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 situação é bastante comum ao minimizar funções não completamente
especificadas, porém, apesar de estranho, não causa nenhum problema, já que as
diferenças nas saı́das ocorrem justamente quando não importa o valor da saı́da,
seja por que aquela entrada nunca ocorre ou por outra razão qualquer.
10