Introdução
A álgebra booleana, como qualquer outro sistema matemático dedutível, pode ser definido como um conjunto de elementos, um conjunto de operadores, e um número de axiomas, ou postulados, não provados.
Os postulados de um sistema
matemático são as suposições, ou considerações
básicas a partir das quais é possível se deduzirem
as regras, os teoremas, e as propriedades do sistema. Os postulados mais
comuns usados para se formularem várias estrutruras algébricas
são:
| 1 – Fechamento: | a * b = c | a,b,c Î S |
| 2 – Lei Associativa: | (a * b) * c = a * (b * c) | a,b,c Î S |
| 3 – Lei Comutativa: | a * b = b * a | a,b Î S |
| 4 – Elemento Identidade: | e * a = a * e = a | a Î S |
| 5 – Inversa: | a * b = e | a,b Î S |
| 6 – Lei Distributiva: | a * (b # c) = (a * b) # (a * c) | a,b,c Î S |
Um exemplo de estrutura algébrica é um corpo (field). Um corpo é um conjunto de elementos, juntamente com dois operadores binários, cada um atendendo as 5 primeiras leis, e os dois combinados para atender a 6a .
A álgebra de Boole
é uma estrutura algébrica definida sobre um conjunto B de
elementos, juntamente com dois operadores + e ·
tal que os seguintes postulados (de Huntington) sejam satisfeitos:
1 – a – fechamento em relação ao operador +;
b – fechamento em relação ao operador · ;2 – a – um elemento identidade em relação a + , designado por 0;
b – um elemento identidade em relação a · , designado por 1;3 – a – Lei comutativa em relação a +;
b – Lei comutativa em relação a · ;4 – a – · é distributiva em relação a + : a· (b+c) = a· b + a· b;
b – + é distributiva em relação a · : a+(b· c) = a+b · a+b;5 – para todo elemento a Î B, existe um elemento a’ Î B (chamado complemento de a)
tal que: (a) a + a’ = 1 e (b) a · a’ = 0 ;6 – Existem pelo menos dois elemntos a, b Î B tal que a ¹ b.
Como a álgebra de
Boole lembra a ágebra dos números reais, os símbolos
+ e · foram escolhidos para representar
seus operadores apenas por atuarem de forma parecida à dos operadores
de soma e multiplicação da álgebra real. Na álgebra
de Boole só existem dois elementos, que pelo motivo de lembrar a
álgebra dos números reais, foram escolhidos 0 e 1.
Operadores utilizados na Álgebra de Boole:
+
adição, união, operação lógica
OU
·
multiplicação, interseção, operação
lógica E
Elementos utilizados na Ágebra de Boole:
0
nível lógico zero, negativo, desligado
1
nível lógico um, afirmativo, ligado
Postulados
e teoremas da Álgebra de Boole
| Caso (a) | Caso (b) | |
| Postulado 2 | a + 0 = a | a · 1 = a |
| Postulado 5 | a + a’ = 1 | a · a’ = 0 |
| Teorema 1 | a + a = a | a · a = a |
| Teorema 2 | a + 1 = 1 | a · 0 = 0 |
| Teorema 3, involução | (a’)’ = a | (a’)’ = a |
| Postulado 3, comutativo | a + b = b + a | a · b = b · a |
| Teorema 4, associativo | a + (b+c) = (a+b) + c | a · (b· c) = (a · b) · c |
| Postulado 4, distributivo | a · (b+c) = (a · b)+(a · c) | a+(b · c) = (a+b) · (a+c) |
| Teorema 5, DeMorgan | (a + b)’ = a’ · b’ | (a · b)’ = a’ + b’ |
| Teorema 6, absorção | a + (a · b) = a | a · (a + b) = a |
| Teorema 7 | a + (a’ · b) = a + b | a · (a’ + b) = a · b |
| Teorema 8 | a’ + (a · b) = a’ + b | a’ · (a + b) = a’ · b |
Verifica-se que os postulados e teoremas são duais, isto é, existem sempre os casos (a) e (b) que são simétricos. No caso (a), onde se escreve + , · , 0 , 1, no caso (b) correspondente, escreve-se · , + , 1 , 0 , respectivamente.
Os teoremas 6 e 7 são derivados dos postulados e teoremas anteriores, mas devem ser citados no quadro por facilitarem as simplificações de várias expressões lógicas.
Nas demonstrações
que se seguem, serão utilizados parênteses apenas sobre as
operações + , desde que assume-se que o operador ·
tem precedência sobre o + . Serão utilizadas as letras P para
postulado, e T para teorema.
Demonstrações
Demonstração do teorema 6 (a):
a + a· b =
= a· 1 + a·
b
(P2)
= a· (b + b’) + a· b (P5)
= a· b + a· b’ + a· b (P4)
= (a· b + a· b) + a· b’ (P3)
= a· b + a· b’ (T1)
= a· (b + b’) (P4)
= a· 1 (P5)
= a
(P2)
Demonstração do teorema 6 (b):
a · (a + b) =
= a· a + a· b (P4)
= a + a· b (T1)
= a
(P6.a)
Demonstração do teorema
7 (a):
a + a’· b =
= a· 1 + a’· b (P2)
= a· (b + b’) + a’· b (P5)
= a· b + a· b’ + a’· b (P4)
= a· b + a· b + a’· b + a’· b (T1)
= a· b + a· b’ + a· b + a’· b (P3)
= a· (b + b’) + (a + a’)· b (P4)
= a· 1 + 1· b (P5)
= a + b
(P2)
Demonstração do teorema
7 (b):
a · (a’ + b) =
= a· a’ + a· b (P4)
= 0 + a· b (P5)
= a· b
(P2)
As demonstrações dos teoremas 8 seguem as demonstrações dos teoremas 7.
Da mesma forma como foram feitas as demonstrações dos teoremas 6 e 7, outras identidades podem ser demonstradas.
Exemplo:
S2 = A· B + C
A· B + A’· C + B’· C =
= A· B + (A’ + B’)· C (P4)
= A· B + (A· B)’ · C (T5)
= A· B + C
(T7)
Bibliografia
[1] M. Morris Mano, Digital Design, Prentice Hall, 2ed., 1991
[2] I.V. Idoeta & F.G. Capuano, Elementos de Eletrônica
Digital, Érica, 6 ed. 1984
João Giacomin – DCC – UFLA – 23/03/2001