教材一覧
PROPOSITIONAL LOGIC

連言導入

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

連言導入

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

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

表:連言導入

上の真理値表より、任意の解釈において\(\left( A\wedge B\right) \rightarrow \left( A\wedge B\right) \)の値が\(1\)であることが確認できるため、以下の推論規則\begin{equation*}A,B\ \models \ A\wedge B
\end{equation*}を得ます。つまり、\(A\)と\(B\)がともに真であるような任意の解釈において\(A\wedge B\)は必ず真になります。以上の推論規則を連言導入(conjunction introduction)や\(\wedge \)導入(\(\wedge \) introduction)などと呼びます。

命題(連言導入)
任意の論理式\(A,B\)に対して、\begin{equation*}A,B\ \models \ A\wedge B
\end{equation*}が成り立つ。
例(連言導入)
以下の推論について考えます。\begin{eqnarray*}
&&\text{今日は日曜日である。} \\
&&\text{今日は私は仕事が休みだ。} \\
&&\text{ゆえに、今日は日曜日であるとともに私は仕事が休みだ。}
\end{eqnarray*}命題変数\(P,Q\)を、\begin{eqnarray*}P &:&\text{今日は日曜日である} \\
Q &:&\text{私は仕事が休みだ}
\end{eqnarray*}とおくと、先の推論は、\begin{equation*}
P,\ Q\ \therefore \ P\wedge Q
\end{equation*}と定式化されます。連言導入よりこれは妥当な推論です。つまり、\begin{equation}
P,\ Q\ \models \ P\wedge Q \quad \cdots (1)
\end{equation}が成り立つということです。これは\(P\)と\(Q\)が真であるような状況において\(P\wedge Q\)が必ず真になることを意味します。では、上の推論の結論に相当する「今日は日曜であるとともに仕事が休み」が偽である場合には何が起きているでしょうか。つまり、\(P\wedge Q\)が偽である場合について考えるということです。推論規則\(\left( 1\right) \)が成り立つことを踏まえると、推論の結論である\(P\wedge Q\)が偽である場合、推論の前提である\(P\)と\(Q\)の少なくとも一方が偽になります。つまり、「今日は日曜であるとともに仕事が休み」が偽である場合には「今日は日曜日ではない」か、または「仕事が休みではない」ということになります。
例(連言導入)
論理式\(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*}が成り立ちます。

 

連言導入の一般化

連言導入は以下のような形で一般化可能です。

命題(連言導入)
任意の論理式\(A_{1},\cdots ,A_{n}\)に対して、\begin{equation*}A_{1},\cdots ,A_{n}\ \models \ \bigwedge_{i=1}^{n}A_{i}
\end{equation*}が成り立つ。
証明

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

上の命題において\(n=2\)の場合には、\begin{equation*}A_{1},A_{2}\ \models \ A_{1}\wedge A_{2}
\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*}が成り立ちます。

 

演習問題

問題(連言導入)
繰り返しになりますが、連言導入とは、任意の論理式\(A,B\)に対して、\begin{equation*}A,B\ \models \ A\wedge B
\end{equation*}が成り立つという推論規則です。本文中では連言導入が成り立つことを真理値表を用いて示しましたが、同じことを同値変形で示してください。
解答を見る

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

問題(連言導入)
本文中では、任意の論理式\(A_{1},\cdots ,A_{n}\)に対して、\begin{equation*}A_{1},\cdots ,A_{n}\ \models \ \bigwedge_{i=1}^{n}A_{i}
\end{equation*}が成り立つことを同値変形を通じて示しましたが、同じことを\(n\)に関する数学的帰納法で示してください。
解答を見る

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

問題(連言導入)
任意の論理式\(A,B,C\)に対して、\begin{equation*}A,B\wedge \lnot C\ \models \ A\wedge \lnot C
\end{equation*}が成り立つことを示してください。
証明

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

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

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

共通部分

積事象

事象 A と事象 B の共通部分として定義される事象を A と B の積事象と呼びます。これは「A と B の双方が起こる」という現象に相当する事象です。また、A と B の積事象が空事象であるとき、A と B はお互いに排反事象であると言います。

共通部分

述語論理における論理積

論理式 A,B に論理演算子 ∧ を作用させることで得られる A∧B もまた論理式です。∧ は論理積と呼ばれる論理演算子であり、論理式 A∧B を A と B の論理積と呼びます。

共通部分

共通部分

集合 A,B の双方に属する要素からなる集合を A と B の共通部分と呼びます。集合 A が命題関数 P(x) から、集合 B が命題関数 Q(x) からそれぞれ内包的に定義されるとき、A と B の共通部分は 2 つの命題 P(x), Q(x) がともに真になるような要素 x からなる集合です。

コンパクト集合

コンパクト集合の演算

実数空間において、コンパクト集合どうしの共通部分や和集合もまたコンパクト集合になることを示します。

共通部分

連言除去

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

共通部分

集合族の共通部分

集合族の要素であるすべての集合に含まれる要素からなる集合を集合族の共通部分と定義します。集合族の共通部分は、その集合族の要素である任意の集合に部分集合として含まれる集合の中でも最大のものです。

DISCUSSION

質問とコメント

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

命題論理