教材一覧
教材一覧
教材検索
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
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE
否定
述語論理における否定

論理式 A に論理演算子 ¬ を作用させることで得られる ¬A もまた論理式です。¬は否定と呼ばれる論理演算子であり、論理式 ¬A を A の否定と呼びます。

否定
命題論理における否定導入

論理式 A から恒偽式が導かれる場合には ¬A は必ず真になります。これは否定導入と呼ばれる推論規則です。否定導入は背理法と呼ばれる証明方法の根拠になります。

前件否定
命題論理における後件否定

論理式 A,B について、「AならばB」と「Bではない」という前提から「Aではない」という結論を導く推論規則を後件否定やモーダストレンスなどと呼びます。

ド・モルガンの法則
量化記号と否定

述語論理において、全称命題の否定は否定の存在命題と論理的に同値であり、存在命題の否定は否定の全称命題と論理的に同値です。これはド・モルガンの法則の一般化です。

命題論理