Álgebra de Boole e Simplificação de Circuitos Lógicos

Prévia do material em texto

111
Álgebra de Boole e Simplificação 
de Circuitos Lógicos
Professora: Priscila Doria, M.Sc.
pdoria@area1.edu.br
2
Roteiro
• Introdução
• Postulados
• Propriedades
• Teoremas de De Morgan
• Identidades Auxiliares
• Simplificação de Expressões Booleanas
• Simplificação de Expressões Booleanas através 
dos Diagramas de Veitch-Karnaugh
3
Introdução
• Geralmente, os circuitos lógicos admitem 
simplificações
• Simplificação dos circuitos lógicos
– Álgebra de Boole
– Diagramas de Karnaugh
4
Postulados
• Postulado da 
complementação
– A = A
• Postulado da adição
– A + 0 = A
– A + 1 = 1
– A + A = A
– A + A = 1
• Postulado da 
multiplicação
– A . 0 = 0
– A . 1 = A
– A . A = A
– A . A = 0
5
Propriedades
• Propriedade Comutativa
– Adição: A + B = B + A
–Multiplicação: A . B = B . A
• Propriedade Associativa
– Adição: A + (B + C) = (A + B) + C = A + B + C
–Multiplicação: A . (B . C) = (A . B) . C = A.B.C
• Propriedade Distributiva
– A . (B + C) = A.B + A.C
6
Teoremas de De Morgan
• 1º Teorema de De Morgan
– O complemento do produto é igual à soma dos 
complementos
•
•
• 2º Teorema de De Morgan
– O complemento da soma é igual ao produto dos 
complementos
•
• NCBANCBA
BABA
.....)...(
.)(
=++++
=+
NCBANCBA
BABA
++++=
+=
...).....(
).(
7
Identidades Auxiliares
• A + A . B = A
– Prova:
A (1 + B)
1 + B = 1
A . 1
A
• (A + B) . (A + C) = A + B.C
– Prova:
A.A + A.C + A.B + B.C
A.A = A
A + A.C + A.B + B.C
A (1 + C + B) + B.C
1 + C + B = 1
A.1 + B.C
A + B.C
8
Identidades Auxiliares
• A + A.B = A + B
– Prova:
BA
BA
BAAA
BAA
BAA
BAA
+
+
+
+
).(
)..(
]).([
])..([
).( AA =Identidade
0. =AAIdentidade
9
Roteiro
• Introdução
• Variáveis e Expressões na Álgebra de Boole
• Postulados
• Propriedades
• Teoremas de De Morgan
• Identidades Auxiliares
• Simplificação de Expressões Booleanas
• Simplificação de Expressões Booleanas através dos 
Diagramas de Veitch-Karnaugh
10
Simplificação de Expressões Booleanas
• Exemplo1: S = ABC + AC + AB
AS
AS
BCBCAS
BCBCAS
BCBCAS
=
=
+=
++=
++=
1.
)]([
)]([
)( Propriedade Associativa
Identidade: A = A
A + A = 1
A . 1 = A
11
Simplificação de Expressões Booleanas
• Exemplo2: CBACBACBAS ++=
CBACAS
CBABBCAS
+=
++= )( B + B = 1
12
Exercícios
1. Simplifique as expressões booleanas, 
apresentadas a seguir:
a.
b.
c.
CABCBACBABCACBAS ++++=
)).(( CBACBAS ++++=
)(])([ ACDCDBACS +++=
BACS +=
CADCS +=
CBABAS ++=
13
Exercícios
2. A partir da expressão , obtenha .)( BAS ⊗= BAS ⊕=
BAS
BABAS
BBBABAAAS
BABAS
BABAS
ABBAS
⊕=
+=
+++=
++=
=
+=
..
....
)).((
).).(.(
)(
14
Exercícios
3. Obtenha o circuito simplificado que executa 
a expressão: ])()()[( CBADCABBAS ++++⊕=
DBACBABCAS ++=
15
Estudo Independente
• Leitura:
– Capítulo 3 (Idoeta e Capuano)
• Seções: 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7 e 3.8
• Atividades:
– Lista de Exercícios Nº 3
• Questões: 1, 2, 3 e 4
– Laboratório Nº 1
• Finalizar
16
Roteiro
• Introdução
• Variáveis e Expressões na Álgebra de Boole
• Postulados
• Propriedades
• Teoremas de De Morgan
• Identidades Auxiliares
• Simplificação de Expressões Booleanas
• Simplificação de Expressões Booleanas através dos 
Diagramas de Veitch-Karnaugh
17
Diagrama de Karnaugh (2 Variáveis)
• Regiões do mapa de Veitch-Karnaugh
A
A
B B
A
A
B B
A
A
B B
Região onde
A = 1
Região onde
B = 1
A
A
B B
Região onde
A = 0
A
A
B B
Região onde
B = 0
18
Diagrama de Karnaugh (2 Variáveis)
A
A
B B
A
A
B B
A
A
B B
A
A
B B
A = 0 e B = 0 A = 0 e B = 1
A = 1 e B = 0 A = 1 e B = 1
19
Diagrama de Karnaugh (2 Variáveis)
• Exemplo:
A B S
0 0 0
0 1 1
1 0 1
1 1 1
0 1
1 1
A
A
B B
0 1
2 3
20
Diagrama de Karnaugh (2 Variáveis)
1=S
1 1
1 1
A
A
B B
Quadra
BABAS +=
0 1
1 0
A
A
B B
Exemplos de 
termos isolados
AS =
0 0
1 1
A
A
B B
1 0
1 0
A
A
B B
Exemplos de pares
BS =
21
Diagrama de Karnaugh (2 Variáveis)
• Exemplo:
ABBABAS ++=
A B S
0 0 0
0 1 1
1 0 1
1 1 1
0 1
1 1
A
A
B B
BAS +=
22
Exercícios
4. Simplifique o circuito que executa a tabela 
verdade abaixo.
A B S
0 0 1
0 1 1
1 0 1
1 1 0
1 1
1 0
A
A
B B
BAS +=
23
Diagrama de Karnaugh (3 Variáveis)
A
A
B B
C C C
24
Regiões do mapa de Karnaugh
A
A
B B
C C C
A
A
B B
C C C
Região onde
B = 0
Região onde
C = 1
A
A
B B
C C C
Região onde
A = 1
A
A
B B
C C C
Região onde
A = 0
A
A
B B
C C C
Região onde
B = 1
A
A
B B
C C C
Região onde
C = 0
25
Diagrama de Karnaugh (3 Variáveis)
• Exemplo:
0111
1011
0101
1001
1
0
1
0
CA B S
0 0 1
0 0 0
0 1 1
0 1 1
1 0
1 0
A
A
B B
1
0
1
1
C C C
0 1
4 5
3 2
7 6
26
Diagrama de Karnaugh (3 Variáveis)
Oitava
1 1
1 1
A
A
B B
1
1
1
1
C C C
1=S
Exemplos de pares
1 0
0 1
A
A
B B
0
1
1
0
C C C
ACCAS +=
Exemplos de termos isolados
0 1
0 0
A
A
B B
0
1
1
0
C C C
ABCCBACBAS ++=
27
Diagrama de Karnaugh (3 Variáveis)
Exemplos de quadras
1 1
0 0
A
A
B B
1
0
1
0
C C C
AS =
1 1
1 1
A
A
B B
0
0
0
0
C C C
BS =
1 0
1 0
A
A
B B
0
0
1
1
C C C
CS =
28
Diagrama de Karnaugh (3 Variáveis)
• Exemplo:
0111
1011
0101
1001
1
0
1
0
CA B S
0 0 1
0 0 0
0 1 1
0 1 1
1 0
1 0
A
A
B B
1
0
1
1
C C C
CBAS +=
29
Exercícios
5. Simplifique o circuito que executa a tabela verdade 
abaixo.
0111
1011
1101
1001
1
0
1
0
CA B S
0 0 0
0 0 1
0 1 0
0 1 1
0 1
1 1
A
A
B B
1
0
0
1
C C C
CBCACAS ++=
0 1
1 1
A
A
B B
1
0
0
1
C C C
CABACAS ++=
30
Diagrama de Karnaugh (4 Variáveis)
A
A
D
B
C C
B
DD
B
31
Regiões do mapa de Karnaugh
A
A
D
B
C C
B
DD
B
Região onde A = 1
A
A
D
B
C C
B
DD
B
Região onde A = 0
32
Regiões do mapa de Karnaugh
A
A
D
B
C C
B
DD
B
Região onde B = 1
A
A
D
B
C C
B
DD
B
Região onde B = 0
33
Regiões do mapa de Karnaugh
A
A
D
B
C C
B
DD
B
Região onde C = 1
A
A
D
B
C C
B
DD
B
Região onde C = 0
34
Regiões do mapa de Karnaugh
A
A
D
B
C C
B
DD
B
Região onde D = 1
A
A
D
B
C C
B
DD
B
Região onde D = 0
35
Diagrama de Karnaugh (4 Variáveis)
• Exemplo:
11111
00111
11011
10011
11101
00101
11001
10001
1
1
0
0
1
1
0
0
C
1110
0010
1110
0010
1
0
1
0
DA B S
0 0 0
0 0 1
0 0 1
0 0 1
0111
1
1
1
0
0
1
11
10
10
A
A
D
B
C C
B
DD
B
0 1 23
4
10
12
5 7 6
11
13 15 14
8 9
36
Diagrama de Karnaugh (4 Variáveis)
Hexa Exemplos de termos isolados
1=S
1111
1
1
1
1
1
1
11
11
11
A
A
D
B
C C
B
DD
B
DCABDCBAS +=
0010
0
1
0
0
0
1
00
00
00
A
A
D
B
C C
B
DD
B
37
Diagrama de Karnaugh (4 Variáveis)
Exemplos de oitava
DS =
0110
1
1
1
0
0
0
10
10
10
A
A
D
B
C C
B
DD
B
BS =
0000
1
0
1
1
0
1
11
00
11
A
A
D
B
C C
B
DD
B
DS =
1001
0
0
0
1
1
1
01
01
01
A
A
D
B
C C
B
DD
B
38
Diagrama de Karnaugh (4 Variáveis)
Exemplos de quadras
BDS =
0110
0
1
0
0
0
0
00
10
00
A
A
D
B
C C
B
DD
B
DBS =
DBS =
0000
0
0
0
1
0
1
01
00
01
A
A
D
B
C C
B
DD
B
0000
1
0
1
0
0
0
10
00
10
A
A
D
B
C C
B
DD
B
39
Diagrama de Karnaugh (4 Variáveis)
Exemplos de pares
DCBS =
DBAS =
0000
0
0
0
0
0
0
10
00
10
A
A
D
B
C C
B
DD
B
0000
0
0
0
0
1
0
00
01
00
A
A
D
B
C C
B
DD
B
BDAS =
0000
0
1
0
0
0
0
00
10
00
A
A
D
B
C C
B
DD
B
40
Diagrama de Karnaugh (4 Variáveis)
• Exemplo:
11111
00111
11011
10011
11101
00101
11001
10001
1
1
0
0
1
1
0
0
C
1110
0010
1110
0010
1
0
1
0
DA B S
0 0 0
0 0 1
0 0 1
0 0 1
0111
1
1
1
0
0
1
11
10
10
A
A
D
B
C C
B
DD
B
CBACADS ++=
41
Exercícios
6. Minimize o circuito que executa a tabela verdade abaixo.
11111
00111
01011
00011
01101
10101
01001
00001
1
1
0
0
1
1
0
0
C
1110
1010
1110
1010
1
0
1
0
DA B S
0 0 0
0 0 1
0 0 0
0 0 1
01000
1
1
1
1
0
00
11
10
DABABCDDCBAS +++=
A
A
D
B
C C
B
DD
B
42
Diagrama de Karnaugh (5 variáveis)
A
E E E
B
C
C
B
DD
C
A
E E E
B
C
C
B
DD
C
43
Regiões do mapa de Karnaugh
A
E E E
B
C
C
B
DD
C
A
E E E
B
C
C
B
DD
C
Região onde A = 1
44
Regiões do mapa de Karnaugh
A
E E E
B
C
C
B
DD
C
A
E E E
B
C
C
B
DD
C
Região onde B = 1
45
Regiões do mapa de Karnaugh
A
E E E
B
C
C
B
DD
C
A
E E E
B
C
C
B
DD
C
Região onde C = 1
46
Regiões do mapa de Karnaugh
A
E E E
B
C
C
B
DD
C
A
E E E
B
C
C
B
DD
C
Região onde D = 1
47
Regiões do mapa de Karnaugh
A
E E E
B
C
C
B
DD
C
A
E E E
B
C
C
B
DD
C
Região onde E = 1
48
Diagrama de Karnaugh (5 variáveis)
• Exemplo:
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
B
01110
10110
11010
00010
01100
10100
11000
10000
1
1
0
0
1
1
0
0
D
1110
0010
1110
1010
1
0
1
0
EA C S
0 0 1
0 0 0
0 0 0
0 0 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
A
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
B
1111
1011
1101
1001
0110
0010
0100
0000
1
1
0
0
1
1
0
0
D
011
101
111
001
1
0
1
0
EC S
0 0
0 0
0 0
0 0
49
Diagrama de Karnaugh (5 variáveis)
A
1111
0
0
0
0
1
0
00
10
00
E E E
B
C
C
B
DD
C
EACDDEBAEBDADCBAEDBAABCEDCS ++++++=
A
E E E
B
C
C
B
DD
C
1010
0
1
1
1
0
0
11
11
01
50
Exercícios
7. Simplifique a expressão da tabela abaixo.
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
B
01110
00110
01010
00010
01100
00100
01000
10000
1
1
0
0
1
1
0
0
D
0110
0010
1110
1010
1
0
1
0
EA C S
0 0 1
0 0 1
0 0 0
0 0 0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
A
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
B
1111
1011
0101
0001
1110
1010
0100
1000
1
1
0
0
1
1
0
0
D
011
101
111
101
1
0
1
0
EC S
0 1
0 1
0 0
0 0
EACDABDEDCDBS +++=
51
Diagrama de Karnaugh
• Exemplo:
0110
0
0
0
1
0
1
11
10
11
A
A
D
B
C C
B
DD
B
DBDCABDS ++=
ABCDDCABDCBADCBA
DCBADCBADCBADCBADCBAS
++++
++++=
52
Exercícios
8. Minimize a expressão abaixo utilizando o diagrama 
de Karnaugh:
1111
1
1
1
1
1
0
00
00
01
ACBCCDABDCBAS ++++=
ABCDDABCDCABDCABCDBA
DCBABCDADBCACDBADCBAS
+++++
++++=
C
A
A
D
B
C
B
DD
B
53
Condições Irrelevantes
• Em alguns projetos, a condição de saída pode 
ser irrelevante, porque certas condições de 
entrada nunca ocorrerão
• Neste caso a saída é dada como X
• No momento da simplificação o X deve 
assumir o valor que possibilitar a melhor 
simplificação
54
Condições Irrelevantes
• Exemplo:
– Projeto de um circuito lógico que controla uma 
porta de elevador em um prédio de três andares
– O circuito tem 4 entradas
• Movimento: M = 0 (parado) e M = 1 (movimento)
• Indicadores dos andares: A1, A2 e A3
– A saída do circuito é o sinal ABRIR
• ABRIR = 0 (porta fechada) e ABRIR = 1 (porta aberta)
55
Condições Irrelevantes
• Exemplo (cont.):
XXX0
X
X
X
0
X
1
00
X1
10
3A
M
M
3A
1A
2A 2A
1A
3A
1A
321 AMAMAMS ++=
)321( AAAMS ++=
X1111
X0111
X1011
00011
X1101
00101
01001
00001
1
1
0
0
1
1
0
0
A2
X110
X010
X110
1010
1
0
1
0
A3M A1 ABRIR
0 0 0
0 0 1
0 0 1
0 0 X
56
A
A
D
B
C C
B
DD
B
Exercícios
9. Simplifique a expressão representativa da tabela abaixo.
01111
X0111
11011
X0011
11101
X0101
01001
10001
1
1
0
0
1
1
0
0
C
0110
1010
1110
1010
1
0
1
0
DA B S
0 0 1
0 0 X
0 0 1
0 0 0
X01X
1
0
0
X
1
1
01
11
X1
CBACBDS ++=
57
Casos que não admitem simplificação
BABAS .. +=
BAS ⊗=BAS ⊕=
0 1
1 0
A
A
B B
BABAS .. +=
1 0
0 1
A
A
B B
58
Casos que não Admitem Simplificação
CBAS ⊕⊕=
1111
0011
0101
1001
1
0
1
0
CA B
0 0 0
0 0 1
0 1 1
0 1 0
CBA ⊕⊕ )(
0 1
1 0
A
A
B B
0
1
1
0
C C C
ABCCBACBACBAS +++=
59
Agrupamentos de Zeros
• Podemos agrupar células que valem 0
• Neste caso obtemos a equação S
1111
1011
1101
1001
1
0
1
0
CA B
0 0 0
0 0 1
0 1 0
0 1 1
0 1
1 1
A
A
B B
1
1
0
1
C C C
).( CAS
CAS
=
=
S
CAS +=
60
Outra forma de apresentação do 
diagrama de Karnaugh
11
11 100100
10
01
00
AB
CD
11 100100
1
0
A
BC10
1
0
A
B
61
Estudo Independente
• Leitura:
– Capítulo 3 (Idoeta e Capuano)
• Seção: 3.9
• Atividades:
– Lista de Exercícios Nº 3
• Questões: 5, 6 e 7