Lógica e álgebra 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 você ainda não leu Como funcionam os bits e os bytes, será útil fazê-lo antes de continuar.
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