ブール代数をPythonで確かめる｜論理回路を"簡約"して減らす

論理回路を設計するとき、同じ働きならゲートは少ないほど良い（安い・速い・省電力）。そのために式を簡単にするのが ブール代数 です。この記事ではPythonの真理値表で、法則の正しさと簡約の効果を確かめます。

準備

Python標準機能だけ。

① 真理値表で法則を検証する

「2つの式が全入力で一致するか」を総当たりで確かめる関数を作ります。

from itertools import product

def equivalent(f, g, n_vars):
    for inputs in product([0, 1], repeat=n_vars):
        if f(*inputs) != g(*inputs):
            return False
    return True

# ド・モルガンの法則: not(a and b) == (not a) or (not b)
demorgan_left  = lambda a, b: int(not (a and b))
demorgan_right = lambda a, b: int((not a) or (not b))
print("ド・モルガン:", equivalent(demorgan_left, demorgan_right, 2))

出力は ド・モルガン: True。全4通りで一致＝法則が正しいことを機械的に確認できました。

② 簡約でゲートを減らす

冗長な式 (A AND B) OR (A AND NOT B) は、実は A だけで済みます（吸収）。

complex_expr = lambda A, B: int((A and B) or (A and (not B)))
simple_expr  = lambda A, B: A

print("簡約は正しい？:", equivalent(complex_expr, simple_expr, 2))

True。3ゲート必要だった回路が、配線1本（ゲート0個）になった——同じ動作で大幅に部品が減りました。これがブール代数で回路を最適化する狙いです。

③ よく使う法則をまとめて検証

laws = {
    "吸収 A+(A·B)=A":      (lambda A,B: int(A or (A and B)), lambda A,B: A),
    "分配 A·(B+C)":         (lambda A,B,C: int(A and (B or C)),
                             lambda A,B,C: int((A and B) or (A and C))),
    "二重否定 ¬¬A=A":       (lambda A: int(not (not A)), lambda A: A),
}
for name, (f, g) in laws.items():
    n = f.__code__.co_argcount
    print(f"{name:<20}: {equivalent(f, g, n)}")

すべて True。手計算で不安な簡約も、真理値表で機械的に検証できます。設計→簡約→検証の流れが、そのままハードウェア設計の基本です。

🌱

カルノー図と自動最適化

人手の簡約にはカルノー図という図解手法があります。実際のチップ設計では、EDAツール（論理合成）が数百万ゲートを自動で簡約・最適化します。原理は今回のブール代数。ツールが何をしているか、手を動かすと腑に落ちます。

⚠️

簡約 ≠ いつも最速

ゲート数を減らすと安く省電力になりますが、配線が長くなって遅くなることもあります。実設計では「面積・速度・電力」のトレードオフを見ながら最適化します。単純に少なければ良い、ではないのが奥深いところです。

まとめ

ブール代数で論理式を簡約し、ゲート数を減らせる
真理値表の総当たりで、法則や簡約の正しさを機械検証できる
冗長な3ゲート回路が配線1本になることも（吸収の法則）
実チップではEDAツールが同じ原理で自動最適化する

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

ブール代数は George Boole が1854年に論理を代数として定式化したもので、真/偽を1/0として AND・OR・NOT で操作します¹。これがデジタル回路と結びついたのは、Claude Shannon が1938年の修士論文で「スイッチ回路はブール代数で解析・設計できる」と示したときです——20世紀で最も影響力のある修士論文とも言われます²。設計上の重要な道具がド・モルガンの法則（NOT(A AND B) = NOT A OR NOT B）で、これを使うと任意の論理を NAND だけで構成できます³。カルノー図やクワイン・マクラスキー法による論理の簡単化は、ゲート数と遅延を減らす実務の基礎になります。

次の一歩 🌸

論理の基礎は論理回路のしくみ、加算器はNANDから全加算器、設計の流れはチップ設計の流れへどうぞ。

Boole, G. (1854). An Investigation of the Laws of Thought. 論理を代数的に扱う体系を確立し、後のデジタル論理の土台となった。 ↩
Shannon, C. (1938). "A Symbolic Analysis of Relay and Switching Circuits." スイッチ回路とブール代数を結びつけ、論理回路設計の理論を開いた。 ↩
ド・モルガンの法則は AND/OR/NOT を相互変換する。これにより NAND や NOR 単体で全論理を実装できる（機能的完全性）。 ↩