命題論理における背理法

論理式\(A_{1},\cdots ,A_{n},B\)と恒偽式\(\bot \)について、以下の2つの命題\begin{eqnarray*}&&\left( a\right) \ A_{1},\cdots ,\ A_{n}\ \models \ B \\
&&\left( b\right) \ A_{1},\cdots ,\ A_{n},\lnot B\ \models \ \bot
\end{eqnarray*}はお互いに必要十分である。

論理式\(A,B,C\)に関する以下の推論\begin{equation*}A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \therefore \ \lnot A
\end{equation*}が妥当であることを証明します。以下の論理式の列

$$\begin{array}{llll}\left( 1\right) & A & \left[ 1\right] & 仮定 \\
\left( 2\right) & A\rightarrow \left( B\wedge C\right) & \quad & 前提 \\
\left( 3\right) & B\wedge C & \left[ 1\right] & \left( 1\right) ,\left( 2\right) と\rightarrow 除去 \\
\left( 4\right) & C & \left[ 1\right] & \left( 3\right) と\wedge 除去 \\
\left( 5\right) & \lnot C & \quad & 前提 \\
\left( 6\right) & \bot & \left[ 1\right] & \left( 4\right) ,\left( 5\right) と\lnot 除去 \\
\left( 7\right) & A\rightarrow \bot & \quad & \left( 1\right) ,\left( 6\right) と\rightarrow 導入 \\
\left( 8\right) & \lnot A & \quad & \left( 7\right) と\lnot 導入
\end{array}$$
について考えます。条件付き証明を利用します。つまり、もともとの前提である\(A\rightarrow \left( B\wedge C\right) \)と\(\lnot C\)が真であることに加えて、結論\(\lnot A\)の否定である\(A\)が真であることを仮定して議論を始めるということです。1行目の論理式\(\left( 1\right) \)の右側に記された\(\left[ 1\right] \)は、\(\left( 1\right) \)が前提ではなく仮定であることを表す記号です。\(\left(2\right) \)と\(\left( 5\right) \)は推論の前提であり仮定ではないため、それらの右側に\(\left[ 2\right] \)や\(\left[ 5\right] \)を記す必要はありません。さて、\(\left( 1\right) \)と\(\left( 2\right) \)に含意除去を適用すると\(\left( 3\right) \)が得られるため、\(\left( 1\right) \)と\(\left( 2\right) \)が真の場合には\(\left( 3\right) \)もまた真であることが保証されます。ただし、\(\left( 3\right) \)が依拠する\(\left( 1\right) \)は前提ではなく仮定であるため、そのことを明示するために\(\left( 3\right) \)の右側に\(\left[ 1\right] \)と記しています。\(\left( 3\right) \)に連言除去を適用すると\(\left( 4\right) \)が得られるため、\(\left( 3\right) \)が真の場合には\(\left( 4\right) \)もまた真であることが保証されます。ただし、\(\left( 3\right) \)は仮定\(\left( 1\right) \)に依拠するため、\(\left( 3\right) \)に依拠する\(\left( 4\right) \)もまた仮定\(\left( 1\right) \)に依拠します。そのことを明示するために\(\left( 4\right) \)の右側に\(\left[ 1\right] \)と記しています。\(\left( 5\right) \)は前提です。\(\left( 4\right) \)と\(\left( 5\right) \)に否定除去を適用すると\(\left( 6\right) \)が得られるため、\(\left( 4\right) \)と\(\left( 5\right) \)が真の場合には\(\left( 6\right) \)もまた真であることが保証されます。ただし、\(\left( 4\right) \)は仮定\(\left( 1\right) \)に依拠するため、\(\left( 4\right) \)に依拠する\(\left( 6\right) \)もまた仮定\(\left( 1\right) \)に依拠します。このことを明示するために\(\left( 6\right) \)の右側に\(\left[ 1\right] \)と記しています。ここからが重要です、これまでの議論により、\begin{equation*}\left( 1\right) ,\left( 2\right) ,\left( 5\right) \ \models \ \left(
6\right)
\end{equation*}すなわち、\begin{equation*}
A,\ A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \models \ \bot
\end{equation*}が成り立つことが示されました。ただ、先の命題より、この推論規則は、\begin{equation*}
A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \models \ \lnot A
\end{equation*}と必要十分であることが保証されますが、これは目標の推論規則に他なりません。したがって証明が完了しました。最後のプロセスを\(\left( 7\right) ,\left(8\right) \)のように理解することもできます。

整数\(z\)が素数であることとは、\(z>1\)であるとともに、\(z\)の約数が\(1\)と\(z\)だけであることを意味します。以上を踏まえた上で、素数が無限個存在することを証明します。命題変数\(P\)を、\begin{equation*}P:\text{素数が無限個存在する}
\end{equation*}と定義したとき、以下の推論規則\begin{equation*}
\models \ P
\end{equation*}が成り立つことを示すことが目標になりますが、背理法より、\begin{equation*}
\lnot P\ \models \ \bot
\end{equation*}が成り立つことを示しても構いません。そこで、\(\lnot P\)が真であると仮定します。つまり、素数が有限\(n\)個であることを仮定するということです。これらの素数を、\begin{equation*}p_{1},p_{2},\cdots ,p_{n}
\end{equation*}と表記します。素数は整数であり、整数どうしの和と積は整数であるため、\begin{equation*}
z=p_{1}\cdot p_{2}\cdot \cdots \cdot p_{n}+1
\end{equation*}は整数です。\(z\)を\(p_{1}\)で割ると\(1\)余るため、\(p_{1}\)は\(z\)の約数ではありません。同様に、\(p_{2},\cdots ,p_{n}\)はいずれも\(z\)の約数ではありません。したがって、\begin{equation*}Q:z\text{は素数の役数を持たない}
\end{equation*}が真です。また、\(z\)は\(1\)よりも大きい整数であるため、これは何らかの素数を約数として持ちます（確認してください）。したがって、\begin{equation*}\lnot Q:z\text{は素数の役数を持つ}
\end{equation*}もまた真です。\(Q\)と\(\lnot Q\)がともに真であるため、\(\wedge \)導入より\(Q\wedge \lnot Q\)は真であり、さらに\(\lnot \)除去より\(\bot \)を得ます。したがって目標が達成されました。

論理式\(A\)に関する以下の推論規則\begin{equation*}A\rightarrow \lnot A\ \models \ \lnot A
\end{equation*}が成り立つことを証明してください。

論理式\(A,B,C\)に関する以下の推論規則\begin{equation*}A\rightarrow \lnot B,\ A\rightarrow C,\ C\rightarrow B\ \models \ \lnot A
\end{equation*}が成り立つことを証明してください。

論理式\(A,B,C,D\)に関する以下の推論規則\begin{equation*}\left( \lnot B\vee C\right) \rightarrow A,\ B\rightarrow D,\ C\vee \lnot D\
\models A
\end{equation*}が成り立つことを証明してください。

論理式\(A\)に関する以下の推論規則\begin{equation*}A\ \models \ \lnot \lnot A
\end{equation*}は二重否定導入であるため成り立ちますが、そのことを背理法を用いて証明してください。

論理式\(A\)に関する以下の推論規則\begin{equation*}\models \ A\vee \lnot A
\end{equation*}は排中律であるため成り立ちますが、そのことを背理法を用いて証明してください。