WIIS

述語論理

述語論理における背理法

目次

Mailで保存
Xで共有

背理法

推論が妥当であることを証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その仮定と前提に対して推論規則を適用していく手法が時として有効です。ここでは背理法(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\)は存在しない」という推論が妥当であることを背理法で証明してください。
解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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