WIIS

述語論理

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

目次

Mailで保存
Xで共有

含意導入

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

解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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