Algebra booleana

Notas de aula: Álgebra Booleana e simplificação algébrica

UTFPR Disciplina: EL66J Prof. Gustavo B. Borba

Álgebra Booleana e simplificação algébrica

Notas de aula

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

1

a1’) A = 1 se A

0

a2) se A = 0, então A = 1 a3) 0 0 = 0 a4) 1 1 = 1 a5) 0 1 = 1 0 = 0

a2’) se A = 1, então A = 0

a3’) 1+1 = 1 a4’) 0+0 = 0 a5’) 1+0 = 0+1 = 1

- Teoremas (há autores que chamam de leis, propriedades, identidades, regras)

t1) A = A t2) A 0 = 0 t3) A 1 = A t4) A A = A t5) A A = 0 t6) A B = B A t7) (A B) C = A (B C) t8) A (B+C) = A B + B C t9) A (A+B) = A t10) A (A+B) = A B t11) (A+B) (A+B) = A t12) A B + A C + B C = A B + A C t13) A B ... Z = A+B+...+Z t2’) A+1 = 1 t3’) A+0 = A t4’) A+A = A t5’) A+A = 1

Involução Elementos nulos Identidades Idempotência Complementos Comutativa Associativa Distributiva Absorção Absorção Adjacência lógica Consenso DeMorgan

t6’) A+B = B+A t7’) (A+B)+C = A+(B+C) t8’) A+(B C) = (A+B) (A+C) t9’) A + A B = A t10’) A + A B = A+B t11’) A B + A B = A

t12’) (A+B) (A+C) (B+C) = (A+B) (A+C) t13’) A+B+...+Z = A B ... Z

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

t9’) A + A B = A
A1+AB A (1+B) A1 A

Absorção

t10) A (A+B) = A B
AA + A B 0+AB AB

t10’) A + A B = A+B
(A+A) (A+B) 1 (A+B) A+B

Absorção

t11) (A+B) (A+B) = A
A + (B B) A+0 A

t11’) A B + A B = A
A (B+B) A1 A

Adjacência lógica

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

t12’) (A+B) (A+C) (B+C) = (A+B) (A+C)
(A+B) (A+C) ((B+C)+A A) (A+B) (A+C) (B+C+A)