Teoremas e Postulados da Algebra Booleana

Prévia do material em texto

Álgebra Booleana (nosso contexto)
Definida através de um conjunto de elementos (variáveis, constantes) e operações
1. Resumo
Conjunto de elementos: B = {0, 1}
• Operação “+” (OU – OR) 
0+0=0 
0+1=1 
1+0=1 
1+1=1 
• Operação “.” (E – AND) 
0.0=0 
0.1=0 
1.0=0 
1 . 1 = 1 
• Operação “ ' “ (negação)
0' = 1
1' = 0
Sejam “a” , “b” e “c” variáveis booleanas e “0” e “1” constantes.
2. Postulados:
P0 (associatividade): i) a + (b + c) = (a + b) + c // ii) a . (b . c) = (a . b) . c
P1 (comutatividade): i) a + b = b + a // ii) a . b = b . a 
P2 (distributividade): i) a + (b . c) = (a + b) . (a + c) // ii) a . (b + c) = (a . b) + (a . c) 
P3 (identidade): i) a + 0 = a // ii) a . 1 = a 
P4 (complementaridade): i) a + a' = 1 // ii) a . a' = 0
3. Princípios:
Dualidade: toda identidade algébrica dedutível dos postulados permanece válida se:
i) “+” for trocado por “.” e vice-versa;
ii) o elemento “0” for trocado por “1” e vice-versa.
Precedência:
i) “.” tem precedência sobre “+”
ii) parênteses podem ser utilizados para forçar precedência
Teoremas:
1) todo elemento de B tem um complemento único 
2) i) a + 1 = 1 // ii) a . 0 = 0 
3) i) 0' = 1 // ii) 1' = 0
4) (Idempotência) i) a + a = a // ii) a . a = a
5) (Involução) (a ' ) ' = a
6) (Absorção) i) a + a . b = a // ii) a . (a + b) = a
7) i) a + a' . b = a + b // ii) a . (a ' + b ) = a . b
Morgan: i) (a + b) ' = a ' . b ' // ii) (a . b) ' = a ' + b ' (generalizável para a, b, c ...)