教材一覧
教材検索
PREDICATE LOGIC

述語論理における証明

目次

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

証明

論理式\(A_{1},\cdots ,A_{n},B\)に関する以下の推論\begin{equation*}A_{1},\cdots ,A_{n}\ \therefore \ B
\end{equation*}の妥当性を示すために、前提\(A_{1},\cdots ,A_{n}\)を出発点として、これまで学んだ同値変形の法則や推論規則を用いて結論を次々に導出し、最終的に結論\(B\)を導出する手法を証明(proof)や演繹(deduction)などと呼びます。

例(証明)
以下の推論\begin{equation*}
\text{全員が幸せならば、誰かが幸せである}
\end{equation*}は妥当でしょうか。変数\(x\)の定義域\(X\)はすべての人間からなる集合であるものとし、命題関数\(P\left( x\right) \)を、\begin{equation*}x\text{は幸せである}
\end{equation*}と定義すると、与えられた推論は、\begin{equation*}
\forall x\in X:P\left( x\right) \ \therefore \ \exists x\in X:P\left(
x\right)
\end{equation*}と定式化されます。この推論が妥当であることを示すためには、前提\(\forall x\in X:P\left( x\right) \)が真である場合には結論\(\exists x\in X:P\left( x\right) \)もまた真であることを示す必要があります。そこで、以下の論理式の列
$$\begin{array}{lll}\left( 1\right) & \forall x\in X:P\left( x\right) & 前提
\\
\left( 2\right) & P\left( c\right) & \left( 1\right) と\forall 除去 \\
\left( 3\right) & \exists x\in X:P\left( x\right) & \left( 2\right) と\exists 導入
\end{array}$$について考えます。\(\left( 1\right) \)は推論の前提であり、以降ではこれが真である場合を想定します。\(\left( 1\right) \)に全称除去を適用すると\(\left( 2\right) \)が得られるため、\(\left( 1\right) \)が真の場合には\(\left( 2\right) \)が真であることが保証されます。さらに、\(\left( 2\right) \)に存在導入を適用すると\(\left(3\right) \)が得られるため、\(\left( 2\right) \)が真の場合には\(\left( 3\right) \)が真であることが保証されます。したがって、\(\left( 1\right) \)が真の場合には\(\left( 3\right) \)が真であることが保証されるため与えられた推論は妥当であり、\begin{equation*}\forall x\in X:P\left( x\right) \ \models \ \exists x\in X:P\left( x\right)
\end{equation*}が成り立つことが示されました。

 

証明のフォーマルな定義

議論を一般化しましょう。前提が\(A_{1},\cdots ,A_{n}\)であり結論が\(B\)であるような推論に対して、以下の条件を満たす論理式の有限な列\(\alpha_{1},\cdots ,\alpha _{m}\)が存在する場合には、これを前提\(A_{1},\cdots ,A_{n}\)から結論\(B\)への証明(proof)や演繹(deduction)などと呼びます。

  1. 最後の論理式\(\alpha _{m}\)は推論の結論\(B\)と一致する。つまり、\(\alpha _{m}=B\)が成り立つ。
  2. それぞれの\(i\ (1\leq i\leq m)\)について以下のどちらかが成り立つ:
    1. 論理式\(\alpha _{i}\)は前提\(A_{1},\cdots ,A_{n}\)の中のいずれかである。
    2. 論理式\(\alpha _{i}\)はそれより前にある論理式に同値変形の法則や推論規則を適用して得られるものである。

前提\(A_{1},\cdots ,A_{n}\)から結論\(B\)への証明が存在する場合には\(A_{1},\cdots ,A_{n}\)から\(B\)が証明可能(provable)であると言います。先の例のように、証明\(\alpha _{1},\cdots ,\alpha _{m}\)を構成する個々の論理式の番号を明示的に表現したい場合には、

$$\begin{array}{ll}\left( 1\right) & \alpha _{1} \\
\cdots & \cdots \\
\left( m\right) & \alpha _{m}
\end{array}$$と表記します。

前提\(A_{1},\cdots ,A_{n}\)から結論\(B\)が証明可能である場合、証明の定義より、\(A_{1},\cdots ,A_{n}\)がいずれも真である場合には\(B\)もまた必ず真になります。すなわち、推論は妥当であるため、推論規則\begin{equation*}A_{1},\cdots ,A_{n}\ \models \ B
\end{equation*}が成り立ちます。特に、推論に前提が存在しない場合には、結論\(B\)は証明可能であると言い、このことを、\begin{equation*}\models \ B
\end{equation*}で表します。これは\(B\)が恒等式であることに他なりません。

例(証明)
以下の推論\begin{eqnarray*}
&&\text{すべての人間はDNAを持っている} \\
&&\text{太郎は人間である} \\
&&\text{したがって、太郎はDNAを持っている}
\end{eqnarray*}は妥当でしょうか。変数\(x\)の定義域\(X\)はすべての対象からなる集合であるものとし、以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は人間である}
\\
Q\left( x\right) &:&x\text{はDNAを持っている}
\end{eqnarray*}を定義すると、与えられた推論は、\begin{equation*}
\forall x\in X:\left( P\left( x\right) \rightarrow Q\left( x\right) \right)
,\ P\left( \text{太郎}\right) \ \therefore \ Q\left( \text{太郎}\right)
\end{equation*}と定式化されます。この推論が妥当であることは以下の証明から証明可能です。

$$\begin{array}{lll}\left( 1\right) & \forall x\in X:\left( P\left( x\right) \rightarrow Q\left( x\right) \right) & 前提 \\
\left( 2\right) & P\left( \text{太郎}\right) \rightarrow Q\left( \text{太郎}\right) & \left( 1\right) と\forall 除去 \\
\left( 3\right) & P\left( \text{太郎}\right) & 前提 \\
\left( 4\right) & Q\left( \text{太郎}\right) & \left( 2\right) ,\left( 3\right) と\rightarrow 除去
\end{array}$$

例(証明)
以下の推論\begin{eqnarray*}
&&\text{ガレージにある車の中には故障車があった} \\
&&\text{ガレージにある車をすべて売った} \\
&&\text{したがって、売った車の中には故障車がある}
\end{eqnarray*}は妥当でしょうか。変数\(x\)の定義域\(X\)はすべての車からなる集合であるものとし、以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{はガレージの中にある} \\
Q\left( x\right) &:&x\text{は故障車である} \\
R\left( x\right) &:&x\text{を売った}
\end{eqnarray*}をそれぞれ定義すると、与えられた推論は、\begin{equation*}
\exists x\in X:\left[ P\left( x\right) \wedge Q\left( x\right) \right] ,\
\forall x\in X:\left[ P\left( x\right) \rightarrow R\left( x\right) \right] \ \therefore \ \exists x\in X\ \left[ Q\left( x\right) \wedge R\left(
x\right) \right] \end{equation*}と定式化されます。この推論が妥当であることは以下の証明から証明可能です。

$$\begin{array}{lll}\left( 1\right) & \exists x\in X:\left[ P\left( x\right) \wedge Q\left( x\right) \right] & 前提 \\
\left( 2\right) & P\left( c\right) \wedge Q\left( c\right) & \left( 1\right) と\exists 除去 \\
\left( 3\right) & P\left( c\right) & \left( 2\right) と\wedge 除去 \\
\left( 4\right) & \forall x\in X:\left[ P\left( x\right) \rightarrow R\left( x\right) \right] & 前提 \\
\left( 5\right) & P\left( c\right) \rightarrow R\left( c\right) & \left( 4\right) と\forall 除去 \\
\left( 6\right) & R\left( c\right) & \left( 3\right) ,\left( 5\right) と\rightarrow 除去 \\
\left( 7\right) & Q\left( c\right) & \left( 2\right) と\wedge 除去 \\
\left( 8\right) & Q\left( c\right) \wedge R\left( c\right) & \left( 6\right) ,\left( 7\right) と\wedge 導入 \\
\left( 9\right) & \exists x\in X:\left[ Q\left( x\right) \wedge R\left( x\right) \right] & \left( 8\right) と\exists 導入
\end{array}$$

例(証明)
以下の推論\begin{equation*}
\text{任意の自然数}x\text{について、}2x+1\text{は奇数である}
\end{equation*}は妥当でしょうか。変数\(x\)の定義域\(X\)はすべての自然数からなる集合であるものとし、以下の命題関数\begin{equation*}P\left( x\right) :2x+1\text{は奇数である}
\end{equation*}を定義すると、与えられた推論は、\begin{equation*}
\therefore \ \forall x\in X:P\left( x\right)
\end{equation*}と定式化されます。自然数\(c\)を任意に選んだとき、\(2c+1\)は奇数であるため、\begin{equation*}P\left( c\right)
\end{equation*}が成り立ちます。すると\(\forall \)導入より、\begin{equation*}\forall x\in X:P\left( x\right)
\end{equation*}が成り立つため、与えられた推論は妥当であること、すなわち、\begin{equation*}
\models \ \forall x\in X:P\left( x\right)
\end{equation*}が成り立つことが示されました。

 

推論が妥当でないことの証明

推論の証明を見つけられないからといって証明が存在しないことにはなりません。推論の証明を見つけられないことは、その推論が妥当でないことを必ずしも意味しません。推論が妥当でないことを示すためには、前提がすべて真である一方で結論が偽になるような解釈を具体的に提示したり、証明が存在しないことを具体的に示す必要があります。

例(証明)
以下の推論\begin{eqnarray*}
&&\text{すべての人間はDNAを持っている} \\
&&\text{太郎はDNAを持っている} \\
&&\text{したがって、太郎は人間である}
\end{eqnarray*}は妥当でしょうか。変数\(x\)の定義域\(X\)はすべての対象からなる集合であるものとし、以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は人間である}
\\
Q\left( x\right) &:&x\text{はDNAを持っている}
\end{eqnarray*}を定義すると、与えられた推論は、\begin{equation*}
\forall x\in X:\left( P\left( x\right) \rightarrow Q\left( x\right) \right)
,\ Q\left( \text{太郎}\right) \ \therefore \ P\left( \text{太郎}\right)
\end{equation*}と定式化されます。例えば、「太郎」がある犬の名前である場合、前提はともに真であるにも関わらず結論は偽であるため、この推論は妥当ではありません。

 

演習問題

問題(証明)
「太郎は18歳でこのクラスの生徒です。18歳になると誰でも運転免許を取得できます。したがって、このクラスには運転免許を持っている生徒がいる可能性があります。」という推論は妥当でしょうか。議論してください。

解答を見る

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

問題(証明)
「このクラスの生徒は皆パソコンを持っています。パソコンを持っている人は皆インターネットを使えます。したがって、このクラスの生徒である太郎はインターネットを使えます。」という推論は妥当でしょうか。議論してください。

解答を見る

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

問題(証明)
「誰かの親である人ならば誰しも、自分自身の子供の子供にはなり得ない。したがって、誰しもが自身の親ではない。」という推論は妥当でしょうか。議論してください。

証明

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

次回は条件付き証明について学びます。

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

関連知識

証明

命題論理における証明

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

条件付き証明

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

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

対偶律

命題論理における対偶法

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

消去法

命題論理における消去法

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

条件付き証明

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

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

条件付き証明

述語論理における背理法

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

対偶律

述語論理における対偶法

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

消去法

述語論理における消去法

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

DISCUSSION

質問とコメント

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

述語論理