Básico do Básico: Álgebra Booleana

Colaborando com a série do meu amigo Caloni e reaproveitando um artigo meu para o wiki do C&C++ Brasil, vou falar um pouco sobre um fundamento básico da programação que muitos não conhecem de uma forma mais formal: a Álgebra Booleana.

Introdução

A álgebra booleana trata de expressões lógicas. George Boole inventou esta algebra para analisar expressões lógicas envolvendo conjuntos (que ele chamava de classes), porém atualmente a usamos principalmente com variáveis que podem assumir um dentre dois valores: verdadeiro ou falso, 0 ou 1, Sim ou Não, etc.

A álgebra booleana pode ser facilmente expressa através de circuitos elétricos e eletrônicos e é a base do projeto dos computadores digitais. Na programação, um conceito essencial é o desvio (ou tomada de decisão) que consiste em mudar a ordem de execução conforme uma expressão lógica.

Operações na Álgebra Booleana

Conforme mencionado, a álgebra booleana envolve variáveis que podem assumir somente dois valores. Nesta descrição vamos chamar estes valores de 0 e 1, porém lembre-se que eles podem significar qualquer par de condições que sejam exclusivas (isto é, uma variável não pode ser 0 e 1 simultaneamente) e complementares (isto é, se não for 0 é 1 e vice-versa).

Uma forma de representar as operações da álgebra booleana é através das tabelas verdade, que mostram os resultados para todas as combinações de entrada.

Uma primeira operação lógica é a negação (ou complemento), que vamos representar por !

A  !A
0  1
1  0

Uma segunda operação é o E (ou AND) que vamos representar por &&

A B A&&B
0 0  0
0 1  0
1 0  0
1 1  1

Ou seja, o E resulta em 1 somente se os dois operandos forem 1.

Outra operação é o OU (ou OR),representado abaixo por ||

A B A||B
0 0  0
0 1  1
1 0  1
1 1  1

O OU resulta em 1 se pelo menos um dos operandos for 1.

Por último vamos considerar o OU EXCLUSIVO (ou XOR), representado abaixo por ^

A B A^B
0 0  0
0 1  1
1 0  1
1 1  0

O XOR resulta 1 se um e somente um dos operados for 1. O XOR é equivalente a uma combinação de E e OU:

A^B = (A||B) && !(A&&B)

Ou seja, o XOR resulta em 1 se um ou o outro for 1 mas não ambos.

Nos circuitos eletrônicos, devido às características dos circuitos construídos com transistores, é comum encontrarmos outros tipos de operações:

A NAND B = !(A && B)
A NOR B = !(A || B)

Propriedades das Operações Booleanas

Da mesma forma que na aritmética e álgebra comuns, as operações booleanas apresentam uma série de propriedades úteis:

A && 1 = A  (elemento neutro)
A && 0 = 0
A && A = A
A && B = B && A (comutativa)
(A && B) && C = A && (B && C) (associativa)

A || 0 = A
A || 1 = 1
A || A = A
A || B = B || A
(A || B) || C = A || (B || C)

A ^ 0 = A
A ^ 1 = !A
A ^ A = 0
A ^ B = B ^ A
(A ^ B) ^ C = A ^ (B ^ C)

A && (B || C) = (A && B) || (A && C) (distributiva)
A || (B && C) = (A || B) && (A || C)

!(A && B) = (!A) || (!B)
!(A || B) = (!A) && (!B)

Notar que existe alguma semelhança entre, respectivamente, OU e E e SOMA e MULTIPLICAÇÃO, mas ela não é completa.

Álgebra Booleana na Programação

A maioria das linguagens possui o conceito de expressões lógicas, que retornam um valor verdadeiro ou falso. Estas expressões são expressões booleanas e utilizam os operadores que vimos acima. A forma mais comum de se obter um valor lógico é a partir de operadores de comparação, como igual, diferente, maior, maior ou igual, etc.

A principal utilidade das expressões lógicas na programação é no controle de fluxo, onde a próxima instrução a ser executada é determinada pelo resultado da expressão. As construções típicas para isto são os IFs e WHILEs.

As linguagens costumam também permitir armazenar o resultado das expressões lógicas em vaiáveis. A maioria das linguagens possui um tipo específico para isto, outras (como C) se utilizam de um tipo mais genérico.

O conhecimento das operações booleanas e suas propriedades facilitam a conversão de condições descritas textualmente em expressões lógicas, assim como as suas simplificações.

Encerrando com dois exemplos:

Testar se o conteúdo da variável num é maior que 0 e menor que 10

if ((num > 0) && (num < 10))

Testar se o conteúdo da variável num não é maior que 0 e menor que 10

if (!((num > 0) && (num < 10))) ou
if ((!(num > 0)) || (!(num < 10))) ou ainda
if ((num <= 0) || (num >= 10))

Reparar que neste segundo caso a negação "converteu" o E em um OU. Um erro comum é manter o E, escrevendo:

if ((num <= 0) && (num >= 10))

neste caso a expressão será sempre falsa (não existe um número que seja menor ou igual a zero E maior e igual que dez)!

12/05/09: acertada a parte final, onde alguns '<' e '>' bagunçaram tudo.