教材一覧
PREDICATE LOGIC

矛盾律

< 前のページ
次のページ >

矛盾律

論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。すると矛盾律より、恒偽式\(\bot \)との間に、\begin{equation*}
\overline{A}\wedge \lnot \overline{A}\Leftrightarrow \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*}
P\left( x\right) \wedge \lnot P\left( x\right) \Leftrightarrow \bot
\end{equation*}が成り立ちます。例えば、\begin{equation*}
P\left( x\right) :x\text{は}2\text{で割り切れる}
\end{equation*}と定義すると、\begin{equation*}
P\left( x\right) \wedge \lnot P\left( x\right) :x\text{は}2\text{で割り切れると同時に}2\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) \wedge \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) \wedge \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)
\wedge \lnot \left( P\left( x\right) \wedge Q\left( x,y\right) \right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\bot \quad \because \text{矛盾律}
\end{eqnarray*}となります。
例(矛盾律)
実数\(x,y\in \mathbb{R}\)を任意に選んだとき、大小関係\(\leq \)と狭義大小関係\(<\)と相等関係\(=\)の間には、\begin{equation}
x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right) \quad\cdots (1)
\end{equation}という関係が成り立つものとします。このとき、\begin{equation*}
\forall x,y,z\in \mathbb{R}:\left( x<y\Rightarrow x+z<y+z\right)
\end{equation*}が成り立つことを証明します。\(x<y\)を満たす実数\(x,y\in \mathbb{R}\)を任意に選びます。さらに実数\(z\in \mathbb{R}\)を任意に選ぶと、\begin{eqnarray*}
x<y &\Leftrightarrow &\left( x\leq y\wedge x\not=y\right) \quad \because
\left( 1\right) \\
&\Rightarrow &x\leq y \\
&\Rightarrow &x+z\leq y+z
\end{eqnarray*}となるため\(x+z\leq y+z\)が成り立ちます。続いて、\(x+z\not=y+z\)であることを示すために\(x+z=y+z\)を仮定して矛盾を導きます。両辺に\(-z\)を加えると、\begin{equation*}
x+z+\left( -z\right) =y+z+\left( -z\right)
\end{equation*}すなわち\(x=y\)が成り立ちます。仮定より\(x<y\)もまた成り立つため、このとき、\begin{eqnarray*}
x<y\wedge x=y &\Leftrightarrow &\left( x\leq y\wedge x\not=y\right) \wedge
x=y\quad \because \left( 1\right) \\
&\Leftrightarrow &x\leq y\wedge \left( x\not=y\wedge x=y\right) \quad
\because \text{結合律} \\
&\Leftrightarrow &x\leq y\wedge \bot \quad \because \text{矛盾律} \\
&\Leftrightarrow &\bot
\end{eqnarray*}となり矛盾です。したがって、\(x+z\not=y+z\)であることが示されました。以上で\(x+z\leq y+z\)と\(x+z\not=y+z\)が示されましたが、\(\left( 1\right) \)より、これは\(x+z<y+z\)を意味します。

 

非矛盾律

繰り返しになりますが、矛盾律より、任意の論理式\(A\)と恒偽式\(\bot \)の間には、\begin{equation}
A\wedge \lnot A\Leftrightarrow \bot \quad\cdots (1)
\end{equation}という関係が成り立ちます。このとき、\begin{eqnarray*}
\lnot \left( A\wedge \lnot A\right) &\Leftrightarrow &\lnot \left( \bot
\right) \quad \because \left( 1\right) \\
&\Leftrightarrow &\top
\end{eqnarray*}すなわち、\begin{equation}
\lnot \left( A\wedge \lnot A\right) \Leftrightarrow \top \quad\cdots (2)
\end{equation}が成り立ちます。逆に\(\left( 2\right) \)から\(\left( 1\right) \)を導くこともできるため、\(\left( 1\right) \)と\(\left( 2\right) \)は交換可能です。\(\left( 2\right) \)を非矛盾律(law of non-contradiction)や無矛盾律などと呼びます。矛盾律と非矛盾律は実質的に同じであるため、どちらを採用しても問題ありません。

命題(非矛盾律)
任意の論理式\(A\)と恒真式\(\top \)について、\begin{equation*}
\lnot \left( A\wedge \lnot A\right) \Leftrightarrow \top
\end{equation*}が成り立つ。
証明を見る(プレミアム会員限定)

次回は排中律について学びます。

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

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

述語論理