教材一覧
教材検索
PROPOSITIONAL LOGIC

否定除去

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

否定除去

論理式\(A\)と恒偽式\(\bot \)をそれぞれ任意に選ぶと、否定と論理積および含意の定義より以下の真理値表が得られます。

$$\begin{array}{ccccc}\hline
A & \bot & \lnot A & A\wedge \lnot A & \left( A\wedge \lnot A\right) \rightarrow \bot \\ \hline
1 & 0 & 0 & 0 & 1 \\ \hline
0 & 0 & 1 & 0 & 1 \\ \hline
\end{array}$$

表:否定除去

上の真理値表より、任意の解釈において\(\left( A\wedge \lnot A\right) \rightarrow \bot \)の値が\(1\)であることが確認できるため、以下の推論規則\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}を得ます。つまり、論理式とその否定から恒偽式を導くことができます。この推論規則を否定除去(negation elimination)と呼びます。

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

例(否定除去)
命題定数\(F\)は典型的な恒偽式です。したがって、否定除去より、任意の論理式\(A\)に対して、\begin{equation*}A,\ \lnot A\ \models \ F
\end{equation*}という推論規則が成り立ちます。

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

 

演習問題

問題(否定除去)
繰り返しになりますが、否定除去とは、任意の論理式\(A\)と恒偽式\(\bot \)に対して、\begin{equation*}A,\ \lnot A\ \models \ \bot
\end{equation*}が成り立つという推論規則です。本文中では否定除去が成り立つことを真理値を用いて示しましたが、同じことを同値変形で示してください。

解答を見る

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

次回は否定導入と呼ばれる推論規則について学びます。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE
DISCUSSION

質問とコメント

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

命題論理