ICC060

SISTEMAS LÓGICOS
:: Aula 2c – Formas Canônicas
2017/2
 INFORMAÇÕES BÁSICAS
Leandro Galvão – IComp/UFAM
[email protected]
1221 – IComp
colabweb.ufam.edu.br/course/view.php?id=325

Estes slides estão licenciados sob Creative Commons Attribution 4.0 International license.
Estes slides foram elaborados usando o template Mowbray, disponível gratuitamente em SlidesCarnival.
2
Sumário

Formas Canônicas

Projeto digital
Cap. 4.1-4.4
1.
Formas canônicas
Outra forma de organizar a Tabela
Verdade
 Formas Canônicas
▪ É desejável representar expressões booleanas em
um formato padrão, conhecido como forma canônica.
▪ Existem dois tipos equivalentes de formas
canônicas:

Soma de produtos (SOP)

Produto de somas (POS)
6
 Soma de produtos (SOP)
▪ Também conhecida como forma normal disjuntiva ou expansão de
mintermos.

▪ Dada uma tabela verdade, cada linha onde a função de saída possui valor
igual a 1 contribui com um termo (mintermo).

▪ Cada mintermo é formado por operações AND entre:

▫ as variáveis de entrada cujo valor é 1, e

▫ os complementos das variáveis de entrada cujo valor é 0.

▪ Os mintermos são concatenados por operações OR, a fim de compor a

expressão canônica.

7
 Soma de produtos - Exemplo

𝐴ҧ𝐵𝐶
ത

ҧ
𝐴𝐵𝐶

ത
𝐴𝐵𝐶
𝐴𝐵𝐶ҧ
𝐴𝐵𝐶

Forma canônica SOP:

𝑓 𝐴, 𝐵, 𝐶 = 𝐴ҧ𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶
8
 Soma de produtos - Exemplo
▪ Podemos interpretar as variáveis A, B, C como uma palavra de três bits,
em que:
▫ A é o bit mais significativo
▫ C é o bit menos significativo

𝑓 𝐴, 𝐵, 𝐶 = 𝐴ҧ𝐵𝐶 ҧ
ത + 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶

𝑓 𝐴, 𝐵, 𝐶 = ෍ 𝑚(001,011,101,110,111)

𝑓 𝐴, 𝐵, 𝐶 = ෍ 𝑚(1,3,5,6,7)

9
 Produto de somas (POS)
▪ Também conhecida como forma normal conjuntiva ou expansão de
maxtermos.

▪ Dada uma tabela verdade, cada linha onde a função de saída possui valor
igual a 0 contribui com um termo (maxtermo).

▪ Cada maxtermo é formado por operações OR entre:

▫ as variáveis de entrada cujo valor é 0, e

▫ os complementos das variáveis de entrada cujo valor é 1.

▪ Os maxtermos são concatenados por operações AND, a fim de compor a

expressão canônica.

10
 Produto de somas – Exemplo

𝐴+𝐵+𝐶

𝐴 + 𝐵ത + 𝐶

𝐴ҧ + 𝐵 + 𝐶

Forma canônica POS:

𝑓 𝐴, 𝐵, 𝐶 = 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵ത + 𝐶 ⋅ (𝐴ҧ + 𝐵 + 𝐶)
11
 Produto de somas
▪ A expressão canônica do POS também pode ser reescrita
de forma mais compacta:

𝑓 𝐴, 𝐵, 𝐶 = 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵ത + 𝐶 ⋅ (𝐴ҧ + 𝐵 + 𝐶)

𝑓 𝐴, 𝐵, 𝐶 = ෑ 𝑀(000,010,100)

𝑓 𝐴, 𝐵, 𝐶 = ෑ 𝑀(0,2,4)

12
 Equivalência entre POS e SOP
▪ As formas canônicas POS e SOP são equivalentes,
pois derivam de uma mesma tabela verdade.
▪ Assim, dos exemplos anteriores, temos:

෍ 𝑚(1,3,5,6,7) ≡ ෑ 𝑀(0,2,4)

13
 Expressões POS e SOP são equivalentes
▫ Expressão POS:
𝐹 = 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵 + 𝐶ҧ ⋅ 𝐴 + 𝐵ത + 𝐶 ⋅ 𝐴ҧ + 𝐵 + 𝐶

▫ Idempotência:
𝐹 = 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵 + 𝐶ҧ
⋅ 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵ത + 𝐶
⋅ 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴ҧ + 𝐵 + 𝐶

14
 Expressões POS e SOP são equivalentes
▫ Associação:
𝐹= 𝐴 + 𝐵 + 𝐶ҧ ⋅ 𝐶
⋅ 𝐴 + 𝐶 + 𝐵ത ⋅ 𝐵
⋅ 𝐵 + 𝐶 + 𝐴ҧ ⋅ 𝐴

▫ Complemento:
𝐹 = 𝐴+𝐵 ⋅ 𝐴+𝐶 ⋅ 𝐵+𝐶

▫ Distribuição:
𝐹 = 𝐴 + 𝐴𝐶 + 𝐵𝐴 + 𝐵𝐶 ⋅ 𝐵 + 𝐶
= 𝐴𝐵 + 𝐴𝐶 + 𝐴𝐵𝐶 + 𝐴𝐶 + 𝐴𝐵 + 𝐴𝐵𝐶 + 𝐵𝐶 + 𝐵𝐶

15
 Expressões POS e SOP são equivalentes
▫ Idempotência:
𝐹 = 𝐴𝐵 + 𝐴𝐵𝐶 + 𝐴𝐶 + 𝐵𝐶

▫ Distribuição:
𝐹 = 𝐴𝐵 1 + 𝐶 + 𝐵𝐶 + 𝐴𝐶

▫ Aniquilação e Identidade:
𝐹 = 𝐴𝐵 + 𝐵𝐶 + 𝐴𝐶

16
 Condições de irrelevância (don’t care)
▪ Em algumas aplicações, a saída produzida por um
conjunto particular de entradas é irrelevante para o
usuário.
▪ Tal situação é conhecida como don’t care.
▪ Representações algébricas:
▫ SOP: 𝑓 = 𝑑(… )
▫ POS: 𝑓 = 𝐷(… )

17
 𝐴 𝐵 𝐶 𝐷 𝑓 #
0 0 0 0 1 0
Exercício 0 0 0 1 0 1
0 0 1 0 1 2
▪ Qual a tabela verdade 0 0 1 1 X 3
equivalente a 0 1 0 0 0 4
0 1 0 1 0 5
𝑓 𝐴, 𝐵, 𝐶, 𝐷 = 0 1 1 0 1 6
0 1 1 1 0 7
∑𝑚 0,2,6,9,13,14 1 0 0 0 X 8
1 0 0 1 1 9
+ 1 0 1 0 X 10
1 0 1 1 0 11
∑𝑑(3,8,10) 1 1 0 0 0 12
1 1 0 1 1 13
1 1 1 0 1 14
1 1 1 1 0 15
18
2.
Projeto Digital
Como projetar um circuito digital?
 Projeto Digital
▪ Para construir um circuito, é necessário conhecer
sua expressão booleana característica.
▪ Para obter a expressão booleana, construa a tabela
verdade para cada situação do problema.

Tabela Expressão
Situação Circuito
Verdade booleana

20
 Projeto Digital – Exemplo 1
▪ Alice, Bob e Cida se reúnem
uma vez por semana para irem
ao cinema ou jogar boliche.
▪ Para decidir o que fazer, eles
votam e a maioria simples
vence.
▪ Supondo que um voto para o
filme é representado por um
nível lógico 1, projete um circuito
lógico que calcule
automaticamente a decisão.
21
 :: Tabela Verdade
Entradas Saída
𝑨 𝑩 𝑪 𝑭
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

22
 :: Expressões SOP e POS
𝑨 𝑩 𝑪 𝑭 SOP:
0 0 0 0 ҧ
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶
0 0 1 0
𝐹 = ∑𝑚(3,5,6,7)
0 1 0 0
0 1 1 1
1 0 0 0 POS:
1 0 1 1 𝐹 = 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵 + 𝐶ҧ ⋅
1 1 0 1
𝐴 + 𝐵ത + 𝐶 ⋅ 𝐴ҧ + 𝐵 + 𝐶
1 1 1 1
𝐹 = Π𝑀(0,1,2,4)

23
 :: Circuito digital SOP
SOP:
ҧ
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶

24
 :: Circuito digital POS
POS:
𝐹 = 𝐴 + 𝐵 + 𝐶 ⋅ 𝐴 + 𝐵 + 𝐶ҧ ⋅
𝐴 + 𝐵ത + 𝐶 ⋅ 𝐴ҧ + 𝐵 + 𝐶

25
 Desenho do circuito lógico – Dica 1
▪ Explicite as entradas e seus complementos.

B Saída

26
 Desenho do circuito lógico – Dica 2
▪ Comece pelos termos mais prioritários (parênteses,
AND).

A
ҧ
𝐴𝐵𝐶
B Saída

27
 Desenho do circuito lógico – Dica 3
▪ Deixe as operações menos prioritárias (OR) para o
fim.

B Saída

28
 Formas canônicas podem ser simplificadas
▪ Expressão SOP:
ҧ
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶

▫ Idempontência:
ҧ
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶 + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶 + 𝐴𝐵𝐶

▫ Distribuição:
𝐹 = 𝐵𝐶(𝐴ҧ + 𝐴) + 𝐴𝐶(𝐵ത + 𝐵) + 𝐴𝐵(𝐶ҧ + 𝐶)

▫ Complemento:
𝐹 = 𝐵𝐶 + 𝐴𝐶 + 𝐴𝐵

29
 Formas canônicas podem ser simplificadas
SOP: Expr. Simplificada:
ҧ
𝐹 = 𝐴𝐵𝐶 ത + 𝐴𝐵𝐶ҧ + 𝐴𝐵𝐶
+ 𝐴𝐵𝐶 𝐹 = 𝐵𝐶 + 𝐴𝐶 + 𝐴𝐵

30
 Projeto Digital – Exemplo 2
▪ Derive as expressões Dígito Excesso de 3
SOP das saídas de um 0 0011
circuito que recebe como 1 0100
entrada um número 2 0101
3 0110
binário de 4 bits, entre 0 e
4 0111
9, e o converte para BCD
5 1000
Excesso de 3.
6 1001
7 1010
8 1011
9 1100
31
 :: Tabela Verdade
𝑨 𝑩 𝑪 𝑫 𝑺𝟑 𝑺𝟐 𝑺𝟏 𝑺𝟎
0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
1 0 1 0 X X X X
1 0 1 1 X X X X
1 1 0 0 X X X X
1 1 0 1 X X X X
1 1 1 0 X X X X
1 1 1 1 X X X X
32
 :: Expressão SOP – Saída S3
▪ SOP:
𝑨 𝑩 𝑪 𝑫 𝑺𝟑
0 0 0 0 0
ҧ 𝐶𝐷
𝐹 = 𝐴𝐵 ҧ + 𝐴𝐵𝐶
ҧ 𝐷 ҧ
ഥ + 𝐴𝐵𝐶𝐷 + 𝐴𝐵ത 𝐶ҧ 𝐷
ഥ 0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
𝐹 = ∑𝑚 5,6,7,9
0 1 0 1 1
+∑𝑑(10,11,12,13,14,15) 0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
1 1 1 1 X
33
 :: Expressão SOP – Saída S2
▪ SOP:
𝑨 𝑩 𝑪 𝑫 𝑺𝟑
0 0 0 0 0
0 0 0 1 1
𝐹 = ∑𝑚 1,2,3,4,9 0 0 1 0 1
0 0 1 1 1
+∑𝑑(10,11,12,13,14,15) 0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
34
1 1 1 1 X
 :: Expressão SOP – Saída S1
▪ SOP:
𝑨 𝑩 𝑪 𝑫 𝑺𝟑
0 0 0 0 1
0 0 0 1 0
𝐹 = ∑𝑚 0,3,4,7,8 0 0 1 0 0
0 0 1 1 1
+∑𝑑(10,11,12,13,14,15) 0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
35
1 1 1 1 X
 :: Expressão SOP – Saída S0
▪ SOP:
𝑨 𝑩 𝑪 𝑫 𝑺𝟑
0 0 0 0 1
0 0 0 1 0
𝐹 = ∑𝑚 0,2,4,6,8 0 0 1 0 1
0 0 1 1 0
+∑𝑑(10,11,12,13,14,15) 0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
36
1 1 1 1 X
 Projeto Digital – Exemplo 3
▪ Alex, Bruna e Cláudia querem pedir uma pizza que agrade a todos. Eis as
preferências:
▫ Alex come pizza de azeitona (A) se e somente se tiver pepperoni (P)
▫ Bruna só come pizza de pepperoni, mas sem calabresa (C).
▫ Cláudia só come pizza com exatamente dois ingredientes.
▪ Determine:
▫ A expressão canônica correspondente à
preferência de cada pessoa.
▫ A expressão canônica correspondente
aos interesses em comum.

37
 :: Tabela Verdade
▪ Preferências:
▫ Alex come pizza de azeitona (A) se e somente se
tiver pepperoni (P)
▫ Bruna só
𝑨 come 𝑷 pizza Alex
𝑪 de Bruna Cláudia
pepperoni, Resultado
mas sem
0 0 0 1 0 0 0
calabresa
0 (C). 0 1 1 0 0 0
0 1 0 0 1 0 0
▫ Cláudia só come pizza com exatamente dois
0 1 1 0 0 1 0
ingredientes.
1 0 0 0 0 0 0
1 0 1 0 0 1 0
1 1 0 1 1 1 1
1 1 1 1 0 0 0
38
 :: Expressão SOP – Alex
𝑨 𝑷 𝑪 Alex ▪ SOP:
0 0 0 1 𝐹𝐴 = 𝐴ҧ𝑃ത 𝐶ҧ + 𝐴ҧ𝑃𝐶
ത + 𝐴𝑃𝐶ҧ + 𝐴𝑃𝐶
0 0 1 1
0 1 0 0
0 1 1 0
▪ Expressão simplificada:
1 0 0 0 𝐹𝐴 = 𝐴ҧ𝑃ത 𝐶ҧ + 𝐶 + 𝐴𝑃 𝐶ҧ + 𝐶
1 0 1 0 𝐹𝐴 = 𝐴ҧ𝑃ത + 𝐴𝑃
1 1 0 1 𝐹𝐴 = 𝐴⨁𝑃
1 1 1 1
39
 :: Expressão SOP – Bruna
𝑨 𝑷 𝑪 Bruna ▪ SOP:
0 0 0 0 𝐹𝐵 = 𝐴𝑃ҧ 𝐶ҧ + 𝐴𝑃𝐶ҧ
0 0 1 0
0 1 0 1
0 1 1 0
▪ Expressão simplificada:
1 0 0 0 𝐹𝐵 = 𝑃𝐶ҧ 𝐴ҧ + 𝐴
1 0 1 0 𝐹𝐵 = 𝑃𝐶ҧ
1 1 0 1
1 1 1 0
40
 :: Expressão SOP – Cláudia
𝑨 𝑷 𝑪 Cláudia ▪ SOP:
0 0 0 0 ҧ
𝐹𝐶 = 𝐴𝑃𝐶 ത + 𝐴𝑃𝐶ҧ
+ 𝐴𝑃𝐶
0 0 1 0
0 1 0 0
0 1 1 1
▪ Expressão simplificada:
1 0 0 0
ҧ
𝐹𝐶 = 𝐴𝑃𝐶 ത + 𝐴𝑃𝐶ҧ
+ 𝐴𝑃𝐶
1 0 1 1
1 1 0 1
1 1 1 0
41
 :: Expressão SOP – Resultado
𝑨 𝑷 𝑪 Resultado ▪ SOP:
0 0 0 0 R = 𝐴𝑃𝐶ҧ
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
42
 :: Circuito – Resultado

𝑅 = 𝐴𝑃𝐶ҧ

43
 Perguntas?

[email protected]

44