Loogikaväravate uurija

Kiibitehas müüb teile ainult ühte ja ainust komponenti: kahe sisendiga NAND-elementi. Ehitage tööriistas valiku Poolliitmik all kujutatud poolliitmik — üks summabitt, üks ülekandebitt — mitte millestki muust. Mitu NAND-elementi selleks kulub ja kust te teate, et olete leidnud kõige odavama lülituse?

1. Alustage NOT-elemendist, mis on odavaim tehe, mida NAND-element teha suudab. Ühendage selle mõlemad sisendid sama juhtmega. Element küsib: „kas mõlemad neist on kõrged?“, ja kuna mõlemad sisendid on A, vastab see alati, kui A seda ei tee.

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

2. AND-element maksab ühe võrra rohkem. NAND ongi juba AND, mille vastus on peapeale pööratud, seega pöörake see tagasi: suunake väljund NOT-elementi, mis sammu 1 kohaselt on teine kokkuühendatud jalgadega NAND-element. OR-element nõuab kolme, inverteerides mõlemat sisendit enne NAND-elementi, mis on De Morgani seadus tagurpidi loetuna.

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

3. XOR-element on see, mis osutab vastupanu. Nõks seisneb vaheliikme ühekordses arvutamises ja selle rakendamises kordamööda kummagi sisendi vastu. Nimetage seda C-ks ning suunake see NAND-elementi A vastu ja uuesti B vastu.

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

4. Avaldage D. Selle sisu on „mitte korraga A ja (mitte A või mitte B)“. Selle osa „A ja mitte-A“ ei saa kunagi tõene olla, mistõttu see langeb välja ning järelejäänu on lühike. E on sama lause, kus tähed on omavahel vahetatud.

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

5. Viimane NAND-element ühendab need. De Morgani seadus muudab kahe eituse NAND-tehte tavaliseks OR-elemendiks ning OR-tehe avaldistest „A, kuid mitte B“ ja „B, kuid mitte A“ ongi see, mida XOR tähendab. Neli elementi summabiti jaoks.

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

6. Nüüd ülekanne. See on A AND B, mille hinnaks rehkendasite sammus 2 kaks elementi — kuid neist kahest esimene on C ning C asub juba juhtmel just ehitatud XOR-elemendi keskel. Lugege seda kolmandat korda ja ühendage see iseendaga.

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

7. Niisiis viis, mitte kuus. Poole sellest oled just kokku pannud: sammu 2 järgi vajab ülekanne eraldi 2 lüli, sammu 5 järgi summa 4 lüli ning sammus 6 märkasime, et neil on täpselt üks ühine lüli, seega 2 + 4 − 1 = 5. Väide, et vähem kui viiest ei piisa, vajab eraldi tõestust, mida sellel lehel ei ole. See tulemus saadakse kahe sisendiga kuni kuuest NAND-lülist koosnevate võrkude ammendava läbivaatamise teel, mis on arvutus, mitte matemaatiline argument.

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

8. Elementide arv ei ütle aja kohta midagi. Jälgige ülekannet: elemendist G1 otse elementi G5, kahe elemendi sügavuselt. Summa peab läbima elemendi G2 või G3 ja seejärel G4, seega on see kolme elemendi sügavune. Loendage teekonnad sisendist A summani — need pole isegi ühepikkused.

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