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

述語論理

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

目次

Twitterで共有
メールで共有

連言除去

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

命題(連言除去)
任意の論理式\(A,B\)に対して、\begin{eqnarray*}&&\left( a\right) \ A\wedge B\ \models \ A \\
&&\left( b\right) \ A\wedge B\ \models \ B
\end{eqnarray*}が成り立つ。

証明

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

上の命題より、解釈を任意に選んだとき、\(A\wedge B\)から得られる命題が真である場合、\(A\)から得られる命題や\(B\)から得られる命題がいずれも真になることが保証されます。以上の推論規則を連言除去(conjunction elimination)や\(\wedge \)除去(\(\wedge \) elimination)、簡単化(conjunction elimination)などと呼びます。

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

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

 

連言除去の一般化

連言除去は以下のような形で一般化可能です。

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

証明

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

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

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

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

Twitterで共有
メールで共有
DISCUSSION

質問とコメント