WIIS

述語論理

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

目次

Mailで保存
Xで共有

選言除去

論理式\(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*}が成り立ちます。

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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