教材一覧
教材一覧
教材検索
PROPOSITIONAL LOGIC

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

目次

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

含意導入

論理式\(A,B,C\)をそれぞれ任意に選ぶと、論理積および含意の定義より以下の真理値表が得られます。

\begin{array}{ccccccc}\hline
A & B & C & A\wedge B & \left( A\wedge B\right) \rightarrow C & B\rightarrow C & A\rightarrow \left( B\rightarrow C\right) \\ \hline
1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline
1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \hline
0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline
0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}

表:含意導入

上の真理値表より、任意の解釈において\(\left( A\wedge B\right) \rightarrow C\)と\(A\rightarrow \left(B\rightarrow C\right) \)の真理値が一致することが確認できるため、\begin{equation*}\left( A\wedge B\right) \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) \)が妥当であることを示してもかまいません。これは含意導入(implication introduction)や\(\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{ゆえに、今日が土曜日ならば、私は仕事が休みだ。}
\end{eqnarray*}命題変数\(P,Q,R\)を、\begin{eqnarray*}P &:&\text{今日は土曜日である} \\
Q &:&\text{今日は日曜日である} \\
R &:&\text{私は仕事が休みだ}
\end{eqnarray*}とおくと、先の推論は、\begin{equation*}
\left( P\vee Q\right) \rightarrow R\ \therefore \ P\rightarrow R
\end{equation*}と定式化されます。含意導入より、この推論の妥当性を示すかわりに、以下の推論\begin{equation*}
\left( P\vee Q\right) \rightarrow R,\ P\ \therefore \ R
\end{equation*}が妥当であることを示しても構いません。つまり、\(\left( P\vee Q\right) \rightarrow R\)と\(P\)がともに真であるような任意の解釈において\(R\)が真であることを示すことが目標です。さて、\(P\)が真の場合には論理和の定義より\(P\vee Q\)も真です。加えて、仮定より\(\left(P\vee Q\right) \rightarrow R\)は真であるため、この場合には含意の定義より\(R\)は真です。したがって証明が完了しました。つまり、\begin{equation}\left( P\vee Q\right) \rightarrow R\ \models \ P\rightarrow R \quad \cdots (1)
\end{equation}が成り立つということです。これは、\(\left(P\vee Q\right) \rightarrow R\)が真であるような状況において\(P\rightarrow R\)が必ず真になることを意味します。つまり、「土曜もしくは日曜は仕事が休み」というルールが成立する場合には、必ず「土曜は仕事は休み」になるということです。では、土曜日であるにも関わらず仕事が休みではなかった場合、すなわち\(P\rightarrow R\)が偽である場合には何が起きているのでしょうか。推論規則\(\left( 1\right) \)が成り立つことを踏まえると、この場合、推論の前提である\(\left( P\vee Q\right)\rightarrow R\)が偽になります。つまり、「土曜もしくは水曜は仕事が休み」というルールがそもそも成立していないということになります。

 

含意導入の一般化

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

 

演習問題

問題(含意導入)
論理式\(A,B,C\)を任意に選んだとき、\begin{equation*}\left( A\wedge B\right) \rightarrow C\Leftrightarrow A\rightarrow \left(
B\rightarrow C\right)
\end{equation*}が成り立つことを本文中では真理値表を用いて証明しましたが、同じことを同値変形で示してください。

解答を見る

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

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

解答を見る

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

問題(含意導入)
以下の推論\begin{eqnarray*}
&&2\text{で割り切れる数は偶数である} \\
&&3\text{で割り切れる数は偶数である} \\
&&\text{ゆえに、}2\text{または}3\text{で割り切れる数は偶数である}
\end{eqnarray*}が妥当であることを示してください。また、この推論が妥当であることを踏まえたとき、「\(2\)または\(3\)で割り切れる数は偶数であるとは限らない」ことは何を意味するか、理由とともに答えてください。
解答を見る

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

問題(含意導入)
以下の推論は妥当であるかそうでないか、理由とともに答えてください。\begin{eqnarray*}
&&\text{Aが1位なら、Bが2位であるかCが3位であるかのどちらか一方である。} \\
&&\text{Cは3位ではなかった。} \\
&&\text{ゆえに、Bが2位でなかったのであれば、Aは1位ではなかった。}
\end{eqnarray*}
解答を見る

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

問題(含意導入)
以下の推論は妥当であるかそうでないか、理由とともに答えてください。\begin{eqnarray*}
&&\text{Aが1位なら、Bが2位であるかCが3位であるかのどちらか一方である。} \\
&&\text{Bは2位ではない。} \\
&&\text{ゆえに、Aが1位ならば、Cは3位ではない。}
\end{eqnarray*}
解答を見る

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

問題(含意導入)
以下の推論は妥当であるかそうでないか、理由とともに答えてください。\begin{eqnarray*}
&&\text{Aが1位ならば、Bが2位であり、Cは3位である。} \\
&&\text{Bは2位ではなかった。} \\
&&\text{ゆえに、Aが1位ではなかった。}
\end{eqnarray*}
解答を見る

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

問題(含意導入)
以下の推論は妥当であるかそうでないか、理由とともに答えてください。\begin{eqnarray*}
&&\text{Aが1位であるとき、Bが2位ならばCは3位である。} \\
&&\text{Bは2位ではなかった。} \\
&&\text{ゆえに、Aが1位であるか、Cが3位であるかのどちらか一方である。}
\end{eqnarray*}
解答を見る

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

問題(含意導入)
以下の推論は妥当であるかそうでないか、理由とともに答えてください。\begin{eqnarray*}
&&\text{遊んで勉強もすれば試験に受かる。} \\
&&\text{だが、遊んで勉強しなければ試験に受からない。} \\
&&\text{ゆえに、遊ぶ場合、勉強して試験に受かるか、勉強せず試験に受からないかのどちらか一方である。}
\end{eqnarray*}
解答を見る

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

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

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

質問とコメント

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

RELATED KNOWLEDGE
推論規則
命題論理における推論規則

既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。また、前提がすべて真である場合に結論が必ず真であるならば、その推論は妥当であると言います。妥当な推論を推論式と呼びます。

共通部分
命題論理における連言除去

論理式 A,B が任意に与えられたとき、「AかつB」という前提から「Aである」という結論(もしくは「B」であるという結論)を導く推論規則を連言除去と呼びます。

共通部分
命題論理における連言導入

論理式 A,B が任意に与えられたとき、「Aである」と「Bである」という2つの前提から「AかつB」という結論を導く推論規則を連言導入と呼びます。

推論規則
命題論理における選言除去

論理式 A,B,C を任意に選んだとき、「AならばC」「BならばC」「AまたはB」という3つの前提から「Cである」という結論を導く推論規則を選言除去と呼びます。

和集合
命題論理における選言導入

論理式 A,B を任意に選んだとき、「Aである」(もしくは「Bである」)という前提から「AまたはB」という結論を導く推論規則を選言導入と呼びます。

仮言三段論法
命題論理における仮言三段論法

論理式 A,B,C について、「AならばB」と「BならばC」という前提から「AならばC」という結論を導く推論規則を仮言三段論法と呼びます。

推論規則
命題論理における構成的ジレンマ

論理式 A,B,C,D について、「AならばB」「CならばD」「AまたはC」という前提から「BまたはD」という結論を導く推論規則を構成的ジレンマと呼びます。

推論規則
命題論理における破壊的ジレンマ

論理式 A,B,C,D について、「AならばB」「CならばD」「BでないかDでないかの少なくとも一方」という前提から「AでないかCでないかの少なくとも一方」という結論を導く推論規則を破壊的ジレンマと呼びます。

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

論理式 A,B がともに真であるような任意の解釈において論理式 C が真であることが示された場合には、A が真であるような任意の解釈のもとで B→C が真であることを示したことになります。これは含意導入と呼ばれる推論規則です。

命題論理