Postagem realizada em: 25/03/2007 às 16:17:40 - Última atualização em: 30/11/-0001 às 00:00:00
Autor: Paloma Altran
Atividade de pesquisa:
Álgebra de Boole: conceitos e conectores booleanos
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.
A mais importante álgebra Booleana tem apenas 2 elementos, 0 e 1, e é definida pelas regras
|
|
|
|
|
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 .
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.