教材一覧
教材一覧
教材検索
PROPOSITIONAL 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) \)が成り立つことを示す)ということです。このような証明方法を背理法と呼びます。

例(背理法)
論理式\(A,B,C\)に関する以下の推論\begin{equation*}A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \therefore \ \lnot A
\end{equation*}が妥当であることを証明します。以下の論理式の列

$$\begin{array}{llll}\left( 1\right) & A & \left[ 1\right] & 仮定 \\
\left( 2\right) & A\rightarrow \left( B\wedge C\right) & \quad & 前提 \\
\left( 3\right) & B\wedge C & \left[ 1\right] & \left( 1\right) ,\left( 2\right) と\rightarrow 除去 \\
\left( 4\right) & C & \left[ 1\right] & \left( 3\right) と\wedge 除去 \\
\left( 5\right) & \lnot C & \quad & 前提 \\
\left( 6\right) & \bot & \left[ 1\right] & \left( 4\right) ,\left( 5\right) と\lnot 除去 \\
\left( 7\right) & A\rightarrow \bot & \quad & \left( 1\right) ,\left( 6\right) と\rightarrow 導入 \\
\left( 8\right) & \lnot A & \quad & \left( 7\right) と\lnot 導入
\end{array}$$
について考えます。条件付き証明を利用します。つまり、もともとの前提である\(A\rightarrow \left( B\wedge C\right) \)と\(\lnot C\)が真であることに加えて、結論\(\lnot A\)の否定である\(A\)が真であることを仮定して議論を始めるということです。1行目の論理式\(\left( 1\right) \)の右側に記された\(\left[ 1\right] \)は、\(\left( 1\right) \)が前提ではなく仮定であることを表す記号です。\(\left(2\right) \)と\(\left( 5\right) \)は推論の前提であり仮定ではないため、それらの右側に\(\left[ 2\right] \)や\(\left[ 5\right] \)を記す必要はありません。さて、\(\left( 1\right) \)と\(\left( 2\right) \)に含意除去を適用すると\(\left( 3\right) \)が得られるため、\(\left( 1\right) \)と\(\left( 2\right) \)が真の場合には\(\left( 3\right) \)もまた真であることが保証されます。ただし、\(\left( 3\right) \)が依拠する\(\left( 1\right) \)は前提ではなく仮定であるため、そのことを明示するために\(\left( 3\right) \)の右側に\(\left[ 1\right] \)と記しています。\(\left( 3\right) \)に連言除去を適用すると\(\left( 4\right) \)が得られるため、\(\left( 3\right) \)が真の場合には\(\left( 4\right) \)もまた真であることが保証されます。ただし、\(\left( 3\right) \)は仮定\(\left( 1\right) \)に依拠するため、\(\left( 3\right) \)に依拠する\(\left( 4\right) \)もまた仮定\(\left( 1\right) \)に依拠します。そのことを明示するために\(\left( 4\right) \)の右側に\(\left[ 1\right] \)と記しています。\(\left( 5\right) \)は前提です。\(\left( 4\right) \)と\(\left( 5\right) \)に否定除去を適用すると\(\left( 6\right) \)が得られるため、\(\left( 4\right) \)と\(\left( 5\right) \)が真の場合には\(\left( 6\right) \)もまた真であることが保証されます。ただし、\(\left( 4\right) \)は仮定\(\left( 1\right) \)に依拠するため、\(\left( 4\right) \)に依拠する\(\left( 6\right) \)もまた仮定\(\left( 1\right) \)に依拠します。このことを明示するために\(\left( 6\right) \)の右側に\(\left[ 1\right] \)と記しています。ここからが重要です、これまでの議論により、\begin{equation*}\left( 1\right) ,\left( 2\right) ,\left( 5\right) \ \models \ \left(
6\right)
\end{equation*}すなわち、\begin{equation*}
A,\ A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \models \ \bot
\end{equation*}が成り立つことが示されました。ただ、先の命題より、この推論規則は、\begin{equation*}
A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \models \ \lnot A
\end{equation*}と必要十分であることが保証されますが、これは目標の推論規則に他なりません。したがって証明が完了しました。最後のプロセスを\(\left( 7\right) ,\left(8\right) \)のように理解することもできます。

例(背理法)
整数\(z\)が素数であることとは、\(z>1\)であるとともに、\(z\)の約数が\(1\)と\(z\)だけであることを意味します。以上を踏まえた上で、素数が無限個存在することを証明します。命題変数\(P\)を、\begin{equation*}P:\text{素数が無限個存在する}
\end{equation*}と定義したとき、以下の推論規則\begin{equation*}
\models \ P
\end{equation*}が成り立つことを示すことが目標になりますが、背理法より、\begin{equation*}
\lnot P\ \models \ \bot
\end{equation*}が成り立つことを示しても構いません。そこで、\(\lnot P\)が真であると仮定します。つまり、素数が有限\(n\)個であることを仮定するということです。これらの素数を、\begin{equation*}p_{1},p_{2},\cdots ,p_{n}
\end{equation*}と表記します。素数は整数であり、整数どうしの和と積は整数であるため、\begin{equation*}
z=p_{1}\cdot p_{2}\cdot \cdots \cdot p_{n}+1
\end{equation*}は整数です。\(z\)を\(p_{1}\)で割ると\(1\)余るため、\(p_{1}\)は\(z\)の約数ではありません。同様に、\(p_{2},\cdots ,p_{n}\)はいずれも\(z\)の約数ではありません。したがって、\begin{equation*}Q:z\text{は素数の役数を持たない}
\end{equation*}が真です。また、\(z\)は\(1\)よりも大きい整数であるため、これは何らかの素数を約数として持ちます(確認してください)。したがって、\begin{equation*}\lnot Q:z\text{は素数の役数を持つ}
\end{equation*}もまた真です。\(Q\)と\(\lnot Q\)がともに真であるため、\(\wedge \)導入より\(Q\wedge \lnot Q\)は真であり、さらに\(\lnot \)除去より\(\bot \)を得ます。したがって目標が達成されました。

 

演習問題

問題(背理法)
論理式\(A\)に関する以下の推論規則\begin{equation*}A\rightarrow \lnot A\ \models \ \lnot A
\end{equation*}が妥当であることを証明してください。

証明

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

問題(背理法)
論理式\(A,B,C\)に関する以下の推論規則\begin{equation*}A\rightarrow \lnot B,\ A\rightarrow C,\ C\rightarrow B\ \models \ \lnot A
\end{equation*}が妥当であることを証明してください。

証明

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

問題(背理法)
論理式\(A,B,C,D\)に関する以下の推論規則\begin{equation*}\left( \lnot B\vee C\right) \rightarrow A,\ B\rightarrow D,\ C\vee \lnot D\
\therefore A
\end{equation*}が妥当であることを証明してください。

証明

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

問題(背理法)
論理式\(A\)に関する以下の推論規則\begin{equation*}A\ \models \ \lnot \lnot A
\end{equation*}は二重否定導入であるため妥当ですが、二重否定導入が妥当であることを背理法を用いて証明してください。

証明

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

問題(背理法)
論理式\(A\)に関する以下の推論規則\begin{equation*}\models \ A\vee \lnot A
\end{equation*}は排中律であるため妥当ですが、排中律が妥当であることを背理法を用いて証明してください。

証明

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

次回は対偶法について学びます。

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

質問とコメント

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

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

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

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

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

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

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

命題論理