Álgebra booleana: a matemática do sim e do não

Álgebra booleana: a matemática do sim e do não

Em 1854, George Boole publicou Uma investigação sobre as leis do pensamento. Nele, propôs tratar a lógica com símbolos, como a álgebra trata números. As variáveis só assumem dois valores: verdadeiro (1) ou falso (0). Essa ideia, que parecia abstrata, virou a base de todos os computadores.

Três operações básicas

Boole usou três operações. E (AND) é 1 só quando as duas entradas são 1. Ou (OR) é 1 quando pelo menos uma entrada é 1. Não (NOT) inverte o valor. Com essas três, é possível expressar qualquer função lógica.

| Operação | Símbolos na aula | Vale 1 quando | | --- | --- | --- | | E (AND) | A*B, A&B, AB | A e B valem 1 | | OU (OR) | A+B, A|B | A ou B (ou ambos) valem 1 | | NÃO (NOT) | !A, A' | A vale 0 | | XOU (XOR) | A^B | A e B são diferentes |

Por exemplo, "chover E NÃO estiver ensolarado" é verdadeiro apenas quando chove e não há sol. Escrever isso como expressão permite simplificar condições longas, algo útil em programação.

Leis que a álgebra obedece

Como na álgebra comum, há regras que podem ser verificadas uma a uma na tabela-verdade da aula:

• Comutativa: A + B = B + A e A·B = B·A.
• Associativa: (A + B) + C = A + (B + C).
• Distributiva: A·(B + C) = A·B + A·C. Diferente da álgebra comum, também vale A + (B·C) = (A + B)·(A + C).
• Identidade: A + 0 = A e A·1 = A.
• Complemento: A + NÃO A = 1 e A·NÃO A = 0. Por isso a primeira é tautologia e a segunda, contradição.
• Absorção: A + A·B = A. Um bom teste no preset "Absorção".
• De Morgan: NÃO (A·B) = (NÃO A) + (NÃO B), e NÃO (A + B) = (NÃO A)·(NÃO B). Use o preset "De Morgan" e veja que as duas colunas são iguais.

Forma soma de produtos

Toda função de n variáveis pode ser escrita como uma soma de produtos: para cada linha da tabela-verdade com saída 1, forma-se um produto em que a variável aparece sem barra quando vale 1 e com barra quando vale 0. Somando esses produtos, obtém-se a função. Cada linha desse tipo é um mintermo, numerado pelo valor binário das entradas (A é o bit mais significativo).

Por exemplo, a função que vale 1 quando A e B são diferentes (o XOU) tem mintermos 1 (A′B) e 2 (AB′). Ela é A′B + AB′. A forma não é a mais curta possível, mas sempre existe e sempre está certa.

Dos circuitos aos processadores

Em 1937, Claude Shannon mostrou, na sua tese de mestrado, que circuitos de relés elétricos podiam implementar a álgebra de Boole. Cada chave aberta ou fechada representa 0 ou 1. A ligação de duas chaves em série faz o papel do E; em paralelo, do OU. Hoje, um processador faz isso com bilhões de transistores, e toda operação que você faz no celular passa por essas portas lógicas.

No circuito da aula, cada porta é uma caixa (E, OU, XOU, NÃO) e os fios transportam 0 ou 1. Fios em destaque valem 1. Clique nas entradas A, B, C ou D para alternar seus valores e acompanhe a saída S.

Como usar a aula

• Digite a expressão no campo S. Espaços são livres, e "AB" equivale a A*B.
• Os casos notáveis preenchem a expressão de um clássico.
• No campo de comparação, escreva uma segunda expressão para testar equivalência. Se forem diferentes, o painel mostra uma combinação que as separa.
• A linha destacada na tabela é a combinação atual das chaves.

Aplicações

• Programação: condições como if (a && !b) são expressões booleanas, e simplificá-las reduz erros.
• Projeto de hardware: somadores, memórias e controladores são feitos de portas lógicas.
• Buscas: motores de busca combinam termos com E e OU.
• Verificação formal: provar que dois circuitos são iguais é, no fundo, verificar uma tabela-verdade ou uma equivalência booleana.

Curiosidade

Boole não pensava em computadores. Seu objetivo era entender a lógica de Aristóteles com álgebra. Quase um século depois, a tese de Shannon mostrou que a mesma álgebra descrevia chaves elétricas, e a ponte entre matemática e máquina ficou pronta.

Perguntas de revisão

1. Qual é o resultado de 1 E 0 na álgebra booleana?

Resposta: 0. O E só vale 1 quando as duas entradas valem 1.

1. O que Claude Shannon mostrou em 1937?

Resposta: que circuitos elétricos podem implementar a álgebra de Boole.