証明
論理式\(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）などと呼びます。
\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）などと呼びます。
- 最後の論理式\(\alpha _{m}\)は推論の結論\(B\)と一致する。つまり、\(\alpha _{m}=B\)が成り立つ。
- それぞれの\(i\ (1\leq i\leq m)\)について以下のどちらかが成り立つ：
- 論理式\(\alpha _{i}\)は前提\(A_{1},\cdots ,A_{n}\)の中のいずれかである。
- 論理式\(\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\)が恒等式であることに他なりません。
&&\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}$$
&&\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}$$
\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*}が成り立つことが示されました。
推論が妥当でないことの証明
推論の証明を見つけられないからといって証明が存在しないことにはなりません。推論の証明を見つけられないことは、その推論が妥当でないことを必ずしも意味しません。推論が妥当でないことを示すためには、前提がすべて真である一方で結論が偽になるような解釈を具体的に提示したり、証明が存在しないことを具体的に示す必要があります。
&&\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*}と定式化されます。例えば、「太郎」がある犬の名前である場合、前提はともに真であるにも関わらず結論は偽であるため、この推論は妥当ではありません。
演習問題
次回は条件付き証明について学びます。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】