論理式 A と恒偽式 ⊥ について、A→⊥ が真であるような任意の解釈のもとで ¬A は必ず真になります。これは否定導入と呼ばれる推論規則です。
< 前のページ
次のページ >

否定導入

以下の命題が成り立ちます。

命題(否定導入)
任意の論理式\(A\)と恒偽式\(\bot \)に対して以下が成り立つ。\begin{equation*}
\left( A\rightarrow \bot \right) \rightarrow \lnot A
\end{equation*}
証明を見る(プレミアム会員限定)

上の命題より、任意の論理式\(A\)と恒偽式\(\bot \)に関して以下の推論規則\begin{equation*}
A\rightarrow \bot \ \models \ \lnot A
\end{equation*}が成立します。つまり、\(A\rightarrow \bot \)が真であるような任意の解釈のもとで\(\lnot A\)は必ず真になります。これは否定導入(negation introduction)と呼ばれる推論規則です。

例えば、論理式\(A\)が真であるような任意の解釈のもとで論理式\(B\)とその否定\(\lnot B\)がともに成り立つことが示されたとします。しかし、\(B\)と\(\lnot B\)がともに真であることは恒偽ですので、否定導入より前提\(A\)は偽であること、すなわち論理式\(\lnot A\)が真であることを示したことになります。後に解説しますが、これは背理法(proof by contradiction)と呼ばれる証明方法です。

例(否定導入)
変数\(x,y\)が任意の整数を値としてとり得るものとします。その上で、以下の主張\begin{equation*}
18x+6y=1\text{を満たす}x,y\text{が存在しない}
\end{equation*}が成り立つことを示します。見通しをよくするために、論理式\(A\)を、\begin{equation*}
A:18x+6y=1\text{を満たす}x,y\text{が存在する}
\end{equation*}とおきます。\(A\)を満たすような整数の組\(x,y\)を任意に選びます。このとき、\(18x+6y=1\)の両辺を\(6\)で割ることにより、\begin{equation*}
B:3x+y=\frac{1}{6}\text{を満たす}x,y\text{が存在する}
\end{equation*}を得ますが、\(x,y\)が整数ならば\(3x+y\)もまた整数でなければならず、ゆえに\(B\)は恒偽式です。したがって否定導入より\(\lnot A\)が成り立ちますが、これはもとの主張に他なりません。

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

次へ進む 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

述語論理
アカウント
ログイン