論理式 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
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

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

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

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

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

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

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