NANDゲートから全加算器を作る｜Pythonで論理回路を組み立てる

CPUの中では、トランジスタが作る論理ゲートが計算をしています。驚くのは、たった1種類の「NANDゲート」だけで、あらゆる論理回路——最終的には足し算まで——が作れること。この記事ではPythonでNANDから出発し、全加算器までボトムアップで組み立てます。半導体が「計算する」しくみが、手を動かすと腹落ちします。

NANDは万能

NAND（Not AND）は「両方1のときだけ0、それ以外は1」を返すゲートです。これ1種類あれば、NOTもANDもORも作れる——この性質を機能的完全性と呼びます。

準備

Pythonだけ。ライブラリは不要です。

① NANDから基本ゲートを作る

NANDを出発点に、NOT・AND・OR・XORを組み上げます。

def NAND(a, b):
    return 0 if (a and b) else 1

def NOT(a):
    return NAND(a, a)

def AND(a, b):
    return NOT(NAND(a, b))

def OR(a, b):
    return NAND(NOT(a), NOT(b))   # ド・モルガンの法則

def XOR(a, b):
    c = NAND(a, b)
    return NAND(NAND(a, c), NAND(b, c))

真理値表で確かめます。

for a in (0, 1):
    for b in (0, 1):
        print(a, b, "| AND", AND(a, b), " OR", OR(a, b), " XOR", XOR(a, b))

XORは「入力が違うとき1」。これが足し算の"繰り上がりのない桁"に効いてきます。

② 半加算器: 1ビットの足し算

1ビット同士の足し算は、答え（sum）と繰り上がり（carry）に分かれます。1+1=10 なので sum=0, carry=1。これはXORとANDそのものです。

def half_adder(a, b):
    s = XOR(a, b)     # 和（繰り上がりを除いた桁）
    c = AND(a, b)     # 繰り上がり
    return s, c

print(half_adder(1, 1))   # (0, 1) = 「0、繰り上がり1」

③ 全加算器: 下の桁からの繰り上がりも足す

複数桁を足すには、下の桁からの繰り上がり（cin）も受け取る必要があります。半加算器を2つ繋げます。

def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s2, c2 = half_adder(s1, cin)
    return s2, OR(c1, c2)     # 和, 繰り上がり

# 全パターンを検証
for a in (0, 1):
    for b in (0, 1):
        for cin in (0, 1):
            s, cout = full_adder(a, b, cin)
            assert (cout * 2 + s) == (a + b + cin)   # 2進の足し算と一致
print("全加算器: 全8パターンOK ✅")

assert が通れば、NANDだけで作った回路が正しく足し算している証明です。あとはこの全加算器を桁数ぶん繋げれば、4ビット・8ビット……の加算器になり、CPUの演算器（ALU）の心臓部になります。

まとめ

• NAND1種類であらゆる論理回路が作れる（機能的完全性）
• NANDからNOT・AND・OR・XORをボトムアップで構築できる
• 半加算器＝XOR（和）＋AND（繰り上がり）、全加算器はそれを2つ連結
• 全加算器を並べればCPUの演算器（ALU）になる

もう少し詳しく（背景と理論）

NAND ゲートは機能的完全（functionally complete）な素子です——NAND だけを組み合わせれば、NOT・AND・OR、ひいては加算器やあらゆる論理回路を構成できます¹。これはド・モルガンの法則から導かれる性質で、NOR も同じく単体で完全です。半導体製造でこれが実務上重要なのは、CMOS では NAND/NOR が AND/OR より少ないトランジスタで作れ、しかも反転論理が自然だからです²。だから実際のチップは「まず NAND/NOR ありき」で設計され、標準セルライブラリの中核を成します。基本ゲート1種類から全計算が生まれるという事実は、コンピュータが「単純な部品の膨大な組み合わせ」であることの原点を示しています³。

次の一歩 🌸

物理的な素子の話はトランジスタの基礎、回路の全体像は論理回路のしくみ、設計の流れはチップ設計の流れへどうぞ。

Footnotes

1. NAND（および NOR）は単体で全論理関数を実現できる機能的完全な演算。NOT=NAND(A,A)、AND=NOT(NAND)、OR はド・モルガンで構成する。 ↩

2. CMOS では NAND/NOR が AND/OR より少トランジスタ（2入力NANDは4石）で実装でき、出力が反転論理。だから物理設計は反転ゲート主体になる。 ↩

3. 単一の万能ゲートから加算器・FSM・CPU まで積み上がる。抽象化の階層（ゲート→機能ブロック→アーキテクチャ）がコンピュータ設計の本質。 ↩