ド・モルガンの法則とは？

ド・モルガンの法則の意味

論理演算で「和の否定は否定の積」「積の否定は否定の和」が成り立つという法則。式で書くと NOT(A AND B) = (NOT A) OR (NOT B)、NOT(A OR B) = (NOT A) AND (NOT B)。論理式の変形や条件式の書き換え、論理回路の簡略化の基礎として頻出する。

ド・モルガンの法則の具体例

「年齢が20以上かつ会員である、ではない」は「20未満である、または会員でない」と言い換えられる。プログラムで !(a >= 20 && member) を a < 20 || !member に直すのは、まさにこの法則の適用。

ド・モルガンの法則は試験でどう引っ掛けられる？

否定を外側から内側へ配る際に、ANDとORの入れ替えを忘れる誤りが定番。NOT(A AND B) を (NOT A) AND (NOT B) としてはいけない。集合演算（補集合と和集合・積集合）でも同じ形で成り立つ。

ド・モルガンの法則と関連する用語

• 排他的論理和
• カルノー図
• グラフ理論

ド・モルガンの法則が出た過去問

• XとYの否定論理積X NAND Yは，NOT(X AND Y)として定義される。X OR YをNANDだけを使って表した論理式はどれか。

  正解：(X NAND X) NAND (Y NAND Y)

  要点：NANDだけでORは(X NAND X) NAND (Y NAND Y)

  ド・モルガンの法則より X OR Y = NOT((NOT X) AND (NOT Y)) と書けます。NANDは1入力を同じ値でまとめると否定として働くので、NOT X は X NAND X、NOT Y は Y NAND Y で作れます。その2つをさらにNANDすれば NOT(NOT X AND NOT Y) となり、OR が得られます。

  出典：平成29年度 春期 基本情報技術者試験 午前 問3（IPA）