ド・モルガンの法則の証明


前回のエントリで無限個の集合に対してド・モルガンの法則が成り立つことを書いた。
もともと覚えることが目的ではないし、確率、統計、微積、基礎解析を結構本気で理解するためにやっているので、ド・モルガンの法則の証明を読んで感じたことを書いていく。

論理的、というとアレだけども、数学が事実を数式で表現する学問である以上、かなり多くの事象を論理式の関係式から説明できる(らしい)。
論理式の式変形を暗記しても仕方がなくて、論理式の変形の意味自体が数式で表される事実の見方になっている。

事実を数学的な主張と捉えるから「命題」という訳だな。
「命題」を論理式として表現し、論理式の関係を立てるというのは、事実を数式で表していることに他ならないな。

ド・モルガンの法則の証明

\(x\)は集合\(A\)の要素であるという命題\(p\)について\( p:x \in A\)、
その否定命題を\( \lnot p\)と表す。\( \lnot p : x \not \in A \)。
命題\( p\)、命題\( q\)の両方が成り立つ主張を\( p \land q \)。
どちらか一方が成り立つ主張を\( p \lor q \)で表す。

このとき以下の関係が成り立つ。何かから導出されたのではなく事実の言及。
実際、\(p\)、\(q\)の2元からなる論理値表を書くと、左辺が成り立てば右辺も成り立つことがわかる。
$$
\lnot(p \land q) \Leftrightarrow (\lnot p \lor \lnot q) \\
\lnot(p \lor q) \Leftrightarrow (\lnot p \land \lnot q)
$$

さて、では無限集合に対するド・モルガンの法則。
ド・モルガンの法則の同値記号の左側について、
同値記号の右辺に異なる見方から導出した論理式を並べていく。

集合\(A\)と集合\(B\)の積集合の補集合に要素\(x\)が含まれるということは、
集合\(A\)と集合\(B\)の積集合に要素\(x\)が含まれないということ。うん当たり前だ。
$$
x\in (A \cap B)^{c} \Leftrightarrow x \not \in A \cap B
$$

…に存在しない、という命題は、…に存在する、という命題の否定だから、
$$
\Leftrightarrow \lnot (x \in A \cup B )
$$

要素\(x\)が\(A \cup B\)に属するということは、要素\(x\)が\(A\)と\(B\)の両方に存在するということだから、
$$
\Leftrightarrow \lnot (x \in A \land x \in B )
$$

ここで最初の式を適用する。
$$
\Leftrightarrow \lnot (x \in A) \lor \lnot (x \in B)
$$

論理式を集合演算子に書き換える。
$$
\Leftrightarrow x \not \in A \lor x \not \in B
$$

補集合の定義から、
$$
\Leftrightarrow x \in A^{c} \lor x \in B^{c}
$$

要素\(x\)が \(A^{c}\)または\(B^{c}\)の要素であることと\(A^{c}\cup B^{c} \)の要素であることは同値だから、

$$
\Leftrightarrow x \in A^{c} \cup B^{c}
$$

最終的に、
$$
x\in (A \cap B)^{c} \Leftrightarrow x \in A^{c} \cup B^{c}
$$

これは、ド・モルガンの法則の1個目の式。ド・モルガンの法則の1個の式が証明された。

結局のところ 

論理式の式変形は、命題を異なる見方で表現することに他ならない。
証明しようとする事実から一歩離れて、論理式の式変形を行うことで証明できるかも。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする