SD Unid I Mapas Karnaugh 2013

Prévia do material em texto

1
UNIDADE I: Álgebra 
das Variáveis Lógicas
1.3
1.1
1.2
1.4
Variáveis e Funções Lógicas
Portas Lógicas
Álgebra de Boole
Simplificação de Funções Lógicas.
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 2
1.4.1 – Formas Canônicas das Funções Lógicas
1.4.1.1 – Soma Padrão de Produtos
1.4.1.3 – Mintermos e Maxtermos
1.4.3.1 – Funções Não Expressas por Mintermos 
1.4 – Simplificação de Funções Lógicas
1.4.2 – Mapas de Veitch Karnaugh (Mapas K)
1.4.1.2 – Produto Padrão de Somas
1.4.3.2 – Funções Incompletamente Especificadas
1.4.3 – Simplificação de Funções Lógicas com Mapa K
1.4.4 – Método Tabular de Quine-McCluskey
2
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 3
1.4 – Simplificação de Funções Lógicas
A equivalência de circuitos combinacionais pode ser
estabelecida partindo-se da simplificação da expressão
booleana que descreve um circuito original.
Neste momento torna-se conveniente o estudo de
processos mais gerais e sistemáticos que conduzam a
simplificações booleanas eficazes.
Até então, o processo de simplificação de expressões
booleanas dependia de nossa habilidade em reconhecer
quais teoremas podiam ser usados com eficiência.
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 4
1.4.1 – Formas Canônicas das Funções Lógicas
Quando é inviável a construção da tabela verdade, o
primeiro passo para obter o Mapa de Karnaugh consiste
em reescrever a expressão booleana original como uma
soma produtos (ou um produto de somas).
Um dos processos sistemáticos de simplificação de
expressões booleanas mais utilizado é conhecido como
Mapa de Karnaugh (ou Mapa K).
Uma forma rápida de obter o Mapa K é através da
tabela verdade, a qual é construída a partir da
expressão booleana original que descreve o circuito.
3
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 5
Ex1.4.1-1.: Dada a função lógica de quatro variáveis
expressar a função como uma soma de produtos.
f (A, B, C, D) = (A + BC)(B + CD) (1.4-1)
Sol.: Usando a lei distributiva [Eq. (1.2-9b)] em 1.4-1, 
vem:
f (A, B, C, D) = AB + ACD + BBC + BCCD (1.4-2)
B 0
f (A, B, C, D) = AB + ACD + BC (1.4-3)
Ex1.4.1-2.: Dada a função lógica de cinco variáveis 
expressar a função como uma soma de produtos.
f (A, B, C, D, E) = (A + BC)(D + BE) (1.4-4)
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 6
Sol.: Usando o teorema de De Morgan [Eqs. (1.2-12a)
e (1.2-12b)] e a lei distributiva, obtemos:
f (A, B, C, D, E) = (A + B + C)(BD + DE) (1.4-7)
f (A, B, C, D, E) = (A + B + C)[D (B + E)] (1.4-6)
f (A, B, C, D, E) = (A + B + C)[D (BE)] (1.4-5)
f (A, B, C, D, E) = ABD + ADE + BD + 
+ BDE + BCD + CDE (1.4-8)
Na situação em que somente variáveis individuais
aparecem complementadas, como no Ex1.4.1-1, é
necessário apenas usar a lei distributiva.
4
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 7
Se um sinal de complemento aparecer sobre uma
combinação de variáveis, como no Ex1.4.1-2, primeiro
usa-se o teorema de De Morgan repetidamente, até que
o sinal de complemento apareça apenas sobre variáveis
individuais. Feito isso, utiliza-se a lei distributiva.
Após obtermos uma expressão booleana na forma de
soma de produtos (ou produtos de somas), o passo que
segue é a padronização da soma de produtos (ou
produto de somas).
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 8
Ex1.4.1.1.: Dada a função lógica de três variáveis:
reescrever a função como uma expressão em que todas
as variáveis aparecem em cada parcela da soma.
f (A, B, C) = A + BC (1.4-9)
1.4.1.1 – Soma Padrão de Produtos
São duas as formas padrão nas quais as funções
lógicas podem ser expressas: soma padrão de produtos
e produto padrão de somas. 
Sol.: Na primeira parcela de 1.4-9 as variáveis B e C
não estão presentes. Para as introduzir, multiplica-se a
referida parcela pelo elemento neutro (B + B)(C + C).
5
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 9
De modo análogo, a segunda parcela de 1.4-9 deve
ser multiplicada por (A + A).
f (A, B, C) = ABC + ABC + ABC + ABC + ABC + ABC 
(1.4-11)
f (A, B, C) = A + BC = A(B + B)(C + C) + (A + A)BC 
(1.4-10)
f (A, B, C) = ABC + ABC + ABC + ABC + ABC 
(1.4-12)
A função f (A, B, C) agora está na forma padrão de
soma de produtos.
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 10
Entenda-se por “padrão” o fato de que cada uma das
variáveis A, B e C aparece (às vezes complementada, às
vezes não) em cada uma das parcelas da soma. Cada
uma dessas parcelas é chamado de mintermo.
1.4.1.2 – O Produto Padrão de Somas
Uma expressão lógica também pode ser escrita na
forma de um produto padrão de somas. Utilizando os
mesmos exemplos anteriores, veremos tal afirmação é
verdadeira.
6
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 11
Ex1.4.1.2-1.: Dada a função lógica de quatro variáveis 
expressar a função como uma produto de somas.
f (A, B, C, D) = (A + BC)(B + CD) (1.4-13)
Sol.: Usando a Eq. (1.2-9a) em (1.4-13), vem:
f (A, B, C, D) = (A + B)(A + C)(B + C)(B + D) (1.4-14)
Ex1.4.1.2-2.: Dada a função lógica de cinco variáveis 
expressar a função como um produto de somas.
f (A, B, C, D, E) = (A + BC)(D + BE) (1.4-15)
Sol.: Aplicando o teorema de De Morgan, obtém-se:
f (A, B, C, D, E) = (A + B + C) D (B + E) (1.4-16)
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 12
Ex1.4.1.2-3.: Dada a função lógica de três variáveis: 
reescrever a função como uma expressão em que todas
as variáveis aparecem em cada fator do produto.
f (A, B, C) = A(B + C) (1.4-17)
Sol.: No primeiro fator de 1.4-17 as variáveis B e C
não estão presentes. Para introduzir tais variáveis, o
elemento neutro BB + CC é adicionado ao fator.
f (A, B, C) = (A + BB + CC)(AA + B + C) (1.4-18)
De modo análogo, o elemento neutro AA deve ser
adicionado ao segundo fator de 1.4-17.
7
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 13
Aplicando repetitivamente a lei distributiva na
forma da Eq. (1.2-9a), obtém-se:
f (A, B, C) = (A + B + C)(A + B + C)(A + B + C)
(A + B + C)(A + B + C)(A + B + C) (1.4-20)
f (A, B, C) = (A + B + C)(A + B + C)(A + B + C)
(A + B + C)(A + B + C) (1.4-21)
A função f (A, B, C) encontra-se agora sob a forma
padrão de produto de somas.
f (A, B, C) = (A + BB + C)(A + BB + C)
(A + B + C)(A + B + C) (1.4-19)
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 14
Os fatores presentes no produto padrão de somas
são denominados maxtermos.
Uma função lógica pode ser especificada de maneira
muito conveniente usando a convenção adotada para a
numeração dos mintermos e maxtermos.
1.4.1.3 – Mintermos e Maxtermos
Seja a função presente na Eq. (1.4-12). Colocando os
mintermos presentes nessa função em ordem crescente
de numeração, obtém-se:
8
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 15
f (A, B, C) = ABC + ABC + ABC + ABC + ABC (1.4-22)
Para mintermos, as variáveis não complementadas
são representadas por 1 e as variáveis complementadas
são representadas por 0 (vide 2ª linha de 1.4-22).
100011 101 110 111
3 4 5 6 7
Na 3ª linha de 1.4-22 os números binários foram
substituídos pelos seus equivalentes decimais.
f (A, B, C) = m3 + m4 + m5 + m6 + m7 (1.4-23)
Pode-se agora reescrever 1.4-22 como segue:21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 16
Uma forma mais compacta para 1.4-23 é:
f (A, B, C) = m(3, 4, 5, 6, 7) = (3, 4, 5, 6, 7) (1.4-24)
f (A, B, C) = M(0, 1, 2, 3, 6) = (0, 1, 2, 3, 6) (1.4-27)
000
Analisa-se agora a função presente na Eq. (1.4-21):
f (A, B, C) = (1.4-25)
= (A + B + C)(A + B + C)(A + B + C)(A + B + C)(A + B + C)
001 010 011 110
0 1 2 3 6
f (A, B, C) = M0 . M1 . M2 . M3 . M6 (1.4-26)
9
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 17
Uma função lógica pode ser expressa em uma tabela
verdade como um soma de mintermos ou como um
produto de maxtermos.
f (A, B, C) = (2, 3, 5, 7)
11117
00116
11015
00014
11103
10102
01001
00000
f (A, B, C)CBANº da linha
Fig. 1.27 – Tabela verdade de 
uma função lógica f (A, B, C). 
A função definida pela tabela 
pode ser expressa como uma 
soma de mintermos ou como 
um produto de maxtermos.
f (A, B, C) = (0, 1, 4, 6)
ou
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 18
Uma função na forma de soma de mintermos deve
incluir precisamente os mintermos cujos números
correspondem às linhas na tabela verdade onde f = 1.
Quando a função é expressa na forma de produto de
maxtermos, os maxtermos que devem ser incluídos
correspondem aos números das linhas da tabela
verdade onde f = 0.
Para obter o complemento de uma função, troca-se
cada f = 0 por f = 1 na tabela verdade.
Ex1.4.1.2-4.: f (A, B) = (0, 1, 3)  f (A, B) = (0, 1, 3)
10
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 19
Um mapa K é uma figura geométrica que contém
uma região (quadrículo) para cada linha da tabela
verdade.
Já ficou observado uma correspondência biunívoca
entre as linhas da tabela verdade e os maxtermos e
mintermos em potencial.
Agora será observado uma correspondência entre os
quadrículos do mapa K e os mintermos, bem como os
quadrículos e os maxtermos.
1.4.2 – Mapas de Veitch Karnaugh
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 20
 Mapa K para uma variável.
Fig. 1.28 – Três esquemas alternativos para identificar
os quadrículos em um mapa K de uma variável.
0 1
(a)
10
A
(b)
A
(c)
O número de quadrículos em um mapa K é igual ao
número de linhas da tabela verdade (2n° de variáveis).
10
A
0 1
Fig. 1.29 – A correspondência entre uma tabela verdade
de uma variável e um mapa K de uma variável.
11
00
f (A)ALinha nº
11
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 21
Ex1.4.2 .: Utilizando um mapa K de duas variáveis
obtenha a função f (A, B) que gera a tabela verdade
apresentada na Fig. 1.31a.
 Mapa K para duas variáveis.
Fig. 1.30 – Uma tabela verdade de duas variáveis e seu Mapa K.
01
00
f (A, B)ALinha nº
13
12
1
0
B
1
0
A
10
0 2
1 3
B
0
1
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 22
1
0 1
0
01
00
f (A, B)ALinha nº
13
12
1
0
0
1
1
0
B
1
0
(a)
Fig. 1.31 – (a) Uma tabela verdade definindo uma função. 
(b) A definição da tabela verdade em um mapa K. 
(c) Um mapa com os 1s registrados. 
(d) Um mapa com os 0s registrados.
A
0
0
10
0 2
1 3
B
0
1
(d)(c)
A
1
1
10
0 2
1 3
B
0
1
(b)
A
10
0 2
1 3
B
0
1
12
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 23
No mapa Karnaugh é suficiente concentra-se apenas
na leitura dos 1s (mintermos) ou apenas na leitura dos
0s (maxtermos).
Partindo da leitura dos 1s pode-se verificar que a
função definida na tabela verdade da Fig. 1.29 é dada
pela soma de mintermos:
f (A, B) = m0 + m3 = AB + AB (1.4-28)
f (A, B) = M1 . M2 = (A + B)(A + B) (1.4-29)
Por outro lado, a leitura dos 0s permite reescrever a
mesma função como um produto de maxtermos:
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 24
Uma maneira alternativa de escrever um mapa K
para duas variáveis é apresentado na Fig. 1.32.
00 01 11 10
AB
0 1 3 2
A
B
Fig. 1.32 – Um mapa alternativo 
para duas variáveis. 
 Mapa K para três variáveis.
A
0
1
00 01 11 10
AB
C
0 2 6 4
1 3 7 5
B
C
Fig. 1.33 – O mapa K para 
três variáveis. 
13
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 25
 Mapa K para quatro variáveis.
A
00
01
00 01 11 10
AB
CD
0 4 12 8
1 5 13 9
B
C
D3 7 15 11
2 6 14 10
11
10
Fig. 1.34 – O mapa K para 
quatro variáveis. 
A numeração dos 24 = 16 quadrículos do mapa K de
quatro variáveis depende da significância numérica e
da associação das variáveis (ABCD, DCBA, CDAB, ...)
com as linhas e colunas do mapa (vide Fig. 1.35).
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 26
Fig. 1.35 – Atribuições alternativas de significância numérica e 
de associação de variáveis com linha e colunas são permitidas. 
00
01
00 01 11 10
CD
AB
0 1
4 5
15 14
8 9 11 10
11
10
3 2
7 6
12 13
00
01
00 01 11 10
DC
BA
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
11
10
1.4.3 – Simplificação de Funções com Mapa K
Nos mapas K, quadrículos adjacentes na horizontal e
vertical (mas não na diagonal) equivalem a mintermos
ou maxtermos que diferem em apenas uma variável.
14
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 27
00
01
00 01 11 10
AB
CD
11
10
11
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
Fig. 1.36 – Mintermos em 
quadrículos adjacentes podem 
ser combinados. 
Considerando, por exemplo, os mintermos m8 e m12,
horizontalmente adjacentes no mapa K da Fig. 1.34,
tem-se:
m8(8=1000) = ABCD (1.4-30)
m12(12=1100) = ABCD (1.4-31)
+
 m8 + m12 = ACD (1.4-32)
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 28
No mapa K, qualquer par de mintermos adjacentes
pode ser combinado em um único termo, que inclui
uma variável a menos que os mintermos originais.
Outra maneira de obter o mesmo resultado anterior é
utilizando abstrações do diagrama de Venn.
D
A
1
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
1
Fig. 1.37 – Um método 
alternativo de identificação dos 
quadrículos em um mapa K. 
ACD
Interseção das
regiões A, C e D
15
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 29
Mintermos geometricamente adjacentes no mapa K
são também logicamente adjacentes. Entretanto, há
casos que embora os quadrículos não sejam
geometricamente adjacentes os mintermos o são.
D
AAB
CD
B
C
11
1
1
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
1
Fig. 1.38 – Simbolismos alternativos que indicam quadrículos 
do mapa que não são geometricamente adjacentes. 
D
AAB
CD
B
C
11
1
1
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
1
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 30
Pode-se visualizar uma adjacência geométrica entre
as colunas da esquerda e da direita imaginado o mapa
enrolado sobre um cilindro vertical.
Analogamente, uma adjacência geométrica entre as
linhas superior e inferior pode se visualizada enrolando
o mapa sobre um cilindro horizontal.
Todas estas adjacências podem ser simultaneamente
visualizadas imaginando-se o mapa enrolado sobre um
toróide.
16
21/03/2011SistemasDigitais Prof. MSc. Edson S. C. Silva 31
m8 + m12 = ACD (1.4-33)
m2 + m3 = ABC (1.4-34)
Seja o mapa K preenchido como na Fig. 1.38. 
11
1
D
A
1
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
1
m2 + m10 = BCD (1.4-35)
A soma dos três pares de mintermos envolvidos
pelos “círculos”, produz:
f(A, B, C, D) = m(2, 3, 8, 10, 12) = ACD + ABC + BCD
(1.4-36)
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 32
m8 + m10 = ABD (1.4-37)
f(A, B, C, D) = m(2, 3, 8, 10, 12) = ACD + ABC + ABD
(1.4-38)
Se assim for desejado, pode-se combinar o mintermo
m10 com m8, em vez de m2, obtendo, então:
m8 + m12 = ACD
m2 + m3 = ABC
11
1
D
A
1
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
1
17
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 33
Pode-se mostrar que as funções descritas em (1.4-36)
e (1.4-37) são equivalentes.
ACD
ABC
BCD
ACD + ABC + BCD
Fig. 1.39 – Implementação da função
apresentada na Eq. (1.4-40)
B C DA
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 34
Analogamente, se 2n quadrículos são adjacentes, eles
podem ser combinados resultando um termo no qual n
variáveis são eliminadas.
Observou-se que dois quadrículos adjacentes em um
mapa K podem ser combinados, resultando um termo
no qual uma variável é eliminada.
m1 + m5 = ACD (1.4-39)
Grupos típicos de quatro quadrículos são mostrados
nas Figs. 1.40 e 1.41. Em particular, na Fig. 1.38a as
combinações m1 + m5 e m3 + m7 produzem:
m3 + m7 = ACD (1.4-40)
18
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 35
Somando (1.4-39) com (1.4-40), obtém-se:
(1, 5, 3, 7) = ACD+ ACD = AD(C + C) = AD (1.4-41)
A leitura do mapa da Fig. 1.38b conduz a:
f(A, B, C, D) = (0, 2, 8, 10) = BD (1.4-42)
11
D
A
11
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
(a)
Fig. 1.40 – Duas adjacências envolvendo quatro quadrículos.
11
1
D
AAB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
1
(b) BDAD
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 36
D
A
1111
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
(a)
Fig. 1.41 – Outras duas adjacências com quatro quadrículos.
11
D
A
11
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
(b)
f(A, B, C, D) = (1, 5, 9, 13) = CD (1.4-43)
Lendo o mapa da Fig. 1.41a obtém-se:
f(A, B, C, D) = (4, 6, 12, 14) = BD (1.4-44)
Finalmente o mapa da Fig. 1.41b permite escrever:
CD BD
19
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 37
Grupos típicos de oito quadrículos são mostrados na
Fig. 1.40.
Na Fig. 1.42a obtém-se f = A, pois oito 1s estão fora
do intervalo A e dentro e fora de B, C e D.
A
Fig. 1.42 – Adjacências representativas de oito quadrículos.
1111
1
D
A
11
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
1
(b)
11
11
1
D
A
11
1
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
(a) D
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 38
Na Fig. 1.42b obtém-se f = D, pois oito 1s estão fora
do intervalo D e dentro e fora de A, B e C.
Consideremos agora alguns casos em que os valores
trabalhados no mapa K são 0s (maxtermos), ao invés de
1s (mintermos).
As regras para agrupar zeros e para determinar se
uma variável é eliminada ou não, seguem preservadas.
Entretanto, ao ler um grupo de zeros o resultado é uma
soma e não um produto; adicionalmente, a regra que
determina se uma variável aparece complementada ou
não, é invertida.
20
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 39
A + C + D (1.4-45)
A + C (1.4-46)
M11.M15 =
M0.M1.M4.M5 =
B (1.4-47)
Fig. 1.43 – Adjacências 
representativas usando 0s.
M0.M1.M2.M3.M8.M9.M10.M11 =
 f (A, B, C, D) = (A + C + D) (A + C) B 
00
0
D
A
00
0
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
0
0
0
0
0
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 40
 Mapa K para cinco variáveis.
Fig. 1.44 – O mapa K de cinco variáveis mais usado.
00
01
00 01 11 10
BC
DE
C
11
10
D
17
19
18
16
21
23
22
20
25
27
26
24
29
31
30
28
A = 1
BB
00
01
00 01 11 10
BC
DE
C
D
11
10
E
0 4 8
1 5 13 9
3 7 15 11
2 6 14 10
12
A = 0
Todas as adjacências em um mapa K de quatro
variáveis são válidas para o mapa de cinco variáveis.
21
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 41
BCDE
BCDEABE ABCDBCDE
Fig. 1.45 – O mapa K de cinco variáveis mais usado ilustrando 
algumas situações de adjacência. Notação completa.
00
01
00 01 11 10
BC
DE
C
11
10
D
1
1
1
1
17
19
18
16
21
23
22
20
25
27
26
24
29
31
30
28
A = 1
BB
00
01
00 01 11 10
BC
DE
C
D
11
10
E
111
11
1
0 4 8
1 5 13 9
3 7 15 11
2 6 14 10
12
A = 0
Adicionalmente, cada quadrículo da parte A = 0 é
adjacente ao quadrículo correspondente da parte A = 1.
K Map
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 42
B
C
D
E
1
111
1
0 4 8
1 5 13 9
3 7 15 11
2 6 14 10
12
D
C
B
A
11
1
1
1
11
17
19
18
16
21
23
22
20
25
27
26
24
29
31
30
28
Fig. 1.46 – O mapa K de cinco variáveis mais usado ilustrando 
outras situações de adjacências. Notação simplificada.
BCDE BCDEBCDE
ACDE
Ex1.4.2.1-1.: Identifique e agrupe todos os mintermos
presentes no mapa K de cinco variáveis da Fig. 1.46.
ACEABC
K Map
22
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 43
 Mapa K para seis variáveis.
Seguindo-se os mesmos passos para a construção do
mapa de cinco variáveis, pode-se obter um mapa K
para seis variáveis.
Todas as situações de adjacência usuais continuam a
existir para cada uma das quatro partes do mapa.
A Fig. 1.47 apresenta o mapa K de seis variáveis e
algumas situações de adjacência.
Em adicional, existem termos adjacentes horizontal
e verticalmente entre as quatro partes do mapa.
Sistemas Digitais Prof. MSc. Edson S. C. Silva
Fi
g.
 1
.4
5 
–
O
 m
ap
a 
K
 d
e 
se
is
 v
ar
iá
ve
is
.
A
E
F
C
D
B
1
1
49
51
50
48
53
55
54
52
57
59
58
56
61
63
62
60
EF
CD
CD
1
1
0 4 8
1 5 13 9
3 7 15 11
2 6 14 10
12
EF
00
01
00 01 11 10
11
10
C
D
11
33
35
34
32
37
39
38
36
41
43
42
40
45
47
46
44
EF
CD
00
01
11
10
E
F
00 01 11 10
1
117
19
18
16
21
23
22
20
25
27
26
24
29
31
30
28
CD
EF
21/03/2011 44
ACDEF
BCDEF
BCDEF ACDEF K Map
23
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 45
O mérito do mapa de Veitch Karnaugh é permitir a
visualização de termos.
Quando o número de variáveis cresce (sete ou mais,
por exemplo), o mapa K torna-se tão grande, que seu
valor no reconhecimento dos termos adjacentes torna-se questionável.
Assim, para o caso de muitas variáveis, métodos
tabulares (como o de Quine-McCluskey) são preferidos.
O mapa de Karnaugh pode ser usado para simplificar
a função lógica seguindo os princípios a seguir.
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 46
 As combinações devem incluir o maior número
possível de quadrículos de modo que todos eles sejam
incluídos pelo menor número possível de combinações.
 A combinação de quadrículos (mintermos) que for
selecionada deve incluir todos os quadrículos ao menos
uma vez. Como visto antes, um quadrículo qualquer
pode aparecer em mais de uma combinação.
A preocupação em encontrar combinações em um
mapa K que incluam o maior número possível de
quadrículos pode causar problemas (vide Fig. 1.48).
24
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 47
(a)
1
111
D
A
111
1
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
(b)
11
11
1
D
A
11
1
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
Fig. 1.48 – Duas ilustrações de problemas associados com 
formação de combinações no mapa K.
O algoritmo que segue, quando aplicado a um mapa
K, leva à expressão mínima para a função lógica,
evitando, ainda, o problema descrito anteriormente.
K Map
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 48
1 – Assinalar e considerar como implicante primo
essencial qualquer quadrículo que não possa ser
combinado com nenhum outro quadrículo.
2 – Identificar e assinalar quadrículos que podem ser
combinados com um único outro quadrículo de uma só
maneira. Quadrículos que podem ser combinados em
grupos de dois, de mais de uma maneira, são deixados
temporariamente de lado.
3 – Marcar quadrículos que podem ser combinados
com três outros quadrículos somente de uma maneira.
25
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 49
4 – Repetir o processo para grupos de oito, etc.
Novamente um quadrículo que pode ser combinado
num grupo de quatro, de maneira não única, deve ser
deixado temporariamente de lado.
Se os quadrículos de tais combinações ainda não
estiverem incluídos em grupos de dois, assinalar a
combinação de quatro.
5 – Se ainda restarem quadrículos não incluídos em
grupamentos, eles podem ser combinados uns com os
outros ou com os quadrículos de outros grupamentos.
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 50
Ex1.4.2.1-2.: Use o mapa de Karnaugh para minimizar a
função f (A, B, C, D) = m(0, 2, 3, 4, 5, 7, 8, 9, 13, 15).
 f (A, B, C, D) = ACD + ABC + ABC + BD 
BDABC
ACD ABC
Fig. 1.49 – Mapa K 
do Exemplo 1.4.2.1-2
1
111
1
D
A
111
1
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
1
Sol.: Identificando os mintermos no mapa, vem:
K Map
26
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 51
Ex1.4.2.1-3.: Use um mapa K para minimizar a função
lógica f (A, B, C, D) = m(0, 1, 3, 5, 6, 9, 11, 12, 13, 15).
ABCD
ABC
AD
BD
CD
ABC
 f (A, B, C, D) = ABCD + ABC + ABC + CD + BD + AD 
1
111
1
D
A
1111
1
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
Fig. 1.50 – Mapa K 
do Exemplo 1.4.2.1-3
Sol.: Preenchendo os mintermos no mapa, obtém-se:
K Map
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 52
 f (A, B, C, D) = (A + C + D).(B + D).(C + D).(B + C)
A + C + D
B + D
C + D
B + C
Ex1.4.2.1-4.: Utilizando um mapa K, minimize a função
f (A, B, C, D) = M(0, 3, 4, 5, 6, 7, 11, 13, 14, 15).
Fig. 1.51 – Mapa K 
do Exemplo 1.4.2.1-4
00
0000
0
D
A
00
0
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
Sol.: Identificando os maxtermos no mapa, tem-se:
K Map
27
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 53
Ex1.4.2.1-1.: Analisar o mapa de Karnaugh da Fig. 1.52.
CE
 f (A, B, C, D) = ABCDE + ABCD + ABD + BDE + CE
ABD
ABCDE
ABCD
BDE
Ex1.4.2.1-6.: Interpretar o mapa K da Fig. 1.51.
Fig. 1.52 – Mapa K de cinco variáveis (Exemplo 1.4.2.1-5)
B
C
D
E
11
1
11
11
0 4 8
1 5 13 9
3 7 15 11
2 6 14 10
12
D
C
B
A
11
11
1 11
17
19
18
16
21
23
22
20
25
27
26
24
29
31
30
28
K Map
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 54
Fi
g.
 1
.5
3 
–
O
 m
ap
a 
K
 d
e 
se
is
 v
ar
iá
ve
is
.
A
E
F
C
D
B
1
1
1
11
11
49
51
50
48
53
55
54
52
57
59
58
56
61
63
62
60
EF
CD
CD
1
0 4 8
1 5 13 9
3 7 15 11
2 6 14 10
12
EF
00
01
00 01 11 10
11
10
C
D
1
1
1
33
35
34
32
37
39
38
36
41
43
42
40
45
47
46
44
EF
CD
00
01
11
10
E
F
00 01 11 10
1
1
11
11
17
19
18
16
21
23
22
20
25
27
26
24
29
31
30
28
CD
EF
ACDE
BCE
CDEF
ABCDF
K Map
28
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 55
11
AC
1
1
AB
BC
1
BC
1
C
B
1.4.2.2 – Funções Não Expressas por Mintermos.
Ex1.4.2.2.: Utilizando o mapa de Karnaugh simplifique
a função f (A, B, C) = AB + AC + BC + BC .
Sol.: Representando cada parcela em um mapa de K
de três variáveis e em seguida re-agrupando, tem-se:
A
0
1
00 01 11 10
AB
C
0 2 6 4
1 3 7 5
B
C
A
1111
110
1
00 01 11 10
AB
C
0 2 6 4
1 3 7 5
B
C
 f (A, B, C) = AB + AC + BC + BC = B + C K Map
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 56
1.4.2.3 – Funções Incompletamente Especificadas
Às vezes, simplesmente não nos interessa que valor
a função assume para certas combinações de variáveis.
Em outros casos, sabemos que certas combinações
de variáveis nunca ocorrem. Neste caso fingimos não
nos interessar, já que o efeito é o mesmo.
Ex1.4.2.3.: Utilizando o mapa de Karnaugh simplifique
a função incompletamente especificada f (A, B, C, D) =
m(1, 2, 5, 6, 9) + d(10, 11, 12, 13, 14, 15). A notação d
representa condições não-essenciais (don’t care).
29
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 57
CD
CD
Sol.: De acordo com a conveniência, ‘x’ pode assumir
o valor 0 ou 1. No mapa que segue, os ‘x’ envolvidos
por ‘círculos’ valem 1 e os não envolvidos valem 0.
XX11
XX
D
A
1X11
X
AB
CD
0 4 12 8
1 5 13 9
B
C
3 7 15 11
2 6 14 10
 f (A, B, C, D) = CD + CD = C  D K Map
21/03/2011Sistemas Digitais Prof. MSc. Edson S. C. Silva 58
Referências 
Bibliográficas
[1] Tocci, J. Ronald; Widmer, Neal S.; Sistemas Digitais;
Prentice Hall, 2007, 10ª Ed.
[2] Idoeta, Ivan V.; Capuano, Francisco G.; Elementos de
Eletrônica Digital; Érica, 2002, 34ª Ed.