教材一覧
教材検索
PREDICATE LOGIC

排中律

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

排中律

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。すると排中律より、恒真式\(\top \)との間に、\begin{equation*}
\overline{A}\vee \lnot \overline{A}\Leftrightarrow \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*}
P\left( x\right) \vee \lnot P\left( x\right) \Leftrightarrow \top
\end{equation*}が成り立ちます。例えば、\begin{equation*}
P\left( x\right) :x\text{は素数である}
\end{equation*}と定義すると、\begin{equation*}
P\left( x\right) \vee \lnot P\left( x\right) :x\text{は素数または非素数である}
\end{equation*}となりますが、排中律より、この主張は任意の\(x\)について真です。
例(排中律)
命題関数\(P\left( x\right) \)と\(Q\left( x,y\right) \)について、\begin{equation*}
\left( P\left( x\right) \wedge Q\left( x,y\right) \right) \vee \left( \lnot
P\left( x\right) \vee \lnot Q\left( x,y\right) \right)
\end{equation*}は恒真式です。実際、この論理式を同値変形すると、\begin{eqnarray*}
&&\left( P\left( x\right) \wedge Q\left( x,y\right) \right) \vee \left(
\lnot P\left( x\right) \vee \lnot Q\left( x,y\right) \right) \\
&\Leftrightarrow &\left( P\left( x\right) \wedge Q\left( x,y\right) \right)
\vee \lnot \left( P\left( x\right) \wedge Q\left( x,y\right) \right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\top \quad \because \text{排中律}
\end{eqnarray*}となります。
例(排中律)
集合\(A,B,C\)をそれぞれ任意に選んだとき、\begin{equation*}
A=\left( A\cap B\right) \cup \left( A\backslash B\right)
\end{equation*}という関係が成り立つことを証明します。具体的には、任意の\(x\)について、\begin{eqnarray*}
x\in A &\Leftrightarrow &x\in A\wedge \top \\
&\Leftrightarrow &x\in A\wedge \left( x\in B\vee x\not\in B\right) \quad
\because \text{排中律} \\
&\Leftrightarrow &\left( x\in A\wedge x\in B\right) \vee \left( x\in A\wedge
x\not\in B\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\left( x\in A\cap B\right) \vee \left( x\in A\backslash
B\right) \quad \because \cap ,\backslash \text{の定義} \\
&\Leftrightarrow &x\in \left( A\cap B\right) \cup \left( A\backslash
B\right) \quad \because \cup \text{の定義}
\end{eqnarray*}が成り立つため、\begin{equation*}
A=\left( A\cap B\right) \cup \left( A\backslash B\right)
\end{equation*}が成り立つことが示されました。ここに登場した諸概念に馴染みがない場合には集合のセクションを参照してください。

次回は恒等律について学びます。

質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定) 次へ進む
< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

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

述語論理