教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における含意導入

目次

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

含意導入

論理式\(A,B,C\)を任意に選んだときに、\begin{equation*}A\wedge B\rightarrow C\Leftrightarrow A\rightarrow \left( B\rightarrow
C\right)
\end{equation*}が成り立つことが示されます。\(\Rightarrow \)は移出律(law of exportation)と呼ばれ、\(\Leftarrow \)は移入律(law of importation)と呼ばれます。

論理式\(A,B,C\)を任意に選んだ上で、以下の2つの推論\begin{eqnarray*}&&\left( a\right) \ A,B\ \therefore \ C \\
&&\left( b\right) \ A\ \therefore \ B\rightarrow C
\end{eqnarray*}について考えます。推論\(\left( a\right) \)が妥当であるものとします。これは論理式\(\left( A\wedge B\right) \rightarrow C\)が恒真式であることを意味しますが、移出律より、このとき論理式\(A\rightarrow \left( B\rightarrow C\right) \)もまた恒真式であるため、推論\(\left( b\right) \)は妥当です。したがって、推論\(\left( b\right) \)が妥当であることを示すかわりに推論\(\left( a\right) \)が妥当であることを示してもかまいません。これは含意導入(implicationintroduction)や\(\rightarrow \)導入(\(\rightarrow \) introduction)と呼ばれる推論規則です。

命題(含意導入)
論理式\(A,B,C\)を任意に選んだとき、\begin{equation*}A,B\ \models \ C
\end{equation*}が成り立つ場合には、\begin{equation*}
A\ \models \ B\rightarrow C
\end{equation*}もまた成り立つ。

証明

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

つまり、妥当であることを示したい推論が、\begin{equation*}
A\ \therefore \ B\rightarrow C
\end{equation*}というように、その結論が含意\(B\rightarrow C\)の形をしている場合、その前件\(B\)を前提とする新たな推論\begin{equation*}A,B\ \therefore \ C
\end{equation*}を構成した上で、それが妥当であることを示してもよいということです。後ほど詳しく解説しますが、これは条件付き証明と呼ばれる証明方法の根拠になります。

例(含意導入)
以下の推論について考えます。\begin{eqnarray*}
&&\text{現在は}x\text{曜日または}y\text{時であるならば、店}z\text{は閉店中だ} \\
&&\text{ゆえに、現在が}x\text{曜日ならば、店}z\text{は閉店中だ}
\end{eqnarray*}変数\(x\)の定義域\(X\)はすべての曜日からなる集合、変数\(y\)の定義域\(Y\)はすべての時刻からなる集合、そして変数\(z\)の定義域\(Z\)は問題としているすべての店からなる集合であるものとします。さらに命題関数\(P,Q,R\)を、\begin{eqnarray*}P\left( x\right) &:&\text{現在は}x\text{曜日である} \\
Q\left( y\right) &:&\text{現在は}y\text{時である} \\
R\left( z\right) &:&\text{店}z\text{は閉店中である}
\end{eqnarray*}と定義すると、先の推論は、\begin{equation*}
P\left( x\right) \vee Q\left( y\right) \rightarrow R\left( z\right) \
\therefore \ P\left( x\right) \rightarrow R\left( z\right)
\end{equation*}と定式化されます。含意導入より、この推論の妥当性を示す代わりに、以下の推論\begin{equation*}
P\left( x\right) \vee Q\left( y\right) \rightarrow R\left( z\right) ,\
P\left( x\right) \ \therefore \ R\left( z\right)
\end{equation*}が妥当であることを示しても構いません。そこで、\(P\left( x\right) \vee Q\left(y\right) \rightarrow R\left( z\right) \)と\(P\left( x\right) \)が真であるような解釈を任意に選びます。\(P\left( x\right) \)が真である場合には\(P\left( x\right) \vee Q\left( y\right) \)もまた真です。このとき\(P\left( x\right) \vee Q\left( y\right) \rightarrow R\left( z\right) \)が真であるためには\(R\left(z\right) \)は真でなければならないため、推論の妥当性が示されました。つまり、\begin{equation*}P\left( x\right) \vee Q\left( y\right) \rightarrow R\left( z\right) \
\models \ P\left( x\right) \rightarrow R\left( z\right)
\end{equation*}が成り立ちます。したがって、具体的な曜日\(\overline{x}\in X\)と時刻\(\overline{y}\in Y\)と店\(\overline{z}\in Z\)をそれぞれ任意に選んだとき、\begin{equation*}P\left( \overline{x}\right) \vee Q\left( \overline{y}\right) \rightarrow
R\left( \overline{z}\right) \ \models \ P\left( \overline{x}\right)
\rightarrow R\left( \overline{z}\right)
\end{equation*}が成り立つことが保証されます。つまり、\(P\left( \overline{x}\right) \vee Q\left( \overline{y}\right)\rightarrow R\left( \overline{z}\right) \)が真の命題である場合には\(P\left( \overline{x}\right) \rightarrow R\left( \overline{z}\right) \)もまた真の命題になることが保証されるということです。逆に、\(P\left( \overline{x}\right) \rightarrow R\left( \overline{z}\right) \)が偽である場合には$P\left( \overline{x}\right) \vee Q\left( \overline{y}\right) \rightarrow R\left(
\overline{z}\right) $もまた偽になります。

 

含意導入の一般化

論理式\(A_{1},\cdots ,A_{n},B,C\)をそれぞれ任意に選んだとき、\begin{equation*}\left( \bigwedge_{i=1}^{n}A_{i}\right) \wedge B\rightarrow C\Leftrightarrow
\left( \bigwedge_{i=1}^{n}A_{i}\right) \rightarrow \left( B\rightarrow
C\right)
\end{equation*}が成り立ちます(演習問題)。\(\Rightarrow \)は移出律の一般化であり、\(\Leftarrow \)は移入律の一般化です。以上の恒真式を踏まえると、含意導入を以下のように一般化できます。

命題(含意導入)
論理式\(A_{1},\cdots ,A_{n},B,C\)を任意に選んだとき、\begin{equation*}A_{1},\cdots ,A_{n},B\ \models \ C
\end{equation*}が成り立つ場合には、\begin{equation*}
A_{1},\cdots ,A_{n}\ \models \ B\rightarrow C
\end{equation*}もまた成り立つ。

証明

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

つまり、妥当であることを示したい推論が、\begin{equation*}
A_{1},\cdots ,A_{n}\therefore \ B\rightarrow C
\end{equation*}というように、その結論が含意\(B\rightarrow C\)の形をしている場合、その前件\(B\)を前提とする新たな推論\begin{equation*}A_{1},\cdots ,A_{n},B\ \therefore \ C
\end{equation*}を構成した上で、それが妥当であることを示してもよいということです。

例(含意導入)
命題関数である\(P\left( x\right),Q\left( x\right) ,R\left( x\right) \)に関する以下の推論\begin{equation*}P\left( x\right) \rightarrow R\left( x\right) ,\ Q\left( x\right)
\rightarrow R\left( x\right) \ \therefore \ \left( P\left( x\right) \vee
Q\left( x\right) \right) \rightarrow R\left( x\right)
\end{equation*}について考えます。含意導入より、この推論の妥当性を示す代わりに、以下の推論\begin{equation*}
P\left( x\right) \rightarrow R\left( x\right) ,\ Q\left( x\right)
\rightarrow R\left( x\right) ,\ P\left( x\right) \vee Q\left( x\right) \
\therefore \ R\left( x\right)
\end{equation*}の妥当性を示しても問題ありません。そこで、\(P\left( x\right) \rightarrow R\left( x\right) \)と\(Q\left( x\right) \rightarrow R\left( x\right) \)と\(P\left(x\right) \vee Q\left( x\right) \)がすべて真であるものとします。\(P\left( x\right) \vee Q\left( x\right) \)が真であるとき、論理和の定義より\(P\left( x\right) \)と\(Q\left( x\right) \)の少なくとも一方は真です。\(P\left( x\right) \)と\(P\left( x\right)\rightarrow R\left( x\right) \)がともに真であるとき、含意の定義より\(R\left( x\right) \)は真です。一方、\(Q\left( x\right) \)と\(P\left(x\right) \rightarrow R\left( x\right) \)がともに真であるとき、やはり含意の定義より\(R\left(x\right) \)は真です。いずれの場合にも\(R\left( x\right) \)は真であるため目標が達成されました。つまり、もとの推論は妥当です。

 

演習問題

問題(含意導入)
論理式\(A,B,C\)を任意に選んだとき、\begin{equation*}A\rightarrow B,\ B\rightarrow C\ \models \ A\rightarrow C
\end{equation*}が成り立つことを証明してください。

解答を見る

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

問題(含意導入)
以下の推論\begin{eqnarray*}
&&\text{整数}x\text{が}2\text{で割り切れるならば、}x\text{は偶数である} \\
&&\text{整数}x\text{が}3\text{で割り切れるならば、}x\text{は偶数である} \\
&&\text{ゆえに、整数}x\text{が}2\text{または}3\text{で割り切れるならば、}x\text{は偶数である}
\end{eqnarray*}が妥当であることを示してください。

解答を見る

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

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

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

質問とコメント

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

RELATED KNOWLEDGE

関連知識

含意導入
命題論理における含意導入

論理式A,B,Cが任意に与えられたとき、前提がA,Bで結論がCであるような推論が妥当である場合、前提がAで結論がB→Cであるような推論もまた妥当になります。これは含意導入と呼ばれる推論規則です。

述語論理