命題論理における否定導入

否定導入

論理式\(A\)と恒偽式\(\bot \)を任意に選んだとき、以下の推論規則\begin{equation*}\left( A\rightarrow \bot \right) \ \models \ \lnot A
\end{equation*}が成り立ちます。つまり、\(A\rightarrow \bot \)が真であるような任意の解釈のもとで\(\lnot A\)は必ず真になります。言い換えると、\(A\)から恒偽式が導かれる場合には\(A\)の否定が導かれます。これは否定導入（negation introduction）と呼ばれる推論規則です。

否定導入\begin{equation}
\left( A\rightarrow \bot \right) \ \models \ \lnot A \quad \cdots (1)
\end{equation}は推論規則であるため、\(\left( 1\right) \)を構成する\(A,\bot \)にそれぞれどのような具体的な論理式\(\alpha \)および恒偽式\(\phi \)を入れた場合においても、\begin{equation*}\left( \alpha \rightarrow \phi \right) \ \models \ \lnot \alpha
\end{equation*}が成り立ちます。つまり、論理式\(\alpha \)から何らかの恒偽式\(\phi \)が導かれる場合には\(\alpha \)が偽になることが保証されます。

背理法

任意の論理式\(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）と呼びます。背理法については場を改めて詳しく解説します。

演習問題