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

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.

Definição e primeiras consequências

Termos Sinônimos.

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.

Símbolos dos operadores

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.

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

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.

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

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.

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.

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