否定除去
論理式\(A\)と恒偽式\(\bot \)を任意に選んだとき、以下の推論規則\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}が成り立ちます。つまり、論理式とその否定から恒偽式を導くことができます。この推論規則を否定除去(negation elimination)と呼びます。
命題(否定除去)
論理式\(A\)と恒偽式\(\bot \)を任意に選んだとき、\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}が成り立つ。
\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) \)の少なくとも一方が偽であることも意味します。
\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*}は論理式であるため、否定除去より、先の推論は妥当です。
\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*}は恒偽式であるため、この結論を導くこともできます。したがって与えられた推論が妥当であることが明らかになりました。
&&\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*}が妥当であることを示してください。
\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*}が妥当であることを示してください。
\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*}が妥当であることを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】