aula 14 ELE-II - simplificacao de expressoes booleanas 110223

Prévia do material em texto

24/02/2011
1
SIMPLIFICAÇÃO DE 
EXPRESSÕES BOOLEANAS
pg 80
Circuitos Digitais
Objetivos
• Postulados, Propriedades e Teoremas
• Simplificações usando esses conceitos
– Equivalência entre portas lógicas
• Mapas de Karnaugh
Simplificação
• Existem várias maneiras de se implementar 
uma determinada expressão lógica
• Por que simplificar a expressão:
– Reduzir o número de portas lógicas necessárias
– Reduzir a variedade de circuitos integrados usados
• Através da equivalência de portas lógicas
24/02/2011
2
Postulados
Se A = 0, então A’ = 1
Se A = 1, então A’ = 0
A’’ = A
0 . 0 = 0 1 . 1 = 1
0 . 1 = 1 . 0 = 0
0 + 0 = 0 1 + 1 = 1
0 + 1 = 1 + 0 = 1
0’ = 1 1’ = 0
A . A = A A . A’ = 0
A + A = A A + A’ = 1
A . 0 = 0 A . 1 = A
A + 0 = A A + 1 = 1
Exercícios
• Prove os postulados do slide anterior 
utilizando as definições das funções lógicas 
básicas AND, OR e NOT
Propriedades
Comutativa
A . B = B . A
A + B = B + A
Associativa
A . (B . C) = (A . B) . C
A + (B + C) = (A + B) + C
Distributiva
A . (B + C) = A . B + A . C
A + (B . C) = (A + B) . (A + C)
24/02/2011
3
Exercícios
• Comprove as propriedades do slide anterior 
utilizando tabelas-verdade
Teoremas
Teoremas de De Morgan
(A . B)’ = A’ + B’
(A + B)’ = A’ . B’
Teoremas da Absorção
A + A . B = A
A + A’ . B = A + B
Exercícios
• Prove os teoremas de De Morgan utilizando 
tabelas-verdade
• Prove os teoremas da Absorção utilizando os 
postulados e propriedades enunciados 
anteriormente
24/02/2011
4
Exercícios
• Mostre que a expressão
S = X’(YZ)’W + X(YZ)’W’ + X(YZ)’W
pode ser escrita como S = (YZ)’(W+X)
• Mostre que a expressão
F = [ (KM)’ + L + N ]’ + M + (KMN)’
pode ser escrita como F = M(N’+K’)
(Assim como em Álgebra, o ponto “.” às vezes é suprimido...)
Exercício
• Simplifique o circuito do controlador de 
bombeamento de água da aula anterior
H
L
A
B
H’
L’
H’L’
H’L
Exercícios
• Simplifique o circuito que você obteve para o 
Controlador de Acesso à Impressora na aula 
anterior
• Simplifique o circuito do Sistema de Votação 
que você projetou na aula anterior
24/02/2011
5
Equivalência entre Portas Lógicas
Desenhe as portas das expressões abaixo:
• S = A’
• S = (A.A)’ = (A)’ = A’
• S = (A+A)’ = (A)’ = A’
Inversores podem ser construídos com portas NAND ou NOR
Equivalência entre Portas Lógicas
Usando os Teoremas de De Morgan:
• Construa uma porta NAND utilizando uma 
porta OR e inversores
• Construa uma porta NOR usando uma porta 
AND e inversores
Mapa de Karnaugh
• N variáveis de entrada
– 2N linhas na tabela verdade
• Mapa de Karnaugh (lê-se Karnô)
– Mapear as 2N linhas em 2N células (quadrículos)
24/02/2011
6
S
A
0 1
0 0 1
B 1 0 1
1º Exemplo: 2 variáveis
A B S
0 0 0
0 1 0
1 0 1
1 1 1
S
A
0 1
0 0 1
B 1 0 1
S = AB’ + AB
S = A.(B’ + B)
S = A.1 = A
S = A
Células adjacentes podem ser tomadas como um “enlace”, 
dentro do qual uma das variáveis é constante.
S
A
0 1
0 0 1
B 1 1 1
2º Exemplo: 2 variáveis
A B S
0 0 0
0 1 1
1 0 1
1 1 1
S = A’B + AB’ + AB
S = A’B + AB + AB’ + AB
S = (A’ + A).B + A.(B’ + B)
S = 1.B + A.1 = A + B
S = A + B
Dentro de um enlace, 
a variável que se 
altera desaparece 
da expressão.
Y + Y = Y
U
m
a 
cé
lu
la
 p
o
d
e 
es
ta
r 
em
 v
ár
io
s 
en
la
ce
s.
3º Exemplo: 3 variáveis
S
BC C=1
00 01 11 10
0 0 0 1 0
A 1 1 0 1 1
B=1
Entre 2 células adjacentes, apenas 
uma variável muda de valor
C
ó
d
ig
o
 d
e 
G
ra
y 
(0
0,
 0
1,
 1
1,
 1
0)
: 
ap
en
as
 u
m
a 
va
ri
áv
el
 s
e 
al
te
ra
 
en
tr
e 
u
m
a 
cé
lu
a 
e 
o
u
tr
a
O mapa é “circular”, e se fecha nele mesmo. 
As células das bordas são adjacentes.
24/02/2011
7
4º Exemplo: 3 variáveis
S
BC C=1
00 01 11 10
0 0 0 1 0
A 1 1 0 1 1
B=1
BCAC’
S = BC + AC’
Cada célula =1 precisa ser considerada pelo menos uma vez.
5º Exemplo: 3 variáveis
S
BC C=1
00 01 11 10
0 0 1 1 0
A 1 0 1 1 1
B=1
AB
C
S = AB + C
6º Exemplo: 3 variáveis
S
BC C=1
00 01 11 10
0 0 1 1 0
A 1 1 1 1 1
B=1
A
C
S = A + C
24/02/2011
8
7º Exemplo: 3 variáveis
S
BC C=1
00 01 11 10
0 0 1 0 1
A 1 1 1 0 0
B=1
A’BC’
B’C
S = B’C + A’BC’ + AB’
AB’
S
CD
D=1
00 01 11 10
AB
00 0 0 1 0
B
01 0 1 1 1
11 1 1 1 0
A
10 1 0 0 1
C
8º Exemplo: 4 variáveis
BD
AB’D’
S = A’CD + BD + ABC’ + AB’D’
ABC’
A’CD
Exercícios: 
Simplifique as 
expessões
A B C S
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
A B C D S
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
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 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
A B C S
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
24/02/2011
9
Exercícios: Simplifique as expressões
• F = ABC’ + A’BC + A’BC’ + ABC
• R = ABC + AB + B’C
• J = AB’CD + ACD’ + ABD + BC’D + ABC’ + A’BCD
• K = AB’C’ + A’BC + A’B’C + ABC + ABC’
• M = A ⊕ B ⊕ C ⊕ D
• W = A ⊕ B + C ⊕ D
• W = A ⊕ B + ABCD + AB’C
Construa a tabela verdade, e depois o mapa de Karnaugh. Em alguns 
casos, vc poderá fazer o mapa de Karnaugh diretamente.