二重否定導入
論理式\(A\)を任意に選んだとき、以下の推論規則\begin{equation*} A\ \models \ \lnot \lnot A
\end{equation*}が成り立ちます。つまり、\(A\)が真であるような任意の解釈において\(\lnot \lnot A\)は真になります。以上の推論規則を二重否定導入（double negation introduction）と呼びます。
命題（二重否定導入）
任意の論理式\(A\)に対して、\begin{equation*} A\ \models \ \lnot \lnot A
\end{equation*}が成り立つ。
\end{equation*}が成り立つ。
例（二重否定導入）
命題変数\(P\)を任意に選びます。命題変数は論理式であるため、二重否定導入より、\begin{equation*} P\ \models \ \lnot \lnot P
\end{equation*}が成り立ちます。以上の事実は、\(P\)が真である場合には\(\lnot \lnot P\)が真であることを意味します。同時に、\(\lnot \lnot P\)が偽である場合には\(P\)が偽であることも意味します。
\end{equation*}が成り立ちます。以上の事実は、\(P\)が真である場合には\(\lnot \lnot P\)が真であることを意味します。同時に、\(\lnot \lnot P\)が偽である場合には\(P\)が偽であることも意味します。
例（二重否定導入）
命題変数\(P,Q\)を任意に選んだとき、これらの含意\begin{equation*} P\rightarrow Q
\end{equation*}は論理式であるため、二重否定導入より、\begin{equation*}
P\rightarrow Q\ \models \ \lnot \lnot \left( P\rightarrow Q\right)
\end{equation*}が成り立ちます。
\end{equation*}は論理式であるため、二重否定導入より、\begin{equation*}
P\rightarrow Q\ \models \ \lnot \lnot \left( P\rightarrow Q\right)
\end{equation*}が成り立ちます。
例（二重否定導入）
以下の推論について考えます。\begin{eqnarray*}
&&\text{今日は週末である。} \\
&&\text{ゆえに、週末でないことはない。}
\end{eqnarray*}命題変数\(P\)を、\begin{equation*} P:\text{今日は週末である}
\end{equation*}とおくと、先の推論は、\begin{equation*}
P\ \therefore \ \lnot \lnot P
\end{equation*}と定式化されます。二重否定導入よりこれは妥当な推論です。つまり、\begin{equation*}
P\ \models \ \lnot \lnot P
\end{equation*}が成り立つということです。これは\(P\)が真であるような状況において\(\lnot \lnot P\)が必ず真になることを意味します。
&&\text{今日は週末である。} \\
&&\text{ゆえに、週末でないことはない。}
\end{eqnarray*}命題変数\(P\)を、\begin{equation*} P:\text{今日は週末である}
\end{equation*}とおくと、先の推論は、\begin{equation*}
P\ \therefore \ \lnot \lnot P
\end{equation*}と定式化されます。二重否定導入よりこれは妥当な推論です。つまり、\begin{equation*}
P\ \models \ \lnot \lnot P
\end{equation*}が成り立つということです。これは\(P\)が真であるような状況において\(\lnot \lnot P\)が必ず真になることを意味します。
例（二重否定導入）
論理式\(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*}が成り立ちます。
\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\)について、\begin{equation*} A\ \models \ \lnot \lnot A
\end{equation*}が成り立ちます。そこで、\(A\)として論理式\(\lnot A\)を採用すれば、\begin{equation*} \lnot A\ \models \ \lnot \lnot \lnot A
\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*}が成り立つ。
\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*}が成り立ちます。
\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\ \models \ \lnot \lnot A
\end{equation*}が成り立つという推論規則です。本文中では二重否定導入が成り立つことを真理値を用いて示しましたが、同じことを同値変形で示してください。
\end{equation*}が成り立つという推論規則です。本文中では二重否定導入が成り立つことを真理値を用いて示しましたが、同じことを同値変形で示してください。
問題（連言除去との組合せ）
任意の論理式\(A,B\)について、\begin{equation*} A\wedge B\ \models \ \lnot \lnot A
\end{equation*}が成り立つことを示してください。
\end{equation*}が成り立つことを示してください。
問題（選言導入との組合せ）
任意の論理式\(A,B\)について、\begin{equation*} A\ \models \ \lnot \lnot \left( A\vee B\right)
\end{equation*}が成り立つことを示してください。
\end{equation*}が成り立つことを示してください。
問題（選言除去との組合せ）
任意の論理式\(A,B,C\)について、\begin{equation*} A\rightarrow C,\ B\rightarrow C,\ A\vee B\ \models \ \lnot \lnot C
\end{equation*}が成り立つことを示してください。
\end{equation*}が成り立つことを示してください。
問題（二重否定導入）
任意の論理式\(A,B\)について、\begin{equation*} A,\ \lnot \lnot \left( A\wedge B\right) \ \models \ \lnot \lnot A\wedge
\lnot \lnot B
\end{equation*}が成り立つことを示してください。
\lnot \lnot B
\end{equation*}が成り立つことを示してください。
