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

背理法

論理式\(A_{1},\cdots ,A_{n},B\)に関する以下の推論\begin{equation}
A_{1},\cdots ,\ A_{n}\ \therefore \ B \tag{1}
\end{equation}の妥当性を示す方法の1つは、以下の論理式\begin{equation*}
\bigwedge_{i=1}^{n}A_{i}\rightarrow B
\end{equation*}が恒真式であることを示すと言うものです。ただ、これは以下の論理式\begin{equation*}
\left( \bigwedge_{i=1}^{n}A_{i}\right) \wedge \lnot B\rightarrow \bot
\end{equation*}と論理的に同値です(演習問題にします)。したがって以下の命題を得ます。

命題(背理法)
論理式\(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_{1},\cdots ,A_{n}\)であり結論が\(B\)であるような推論の妥当性を示すためには、結論\(B\)の否定を前提に加えた上で、そこから何らかの恒偽式を導けばよいということです。このような証明方法を背理法(proof by contradiction)と呼びます。

例(背理法)
命題変数\(P,Q,R\)に関する以下の推論\begin{equation*}
P\rightarrow \left( Q\wedge R\right) ,\ \lnot R\ \therefore \ \lnot P
\end{equation*}が妥当であることを証明します。つまり、\(P\rightarrow \left( Q\wedge R\right) \)と\(\lnot R\)がともに真である場合には\(\lnot P\)もまた必ず真であることを示します。以下の論理式の列
$$\begin{array}{llll}
\left( 1\right) & P & \left[ 1\right] & 仮定 \\
\left( 2\right) & P\rightarrow \left( Q\wedge R\right) & \quad & 前提 \\
\left( 3\right) & Q\wedge R & \left[ 1\right] & \left( 1\right) ,\left( 2\right) と\rightarrow 除去 \\
\left( 4\right) & R & \left[ 1\right] & \left( 3\right) と\wedge 除去 \\
\left( 5\right) & \lnot R & \quad & 前提 \\
\left( 6\right) & \bot & \left[ 1\right] & \left( 4\right) ,\left( 5\right) と\lnot 除去 \\
\left( 7\right) & P\rightarrow \bot & \quad & \left( 1\right) ,\left( 6\right) と\rightarrow 導入 \\
\left( 8\right) & \lnot P & \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] \)と記しています。したがって推論規則\(P\models \bot \)が成り立ちますが、このとき、含意導入より\(\models P\rightarrow \bot \)が成り立ちます。つまり、\(\left( 1\right) \)が真であることを仮定せずとも\(P\rightarrow \bot \)は常に真ですから、\(\left( 7\right) \)の右側に\(\left[ 1\right] \)を記す必要はありません。最後に、\(\left( 7\right) \)に否定導入を適用して推論の結論である\(\left( 8\right) \)を得るため、推論が妥当であることが示されました。
例(背理法)
命題変数\(P,Q,R\)に関する以下の推論規則\begin{equation*}
P\rightarrow \lnot Q,\ P\rightarrow R,\ R\rightarrow Q\ \models \ \lnot P
\end{equation*}は、以下の証明によって証明可能です。
$$\begin{array}{llll}
\left( 1\right) & P & \left[ 1\right] & 仮定 \\
\left( 2\right) & P\rightarrow \lnot Q & \quad & 前提 \\
\left( 3\right) & \lnot Q & \left[ 1\right] & \left( 1\right) ,\left( 2\right) と\rightarrow 除去 \\
\left( 4\right) & P\rightarrow R & \quad & 前提 \\
\left( 5\right) & R & \left[ 1\right] & \left( 1\right) ,\left( 4\right) と\rightarrow 除去 \\
\left( 6\right) & R\rightarrow Q & \quad & 前提 \\
\left( 7\right) & Q & \left[ 1\right] & \left( 5\right) ,\left( 6\right) と\rightarrow 除去 \\
\left( 6\right) & Q\wedge \lnot Q & \left[ 1\right] & \left( 3\right) ,\left( 7\right) と\wedge 導入 \\
\left( 7\right) & \bot & \left[ 1\right] & \left( 6\right) と\bot 導入 \\
\left( 8\right) & P\rightarrow \bot & \quad & \left( 1\right) ,\left( 7\right) と\rightarrow 導入 \\
\left( 9\right) & \lnot P & \quad & \left( 8\right) と\lnot 導入
\end{array}$$

次回は対偶法について学びます。

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

命題論理
アカウント
ログイン