EEL5105 – Circuitos e Técnicas Digitais
Aula 4
P f Eduardo
Prof.
Ed d L
L. O
O. B
Batista
ti t
[email protected]
http://www.inf.ufsc.br/~ebatista
2 Ál
2.
Álgebra
b Booleana
B l
• Álgebra com dois níveis lógicos:
0
1
False
True
Baixo
Alto
Não
Sim
Aberto
Fechado
2
2 Ál
2.
Álgebra
b Booleana
B l
• Operações Lógicas Básicas
• OR (“ou”)
• AND (“e”)
• NOT (“não”)
• Realizadas
R li d por portas
t ló
lógicas
i
construídas
t íd com circuitos
i
it elétricos
lét i
3
2 Álgebra Booleana
2.
2.1. Tabela Verdade
• Técnica para descrever a relação de entrada e saída de um circuito
ou porta lógica
4
2 Álgebra Booleana
2.
2.1. Tabela Verdade
• Técnica para descrever a relação de entrada e saída de um circuito
ou porta lógica
• Exemplo: porta lógica hipotética
A
N=2 entradas
B
?
S
M=1 saída
5
2 Álgebra Booleana
2.
2.1. Tabela Verdade
• Técnica para descrever a relação de entrada e saída de um circuito
ou porta lógica
• Exemplo: porta lógica hipotética
A
N=2 entradas
B
?
S
M=1 saída
• Tabela verdade:
A
B
S
0
0
1
0
1
0
1
0
1
1
1
0
6
2 Álgebra Booleana
2.
2.1. Tabela Verdade
• Técnica para descrever a relação de entrada e saída de um circuito
ou porta lógica
• Exemplo: porta lógica hipotética
A
N=2 entradas
• Tabela verdade:
2N
linhas
?
B
S
M=1 saída
N colunas
M colunas
A
B
S
0
0
1
0
1
0
1
0
1
1
1
0
7
2 Álgebra Booleana
2.
2.1. Tabela Verdade
• Técnica para descrever a relação de entrada e saída de um circuito
ou porta lógica
• Outro exemplo hipotético:
A
B
C
?
S1
S2
Quantas linhas e colunas terá a
tabela verdade para essa porta
lógica?
8
2 Álgebra Booleana
2.
2.1. Tabela Verdade
• Técnica para descrever a relação de entrada e saída de um circuito
ou porta lógica
• Outro exemplo hipotético:
A
B
C
?
S1
S2
A
B
C
S1
S2
0
0
0
1
1
0
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
9
2 Álgebra Booleana
2.
2.2. Operação e porta OR (“OU”)
10
2 Álgebra Booleana
2.
2.2. Operação e porta OR (“OU”)
• Representação da operação:
• 2 entradas: S = A + B
• Mais entradas: S = A + B + C + D + ...
11
2 Álgebra Booleana
2.
2.2. Operação e porta OR (“OU”)
• Representação da operação:
• 2 entradas: S = A + B
• Mais entradas: S = A + B + C + D + ...
• Representação da porta:
A
B
S
12
2 Álgebra Booleana
2.
2.2. Operação e porta OR (“OU”)
• Representação da operação:
• 2 entradas: S = A + B
• Mais entradas: S = A + B + C + D + ...
• Representação da porta:
A
B
S
A
B
S
0
0
0
0
1
1
1
0
1
1
1
1
13
2 Álgebra Booleana
2.
2.2. Operação e porta OR (“OU”)
• Representação da operação:
• 3 entradas: S = A + B + C
A
B
C
S
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
S
14
2 Álgebra Booleana
2.
2.2. Operação e porta OR (“OU”)
• Representação da operação:
• 3 entradas: S = A + B + C
A
B
C
S
A
B
C
S
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
15
2 Álgebra Booleana
2.
2.3. Operação e porta AND (“E”)
16
2 Álgebra Booleana
2.
2.3. Operação e porta AND (“E”)
• Representação da operação:
• 2 entradas: S = A · B
• Mais entradas: S = A · B · C · D · ...
• Representação da porta:
A
B
S
A
B
S
0
0
0
0
1
0
1
0
0
1
1
1
17
2 Álgebra Booleana
2.
2.3. Operação e porta AND (“E”)
• Representação da operação:
• 3 entradas: S = A · B · C
A
B
C
S
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
S
18
2 Álgebra Booleana
2.
2.3. Operação e porta AND (“E”)
• Representação da operação:
• 3 entradas: S = A · B · C
A
B
C
S
A
B
C
S
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
19
2 Álgebra Booleana
2.
2.4. Operação e porta NOT (“NÃO”)
20
2 Álgebra Booleana
2.
2.4. Operação e porta NOT (“NÃO”)
• Representação da operação:
• 1 entrada: S = A
21
2 Álgebra Booleana
2.
2.4. Operação e porta NOT (“NÃO”)
• Representação da operação:
• 1 entrada: S = A
A
S
0
1
1
0
22
2 Álgebra Booleana
2.
2.5. Outras Portas
23
2 Álgebra Booleana
2.
2.5. Outras Portas
• NAND (NÃO-E):
A
B
S A⋅B
S=A
A
B
S
0
0
1
0
1
1
1
0
1
1
1
0
24
2 Álgebra Booleana
2.
2.5. Outras Portas
• NAND (NÃO-E):
A
B
S A⋅B
S=A
• NOR (NÃO
(NÃO-OU):
OU):
A
B
S=A + B
A
B
S
0
0
1
0
1
1
1
0
1
1
1
0
A
B
S
0
0
1
0
1
0
1
0
0
1
1
0
25
2 Álgebra Booleana
2.
2.5. Outras Portas
• XOR (OU-EXCLUSIVO):
A
B
S=A
S
A⊕B
=AB+AB
A
B
S
0
0
0
0
1
1
1
0
1
1
1
0
26
2 Álgebra Booleana
2.
2.5. Outras Portas
• XOR (OU-EXCLUSIVO):
A
B
S=A
S
A⊕B
=AB+AB
• XNOR (NÃO
(NÃO-OU-EXCLUSIVO):
OU EXCLUSIVO):
A
B
S=A ⊕ B
= AB+AB
A
B
S
0
0
0
0
1
1
1
0
1
1
1
0
A
B
S
0
0
1
0
1
0
1
0
0
1
1
1
27
2 Ál
2.
Álgebra
b Booleana
B l
• Exemplo 1: Fazer a tabela verdade do circuito abaixo
A
B
S
C
28
2 Ál
2.
Álgebra
b Booleana
B l
• Exemplo 2: Fazer a tabela verdade do circuito abaixo
A
B
S
C
29
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
30
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 =
b) X + 1 =
31
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
b) X + 1 = 1
32
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
b) X + 1 = 1
2)
a) X ⋅ 1 =
b) X + 0 =
33
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
b) X + 1 = 1
2)
a) X ⋅ 1 = X
b) X + 0 = X
34
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
b) X + 1 = 1
2)
3)
a) X ⋅ X =
b) X + X =
a) X ⋅ 1 = X
b) X + 0 = X
35
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
b) X + 1 = 1
2)
3)
a) X ⋅ X = X
b) X + X = X
a) X ⋅ 1 = X
b) X + 0 = X
36
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
3)
b) X + 1 = 1
2)
a) X ⋅ 1 = X
b) X + 0 = X
a) X ⋅ X = X
b) X + X = X
4)
a) X ⋅ X =
b) X + X =
37
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com uma única variável:
1)
a) X ⋅ 0 = 0
3)
b) X + 1 = 1
2)
a) X ⋅ 1 = X
b) X + 0 = X
a) X ⋅ X = X
b) X + X = X
4)
a) X ⋅ X = 0
b) X + X = 1
38
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com mais de uma variável:
5)
a)) X + Y = Y + X
b) X ⋅ Y = Y ⋅ X
6)
39
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com mais de uma variável:
5)
a)) X + Y = Y + X
b) X ⋅ Y = Y ⋅ X
6)
a) X+(Y+Z) = (X+Y)+Z= X+Y+Z
b) X ⋅ (Y ⋅ Z) = (X ⋅ Y) ⋅ Z=X ⋅ Y ⋅ Z
40
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com mais de uma variável:
7)
a) X ⋅ (Y+Z) = X ⋅ Y + X ⋅ Z
b) X + (Y ⋅ Z) = (X + Y) ⋅ (X + Z)
8)
41
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com mais de uma variável:
7)
a) X ⋅ (Y+Z) = X ⋅ Y + X ⋅ Z
b) X + (Y ⋅ Z) = (X + Y) ⋅ (X + Z)
8)
a) X + X ⋅ Y = X
b) X ⋅ (X + Y) = X
42
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com mais de uma variável:
9)
a)) X + X ⋅ Y = X + Y
b) X ⋅ (X + Y) = X ⋅ Y
10)
43
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Teoremas com mais de uma variável:
9)
a)) X + X ⋅ Y = X + Y
b) X ⋅ (X + Y) = X ⋅ Y
10) Teoremas de “DeMorgan”
a)) X + Y + Z = X ⋅ Y ⋅ Z
b) X ⋅ Y ⋅ Z = X + Y + Z
44
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Dualidade
⎧0 → 1
⎪1 → 0
• a) → b) fazendo ⎨
+→⋅
⎪
⎩⋅ → +
• Em todos teoremas:
• A dualidade pode ser usada para simplificar expressões
booleanas. Feita a simplificação, forma anterior deve ser
restaurada.
restaurada
45
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Dualidade
• Exemplo: Simplificando X + X ⋅ Y
X +X⋅Y
⇓ dual
X ⋅ (X + Y) = X ⋅ X + X ⋅ Y = 0 + X ⋅ Y = X ⋅ Y
⇓ dual
= X+Y
46
2 Álgebra Booleana
2.
2.6. Teoremas Booleanos
• Exercícios – Simplificar as seguintes expressões:
(i) y = ABD + ABD
(v) y = ABCD + ABCD
(ii) y = (A + B)(A + B)
(vi) y = (A + C)(B + D)
(iii) y = ACD + ABCD
(iv) y = AD + ABD
47
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
possível implementar qualquer função lógica.
48
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
Inversor:
A
S=A
49
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
Inversor:
A
A
S=A
S= A⋅A = A
50
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
Inversor:
A
A
A
S=A
S= A⋅A = A
S=A+A =A
51
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
OR (“OU”):
A
B
S = A+B
52
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
OR (“OU”):
A
B
S = A+B
A
B
S = A+B = A+B
A+B
53
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
OR (“OU”):
A
B
S = A+B
54
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
OR (“OU”):
A
B
A
S = A+B
A⋅A = A
S= A⋅B
B
B⋅ B = B
=A+B
=A+B
55
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
AND (“E”):
A
B
S= A⋅B
56
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
AND (“E”):
A
B
S= A⋅B
A
B
S= A⋅B= A⋅B
A⋅B
57
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
AND (“E”):
A
B
S= A⋅B
58
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Somente com portas NAND ou somente com portas NOR
NOR, é
•
possível implementar qualquer função lógica.
AND (“E”):
A
B
A
S= A⋅B
A+A=A
S=A+B
B
B+B= B
= A⋅B
= A⋅B
59
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Exemplo: Implementar S = AB+CD usando somente NAND
60
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Exemplo: Implementar S = AB+CD usando somente NAND
AB
A
B
C
D
CD
S = AB+CD
61
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Exemplo: Implementar S = AB+CD usando somente NAND
A
B
C
D
62
2 Álgebra Booleana
2.
2.7. Universalidade das Portas NAND e NOR
• Exemplo: Implementar S = AB+CD usando somente NAND
A
B
C
D
S = AB
AB+CD
CD
63
EEL5105 – Circuitos e Técnicas Digitais
Aula 4
P f Eduardo
Prof.
Ed d L
L. O
O. B
Batista
ti t
[email protected]
http://www.inf.ufsc.br/~ebatista