Introdução à Engenharia de
Computação
Álgebra de Boole
Universidade Federal da Paraíba
Departamento de Informática
Álgebra de Boole
• A idéia básica da álgebra booleana é utilizar
conceitos de álgebra para expressar questões de
probabilidade ou de lógica
– 1 expressa o conceito lógico de verdadeiro ou o
conceito probabilístico (Teoria dos Conjuntos) de todo
o espaço amostral
– 0 é o equivalente lógico de falso ou de conjunto nulo
a
b
c
Universidade Federal da Paraíba
Departamento de Informática
Álgebra de
Boole
f(a,b,c,...)
Álgebra de Boole
• A soma “+” equivale:
– “ou” lógico, or, v
– “” união da teoria dos conjuntos
• A multiplicação “.” equivale
– “e” lógico, and, ^
– “” interseção da teoria dos conjuntos
• O and lógico (multiplicação) tem prioridade em relação ao or (soma)
– Tente diferenciar resolvendo a expressão: 1+1 .0
Universidade Federal da Paraíba
Departamento de Informática
Exemplos de Conjuntos
Universidade Federal da Paraíba
Departamento de Informática
Exemplos de Conjuntos
A=
B=
C=
A=
B=
C=
Universidade Federal da Paraíba
Departamento de Informática
Exemplos de Conjuntos
• Conjuntos :
– 1 = A . B . C
– 2 = A . C + A . B
– 3 = A . A = 0
– 4 = A + B + A . B = 1
– 5 =
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Postulado 1 – Operações
– A álgebra de Boole tem um conjunto K de 2 ou mais
variáveis e duas operações: · e +
– Para todo a, b pertencentes a K:
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Adição
• Multiplicação
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Postulado 2 – Valores Neutros
– Para os valores constantes 0 e 1 e uma variável “a”
temos que:
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Postulado 3 – Comutatividade
– Para qualquer valor “a” e “b” temos que:
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Postulado 4 – Associatividade
– Para qualquer valor “a”, “b” e “c” temos que:
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Postulado 5 – Distributividade
– Para qualquer valor “a”, “b” e “c” temos que:
Universidade Federal da Paraíba
Departamento de Informática
Postulados
• Postulado 6 – Existência de Complemento
– Para todo a  K, existe um e apenas um ā  K,
chamado o complemento de a,tal que:
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• OBSERVAÇÃO (Postulado x Teorema)
– Um axioma ou POSTULADO é uma verdade auto-evidente, na
qual outros conhecimentos se devem apoiar e a partir da qual
outro conhecimento é construído
– Por TEOREMA entende-se a fórmulas, proposição , ou frase
matemática que, para se admitir ou tornar evidente, precisa de
demonstração (geralmente usando POSTULADOS e/ou
TEOREMAS já provados)
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 1
– A soma ou o produto de um valor por ele mesmo é
igual a ele mesmo.
Prova:
a=a+0
[vn]
Prova:
a=a.1
a=a+a.ā
[ec]
a=a.a+ā
a = (a + a) . (a + ā)
[dis]
a = (a . a) + (a . ā)
a = (a + a) . 1
[ec]
a = (a . a) + 0
a=a+a
[vn]
a=a.a
Note a propriedade da dualidade
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 2
– A soma ou o produto de um valor pelo elemento não
neutro da operação é igual a este elemento.
Prova:
a + 1 = a + (a + ā)
[ec]
Prova:
a . 0 = a . (a . ā)
a + 1 = (a + a) + ā
[ass]
a . 0 = (a . a) . ā
a+1=a+ā
[T1]
a.0=a.ā
a+1=1
[ec]
a.0=0
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 3
– O complemento do complemento de um valor é igual
ao próprio valor.
Prova:
Seja ā = u
a=ū
a=ā
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 4
– A soma ou multiplicação de um valor pelo resultado da operação
oposto deste mesmo valor com outro qualquer é igual ao valor
inicial.
Prova:
a+a.b=a.1+a.b
= a.(b + b) + a . b
[T2]
[ec]
= a . b + a . b + a . b [dis]
=a.b+a.b
=a.1
a+a.b=a
Universidade Federal da Paraíba
Departamento de Informática
[???]
[???]
[vn]
Prova:
a . (a + b ) = ...
Teoremas
• Teorema 4
– O significado deste teorema é melhor visto através de
um diagrama de Johnston.
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 5
– A soma ou multiplicação de um valor pelo resultado da operação
oposto do complemento deste mesmo valor com outro qualquer é
igual a mesma operação do primeiro e último valor.
Prova:
a + ā . b = (a + a . b) + ā . b [T4]
= a + b. ( a + ā )
[dis]
=a+b.1
[vn]
a + ā. b = a + b
Universidade Federal da Paraíba
Departamento de Informática
[en]
Prova:
a . (ā + b ) = ...
Teoremas
• Teorema 5
– A soma ou multiplicação de um valor pelo resultado da operação
oposto do complemento deste mesmo valor com outro qualquer é
igual a mesma operação do primeiro e último valor.
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 6
Prova:
a.b+a.b=a.(b+b)
=a.1
a.b+a.b=a
Universidade Federal da Paraíba
Departamento de Informática
[dis]
[ec]
[vn]
Prova:
(a + b) . (a + b ) = a
...
Teoremas
• Teorema 6
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 7
Prova:
a.b+a.b.c=a.b.1+a.b.c
= a . b. (1 + c) + a . b . c
[T2]
= a . b. 1 + a . b . c + a . b . c
[dis]
= a . b + a . c . (b + b)
[dis]
a.b+a.b.c=a.b+a.c
Universidade Federal da Paraíba
Departamento de Informática
[vn]
[ec]
Prova:
...
Teoremas
• Teorema 7
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 8 – Leis de DeMorgan
Prova: mostramos que ā.b é o complemento de a+b
Universidade Federal da Paraíba
Departamento de Informática
Teoremas
• Teorema 8 – Leis de DeMorgan
Prova: mostramos que a.b é o complemento de a+b
(a + b) + ā . b = (a + b + ā) . (a + b . b)
= (1 + b) . (1 + a)
[ec]
=1.1
[T2]
(a + b) + ā . b = 1
Universidade Federal da Paraíba
Departamento de Informática
[dis]
[op]
Teoremas
• Teorema 9 – Teorema do Consenso
[ass]
[T1]
[ass]
a.b+ā.c+b.c =a.b+ā.c
Universidade Federal da Paraíba
Departamento de Informática
[dis + ec]
Teoremas
• Teorema 9 – Teorema do Consenso
c
a
Universidade Federal da Paraíba
Departamento de Informática
b