Álgebra booleana
Origem: Wikipédia, a enciclopédia livre.
Na matemática e na ciência da computação, as álgebras booleanas (também conhecida como Álgebra de Boole) 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. Ela também é o fundamento da matemática computacional, baseada em números binários.
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.
Índice |
[editar] Definição e primeiras consequências
 |
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor verifique e melhore a consistência e o rigor deste artigo. Considere utilizar {{revisão-sobre}} para associar este artigo com um WikiProjeto. |
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 as Leis de De Morgan
- ¬(a ∨ b) = (¬a) ∧ (¬b)
- ¬(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
|
|
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.
