対偶法
推論が妥当であることを証明する際に、目標とする推論規則が成り立つことを示す代わりに、それと必要十分であるような推論規則が成り立つことを示す手法を間接証明法（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\left( x\right) &:&x\text{は偶数}
\end{eqnarray*}を定義すると、与えられた推論は、\begin{equation}
\therefore \ \forall x\in X:\left( P\left( x\right) \rightarrow Q\left(
x\right) \right) \quad \cdots (1)
\end{equation}と定式化されます。整数\(c\)を任意に選んだとき、\begin{equation}P\left( c\right) \Rightarrow Q\left( c\right) \quad \cdots (2)
\end{equation}が成り立つことを示せば、全称導入より\(\left( 1\right) \)が妥当になるため、以下では\(\left( 2\right) \)を示します。対偶法より、\begin{equation}\lnot Q\left( c\right) \Rightarrow \lnot P\left( c\right) \quad \cdots (3)
\end{equation}を示しても構いません。そこで、\(\lnot Q\left( c\right) \)が成り立つものとします。つまり、整数\(c\)は偶数ではないということです。これは\(c\)が奇数であることと必要十分であるため、\begin{equation}c=2d+1 \quad \cdots (4)
\end{equation}を満たす整数\(d\)が存在します。このとき、\begin{eqnarray*}c^{2} &=&\left( 2d+1\right) ^{2}\quad \because \left( 4\right) \\
&=&4d^{2}+4d+1 \\
&=&2\left( 2d^{2}+2d\right) +1
\end{eqnarray*}となるため、\(c^{2}\)が奇数であること、すなわち\(c^{2}\)が偶数ではないこと、すなわち\(\lnot P\left( c\right) \)が真であることが示されました。以上より\(\left( 3\right) \)が成り立つことが示されたため証明が完了しました。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】