論理式\(A_{1},\cdots ,A_{n}\)が前提であり、結論が論理式\(B\)であるとき、結論の否定 \(\lnot B\) が真であることを仮定した上で、これと推論の前提\(A_{1},\cdots ,A_{n}\)に対して推論規則を適用して最終的に恒偽式\(\bot \)を導くことができれば、否定導入より推論式が妥当であることが示されます。このような証明方法を背理法と呼びます。

2018年11月22日:公開

背理法

論理式\(A_{1},\cdots ,A_{n}\)が前提であり、結論が論理式\(B\)で表される推論\begin{equation*}
A_{1},\cdots ,\ A_{n}\ \therefore \ B
\end{equation*}が与えられたとき、\(B\)が偽すなわち\(\lnot B\)が真であることを仮定した上で、これと推論の前提\(A_{1},\cdots ,A_{n}\)に対して推論規則を適用して最終的に恒偽式\(\bot \)を導くことができれば、否定導入より\(\lnot \lnot B\)すなわち\(B\)が真になるため、推論式が妥当であることが示されます。このような証明方法を背理法(proof by contradiction)と呼びます。

否定導入について復習する

 

背理法の簡単な例を考えましょう。論理式\(A,B,C\)に関する以下の推論\begin{equation*}
A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \therefore \ \lnot A
\end{equation*}が妥当であることを証明します。つまり、\(A\rightarrow \left( B\wedge C\right) \)と\(\lnot C\)がともに真である場合には\(\lnot A\)もまた必ず真であることを示します。以下の論理式の列
\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}を考えます。\(\left( 1\right) \)は推論の前提ではありませんが、便宜上、これが真であるものと仮定して議論を進めます。\(\left( 1\right) \)の右側に記された\(\left[ 1\right] \)は\(\left( 1\right) \)が仮定であることを表す記号です。\(\left( 2\right) \)は推論の前提です。\(\left( 3\right) \)は\(\left( 1\right) \)と\(\left( 2\right) \)に対して推論規則(含意除去)を適用して得られる論理式ですが、これは仮定\(\left( 1\right) \)に依拠するため、\(\left( 3\right) \)の右側に\(\left[ 1\right] \)と記しています。\(\left( 4\right) \)は\(\left( 3\right) \)に対して推論規則(連言除去)を適用して得られる論理式ですが、これは仮定\(\left( 1\right) \)に依拠するため、\(\left( 4\right) \)の右側に\(\left[ 1\right] \)と記しています。\(\left( 5\right) \)は推論の前提です。\(\left( 6\right) \)は\(\left( 4\right) \)と\(\left( 5\right) \)に対して推論規則(否定除去)を適用して得られる論理式ですが、これは仮定\(\left( 1\right) \)に依拠するため、\(\left( 6\right) \)の右側に\(\left[ 1\right] \)と記しています。したがって推論規則\(A\models \bot \)が成り立ちますが、このとき、含意導入より\(\models A\rightarrow \bot \)が成り立ちます。つまり、\(\left( 1\right) \)が真であることを仮定せずとも\(A\rightarrow \bot \)は常に真ですから、\(\left( 7\right) \)の右側に\(\left[ 1\right] \)を記す必要はありません。最後に、\(\left( 7\right) \)に否定導入を適用して推論の結論である\(\left( 8\right) \)を得るため、推論が妥当であることが示されました。

含意除去について復習する 連言除去について復習する 否定除去について復習する 含意導入について復習する 否定導入について復習する
例(背理法)
論理式\(A,B,C\)に関する以下の推論\begin{equation*}
A\rightarrow \lnot B,\ A\rightarrow C,\ C\rightarrow B\ \models \ \lnot A
\end{equation*}は、以下の証明によって証明可能です。
\begin{array}{llll}
\left( 1\right) & A & \left[ 1\right] & 仮定 \\
\left( 2\right) & A\rightarrow \lnot B & \quad & 前提 \\
\left( 3\right) & \lnot B & \left[ 1\right] & \left( 1\right) ,\left( 2\right) と\rightarrow 除去 \\
\left( 4\right) & A\rightarrow C & \quad & 前提 \\
\left( 5\right) & C & \left[ 1\right] & \left( 1\right) ,\left( 4\right) と\rightarrow 除去 \\
\left( 6\right) & C\rightarrow B & \quad & 前提 \\
\left( 7\right) & B & \left[ 1\right] & \left( 5\right) ,\left( 6\right) と\rightarrow 除去 \\
\left( 6\right) & B\wedge \lnot B & \left[ 1\right] & \left( 3\right) ,\left( 6\right) と\wedge 導入 \\
\left( 7\right) & \bot & \left[ 1\right] & \left( 6\right) と\bot 導入 \\
\left( 8\right) & A\rightarrow \bot & \quad & \left( 1\right) ,\left( 7\right) と\rightarrow 導入 \\
\left( 9\right) & \lnot A & \quad & \left( 8\right) と\lnot 導入
\end{array}

次回は対偶法について学びます。
次へ進む 演習問題(プレミアム会員限定)