Álgebra booleana

Origem: Wikipédia, a enciclopédia livre.

Na matemática e na ciência da computação, as álgebras booleanas são estruturas algébricas que "capturam a essência" das operações lógicas E, OU e NÃO, bem como das operações da teoria de conjuntos soma, produto e complemento.

Receberam o nome de George Boole, matemático inglês, que foi o primeiro a defini-las como parte de um sistema de lógica em meados do século XIX. Mais especificamente, a álgebra booleana foi uma tentativa de utilizar técnicas algébricas para lidar com expressões no cálculo proposicional. Hoje, as álgebras booleanas têm muitas aplicações na electrónica. Foram pela primeira vez aplicadas a interruptores por Claude Shannon, no século XX.

Os operadores da álgebra booleana podem ser representados de várias formas. É frequente serem simplesmente escritos como E, OU ou NÃO (são mais comuns os seus equivalentes em inglês: AND, OR e NOT). Na descrição de circuitos também podem ser utilizados NAND (NOT AND), NOR (NOT OR) e XOR (OR exclusivo). Os matemáticos usam com frequência + para OU e . para E (visto que sob alguns aspectos estas operações são análogas à adição e multiplicação noutras estruturas algébricas) e representam NÃO com uma linha traçada sobre a expressão que está a ser negada.

Aqui iremos usar outra notação comum, com ∧ (ou ^ para browsers que não suportam esse caracter) para E, ∨ (ou v) para OU, e ¬ (ou ~) para NÃO.

[editar] Definição e primeiras consequências

Uma álgebra booleana é um reticulado (lattice) (A, ∧ , ∨) com as quatro propriedades adicionais que seguem:

limitado inferiormente: Existe um elemento 0, tal que a ∨ 0 = a para qualquer a em A.
limitado superiormente: Existe um elemento 1, tal que a ∧ 1 = a para qualquer a em A.
lei distributiva: Para quaisquer a, b, c em A, (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c).
existência de complementos: Para qualquer a em A existe um elemento ¬a em A tal que a ∨ ¬a = 1 e a ∧ ¬a = 0.

Destes axiomas, podemos mostrar directamente que o elemento menor 0 e o elemento maior 1 são únicos, que todo o elemento tem um só complemento, que

a ∧ 0 = 0 e a ∨ 1 = 1,

¬1 = 0 e ¬0 = 1,

e que Leis de deMorgan

¬(a ∨ b) = (¬a) ∧ (¬b) e ¬(a ∧ b) = (¬a) ∨ (¬b)

são válidas. A versão dual da lei distributiva,

(a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c)

também se verifica. Em geral, qualquer lei sobre álgebras Booleanas podem ser transformadas em outra, igualmente válida, lei "dual" pela troca de 0 por 1 e ∧ por ∨, e vice-versa.

Como qualquer reticulado, uma álgebra Booleana pode ser vista como um conjunto parcialmente ordenado (POSET) definindo-se

a ≤ b sse a = a ∧ b

(o que é equivalente a b = a ∨ b).

[editar] Exemplos

A mais importante álgebra Booleana tem apenas 2 elementos, 0 e 1, e é definida pelas regras

∧	0	1
0	0	0
1	0	1

∨	0	1
0	0	1
1	1	1

Isso tem aplicação em lógica, onde 0 é interpretado como "falso", 1 é "verdadeiro", ∧ é "e", ∨ é "ou", e ¬ "não". Expressões envolvendo variáveis e operações Booleanas representam formas de indicações, e as tais duas expressões podem ser mostradas para ser usadas igualmente utilizando o axioma acima se e somente se as formas indicadas correspondentes forem equivalentes lógicos. A álgebra Booleana de dois elementos é também utilizada no projeto de circuitos em engenharia elétrica; aqui 0 e 1 representam os dois diferentes estados de um bit em um circuito digital, tipicamente alta e baixa voltagem. Os circuitos são descritos por expressões contendo variáveis, e as tais duas expressões são iguais para todos os valores das variáveis se e somente se o circuito correspondente tiver o mesmo comportamento de entrada-saída. Além disso, cada possibilidade do comportamento de entrada e saída pode ser modelada pela expressão Booleana apropriada.

A álgebra booleana binária é também importante na teoria geral de álgebras booleanas, porque uma equação envolvendo diversas variáveis é verdadeira em todas as álgebras booleanas se e só se é verdadeira na álgebra booleana de dois elementos . Isto pode, por exemplo, ser usado para mostrar que os seguintes teoremas (Teoremas de consenso) são válidos em todas as álgebras booleanas em geral:

(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) = (a ∨ b) ∧ (¬a ∨ c)

(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) = (a ∧ b) ∨ (¬a ∧ c)

O conjunto das partes de um conjunto S forma uma álgebra booleana com as operaçôes ∨ = união e ∧ = intersecçâo. O menor elemento 0 é o conjunto vazio e o maior elemento 1 é o próprio conjunto S.

O conjunto dos subconjuntos finitos ou co-finitos de um conjunto S, com as operações de união e interseção é uma álgebra Booleana .

[editar] Homomorfismos e isomorfismos

Um homomorfismo entre as álgebras Booleanas A e B é uma função f : A → B tal que para todos a, b em A:

f(a ∨ b) = f(a) ∨ f(b)

f(a ∧ b) = f(a) ∧ f(b)

f(0) = 0

f(1) = 1

Segue-se que f(¬a) = ¬f(a) para todo a em A.

A classe de todas as álgebras Booleanas, com esta noção de morfismo, forma uma categoria. Um isomorfismo de A para B é um homomorfismo bijetivo de A para B. O inverso de um isomorfismo é ainda um isomorfismo , e chamamos as duas álgebras Booleanas A e B de isomorfas. Do ponto de vista da teoria das álgebras Booleanas, elas não podem ser distinguidas entre si; somente diferem na notação de seus elementos.