否定除去
論理式\(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
\end{equation*}は推論規則であるため、\(A,\bot \)にそれぞれどのような具体的な論理式\(\alpha \)および恒偽式\(\phi \)を入れた場合においても、\begin{equation*}\alpha ,\ \lnot \alpha \ \models \ \phi
\end{equation*}が成り立ちます。つまり、任意の論理式\(\alpha \)とその否定\(\lnot \alpha \)から任意の恒偽式\(\phi \)を導くことができます。同時に、否定除去は\(\alpha \)または\(\lnot \alpha \)の少なくとも一方が偽であることを保証します。なぜなら、仮に\(\alpha \)と\(\lnot \alpha \)がともに真である場合、否定除去より\(\phi \)が真であることが導き出されますが、これは\(\phi \)が恒偽式であることと矛盾だからです。
例（否定除去）
命題変数\(P\)と命題定数\(F\)を任意に選びます。命題変数\(P\)は論理式であり、命題定数\(F\)は恒偽式であるため、否定除去より、\begin{equation*}P,\ \lnot P\ \models \ F
\end{equation*}が成り立ちます。つまり、命題変数\(P\)とその否定\(\lnot P\)から命題定数\(F\)を導くことができます。同時にこれは、\(P\)または\(\lnot P\)の少なくとも一方が偽であることも意味します。
\end{equation*}が成り立ちます。つまり、命題変数\(P\)とその否定\(\lnot P\)から命題定数\(F\)を導くことができます。同時にこれは、\(P\)または\(\lnot P\)の少なくとも一方が偽であることも意味します。
例（否定除去）
命題変数\(P,Q,R\)を任意に選びます。以下の論理式\begin{equation*}P\rightarrow Q
\end{equation*}と以下の恒偽式\begin{equation*}
R\wedge \lnot R
\end{equation*}に注目すると、含意除去より、\begin{equation*}
\left( P\rightarrow Q\right) ,\ \lnot \left( P\rightarrow Q\right) \ \models
\ R\wedge \lnot R
\end{equation*}が成り立ちます。つまり、論理式\(P\rightarrow Q\)とその否定\(P\rightarrow Q\)から恒偽式\(R\wedge \lnot R\)を導くことができます。同時にこれは、\(P\rightarrow Q\)または\(\lnot \left( P\rightarrow Q\right) \)の少なくとも一方が偽であることも意味します。
\end{equation*}と以下の恒偽式\begin{equation*}
R\wedge \lnot R
\end{equation*}に注目すると、含意除去より、\begin{equation*}
\left( P\rightarrow Q\right) ,\ \lnot \left( P\rightarrow Q\right) \ \models
\ R\wedge \lnot R
\end{equation*}が成り立ちます。つまり、論理式\(P\rightarrow Q\)とその否定\(P\rightarrow Q\)から恒偽式\(R\wedge \lnot R\)を導くことができます。同時にこれは、\(P\rightarrow Q\)または\(\lnot \left( P\rightarrow Q\right) \)の少なくとも一方が偽であることも意味します。
例（否定除去）
以下の推論について考えます。\begin{eqnarray*}
&&\text{私は人間であるとともに人間ではない} \\
&&\text{ゆえに、私は犬であるとともに犬ではない}
\end{eqnarray*}命題変数\(P,Q\)を、\begin{eqnarray*}P &:&\text{私は人間である} \\
Q &:&\text{私は犬である}
\end{eqnarray*}とおくと、先の推論は、\begin{equation*}
P\wedge \lnot P\ \therefore \ Q\wedge \lnot Q
\end{equation*}と定式化されます。命題変数\(P\)は論理式であり、論理式\(Q\wedge \lnot Q\)は恒偽式であるため、否定除去より、この推論は妥当です。
&&\text{私は人間であるとともに人間ではない} \\
&&\text{ゆえに、私は犬であるとともに犬ではない}
\end{eqnarray*}命題変数\(P,Q\)を、\begin{eqnarray*}P &:&\text{私は人間である} \\
Q &:&\text{私は犬である}
\end{eqnarray*}とおくと、先の推論は、\begin{equation*}
P\wedge \lnot P\ \therefore \ Q\wedge \lnot Q
\end{equation*}と定式化されます。命題変数\(P\)は論理式であり、論理式\(Q\wedge \lnot Q\)は恒偽式であるため、否定除去より、この推論は妥当です。
演習問題
問題（否定除去）
否定除去とは、任意の論理式\(A\)と恒偽式\(\bot \)に対して、\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}が成り立つという推論規則です。本文中では否定除去が成り立つことを真理値を用いて示しましたが、同じことを同値変形で示してください。
\end{equation*}が成り立つという推論規則です。本文中では否定除去が成り立つことを真理値を用いて示しましたが、同じことを同値変形で示してください。
問題（否定除去を利用した証明）
論理式\(A,B\)と恒偽式\(\bot \)に関する以下の推論\begin{equation*}A\rightarrow B,\ \lnot B\ \therefore \ A\rightarrow \bot
\end{equation*}が妥当であることを示してください。
\end{equation*}が妥当であることを示してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。