教材一覧
教材一覧
教材検索
PROPOSITIONAL 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\)もまた偶数である」という推論は妥当でしょうか。以下の命題変数\begin{eqnarray*}P &:&x^{2}\text{は偶数} \\
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}\)が偶数ではないことと必要十分であるため証明が完了しました。
例(対偶法)
整数\(x,y\)について、「\(x\)が偶数で\(y\)が奇数ならば\(x+y\)は奇数である」という推論は妥当でしょうか。以下の命題変数\begin{eqnarray*}P &:&x\text{は偶数} \\
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\)が偶数であることと必要十分であるため、\begin{equation}x+y=2n \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}\)が偶数ではないことと必要十分であるため証明が完了しました。

 

対偶法と条件付き証明の併用

対偶法と条件付き証明を併用することもできます。まずは根拠となる命題を提示します。

命題(対偶法と条件付き証明の併用)
論理式\(A_{1},\cdots ,A_{n},B\)について、以下の2つの命題\begin{eqnarray*}&&\left( a\right) \ A_{1},\cdots ,A_{n}\ \models \ B \\
&&\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) \)を示しても構わないということになります。

例(対偶法と条件付き証明の併用)
以下の推論について考えます。\begin{eqnarray*}
&&\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}$$
によって証明可能です。

 

演習問題

問題(対偶法)
整数\(x\)について、「\(7x+9\)が偶数ならば\(x\)は奇数である」という推論が妥当であることを対偶法を用いて証明してください。
解答を見る

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

問題(対偶法)
実数\(x,y\)について、「\(y^{3}+yx^{2}\leq x^{3}+xy^{2}\)ならば\(\ y\leq x\)である」という推論が妥当であることを対偶法を用いて証明してください。
解答を見る

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

問題(対偶法)
以下の推論が妥当であることを対偶法と条件付き証明を用いて証明してください。\begin{eqnarray*}
&&\text{雨が降るなら海へは行かない} \\
&&\text{車があれば海へ行く} \\
&&\text{車はある} \\
&&\text{したがって、雨は降っていない}
\end{eqnarray*}
証明

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

問題(対偶法)
以下の推論が妥当であることを対偶法と条件付き証明を用いて証明してください。\begin{eqnarray*}
&&\text{鈴木さんは魚釣りをしない予定ならば、海へはドライブしない} \\
&&\text{鈴木さんは山へドライブする場合には、レンタカーを借りる} \\
&&\text{鈴木さんの車が壊れていなければ、彼はレンタカーを借りない} \\
&&\text{鈴木さんが海へドライブしないならば、彼は山へドライブする} \\
&&\text{鈴木さんの車は壊れていない} \\
&&\text{したがって、鈴木さんは魚釣りをする}
\end{eqnarray*}
解答を見る

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

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

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

質問とコメント

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

対偶律
述語論理における対偶法

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

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

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

命題論理