WIIS

述語論理

述語論理における二重否定除去

目次

Mailで保存
Xで共有

二重否定除去

論理式\(A\)を任意に選んだときに、\begin{equation*}\lnot \lnot A\Rightarrow A
\end{equation*}が成り立つことが示されるため、ここから以下の推論規則を得ます。

命題(二重否定除去)
任意の論理式\(A\)に対して、\begin{equation*}\lnot \lnot A\ \models \ A
\end{equation*}が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

上の命題より、解釈を任意に選んだとき、\(\lnot \lnot A\)から得られる命題が真である場合、\(A\)から得られる命題もまた真になることが保証されます。この推論規則を二重否定除去(double negation elimination)と呼びます。

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

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

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

 

二重否定除去の一般化

二重否定除去より、任意の論理式\(A\)について、\begin{equation*}\lnot \lnot A\ \models \ A
\end{equation*}が成り立ちます。そこで、\(A\)として論理式\(\lnot A\)を採用すれば、\begin{equation*}\lnot \lnot \lnot A\ \models \ \lnot A
\end{equation*}を得ますし、\(A\)として論理式\(\lnot \lnot A\)を採用すれば、\begin{equation*}\lnot \lnot \lnot \lnot A\ \models \ \lnot \lnot A
\end{equation*}を得ます。以降についても同様です。

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録