Explorador de Portas Lógicas

Uma fábrica de semicondutores vende-lhe um componente e um componente apenas: a porta NAND de duas entradas. Construa o meio somador que a ferramenta desenha em Meio Somador — um bit de soma, um bit de transporte — sem usar mais nada. De quantas portas NAND precisa, e como saberia que tinha encontrado o circuito mais barato?

1. Comece com o NOT, que é a função mais barata em que uma NAND se pode converter. Ligue ambas as suas entradas ao mesmo fio. A porta pergunta "ambas as entradas estão no nível alto?", e como ambas são A, responde sempre que A não estiver.

   $$A\uparrow A=\neg (A\wedge A)=\neg A$$

2. O AND custa mais uma. Uma NAND já é um AND com a resposta invertida, por isso volte a invertê-la: encaminhe a saída para um NOT, que pelo passo 1 é uma segunda NAND com as entradas ligadas entre si. O OR exige três, invertendo cada entrada antes de uma NAND, o que é a lei de De Morgan lida ao contrário.

   $$(A\uparrow B)\uparrow (A\uparrow B)=\neg \neg (A\wedge B)=A\wedge B$$

3. O XOR é o que oferece resistência. O truque consiste em calcular o termo intermédio uma vez e combiná-lo com cada entrada, por sua vez. Chame-lhe C, e encaminhe-o para uma NAND juntamente com A, e novamente com B.

   $$C=A\uparrow B,D=A\uparrow C,E=B\uparrow C$$

4. Desenvolva D. Lê-se "não ambos A e (não A ou não B)". A metade A-e-não-A dessa expressão nunca pode acontecer, pelo que é eliminada, e o que resta é curto. E é a mesma expressão com as letras trocadas.

   $$D=\neg (A\wedge (\neg A\vee \neg B))=\neg (A\wedge \neg B),E=\neg (B\wedge \neg A)$$

5. A última NAND junta-os. De Morgan transforma uma NAND de duas negações num OR simples, e um OR de "A mas não B" com "B mas não A" é o significado de XOR. Quatro portas para o bit de soma.

   $$D\uparrow E=(A\wedge \neg B)\vee (B\wedge \neg A)=A\oplus B$$

6. Agora o transporte. É A AND B, cujo custo avaliou em duas portas no passo 2 — mas a primeira dessas duas é C, e C já se encontra num fio a meio do XOR que acabou de construir. Leia-o uma terceira vez e ligue-o a si próprio.

   $$C\uparrow C=\neg (A\uparrow B)=A\wedge B$$

7. Portanto, são cinco em vez de seis. Metade dessa conclusão já foi obtida: pelo passo 2, o transporte requer, por si só, 2 portas; pelo passo 5, a soma requer 4; e o passo 6 mostra que ambos partilham exatamente uma porta. Assim, 2 + 4 − 1 = 5. Provar que não existe uma solução com menos de cinco portas é outra questão, e nada nesta página o demonstra. Esse resultado provém de uma busca exaustiva de todas as redes NAND com, no máximo, seis portas e duas entradas, ou seja, de um cálculo, não de um argumento matemático.

   $$\neg :1,\wedge :2,\vee :3,\oplus :4,\{S,C\}:5$$

8. A contagem de portas nada diz sobre o tempo. Siga o transporte: sai de G1, vai diretamente para G5, com duas portas de profundidade. A soma tem de passar por G2 ou G3 e depois por G4, pelo que tem três portas de profundidade. Conte os caminhos de A para a soma e constatará que nem sequer têm o mesmo comprimento entre si.

   $$A\to G_2\to G_4=2\text{ gates},A\to G_1\to G_2\to G_4=3\text{ gates}$$