論理と命題

概要

前提知識: 命題, 論理演算, 集合演算

動機

本記事は、初歩的な集合論を述べるために必要な最小限の論理と命題（logic and propositions）を扱う。論理式そのものを数学的対象として形式的に定式化する立場（数理論理学）は取らない。
集合論の議論で実際に必要になるのは、命題についての法則がそのまま集合演算についての法則を与えるという仕組みである。旧来これは個々の等式ごとに真偽表を書いて確かめられてきたが、「どの真偽の割り当てでも同じ真偽をとる二つの論理式は、集合に読み替えても同じ集合を与える」という一つの定理にまとめられる。本記事はこの定理と、その証明でも使われる排中律を主題とする。
命題の概念そのものと、個々の結合子の詳しい扱いは命題と論理演算に譲る（いずれも未作成）。本記事で使う範囲の定義は次のとおりである。

論理結合子と真理値表

命題は真・偽のいずれか一方だけに確定するものとする（古典論理の立場）。命題 $P,Q$ から新しい命題を作る次の記号を論理結合子（logical connective）という。

$\lnot P$（$P$ の否定）は、$P$ が真のとき偽、$P$ が偽のとき真である。
$P\land Q$（$P$ かつ $Q$、連言）は、$P$ と $Q$ がともに真のときに限り真である。
$P\lor Q$（$P$ または $Q$、選言）は、$P$ と $Q$ の少なくとも一方が真のとき真である。両方が真であってもよい。
$P\Rightarrow Q$（$P$ ならば $Q$、含意）は、$P$ が真かつ $Q$ が偽のときに限り偽である。とくに $P$ が偽ならば $Q$ の真偽によらず真である（空虚な真）。
$P\Leftrightarrow Q$（$P$ と $Q$ は同値）は $(P\Rightarrow Q)\land(Q\Rightarrow P)$ の略記であり、$P$ と $Q$ の真偽が一致するとき、かつそのときに限り真である。
$P,Q$ の真偽の組み合わせ 4 通りのそれぞれについて各結合子の値を一覧にした次の表を真理値表（truth table）という。

$P$ $Q$ $\lnot P$ $P\land Q$ $P\lor Q$ $P\Rightarrow Q$ $P\Leftrightarrow Q$

真真偽真真真真
真偽偽偽真偽偽
偽真真偽真真偽
偽偽真偽偽真真

$P$	$Q$	$\lnot P$	$P\land Q$	$P\lor Q$	$P\Rightarrow Q$	$P\Leftrightarrow Q$
真	真	偽	真	真	真	真
真	偽	偽	偽	真	偽	偽
偽	真	真	偽	真	真	偽
偽	偽	真	偽	偽	真	真

基本的な恒真式

任意の命題 $P,Q$ について、次の各式は $P,Q$ の真偽によらず真である（恒真式）。

（二重否定）$\lnot(\lnot P)\Leftrightarrow P$。
（対偶）$(P\Rightarrow Q)\Leftrightarrow(\lnot Q\Rightarrow\lnot P)$。
（De Morgan の法則）$\lnot(P\land Q)\Leftrightarrow(\lnot P\lor\lnot Q)$ および $\lnot(P\lor Q)\Leftrightarrow(\lnot P\land\lnot Q)$。

$P\Leftrightarrow Q$ 型の式は両辺の真偽が一致するとき、かつそのときに限り真だから、各式について、$P,Q$ の真偽のすべての組み合わせで両辺の真偽が一致することを def-logic-connectives-truth-table の表から確かめればよい。

$P$ が真なら $\lnot P$ は偽、$\lnot(\lnot P)$ は真で、$P$ と一致する。$P$ が偽なら $\lnot P$ は真、$\lnot(\lnot P)$ は偽で、$P$ と一致する。
$P\Rightarrow Q$ が偽になるのは $P$ が真かつ $Q$ が偽の 1 通りだけである。一方 $\lnot Q\Rightarrow\lnot P$ が偽になるのは $\lnot Q$ が真かつ $\lnot P$ が偽、すなわち $Q$ が偽かつ $P$ が真の 1 通りだけである。両辺は同じ 1 通りの組み合わせでのみ偽、残りの 3 通りで真であり、真偽が一致する。
前半について。$\lnot(P\land Q)$ が偽になるのは $P\land Q$ が真、すなわち $P,Q$ がともに真の 1 通りだけである。$\lnot P\lor\lnot Q$ が偽になるのは $\lnot P$ と $\lnot Q$ がともに偽、すなわち $P,Q$ がともに真の 1 通りだけである。よって真偽が一致する。後半について。$\lnot(P\lor Q)$ が真になるのは $P\lor Q$ が偽、すなわち $P,Q$ がともに偽の 1 通りだけであり、$\lnot P\land\lnot Q$ が真になるのも $\lnot P,\lnot Q$ がともに真、すなわち $P,Q$ がともに偽の 1 通りだけである。よって真偽が一致する。$\square$

変数を含む主張（述語）と、それに全称・存在の量化を施した命題については全称記号を参照する。また、$P\Rightarrow Q$ が真であるときの「$P$ は $Q$ の十分条件、$Q$ は $P$ の必要条件」という言いかたと、両向きの含意が真であるときの必要十分条件・同値という言いかたは本記事では定義せず、必要条件と十分条件に譲る（未作成）。

定義

集合による解釈のとりかた

$p_1,\dots,p_n$ を変数記号とし、これらから $\lnot,\land,\lor,\Rightarrow$ を有限回用いて作られる式を、本記事では $p_1,\dots,p_n$ の論理式といい $\Phi,\Psi$ などで表す。量化記号は含めない。各 $p_i$ に真・偽のいずれか一方を対応させる規則 $v$ を割り当てといい、割り当て $v$ のもとでの $\Phi$ の真偽を $\Phi[v]$ と書く。$\Phi[v]$ は、$\Phi$ の作られかたの順に、上に挙げた真偽の定めかたによって定まる。一般の論理式の定め方と真理値割り当ての扱いはそれぞれの記事に譲り、ここでは上の形の式だけを考える。
集合 $X$ とその部分集合 $A_1,\dots,A_n$ に対し、$\Phi$ の集合による解釈（set-theoretic interpretation）$\Phi^X(A_1,\dots,A_n)$ を、$\Phi$ の作られかたの順に次で定める。
$$p_i^X=A_i,\qquad(\lnot\Phi)^X=X\setminus\Phi^X,\qquad(\Phi\land\Psi)^X=\Phi^X\cap\Psi^X,$$
$$(\Phi\lor\Psi)^X=\Phi^X\cup\Psi^X,\qquad(\Phi\Rightarrow\Psi)^X=(X\setminus\Phi^X)\cup\Psi^X.$$
ここで $A\cap B$ は共通部分、$A\cup B$ は和集合、$X\setminus A$ は $X$ における $A$ の補集合（補集合）である。$A_1,\dots,A_n$ が文脈から明らかなときは $\Phi^X$ と略記する。

定理

排中の法則

任意の命題 $P$ に対し、$P$ の真偽によらず $P\lor\lnot P$ は真である。これを排中律（law of excluded middle）という。

命題は真・偽のいずれか一方だけに確定するから、$P$ については次の二つの場合に尽きる。
$P$ が真の場合。$P\lor\lnot P$ は $P$ と $\lnot P$ の少なくとも一方が真であれば真であり、いま $P$ が真なので $P\lor\lnot P$ は真である。
$P$ が偽の場合。否定の定めかたにより $\lnot P$ は真である。よって少なくとも一方が真なので $P\lor\lnot P$ は真である。
いずれの場合も $P\lor\lnot P$ は真であり、この二つで場合は尽きている。$\square$

排中律は、$\lnot P$ を仮定して矛盾を導くことで $P$ を結論する背理法の論理的な根拠になっている。また $P\Rightarrow Q$ を示す代わりにその対偶 $\lnot Q\Rightarrow\lnot P$ を示す方法もよく使われ、その正当性は prop-logic-basic-tautologies の 2 による。二重否定 $\lnot(\lnot P)\Leftrightarrow P$ も同命題の 1 で示した。背理法・対偶による証明そのものは背理法と対偶による証明に譲る（いずれも未作成）。なお排中律を一般には認めない立場（直観主義論理）もあるが、本記事および本サイトの初等的な集合論の記述は排中律を認める古典論理に立つ（Kunen16）。

所属の言い換え

$X$ を集合、$A_1,\dots,A_n$ をその部分集合、$\Phi$ を $p_1,\dots,p_n$ の論理式とする。$x\in X$ に対し、各 $p_i$ に命題「$x\in A_i$」の真偽を対応させる割り当てを $v_x$ と書く。このとき $\Phi^X(A_1,\dots,A_n)$ は $X$ の部分集合であり、
$$x\in\Phi^X(A_1,\dots,A_n)\iff\Phi[v_x]\ \text{が真である}$$
が成り立つ。

まず $\Phi^X\subset X$ を、$\Phi$ の作られかたに関する帰納法（構造帰納法）で示す。$\Phi=p_i$ のときは $\Phi^X=A_i\subset X$ である。$\Phi^X\subset X$ かつ $\Psi^X\subset X$ のとき、$X\setminus\Phi^X\subset X$、$\Phi^X\cap\Psi^X\subset X$、$\Phi^X\cup\Psi^X\subset X$、$(X\setminus\Phi^X)\cup\Psi^X\subset X$ はいずれも定義から明らかである。よってすべての論理式について $\Phi^X\subset X$ である。
次に同値を、$\Phi$ の作られかたに関する帰納法で示す。以下 $x\in X$ を固定する。
$\Phi=p_i$ のとき。$\Phi^X=A_i$ であり、$v_x(p_i)$ は命題「$x\in A_i$」の真偽そのものだから、$x\in A_i$ であることと $\Phi[v_x]$ が真であることは同値である。
$\Phi=\lnot\Psi$ のとき。$x\in X$ だから、$x\in X\setminus\Psi^X$ であることと $x\notin\Psi^X$ であることは同値である。帰納法の仮定より $x\in\Psi^X$ と「$\Psi[v_x]$ が真」は同値なので、$x\notin\Psi^X$ と「$\Psi[v_x]$ が偽」は同値である。否定の定めかたにより、これは「$(\lnot\Psi)[v_x]$ が真」と同値である。
$\Phi=\Psi\land\Theta$ のとき。$x\in\Psi^X\cap\Theta^X$ であることは、$x\in\Psi^X$ かつ $x\in\Theta^X$ であることと同値である（集合演算）。帰納法の仮定によりこれは「$\Psi[v_x]$ と $\Theta[v_x]$ がともに真」と同値であり、連言の定めかたにより「$(\Psi\land\Theta)[v_x]$ が真」と同値である。
$\Phi=\Psi\lor\Theta$ のとき。$x\in\Psi^X\cup\Theta^X$ であることは、$x\in\Psi^X$ または $x\in\Theta^X$ であることと同値である（集合演算）。帰納法の仮定と選言の定めかたにより、これは「$(\Psi\lor\Theta)[v_x]$ が真」と同値である。
$\Phi=\Psi\Rightarrow\Theta$ のとき。$x\in(X\setminus\Psi^X)\cup\Theta^X$ であることは、$x\in X\setminus\Psi^X$ または $x\in\Theta^X$ であることと同値であり、$x\in X$ だから、$x\notin\Psi^X$ または $x\in\Theta^X$ であることと同値である。帰納法の仮定より、これは「$\Psi[v_x]$ が偽、または $\Theta[v_x]$ が真」と同値である。含意の定めかたにより $(\Psi\Rightarrow\Theta)[v_x]$ が偽であるのは $\Psi[v_x]$ が真かつ $\Theta[v_x]$ が偽のときに限るから、「$\Psi[v_x]$ が偽、または $\Theta[v_x]$ が真」は「$(\Psi\Rightarrow\Theta)[v_x]$ が真」と同値である。
論理式は $p_1,\dots,p_n$ から上の五つの作りかたを有限回用いて得られるものに限るので、帰納法によりすべての論理式について同値が成り立つ。$\square$

恒真な同値からの移送

$\Phi,\Psi$ を $p_1,\dots,p_n$ の論理式とし、どの割り当て $v$ に対しても $\Phi[v]$ と $\Psi[v]$ の真偽が一致するとする（すなわち $\Phi\Leftrightarrow\Psi$ がすべての割り当てで真である。恒真式）。このとき、任意の集合 $X$ と $X$ の任意の部分集合 $A_1,\dots,A_n$ に対して
$$\Phi^X(A_1,\dots,A_n)=\Psi^X(A_1,\dots,A_n)$$
が成り立つ。

lem-logic-and-proposition-membership により両辺はともに $X$ の部分集合である。したがって、$X$ の各元について両辺への所属が一致することを示せばよい。
$x\in X$ を任意にとり、lem-logic-and-proposition-membership の割り当て $v_x$ を考える。同補題より、$x\in\Phi^X$ であることは $\Phi[v_x]$ が真であることと同値である。仮定を割り当て $v_x$ に適用すると、$\Phi[v_x]$ が真であることと $\Psi[v_x]$ が真であることは同値である。ふたたび同補題より、$\Psi[v_x]$ が真であることは $x\in\Psi^X$ であることと同値である。よって $x\in\Phi^X$ と $x\in\Psi^X$ は同値である。
$x\in X$ は任意であり、両辺は $X$ の部分集合だから、$\Phi^X$ と $\Psi^X$ は同じ元からなる。よって両者は等しい。$\square$

帰結・補足

つねに真である式の解釈

$\Phi$ を $p_1,\dots,p_n$ の論理式とし、どの割り当て $v$ に対しても $\Phi[v]$ が真であるとする。このとき、任意の集合 $X$ と $X$ の任意の部分集合 $A_1,\dots,A_n$ に対して $\Phi^X(A_1,\dots,A_n)=X$ が成り立つ。

lem-logic-and-proposition-membership により $\Phi^X\subset X$ である。逆に $x\in X$ を任意にとると、仮定より割り当て $v_x$ について $\Phi[v_x]$ は真であり、同補題より $x\in\Phi^X$ である。よって $X\subset\Phi^X$ であり、両包含から $\Phi^X=X$ である。$\square$

$\Phi=p_1\lor\lnot p_1$ はどの割り当てでも真であり（thm-logic-and-proposition-excluded-middle）、その解釈は $\Phi^X(A)=A\cup(X\setminus A)$ である。したがって $A\cup(X\setminus A)=X$ はこの系の一例にあたる。この集合の等式そのものは公開記事補集合が扱う。

移送の逆向き

$X$ を空でない集合とし、$\Phi,\Psi$ を $p_1,\dots,p_n$ の論理式とする。$X$ の任意の部分集合の組 $A_1,\dots,A_n$ に対して $\Phi^X(A_1,\dots,A_n)=\Psi^X(A_1,\dots,A_n)$ が成り立つならば、どの割り当て $v$ に対しても $\Phi[v]$ と $\Psi[v]$ の真偽は一致する。

割り当て $v$ を任意にとる。$X$ は空でないので元 $x_0\in X$ をとることができる。各 $i$ について、$v(p_i)$ が真のときは $A_i:=X$、偽のときは $A_i:=\emptyset$（空集合）と定める。いずれも $X$ の部分集合である。
このとき、$x_0\in A_i$ であることと $v(p_i)$ が真であることは同値である。実際、$v(p_i)$ が真なら $A_i=X$ で $x_0\in X$ であり、$v(p_i)$ が偽なら $A_i=\emptyset$ で $x_0\notin\emptyset$ である。よって lem-logic-and-proposition-membership の割り当て $v_{x_0}$ は $v$ に一致する。
同補題より、$x_0\in\Phi^X(A_1,\dots,A_n)$ であることは $\Phi[v]$ が真であることと同値であり、$x_0\in\Psi^X(A_1,\dots,A_n)$ であることは $\Psi[v]$ が真であることと同値である。仮定によりこの二つの集合は等しいから、$x_0$ の所属は一致し、したがって $\Phi[v]$ と $\Psi[v]$ の真偽は一致する。$v$ は任意だったので主張が従う。$\square$

反例：空集合上では逆向きが成り立たない

次の例は、cor-logic-and-proposition-converse の仮定「$X$ は空でない」が落とせないことを示す。破れる含意は「$X$ の任意の部分集合の組について解釈が一致するならば、二つの論理式はどの割り当てでも同じ真偽をとる」である。
$X=\emptyset$ とする。$\emptyset$ の部分集合は $\emptyset$ だけであり、lem-logic-and-proposition-membership によりどの論理式 $\Phi$ の解釈も $\emptyset$ の部分集合、すなわち $\emptyset$ である。したがって $\Phi=p_1$、$\Psi=\lnot p_1$ という、どの割り当てでも真偽がちょうど食い違う二つの論理式についても $\Phi^{\emptyset}=\Psi^{\emptyset}=\emptyset$ が成り立ってしまう。仮定を満たす対象が一つもないために条件がすべて成り立つという事情については空虚な真を参照。

包含関係との対応

$X$ を集合、$A,B$ をその部分集合とする。$(p_1\Rightarrow p_2)^X(A,B)=X$ であることと $A\subset B$ であることは同値である。

定義より $(p_1\Rightarrow p_2)^X(A,B)=(X\setminus A)\cup B$ である。
$A\subset B$ とする。$x\in X$ を任意にとると、thm-logic-and-proposition-excluded-middle を命題「$x\in A$」に適用して、$x\in A$ であるか $x\notin A$ であるかのいずれかが成り立つ。前者なら $A\subset B$ より $x\in B$ であり、後者なら $x\in X$ とあわせて $x\in X\setminus A$ である。いずれにせよ $x\in(X\setminus A)\cup B$ であり、$X\subset(X\setminus A)\cup B$ を得る。逆の包含は $X\setminus A\subset X$ と $B\subset X$ から従う。よって $(X\setminus A)\cup B=X$ である。
逆に $(X\setminus A)\cup B=X$ とする。$x\in A$ を任意にとると $A\subset X$ より $x\in X$ であり、$x\in A$ だから $x\notin X\setminus A$ である。仮定より $x\in(X\setminus A)\cup B$ なので $x\in B$ である。よって $A\subset B$ である。$\square$

共通部分の交換律を移送で導く

$\Phi=p_1\land p_2$、$\Psi=p_2\land p_1$ とおく。連言は二つの項がともに真のときに限り真だから、どの割り当てに対しても $\Phi$ と $\Psi$ の真偽は一致する。集合 $X$ とその部分集合 $A,B$ について $\Phi^X(A,B)=A\cap B$、$\Psi^X(A,B)=B\cap A$ であるから、thm-logic-and-proposition-transfer により $A\cap B=B\cap A$ が従う。
同じ手続きを $\lnot(p_1\land p_2)$ と $\lnot p_1\lor\lnot p_2$ の組（prop-logic-basic-tautologies の 3）に適用すれば $X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B)$ が、$p_1\land(p_2\lor p_3)$ と $(p_1\land p_2)\lor(p_1\land p_3)$ の組に適用すれば $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ が得られる。得られる集合の等式そのもの（交換律・結合律・分配律・De Morganの法則など）を主題として扱うことは集合演算に譲り（未作成）、本記事はそれらを導く手続きのほうを扱う。

補足を 3 点述べる。

本記事のどの証明でも選択公理は使っていない。
論理式は有限個の記号から作られるので、上の移送は有限個の部分集合についての等式しか与えない。添字集合 $I$ による $\bigcup_{i\in I}A_i$ や $\bigcap_{i\in I}A_i$ の法則は、量化を含む主張として別に扱う必要がある（全称記号）。
ここで扱った範囲を超えて、論理式・証明・モデルそのものを数学の対象として研究する分野が数理論理学である。
本記事の記述はおおむね Hara20 第 2 章および Kunen16 に従う。