述語論理における破壊的ジレンマ

破壊的ジレンマ

論理式\(A,B,C,D\)を任意に選んだとき、以下の推論規則\begin{equation*}A\rightarrow B,\ C\rightarrow D,\ \lnot B\vee \lnot D\ \models \ \lnot A\vee
\lnot C
\end{equation*}が成り立ちます。つまり、\(A\rightarrow B\)と\(C\rightarrow D\)と\(\lnot B\vee \lnot D\)がいずれも真であるような任意の解釈のもとで\(\ \lnot A\vee \lnot C\)は必ず真になります。これは破壊的ジレンマ（destructive dilemma）と呼ばれる推論規則です。

破壊的ジレンマ\begin{equation}
A\rightarrow B,\ C\rightarrow D,\ \lnot B\vee \lnot D\ \models \ \lnot A\vee
\lnot C \quad \cdots (1)
\end{equation}は推論規則であるため、\(\left( 1\right) \)を構成する\(A,B,C,D\)にそれぞれどのような具体的な論理式\(\alpha ,\beta ,\psi ,\delta \)を入れた場合においても、\begin{equation*}\alpha \rightarrow \beta ,\ \psi \rightarrow \delta ,\ \lnot \beta \vee
\lnot \delta \ \models \ \lnot \alpha \vee \lnot \psi
\end{equation*}が成り立ちます。つまり、\(\alpha \rightarrow \beta \)と\(\psi \rightarrow\delta \)と\(\lnot \beta \vee \lnot \delta \)が真である場合には\(\lnot \alpha \vee \lnot\psi \)は真になります。同時に、\(\lnot \alpha \vee \lnot \psi \)が偽である場合には、\(\alpha \rightarrow \beta \)または\(\psi \rightarrow \delta \)または\(\lnot \beta \vee \lnot \delta \)の中の少なくとも1つが偽になることが保証されます。なぜなら、仮にこれらがすべて真である場合、破壊的ジレンマ\(\left( 1\right) \)より\(\lnot \alpha \vee \lnot \psi \)が真であることが導き出されますが、これは\(\lnot \alpha \vee \lnot\psi \)が偽であることと矛盾するからです。