terça-feira, fevereiro 03, 2009

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.

4 comentários:

wmoecke disse...

Olha, eu achei um negócio bem interessante, enquanto lia uma apresentação da SCOPUS...

No menu lateral, expanda o capítulo "Os Anos 80", clique no capítulo "Nexus 1600". Tem um nome de um "gaiato", perdido lá no meio...

Naquela época, já tinha uns "cara bão" fazendo a história da informática no Brasil. Eu queria ter nascido uns 15 anos antes...

Daniel Quadros disse...

Werner,

Pois é, eles até me convidaram para a festa de 30 anos! Eu ainda tenho a revista com a reportagem e uma outra que saiu na Folha Informática.

Estão na minha lista falar um pouco sobre os altos e baixos da reserva de mercado e uma série de posts com minhas memórias dos anos 80 e 90.

A Scopus tinha uma equipe muito especial e fez coisas muito incríveis (algumas ingênuas e umas poucas estúpidas mas mesmo assim incríveis).

Continua existindo um monte de "cara bão" aqui no Brasil, embora poucos estejam fazendo história. Também já esquecemos muito da história que foi feita.

Será que alguem lembra do SOX - o Unix feito pela Cobra nos anos 80?. Ops - dei uma busca no Google e a Wikipedia lembra: http://en.wikipedia.org/wiki/SOX_Unix

O que falta é um pouco de amor próprio, não duvidar que podemos fazer o mesmo que se faz em outros países.

wmoecke disse...

Eu me sinto privilegiado em tê-lo conhecido. Sentiria muito orgulho em ter trabalhado em uma empresa como a Scopus foi (agora é do Bradesco), tendo feito parte de tantos projetos interessantes (contando erros e acertos)...

Eu lembro do SISNE, que foi o motivo pelo qual a Microsoft quis processar a Scopus por plágio (alegando que o SISNE era uma cópia descarada do DOS) - bah, eu não acredito, ainda mais vindo do "mestre do plágio", Bill Gate$, que fez sua fortuna pegando o trabalho dos outros e "mudando a cara" pra ninguém acusá-lo de plágio (um legítimo FDP, na minha opinião).

Isso e mais o que você disse sobre faltar amor próprio (na verdade eu acho que esse amor próprio precisava estar presente mais na política do que no meio técnico e acadêmico), é o que na minha opinião causou a banalização total da nossa área de TI hoje em dia. Temos muita gente fazendo pose, posando de "mestres Yoda" e não fazendo nada de bom, enquanto os nossos "cara bão" ficam fazendo o trabalho deles, sem esperarem o menor reconhecimento (que de fato, quase nunca vem).

Eu escrevi aqui nesse outro blog dois comentários acerca dessa minha frustração, inclusive citando o fato que você mencionou aqui, sobre a falta de memória e reconhecimento do brasileiro (tem um museu do computador, que está quase fechando por falta de interesse). É uma pena mesmo...

Eu acho que o Brasil teve muita capacidade de deslanchar por conta própria nessa área, e acredito que teria dado muito certo, se não tivesse "aberto as pernas" na época da reserva de mercado.

Gostaria muito de ler o que vc tiver pra dizer sobre essa época. Ficarei atento aos seus posts!
Um abraço!

wmoecke disse...

Ainda desabafando: sobre a banalização que sofremos hoje aqui no Brasil, é uma vergonha o que se faz hoje - No Brasil (e no mundo inteiro) infelizmente, veneram-se "figuras" como o Bill Gate$ e a sua empresa (que deveria ser uma empresa de marketing, e não informática), enquanto que gente que realmente fez e continua fazendo (pra mim, nenhum exemplo é melhor do que o do Edson Fregni, que saiu do Patinho Feio até chegar à SCOPUS - esse é o verdadeiro empreendedor) permanece no escuro. Ninguém merece...