教材一覧
PREDICATE LOGIC

含意除去

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

含意除去

論理式\(A,B\)をそれぞれ任意に選ぶと、\begin{align*}
\left( \left( A\rightarrow B\right) \wedge A\right) \rightarrow B&
\Leftrightarrow \lnot \left( \left( \lnot A\vee B\right) \wedge A\right)
\vee B\quad \because \rightarrow \text{の言い換え} \\
& \Leftrightarrow \lnot \left( \left( \lnot A\wedge A\right) \vee \left(
B\wedge A\right) \right) \vee B\quad \because \text{分配律}
\\
& \Leftrightarrow \lnot \left( \bot \vee \left( B\wedge A\right) \right)
\vee B\quad \because \text{矛盾律} \\
& \Leftrightarrow \lnot \left( B\wedge A\right) \vee B\quad \because \text{恒偽式}\bot \text{の性質} \\
& \Leftrightarrow (\lnot B\vee \lnot A)\vee B\quad \because \text{ド・モルガンの法則} \\
& \Leftrightarrow \left( B\vee \lnot B\right) \vee \lnot A\quad \because
\text{交換律と結合律} \\
& \Leftrightarrow \top \vee \lnot A\quad \because \text{排中律} \\
& \Leftrightarrow \top \quad \because \text{恒真式}\top
\text{の性質}
\end{align*}すなわち、\begin{equation*}
\left( \left( A\rightarrow B\right) \wedge A\right) \Rightarrow B
\end{equation*}が成り立ちます。ここから以下の推論規則を得ます。

命題(含意除去)
任意の論理式\(A,B\)に対して以下が成り立つ。\begin{equation*}
A\rightarrow B,\ A\ \models \ B
\end{equation*}
証明を見る(プレミアム会員限定)

つまり、\(A\rightarrow B\)から得られる命題と\(A\)から得られる命題がともに真であるような任意の解釈において\(B\)から得られる命題は必ず真になります。この推論規則を含意除去(implication elimination)や前件肯定(affirming the antecedent)、\(\rightarrow \)除去(\(\rightarrow \ \)elimination)、モーダスポネンス(modus ponens)などと呼びます。

例(含意除去)
命題関数\(P\left( x\right) ,Q\left( x\right) \)に関する以下の推論\begin{equation*}
P\left( x\right) \rightarrow Q\left( x\right) ,\ P\left( x\right) \
\therefore \ Q\left( x\right)
\end{equation*}を考えます。含意除去よりこれは妥当な推論であるため、\begin{equation}
P\left( x\right) \rightarrow Q\left( x\right) ,\ P\left( x\right) \ \models
\ Q\left( x\right) \tag{1}
\end{equation}が成り立ちます。例えば、\(x\)の定義域はすべての整数からなる集合であるとともに、\begin{eqnarray*}
P\left( x\right) &:&x\text{は偶数である}
\\
Q\left( x\right) &:&x^{2}\text{は偶数である}
\end{eqnarray*}と定めると、\(\left( 1\right) \)より、\begin{eqnarray*}
&&x\text{が偶数ならば、}x^{2}\text{は偶数である} \\
&&x\text{は偶数である} \\
&&\text{ゆえに、}x^{2}\text{は偶数である}
\end{eqnarray*}は妥当な推論です。したがって、\(P\left( \overline{x}\right) \rightarrow Q\left( \overline{x}\right) \)と\(P\left( \overline{x}\right) \)がともに真になるような値\(\overline{x}\)に関して\(Q\left( \overline{x}\right) \)が真になることが保証されます。
例(含意除去)
命題関数\(P\left( x,y\right) ,Q\left( x,y\right) \)に関する以下の推論\begin{equation*}
P\left( x,y\right) \rightarrow Q\left( x,y\right) ,\ P\left( x,y\right) \
\therefore \ Q\left( x,y\right)
\end{equation*}を考えます。含意除去よりこれは妥当な推論であるため、\begin{equation}
P\left( x,y\right) \rightarrow Q\left( x,y\right) ,\ P\left( x,y\right) \
\models \ Q\left( x,y\right) \tag{1}
\end{equation}が成り立ちます。例えば、\(x\)の定義域はある大学の学生からなる集合、\(y\)の定義域はその大学で開講されている講義からなる集合であるとともに、\begin{eqnarray*}
P\left( x,y\right) &:&x\text{が}y\text{に出席する} \\
Q\left( x,y\right) &:&x\text{が}y\text{の単位を取得する}
\end{eqnarray*}と定めると、\(\left( 1\right) \)より、\begin{eqnarray*}
&&\text{学生}x\text{が講義}y\text{に出席するならば、学生}x\text{は講義}y\text{の単位を取得する} \\
&&\text{学生}x\text{が講義}y\text{に出席する} \\
&&\text{ゆえに、学生}x\text{は講義}y\text{の単位を取得する}
\end{eqnarray*}は妥当な推論です。したがって、\(P\left( \overline{x},\overline{y}\right) \rightarrow Q\left( \overline{x},\overline{y}\right) \)と\(P\left( \overline{x},\overline{y}\right) \)がともに真になるような値の組\(\left( \overline{x},\overline{y}\right) \)に関して\(Q\left( \overline{x},\overline{y}\right) \)が真になることが保証されます。

 

後件肯定

含意の前件を肯定する前件肯定は妥当である一方で、含意の後件を肯定する後件肯定(affirming the consequent)は妥当ではありません。すなわち、\begin{equation*}
A\rightarrow B,\ B\ \not\models \ A
\end{equation*}となります。これは論理式\(\left( A\rightarrow B\right) \wedge B\rightarrow A\)が恒真式でないことから明らかです。具体的には、\(A\)から得られる命題が偽で\(B\)から得られる命題が真であるような解釈において、\(A\rightarrow B\)から得られる命題と\(B\)から得られる命題はともに真である一方で、結論に相当する\(A\)から得られる命題は偽になります。

例(後件否定)
以下の推論について考えます。\begin{eqnarray*}
&&\text{学生}x\text{が講義}y\text{に出席するならば、学生}x\text{は講義}y\text{の単位を取得する} \\
&&\text{学生}x\text{は講義}y\text{の単位を取得する} \\
&&\text{ゆえに、学生}x\text{が講義}y\text{に出席する}
\end{eqnarray*}ただし、\(x\)の定義域はある大学の学生からなる集合、\(y\)の定義域はその大学で開講されている講義からなる集合です。先と同様の表記を用いると、この推論は、\begin{equation*}
P\left( x,y\right) \rightarrow Q\left( x,y\right) ,\ Q\left( x,y\right) \
\therefore \ P\left( x,y\right)
\end{equation*}と定式化できます。この推論は妥当ではありません。実際、出席しなくても単位がとれるような講義が存在する可能性があるからです。学生\(\overline{x}\)が講義\(\overline{y}\)に出席せずに講義\(\overline{y}\)の単位をとった場合、\(P\left( \overline{x},\overline{y}\right) \rightarrow Q\left( \overline{x},\overline{y}\right) \)と\(Q\left( \overline{x},\overline{y}\right) \)はともに真である一方で\(P\left( \overline{x},\overline{y}\right) \)は偽です。

ただし、後件否定が成り立つようなケースもあります。

例(後件肯定)
以下の推論について考えます。\begin{eqnarray*}
&&x\text{が偶数ならば、}x^{2}\text{は偶数である} \\
&&x^{2}\text{は偶数である} \\
&&\text{ゆえに、}x\text{は偶数である}
\end{eqnarray*}ただし、\(x\)の定義域はすべての整数からなる集合です。先と同様の表記を用いると、この推論は、\begin{equation*}
P\left( x\right) \rightarrow Q\left( x\right) ,\ Q\left( x\right) \
\therefore \ P\left( x\right)
\end{equation*}と定式化できます。\(Q\left( \overline{x}\right) \)が真になるような値\(\overline{x}\)を任意に選んだとき、すなわち\(\overline{x}^{2}\)が偶数になるような整数\(\overline{x}\)を任意に選んだとき、これは偶数であることが保証されるため、この場合には上の推論が妥当になります。ただし、一般には後件肯定は成り立つとは限りません。

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

質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定) 次へ進む
< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

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

述語論理