論理の分配法則、集合の分配法則とは、証明

どうも、木村(@kimu3_slime)です。

論理の分配法則、集合の分配法則とは何か、その証明を紹介します。

前提知識:記号論理、命題論理入門:覚えるべき論理記号(否定、かつ、または、ならば、同値)とは

 

論理の分配法則

論理の分配法則とは、命題\(P,Q,R\)について、次の論理同値が成り立つことです。

\[P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)\]

\[P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)\]

ここで、\(\land\)はかつ(論理積)、\(\lor\)はまたは(論理和)、\(\equiv\)は論理同値を表す記号です。

特に前者を、命題を数に、\(\land\)を\(\times\)、\(\lor\)を\(+\)で置き換えると、

\[p \times(q + r) = p\times q + p \times r\]

という数の分配法則となります。

これと同じように、論理の分配法則(distributive law)と呼ばれてます。命題代数の法則のひとつとして、分配原理(principle of distributivity)とも。

 

まず前半を、命題の真偽(T、F)の総当り、真理値によって証明しましょう。

\(P\)\(Q\)\(R\)\(Q \lor R\)\(P \land (Q \lor R)\)
TTTTT
TTFTT
TFTTT
TFFFF
FTTTF
FTFTF
FFTTF
FFFFF

 

\(P\)\(Q\)\(R\)\(P \land Q\)\(P \land R\)\((P \land Q) \lor (P \land R)\)
TTTTTT
TTFTFT
TFTFTT
TFFFFF
FTTFFF
FTFFFF
FFTFFF
FFFFFF

いずれのケースでも2つの命題の真理値は一致するので、これらの命題は論理同値です。

 

後半の主張は、同様に証明できますが、論理に関するド・モルガンの法則からも導けます。

\[P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)\]

において、両辺を否定しましょう。ド・モルガンの法則から、かつとまたはが入れ替わり、左辺は

\[ \lnot P \lor (\lnot Q \land \lnot R)\]

となり、右辺は

\[ (\lnot P \lor \lnot Q) \land (\lnot P \lor \lnot R)\]

となります。\(P,Q,R\)はどんな命題であっても成り立つ論理同値を用いたので、その否定命題\(\lnot P , \lnot Q , \lnot R\)もどんな命題であっても良いです。したがって、それらを新たに\(P^{\prime}, Q^{\prime},R^{\prime}\)と置き換えれば、

\[P^{\prime} \lor (Q^{\prime} \land R^{\prime}) \equiv (P^{\prime} \lor Q^{\prime}) \land (P^{\prime} \lor R^{\prime})\]

が成り立つことが示せました。

 

集合の分配法則

集合の分配法則とは、集合\(A,B,C\)について、常に次の2つの集合が(集合として)等しくなることです。

\[A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\]

\[A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\]

\(\cap\)は共通部分、\(\cap\)は和集合です。

これらの分配法則は、論理の分配法則において、\(\land\)を\(\cap\)に、\(\lor \)を\(\cup\)に、\(\equiv\)を\(=\)に置き換えた形をしていますね。

 

集合の分配法則の証明は、論理の分配法則の証明に帰着されます。

集合と要素の定義、共通部分と和集合の定義から、どんな要素\(x\)についても、

\[x\in A \cap (B \cup C) \\ \Leftrightarrow (x\in A) \land ((x \in B) \lor (x \in C))\]

\[x\in (A \cap B) \cup (A \cap C) \\ \Leftrightarrow ((x\in A) \land (x \in B)) \lor ((x\in A) \land (x \in C))  \]

が成りたちます。したがって、命題\(P,Q,R\)を

\[P: x \in A\]

\[Q: x \in B\]

\[R: x \in C\]

と定めれば、論理の分配法則から、これらの命題が同値であることがわかります。

集合が等しいこと\(D=E\)の定義は、すべての\(x\)について\( x \in D \Leftrightarrow x\in E\)が成り立つことなので、集合の分配法則の前半が示せました。

後半も全く同様です。

 

以上、論理の分配法則、集合の分配法則とは何か、その証明を紹介してきました。

集合の分配法則はしばしば当たり前のものとされがちですが、それが論理の分配法則にもとづいて証明できることが伝われば嬉しいです。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

論理と集合から始める数学の基礎
嘉田 勝(著)
日本評論社 (2008-12-10T00:00:00.000Z)
5つ星のうち3.9
¥2,717

 
 

集合・位相入門 (松坂和夫 数学入門シリーズ 1)
松坂 和夫(著)
岩波書店 (2018-11-07T00:00:01Z)
5つ星のうち4.7
¥2,255 (中古品)

 

こちらもおすすめ

記号論理、命題論理入門:覚えるべき論理記号(否定、かつ、または、ならば、同値)とは

論理に関するド・モルガンの法則を真偽値の計算(プログラミング)で確かめる

複数の命題の同値「A⇔B⇔C」はサイクル「A⇒B⇒C⇒A」と同値であることの証明