WIIS

述語論理

述語論理における矛盾律

目次

関連知識

Mailで保存
Xで共有

矛盾律

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

命題(矛盾律)
任意の論理式\(A\)と恒偽式\(\bot \)の間には、\begin{equation*}A\wedge \lnot A\Leftrightarrow \bot
\end{equation*}が成り立つ。

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。矛盾律は\(\overline{A}\wedge \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) \wedge \lnot P\left( x\right) \)は、\begin{equation*}x\text{は}2\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) \wedge \lnot P\left( x,y\right) \)は、\begin{equation*}x\text{は}y\text{と知り合いであるとともに}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) \wedge \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) \wedge \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)
\wedge \lnot \left( P\left( x\right) \wedge Q\left( x\right) \right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\bot \quad \because \text{矛盾律}
\end{eqnarray*}となります。

 

非矛盾律

繰り返しになりますが、矛盾律より、任意の論理式\(A\)と恒偽式\(\bot \)の間には、\begin{equation*}A\wedge \lnot A\Leftrightarrow \bot
\end{equation*}という関係が成り立ちます。以上の事実を利用すると、\begin{equation*}
\lnot \left( A\wedge \lnot A\right) \Leftrightarrow \top
\end{equation*}を導くことができます。これを非矛盾律(law of non-contradiction)や無矛盾律などと呼びます。逆に、非矛盾律から矛盾律を導くこともできるため両者は必要十分です。

命題(非矛盾律)
論理式\(A\)と恒真式\(\top \)をそれぞれ任意に選んだとき、以下の2つは必要十分である。\begin{eqnarray*}&&\left( a\right) \ A\wedge \lnot A\Leftrightarrow \bot \\
&&\left( b\right) \ \lnot \left( A\wedge \lnot A\right) \Leftrightarrow \top
\end{eqnarray*}が成り立つ。

証明

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

 

演習問題

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

解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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