含意導入
論理式\(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）と呼ばれる推論規則です。
\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*}を構成した上で、それが妥当であることを示してもよいということです。後ほど詳しく解説しますが、これは条件付き証明と呼ばれる証明方法の根拠になります。
&&\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 \)は移入律の一般化です。以上の恒真式を踏まえると、含意導入を以下のように一般化できます。
\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*}を構成した上で、それが妥当であることを示してもよいということです。
\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\)と\(Q\rightarrow R\)がともに真であるとき、やはり含意の定義より\(R\)は真です。いずれの場合にも\(R\)は真であるため目標が達成されました。つまり、もとの推論は妥当です。
演習問題
B\rightarrow C\right)
\end{equation*}が成り立つことを本文中では真理値表を用いて証明しましたが、同じことを同値変形で示してください。
\end{equation*}が成り立つことを証明してください。
&&2\text{で割り切れる数は偶数である} \\
&&3\text{で割り切れる数は偶数である} \\
&&\text{ゆえに、}2\text{または}3\text{で割り切れる数は偶数である}
\end{eqnarray*}が妥当であることを示してください。また、この推論が妥当であることを踏まえたとき、「\(2\)または\(3\)で割り切れる数は偶数であるとは限らない」ことは何を意味するか、理由とともに答えてください。
&&\text{Aが1位なら、Bが2位であるかCが3位であるかのどちらか一方である。} \\
&&\text{Cは3位ではなかった。} \\
&&\text{ゆえに、Bが2位でなかったのであれば、Aは1位ではなかった。}
\end{eqnarray*}
&&\text{Aが1位なら、Bが2位であるかCが3位であるかのどちらか一方である。} \\
&&\text{Bは2位ではない。} \\
&&\text{ゆえに、Aが1位ならば、Cは3位ではない。}
\end{eqnarray*}
&&\text{Aが1位ならば、Bが2位であり、Cは3位である。} \\
&&\text{Bは2位ではなかった。} \\
&&\text{ゆえに、Aが1位ではなかった。}
\end{eqnarray*}
&&\text{Aが1位であるとき、Bが2位ならばCは3位である。} \\
&&\text{Bは2位ではなかった。} \\
&&\text{ゆえに、Aが1位であるか、Cが3位であるかのどちらか一方である。}
\end{eqnarray*}
&&\text{遊んで勉強もすれば試験に受かる。} \\
&&\text{だが、遊んで勉強しなければ試験に受からない。} \\
&&\text{ゆえに、遊ぶ場合、勉強して試験に受かるか、勉強せず試験に受からないかのどちらか一方である。}
\end{eqnarray*}
プレミアム会員専用コンテンツです
【ログイン】【会員登録】