Álgebra de Boole e portas lógicas

Uma lâmpada só acende quando os dois interruptores estão ligados. Com entradas A e B a indicar cada interruptor, a regra é $Y=AB$; esta função booleana associa uma saída de 0 ou 1 a cada combinação das entradas, e a expressão, a tabela de verdade e o circuito descrevem a mesma regra.

Operações

Escrevemos AND por justaposição ou ponto, OR por $+$ e NOT por uma barra; aqui $+$ é OR, não a soma dos inteiros. XOR, $A\oplus B$, é 1 quando as entradas diferem, enquanto XNOR é 1 quando são iguais.

$A$	$B$	$AB$	$A+B$	$A\oplus B$	$\overline{A\oplus B}$
0	0	0	0	0	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	1	0	1

Sem parênteses, aplica primeiro NOT, depois AND, depois OR. Por exemplo, $A+B C$ é $A+(BC)$, enquanto $(A+B)C$ exige que $C=1$; uma letra negada continua a representar um bit, não um número negativo.

NAND é $\overline{AB}$ e NOR é $\overline{A+B}$. O círculo numa entrada ou saída de uma porta indica negação. Não confundas uma saída ativa a 0 com uma saída que nunca pode ser 1.

Simplificar sem mudar a função

As identidades permitem substituir expressões equivalentes:

Regra	AND	OR
Elemento neutro	$A\cdot1=A$	$A+0=A$
Elemento absorvente	$A\cdot0=0$	$A+1=1$
Idempotência	$AA=A$	$A+A=A$
Complemento	$A\overline A=0$	$A+\overline A=1$
Absorção	$A(A+B)=A$	$A+AB=A$

A distributividade vale nas duas direções: $A(B+C)=AB+AC$ e $A+BC=(A+B)(A+C)$. A dualidade troca AND por OR e 0 por 1 numa identidade válida.

Por exemplo, com

$$AB+A\overline BC=A(B+\overline BC)=A(B+C),$$

onde a passagem interior usa $B+\overline BC=(B+\overline B)(B+C)=B+C$. O circuito pode usar uma OR de $B,C$ seguida de uma AND com $A$, em vez de dois produtos separados.

De Morgan diz $\overline{AB}=\overline A+\overline B$ e $\overline{A+B}=\overline A\,\overline B$. Ao negar uma expressão, troca todas as operações do nível abrangido e nega os operandos: $\overline{A+BC}=\overline A(\overline B+\overline C)$.

Formas canónicas

Com $n$ entradas, a tabela tem $2^n$ linhas. Na ordem $A,B,C$, o índice da linha é o inteiro binário ABC; um mintermo contém todas as variáveis e vale 1 numa só linha. O mintermo 5, 101, é $A\overline BC$.

Suponhamos $F=1$ nos índices 1, 3, 5 e 6. A soma de mintermos é

$$F=\Sigma m(1,3,5,6)=\overline A\overline BC+\overline ABC+A\overline BC+AB\overline C.$$

As linhas onde $F=0$ são 0, 2, 4 e 7. Um maxtermo vale 0 numa só linha: coloca a variável direta se o bit dessa linha for 0, e negada se for 1, logo

$$F=\Pi M(0,2,4,7)=(A+B+C)(A+\overline B+C)(\overline A+B+C)(\overline A+\overline B+\overline C).$$

A soma de produtos simplificada pode omitir variáveis; a forma canónica não. Um termo $BC$ reúne duas linhas e não é um mintermo de uma função de três entradas.

NAND, NOR e seleção

Para implementar $H=AB+CD$ só com NAND, calcula $u=\overline{AB}$ e $v=\overline{CD}$; uma terceira NAND dá

$$H=\overline{uv}=\overline{\overline{AB}\,\overline{CD}}=AB+CD,$$

pois De Morgan transforma a negação do produto das duas saídas numa OR dos produtos originais. Por exemplo, com AB=1 e CD=0, os nós são u=0, v=1 e H=1; uma negação isolada é $\overline A=\operatorname{NAND}(A,A)$. NAND permite assim construir NOT, AND e OR, por isso é universal, tal como NOR.

A expansão de Shannon separa os casos de uma entrada, com

$$F=\overline A\,F(0,B,C)+A\,F(1,B,C),$$

onde as duas subfunções, chamadas cofatores, fixam A em 0 e em 1. Esta forma escolhe entre os dois cofatores conforme A; um multiplexador faz exatamente esta seleção e será estudado nos módulos combinatórios. Retomamos $F=\Sigma m(1,3,5,6)$ das formas canónicas:

Seleção	Linhas usadas	Cofator	Valor com A fixo
A=0	Índices 0 a 3	$\overline BC+BC=C$	$C$
A=1	Índices 4 a 7	$\overline BC+B\overline C=B\oplus C$	$B\oplus C$

Quando A=0, só o primeiro produto de Shannon contribui; quando A=1, só o segundo. Um multiplexador selecionado por A escolheria assim o cofator correspondente sem alterar F.

Confirma uma simplificação em todas as linhas, sobretudo nas que ficaram fora dos termos escolhidos, porque a igualdade num único exemplo não prova que os circuitos implementam a mesma função.