WIIS

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

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

目次

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

選言導入

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

$$\begin{array}{ccccc}\hline
A & B & A\vee B & A\rightarrow A\vee B & B\rightarrow A\vee B \\
\hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 1 & 1 & 1 \\ \hline
0 & 1 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 1 & 1 \\ \hline
\end{array}$$

表:選言除去

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

命題(選言導入)
任意の論理式\(A,B\)に対して、\begin{eqnarray*}\left( a\right) \ A\ &\models &\ A\vee B \\
\left( b\right) \ B\ &\models &\ A\vee B
\end{eqnarray*}が成り立つ。

例(選言導入)
以下の推論について考えます。\begin{eqnarray*}
&&\text{今日は雨が降っている。} \\
&&\text{ゆえに、今日は雨が降っているか、もしくは寒い。}
\end{eqnarray*}命題変数\(P,Q\)を、\begin{eqnarray*}P &:&\text{今日は雨が降っている} \\
Q &:&\text{今日は寒い}
\end{eqnarray*}とおくと、先の推論は、\begin{equation*}
P\ \therefore \ P\vee Q
\end{equation*}と定式化されます。選言導入よりこれは妥当な推論です。つまり、\begin{equation}
P\ \models \ P\vee Q \quad \cdots (1)
\end{equation}が成り立つということです。これは\(P\)が真であるような状況において\(P\vee Q\)が必ず真になることを意味します。では、上の推論の結論に相当する「今日は雨が降っているか寒い」が偽である場合には何が起きているでしょうか。つまり、\(P\vee Q\)が偽である場合について考えるということです。推論規則\(\left( 1\right) \)が成り立つことを踏まえると、推論の結論である\(P\vee Q\)が偽である場合、推論の前提である\(P\)もまた偽になります。つまり、「今日は雨が降っているか寒い」が偽である場合には「今日は雨が降っていない」ということになります。
例(選言導入)
論理式\(A,B,C\)に関する以下の推論\begin{equation*}\left( A\vee B\right) \rightarrow C\ \therefore \ A\rightarrow C
\end{equation*}について考えます。含意導入より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
\left( A\vee B\right) \rightarrow C,\ A\ \therefore \ C
\end{equation*}の妥当性を示しても問題ありません。\(\left(A\vee B\right) \rightarrow C\)と\(A\)が真であるものとします。\(A\)が真であるとき、選言導入より\(A\vee B\)は真です。\(A\vee B\)と\(\left( A\vee B\right) \rightarrow C\)が真であるとき、含意除去より\(C\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}\left( A\vee B\right) \rightarrow C\ \models \ A\rightarrow C
\end{equation*}が成り立ちます。

 

選言導入の一般化

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

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

証明

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

つまり、\(A_{1}\)が真であるような任意の解釈において\(\bigvee_{i=1}^{n}A_{i}\)は必ず真になります。これは選言導入の一般化です。ここでは推論の前提として\(A_{1}\)を採用しましたが、\(A_{1},\cdots ,A_{n}\)の中のどの論理式を前提として採用した場合でも同様の議論が成り立ちます。

例(選言導入)
論理式\(A,B,C,D\)に関する以下の推論\begin{equation*}\left( A\vee B\vee C\right) \rightarrow D\ \therefore \ A\rightarrow D
\end{equation*}について考えます。含意導入より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
\left( A\vee B\vee C\right) \rightarrow D,\ A\ \therefore \ D
\end{equation*}の妥当性を示しても問題ありません。\(\left(A\vee B\vee C\right) \rightarrow D\)と\(A\)が真であるものとします。\(A\)が真であるとき、選言導入より\(A\vee B\vee C\)は真です。\(A\vee B\vee C\)と\(\left( A\vee B\vee C\right)\rightarrow D\)が真であるとき、含意除去より\(D\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}\left( A\vee B\vee C\right) \rightarrow D\ \models \ A\rightarrow D
\end{equation*}が成り立ちます。

 

演習問題

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

解答を見る

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

問題(選言導入)
任意の論理式\(A,B,C\)について、\begin{equation*}A,\ \left( A\vee B\right) \rightarrow C\ \models \ 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 が命題関数 P(x) から、集合 B が命題関数 Q(x) からそれぞれ内包的に定義されるとき、A と B の和集合は 2 つの命題 P(x),Q(x) の少なくとも一方が真になるような要素 x からなる集合です。

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

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

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

論理式A,B,Cが任意に与えられたとき、前提がA,Bで結論がCであるような推論が妥当である場合、前提がAで結論がB→Cであるような推論もまた妥当になります。これは含意導入と呼ばれる推論規則です。

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

論理式 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,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でないかの少なくとも一方」という結論を導く推論規則を破壊的ジレンマと呼びます。

和集合
集合族の和集合

集合族の要素である少なくとも1つの集合に含まれる要素からなる集合を集合族の和集合と定義します。集合族の和集合は、その集合族の要素である任意の集合を部分集合として含む集合の中でも最小のものです。

推論規則
述語論理における推論規則

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

選言導入
述語論理における選言導入

述語論理においても選言導入が成り立ちます。つまり、論理式A,Bについて、Aから論理和A∨Bを導いたり、Bから論理和A∨Bを導くことができます。

DISCUSSION

質問とコメント

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

命題論理