教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における対偶法

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

対偶法

推論が妥当であることを証明する際に、目標とする推論規則が成り立つことを示す代わりに、それと必要十分であるような推論規則が成り立つことを示す手法を間接証明法(indirect proof)と呼びます。先に学んだ背理法は間接証明法の1つですが、ここでは対偶法(proof by contrapositive)と呼ばれる間接証明法について解説します。まず、対偶法の根拠となる命題を提示します。

命題(対偶法)
論理式\(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\)であるような推論規則\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)と呼びます。

例(対偶法)
「任意の整数\(x\)について、\(x^{2}\)が偶数ならば\(x\)は偶数である」という推論が妥当であることを証明します。変数\(x\)の定義域\(X\)はすべての整数からなる集合であり、以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x^{2}\text{は偶数} \\
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) \)が成り立つことが示されたため証明が完了しました。

 

演習問題

問題(対偶法)
「任意の整数\(x\)について、\(x^{2}-6x+5\)が偶数ならば\(x\)は奇数である」という推論が妥当であることを対偶法を用いて証明してください。
解答を見る

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

問題(対偶法)
「任意の実数\(x,y\)について、\(y^{3}+x^{2}y\leq x^{3}+xy^{2}\)が成り立つ場合には\(y\leq x\)もまた成り立つ」という推論が妥当であることを対偶法を用いて証明してください。
解答を見る

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

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

対偶
命題論理における対偶律

論理式 A,B に対して、B→A を含意 A→B の逆と呼び、¬A→¬B を A→B の裏と呼び、¬B→¬A を A→B の対偶と呼びます。含意とその対偶は同値であり、含意の逆と裏は同値です。

証明
命題論理における証明

推論の妥当性を示すために、前提を出発点として同値変形の法則や推論規則を用いて結論を次々に導出し、最終的に当初の推論式の結論を導出する手法を証明や演繹などと呼びます。

条件付き証明
命題論理における条件付き証明

推論を証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その論理式と推論の前提に対して推論規則を適用していく手法が時として有効です。仮定を利用する証明方法の代表的なものは条件付き証明です。

対偶律
命題論理における対偶法

推論の結論が偽であることを出発点として、推論の前提の少なくとも 1 つが偽であることを導くことができれば、対偶律よりもとの推論の妥当性が示されます。このような証明方法を対偶法と呼びます。

消去法
命題論理における消去法

結論が論理式 B,C を用いて B∨C で表される推論が与えられたとき、推論の前提に加えて ¬B が真であるということを出発点として C が真であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法と呼びます。

証明
述語論理における証明

推論の妥当性を示すために、前提を出発点として同値変形の法則や推論規則を用いて結論を次々に導出し、最終的に当初の推論式の結論を導出する手法を証明や演繹などと呼びます。

条件付き証明
述語論理における条件付き証明

推論を証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その論理式と推論の前提に対して推論規則を適用していく手法が時として有効です。仮定を利用する証明方法の代表的なものは条件付き証明です。

条件付き証明
述語論理における背理法

推論の結論が論理式 Bとして表されるとき、その否定 ¬B が真であることを仮定した上で、これと推論の前提に対して推論規則を適用して最終的に恒偽式を導くことができれば推論式が妥当であることを示したことになります。このような証明方法を背理法と呼びます。

消去法
述語論理における消去法

結論が論理式 B,C を用いて B∨C で表される推論が与えられたとき、推論の前提に加えて ¬B が真であるということを出発点として C が真であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法と呼びます。

述語論理