対偶法
推論が妥当であることを証明する際に、目標とする推論規則が成り立つことを示す代わりに、それと必要十分であるような推論規則が成り立つことを示す手法を間接証明法（indirect proof）と呼びます。先に学んだ背理法は間接証明法の1つですが、ここでは対偶法（proof by contrapositive）と呼ばれる間接証明法について解説します。まず、対偶法の根拠となる命題を提示します。
&&\left( b\right) \ \lnot B\ \models \ \bigvee_{i=1}^{n}\lnot A_{i}
\end{eqnarray*}はお互いに必要十分である。
上の命題はどのような意味において有用なのでしょうか。前提が\(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}と必要十分であるため、\(\left( 1\right) \)のかわりに\(\left( 2\right) \)を示しても構わないということになります。つまり、前提が\(\lnot B\)であり結論が\(\bigvee_{i=1}^{n}\lnot A_{i}\)であるような推論の妥当性を示せばよいということです。言い換えると、\(B\)が偽である場合には\(A_{i}\ (i=1,\cdots ,n)\)の中の少なくとも1つが必ず偽になることを示せばよいということになります。このような証明法を対偶法（proof bycontrapositive）と呼びます。
Q &:&x\text{は偶数}
\end{eqnarray*}を定義すると、与えられた推論は、\begin{equation*}
P\ \therefore \ Q
\end{equation*}と定式化されます。対偶法より、以下の推論\begin{equation*}
\lnot Q\ \because \ \lnot P
\end{equation*}が妥当であることを示しても問題ありません。つまり、「\(x\)が偶数ではない場合には\(x^{2}\)は偶数ではない」という推論の妥当性を示すことが目標になります。そこで、整数\(x\)が偶数ではないものとします。これは\(x\)が奇数であることと必要十分であるため、\begin{equation}x=2n+1 \quad \cdots (1)
\end{equation}という関係を満たす整数\(n\)が存在します。このとき、\begin{eqnarray*}x^{2} &=&\left( 2n+1\right) ^{2}\quad \because \left( 1\right) \\
&=&4n^{2}+4n+1 \\
&=&2\left( 2n^{2}+2n\right) +1
\end{eqnarray*}となるため、\(x^{2}\)は奇数であることが明らかになりました。これは\(x^{2}\)が偶数ではないことと必要十分であるため証明が完了しました。
Q &:&y\text{は奇数} \\
R &:&x+y\text{は奇数}
\end{eqnarray*}を定義すると、与えられた推論は、\begin{equation*}
P,\ Q\ \therefore \ R
\end{equation*}と定式化されます。対偶法より、以下の推論\begin{equation*}
\lnot R\ \because \ \lnot P\vee \lnot Q
\end{equation*}が妥当であることを示しても問題ありません。つまり、「\(x+y\)が奇数ではない場合には\(x\)が偶数ではないか\(y\)が奇数でないかの少なくとも一方である」という推論の妥当性を示すことが目標になります。そこで、整数\(x+y\)が奇数ではないものとします。これは\(x+y\)が偶数であることと必要十分であるため、\begin{equation}x+y=2n \quad \cdots (1)
\end{equation}という関係を満たす整数\(n\)が存在します。まずは\(x\)が偶数であるものとします。つまり、\begin{equation}x=2m \quad \cdots (2)
\end{equation}という関係を満たす整数\(m\)が存在します。このとき、\begin{eqnarray*}y &=&2n-x\quad \because \left( 1\right) \\
&=&2n-2m\quad \because \left( 2\right) \\
&=&2\left( n-m\right)
\end{eqnarray*}となるため\(y\)は偶数であり、したがって\(y\)は奇数ではありません。したがってこの場合には主張が成り立ちます。一方、\(x\)が偶数ではない場合には明らかに主張が成り立ちます。以上で証明が完了しました。
対偶法と条件付き証明の併用
対偶法と条件付き証明を併用することもできます。まずは根拠となる命題を提示します。
&&\left( b\right) \ \lnot B,\ A_{1},\cdots ,A_{n-1}\ \models \ \lnot A_{n}
\end{eqnarray*}はお互いに必要十分である。
上の命題はどのような意味において有用なのでしょうか。前提が\(A_{1},\cdots ,A_{n}\)であり結論が\(B\)であるような推論規則\begin{equation}\ A_{1},\cdots ,A_{n}\ \models \ B \quad \cdots (1)
\end{equation}が成り立つことを証明しようとしている状況を想定してください。先の命題より、この推論規則は以下の推論規則\begin{equation}
\lnot B,\ A_{1},\cdots ,A_{n-1}\ \models \ \lnot A_{n} \quad \cdots (2)
\end{equation}と必要十分であるため、\(\left( 1\right) \)のかわりに\(\left( 2\right) \)を示しても構わないということになります。
&&\text{加藤さんは日本人または米国人である。} \\
&&\text{加藤さんが日本人ならば、彼は日本生まれである。} \\
&&\text{加藤さんは日本生まれではない。} \\
&&\text{ゆえに、加藤さんは米国人である。}
\end{eqnarray*}命題変数\(P,Q,R\)を、\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}$$
によって証明可能です。
演習問題
&&\text{雨が降るなら海へは行かない} \\
&&\text{車があれば海へ行く} \\
&&\text{車はある} \\
&&\text{したがって、雨は降っていない}
\end{eqnarray*}
&&\text{鈴木さんは魚釣りをしない予定ならば、海へはドライブしない} \\
&&\text{鈴木さんは山へドライブする場合には、レンタカーを借りる} \\
&&\text{鈴木さんの車が壊れていなければ、彼はレンタカーを借りない} \\
&&\text{鈴木さんが海へドライブしないならば、彼は山へドライブする} \\
&&\text{鈴木さんの車は壊れていない} \\
&&\text{したがって、鈴木さんは魚釣りをする}
\end{eqnarray*}
プレミアム会員専用コンテンツです
【ログイン】【会員登録】