述語論理における二重否定導入

任意の論理式\(A\)に対して、\begin{equation*} A\ \models \ \lnot \lnot A
\end{equation*}が成り立つ。

命題関数\(P\left( x\right) \)が任意に与えられたとき、二重否定導入より、\begin{equation*} P\left( x\right) \ \models \ \lnot \lnot P\left( x\right)
\end{equation*}が成り立ちます。

以下の推論について考えます。\begin{eqnarray*}
&&\text{任意の偶数は}2\text{で割り切れる} \\
&&\text{ゆえに、任意の偶数は}2\text{で割り切れないことはない}
\end{eqnarray*}すべての偶数からなる集合\(X\)を定義域とする変数\(x\)に関する以下の命題関数\begin{equation*} P\left( x\right) :x\text{は}2\text{で割り切れる}
\end{equation*}を定義すると、先の推論は、\begin{equation*}
\forall x\in X:P\left( x\right) \ \therefore \ \forall x\in X:\lnot \lnot
P\left( x\right)
\end{equation*}と定式化されます。推論の前提に全称除去を適用すると、\begin{equation*}
P\left( c\right)
\end{equation*}を得ます。これに二重否定導入を適用すると、\begin{equation*}
\lnot \lnot P\left( c\right)
\end{equation*}を得ます。さらにこれに全称導入を適用すると、\begin{equation*}
\forall x\in X:\lnot \lnot P\left( x\right)
\end{equation*}を得るため、推論が妥当であることが示されました。

論理式\(A,B\)に関する以下の推論\begin{equation*} \lnot A\ \therefore \ A\vee B\rightarrow \lnot \lnot B
\end{equation*}について考えます。含意導入より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
\lnot A,\ A\vee B\ \therefore \ \lnot \lnot B
\end{equation*}の妥当性を示しても問題ありません。\(\lnot A\)と\(A\vee B\)がともに真であるものとします。\(\lnot A\)が真であるとき、\(A\)は偽です。また、\(A\vee B\)が真であるとき、\(A\)と\(B\)の少なくとも一方が真です。したがって、\(B\)が真であるため、二重否定導入より\(\lnot \lnot B\)は真であり、先の推論が妥当であることが示されました。つまり、\begin{equation*} \lnot A\ \models \ A\vee B\rightarrow \lnot \lnot B
\end{equation*}が成り立ちます。

論理式\(A\)と番号\(n\in \mathbb{N} \)を任意に選んだ上で、\(A\)の\(n\)重否定を、\begin{equation*} \lnot ^{n}A
\end{equation*}で表記する。このとき、以下の推論規則\begin{equation*}
\left\{
\begin{array}{cc}
\lnot A\ \models \ \lnot ^{n}A & \left( if\ n\text{が奇数}\right) \\
A\ \models \ \lnot ^{n}A & \left( if\ n\text{が偶数}\right)\end{array}\right.
\end{equation*}が成り立つ。

論理式\(A,B\)に関する以下の推論\begin{equation*} \lnot A\ \therefore \ \lnot \left( \lnot \left( A\vee B\right) \right)
\rightarrow \lnot \lnot \lnot \lnot B
\end{equation*}について考えます。含意導入より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
\lnot A,\ \lnot \left( \lnot \left( A\vee B\right) \right) \ \therefore \
\lnot \lnot \lnot \lnot B
\end{equation*}の妥当性を示しても問題ありません。\(\lnot A\)と\(\lnot \left( \lnot \left( A\vee B\right) \right) \)がともに真であるものとします。ド・モルガンの法則より、\begin{eqnarray*} \lnot \left( \lnot \left( A\vee B\right) \right) &\Leftrightarrow &\lnot
\left( \lnot A\wedge \lnot B\right) \\
&\Leftrightarrow &\lnot \lnot A\vee \lnot \lnot B
\end{eqnarray*}という同値変形が可能であるため、\(\lnot \left( \lnot \left( A\vee B\right) \right) \)が真であるとき、\(\lnot \lnot A\)と\(\lnot \lnot B\)の少なくとも一方は真です。ただ、\(\lnot A\)が真であるとき、その否定である\(\lnot \lnot A\)は偽です。したがって\(\lnot \lnot B\)は真であるため、二重否定導入より\(\lnot \lnot \lnot \lnot B\)は真です。以上でもとの推論が妥当であることが示されました。つまり、\begin{equation*} \lnot A\ \models \ \lnot \left( \lnot \left( A\vee B\right) \right)
\rightarrow \lnot \lnot \lnot \lnot B
\end{equation*}が成り立ちます。

論理式\(A\)に関する以下の推論\begin{equation*} A\ \therefore \ \lnot \lnot \left( A\wedge A\right)
\end{equation*}が妥当であることを示してください。

論理式\(A,B\)に関する以下の推論\begin{equation*} A\rightarrow B,\ A\ \therefore \ \lnot \lnot B
\end{equation*}が妥当であることを示してください。

論理式\(A,B,C\)に関する以下の推論\begin{equation*} A,\ B\rightarrow C\ \therefore \ \lnot \lnot A\wedge \left( B\rightarrow
C\right)
\end{equation*}が妥当であることを示してください。

論理式\(A,B,C\)について、以下の推論が妥当であることを示してください。 \begin{equation*}
A\rightarrow B,\ B\rightarrow C,\ A\ \therefore \ \lnot \lnot C
\end{equation*}

論理式\(A,B,C\)について、以下の推論が妥当であることを示してください。 \begin{equation*}
A\rightarrow B\ \models \ A\rightarrow \lnot \lnot B
\end{equation*}

変数\(x\)の定義域を\(X\)とします。以下の推論が妥当であることを示してください。 \begin{equation*}
\forall x\in X:P\left( x\right) \ \therefore \ \forall x\in X:\lnot \lnot
P\left( x\right)
\end{equation*}

変数\(x\)の定義域を\(X\)とします。以下の推論が妥当であることを示してください。 \begin{equation*}
\exists x\in X:P\left( x\right) \ \therefore \ \exists x\in X:\lnot \lnot
P\left( x\right)
\end{equation*}

論理式\(A\)について、以下の推論が妥当であることを示してください。 \begin{equation*}
\lnot A\ \therefore \ \lnot ^{9}A
\end{equation*}

論理式\(A,B,C,D\)について、以下の推論が妥当であることを示してください。 \begin{equation*}
A,\ B\ \therefore \ \lnot \lnot \left( A\vee C\right) \wedge \lnot \lnot
\left( B\vee D\right)
\end{equation*}

論理式\(A,B\)について、以下の推論は妥当でしょうか。判断してください。 \begin{equation*}
\lnot \lnot A\ \therefore \ \lnot \lnot B.
\end{equation*}

変数\(x\)の定義域を\(X\)とします。以下の2つの推論が妥当であることをそれぞれ示してください。 \begin{eqnarray*}
&&\left( a\right) \quad \forall x\in X:P\left( x\right) \ \therefore \ \lnot
\lnot \left( \forall x\in X:P\left( x\right) \right) \\
&&\left( b\right) \quad \forall x\in X:P\left( x\right) \ \therefore \
\forall x\in X:\lnot \lnot P\left( x\right).
\end{eqnarray*}