Mapa de Karnaugh

Prévia do material em texto

oo RReevviissããoo ddaa aauullaa aanntteerriioorr 
oo IInnttrroodduuççããoo 
oo DDiiaaggrraammaass ppaarraa dduuaass vvaarriiáávveeiiss 
oo DDiiaaggrraammaass ppaarraa ttrrêêss vvaarriiáávveeiiss 
oo DDiiaaggrraammaass ppaarraa qquuaattrroo vvaarriiáávveeiiss 
oo DDiiaaggrraammaass ppaarraa cciinnccoo vvaarriiáávveeiiss 
 
 
 
 
 Alexandre da Silva Simões 
 
 
 
 
 
 
MMaappaass ddee 
KKaarrnnaauugghh 
Transparências de 
Circuitos Digitais 
AAuullaa 0055 
Diagrama de Veitch-Karnaugh 
 
 
Métodos para a simplificação de circuitos: 
1. Álgebra de Boole; 
2. Diagramas (ou mapas) de Veitch-Karnaugh; 
 
Origens: 
• Desenvolvidos por Edward Veitch (1952); 
• Aperfeiçoados por Maurice Karnaugh; 
 
Características do diagrama: 
• Simplificação mais rápida e intuitiva; 
• Pode ser aplicado a funções bastante 
complexas; 
• Requer a tabela-verdade da expressão; 
 
Descrição: 
 
O processo de minimização proposto por Veitch- 
Karnaugh consiste em um mapa com n células que 
serão preenchidas com os mintermos (ou 
eventualmente os maxtermos) da função. Esse mapa 
possibilita a visualização dos termos redundantes e sua 
simplificação de forma imediata; 
• mintermo: produto algébrico que contém todas as 
variáveis da função; 
• maxtermo: soma algébrica que contém todas as 
variáveis da função; 
Diagrama de Karnaugh para 2 var. 
 
 
Seja o mapa abaixo (mapa para duas variáveis): 
 
 
 
 
 
 
Célula Designação 
binária 
Designação algébrica 
(mintermo) 
Designação algébrica 
(maxtermo) 
1 00 A B
 
A + B 
2 01 A B
 
A + B 
3 10 A B
 
A + B 
4 11 A B
 
A + B 
 
Exemplo de representação de funções no mapa de 
Karnaugh: 
 
 
A B S 
0 0 0 
0 1 1 
1 0 1 
1 1 1 
 
B
 
B
 
A 1 2 
3 4 A
 
B
 
B
 
A
 
0 1 
1 1 A
 
Processo de minimização de funções 
 
 
 O processo de minimização de uma função via 
mapa de Karnaugh consiste em tentar agrupar regiões 
onde S=1 na seguinte seqüência: 
 
a) Quadra 
 
 
 
 
 
 
 Conjunto de 4 regiões. É o 
agrupamento máximo no 
diagrama de 2 variáveis. 
 
Expressão simplificada: 
A B + A B + A B + A B = 
A ( B + B ) + A ( B + B ) = 
A + A � 
S = 1 
b) Pares: 
 
 
 
 
 
 
 
 
 
 
 
 Conjunto de 2 regiões (na 
horizontal ou vertical). 
 
Expressão simplificada: 
A B + A B = 
A
 ( B + B ) 
�
 
S = A 
 
Expressão simplificada: 
B A + B A = 
B ( A + A ) 
�
 
S = B 
B
 
B
 
A 1 1 
1 1 A
 
B B
A
 
0 0 
1 1 A
 
B
 
B
 
A
 
1 0 
1 0 A
 
Processo de minimização de funções II 
 
 
c) Termos isolados 
 
 
 
 
 
 
 Casos em que não é 
possível simplificação: 
 
Expressão simplificada: 
S = A B + A B 
 
Exercício: 
 
Determinar a expressão minimizada para a tabela verdade: 
 
 A B S 
 0 0 1 
 0 1 1 
 1 0 1 
 1 1 0 
 
Diagrama para 3 variáveis 
 
 
O diagrama para 3 variáveis (8 células) é o 
mostrado abaixo: 
 
 
 
 
B
 
B
 
A
 
1 0 
0 1 A
 
CC C 
B
 
A
 
1 2 
5 6 A
 
B
 
3 4 
7 8 
Diagramas para 3 variáveis II 
 
 
 Exemplo de representação de função de 3 var.: 
 
 A B C S 
 0 0 0 1 
 0 0 1 0 
 0 1 0 1 
 0 1 1 1 
 1 0 0 1 
 1 0 1 0 
 1 1 0 0 
 1 1 1 1 
 
 
 
 
 
 
 
Simplificação de mapas com 3 variáveis 
 
 
Procurar pelos grupos a seguir na ordem apresentada: 
 
a) Oitava 
 
 
 
 
 
 
Agrupamento máximo no 
diagrama de 3 variáveis. 
 
Expressão simplificada: 
 
S = 1 
CC C 
B
 
A
 
1 0 
1 0 A
 
B
1 1 
1 0 
C
 
C
 
C
 
B
 
A
 
1 1 
1 1 A
 
B
 
1 1 
1 1 
Simplificação de mapas com 3 var. II 
 
 
 
b) Quadra 
 
 
 
 
 
 
 
(b-1) (b-2) 
 
 
 
 
 
 
 
 
b-1) Quadra S= A ; 
b-2) Quadra S= B ; 
b-3) Quadra S=C ; 
(b-3) 
 
 c) Pares 
 
 
 
 
 
 
 
 
 
 
 
C
 
C
 
C
 
B
A
 
1 1 
0 0 A
 
B
 
1 1 
0 0 
C
 
C
 
C
 
B
A
 
1 1 
1 1 A
 
B
 
0 0 
0 0 
C
 
C
 
C
 
B
 
A
 
1 0 
1 0 A
 
B
 
0 1 
0 1 
C
 
C
 
C
 
B
 
A
 
1 0 
0 1 A
 
B
0 1 
1 0 
Par A C 
Par A C 
Simplificação de mapas com 3 var. III 
 
 
d) Termos isolados 
 
 
 
 
 
 
 
 
Exercício: 
 
Determinar a expressão minimizada para a tabela verdade: 
 
 A B C S 
 0 0 0 1 
 0 0 1 0 
 0 1 0 1 
 0 1 1 1 
 1 0 0 1 
 1 0 1 0 
 1 1 0 1 
 1 1 1 0 
 
 
 
 
 
 
 
C
 
C
 
C
 
B
 
A
 
1 0 
0 1 A
 
B
 
0 0 
0 0 
Termo A B C 
Termo A B C 
Diagramas com 4 variáveis 
 
 
Seja o mapa de Veitch-Karnaugh de 4 variáveis (16 células): 
 
 
 
 
 
 
 
 
 
 
 
Simplificação de mapas com 4 variáveis 
 
 
Procurar pelo caso mais genérico: 
 
a) Grupo de 16 
Função Simplificada: 
 S = 1 
A seguir buscar os casos: 
 
b) Oitava; 
c) Quadra; 
d) Par; 
e) Termos isolados; 
 
 
 
 
 
 
 
 
 
 
 
C
 
A
 
1 2 
5 6 
B
 
C
 
3 4 
7 8 
D
 
D
 
D
 
B
 
9 10 
13 14 A 
11 12 
15 16 
B
C
 
A
 
1 1 
1 1 
B
 
C
1 1 
1 1 
D
 
D
 
D
 
B
1 1 
1 1 
A
 
1 1 
1 1 
B
 
Simplificação de mapas com 4 var. II 
 
 
 
Exercício: 
 
 A B C D S 
 0 0 0 0 0 
 0 0 0 1 1 
 0 0 1 0 0 
 0 0 1 1 1 
 0 1 0 0 0 
 0 1 0 1 1 
 0 1 1 0 1 
 0 1 1 1 1 
 1 0 0 0 1 
 1 0 0 1 1 
 1 0 1 0 0 
 1 0 1 1 1 
 1 1 0 0 1 
 1 1 0 1 1 
 1 1 1 0 0 
 1 1 1 1 1 
 
 Karnaugh de 2 a 4 variáveis - resumo 
 
 
• Diagramas de Veitch-Karnaugh - Passos: 
 
1. Desenhar o diagrama com o número de variáveis 
desejadas; 
2. Transportar a tabela-verdade para o diagrama; 
3. Procurar grupos de “1s” procurando sempre o maior 
grupo possível; 
4. Observar as variáveis irrelevantes (variáveis que 
assumem diferentes níveis lógicos para um mesmo 
grupo); 
 
• Diagrama para 2 variáveis – Procurar as figuras: 
a) Quadra (S=1); 
b) Par; 
c) Termo isolado; 
 
• Diagrama para 3 variáveis – Procurar as figuras: 
a) Oitava (S=1); 
b) Quadra; 
c) Par; 
d) Termo isolado; 
 
• Diagrama para 4 variáveis – Procurar as figuras: 
a) Grupo de 16 (S=1); 
b) Oitava; 
c) Quadra; 
d) Par; 
e) Termo isolado; 
E
 
E
 
A
 
A
 
E
 
E
 
C0 
 
B
 
C
 
 
D
 
D
 
 
 
 
 1 
B
 
C
 
E
 
E
 
C
 
 
 
B
 
C
 
 
1 
D
 
D
 
 
 
 
 
B
C
 
Diagramas para 5 variáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
(Total de células : 32) 
 
Exemplos de preenchimento do diagrama: 
 
 A B C D E S 
 0 0 0 0 0 0 
 0 1 0 1 0 1 
 1 0 1 1 1 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
EE
 
A A
 
E
 
E
 
C
 
1 2 
5 6 
B
 
C
 
3 4 
7 8 
D
 
D
 
9 10 
13 14 
11 12 
15 16 
B
 
C
 
E
 
E
 
C
 
17 18 
21 22 
B
 
C
 
19 20 
23 24 
D
 
D
 
25 26 
29 30 
27 28 
31 32 
B
 
C
 
Simplificação p/ diagr. de 5 variáveis 
 
 
Procurar pelas figuras abaixo nesta ordem: 
a) grupo de 32 (S=1); 
b) grupo de 16; 
c) oitava; 
d) quadra; 
e) par; 
f) termos isolados; 
 
Observação: O diagrama a partir de 5 variáveis para facilitar 
a simplificação deve ser enxergado de forma sobreposta 
 
 
 
Na prática, não é necessário desenhar os dois planos do 
mapa de Karnaugh sobrepostos. Basta o entendimento deste 
conceito e sua aplicação para os dois planos dispostos 
lateralmente. 
Quadra 
EDB 
Oitava 
CE 
Par 
EDCB 
Exemplo de simplificação p/ 5 variáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 a) Grupo de 32 Não 
 b) Grupo de 16 Não 
 c) Oitava DB
 
 
 d) Quadra EDC
 
 
 ABD
 
 
 e) Par EACD
 
 
 f) Termo isolado Não 
 
 
Função minimizada: 
 
S = DB + EDC + ABD + EACD 
 
 
E
 
E
A
 
A
 
E
 
E
 
C
 
1 1 
1 1 
B
 
C
 
0 0 
0 0 
D
 
D
 
0 0 
1 0 
0 0 
0 0 
B
 
C
 
E E
C
 
1 1 
1 1 
B
 
C
 
0 0 
0 1 
D
 
D
 
0 0 
1 0 
1 1 
1 1 
B
 
C
Exercício para 5 variáveis 
 
 
 
 A B C D E S 
 0 0 0 0 0 1 
 0 0 0 0 1 0 
 0 0 0 1 0 0 
 0 0 0 1 1 1 
 0 0 1 0 0 1 
 0 0 1 0 1 1 
 0 0 1 1 0 0 
 0 0 1 1 1 1 
 0 1 0 0 0 1 
 0 1 0 0 1 1 
 0 1 0 1 0 1 
 0 1 0 1 1 0 
 0 1 1 0 0 0 
 0 1 1 0 1 1 
 0 1 1 1 0 1 
 0 1 1 1 1 0 
 1 0 0 0 0 0 
 1 0 0 0 1 01 0 0 1 0 0 
 1 0 0 1 1 0 
 1 0 1 0 0 0 
 1 0 1 0 1 1 
 1 0 1 1 0 1 
 1 0 1 1 1 0 
 1 1 0 0 0 0 
 1 1 0 0 1 0 
 1 1 0 1 0 0 
 1 1 0 1 1 0 
 1 1 1 0 0 1 
 1 1 1 0 1 1 
 1 1 1 1 0 1 
 1 1 1 1 1 1 
 
Diagramas com condições irrelevantes 
 
 
 
Em casos práticos, podemos assumir que uma dada 
condição de entrada nunca vai ocorrer. Neste caso, a saída 
assume uma condição irrelevante (X), isto é, a saída pode ser 
0 ou 1 e é irrelevante qual ela seja, visto que nunca vai 
ocorrer. 
 Para a minimização dessa saída, podemos assumi-la 
como 0 ou 1 (o que melhor possibilitar o agrupamento). 
 
Exemplo para três variáveis: 
 
A B C S 
0 0 0 X 
0 0 1 1 
0 1 0 1 
0 1 1 1 
1 0 0 0 
1 0 1 0 
1 1 0 0 
1 1 1 0 
 
 
Caso assumamos X = 0 � Obteremos 2 pares; 
Caso assumamos X = 1 � Obteremos 1 quadra; 
 
Caso adotado: X=1 
�
 quadra A 
C
 
C
 
C
 
B
 
A
 
X 1 
0 0 A
 
B
 
1 1 
0 0 
Exercício com condições irrelevantes 
 
 
Exercício com 3 variáveis: 
 
 A B C S 
 0 0 0 1 
 0 0 1 X 
 0 1 0 0 
 0 1 1 0 
 1 0 0 1 
 1 0 1 X 
 1 1 0 0 
 1 1 1 0 
 
 
Exercício com 4 variáveis: 
 
 A B C D S 
 0 0 0 0 X 
 0 0 0 1 0 
 0 0 1 0 1 
 0 0 1 1 X 
 0 1 0 0 1 
 0 1 0 1 0 
 0 1 1 0 1 
 0 1 1 1 1 
 1 0 0 0 0 
 1 0 0 1 1 
 1 0 1 0 X 
 1 0 1 1 0 
 1 1 0 0 0 
 1 1 0 1 X 
 1 1 1 0 0 
 1 1 1 1 X 
 
Agrupamento de zeros 
 
 
 Uma alternativa ao agrupamento de “1”s é o 
agrupamento de “0”s. Porém, a variável encontrada com tal 
agrupamento não é mais S, mas sim S . 
 Exemplo: 
 
 A B C S 
 0 0 0 0 
 0 0 1 1 
 0 1 0 1 
 0 1 1 1 
 1 0 0 0 
 1 0 1 1 
 1 1 0 1 
 1 1 1 1 
 
 Resolução: 
 
 
 
 
 
 
 
CBS .=
 
�
 
CBCBS +== .
�
 
 
S = B+C 
 
C
 
C
 
C
 
B
 
A
 
0 1 
0 1 A
 
B
 
1 1 
1 1