教材一覧
教材一覧
教材検索

述語論理

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

目次

Twitterで共有
メールで共有

含意導入

論理式\(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{すべての外科医は医者だ} \\
&&\text{すべての医者は大学を卒業している} \\
&&\text{したがって、すべての外科医は大学を卒業している}
\end{eqnarray*}変数\(x\)の定義域\(X\)はすべての人間からなる集合です。以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は外科医である} \\
Q\left( x\right) &:&x\text{は医者である}
\\
R\left( x\right) &:&x\text{は大学を卒業している}
\end{eqnarray*}を定義すると、先の推論は、\begin{eqnarray*}
\forall x &\in &X:\left( P\left( x\right) \rightarrow Q\left( x\right)
\right) , \\
\forall x &\in &X:\left( Q\left( x\right) \rightarrow R\left( x\right)
\right) \\
&\models &\ \forall x\in X:\left( P\left( x\right) \rightarrow R\left(
x\right) \right)
\end{eqnarray*}と定式化されます。推論の前提に全称除去を適用すると、\begin{eqnarray}
P\left( c\right) &\rightarrow &Q\left( c\right) \quad \cdots (1) \\
Q\left( c\right) &\rightarrow &R\left( c\right) \quad \cdots (2)
\end{eqnarray}を得ます。このとき、推論の結論に関して、\begin{equation}
P\left( c\right) \rightarrow R\left( c\right) \quad \cdots (3)
\end{equation}を示すことに成功すれば、全称導入より、\begin{equation*}
\forall x\in X:\left( P\left( x\right) \rightarrow R\left( x\right) \right)
\end{equation*}が成り立つため、推論が妥当となります。以上を踏まえると、\(\left( 1\right) ,\left( 2\right) \)から\(\left( 3\right) \)を導くこと、すなわち、\begin{equation*}P\left( c\right) \rightarrow Q\left( c\right) ,\ Q\left( c\right)
\rightarrow R\left( c\right) \ \therefore \ P\left( c\right) \rightarrow
R\left( c\right)
\end{equation*}が妥当であることを示すことが目標になります。ただし、含意導入より、\begin{equation*}
P\left( c\right) \rightarrow Q\left( c\right) ,\ Q\left( c\right)
\rightarrow R\left( c\right) ,\ P\left( c\right) \ \therefore \ R\left(
c\right)
\end{equation*}を示しても問題ありません。そこで、\(P\left(c\right) \rightarrow Q\left( c\right) \)と\(Q\left( c\right) \rightarrow R\left( c\right) \)と\(P\left( c\right) \)が真であるものとします。\(P\left(c\right) \)と\(P\left( c\right) \rightarrow Q\left( c\right) \)に含意除去を適用すると\(Q\left( c\right) \)を得るため、これと\(Q\left( c\right) \rightarrow R\left( c\right) \)に含意除去を適用すると\(R\left( c\right) \)を得ます。したがって証明が完了しました。
例(含意導入)
以下の推論について考えます。\begin{eqnarray*}
&&x\text{曜日または}y\text{時であるならば、店}z\text{は閉店中だ} \\
&&\text{ゆえに、}x\text{曜日ならば、店}z\text{は閉店中だ}
\end{eqnarray*}変数\(x\)の定義域\(X\)はすべての曜日からなる集合、変数\(y\)の定義域\(Y\)はすべての時刻からなる集合、そして変数\(z\)の定義域\(Z\)は問題としているすべての店からなる集合であるものとします。以下の命題関数\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{eqnarray*}
\forall x &\in &X,\ \forall y\in Y:\left( \left( P\left( x\right) \vee
Q\left( y\right) \right) \rightarrow R\left( z\right) \right) \\
&\therefore &\ \forall x\in X,\ \forall z\in Z:\left( P\left( x\right)
\rightarrow R\left( z\right) \right)
\end{eqnarray*}と定式化されます。推論の前提に全称除去を適用すると、\begin{equation}
\left( P\left( c\right) \vee Q\left( d\right) \right) \rightarrow R\left(
e\right) \quad \cdots (1)
\end{equation}を得ます。このとき、推論の結論に関して、\begin{equation}
P\left( c\right) \rightarrow R\left( e\right) \quad \cdots (2)
\end{equation}を示すことに成功すれば、全称導入より、\begin{equation*}
\forall x\in X,\ \forall z\in Z:\left( P\left( x\right) \rightarrow R\left(
z\right) \right)
\end{equation*}が成り立つため、推論が妥当となります。以上を踏まえると、\(\left( 1\right) \)から\(\left( 2\right) \)を導くこと、すなわち、\begin{equation*}\left( P\left( c\right) \vee Q\left( d\right) \right) \rightarrow R\left(
e\right) \ \therefore \ P\left( c\right) \rightarrow R\left( e\right)
\end{equation*}が妥当であることを示すことが目標になります。ただし、含意導入より、\begin{equation*}
\left( P\left( c\right) \vee Q\left( d\right) \right) \rightarrow R\left(
e\right) ,\ P\left( c\right) \ \therefore \ R\left( e\right)
\end{equation*}を示しても問題ありません。そこで、\(\left(P\left( c\right) \vee Q\left( d\right) \right) \rightarrow R\left( e\right) \)と\(P\left( c\right) \)が真であるものとします。\(P\left( c\right) \)が真である場合には\(P\left(c\right) \vee Q\left( d\right) \)は真であるため、これと\(\left( P\left( c\right)\vee Q\left( d\right) \right) \rightarrow R\left( e\right) \)に含意除去を適用すると\(R\left( e\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*}を構成した上で、それが妥当であることを示してもよいということです。

例(含意導入)
論理式\(A,B,C\)に関する以下の推論\begin{equation*}A\rightarrow C,\ B\rightarrow C\ \therefore \ \left( A\vee B\right)
\rightarrow C
\end{equation*}について考えます。含意導入より、この推論の妥当性を示す代わりに、以下の推論\begin{equation*}
A\rightarrow C,\ B\rightarrow C,\ A\vee B\ \therefore \ C
\end{equation*}の妥当性を示しても問題ありません。そこで、\(A\rightarrow C\)と\(B\rightarrow C\)と\(A\vee B\)がすべて真であるものとします。\(A\vee B\)が真であるとき、論理和の定義より\(A\)と\(B\)の少なくとも一方が真です。\(A\)が真であるとき、これと\(A\rightarrow C\)に含意除去を適用すれば\(C\)を得ます。\(B\)が真であるとき、これと\(B\rightarrow C\)に含意除去を適用すれば\(C\)を得ます。いずれの場合にも\(C\)が導かれたため証明が完了しました。つまり、もとの推論は妥当です。

 

演習問題

問題(含意導入)
論理式\(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*}が妥当であることを示してください。

解答を見る

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

Twitterで共有
メールで共有
DISCUSSION

質問とコメント