Lógica combinatória

Em nossa jornada para entender o motivo pelo qual os transistores são essenciais para a computação, precisamos agora entender o que é possível fazer com os circuitos lógicos que conseguimos construir a partir dos transistores. Para isso, precisamos entender formalmente a lógica booleana.

O livro que começou a teoria que tornou George Boole em um tipo de variável

No século XIX, o matemático britânico George Boole publicou sua obra seminal “An Investigation of the Laws of Thought” (1854), estabelecendo as bases para um sistema algébrico revolucionário. Boole percebeu que os processos de raciocínio humano poderiam ser expressos através de operações matemáticas simbólicas, criando uma ponte entre a filosofia e a matemática. Seu trabalho permaneceu como curiosidade teórica por quase um século, até que Claude Shannon (1938) percebeu que a álgebra booleana era a linguagem perfeita para descrever e projetar circuitos de relês e chaves elétricas, lançando as bases para a computação digital moderna.

O insight revolucionário foi perceber que esses circuitos de relês e chaves podem existir em apenas dois estados físicos: aberto/fechado, ligado/desligado, alto/baixo. É dessa simplicidade binária que nasce toda a complexidade da computação digital.

Na álgebra booleana, representamos esses dois estados como

• 1 | 0
• Verdadeiro | Falso
• Alto | Baixo

São três formas de dizer a mesma coisa, dependendo do contexto (abstração matemática, lógica de programação, ou eletrônica física).

A partir desta representação, surgem algumas operações fundamentais que definem o que conhecemos como álgebra booleana. São elas:

1. Operação NOT (¬ ou ’) — inverte o valor de entrada. Se $A=1$, então $\overline{A}=0$. Essa operação é a porta de entrada para o conceito de complemento.

$A$	$\overline{A}$
0	1
1	0

2. Operação AND (· ou ×) — Conjunção lógica: produz saída 1 apenas quando todas as entradas forem 1. Modela decisões do tipo “todos os critérios devem ser atendidos” (exemplo: todas as condições de segurança devem ser satisfeitas para liberar acesso).

$A$	$B$	$A\cdot B$
0	0	0
0	1	0
1	0	0
1	1	1

3. Operação OR (+) — Disjunção lógica: produz saída 1 quando pelo menos uma das entradas for 1. Captura situações onde “qualquer condição satisfaz o requisito” (exemplo: qualquer sensor de falha dispara o alarme de emergência).

$A$	$B$	$A+B$
0	0	0
0	1	1
1	0	1
1	1	1

4. Operação XOR (⊕) — OU Exclusivo: produz saída 1 exclusivamente quando exatamente uma das entradas for 1. Fundamental para operações aritméticas como soma binária e detecção de diferença entre bits.

$A$	$B$	$A\oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

Quando conversamos sobre transistores, falamos que essas portas lógicas podem ser feitas utilizando transistores. Por exemplo, se queremos criar uma porta XOR, devemos criar o circuito abaixo:

Porta XOR feita com transistores.

Desafio

Consegue explicar por quê essa configuração gera o mesmo comportamento lógico da porta XOR?

Propriedades da álgebra booleana

Assim como na álgebra decimal, que aprendemos na escola, a álgebra booleana conta com uma série de propriedades que servem como regras para as operações que podemos fazer.

Propriedade	AND	OR
Comutativa	$AB=BA$	$A+B=B+A$
Associativa	$(AB)C=A(BC)$	$(A+B)+C=A+(B+C)$
Distributiva	$A(B+C)=AB+AC$	$A+BC=(A+B)(A+C)$
Identidade	$A\cdot 1=A$	$A+0=A$
Complemento	$A\overline{A}=0$	$A+\overline{A}=1$
Idempotência	$AA=A$	$A+A=A$
Nulidade	$A\cdot 0=0$	$A+1=1$
Dupla Negação	$\overline{\overline{A}}=A$	—

Também de forma análoga à álgebra decimal, essas propriedades podem ser muito úteis para simplificar expressões complexas.

Vou deixar separadas aqui duas propriedades que tem um nível de importância mais elevado, que são duas propriedades derivadas do Teorema de DeMorgan.

Leis de DeMorgan
$\overline{A\cdot B}=\overline{A}+\overline{B}$
$\overline{A+B}=\overline{A}\cdot \overline{B}$

Essas duas propriedades concedem às portas XOR e NAND um super poder: é possível reproduzir o comportamento de qualquer circuito lógico apenas com uma combinação de qualquer uma dessas duas portas.

Desafio

E aí, consegue provar isso?

Dica: se você provar que consegue representar o comportamento de todas as outras portas lógicas básicas usando só o XOR ou só o NAND, isso significa que consegue fazer qualquer circuito lógico combinatório.

Na eletrônica digital, os circuitos que utilizam apenas combinações de operadores lógicos são denominados de circuitos combinatórios. Eles formam a base para as operações lógicas e aritméticas de uma CPU. Uma das ferramentas mais úteis para avaliar o comportamento de um circuito combinatório é a tabela verdade.

A tabela verdade

Você já viu uma tabela verdade. Na verdade, já viu quatro delas — aquelas que apresentei logo acima, mostrando todas as combinações possíveis de entradas para as portas NOT, AND, OR e XOR, junto com suas respectivas saídas.

De modo formal, podemos definir:

Tabela Verdade: uma representação tabular que mapeia todas as combinações possíveis de valores de entrada de uma função booleana (ou circuito lógico) para seus correspondentes valores de saída. Para $n$ variáveis de entrada, a tabela possui $2^n$ linhas, cobrindo sistematicamente todas as combinações de 0s e 1s.

Simples, né?

Exemplo prático

Vamos projetar um sistema de irrigação automática para um jardim com duas zonas. O sistema deve ligar a bomba d’água apenas quando as condições forem favoráveis:

• A: Sensor de umidade do solo (1 = solo seco, 0 = solo úmido)
• B: Sensor de chuva (1 = não está chovendo, 0 = está chovendo)
• C: Seletor da Zona 1 (1 = zona ativa, 0 = zona inativa)
• D: Seletor da Zona 2 (1 = zona ativa, 0 = zona inativa)

A bomba (S) deve ligar quando:

1. O solo está seco E não está chovendo E a Zona 1 está selecionada
2. O solo está seco E não está chovendo E a Zona 2 está selecionada
3. O solo está seco E não está chovendo E ambas as zonas estão selecionadas

Tabela Verdade

Com 4 variáveis, temos $2^4=16$ combinações.

Para criar uma tabela verdade, listamos todas as combinações possíveis das variáveis de entrada. Com 4 variáveis (A, B, C, D), temos $2^4=16$ combinações. Para cada linha, determinamos a saída S seguindo a especificação: a bomba liga apenas quando A=1 (solo seco), B=1 (sem chuva) e C=1 ou D=1 (pelo menos uma zona ativa).

A	B	C	D	S	Situação
0	0	0	0	0	Solo úmido, está chovendo, nenhuma zona ativa
0	0	0	1	0	Solo úmido, está chovendo, só Zona 2 ativa
0	0	1	0	0	Solo úmido, está chovendo, só Zona 1 ativa
0	0	1	1	0	Solo úmido, está chovendo, ambas zonas ativas
0	1	0	0	0	Solo úmido, sem chuva, nenhuma zona ativa
0	1	0	1	0	Solo úmido, sem chuva, só Zona 2 ativa
0	1	1	0	0	Solo úmido, sem chuva, só Zona 1 ativa
0	1	1	1	0	Solo úmido, sem chuva, ambas zonas ativas
1	0	0	0	0	Solo seco, está chovendo, nenhuma zona ativa
1	0	0	1	0	Solo seco, está chovendo, só Zona 2 ativa
1	0	1	0	0	Solo seco, está chovendo, só Zona 1 ativa
1	0	1	1	0	Solo seco, está chovendo, ambas zonas ativas
1	1	0	0	0	Solo seco, sem chuva, nenhuma zona selecionada
1	1	0	1	1	Solo seco, sem chuva, só Zona 2 ativa → BOMBA LIGA
1	1	1	0	1	Solo seco, sem chuva, só Zona 1 ativa → BOMBA LIGA
1	1	1	1	1	Solo seco, sem chuva, ambas zonas ativas → BOMBA LIGA

Extração da Expressão Lógica

Agora vamos converter a tabela verdade em uma expressão booleana usando o método SOP (Sum of Products ou Soma de Produtos).

Como funciona o método SOP:

1. Identifique todas as linhas da tabela onde a saída S = 1
2. Para cada linha, crie um termo produto (AND) com todas as variáveis:
   • Se a variável vale 1, use ela diretamente (ex: A)
   • Se a variável vale 0, use ela negada (ex: $\overline{A}$)
3. Some (OR) todos esses termos produto para obter a expressão final

No nosso caso, temos 3 linhas onde S = 1:

Linha	A	B	C	D	Termo Produto
14	1	1	0	1	$AB\overline{C}D$
15	1	1	1	0	$ABC\overline{D}$
16	1	1	1	1	$ABCD$

Somando todos os termos:

$S=ABC\overline{D}+AB\overline{C}D+ABCD$

Simplificação Algébrica

Vamos simplificar passo a passo:

Passo 1: Fatorar $AB$ comum a todos os termos

$S=AB(C\overline{D}+\overline{C}D+CD)$

Passo 2: Agrupar os termos que têm $C$ em comum

$S=AB[C(\overline{D}+D)+\overline{C}D]$

Passo 3: Aplicar a propriedade do complemento ($\overline{D}+D=1$)

$S=AB[C(1)+\overline{C}D]$

$S=AB(C+\overline{C}D)$

Passo 4: Aplicar a propriedade distributiva e simplificar

Usando a propriedade: $C+\overline{C}D=C+D$ (absorção)

$S=AB(C+D)$

Ou na forma expandida:

$S=ABC+ABD$

Interpretação do Resultado

A expressão simplificada $S=AB(C+D)$ tem uma interpretação física muito clara:

• $AB$: Condições básicas — solo seco E não está chovendo
• $(C+D)$: Pelo menos uma zona está selecionada (Zona 1 OU Zona 2)
• A bomba liga quando: (condições favoráveis) E (alguma zona ativa)

Verificação

A expressão lógica acima faz sentido, mas será que está correta?

A melhor forma de garantir que essa expressão lógica é consistente com o problema que descrevemos é recriando a tabela verdade a partir da expressão lógica.

Faça isso agora.