論理ゲート・エクスプローラー

半導体工場（ファブ）が販売している部品が「2入力NANDゲート」ただ1種類のみであるとします。ツールが半加算器の項目で描く半加算器（1つの和ビットと1つの桁上がりビット）を、これ以外の部品を使わずに構築してください。NANDゲートは何個必要でしょうか？また、それが最もコストの低い（最小の）構成だとどうすれば確認できるでしょうか？

1. まずNOTから始めましょう。これはNANDで作れる最も安価な論理機能です。両方の入力を同じ配線に接続します。ゲートは「両方ともHighか？」と問いかけますが、どちらの入力もAであるため、AがHighでないときに常にTrue（High）を出力します。

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

2. ANDを作るにはもう1個必要です。NANDはすでにANDの出力を反転させたものなので、元に戻せばよいのです。出力をNOT（ステップ1で見たように入力を短絡させた2つ目のNAND）に入力します。ORを作るには3個必要で、NANDに入る前の各入力を反転させます。これはド・モルガンの法則を逆読みしたものです。

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

3. 一筋縄ではいかないのがXORです。コツは、中間項を1回計算し、それを各入力に対して順番に組み合わせることです。その中間項をCと呼び、Aとの組み合わせ、およびBとの組み合わせをそれぞれNANDに入力します。

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

4. Dを展開します。これは「A かつ (not A または not B) の全体否定」を意味します。このうち「A かつ not A」の部分は決して起こり得ないため消滅し、残る式は簡潔な形になります。Eは文字を入れ替えた同じ式になります。

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

5. 最後のNANDでこれらを結合します。ド・モルガンの法則により、2つの否定のNANDは通常のORとなり、「AであってBでない」と「BであってAでない」のORこそがXORの定義です。和のビットには4個のゲートが必要です。

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

6. 次に桁上がりです。これは「A AND B」であり、ステップ2の計算ではゲート2個分でした。しかし、その2個のうち1個目はCそのものであり、Cは直前に構築したXORの中央の配線上にすでに存在しています。これを3回目に読み出し、それ自体に接続します。

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

7. 必要なのは六つではなく、五つです。ここまでで示したのは、その主張の半分です。手順2から、桁上がりだけなら2ゲート。手順5から、和には4ゲートが必要です。そして手順6で、両者がちょうど一つのゲートを共有すると分かるので、2 + 4 − 1 = 5 となります。五つ未満では実現できないという下限は、これとは別の主張です。このページの議論だけでは証明されていません。二つの入力に対する六ゲート以下のNAND回路をすべて網羅的に探索した計算結果に基づくもので、数学的な論証ではありません。

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

8. ゲート数は処理時間については何も語りません。桁上がりを追いかけると、G1を出て直接G5に入るため、ゲートの深さは2段です。和はG2またはG3を通り、さらにG4を通過する必要があるため、3段の深さになります。Aから和への経路を数えてみると、それら自体の長ささえ等しくありません。

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