ド・モルガンの法則｜コードで実践

ド・モルガンの法則

このレッスンで分かること

ハードウェアでは NAND 1 種類だけで全ての論理が組める

論理演算には「否定をどう内側に押し込むか」という重要な等価変形があります

左辺は「a AND b の否定」「a OR b の否定」というカタマリに対する否定、右辺は否定を分配したものです

ド・モルガンの法則とは

ド・モルガンの法則を使って NOT (a AND b) を NOT a OR NOT b に変換する関数を実装し、等価性を実感します。

論理演算には「否定をどう内側に押し込むか」という重要な等価変形があります。それが ド・モルガンの法則 で、次の 2 つの式で表されます。

プレーンテキスト

NOT (a AND b)  =  (NOT a) OR  (NOT b)
NOT (a OR  b)  =  (NOT a) AND (NOT b)

左辺は「a AND b の否定」「a OR b の否定」というカタマリに対する否定、右辺は否定を分配したものです。NOT を AND/OR の中に持ち込むと、AND は OR に、OR は AND に切り替わる、というのがミソです。19 世紀のイギリスの数学者 Augustus De Morgan (オーガスタス・ド・モルガン) にちなんで命名されました。

プログラマーにとってこの法則は単なる知識ではなく、実務でリファクタリングのたびに使うツールです。if not (a and b) という条件は if (not a) or (not b) と書き換えられ、文脈によって読みやすい方を選べます。SQL の WHERE 句、React の条件レンダリング、bash の [[ ! (cond1 && cond2) ]] などでも頻出です。

「NOT を内側に押し込むと、AND と OR が入れ替わる」。これがド・モルガンの本質。

真理値表で等価性を確かめる

a, b の全 4 通りで、左辺と右辺の結果を並べると次のようになります。

a	b	NOT (a AND b)	NOT a OR NOT b
F	F	T	T
F	T	T	T
T	F	T	T
T	T	F	F

両方の列が完全に一致するので、ド・モルガンの法則が成り立っていることが確認できます。これを「真理値表による証明」と呼びます。論理回路の世界では、NAND ゲート (= NOT AND) と OR + NOT で同じ機能が実現できる、というハードウェア設計の指針にもなっています。

Python

def left(a, b):
    return not (a and b)

def right(a, b):
    return (not a) or (not b)

for a in [False, True]:
    for b in [False, True]:
        print(a, b, left(a, b) == right(a, b))  # 全部 True

ド・モルガンの可視化

diagram (will load when visible)

図のポイント (テキスト併記)

左の経路 NOT (a AND b) と右の経路 (NOT a) OR (NOT b) は、回路の見た目は違っても出力は完全に一致します

左の経路 NOT (a AND b) と右の経路 (NOT a) OR (NOT b) は、回路の見た目は違っても出力は完全に一致します。これは半導体の設計でも「NAND だけで全ての論理回路を作れる」という有名な性質につながります。

ハードウェアでは NAND 1 種類だけで全ての論理が組める。これもド・モルガンの法則のおかげ。

実務での活用シーン

ド・モルガンの法則は、可読性向上の道具として使われます。たとえば「未ログイン or 権限なし でアクセス拒否」と書くか、「ログイン済 and 権限あり のときだけ通す」と書くか。両者は同じ結果を返しますが、意味の読みやすさが文脈で変わります。

Python

# パターン A (否定で書く)
if not (logged_in and has_permission):
    deny()

# パターン B (ド・モルガンで分配)
if (not logged_in) or (not has_permission):
    deny()

この 2 つの書き方は等価ですが、B の方が「logged_in でないか、または has_permission でないか」をストレートに表現できる場面もあります。逆に「両方の条件を満たさないとダメ」というニュアンスを残したいときは A の方が読みやすい。リファクタリング時にどちらを選ぶか判断するときに、ド・モルガンの法則が頭に入っているとスピードが上がります。

ド・モルガンを覚えると、if not (...) と if (...) or (...) をスムーズに行き来できる。

よくある間違い

1 つめは、NOT (a AND b) = NOT a AND NOT b のように AND/OR の交代を忘れるケースです。これは間違いで、正しくは NOT a OR NOT b です。2 つめは、a > 0 のような比較式を NOT で囲ったときに a <= 0 に変換するときの境界の取り扱いを誤るケース。> の否定は <=、< の否定は >= です。3 つめは、Python の not の優先順位を勘違いし、not a == b を not (a == b) ではなく (not a) == b のつもりで書くケース。== の方が優先度が高いので、not a == b は not (a == b) と解釈されます。

やってみよう

2 つの真偽値を 0/1 で表した a b を受け取り、(NOT a) OR (NOT b) の結果を 0 か 1 で返す関数 deMorgan(a, b) を実装します。ド・モルガンの法則により、これは NOT (a AND b) と等価です。実装は素直に「a == 0 OR b == 0」と書けば OK。a = 1, b = 1 のときだけ 0 を返し、それ以外の 3 通りは 1 を返します。検算として、NOT (a AND b) のロジック (a*b == 1 のとき 0、それ以外 1) と同じ結果になることを確認してみてください。

よくある質問

Q. 真理値表は何のために覚えるのですか？

A. 複雑な条件式を網羅的に検証するための基本ツールです。バグの多くは「すべてのケースを考慮していない」ことが原因で、真理値表を書くと抜けが可視化されます。テスト設計でも各入力組み合わせを表にして網羅性を確認します。

Q. ド・モルガンの法則はコードで使う？

A. if (!(a && b)) を if (!a || !b) に書き換えるのがド・モルガンの応用です。否定をネストすると読みにくくなるため、否定を分配して短絡評価できる形に変えると可読性が上がります。レビューで頻出のリファクタです。

Q. 含意 (→) を AND/OR で表すには？

A. a → b は !a || b と等価です。論理学では a が偽のとき含意は真とみなすため、コードでは「a が成り立つなら b も成り立つはず」を !a || b で書きます。バリデーションロジックなどで頻出のパターンです。

次のレッスン

次は 第2章まとめクイズ に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

ド・モルガンの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. ド・モルガンとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

ド・モルガンの法則