論理式 A,B,C を任意に選んだとき、「AならばC」「BならばC」「AまたはB」という3つの前提から「Cである」という結論を導く推論規則を選言除去と呼びます。
< 前のページ
次のページ >

選言除去

論理式\(A,B,C\)をそれぞれ任意に選ぶと、\begin{eqnarray*}
&&\left( A\rightarrow C\right) \wedge \left( B\rightarrow C\right) \wedge
\left( A\vee B\right) \rightarrow C \\
&\Leftrightarrow &\lnot \left( \left( \lnot A\vee C\right) \wedge \left(
\lnot B\vee C\right) \wedge \left( A\vee B\right) \right) \vee C\quad
\because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot \left( \lnot A\vee C\right) \vee \lnot \left(
\lnot B\vee C\right) \vee \lnot \left( A\vee B\right) \right) \vee C\quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \left( A\wedge \lnot C\right) \vee \left( B\wedge
\lnot C\right) \vee \left( \lnot A\wedge \lnot B\right) \right) \vee C\quad
\because \text{ド・モルガンの法則、二重否定} \\
&\Leftrightarrow &\left( \left( A\wedge \lnot C\right) \vee C\right) \vee
\left( \left( B\wedge \lnot C\right) \vee C\right) \vee \left( \lnot A\wedge
\lnot B\right) \quad \because \text{ベキ等律、交換律、結合律} \\
&\Leftrightarrow &\left( \left( A\vee C\right) \wedge \left( \lnot C\vee
C\right) \right) \vee \left( \left( B\vee C\right) \wedge \left( \lnot C\vee
C\right) \right) \vee \left( \lnot A\wedge \lnot B\right) \ \because \text{分配律} \\
&\Leftrightarrow &\left( \left( A\vee C\right) \wedge \top \right) \vee
\left( \left( B\vee C\right) \wedge \top \right) \vee \left( \lnot A\wedge
\lnot B\right) \quad \because \text{排中律} \\
&\Leftrightarrow &\left( A\vee C\right) \vee \left( B\vee C\right) \vee
\left( \lnot A\wedge \lnot B\right) \quad \because \text{恒真式}\top \text{の性質} \\
&\Leftrightarrow &\left( A\vee B\right) \vee \lnot \left( A\vee B\right)
\vee C\quad \because \text{交換律、ベキ等律、ド・モルガンの法則} \\
&\Leftrightarrow &\top \vee C\quad \because \text{排中律}
\\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち、\begin{equation*}
\left( A\rightarrow C\right) \wedge \left( B\rightarrow C\right) \wedge
\left( A\vee B\right) \Rightarrow C
\end{equation*}が成り立ちます。ここから以下の推論規則を得ます。

命題(選言除去)
任意の論理式\(A,B,C\)に対して以下が成り立つ。\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)などと呼びます。

例(選言除去)
以下の推論について考えます。\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*}と定式化されます。選言除去より、これは妥当な推論です。
例(選言除去)
命題変数\(P,Q,R\)に関する以下の推論\begin{equation*}
P\rightarrow R,\ Q\rightarrow R\ \therefore \ \left( P\vee Q\right)
\rightarrow R
\end{equation*}について考えます。含意導入より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
P\rightarrow R,\ Q\rightarrow R,\ P\vee Q\ \therefore \ R
\end{equation*}の妥当性を示しても問題ありません。\(P\rightarrow R\)と\(Q\rightarrow R\)と\(P\vee Q\)がいずれも真であるとします。このとき、選言除去より\(R\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}
P\rightarrow R,\ Q\rightarrow R\ \models \ \left( P\vee Q\right) \rightarrow
R
\end{equation*}が成り立ちます。

 

選言除去の一般化

論理式\(A_{1},\cdots ,A_{n},B\)をそれぞれ任意に選ぶと、先と同様の同値変形により、

\begin{equation*}
\left( A_{1}\rightarrow B\right) \wedge \cdots \wedge \left(
A_{n}\rightarrow B\right) \wedge \left( \bigvee_{i=1}^{n}A_{i}\right)
\Rightarrow B
\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*}
証明を見る(プレミアム会員限定)
例(選言除去)
命題変数\(P,Q,R\)に関する以下の推論\begin{equation*}
P\rightarrow S,\ Q\rightarrow S,\ R\rightarrow S\ \therefore \ \left( P\vee
Q\vee R\right) \rightarrow S
\end{equation*}について考えます。含意導入より、上の推論の妥当性を示す代わりに、以下の推論\begin{equation*}
P\rightarrow S,\ Q\rightarrow S,\ R\rightarrow S,\ P\vee Q\vee R\ \therefore
\ S
\end{equation*}の妥当性を示しても問題ありません。\(P\rightarrow S\)と\(Q\rightarrow S\)と\(R\rightarrow S\)と\(P\vee Q\vee R\)がいずれも真であるとします。このとき、選言除去より\(S\)は真であるため、先の推論が妥当であることが示されました。つまり、\begin{equation*}
P\rightarrow S,\ Q\rightarrow S,\ R\rightarrow S\ \models \ \left( P\vee
Q\vee R\right) \rightarrow S
\end{equation*}が成り立ちます。

次回は選言導入と呼ばれる推論規則について学びます。
次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)

Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

命題論理
アカウント
ログイン