否定導入
論理式\(A\)と恒偽式\(\bot \)を任意に選んだとき、以下の推論規則\begin{equation*}A\rightarrow \bot \ \models \ \lnot A
\end{equation*}が成り立ちます。つまり、\(A\rightarrow \bot \)が真であるような任意の解釈のもとで\(\lnot A\)は必ず真になります。言い換えると、\(A\)から恒偽式が導かれる場合には\(A\)の否定が導かれます。これは否定導入（negation introduction）と呼ばれる推論規則です。
\end{equation*}が成り立つ。
否定導入\begin{equation}
A\rightarrow \bot \ \models \ \lnot A \quad \cdots (1)
\end{equation}は推論規則であるため、\(\left( 1\right) \)を構成する\(A,\bot \)にそれぞれどのような具体的な論理式\(\alpha \)および恒偽式\(\phi \)を入れた場合においても、\begin{equation*}\alpha \rightarrow \phi \ \models \ \lnot \alpha
\end{equation*}が成り立ちます。つまり、論理式\(\alpha \)から何らかの恒偽式\(\phi \)が導かれる場合には\(\alpha \)が偽になることが保証されます。
\end{equation*}が成り立ちます。つまり、命題関数\(P\left( x\right) \)から恒偽式\(\bot \)が導かれる場合には\(P\left( x\right) \)の否定が導かれます。
\end{equation*}と以下の恒偽式\begin{equation*}
R\left( x\right) \wedge \lnot R\left( x\right)
\end{equation*}に注目すると、否定導入より、\begin{equation*}
\left( P\left( x\right) \rightarrow Q\left( x\right) \right) \rightarrow
\left( R\left( x\right) \wedge \lnot R\left( x\right) \right) \ \models \
\lnot \left( P\left( x\right) \rightarrow Q\left( x\right) \right)
\end{equation*}が成り立ちます。つまり、論理式\(P\left( x\right)\rightarrow Q\left( x\right) \)から恒偽式\(R\left( x\right) \wedge \lnot R\left( x\right) \)が導かれる場合には\(P\left( x\right)\rightarrow Q\left( x\right) \)の否定が導かれます。
\forall x\in X:\lnot P\left( x\right)
\end{equation*}が妥当であることを示します。以下の同値変形\begin{equation*}
\forall x\in X:\lnot P\left( x\right) \Leftrightarrow \lnot \left( \exists
x\in X:P\left( x\right) \right)
\end{equation*}が可能であるため、先の推論を、\begin{equation*}
\left( \exists x\in X:P\left( x\right) \right) \rightarrow \bot \ \models \
\lnot \left( \exists x\in X:P\left( x\right) \right)
\end{equation*}と表現できます。存在命題\begin{equation*}
\exists x\in X:P\left( x\right)
\end{equation*}は論理式であるため、否定導入より、先の推論は妥当です。
\text{和が奇数になるような2つの偶数が存在する}
\end{equation*}すべての偶数からなる集合を\(E\)で、すべての奇数からなる集合を\(O\)で表記する場合、上の主張を、\begin{equation}\exists e_{1}\in E,\ \exists e_{2}\in E:e_{1}+e_{2}\in O \quad \cdots (1)
\end{equation}と表現できます。偶数は何らかの整数の\(2\)倍として表現できるため、すべての整数からなる集合を\(\mathbb{Z} \)で表記する場合、上の命題は、\begin{equation*}\exists z_{1}\in \mathbb{Z} ,\ \exists z_{2}\in \mathbb{Z} :2z_{1}+2z_{2}\in O
\end{equation*}すなわち、\begin{equation*}
\exists z_{1}\in \mathbb{Z} ,\ \exists z_{2}\in \mathbb{Z} :2\left( z_{1}+z_{2}\right) \in O
\end{equation*}と必要十分です。整数どうしの和\(z_{1}+z_{2}\)は整数であり、整数の2倍\(2\left( z_{1}+z_{2}\right) \)は整数であるため、上の命題は偽です。したがって否定導入より、\(\left( 1\right) \)の否定\begin{equation*}\lnot \left( \exists e_{1}\in E,\ \exists e_{2}\in E:e_{1}+e_{2}\in O\right)
\end{equation*}が導かれます。これは以下の命題\begin{equation*}
\forall e_{1}\in E,\ \forall e_{2}\in E:e_{1}+e_{2}\not\in O
\end{equation*}すなわち、\begin{equation*}
\forall e_{1}\in E,\ \forall e_{2}\in E:e_{1}+e_{2}\in E
\end{equation*}と必要十分です。したがって、任意の2つの偶数の和は偶数であることが明らかになりました。
背理法
任意の論理式\(A_{1},\cdots ,A_{n},B\)に関する以下の推論\begin{equation}A_{1},\cdots ,\ A_{n}\ \therefore \ B \quad \cdots (1)
\end{equation}が妥当であることを示そうとしている状況を想定します。このとき、以下の推論\begin{equation}
A_{1},\cdots ,\ A_{n},\ \lnot B\therefore \ \bot \quad \cdots (2)
\end{equation}が妥当であることを示すことに成功したとします。すると含意導入より、以下の推論\begin{equation*}
A_{1},\cdots ,\ A_{n}\ \therefore \ \lnot B\rightarrow \bot
\end{equation*}もまた妥当です。最後の推論の結論\(\lnot B\rightarrow\bot \)が真であるとき、否定導入より\(\lnot \lnot B\)すなわち\(B\)が真であるため、このとき、\begin{equation*}A_{1},\cdots ,\ A_{n}\ \models \ B
\end{equation*}が成り立ちます。つまり、当初の推論\(\left(1\right) \)が妥当であるということです。
以上の理由により、推論\(\left( 1\right) \)が妥当であることを示す代わりに、推論\(\left( 2\right) \)が妥当であることを示しても問題ありません。つまり、推論\(\left( 1\right) \)の妥当性を示すためには、\(\left( 1\right) \)の結論\(B\)を前提に加えた上で、そこから恒偽式を導けばよいということです。このような手法を背理法（proof by contradiction）と呼びます。背理法については場を改めて詳しく解説します。
\end{equation*}について考えます。背理法より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
A\rightarrow \left( B\wedge C\right) ,\ \lnot C,\ \lnot \lnot A\ \therefore
\ \bot
\end{equation*}の妥当性を示しても問題ありません。\(A\rightarrow \left( B\wedge C\right) \)と\(\lnot C\)と\(\lnot \lnot A \)がいずれも真であるものとします。\(\lnot \lnot A\)が真であるとき、二重否定除去より\(A\)は真です。\(A\)と\(A\rightarrow \left( B\wedge C\right) \)が真であるとき、含意除去より\(B\wedge C\)が真です。\(B\wedge C\)が真であるとき、連言除去より\(C\)は真です。\(C\)と\(\lnot C\)が真であるとき、否定除去より\(\bot \)が導かれます。したがって、もとの推論が妥当であることが示されました。つまり、\begin{equation*}A\rightarrow \left( B\wedge C\right) ,\ \lnot C\ \models \ \lnot A
\end{equation*}が成り立ちます。
演習問題
\end{equation*}が成り立つことを示してください。
\end{equation*}が成り立つことは二重否定導入より明らかですが、二重否定導入を使わずに上の推論規則が成り立つことを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】