WIIS

教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における排中律

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

排中律

論理式\(A\)と恒真式\(\top \)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(\top \)から得られる命題を\(\overline{\top }\)でそれぞれ表記します。すると命題論理における排中律より、\begin{equation*}\overline{A}\vee \lnot \overline{A}\Leftrightarrow \overline{\top }
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
A\vee \lnot A\Leftrightarrow \top
\end{equation*}が成り立つことが示されました。つまり、述語論理においても排中律(law of excluded middle)が成り立つということです。

命題(排中律)
任意の論理式\(A\)と恒真式\(\top \)の間には、\begin{equation*}A\vee \lnot A\Leftrightarrow \top
\end{equation*}が成り立つ。

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。排中律は\(\overline{A}\vee \lnot \overline{A}\)が任意の解釈において真であること、すなわち\(\overline{A}\)と\(\lnot \overline{A}\)の少なくとも一方が真であることを意味しますが、否定の定義より\(\overline{A}\)と\(\lnot \overline{A}\)の真理値は常に逆転しているため、これは\(\overline{A}\)が真もしくは偽のどちらか一方であることを意味します。ゆえに排中律とは、論理式から生成される命題が真か偽のどちらか一方であり、真と偽の中間の状態は起こり得ないという主張です。以上が排中律と呼ばれる理由です。

例(排中律)
命題関数\(P\left( x\right) \)を、\begin{equation*}x\text{は}2\text{で割り切れる}
\end{equation*}と定義します。ただし、\(x\)の定義域はすべての自然数からなる集合です。論理式\(P\left(x\right) \vee \lnot P\left( x\right) \)は、\begin{equation*}x\text{は}2\text{で割り切れるか割り切れないかの少なくとも一方である}
\end{equation*}となりますが、排中律より、これは任意の自然数\(x\)について真です。
例(排中律)
命題関数\(P\left( x,y\right) \)を、\begin{equation*}x\text{は}y\text{と知り合いである}
\end{equation*}と定義します。ただし、\(x,y\)の定義はともにある街の住人からなる集合です。論理式\(P\left( x,y\right) \vee \lnot P\left( x,y\right) \)は、\begin{equation*}x\text{は}y\text{と知り合いであるか知り合いでないかの少なくとも一方である}
\end{equation*}となりますが、排中律より、これは任意の住人\(x,y\)について真です。
例(排中律)
命題関数\(P\left( x\right) \)と\(Q\left( x\right) \)がそれぞれ任意に与えられたとき、\begin{equation*}\left( P\left( x\right) \wedge Q\left( x\right) \right) \vee \left( \lnot
P\left( x\right) \vee \lnot Q\left( x\right) \right)
\end{equation*}は恒真式です。実際、この論理式を同値変形すると、\begin{eqnarray*}
&&\left( P\left( x\right) \wedge Q\left( x\right) \right) \vee \left( \lnot
P\left( x\right) \vee \lnot Q\left( x\right) \right) \\
&\Leftrightarrow &\left( P\left( x\right) \wedge Q\left( x\right) \right)
\vee \lnot \left( P\left( x\right) \wedge Q\left( x\right) \right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\top \quad \because \text{排中律}
\end{eqnarray*}となります。

 

演習問題

問題(排中律)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)が任意に与えられたとき、以下の論理式\begin{equation*}\forall x\in X:\left( P\left( x\right) \vee \lnot P\left( x\right) \right)
\end{equation*}は恒真式、恒偽式、事実式のどれでしょうか。議論してください。

解答を見る

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

問題(排中律)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)が任意に与えられたとき、以下の論理式\begin{equation*}\exists x\in X:\left( P\left( x\right) \vee \lnot P\left( x\right) \right)
\end{equation*}は恒真式、恒偽式、事実式のどれでしょうか。議論してください。

解答を見る

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

排中律
命題論理における排中律

任意の論理式から排中律と呼ばれる恒真式を構成できます。これは、論理式はそれぞれの解釈において真か偽のどちらか一方であるという主張です。状況によっては排中律が成り立たないように思われますが、この問題を解決する手法としてファジィ理論や述語論理などがあります。

DISCUSSION

質問とコメント

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

述語論理