教材一覧
教材一覧
教材検索

述語論理

述語論理における選言除去

目次

Twitterで共有
メールで共有

選言除去

論理式\(A,B,C\)をそれぞれ任意に選んだときに、\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)などと呼びます。

例(選言除去)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)および\(R\left( x\right) \)がそれぞれ任意に与えられたとき、選言除去より、\begin{equation*}P\left( x\right) \rightarrow R\left( x\right) ,\ Q\left( x\right)
\rightarrow R\left( x\right) ,\ P\left( x\right) \vee Q\left( x\right) \
\models \ R\left( x\right)
\end{equation*}が成り立ちます。

例(選言除去)
以下の推論について考えます。\begin{eqnarray*}
&&\text{任意の整数}x\text{について、}x\text{が奇数ならば}x^{2}+x\text{は偶数である} \\
&&\text{任意の整数}x\text{について、}x\text{が偶数ならば}x^{2}+x\text{は偶数である} \\
&&\text{任意の整数}x\text{は奇数または偶数である} \\
&&\text{したがって、任意の整数}x\text{について}x^{2}+x\text{は偶数である}
\end{eqnarray*}ただし、変数\(x\)の定義域はすべての整数からなる集合\(\mathbb{Z} \)です。以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は奇数である}
\\
Q\left( x\right) &:&x\text{は偶数である}
\\
R\left( x\right) &:&x^{2}+x\text{は偶数である}
\end{eqnarray*}を定義すると、先の推論は、\begin{eqnarray*}
\forall x &\in &\mathbb{Z} :\left( P\left( x\right) \rightarrow R\left( x\right) \right) , \\
\forall x &\in &\mathbb{Z} :\left( Q\left( x\right) \rightarrow R\left( x\right) \right) , \\
\forall x &\in &\mathbb{Z} :\left( P\left( x\right) \vee Q\left( x\right) \right) \\
&\therefore &\ \forall x\in \mathbb{Z} :R\left( x\right)
\end{eqnarray*}と定式化されます。推論の前提に全称除去を適用すると、\begin{eqnarray*}
&&P\left( c\right) \rightarrow R\left( c\right) \\
&&Q\left( c\right) \rightarrow R\left( c\right) \\
&&P\left( c\right) \vee Q\left( c\right)
\end{eqnarray*}を得ます。これらに選言除去を適用すると、\begin{equation*}
R\left( c\right)
\end{equation*}を得て、さらにこれに全称導入を適用すると、\begin{equation*}
\forall x\in \mathbb{Z} :R\left( x\right)
\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*}が成り立ちます。

Twitterで共有
メールで共有
DISCUSSION

質問とコメント