教材一覧
教材一覧
教材検索
PROPOSITIONAL LOGIC

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

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

否定導入

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

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

表:否定導入

上の真理値表より、任意の解釈において\(\left( A\rightarrow \bot \right) \rightarrow \lnot A\)の値が\(1\)であることが確認できるため、以下の推論規則\begin{equation*}\left( A\rightarrow \bot \right) \ \models \ \lnot A
\end{equation*}を得ます。つまり、\(A\rightarrow \bot \)が真であるような任意の解釈のもとで\(\lnot A\)は必ず真になります。これは否定導入(negation introduction)と呼ばれる推論規則です。

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

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

 

背理法

論理式\(A_{1},\cdots ,A_{n},B\)をそれぞれ任意に選んだ上で、以下の推論\begin{equation}A_{1},\cdots ,\ A_{n}\ \therefore \ B \quad \cdots (1)
\end{equation}が妥当であることを示すことが目標であるものとします。このとき、以下の推論\begin{equation}
A_{1},\cdots ,\ A_{n},\ \lnot B\therefore \ \bot \quad \cdots (2)
\end{equation}が妥当であることを示すことに成功したとします。すると含意導入より、以下の推論\begin{equation*}
A_{1},\cdots ,\ A_{n}\ \therefore \ \lnot B\rightarrow \bot
\end{equation*}もまた妥当です。最後の推論の結論\(\lnot B\rightarrow\bot \)が真であるとき、否定導入より\(\lnot \lnot B\)すなわち\(B\)が真であるため、このとき、\begin{equation*}A_{1},\cdots ,\ A_{n}\ \models \ B
\end{equation*}が成り立ちます。つまり、当初の推論\(\left(1\right) \)が妥当であるということです。

議論を整理すると、推論\(\left( 1\right) \)が妥当であることを示す代わりに、推論\(\left( 2\right) \)が妥当であることを示しても問題ありません。つまり、推論\(\left( 1\right) \)の妥当性を示すためには、\(\left( 1\right) \)の結論\(B\)を前提に加えた上で、そこから恒偽式を導けばよいということです。このような手法を背理法(proof by contradiction)と呼びます。背理法については場を改めて詳しく解説します。

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

 

演習問題

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

解答を見る

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

問題(背理法)
任意の論理式\(A\)について、\begin{equation*}A\rightarrow \lnot A\ \models \ \lnot A
\end{equation*}が成り立つことを示してください。

解答を見る

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

問題(背理法)
任意の論理式\(A\)について、\begin{equation*}A\ \models \ \lnot \lnot A
\end{equation*}が成り立つことは二重否定導入より明らかですが、二重否定導入を使わずに上の推論規則が成り立つことを示してください。

解答を見る

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

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

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

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

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

否定
命題論理における否定除去

論理式 A とその否定 ¬A がともに真である場合には恒偽式が導かれます。これは否定除去と呼ばれる推論規則です。

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

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

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

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

命題論理