WIIS

述語論理

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

目次

Mailで保存
Xで共有

選言導入

論理式\(A,B\)をそれぞれ任意に選んだときに、\begin{eqnarray*}\left( a\right) \ A &\Rightarrow &A\vee B \\
\left( b\right) \ B &\Rightarrow &A\vee B
\end{eqnarray*}が成り立つことが示されるため、ここから以下の推論規則を得ます。

命題(選言導入)
任意の論理式\(A,B\)に対して、\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\)から得られる命題が真になることが保証されます。以上の推論規則を選言導入(disjunctionintroduction)や\(\vee \)導入(\(\vee \)introduction)などと呼びます。

例(選言導入)
命題関数\(P\left( x\right) ,Q\left( x\right) \)がそれぞれ任意に与えられたとき、選言導入より、\begin{eqnarray*}&&\left( a\right) \ P\left( x\right) \ \models \ P\left( x\right) \vee
Q\left( x\right) \\
&&\left( b\right) \ Q\left( x\right) \ \models \ P\left( x\right) \vee
Q\left( x\right)
\end{eqnarray*}が成り立ちます。

例(選言導入)
以下の推論について考えます。\begin{eqnarray*}
&&\text{任意の偶数は}2\text{で割り切れる} \\
&&\text{ゆえに、任意の偶数は}2\text{または}3\text{で割り切れる}
\end{eqnarray*}ただし、変数\(x\)の定義域はすべての整数からなる集合\(\mathbb{Z} \)です。以下の命題関数\begin{eqnarray*}P\left( x\right) &:&x\text{は}2\text{で割り切れる} \\
Q\left( x\right) &:&x\text{は}3\text{で割り切れる}
\end{eqnarray*}を定義すると、先の推論は、\begin{equation*}
\forall x\in \mathbb{Z} :P\left( x\right) \ \therefore \ \forall x\in \mathbb{Z} :\left( P\left( x\right) \vee Q\left( x\right) \right)
\end{equation*}と定式化されます。推論の前提に全称除去を適用すると、\begin{equation*}
P\left( c\right)
\end{equation*}を得ます。これに選言導入を適用すると、\begin{equation*}
P\left( c\right) \vee Q\left( c\right)
\end{equation*}を得ます。さらにこれに全称導入を適用すると、\begin{equation*}
\forall x\in \mathbb{Z} :\left( P\left( x\right) \vee Q\left( x\right) \right)
\end{equation*}を得るため、推論が妥当であることが示されました。

 

選言導入の一般化

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

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

証明

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

上の命題において\(n=2\)とおくと、\begin{eqnarray*}A_{1}\ &\models &\ A_{1}\vee A_{2} \\
A_{2}\ &\models &\ A_{1}\vee A_{2}
\end{eqnarray*}などが得られますが、これは先に示した選言導入に他なりません。

例(選言導入)
命題関数\(P_{1}\left( x\right) ,\cdots ,P_{n}\left(x\right) \)がそれぞれ任意に与えられたとき、先の命題より、\begin{equation*}P_{j}\left( x\right) \ \models \ \bigvee_{i=1}^{n}P_{i}\left( x\right) \quad
\left( j=1,\cdots ,n\right)
\end{equation*}が成り立ちます。

 

演習問題

問題(選言導入)
任意の論理式\(A,B,C,D\)に関して、\begin{equation*}\left( A\vee B\vee C\right) \rightarrow D\ \models \ A\rightarrow D
\end{equation*}が成り立つことを示してください。

証明

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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