Á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
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.
