Notas de aula: Álgebra Booleana e simplificação algébrica
UTFPR
Disciplina: EL66J
Prof. Gustavo B. Borba
Notas de aula
Álgebra Booleana e simplificação algébrica
George Boole, 1854: “An investigation of the laws of thought, on which are founded the
mathematical theories of logic and probability.”
Claude Shannon, 1938, aplicação da algebra Booleana na eletrônica: “Symbolic analysis of relay
and switching circuits.”
- Axiomas (há autores que chamam de postulados)
a1) A = 0 se A
a1’) A = 1 se A
1
a2) se A = 0, então A = 1
0
a2’) se A = 1, então A = 0
a3) 0 0 = 0
a3’) 1+1 = 1
a4) 1 1 = 1
a4’) 0+0 = 0
a5) 0 1 = 1 0 = 0
a5’) 1+0 = 0+1 = 1
- Teoremas (há autores que chamam de leis, propriedades, identidades, regras)
Involução
t1) A = A
t2) A 0 = 0
t2’) A+1 = 1
Elementos nulos
t3) A 1 = A
t3’) A+0 = A
Identidades
t4) A A = A
t4’) A+A = A
Idempotência
t5) A A = 0
t5’) A+A = 1
Complementos
t6) A B = B A
t6’) A+B = B+A
Comutativa
t7) (A B) C = A (B C)
t7’) (A+B)+C = A+(B+C)
Associativa
t8) A (B+C) = A B + B C
t8’) A+(B C) = (A+B) (A+C)
Distributiva
t9) A (A+B) = A
t9’) A + A B = A
Absorção
t10) A (A+B) = A B
t10’) A + A B = A+B
Absorção
t11) (A+B) (A+B) = A
t11’) A B + A B = A
Adjacência lógica
t12) A B + A C + B C = A B + A C
t12’) (A+B) (A+C) (B+C) = (A+B) (A+C)
Consenso
t13) A B ... Z = A+B+...+Z
t13’) A+B+...+Z = A B ... Z
DeMorgan
EL66J
1/3
Notas de aula: Álgebra Booleana e simplificação algébrica
- Algumas provas
t9) A (A+B) = A
(A+0) (A+B)
A+(0 B)
A+0
A
t10) A (A+B) = A B
t9’) A + A B = A
A1+AB
A (1+B)
A1
A
t10’) A + A B = A+B
AA + A B
0+AB
AB
t11) (A+B) (A+B) = A
Absorção
Absorção
(A+A) (A+B)
1 (A+B)
A+B
t11’) A B + A B = A
A + (B B)
A+0
A
Adjacência lógica
A (B+B)
A1
A
t12) A B + A C + B C = A B + A C
t12’) (A+B) (A+C) (B+C) = (A+B) (A+C)
A B + A C + B C (A+A)
AB+AC+BCA+BCA
AB+ABC+AC+ACB
A B (1+C) + A C (1+B)
AB1+AC1
AB+AC
(A+B) (A+C) ((B+C)+A A)
(A+B) (A+C) (B+C+A) (B+C+A)
(A+B) (A+B+C) (A+C) (A+C+B)
((A+B)+(0 C)) ((A+C)+(0 B))
(A+B+0) (A+C+0)
(A+B) (A+C)
Consenso
- Símbolos equivalentes para as portas NE e NOU
Conforme os teoremas de DeMorgan:
Assim, às vezes são utilizados os símbolos a seguir para representar as portas NE e NOU:
EL66J
2/3
Notas de aula: Álgebra Booleana e simplificação algébrica
- Exemplos
1. DeMorgan
b) Y = A B C + D E F
a) Y = A+B+C+D E
c) Y = (A B+C) (D+E F)
d) Y = A+B C+D (E+F)
A B C + D+E
ABC DEF
(A B+C)+(D+E F)
(A (B+C))+(D (E F))
A B C + D+E
(A+B+C) (D+E+F)
(A+B) C + D (E+F)
(A+(B C)) (D+(E+F))
(A+B C) (D+E+F)
Resolver 'de fora para
dentro' seria mais fácil.
2. Prove que os
circuitos são
equivalentes
A
A
Y1
Y2
B
B
Y2 = A B+A+B
Y1 = A B (A+B)
A B+A+B
=
A B+A+B
3. Simplifique o
circuito
A
Y = A B B+C
(A+B) B C
Y
B
A B C+B B C
B
C
Y
B C (A+1)
C
BC
4. Simplifique as expressões
a) Y = AB + A(B+C) + B(B+C)
b) Y = (AB(C + BD) + AB)C
c) Y = (A+B)(A+C)
d) Y = AB + ABC + A
AB + AB + AC + BB + BC
(ABC + ABBD + AB)C
AA + AC + AB + BC
(AB + AB)(AB + C) + A
AB + AC + B + BC
(ABC + 0 + AB)C
A + AC + AB + BC
1(AB + C) + A
B(1+A+C) + AC
ABCC + ABC
A(1+C+B) + BC
AB + C + A
B1 + AC
ABC + ABC
A1 + BC
A(1+B) + C
B + AC
BC(A + A)
A + BC
A1 + C
A+C
BC1
BC
e) Y = ABC + A+B+C + ABCD
f) Y = ABC(AB+C(BC+AC))
g) Y = AB + A+C
h) Y = AB + CD + ACD
ABC + ABC + ABCD
ABC(AB+BCC+ACC)
A + B + AC
ABCD + AC + D
ABC + ABC + ABCD
ABC(AB+0+0)
A(1+C) + B
AB(C+D) + A + C + D
ABC + ABCD
ABC(AB)
A1 + B
ABC + ABD + A + C + D
AB(C + CD)
AABBC
A+B
C(AB+1) + A + ABD + D
AB((C+C)(C+D))
ABC
C1 + (A+A)(A+BD) + D
AB(1(C+D))
C + 1(A+BD) + D
AB(C+D)
C + A + D + DB
C + A + (D+D)(D+B)
C + A + 1(D+B)
C+A+D+B
EL66J
3/3