論理式\(A_{1},\cdots ,A_{n}\)が前提であり、結論が論理式\(B\)で表される推論が与えられたとき、\(B\)が偽であることを出発点として\(A_{i}\)の中の少なくとも 1 つが偽であることを導くことができれば、対偶律よりもとの推論が妥当であることが示されます。このような証明方法を対偶法と呼びます。

2018年11月23日:公開

対偶法

論理式\(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*}と言い換えられます。したがって、\(B\)が偽であるときに、\(A_{i}\ (i=1,\cdots ,n)\)の中の少なくとも 1 つが偽であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを対偶法(proof by contrapositive)と呼びます。

対偶律について復習する ド・モルガンの法則について復習する
例(対偶法)
整数\(x\)について、\(x^{2}\)が偶数ならば\(x\)もまた偶数であることを証明します。対偶法より、整数\(x\)について、\(x\)が偶数でなければ\(x^{2}\)もまた偶数でないこと、すなわち、\(x\)が奇数ならば\(x^{2}\)も奇数であることを示してもかまいません。\(x\)は奇数ですので、\begin{equation*}
x=2n+1
\end{equation*}と表現できます。ただし、\(n\)は整数です。このとき、\begin{eqnarray*}
x^{2} &=&\left( 2n+1\right) ^{2} \\
&=&4n^{2}+4n+1 \\
&=&2\left( 2n^{2}+2n\right) +1
\end{eqnarray*}となるため、\(x^{2}\)もまた奇数です。したがって証明が完了しました。

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