ド・モルガンの法則を徹底解説：論理演算・集合論とIT実務での活用
エバープレイ編集部ド・モルガンの法則とは
ド・モルガンの法則（De Morganの法則）は、論理演算および集合演算における基本的かつ強力な恒等式です。論理式の否定を論理積（AND）や論理和（OR）の中に“押し込む（分配する）”ためのルールを与え、プログラミングやデジタル回路設計、検索クエリ最適化、論理式の正規形への変換など、IT の多くの分野で幅広く使われます。
定義（論理と集合の両面）
論理演算での定式化は次のとおりです。
- ¬(A ∧ B) ≡ (¬A) ∨ (¬B)
- ¬(A ∨ B) ≡ (¬A) ∧ (¬B)
集合論の表現では補集合と和積に対して次が成り立ちます（任意の集合 A, B について）。
- (A ∩ B)c = Ac ∪ Bc
- (A ∪ B)c = Ac ∩ Bc
上記は 2 項の場合の形ですが、任意個の項に対しても同様に成り立ちます（補集合が交叉と和の間で交換される）。
簡単な証明（真理値表と直感）
論理の真理値表を用いると明確です。A, B の 4 通りの組合せを列挙すると、左辺と右辺はすべての行で一致します。例えば ¬(A ∧ B) の場合、A ∧ B が真のときだけ左辺は偽で、それ以外は真。右辺 (¬A) ∨ (¬B) も同様に A と B の両方が真のときだけ偽になります。集合論的にも「両方に含まれる元が集合の補集合に含まれない」⇔「少なくとも一方の補集合に含まれる」として直観的に理解できます。
IT における応用例
以下は実務でよく出会う応用例です。
- プログラミング（コードの簡略化と可読性）
条件式の否定を展開して読みやすくしたり、短絡評価（short-circuit）を考慮して順序を入れ替えたりします。// C / Java の例 if (!(a && b)) { ... } // 等価: if (!a || !b) { ... } - ビット演算
ビットごとの否定と論理演算でも同様に成り立ちます（ビット演算子の補数と AND/OR の関係）。// ビット演算の例（符号や符号なしの振る舞いに注意） ~(x & y) == (~x) | (~y) ~(x | y) == (~x) & (~y) - デジタル回路設計
NAND や NOR は汎用ゲート（universal gate）として知られており、ド・モルガンの法則を用いることで AND/OR と NOT の組合せを NAND/NOR のみで実装できます。ハードウェアで論理を逆転させたりゲート数を最適化するときに重要です。 - 検索クエリ・フィルタ
検索エンジンやファイル検索で否定を内部に押し込むことで、インデックスやフィルタの適用が容易になります（例：NOT(タグA AND タグB) → NOT A OR NOT B）。 - SATソルバー・CNF 変換
論理式を CNF（合取標準形）や DNF（和標準形）に変換する際、否定を原子命題の前まで押し下げる（Negation Normal Form にする）操作でド・モルガンは必須です。以後、分配則などを使って CNF に変換していきます。
実用上の注意点
- 演算子の種類と優先順位
プログラミング言語では論理演算子（&&, ||, !）とビット演算子（&, |, ~）が異なるため、置換の際は型と意味（論理 vs ビット）に注意してください。また優先順位や結合性で括弧が必要になる場合があります。 - 三値論理（NULL）や特殊値
SQL の NULL を伴う三値論理や、浮動小数点の NaN 比較など、真偽が True/False 以外の値を取りうる場面では期待通りの振る舞いにならないことがあります。一般にド・モルガンの法則自体は論理体系の定義に依存しますが、実務では NULL を明示的に扱う（IS NULL / IS NOT NULL を使う）ことが安全です。 - 置換による意味の変化
特に SQL の WHERE 句などで、等式や不等式の書き換えを行うとき、NULL や三値論理、インデックスの利用状況によってはパフォーマンスや結果の包含関係が変わることがあるためテストが必要です。
具体例
いくつか実用的な例を示します。
- C 言語の条件式
if (!(is_ready && has_resource)) { // is_readyがfalseまたはhas_resourceがfalseのとき実行 } // → 等価 if (!is_ready || !has_resource) { ... } - ビット操作
uint8_t x = 0b1100; uint8_t y = 0b1010; uint8_t a = ~(x & y); // ~(1100 & 1010) = ~(1000) = 0111 uint8_t b = (~x) | (~y); // (~1100) | (~1010) = 0011 | 0101 = 0111 // a == b が成り立つ - SQL の注意（NULL を含む）
SQL での単純な書き換え例（NOT と AND/OR の置換）は大抵の場合に成り立ちますが、NULL をどう扱うかに注意してください。明確な結果を得たい場合は IS NULL/IS NOT NULL や COALESCE を併用しておくと安全です。
回路設計での応用：NAND / NOR の利用
ド・モルガンの法則を使うと、例えば OR を NAND のみで実現できます。
- OR を NAND のみで実現する手順：
- A OR B = NOT (NOT A AND NOT B)（ド・モルガンの逆）
- NOT A と NOT B はそれぞれ NAND(A,A), NAND(B,B) で得られる
- AND を NAND の出力で構成し、最後に NAND で否定することで OR を実現
理論的拡張：双対性（duality）との関係
ド・モルガンはブール代数の「双対性（dual）」と密接に関係します。式の中で ∧ と ∨、0 と 1 を置換しても成り立つ関係（双対）という観点から、ド・モルガンの法則はブール代数の根本的な対称性を表しています。
まとめ
ド・モルガンの法則は、否定と AND/OR の関係を明確にする基本法則で、プログラミング、クエリ最適化、回路設計、論理式の正規化など多岐にわたる実務で頻繁に使われます。置換自体は単純ですが、言語ごとの演算子の意味や三値論理、NULL・NaN といった特殊値の扱いには注意して適用してください。論理式を扱う場面ではまずこの法則を思い出し、式の簡略化や正規化、回路変換などに活用しましょう。
参考文献
- ド・モルガンの法則 - Wikipedia（日本語）
- De Morgan's laws - Wikipedia (English)
- NAND gate - Wikipedia (English)
- Three-valued logic — SQL and NULL - Wikipedia (English)
- PostgreSQL: Boolean Functions and Operators — PostgreSQL Documentation
投稿者プロフィール
