教材一覧
PROPOSITIONAL LOGIC

対偶法(間接証明)

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

対偶法

論理式\(A_{1},\cdots ,A_{n},B\)に関する以下の推論\begin{equation*}A_{1},\cdots ,\ A_{n}\ \therefore \ B
\end{equation*}の妥当性を示す方法の1つは、以下の論理式\begin{equation*}
\bigwedge_{i=1}^{n}A_{i}\rightarrow B
\end{equation*}が恒真式であることを示すというものです。ただ、対偶律より、これは以下の論理式\begin{equation*}
\lnot B\rightarrow \lnot \left( \bigwedge_{i=1}^{n}A_{i}\right)
\end{equation*}と論理的に同値であり、さらにド・モルガンの法則より、上の論理式は、\begin{equation*}
\lnot B\rightarrow \bigvee_{i=1}^{n}\lnot A_{i}
\end{equation*}と論理的に同値です。したがって以下の命題を得ます。

命題(対偶法)
論理式\(A_{1},\cdots ,A_{n},B\)について、以下の2つの命題はお互いに必要十分である。\begin{eqnarray*}&&\left( a\right) \ A_{1},\cdots ,A_{n}\ \models \ B \\
&&\left( b\right) \ \lnot B\ \models \ \bigvee_{i=1}^{n}\lnot A_{i}
\end{eqnarray*}
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

上の命題より、前提が\(A_{1},\cdots ,A_{n}\)であり結論が\(B\)であるような推論の妥当性を示すためには、前提が\(\lnot B\)であり結論が\(\bigvee_{i=1}^{n}\lnot A_{i}\)であるような推論の妥当性を示せばよいということになります。言い換えると、\(B\)が偽であるとともに\(A_{i}\ (i=1,\cdots,n)\)の中の少なくとも1つが偽であるような解釈が存在することを示せばよいということになります。このような証明法を対偶法(proof by contrapositive)や間接証明法(indirect proof)などと呼びます。

例(対偶法)
論理式\(A,B\)に関する以下の推論規則\begin{equation*}A\ \models \ B
\end{equation*}が成り立つことを示すためには、対偶法より、以下の推論規則\begin{equation*}
\lnot B\ \models \ \lnot A
\end{equation*}が成り立つことを示せばよいということになります。
例(対偶法)
何らかの整数\(x\)を任意に選んだとき、\(x^{2}\)が偶数ならば\(x\)もまた偶数であることを証明します。整数\(x\)を任意に選んだ上で、命題変数\(P,Q\)をそれぞれ、\begin{eqnarray*}P &:&x^{2}\text{は偶数である} \\
Q &:&x\text{は偶数である}
\end{eqnarray*}とおくと、以下の推論規則\begin{equation*}
P\ \models \ Q
\end{equation*}が成り立つことを示すことが目標になります。ただ、対偶法より、上の推論規則を示す代わりに、以下の推論規則\begin{equation*}
\lnot Q\ \models \ \lnot P
\end{equation*}が成り立つことを示しても構いません。つまり、\(x\)が偶数でない場合には、\(x^{2}\)は偶数でないことを示せば目標は達成されます。\(x\)は整数であるため、\(x\)や\(x^{2}\)が偶数でないことは、それらが奇数であることと言い換え可能です。したがって、\(x\)が奇数ならば\(x^{2}\)もまた奇数であることを示すことが目標です。\(x\)は奇数であるため、何らかの整数\(n\)を用いて、\begin{equation*}x=2n+1
\end{equation*}と表現できます。このとき、\begin{eqnarray*}
x^{2} &=&\left( 2n+1\right) ^{2} \\
&=&4n^{2}+4n+1 \\
&=&2\left( 2n^{2}+2n\right) +1
\end{eqnarray*}となるため、\(x^{2}\)もまた奇数です。したがって証明が完了しました。

 

対偶法と条件付き証明を併用する

繰り返しになりますが、論理式\(A_{1},\cdots ,A_{n},B\)に関する推論式\begin{equation}A_{1},\cdots ,A_{n}\ \models \ B \quad \cdots (1)
\end{equation}が成り立つことを示すかわりに、以下の推論式\begin{equation}
\lnot B\ \models \ \bigvee_{i=1}^{n}\lnot A_{i} \quad \cdots (2)
\end{equation}が成り立つことを示しても問題ないことを対偶律は保証します。このとき、\begin{eqnarray*}
\bigvee_{i=1}^{n}\lnot A_{i} &\Leftrightarrow &\left(
\bigvee_{i=1}^{n-1}\lnot A_{i}\right) \vee \lnot A_{n} \\
&\Leftrightarrow &\lnot \left( \bigwedge_{i=1}^{n-1}A_{i}\right) \vee \lnot
A_{n}\quad \because \text{ド・モルガン法則} \\
&\Leftrightarrow &\left( \bigwedge_{i=1}^{n-1}A_{i}\right) \rightarrow \lnot
A_{n}\quad \because \text{含意の言い換え}
\end{eqnarray*}という同値変形が可能であるため、\(\left( 2\right) \)は、\begin{equation}\lnot B\ \models \ \left( \bigwedge_{i=1}^{n-1}A_{i}\right) \rightarrow
\lnot A_{n} \quad \cdots (3)
\end{equation}と必要十分です。さらに条件付き証明より、\(\left( 3\right) \)は、\begin{equation*}\lnot B,\ \left( \bigwedge_{i=1}^{n-1}A_{i}\right) \ \models \ \lnot A_{n}
\end{equation*}すなわち、\begin{equation}
\lnot B,\ A_{1},\cdots ,A_{n-1}\ \models \ \lnot A_{n} \quad \cdots (4)
\end{equation}と必要十分です。以上の議論より、\(\left( 1\right) \)のかわりに\(\left( 4\right) \)を示しても問題ないことが明らかになりました。つまり、\(\left( 1\right) \)の結論および\(n-1\)個の前提がいずれも真であるという解釈のもとでは残りの前提が偽になることを示せばよいということです。

例(対偶法と条件付き証明)
以下の推論について考えます。\begin{eqnarray*}
&&\text{加藤さんは日本人または米国人である。} \\
&&\text{加藤さんが日本人ならば、彼は日本生まれである。} \\
&&\text{加藤さんは日本生まれではない。} \\
&&\text{ゆえに、加藤さんは米国人である。}
\end{eqnarray*}命題変数\(P,Q\)を、\begin{eqnarray*}P &:&\text{加藤さんは日本人である} \\
Q &:&\text{加藤さんは米国人である} \\
R &:&\text{加藤さんは日本生まれである}
\end{eqnarray*}とおくと、先の推論は、\begin{equation*}
P\vee Q,\ P\rightarrow R,\ \lnot R\ \therefore \ Q
\end{equation*}と定式化されます。対偶法および条件付き証明より、以下の推論\begin{equation*}
\lnot Q,\ P\vee Q,\ P\rightarrow R\ \therefore \ \lnot \lnot R
\end{equation*}が妥当であることを示しても問題ありません。具体的には、この推論は以下の証明

$$\begin{array}{lll}\left( 1\right) & \lnot Q & 前提 \\
\left( 2\right) & P\vee Q & 前提 \\
\left( 3\right) & P\rightarrow R & 前提 \\
\left( 4\right) & P & \left( 1\right) ,\left( 2\right) と選言三段論法 \\
\left( 5\right) & R & \left( 3\right) ,\left( 4\right) と含意除去 \\
\left( 6\right) & \lnot \lnot R & \left( 5\right) と二重否定導入\end{array}$$
によって証明可能です。したがって、\begin{equation}
P\vee Q,\ P\rightarrow R,\ \lnot R\ \models \ Q \quad \cdots (1)
\end{equation}が成り立つことが示されました。

 

演習問題

問題(対偶法)
以下の推論が妥当であることを通常の証明(直接法)と対偶法(間接法)のそれぞれで証明してください。\begin{eqnarray*}
&&\text{雨が降るなら海へは行かない} \\
&&\text{車があれば海へ行く} \\
&&\text{車はある} \\
&&\text{したがって、雨は降っていない}
\end{eqnarray*}
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(対偶法)
以下の推論が妥当であることを対偶法および条件付き証明を用いて証明してください。\begin{eqnarray*}
&&\text{鈴木さんは魚釣りをしない予定ならば、海へはドライブしない} \\
&&\text{鈴木さんは山へドライブする場合には、レンタカーを借りる} \\
&&\text{鈴木さんの車が壊れていなければ、彼はレンタカーを借りない} \\
&&\text{鈴木さんが海へドライブしないならば、彼は山へドライブする} \\
&&\text{鈴木さんの車は壊れていない} \\
&&\text{したがって、鈴木さんは魚釣りをする}
\end{eqnarray*}
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回は消去法について学びます。

質問・コメント(プレミアム会員限定) 次へ進む
< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

命題論理