Soma de Produtos
• Soma de produtos é uma forma padrão de representação de
funções Booleanas constituida pela aplicação da operação
lógica OU sobre um conjunto de termos formados pela
operação E:
Soma de produtos
Z = AB  AC  D’F
2 níveis lógicos
Circuitos Digitais
Termo produto
CIC - UnB
Produto de Somas
• O produto de somas é outra forma padrão de representação
de funções Booleanas caracterizada pela aplicação da
operação E sobre um conjunto de operações OU sobre as
entradas
Produto de Somas
Z = (A  B)(A  C)(D’  F)
2 níveis lógicos
Circuitos Digitais
Termo soma
CIC - UnB
Mintermos
• Um mintermo é um termo produto que vale 1 em apenas
um ponto do domínio de uma função Booleana
• É definido por um produto (AND) onde cada variável
aparece apenas uma vez, direta ou complementada
A
0
0
0
0
1
1
1
1
Circuitos Digitais
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F = A’BC
0
0
0
1
0
0
0
0
Mintermo A’BC
CIC - UnB
Maxtermos
• Um maxtermo é um termo soma que vale 0 (zero) em
apenas um ponto do domínio da função
• É determinado por uma disjunção (OR) onde cada variável
aparece apenas uma vez, direta ou complementada
A
0
0
0
0
1
1
1
1
Circuitos Digitais
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
1
1
1
0
1
1
1
1
Maxtermo (A’  B  C)
CIC - UnB
Formas Canônicas
• Uma tabela verdade é uma assinatura que identifica
unívocamente uma função Booleana
• Espressões Booleanas diferentes podem representar uma
mesma função Booleana
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
0
0
1
1
1
1
1
Tabela Verdade
Circuitos Digitais
F
1
1
1
0
0
0
0
0
F = A  BC
F = A B  A B’  BC
F = A( B  C  B’ C’)  B C
Espressões Booleanas
CIC - UnB
Formas Canônicas Dois Níveis
• Formas Canônicas são representações (assinaturas) únicas
de funções Booleanas
– Ex: uma soma de produtos é uma forma canônica
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
OR de 1’s
Circuitos Digitais
F
0
0
0
1
1
1
1
1
F
1
1
1
0
0
0
0
0
011
100
101
110
111
F = A' B C  A B' C'  A B' C  A B C'  A B C
F' = A' B' C'  A' B' C  A' B C'
CIC - UnB
Formas Canônicas Dois Níveis
• Formas Canônicas são representações (assinaturas) únicas
de funções Booleanas
– Ex: produto de somas é outra forma canônica
000
001
010
F = (A  B  C) (A  B  C’) (A  B’  C)
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
0
0
1
1
1
1
1
F
1
1
1
0
0
0
0
0
AND de 0’s
F' = (A  B’  C’) (A  B’  C’) (A  B’  C) (A  B  C’) (A  B  C)
Circuitos Digitais
CIC - UnB
Formas Canônicas Dois Níveis
• Notação para soma de mintermos:
– F(A,B,C) = (1, 3, 5, 7)
= m1  m3  m5  m7
= A B C’  A B' C'  A B’ C  A B C
• Notação para produto de maxtermos:
– F(A,B,C) = (0, 2, 4, 6)
= M0·M2·M4·M6
= (A  B  C) (A  B’  C) (A’  B  C) (A’  B’  C)
Circuitos Digitais
CIC - UnB
Simplificação de Soma de Mintermos
• Usando métodos algébricos:
– F(A,B,C) = ∑(3,4,5,6,7)
= m3  m4  m5  m6  m7
= A' B C  A B' C'  A B' C  A B C'  A B C
= A B' (C  C')  A' B C  A B (C'  C)
= A B'  A' B C  A B
= A (B'  B)  A' B C
= A  A' B C
=A BC
B
Implementação
C
F
A
Circuitos Digitais
CIC - UnB
Mintermos x Maxtermos
• É possível obter um produto de maxtermos a partir de uma
soma de mintermos e vice-versa aplicando De Morgan
sobre o complemento da função
– F(A,B,C) = (1, 2, 3, 5, 7) = A’ B’ C  A’ B C’  A B’ C  A B C
 F ’ (A,B,C) =  (0, 4, 6) = A’ B’ C’  A B’ C’  A B C’
 F (A,B,C) = (F ’ (A,B,C) )’ = (A’ B’ C’  A B’ C’  A B C’)’
= (A B  C’)(A  B’  C’)(A’  B’  C’)
= (1, 3, 7)
Circuitos Digitais
CIC - UnB
Funções Incompletas
• São funções para as quais algumas combinações de valores
das entradas nunca ocorrem
– Ex: acionador de display de 7 segmentos para dígitos BCD
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
S1
1
0
1
1
0
1
1
1
1
1
X
X
X
X
X
X
Circuitos Digitais
s1
x1
x2
x3
x4
• 4 entradas -> 16 combinações
• apenas 10 utilizadas
• 6 combinações nunca ocorrem
• são denominadas irrelevantes
(don’t cares)
• podem ser utilizadas para simplificar a lógica
s6
s7
s2
s5 s 3
s4
CIC - UnB
Funções Incompletas
• Funções incompletas mapeiam pontos do domínio da
função em 3 valores possíveis:
– F(A, B, C, D)  { 0, 1, X }
• Os domínios de pontos onde F vale { 0, 1, X} são
denominados, respectivamente, de:
F1 = {m0, m2, m3, m5, m6, m7, m8, m9 }
Fx = {i10, i11, i12, i13, i14, i15 }
F0 = {M1, M4 }
• F pode ser descrita definindo-se dois desses três conjuntos:
– F (A, B, C, D) = F1  Fx ou
Circuitos Digitais
F1  F0 ou F0  Fx
CIC - UnB
Minimização Lógica Dois Níveis
• Manipulação algébrica:
– Difícil determinar a ordem e quais transformações aplicar
– Como saber se atingiu-se a melhor solução ?
• Ferramentas de auxílio:
– Não conseguem tratar problemas grandes de forma exata
– Baseiam-se em heurísticas e critérios de custo
– Resultados bastante bons em lógica dois níveis
• Métodos manuais apenas para fins didáticos ou funções
muito simples
Circuitos Digitais
CIC - UnB
Minimização Lógica Dois Níveis
• Idéia base: aplicação de distribuição e complemento
A(B  B’) = A
F = A B' + A B = A (B' + B) = A
A
0
0
1
1
B
0
1
0
1
F
0
0
1
1
Dentro de F1:
B varia enquanto
A não muda
G = A' B' + A B' = (A' + A) B' = B'
Dentro de G1:
A varia enquanto
A
0
0
1
1
B
0
1
0
1
G
1
0
1
0
B não muda
Resultado: A é eliminado!
Resultado: B é eliminado!
Circuitos Digitais
CIC - UnB
Cubos
0
1
Cubo 1
X
• O espaço Booleano n-dimencional pode ser
visualizado espacialmente
• Produtos de literais são chamados de cubos
XY
11
01
Y
Cubo 2
00
10
X
011
XYZ
111
WXYZ
1011
1111
0111
0011
010
1010
1110
110
0010
0110
Y
Z
001
000
Cubo 3 X
101
100
Y
0001
1001
1101
0101
Z
1100
W
0000
X
1000
0100
Cubo 4
Circuitos Digitais
CIC - UnB
Visualização de Cubos
XYZ
111
011
110
010
F(X, Y, Z) = ∑(4,5,6,7) = X
Y
Z
001
000
Cubo 3 X
Circuitos Digitais
101
100
• Pontos adjacentes diferem em 1 bit
• Todos os pontos da função estão dispostos
sobre uma face
• Y e Z variam enquanto X permanece
inalterado: Y e Z podem ser eliminados da
expressão
CIC - UnB
Mapas de Karnaugh
• Visualização do domínio de uma função na forma matricial
• Pontos do domínio estão dispostos seguindo o código
Gray, pares adjacentes diferem em 1 bit
A
0
B
1
0
0
1
1
A
AB
00
CD
2
00
01
11
00
0
4
12
8
1
5
13
9
3
7
15
11
2
6
14
10
3
01
A
AB
C
00
01
11
11
10
10
0
1
Circuitos Digitais
C
0
2
6
4
1
3
7
5
B
D
B
CIC - UnB
Adjacências no Mapa de Karnaugh
• Os elementos nas extremidades das linhas e colunas são
também adjacentes
AB
00
C
01
11
111
011
A
10
010
0
000
010
110
100
1
001
011
111
101
110
B
001
101
C
B
000
100
A
Circuitos Digitais
CIC - UnB
Adjacências no Mapa de Karnaugh
A
0
B
0
1
0
0
1
1
B é eliminado
A permanece
A
00
01
11
10
0
0
0
1
1
1
0
0
1
1
F=?
A
0
1
0
1
1
1
0
0
B
AB
C
1
B
A é eliminado
B’ permanece
F=?
F=?
• O cubo obtido é definido pelas variáveis que não mudam
de fase ao longo de seus mintermos
Circuitos Digitais
CIC - UnB
Adjacências no Mapa de Karnaugh
A
0
B
0
1
0
0
AB
C
1
1
1
B é eliminado
A permanece
00
01
11
10
0
0
0
1
1
1
0
0
1
1
F = A B’  AB = A
A
B
0
1
0
1
1
A é eliminado
B’ permanece
1
0
0
F = A’ B’  AB’ = B’
B
A
F = A B C’  A B C  AB’C  A B’ C’
= A(B(C  C’)  B’(C  C’))
=A
• O cubo obtido é definido pelas variáveis que não mudam
de fase ao longo de seus mintermos
Circuitos Digitais
CIC - UnB
Adjacências no Mapa-K
AB
C
0
A
00
01
11
10
1
0
0
1
•Adjacência nas extremidades das linhas
1
0
0
1
1
B
AB
C
A
00
01
11
10
0
1
0
1
0
1
1
0
1
0
•Adjacência nas extremidades das colunas
B
Circuitos Digitais
CIC - UnB
Complemento de uma Função
AB
C
0
A
00
01
11
10
1
0
0
1
F=?
1
0
0
1
1
B
AB
C
0
A
Trocar 0’s por 1’s
00
01
11
10
0
1
1
0
F’ = ?
1
1
1
0
0
B
Circuitos Digitais
CIC - UnB
Complemento de uma Função
AB
C
0
A
00
01
11
10
1
0
0
1
F = A C  B’ C’
1
0
0
1
1
B
AB
C
0
A
Trocar 0’s por 1’s
00
01
11
10
0
1
1
0
F’ = A’ C  B C’
1
1
1
0
0
B
Circuitos Digitais
CIC - UnB
Karnaugh de 4 variáveis
AB
00
CD
A
01
11
10
00
1
0
0
1
01
0
1
0
0
D
11
1
1
1
1
10
1
1
1
1
F=?
C
B
Circuitos Digitais
CIC - UnB
Karnaugh de 4 variáveis
AB
00
CD
A
01
11
10
00
1
0
0
1
01
0
1
0
0
F = C + A' B D + B' D'
D
11
1
1
1
1
10
1
1
1
1
C
B
Circuitos Digitais
CIC - UnB
Minimização com Irrelevâncias
• Os pontos irrelevantes podem ser considerados como 1 ou
0 no mapa de Karnaugh
• São utilizados para formar cubos maiores, simplificando a
função
AB
C
A
00
01
11
10
0
1
0
x
1
1
0
x
1
x
Os pontos irrelevantes deste cubo
estão sendo computados como 1’s
B
Este ponto irrelevante é considerado como 0
Circuitos Digitais
CIC - UnB
Exemplo: comparador de 2 bits
A
B
C
D
N1
F1 A B = C D
=, >, < F2 A B < C D
F3 A B > C D
N2
A
0
0
1
• 3 funções de 4 variáveis
• 3 mapas de Karnaugh
1
Circuitos Digitais
© R.H. Katz
B C D
0 0 0
0 1
1 0
1 1
1 0 0
0 1
1 0
1 1
0 0 0
0 1
1 0
1 1
1 0 0
0 1
1 0
1 1
F1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
F2
0
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
F3
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
0
CIC - UnB
Exemplo: comparador de 2 bits
AB
CD
A
00
01
11
10
00
1
0
0
0
01
0
1
0
0
AB
CD
A
00
01
11
10
00
0
0
0
0
01
1
0
0
0
D
11
0
0
1
11
1
1
0
0
0
0
00
01
11
10
00
0
1
1
1
01
0
0
1
1
1
11
0
0
0
0
10
0
0
1
0
C
10
B
K-map for F1
D
1
C
10
A
D
0
C
AB
CD
1
1
0
B
K-map for F2
0
B
K-map for F3
F1 = ?
F2 = ?
F3 = ?
Circuitos Digitais
© R.H. Katz
CIC - UnB
Exemplo: comparador de 2 bits
AB
CD
A
00
01
11
10
00
1
0
0
0
01
0
1
0
0
AB
CD
A
00
01
11
10
00
0
0
0
0
01
1
0
0
0
D
11
0
0
1
0
10
0
0
0
1
C
AB
CD
A
00
01
11
10
00
0
1
1
1
01
0
0
1
1
D
11
1
1
0
1
10
1
1
0
0
C
D
11
0
0
0
0
10
0
0
1
0
C
B
K-map for F1
B
K-map for F2
B
K-map for F3
F1 = A' B' C' D' + A' B C' D + A B C D + A B' C D'
F2 = A' B' D + A' C
F3 = B C' D' + A C' + A B D'
A xnor B xnor C xnor D
Circuitos Digitais
© R.H. Katz
CIC - UnB