WIIS

述語論理

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

目次

Mailで保存
Xで共有

否定除去

論理式\(A\)と恒偽式\(\bot \)を任意に選んだとき、以下の推論規則\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}が成り立ちます。つまり、論理式とその否定から恒偽式を導くことができます。この推論規則を否定除去(negation elimination)と呼びます。

命題(否定除去)
論理式\(A\)と恒偽式\(\bot \)を任意に選んだとき、\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}が成り立つ。

証明

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

否定除去\begin{equation}
A,\ \lnot A\ \models \ \bot \quad \cdots (1)
\end{equation}は推論規則であるため、\(\left( 1\right) \)を構成する\(A,\bot \)にそれぞれどのような具体的な論理式\(\alpha \)および恒偽式\(\phi \)を入れた場合においても、\begin{equation*}\alpha ,\ \lnot \alpha \ \models \ \phi
\end{equation*}が成り立ちます。つまり、任意の論理式\(\alpha \)とその否定\(\lnot \alpha \)から任意の恒偽式\(\phi \)を導くことができます。同時に、否定除去\(\left( 1\right) \)は\(\alpha \)と\(\lnot \alpha \)の少なくとも一方が偽であることを保証します。なぜなら、仮に\(\alpha \)と\(\lnot \alpha \)がともに真である場合、否定除去\(\left( 1\right) \)より\(\phi \)が真であることが導き出されますが、実際には\(\phi \)は恒偽式であるため真になり得ず、矛盾だからです。

例(否定除去)
命題関数\(P\left( x\right) \)と恒偽式\(\bot \)をそれぞれ任意に選んだとき、命題変数は論理式であるため、否定除去より、\begin{equation*}P\left( x\right) ,\ \lnot P\left( x\right) \ \models \ \bot
\end{equation*}が成り立ちます。つまり、命題関数\(P\left( x\right) \)とその否定\(\lnot P\left( x\right) \)から任意の恒偽式\(\bot \)を導くことができます。同時にこれは、\(P\left(x\right) \)と\(\lnot P\left( x\right) \)の少なくとも一方が偽であることも意味します。
例(否定除去)
命題関数\(P\left( x\right) \)と恒偽式\(\bot \)をそれぞれ任意に選んだとき、以下の推論\begin{equation*}\forall x\in X:P\left( x\right) ,\ \exists x\in X:\lnot P\left( x\right) \
\therefore \ \bot
\end{equation*}は妥当であることを示します。以下の同値変形\begin{equation*}
\exists x\in X:\lnot P\left( x\right) \Leftrightarrow \lnot \left( \forall
x\in X:P\left( x\right) \right)
\end{equation*}が可能であるため、先の推論を、\begin{equation*}
\forall x\in X:P\left( x\right) ,\ \lnot \left( \forall x\in X:P\left(
x\right) \right) \ \therefore \ \bot
\end{equation*}と表現できます。全称命題\begin{equation*}
\forall x\in X:P\left( x\right)
\end{equation*}は論理式であるため、否定除去より、先の推論は妥当です。

例(否定除去)
以下の推論について考えます。\begin{eqnarray*}
&&\text{すべての人間は男であるとともに男ではない} \\
&&\text{ゆえに、すべての人間は女であるとともに女ではない}
\end{eqnarray*}命題関数\(P\left( x\right) ,Q\left( x\right) \)を、\begin{eqnarray*}P\left( x\right) &:&x\text{は男である} \\
Q\left( x\right) &:&x\text{は女である}
\end{eqnarray*}と定めます。ただし、\(x\)の定義域\(X\)はすべての人間からなる集合です。先の推論は、\begin{equation*}\forall x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right) \right)
\ \therefore \ \forall x\in X:\left( Q\left( x\right) \wedge \lnot Q\left(
x\right) \right)
\end{equation*}と定式化されます。推論の前提\begin{equation*}
\forall x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right) \right)
\end{equation*}が成り立つものとします。全称除去を適用すると、\begin{equation*}
P\left( c\right) \wedge \lnot P\left( c\right)
\end{equation*}を得ます。ただし、\(c\)は変数\(x\)がとり得る「すべての値」を代表的な形で表す記号です。\(P\left( c\right) \)は論理式であるため、否定除去より、ここから任意の恒偽式を導くことができます。推論の結論\begin{equation*}\forall x\in X:\left( Q\left( x\right) \wedge \lnot Q\left( x\right) \right)
\end{equation*}は恒偽式であるため、この結論を導くこともできます。したがって与えられた推論が妥当であることが明らかになりました。

 

演習問題

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

証明

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

問題(否定除去)
以下の推論\begin{eqnarray*}
\forall x &\in &\mathbb{R} :x^{3}\geq 0\wedge \exists x\in \mathbb{R} :x^{3}<0 \\
\ &\therefore &\ \forall x\in \mathbb{R} :\left( x=0\wedge x\not=0\right)
\end{eqnarray*}が妥当であることを示してください。

証明

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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