論理式\(A_{1},\cdots ,A_{n}\)が前提であり、結論が論理式\(B,C\)の論理和で表される推論が与えられたとき、\(A_{1},\cdots ,A_{n}\)に加えて\(\lnot B\)が真であるということを出発点として\(C\)が真であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法と呼びます。

消去法

まず、以下の命題が成り立ちます。

命題(消去法の根拠)
任意の論理式\(A_{1},\cdots ,A_{n},B,C\)に対して以下が成り立つ。\begin{equation*}
\left( \bigwedge_{i=1}^{n}A_{i}\right) \rightarrow \left( B\vee C\right) \Leftrightarrow \left( \left( \bigwedge_{i=1}^{n}A_{i}\right) \wedge \lnot B\right) \rightarrow C
\end{equation*}
証明を見る(プレミアム会員限定)

論理式\(A_{1},\cdots ,A_{n}\)が前提であり、結論が論理式\(B,C\)の論理和で表される推論\begin{equation*}
A_{1},\cdots ,\ A_{n}\ \therefore \ B\vee C
\end{equation*}が与えられたとき、これを示す方法の 1 つは以下の論理式\begin{equation*}
\left( \bigwedge_{i=1}^{n}A_{i}\right) \rightarrow \left( B\vee C\right)
\end{equation*}が恒真であることを示すというものですが、上の命題より、これは以下の論理式\begin{equation*}
\left( \left( \bigwedge_{i=1}^{n}A_{i}\right) \wedge \lnot B\right) \rightarrow C
\end{equation*}と論理的に同値です。したがって、以下の推論\begin{equation*}
A_{1},\cdots ,\ A_{n},\lnot B\ \therefore \ C
\end{equation*}が妥当であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法(proof by elimination)と呼びます。

例(消去法)
実数\(x\)について、\(x=x^{2}\)が成り立つ場合には\(x=0\)または\(x=1\)であることを証明します。消去法より、実数\(x\)について、\(x=x^{2}\)かつ\(x\not=0\)が成り立つ場合には\(x=1\)であることを示してもかまいません。\(x\not=0\)ですので\(x=x^{2}\)の両辺を\(x\)で割ることができるため\(1=x\)を得ます。したがって証明が完了しました。

次回は場合分けについて学びます。
次へ進む 演習問題(プレミアム会員限定)