ド・モルガンの法則

1 基本概念

ド・モルガンの法則は、否定と論理結合子の関係を示す基本的な等式である。命題論理では「かつ」「または」を含む式の否定を、要素ごとの否定と結び替えた形に変換できる。集合論では、和集合や積集合の補集合に対応する形として現れ、論理学と集合論の橋渡しになる。

1.1 ド・モルガンの法則の定義

この法則は、2つの代表的な形で表される。ひとつは「A かつ B」である否定が「A でない または B でない」と同値になるという形であり、もうひとつは「A または B」である否定が「A でない かつ B でない」と同値になるという形である。複数の対象をまとめて否定する操作を、個別の否定へ分解する規則として理解される。

1.2 論理学における意味

論理学では、複雑な命題を整理し、同値なより扱いやすい式へ書き換えるために用いられる。特に、証明の途中で否定を外側から内側へ移したり、条件分岐を整理したりする場面で有効である。真偽を保ったまま式の形を変えられるため、推論の流れを明瞭にする。

1.3 集合論における対応

集合論では、補集合の計算を通じてこの法則が表現される。ある集合の和集合の外側にある要素は、それぞれの集合に属さない要素として記述でき、逆に積集合の外側は少なくとも一方に属さない要素の集まりとして表される。論理記号との対応関係が明確で、両分野を同じ構造として捉えやすい。

2 命題論理での表現

命題論理では、ド・モルガンの法則は否定の分配則のように働く。連言と選言のどちらに対しても、外側の否定を内側へ移しながら結合子を入れ替えることで、同値な命題を得られる。

2.1 否定と連言の関係

「A かつ B」の否定は、両方が同時に成り立つことが否定されるため、「A でない または B でない」と等しい。少なくとも一方が偽であれば元の連言は真にならないため、全体の否定は個々の否定の選言で表せる。

2.2 否定と選言の関係

「A または B」の否定は、どちらか一方が成り立つことを否定するので、「A でない かつ B でない」と同値になる。いずれかが真であれば選言は真になるため、その否定は両方とも偽である場合に限られる。

2.2.1 論理式の変形例

たとえば、命題 P と Q に対して、否定 ¬(P ∧ Q) は ¬P ∨ ¬Q に変えられる。また、¬(P ∨ Q) は ¬P ∧ ¬Q となる。これらの変形は、式の外観を単純にするだけでなく、他の推論規則と組み合わせる際の見通しもよくする。

2.2.2 真理値表による確認

真理値表を用いると、両辺がすべての真偽の組合せで一致することを確かめられる。各命題の真偽を列挙すると、連言や選言の否定が対応する個別否定の組合せと同じ結果を返すことが分かる。こうした確認は、等価変形が単なる形式上の操作ではないことを示す。

2.3 論理式の同値変形

ド・モルガンの法則は、他の同値法則と併用されることが多い。二重否定の除去や分配法則、含意の書き換えと組み合わせると、複雑な式を段階的に簡約できる。証明や計算機処理では、標準形へ整えるための基礎的な手順となる。

3 集合論での表現

集合論では、補集合を含む式を扱う際にド・モルガンの法則が直接役立つ。論理式の対応物として見ると、和集合と積集合のどちらにも対称的な関係がある。

3.1 和集合の補集合

集合 A と B の和集合の補集合は、A にも B にも属さない要素の集合である。これは A の補集合と B の補集合の積集合に一致する。つまり、全体集合の中でどちらにも入らない部分を取り出す操作として理解できる。

3.2 積集合の補集合

A と B の積集合の補集合は、A と B の両方に同時には属さない要素の集まりであり、A の補集合と B の補集合の和集合に等しい。少なくとも一方から外れる要素を集める形になるため、和集合側の表現が自然に対応する。

3.3 ベン図による理解

ベン図では、図形の塗り分けによってこの法則の意味を視覚的に確かめられる。領域の外側や重なり部分を観察すると、補集合の対応関係が直感的に把握しやすい。

3.3.1 図式的な説明

2つの円で表した集合を考えると、和集合の外側は両方の円の外部に当たる。積集合の外側は、少なくとも一方の円の外部に相当する。図の陰影を比較すると、記号操作と領域の対応が一目で分かる。

3.3.2 具体例

たとえば、学生の集合とスポーツ部員の集合を考えると、「どちらにも属さない人」はそれぞれの補集合の積集合に当たる。また、「両方に属する人でない」は、少なくとも一方に属していない人として表せる。抽象的な関係が、身近な分類でも同じ形で成り立つ。

4 応用

ド・モルガンの法則は、純粋数学だけでなく、回路設計やプログラム構築にも現れる。否定条件の整理や論理の変換を支えるため、実務的な場面でも広く使われる。

4.1 数学の証明での利用

反証法や場合分けを用いる証明では、否定を扱いやすい形へ変えるためにこの法則が有効である。命題の外側にある否定を内側へ移すことで、仮定の構造を見直しやすくなる。集合や論理の議論でも、同値変形の起点として頻繁に使われる。

4.2 電気回路と論理回路

論理回路では、AND、OR、NOT の対応を通じてこの法則が実装上の指針になる。ある機能を別のゲート構成へ置き換える際に、否定の位置を調整できるため、回路の構成が簡潔になることがある。デジタル回路の設計では、同値な表現を選ぶことが部品数や配線の最適化につながる。

4.3 プログラミングにおける条件式の整理

プログラムでは、条件式の否定を分かりやすく書き換えるのに役立つ。たとえば、「両方満たす」ことの否定を、「どちらか一方が満たされない」と表現すれば、分岐条件が読みやすくなる。バグの確認や条件の簡略化にも有用で、保守性の向上にも寄与する。