含意導入
論理式\(A,B,C\)をそれぞれ任意に選ぶと、以下の恒真式\begin{equation*}\left( A\wedge B\right) \rightarrow C\Leftrightarrow A\rightarrow \left(
B\rightarrow C\right)
\end{equation*}が成り立ちます。特に、\(\Rightarrow \)に相当する主張\begin{equation*}\left( A\wedge B\right) \rightarrow C\Rightarrow A\rightarrow \left(
B\rightarrow C\right)
\end{equation*}を移出律（law of exportation）と呼び、\(\Leftarrow \)に相当する主張\begin{equation*}A\rightarrow \left( B\rightarrow C\right) \Rightarrow \left( A\wedge
B\right) \rightarrow C
\end{equation*}を移入律（law of importation）と呼びます。
論理式\(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\)を任意に選んだ上で、以下の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) \)は妥当です。つまり、妥当であることを示したい推論が、\begin{equation*}A\ \therefore \ B\rightarrow C
\end{equation*}というように、その結論が含意\(B\rightarrow C\)の形をしている場合、その前件\(B\)を前提とする新たな推論\begin{equation*}A,\ B\ \therefore \ C
\end{equation*}を構成した上で、それが妥当であることを示してもよいということです。これは含意導入（implication introduction）や\(\rightarrow \)導入（\(\rightarrow \)introduction）と呼ばれる推論規則です。後ほど詳しく解説しますが、これは条件付き証明と呼ばれる証明方法の根拠になります。
\end{equation*}が成り立つ場合には、\begin{equation*}
A\ \models \ B\rightarrow C
\end{equation*}もまた成り立つ。
&&\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) \\
&\therefore &\ \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) \)を得ます。以上で証明が完了しました。
&&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,\ \forall z\in Z:\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) \)を得ます。以上で証明が完了しました。
含意導入の一般化
移出律と移入律は以下のように一般化されます。
\left( \bigwedge_{i=1}^{n}A_{i}\right) \rightarrow \left( B\rightarrow
C\right)
\end{equation*}が成り立つ。
論理式\(A_{1},\cdots ,A_{n},B,C\)を任意に選んだ上で、以下の2つの推論\begin{eqnarray*}&&\left( a\right) \ A_{1},\cdots ,A_{n},B\ \models \ C \\
&&\left( b\right) \ A_{1},\cdots ,A_{n}\ \models \ B\rightarrow C
\end{eqnarray*}を構成します。推論\(\left( a\right) \)が妥当であるものとします。これは論理式\(\left( \bigwedge_{i=1}^{n}A_{i}\right) \wedge B\rightarrow C\)が恒真式であることを意味しますが、先の命題より、このとき論理式\(\left(\bigwedge_{i=1}^{n}A_{i}\right) \rightarrow \left( B\rightarrow C\right) \)もまた恒真式であるため、推論\(\left( b\right) \)は妥当です。つまり、妥当であることを示したい推論が、\begin{equation*}A_{1},\cdots ,A_{n}\ \models \ B\rightarrow C
\end{equation*}というように、その結論が含意\(B\rightarrow C\)の形をしている場合、その前件\(B\)を前提とする新たな推論\begin{equation*}A_{1},\cdots ,A_{n},B\ \models \ C
\end{equation*}を構成した上で、それが妥当であることを示してもよいということです。以上が含意導入の一般化です。
\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\)が導かれたため証明が完了しました。つまり、もとの推論は妥当です。
演習問題
\end{equation*}が成り立つことを証明してください。
\rightarrow C
\end{equation*}が成り立つことを証明してください。
B\right) \rightarrow C
\end{equation*}が成り立つことを証明してください。
\rightarrow \left( C\wedge D\right)
\end{equation*}が成り立つことを証明してください。
&&\text{整数}x\text{が}2\text{で割り切れるならば、}x\text{は偶数である} \\
&&\text{整数}x\text{が}4\text{で割り切れるならば、}x\text{は偶数である} \\
&&\text{ゆえに、整数}x\text{が}2\text{または}4\text{で割り切れるならば、}x\text{は偶数である}
\end{eqnarray*}が妥当であることを示してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。