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

対偶法

論理式\(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\)であるような推論の妥当性を示すためには、\(B\)が偽であるとともに、\(A_{i}\ (i=1,\cdots ,n)\)の中の少なくとも1つが偽であるような解釈が存在することを示せばよいということになります。このような証明法を対偶法(proof by contrapositive)と呼びます。

例(対偶法)
命題変数\(P,Q\)に関する以下の推論規則\begin{equation*}
P\ \models \ Q
\end{equation*}が成り立つことを示すためには、対偶法より、以下の推論規則\begin{equation*}
\lnot Q\ \models \ \lnot P
\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}\)もまた奇数です。したがって証明が完了しました。

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

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

プレミアム会員サービス

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

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

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