Álgebra booleana
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 nos permitem uma analise formal de circuitos digitais, a álgebra booleana "capta a essência" das operações lógicas, com operadores E, OU e NÃO, bem como das operações da teoria de conjuntos soma, produto e complemento.
Índice |
[editar] História
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.
[editar] Definição e primeiras consequências
Enquanto as portas lógicas são úteis para a implementação de circuitos, as equações são melhores para a manipulação desses circuitos.
Portanto, a álgebra booleana nos fornece ferramentas algébricas que nos permitem manipular equações (simplificação, verificação de equivalências, invertê-las e demonstrar propriedades), ou seja, ela manipula circuitos digitais por meio de equações. A principal diferença entre a álgebra booleana e a álgebra convencional, e que na booleana suas variáveis e constantes podem assumir apenas dois valores 0 e 1. Elas representam o nível de tensão contido em uma conexão ou em entrada (as circunstancias) e saídas (as decisões) de circuitos. Não possuem frações , decimais, números negativos, raízes (quadradas, cúbicas, quádruplas, etc.), logaritmos, números imaginários, entre outros.
Os valores possuem termos sinônimos.
Os operadores da álgebra booleana podem ser representados de várias formas. É freqüente 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 freqüência + para OU e . para E (visto que sob alguns aspectos estas operações são análogas à adição e multiplicação em outras estruturas algébricas) e representam NÃO com uma linha traçada sobre a expressão que está a ser negada.
Ela também é o fundamento da matemática computacional, baseada em números binários.
Aqui iremos usar outra notação comum, com ? (ou ^ para browsers que não suportam esse caráter) para E, ? (ou v) para OU, e ´ (ou ~) para NÃO.
[editar] Teoremas Booleanos
- Leis computativas
A ordem em que as variáveis aparecem nas operações OR e AND não importa. Exemplo:
X+Y = Y+X X.Y = Y.X
- Leis associativas
Podemos agrupar as variáveis em expressões AND ou OR do modo que quisermos. Exemplo:
X + (Y+Z) = (X+Y)+Z X(YZ) = (XY)Z
- Leis Distributivas
Diz que a operação AND de única variável com o resultado de uma operação OR aplicada em duas ou mais variáveis é equivalente a uma operação OR entre os resultados das operações AND entre uma única variável e cada umas das duas ou mais variáveis.
Exemplos:
S= A(B+C) S= AB + BC
- Lei da identidade
Também está contida nas regras da álgebra de boole. Consiste em:
0+A = A+0 = A 1.A = A.1 = A
- Lei complemento
Independentemente do valor de A, A~ terá o valor oposto, de modo que se obtém 0 e 1, ou 1 e 0.
A + A~ =1 A.A~= 0
[editar] Tabela verdade
É uma representação numérica de uma função booleana. Portanto Para uma função de N variáveis, são necessárias 2^n linhas. Atribuindo valores 0 e 1 para todas as variáveis, seguindo a ordem de números binários.
[editar] Regras da Álgebra Booleana
Existem 12 regras básicas para a manipulação e simplificação de expressões booleanas.
Aplicações em portas lógicas: 1- A+0 = A 2- A+1=1 3- A.0=0 4- A.1=A 5- A+ A = A 6- A + A~ = 1 7- A.A = A 8- A.A~ = 0 9- A~~=A
Termos de regras mais simples e leis: 10- A + AB= A 11- A + A~B = A + B 12- (A+B)(A+C) = A +BC
[editar] Lendo Equações Booleanas
Embora tenhamos “emprestado” as operações de multiplicação e adição da álgebra convencional, não é utilizado o termo “vezes” para AND e “mais’ para OR. Exemplo: X= A’B’ + C.
Lê-se: “X é igual a A linha, B linha ou C.”
Assim como na álgebra convencional, há regras de precedência na álgebra booleana. Exemplo: F = (A+B’).C+D’ Resposta: O parêntese tem a máxima precedência. Dentro dos parênteses o NOT tem a precedência mais elevada. Assim, avaliamos a parte dos parênteses como (1+(1’)) = (1+(0)) = (1+0)= 1. A seguir, * tem precedência sobre +, resultado (1.0) + 1’ = (0)+1’. O NOT tem precedência sobre o OR, dando (0) + (1’) = (0)+(0) = 0+0 =0.
[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 e tem como função preservar dada estrutura: 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.
Exemplo: Seja um conjunto A composto por N elementos incluindo o 0, e domínio de uma função F(X) e um outro conjunto B formado pela imagem de F(X), ou seja o contradomínio da função F(X). Diremos que existe um homomorfismo de grupo, quando, e somente se F(X*Y) = F(X) * F(Y) ; ou seja quando se preservam as operações binárias.
[editar] Ver também
- Números binários
- Lógica binária
- Tabela verdade
- Função booleana
- Circuito digital
- Forma canónica
- Sistema formal
- Mapa de Karnaugh
- Diagrama de Venn
- Álgebra de Heyting