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

述語論理における背理法

目次

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

背理法

推論が妥当であることを証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その仮定と前提に対して推論規則を適用していく手法が時として有効です。ここでは背理法(proof by contradiction)と呼ばれる証明方法について解説しますが、その前に根拠となる命題を提示します。

命題(背理法)
論理式\(A_{1},\cdots ,A_{n},B\)と恒偽式\(\bot \)について、以下の2つの命題\begin{eqnarray*}&&\left( a\right) \ A_{1},\cdots ,\ A_{n}\ \models \ B \\
&&\left( b\right) \ A_{1},\cdots ,\ A_{n},\lnot B\ \models \ \bot
\end{eqnarray*}はお互いに必要十分である。

証明

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

上の命題はどのような意味において有用なのでしょうか。論理式\(A_{1},\cdots ,A_{n}\)が前提であり、結論が論理式\(B\)であるような推論規則\begin{equation}A_{1},\cdots ,\ A_{n}\ \models \ B \quad \cdots (1)
\end{equation}が成り立つことを証明しようとしている状況を想定してください。先の命題より、この推論規則は以下の推論規則\begin{equation}
A_{1},\cdots ,\ A_{n},\lnot B\ \models \ \bot \quad \cdots (2)
\end{equation}と必要十分であるため、\(\left( 1\right) \)のかわりに\(\left( 2\right) \)を示しても構わないということになります。つまり、前提が\(A_{1},\cdots ,A_{n}\)であり結論が\(B\)であるような推論規則\(\left( 1\right) \)が成り立つことを示すかわりに、結論\(B\)の否定\(\lnot B\)を仮の前提(仮定)として加えた上で、そこから推論規則を適用して恒偽式を導いてもよい(推論規則\(\left(2\right) \)が成り立つことを示す)ということです。このような証明方法を背理法と呼びます。

例(背理法)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) ,R\left( x\right) \)が与えられたとき、以下の推論\begin{equation*}\forall x\in X:\left( \left( P\left( x\right) \rightarrow P\left( x\right)
\right) \rightarrow \left( Q\left( x\right) \rightarrow R\left( x\right)
\right) \right) \ \therefore \ \forall x\in X:\left( Q\left( x\right)
\rightarrow R\left( x\right) \right)
\end{equation*}が妥当であることを条件付き証明を用いて示します。つまり、もともとの前提である、\begin{equation*}
\forall x\in X:\left( \left( P\left( x\right) \rightarrow P\left( x\right)
\right) \rightarrow \left( Q\left( x\right) \rightarrow R\left( x\right)
\right) \right)
\end{equation*}が真であることに加えて、結論\begin{equation*}
\forall x\in X:\left( Q\left( x\right) \rightarrow R\left( x\right) \right)
\end{equation*}の否定である、\begin{equation*}
\lnot \left( \forall x\in X:\left( Q\left( x\right) \rightarrow R\left(
x\right) \right) \right)
\end{equation*}が真であることを仮定して議論を始めるということです。具体的には、以下の証明によって証明可能です。

$$\begin{array}{llll}\left( 1\right) & \forall x\in X:\left( \left( P\left( x\right) \rightarrow P\left( x\right) \right) \rightarrow \left( Q\left( x\right) \rightarrow R\left( x\right) \right) \right) & \quad & 前提 \\
\left( 2\right) & \lnot \left( \forall x\in X:\left( Q\left( x\right) \rightarrow R\left( x\right) \right) \right) & \left[ 2\right] & 仮定 \\
\left( 3\right) & \exists x\in X:\lnot \left( Q\left( x\right) \rightarrow R\left( x\right) \right) & \left[ 2\right] & \left( 2\right) と全称命題の否定 \\
\left( 4\right) & \lnot \left( Q\left( c\right) \rightarrow R\left( c\right) \right) & \left[ 2\right] & \left( 3\right) と\exists 除去 \\
\left( 5\right) & \left( P\left( c\right) \rightarrow P\left( c\right) \right) \rightarrow \left( Q\left( c\right) \rightarrow R\left( c\right) \right) & \quad & \left( 1\right) と\forall 除去 \\
\left( 6\right) & \lnot \left( P\left( c\right) \rightarrow P\left( c\right) \right) & \left[ 2\right] & \left( 4\right) ,\left( 5\right) と\rightarrow 除去 \\
\left( 7\right) & \lnot \left( \lnot P\left( c\right) \vee P\left( c\right) \right) & \left[ 2\right] & \left( 6\right) と\rightarrow の言い換え \\
\left( 8\right) & \lnot \lnot P\left( c\right) \wedge \lnot P\left( c\right) & \left[ 2\right] & \left( 7\right) とド・モルガンの法則 \\
\left( 9\right) & P\left( c\right) \wedge \lnot P\left( c\right) & \left[ 2\right] & \left( 8\right) と\lnot \lnot 除去 \\
\left( 10\right) & \bot & \left[ 2\right] & \left( 9\right) と\lnot 除去 \\
\left( 11\right) & \lnot \left( \forall x\in X:\left( Q\left( x\right) \rightarrow R\left( x\right) \right) \right) \rightarrow \bot & \quad & \left( 2\right) ,\left( 10\right) と\rightarrow 導入 \\
\left( 12\right) & \lnot \lnot \left( \forall x\in X:\left( Q\left( x\right) \rightarrow R\left( x\right) \right) \right) & \quad & \left( 11\right) と\lnot 導入 \\
\left( 13\right) & \forall x\in X:\left( Q\left( x\right) \rightarrow R\left( x\right) \right) & \quad & \left( 12\right) と\lnot \lnot 除去
\end{array}$$

例(背理法)
「任意の整数\(z\)について、\(z^{3}+5\)が奇数である場合には\(z\)は偶数である」という推論の妥当性を示します。変数\(z\)の定義域\(Z\)はすべての整数です。以下の命題関数\begin{eqnarray*}P\left( z\right) &:&z^{3}+5\text{は奇数} \\
Q\left( z\right) &:&z\text{は偶数}
\end{eqnarray*}を定義すると、与えられた推論は、\begin{equation*}
\therefore \ \forall z\in Z:\left( P\left( x\right) \rightarrow Q\left(
z\right) \right)
\end{equation*}と定式化されます。背理法より、上の推論の結論の否定\begin{equation}
\lnot \left( \forall z\in Z:\left( P\left( x\right) \rightarrow Q\left(
z\right) \right) \right) \quad \cdots (1)
\end{equation}が真であることを仮定した上で、そこから恒偽式を導けば目的を達成したことになります。\(\left( 1\right) \)を同値変形すると、\begin{eqnarray*}\lnot \left( \forall z\in Z:\left( P\left( x\right) \rightarrow Q\left(
z\right) \right) \right) &\Leftrightarrow &\exists z\in Z:\lnot \left(
P\left( x\right) \rightarrow Q\left( z\right) \right) \quad \because \text{全称命題の否定} \\
&\Leftrightarrow &\exists z\in Z:\lnot \left( \lnot P\left( x\right) \vee
Q\left( z\right) \right) \quad \because \text{含意の言い換え} \\
&\Leftrightarrow &\exists z\in Z:\left( \lnot \lnot P\left( x\right) \wedge
\lnot Q\left( z\right) \right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\exists z\in Z:\left( P\left( x\right) \wedge \lnot
Q\left( z\right) \right) \quad \because \text{二重否定}
\end{eqnarray*}すなわち、\begin{equation*}
\exists z\in Z:\left( P\left( x\right) \wedge \lnot Q\left( z\right) \right)
\end{equation*}を得ます。つまり、ある整数\(z\)について\(z^{3}+5\)は奇数であり、なおかつ\(z\)は偶数ではない(奇数である)ことを仮定するということです。つまり、\begin{equation*}\exists k\in X,\ \exists l\in l:\left( z^{3}+5=2k+1\wedge z=2l+1\right)
\end{equation*}を仮定します。\(z\)を消去して変形すると、\begin{equation*}\exists k\in X,\ \exists l\in l:k-4l^{3}-6l^{2}-3l=\frac{5}{2}
\end{equation*}となりますが、左辺の\(k-4l^{3}-6l^{2}-3l\)は整数である一方で右辺の\(\frac{5}{2}\)は整数ではないため、これは恒偽式です。したがって証明が完了しました。

 

演習問題

問題(背理法)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) ,R\left( x\right) \)が与えられたとき、以下の推論\begin{equation*}\left( \exists x\in X:P\left( x\right) \right) \vee \left( \exists x\in
X:Q\left( x\right) \right) ,\ \forall x\in X:\left( P\left( x\right)
\rightarrow Q\left( x\right) \right) \ \because \ \exists x\in X:Q\left(
x\right)
\end{equation*}が妥当であることを証明してください。

証明

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

問題(背理法)
「\(18x+6y=1\)を満たす整数\(x,y\)は存在しない」という推論が妥当であることを背理法で証明してください。
解答を見る

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

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

質問とコメント

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

RELATED KNOWLEDGE

関連知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

述語論理