WIIS

述語論理

述語論理における証明

目次

関連知識

Mailで保存
Xで共有

証明

論理式\(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歳になると誰でも運転免許を取得できます。したがって、このクラスには運転免許を持っている生徒がいる可能性があります。」という推論は妥当でしょうか。議論してください。

解答を見る

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

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

解答を見る

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

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

証明

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

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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