教材一覧
PROPOSITIONAL LOGIC

選言除去

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

選言除去

論理式\(A,B,C\)をそれぞれ任意に選んだとき、便宜的に、\begin{equation*}D=\left( A\rightarrow C\right) \wedge \left( B\rightarrow C\right) \wedge
\left( A\vee B\right)
\end{equation*}と表記すると、含意と論理積および論理和の定義より以下の真理値表が得られます。

$$\begin{array}{cccccccc}\hline
A & B & C & A\rightarrow C & B\rightarrow C & A\vee B & D & D\rightarrow C \\ \hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline
1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline
0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ \hline
0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ \hline
\end{array}$$

表:選言除去

上の真理値表より、任意の解釈において\(D\rightarrow C\)すなわち、\begin{equation*}\left( A\rightarrow C\right) \wedge \left( B\rightarrow C\right) \wedge
\left( A\vee B\right) \rightarrow C
\end{equation*}の値が\(1\)であることが確認できるため、以下の推論規則\begin{equation*}A\rightarrow C,\ B\rightarrow C,\ A\vee B\ \models \ C
\end{equation*}を得ます。つまり、含意である\(A\rightarrow C\)および\(B\rightarrow C\)と論理和\(A\vee B\)が真であるような任意の解釈において\(C\)は真になります。以上の推論規則を選言除去(disjunction elimination)や\(\vee \)除去(\(\vee \) elimination)などと呼びます。

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

 

選言除去の一般化

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

命題(選言除去の一般化)
任意の論理式\(A_{1},\cdots ,A_{n},B\)に対して、\begin{equation*}A_{1}\rightarrow B,\cdots ,\ A_{n}\rightarrow B,\ \bigvee_{i=1}^{n}A_{i}\
\models \ B
\end{equation*}が成り立つ。
証明

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

上の命題において\(n=1\)の場合には、\begin{equation*}A\rightarrow B,\ A\ \models \ B
\end{equation*}となりますが、これは含意除去に他なりません。また、\(n=2\)の場合には、\begin{equation*}A_{1}\rightarrow B,\ A_{2}\rightarrow B,\ A_{1}\vee A_{2}\ \models \ B
\end{equation*}となりますが、これは先に示した選言除去です。

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

 

演習問題

問題(選言除去)
ある通りに5軒のラーメン屋さんがありますが、どの店も美味しいことで有名です。この通りのお店でラーメンを食べたとき、必ず美味しいラーメンが食べられることを選言除去を用いて証明してください。
解答を見る

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

問題(選言除去)
繰り返しになりますが、選言除去とは、任意の論理式\(A,B,C\)に対して、\begin{equation*}A\rightarrow C,\ B\rightarrow C,\ A\vee B\ \models \ C
\end{equation*}が成り立つという推論規則です。本文中では選言除去が成り立つことを真理値表を用いて示しましたが、同じことを同値変形で示してください。つまり、\begin{equation*}
\left( A\rightarrow C\right) \wedge \left( B\rightarrow C\right) \wedge
\left( A\vee B\right) \rightarrow C\Leftrightarrow \top
\end{equation*}が成り立つことを同値変形により証明してください。
証明

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

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

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

関連知識

DISCUSSION

質問とコメント

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

命題論理