Algebra de Boole

Prévia do material em texto

A´lgebra de Boole
Joa˜o Paulo Cerquinho Cajueiro
19 de agosto de 2009
A a´lgebra de Boole foi desenvolvida por George Boole(1815–1864) em seu
livro An Investigation of the Laws of Thought on Which are Founded the Mathe-
matical Theories of Logic and Probabilities de 1854. Ela buscava uma base ma-
tema´tica formal para a lo´gica e probabilidade e passou um longo tempo sendo
conhecida apenas por matema´ticos, sem encontrar uma utilidade pra´tica. Foi,
de certo modo, descoberta por Claude Shannon(1916–2001), que a utilizou em
sua tese de mestrado A Symbolic Analysis of Relay and Switching Circuits em
1937 para desenvolver circuitos ele´tricos que realizassem func¸o˜es lo´gicas.
1 Postulados
Pensando em probabilidade, a ide´ia ba´sica da a´lgebra booleana e´ de utilizar
conceitos de a´lgebra para expressar questo˜es de probabilidade ou de lo´gica.
Neste sentido o nu´mero 1 expressa o conceito lo´gico de verdadeiro ou o conceito
probabil´ıstico (ou melhor, de teoria de conjuntos) de todo o espac¸o amostral,
o 0 e´ o equivalente lo´gico de falso ou de conjunto nulo, a soma + equivale
ao ou lo´gico e a unia˜o (∪) de conjuntos e a multiplicac¸a˜o equivale a operac¸a˜o
lo´gica e e a intersecc¸a˜o (∩) de conjuntos. Os potulados sa˜o feitos de modo a
garantir esta equivaleˆncia.
Postulado 1 – Operac¸o˜es:
A a´lgebra de Boole tem um conjunto K de 2 ou mais valores e duas operac¸o˜es:
· e +, de modo que para todo a, b pertencentes a K:
(a) a · b ∈ K
(b) a + b ∈ K
(P1)
Postulado 2 – Valores Neutros:
Existem valores 0 e 1 tais que:
(a) a + 0 = a
(b) a · 1 = 1
(P2)
Postulado 3 – comutatividade:
(a) a + b = b + a
(b) a · b = b · a
(P3)
1
Postulado 4 – associatividade:
(a) a + (b + c) = (a + b) + c
(b) a · (b · c) = (a · b) · c
(P4)
Postulado 5 – distributividade:
(a) a + (b · c) = (a + b) · (a + c)
(b) a · (b + c) = (a · b) + (a · c)
(P5)
Postulado 6 – existeˆncia de complemento:
Para todo a ∈ K, existe um e apenas um a ∈ K, chamado o complemento de a,
tal que:
(a) a + a = 1
(b) a · a = 0
(P6)
2 Teoremas
Va´rias caracter´ısticas da a´lgebra de Boole na˜o aparecem diretamente nos pos-
tulados, mas podem ser inferidas a partir deles. Muitas destas caracter´ısticas
sera˜o u´teis para no´s, e abaixo descrevemos 10 teoremas, provados a partir dos
postulados (ou de teoremas ja´ provados, o que da´ no mesmo).
Dentre os 10 teoremas mostrados, 9 deles tem 2 formas, aqui chamadas de (a)
e (b), que sa˜o as formas duais dos teoremas. A dualidade sera´ melhor discutida
usando o teorema 1 como exemplo.
Teorema 1:
A soma ou o produto de um valor por ele mesmo e´ igual a ele mesmo.
(a) a + a = a
(b) a · a = a
(T1)
E a prova deste teorema encontra-se abaixo:
Prova:
a = a + 0
= a + a · a
= (a + a) · (a + a)
= (a + a) · 1
a = a + a
a = a · 1
= a · (a + a)
= (a · a) + (a · a)
= (a · a) + 0
a = a · a
Note que a prova de T1(a) e´ ideˆntica a de T1(b), ao se trocar as operac¸o˜es
de soma por multiplicac¸a˜o e vice-versa e os 0’s por 1’s e vice-versa. Isto na˜o e´
uma coincideˆncia, mas vem diretamente do fato de que os postulados tem esta
simetria. Em a´lgebra de Boole isto e´ chamado de dualidade. Diz-se enta˜o que
uma expressa˜o e´ o dual da outra quando se trocam os · por + e vice-versa e os
0’s por 1’s e vice-versa.
Ale´m disso, a simetria dos postulados garante que: se uma expressa˜o f e´
verdadeira, logo a expressa˜o dual fd tambe´m e´ verdadeira. Por conta disto, para
todos os teoremas subsequentes que tenham expresso˜es duais, so´ provaremaos
uma delas, ja´ que o dual do teorema e´ automaticamente verdadeiro.
2
Teorema 2:
(a) a + 1 = 1
(b) a · 0 = 0
(T2)
Prova:
a + 1 = a + (a + a)
= (a + a) + a
= a + a
a + 1 = 1
Teorema 3:
a = a (T3)
Prova:
Seja a = b:
b · a = a · b = a · a , 0
b + a = a + b = a + a , 1
logo:
a , b = a
Teorema 4:
(a) a + a · b = a
(b) a · (a + b) = a
(T4)
Prova:
a + a · b = a · 1 + a · b
= a(b + b + a · b
= a · b + a · b + a · b
= a · b + a · b
= a · 1
a + a · b = a
O significado deste teorema e´ melhor visto atrave´s de um diagrama de Venn1,
mostrando a e a · b (lembrando que a multiplicac¸a˜o equivale a` intersecc¸a˜o e a
soma a` unia˜o). A figura 1 mostra justamente isto.
Teorema 5:
(a) a + a · b = a + b
(b) a · (a + b) = a · b
(T5)
3
a ba · b
Figura 1: Diagrama de Venn demostrando o teorema T4.
a a · b
Figura 2: Diagrama de Venn demonstrando o teorema T5.
Prova:
a + a · b = (a + a · b) + a · b
= a + b(a + a)
= a + b · 1
a + a · b = a + b
Teorema 6:
(a) a · b + a · b = a
(b) (a + b) · (a + b) = a
(T6)
Prova:
a · b + a · b = a(b + b)
= a · 1
a · b + a · b = a
1na verdade, este e´ um diagrama de Johnston. Um diagrama de Venn mostraria todas as
possibilidades: a · b, a · b, a · b e a · b.
4
a · b a · b
Figura 3: Diagrama de Venn demonstrando o teorema T6.
a · b · c
a · b
c
a b
Figura 4: Diagrama de Venn demostrando o teorema T7.
Teorema 7:
(a) a · b + a · b · c = a · b + a · c
(b) (a + b) · (a + b + c) = (a + b) · (a + c)
(T7)
Prova:
a · b + a · b · c = a · b · 1 + a · b · c
= a · b · (1 + c) + a · b · c
= a · b · 1 + a · b · c + a · b · c
= a · b + a · c(b + b)
a · b + a · b · c = a · b + a · c
Teorema 8 – Leis de DeMorgan2:
(a) a + b = a · b
(b) a · b = a + b
(T8)
5
a · b
a + b
a + b
a · b
Figura 5: Diagrama de Venn mostrando que a)a · b e´ o complemento de a + b e
que b)a + b e´ o complemento de a · b para provar as Leis de deMorgan (T8).
Prova:
Prova-se mostrando que a · b e´ o complemento de a+b:
(a + b)a · b = a · a · b + b · a · b
= 0 + 0
(a + b)a · b = 0
(a + b) + a · b = (a + b + a)(a + b + b)
= (1 + b)(1 + a)
= 1 · 1
(a + b) + a · b = 1
Logo:
a + b , a · b
E´ poss´ıvel ainda aplicar o teorema repetidas vezes e provar que:
f (x1, x2, . . . , xn) = fd (x1, x2, . . . , xn)
Teorema 9 – Teorema do consenso:
(a) a · b + a · c + b · c = a · b + a · c
(b) (a + b) · (a + c) · (b + c) = (a + b) · (a + c)
(T9)
Prova:
a · b + a · c + b · c = (a · b · c + a · b · c) + (a · b · c + a · b · c) + (a · b · c + a · b · c)
= (a · b · c + a · b · c) + a · b · c + (a · b · c + a · b · c) + a · b · c
= a · b · c + a · b · c + a · b · c + a · b · c
= (a · b · c + a · b · c) + (a · b · c + a · b · c)
a · b + a · c + b · c = a · b + a · c
6
a · c
a · b
Figura 6: Diagrama de Venn demonstrando o teorema do consenso.
Teorema 10 – Expansa˜o de Shannon3:
(a) f (x1, x2, . . . , xn) = x1 · f (1, x2, . . . , xn) + x1 · f (0, x2, . . . , xn)
(b) f (x1, x2, . . . , xn) = [x1 + f (0, x2, . . . , xn)] · [x1 + f (1, x2, . . . , xn)]
(T10)
Prova:
Considerando que x1 ·x1 = x1 · 1 e que x1 ·x1 = x1 ·x1 ·x1 = x1 · 0, podemos
afirmar que:
x1 · f (x1, x2, . . . , xn) = x1 · f (1, x2, . . . , xn)
E pelo mesmo racioc´ınio chegamos a:
x1 · f (x1, x2, . . . , xn) = x1 · f (0, x2, . . . , xn)
Podemos enta˜o separar a func¸a˜o e aplicar estas igualdades:
f(. . .) = 1 · f(. . .)
= x1 · f(. . .) + x1 · f(. . .)
f(. . .) = x1 · f (1, x2, . . . , xn) + x1 · f (0, x2, . . . , xn)
3 Aplicac¸a˜o dos postulados e teoremas
Podemos aplicar os postulados e teoremas da a´lgebra de Boole para simplificar
equac¸o˜es booleanas. Como estas equac¸o˜es sera˜o ou sa˜o implementadas por um
circuito, isto significa um circuito menor e, consequentemente, mais barato e
mais ra´pido. A tabela 1 condensa todas os postulados e teoremas ate´ enta˜o
desenvolvidos para facilitar o acesso.
Exemplo 1:
Minimize o circuito lo´gico mostrado na figura 7.
7
P1 ∀a, b ∈ K : a · b ∈ K ∀a, b ∈ K : a + b ∈ K
P2 a + 0 = a a · 1 = 1
P3 a + b = b + a a · b = b · a
P4 a + (b + c) = (a + b) + c a · (b · c) = (a · b) · c
P5 a + (b· c) = (a + b) · (a + c) a · (b + c) = (a · b) + (a · c)
P6 a + a = 1 a · a = 0
T1 a + a = a a · a = a
T2 a + 1 = 1 a · 0 = 0
T3 a = a
T4 a + a · b = a a · (a + b) = a
T5 a + a · b = a + b a · (a + b) = a · b
T6 a · b + a · b = a (a + b) · (a + b) = a
T7 a · b + a · b · c = a · b + a · c (a + b) · (a + b + c) = (a + b) · (a + c)
T8 a + b = a · b a · b = a + b
T9 a · b + a · c + b · c = a · b + a · c (a + b) · (a + c) · (b + c) = (a + b) · (a + c)
T10 f (x1, . . .) = x1 · f (1, . . .) + x1 · f(0, . . .) f(x1, . . .) = [x1 + f(0, . . .)] · [x1 + f(1, . . .)]
Tabela 1: Resumo dos postulados e Teoremas.
a
b
c
z
Figura 7: Circuito do exemplo 1.
Resoluc¸a˜o:
Pela ana´lise do circuito obtemos z = abc+ac · ab. Aplicamos agora os postulados
8
e teoremas cab´ıveis:
z(a, b, c) = abc + ac · ab
︸︷︷︸
T8
= abc + ac · (a + b)
︸ ︷︷ ︸
T3
= abc + ac(a + b)
︸ ︷︷ ︸
P5
= abc + aca
︸︷︷︸
P3
+ acb
︸︷︷︸
P3
= abc + aa ·
︸︷︷︸
T1
c + abc
= abc + ac + abc
︸ ︷︷ ︸
P3
= abc + abc
︸ ︷︷ ︸
T6
+ac
= ab + ac
︸ ︷︷ ︸
P5
z(a, b, c) = a(b + c)
O circuito simplificado e´ mostrado na figura 8.
a
b
c
z
Figura 8: Circuito simplificado do exemplo 1.
4 Formas canoˆnicas
Ha´ casos em que e´ necessa´rio obter uma equac¸a˜o booleana a partir de uma ta-
bela verdade. Nestas situac¸o˜es sa˜o bastante u´teis as formas canoˆnicas (tambe´m
conhecidas de formas padro˜es) de soma de mintermos ou produto de maxtermos.
Obviamente para entendeˆ-las precisamos primeiro saber o que sa˜o mintermos e
maxtermos. Vamos comec¸ar pela definic¸a˜o de mintermos e analisar a forma de
soma de mintermos.
Um mintermo e´ um produto na˜o barrado de todas as varia´veis da
func¸a˜o, sejam elas barradas ou na˜o.
Considerando uma func¸a˜o de 4 varia´veis, sa˜o exemplos de mintermos: abcd,
abcd e abcd.
9
Na˜o sa˜o mintermos abc (pois na˜o tem todas as varia´veis), ab + cd (pois na˜o e´
um produto das 4 varia´veis), ab(cd) (pois as varia´veis tem que ser barradas uma
a uma) e nem abcdd (pois a varia´vel d esta´ repetida).
Um exemplo de func¸a˜o descrita na forma soma de mintermos (por sim-
plicidade referido por sdm- soma de mintermos) e´ a func¸a˜o de 3 varia´veis
g = abc + abc + abc. Para entender a utilidade desta forma, observe a ta-
bela 2, que e´ uma tabela verdade da func¸a˜o g e de cada um dos mintermos
presentes nela.
a b c abc abc abc g
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 1 0 0 1
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 1 0 1
1 1 1 0 0 1 1
Tabela 2: tabela verdade da func¸a˜o g = abc + abc + abc e seus mintermos.
Um mintermo, sendo um produto de todas as varia´veis presentes, so´ pode
ser 1 em um u´nico caso, o que e´ exemplificado na tabela. Ale´m disso mintermos
diferentes representam um 1 em posic¸o˜es diferentes da tabela verdade, logo a
soma de mintermos indica qual das posic¸o˜es da tabela-verdade e´ 1. Com base
nisto, e´ poss´ıvel descrever qualquer func¸a˜o lo´gica no formato sdm.
Fica enta˜o fa´cil obter uma tabela verdade a partir de uma equac¸a˜o na forma
sdm ou vice-versa. Dada uma tabela verdade qualquer, cada linha em que a
func¸a˜o e´ 1 corresponde a um mintermo. O mintermo abc so´ sera´ 1 quando a
etrada for abc = 111; abc sera´ 1 quando abc = 011 e assim por diante. Ou seja,
para uma varia´vel na˜o barrada num mintermo corresponde aquela varia´vel ser
1 na tabela verdade e uma varia´vel barrada corresponde a um 0.
A tabela 4 apresenta todos os mintermos de uma func¸a˜o de 4 varia´veis junto
com a respectiva entrada que faz ele ser 1. Obviamente, com 2 varia´veis temos
4 mintermos poss´ıveis (ab, ab, ab e ab), com 3 varia´veis temos 8 mintermos
poss´ıveis, com 4 temos 16 e assim por diante.
E´ bastante usual se trabalhar com equac¸o˜es na forma sdm. Uma das ra-
zo˜es para isso e´ que uma sdm e´ uma soma de produtos, obviamente, e estamos
acostumados a trabalhar com equac¸o˜es na forma de soma de produtos devido
a`s propriedades da a´lgebra convencional. Mas a a´lgebra de Boole abre a opor-
tunidade de trabalharmos com uma equac¸a˜o na forma produto de somas, o que
leva a uma forma padra˜o alternativa: a forma padra˜o produto de maxtermos
(ou pdm).
Um maxtermo e´ uma soma na˜o barrada de todas as varia´veis da
func¸a˜o, sejam elas barradas ou na˜o.
Considerando uma func¸a˜o de 4 varia´veis, sa˜o exemplos de maxtermos: a +
b + c + d, a + b + c + d e a + b + c + d.
Na˜o sa˜o maxtermos a + b + c (pois na˜o tem todas as varia´veis), ab + cd (pois
10
na˜o e´ um produto das 4 varia´veis), a+ b+(c + d) (pois as varia´veis tem que ser
barradas uma a uma) e nem a + b + c + d + d (pois a varia´vel d esta´ repetida).
Da mesma forma que fizemos com mintermos, vamos analisar a func¸a˜o exem-
plo g′ = (a + b + c) · (a + b + c) · (a + b + c) para entender a utilidade da forma
pdm, observe a tabela 3, que e´ uma tabela verdade da func¸a˜o g e de cada um
dos maxtermos presentes nela.
a b c a + b + c a + b + c a + b + c g′
0 0 0 1 1 0 0
0 0 1 1 0 1 0
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 0
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
Tabela 3: tabela verdade da func¸a˜o g′ = (a + b + c) · (a + b + c) · (a + b + c) e
seus maxtermos.
Observa-se analisando a tabela que cada maxtermo so´ e´ 0 para um u´nico
vetor de entrada e 1 para qualquer outra entrada. Pegando como exemplo o
maxtermo a+ b+ c, como se trata de uma soma, ele e´ 1 sempre que a = 1, que
b = 1 ou que c = 0 (pois c esta´ barrado), logo ele so´ e´ 0 quando a = b = 0
e c = 1. Isto quer dizer que, enquanto cada mintermo representava uma linha
da tabela verdade com sa´ıda 1, cada maxtermo representa uma linha na tabela
verdade com sa´ıda 0.
E para unir diferentes maxtermos, faz-se o produto deles, pois assim os 0’s
se somam na fo´rmula final. Da´ı a forma ser o produto dos maxtermos. Fica
enta˜o fa´cil descrever qualquer func¸a˜o como sdm ou pdm a partir de uma tabela
verdade. Ou de uma equac¸a˜o em uma das duas forma padro˜es, obter a tabela
verdade. A tabela 4 mostra tambe´m os 16 maxtermos equivalentes a cada
entrada poss´ıvel com 4 varia´veis.
Exemplo 2:
Reanalisando as tabelas 2 e 3, e´ fa´cil chegar nas equac¸o˜es das func¸o˜es g na
forma pdm e g′ na forma sdm:
g = (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c) (1)
g′ = abc + abc + abc + abc + abc (2)
Exemplo 3:
Deseja-se implementar um circuito que acione uma sa´ıda f caso 2 ou mais de
suas 3 entradas A, B e C forem 1.
Resoluc¸a˜o (Usando Mintermos):
O primeiro passo e´ montar a tabela verdade da func¸a˜o f , vide tabela 5
Analisando a tabela 5, podemos obter a equac¸a˜o de f na forma sdm.
f(A,B,C) = ABC + ABC + ABC + ABC (3)
11
a b c d mintermo maxtermo
0 0 0 0 abcd a + b + c + d
0 0 0 1 abcd a + b + c + d
0 0 1 0 abcd a + b + c + d
0 0 1 1 abcd a + b + c + d
0 1 0 0 abcd a + b + c + d
0 1 0 1 abcd a + b + c + d
0 1 1 0 abcd a + b + c + d
0 1 1 1 abcd a + b + c + d
1 0 0 0 abcd a + b + c + d
1 0 0 1 abcd a + b + c + d
1 0 1 0 abcd a + b + c + d
1 0 1 1 abcd a + b + c + d
1 1 0 0 abcd a + b + c + d
1 1 0 1 abcd a + b + c + d
1 1 1 0 abcd a + b + c + d
1 1 1 1 abcd a + b + c + d
Tabela 4: Mintermos e maxtermos equivalentes a cada um dos poss´ıveis valores
de entrada de uma func¸a˜o de 4 varia´veis.
A B C f
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Tabela 5: Tabela verdade da func¸a˜o f .
E enta˜o basta aplicar os postulados e teoremas cab´ıveis a` equac¸a˜o 3 para
12
minimizar a func¸a˜o.
f(A,B,C) = ABC + ABC + ABC + ABC
︸ ︷︷ ︸
AB (T6)
= ABC + ABC + AB
︸ ︷︷ ︸
AC+AB (T7)
= ABC + AC
︸ ︷︷ ︸
BC+AC (T7)
+AB
f(A,B,C) = BC + AC + AB (4)
Resoluc¸a˜o (Usando maxtermos):
Reanalisando a tabela 5, obtemos a equac¸a˜o de f na forma pdm.
f(A,B,C) = (A + B + C)(A + B + C)(A + B + C)(A + B + C)(5)
E novamente aplicando os postulados e teoremas cab´ıveis:
f(A,B,C) = (A + B + C)(A + B + C)
︸ ︷︷ ︸
A+B (T6)
(A + B + C)(A + B + C)
= (A + B) (A + B + C)
︸ ︷︷ ︸
A+C (T7)
(A + B + C)
= (A + B)(A + C) (A + B + C)
︸ ︷︷ ︸
B+C (T7)
f(A,B,C) = (A + B)(A + C)(B + C) (6)
E´ fa´cil mostrar que a equac¸a˜o 6 e´ equivalente a` 4. Para tanto basta aplicar
repetidas vezes o postulado da distributividade (P5).
13