連言導入
論理式\(A,B\)を任意に選んだとき、以下の推論規則\begin{equation*}A,\ B\ \models \ A\wedge B
\end{equation*}が成り立ちます。つまり、\(A\)と\(B\)がともに真であるような任意の解釈において\(A\wedge B\)は必ず真になります。以上の推論規則を連言導入（conjunction introduction）や\(\wedge \)導入（\(\wedge \) introduction）などと呼びます。
連言除去\begin{eqnarray*}
\left( a\right) \ A\wedge B\ &\models &\ A \\
\left( b\right) \ A\wedge B\ &\models &\ B
\end{eqnarray*}は、複数の情報から必要な情報だけを取り出す推論規則です。一方、連言導入\begin{equation*}
A,\ B\ \models \ A\wedge B
\end{equation*}は、複数の情報が得られたとき、それらを1つの論理式へまとめる推論規則です。実際の証明では、連言除去と連言導入を組み合わせて用いることが多くあります。
命題（連言導入）
任意の論理式\(A,B\)に対して、\begin{equation*}A,\ B\ \models \ A\wedge B
\end{equation*}が成り立つ。
\end{equation*}が成り立つ。
例（連言導入）
命題関数\(P\left( x\right) ,Q\left( x\right) \)を任意に選んだとき、連言導入より、\begin{equation*}P\left( x\right) ,\ Q\left( x\right) \ \models \ P\left( x\right) \wedge
Q\left( x\right)
\end{equation*}が成り立ちます。
Q\left( x\right)
\end{equation*}が成り立ちます。
例（連言導入）
論理式\(A,B,C\)に関する以下の推論\begin{equation*}A\rightarrow B,\ A\rightarrow C,\ A\ \therefore \ B\wedge C
\end{equation*}について考えます。\(A\rightarrow B\)と\(A\rightarrow C\)と\(A\)がいずれも真であるものとします。\(A\)と\(A\rightarrow B\)が真であるとき、含意除去より\(B\)は真です。また、\(A\)と\(A\rightarrow C\)が真であるとき、含意除去より\(C\)は真です。\(B\)と\(C\)が真であるため、連言導入より\(B\wedge C\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}A\rightarrow B,\ A\rightarrow C,\ A\ \models \ B\wedge C
\end{equation*}が成り立ちます。
\end{equation*}について考えます。\(A\rightarrow B\)と\(A\rightarrow C\)と\(A\)がいずれも真であるものとします。\(A\)と\(A\rightarrow B\)が真であるとき、含意除去より\(B\)は真です。また、\(A\)と\(A\rightarrow C\)が真であるとき、含意除去より\(C\)は真です。\(B\)と\(C\)が真であるため、連言導入より\(B\wedge C\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}A\rightarrow B,\ A\rightarrow C,\ A\ \models \ B\wedge C
\end{equation*}が成り立ちます。
例（連言導入）
以下の推論について考えます。\begin{eqnarray*}
&&\text{任意の偶数は}1\text{で割り切れる} \\
&&\text{任意の偶数は}2\text{で割り切れる} \\
&&\text{ゆえに、任意の偶数は}1\text{と}2\text{で割り切れる}
\end{eqnarray*}ただし、変数\(x\)の定義域はすべての整数からなる集合\(\mathbb{Z} \)です。以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は}1\text{で割り切れる} \\
Q\left( x\right) &:&x\text{は}2\text{で割り切れる}
\end{eqnarray*}を定義すると、先の推論は、\begin{equation*}
\forall x\in \mathbb{Z} :P\left( x\right) ,\ \forall x\in \mathbb{Z} :Q\left( x\right) \ \therefore \ \forall x\in \mathbb{Z} :\left( P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}と定式化されます。推論の前提に全称除去を適用すると、\begin{eqnarray*}
&&P\left( c\right) \\
&&Q\left( c\right)
\end{eqnarray*}を得ます。これらに連言導入を適用すると、\begin{equation*}
P\left( c\right) \wedge Q\left( c\right)
\end{equation*}を得て、さらにこれに全称導入を適用すると、\begin{equation*}
\forall x\in \mathbb{Z} :\left( P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}を得るため、推論が妥当であることが示されました。
&&\text{任意の偶数は}1\text{で割り切れる} \\
&&\text{任意の偶数は}2\text{で割り切れる} \\
&&\text{ゆえに、任意の偶数は}1\text{と}2\text{で割り切れる}
\end{eqnarray*}ただし、変数\(x\)の定義域はすべての整数からなる集合\(\mathbb{Z} \)です。以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は}1\text{で割り切れる} \\
Q\left( x\right) &:&x\text{は}2\text{で割り切れる}
\end{eqnarray*}を定義すると、先の推論は、\begin{equation*}
\forall x\in \mathbb{Z} :P\left( x\right) ,\ \forall x\in \mathbb{Z} :Q\left( x\right) \ \therefore \ \forall x\in \mathbb{Z} :\left( P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}と定式化されます。推論の前提に全称除去を適用すると、\begin{eqnarray*}
&&P\left( c\right) \\
&&Q\left( c\right)
\end{eqnarray*}を得ます。これらに連言導入を適用すると、\begin{equation*}
P\left( c\right) \wedge Q\left( c\right)
\end{equation*}を得て、さらにこれに全称導入を適用すると、\begin{equation*}
\forall x\in \mathbb{Z} :\left( P\left( x\right) \wedge Q\left( x\right) \right)
\end{equation*}を得るため、推論が妥当であることが示されました。
連言導入の一般化
連言導入は以下のような形で一般化可能です。
命題（連言導入）
任意の論理式\(A_{1},\cdots ,A_{n}\)に対して、\begin{equation*}A_{1},\cdots ,A_{n}\ \models \ \bigwedge_{i=1}^{n}A_{i}
\end{equation*}が成り立つ。
\end{equation*}が成り立つ。
例（連言導入）
命題関数\(P_{1}\left( x\right) ,\cdots ,P_{n}\left(x\right) \)が任意に与えられたとき、先の命題より、\begin{equation*}P_{1}\left( x\right) ,\cdots ,P_{n}\left( x\right) \ \models \
\bigwedge_{i=1}^{n}P_{i}\left( x\right)
\end{equation*}が成り立ちます。
\bigwedge_{i=1}^{n}P_{i}\left( x\right)
\end{equation*}が成り立ちます。
例（連言導入）
論理式\(A,B,C,D\)に関する以下の推論\begin{equation*}A\rightarrow B,\ A\rightarrow C,\ A\rightarrow D,\ A\ \therefore \ B\wedge
C\wedge D
\end{equation*}について考えます。\(A\rightarrow B\)と\(A\rightarrow C\)と\(A\rightarrow D\)と\(A\)がいずれも真であるものとします。\(A\)と\(A\rightarrow B\)が真であるとき、含意除去より\(B\)は真です。同様に、\(A\)と\(A\rightarrow C\)から\(C\)が、\(A\)と\(A\rightarrow D\)から\(D\)がそれぞれ含意除去より導かれます。\(B,C,D\)が真であるため、連言導入より\(B\wedge C\wedge D\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}A\rightarrow B,\ A\rightarrow C,\ A\rightarrow D,\ A\ \models \ B\wedge
C\wedge D
\end{equation*}が成り立ちます。
C\wedge D
\end{equation*}について考えます。\(A\rightarrow B\)と\(A\rightarrow C\)と\(A\rightarrow D\)と\(A\)がいずれも真であるものとします。\(A\)と\(A\rightarrow B\)が真であるとき、含意除去より\(B\)は真です。同様に、\(A\)と\(A\rightarrow C\)から\(C\)が、\(A\)と\(A\rightarrow D\)から\(D\)がそれぞれ含意除去より導かれます。\(B,C,D\)が真であるため、連言導入より\(B\wedge C\wedge D\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}A\rightarrow B,\ A\rightarrow C,\ A\rightarrow D,\ A\ \models \ B\wedge
C\wedge D
\end{equation*}が成り立ちます。
演習問題
問題（連言導入）
本文中では、任意の論理式\(A_{1},\cdots ,A_{n}\)に対して、\begin{equation*}A_{1},\cdots ,A_{n}\ \models \ \bigwedge_{i=1}^{n}A_{i}
\end{equation*}が成り立つことを同値変形を通じて示しましたが、同じことを論理式の個数\(n\)に関する数学的帰納法で示してください。
\end{equation*}が成り立つことを同値変形を通じて示しましたが、同じことを論理式の個数\(n\)に関する数学的帰納法で示してください。
問題（連言導入）
任意の論理式\(A,B,C\)に対して、\begin{equation*}A,\ B\wedge \lnot C\ \models \ A\wedge \lnot C
\end{equation*}が成り立つことを示してください。
\end{equation*}が成り立つことを示してください。
問題（推論の妥当性）
命題関数\(P\left( x\right) ,Q\left( x\right) ,R\left(x\right) \)に関する以下の推論\begin{equation*}P\left( x\right) \wedge Q\left( x\right) \wedge R\left( x\right) \
\therefore \ Q\left( x\right) \wedge R\left( x\right)
\end{equation*}が妥当であることを示してください。
\therefore \ Q\left( x\right) \wedge R\left( x\right)
\end{equation*}が妥当であることを示してください。
問題（推論の妥当性）
論理式\(A,B,C\)に関する以下の推論\begin{equation*}A\rightarrow B,\ A\rightarrow C\ \therefore \ A\rightarrow B\wedge C
\end{equation*}が妥当であることを示してください。
\end{equation*}が妥当であることを示してください。
問題（推論の妥当性）
論理式\(A,B,C\)に関する以下の推論\begin{equation*}A\wedge B\ \therefore \ C\rightarrow B\wedge C
\end{equation*}が妥当であることを示してください。
\end{equation*}が妥当であることを示してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。