Como funciona a algebra booleana

Introdução

Você já se perguntou como um computador é capaz de fazer coisas como controle do orçamento doméstico, jogar xadrez, ou verificar a ortografia em um documento? Há bem pouco tempo, essas coisas só podiam ser feitas por humanos. Agora, os computadores as fazem com aparente facilidade. Como um "chip" feito de silício e fios pode fazer algo que, aparentemente, só poderia ser realizado pelo cérebro humano?

Para entender a resposta para essa pergunta, primeiro você precisa conhecer algo chamado lógica booleana. A lógica booleana, originalmente desenvolvida por George Boole em meados de 1800, permite que uma série de coisas pouco prováveis sejam mapeadas em bits e bytes. O que há de genial sobre a lógica booleana é que, uma vez entendido seu processo, ela (ou pelo menos a parte necessária para compreender as operações de um computador) é absurdamente simples. Neste artigo, vamos começar discutindo "portas" lógicas simples, e depois veremos como transformá-las em algo útil.

Portas simples

Há três, cinco ou sete portas simples que precisamos conhecer, dependendo de como se queira contá-las (logo veremos o motivo). Com elas, podem-se construir combinações que implementarão qualquer componente digital imaginável. Essas portas parecerão um pouco limitadas e incrivelmente simples, mas veremos algumas combinações interessantes nas seções seguintes que as tornarão bem mais inspiradoras. Se

A porta mais simples chama-se "inversor", ou porta NOT. Ela usa um bit como entrada e produz seu oposto como saída. Segue abaixo, a tabela lógica para a porta NOT e seu símbolo comummente usado em diagramas de circuitos:

Porta NOT
A Q 0 1 1 0

Nesta figura, perceba que a porta NOT tem uma entrada chamada A e uma saída chamada Q ("Q" é usada para a saída porque se usarmos "O" (do inglês "output") ela pode se confundir com zero). A tabela mostra o comportamento da porta. Ao atribuirmos o valor 0 a A, Q produz um 1. Ao atribuirmos o valor 1 a A, Q produz um 0. Simples.

A porta AND executa uma operação lógica "e" sobre duas entradas, A e B:

Porta AND
A B Q 0 0 0 0 1 0 1 0 0 1 1 1

A idéia por trás de uma porta AND é, "Se A = 1 E B = 1, então Q = 1." Podemos notar este comportamento na tabela lógica desta porta. A tabela deve ser lida linha por linha, assim:

Porta AND

A B Q 0 0 0 Se A = 0 E B = 0, Q = 0. 0 1 0 Se A = 0 E B = 1, Q = 0. 1 0 0 Se A = 1 E B = 0, Q = 0. 1 1 1 Se A = 1 E B = 1, Q = 1.

A próxima é a porta OR. Sua idéia básica é "Se A = 1 OU B = 1 (ou se ambas forem iguais a 1), então Q = 1."

Porta OR
A B Q 0 0 0 0 1 1 1 0 1 1 1 1

Essas são as três portas básicas (uma maneira de contá-las). É bastante comum que se reconheçam outras duas também: a porta NAND e a porta NOR. Essas são combinações simples da porta AND ou da porta OR com a porta NOT. Se as incluirmos, a contagem subirá para cinco. Este é o funcionamento básico das portas NAND e NOR (elas são apenas inversões das portas AND e OR):

Porta NOR
A B Q 0 0 1 0 1 0 1 0 0 1 1 0

Porta NAND
A B Q 0 0 1 0 1 1 1 0 1 1 1 0

As duas últimas portas que podem aparecer na lista são as portas XOR e XNOR, também conhecidas como portas "OR exclusivo" e "NOR exclusivo", respectivamente. Estas são suas tabelas:

Porta XOR
A B Q 0 0 0 0 1 1 1 0 1 1 1 0

Porta XNOR
A B Q 0 0 1 0 1 0 1 0 0 1 1 1

A idéia por trás da porta XOR é: "se A= 1 OU B = 1, mas NÃO ambas, então Q = 1." O motivo pelo qual XOR pode não constar de uma lista de portas é porque ela pode ser facilmente implementada com o uso das três portas listadas originalmente. Esta é uma implementação:

Se tentarmos todos os quatro padrões diferentes para A e B e os rastrearmos através do circuito, veremos que Q se comporta como uma porta XOR. Como existe um símbolo bastante compreensível para as portas XOR, costuma ser mais fácil pensar em XOR como uma "porta padrão" e usá-la da mesma maneira que as portas AND e OR nos diagramas de circuitos.