ベキ等律
論理式\(A\)が任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で表記します。すると命題論理における\(\wedge \)に関するベキ等律より、\begin{equation*}
\overline{A}\wedge \overline{A}\Leftrightarrow \overline{A}
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
\left( a\right) \ A\wedge A\Leftrightarrow A
\end{equation*}が成り立つことが示されました。\(\left( a\right) \)において\(\wedge \)を\(\vee \)に置き換えると、\begin{equation*}
\left( b\right) \ A\vee A\Leftrightarrow A
\end{equation*}を得ますが、これが成り立つことも同様にして示されます。つまり、述語論理においても論理積や論理和についてベキ等律(idempotent law)が成り立つということです。
& \left( a\right) \ A\wedge A\Leftrightarrow A \\
& \left( b\right) \ A\vee A\Leftrightarrow A
\end{align*}
ベキ等律と\(\Leftrightarrow \)の推移律より、任意の論理式\(A\)に対して、\begin{equation*}
\left( c\right) \ A\wedge A\Leftrightarrow A\vee A
\end{equation*}という関係もまた成立します。つまり、同一の論理積どうしの論理積と論理和は論理的に同値です。
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\end{equation*}が成り立ちます。
\forall y\ P\left( x,y\right) \wedge \forall y\ P\left( x,y\right)
\Leftrightarrow \forall y\ P\left( x,y\right)
\end{equation*}が成り立ちます。
\forall x\ P\left( x\right) &\Leftrightarrow &\forall x\ \left( P\left(
x\right) \wedge P\left( x\right) \right) \\
&\Leftrightarrow &\forall x\ \left( P\left( x\right) \vee P\left( x\right)
\right)
\end{eqnarray*}が成り立ちます。
A &\Leftrightarrow &A\wedge A\quad \because \text{ベキ等律} \\
&\Leftrightarrow &\left( A\wedge A\right) \wedge A\quad \because \text{ベキ等律} \\
&\Leftrightarrow &A\wedge \left( A\wedge A\right) \quad \because \text{ベキ等律}
\end{eqnarray*}が成り立ちます。また、\begin{eqnarray*}
A &\Leftrightarrow &A\vee A\quad \because \text{ベキ等律} \\
&\Leftrightarrow &\left( A\vee A\right) \vee A\quad \because \text{ベキ等律} \\
&\Leftrightarrow &A\vee \left( A\vee A\right) \quad \because \text{ベキ等律}
\end{eqnarray*}が成り立ちます。さらに、\(\Leftrightarrow \)の推移律より、ここに登場したすべての論理式は論理的に同値です。
\left( \left( P\left( x\right) \vee P\left( x\right) \right) \wedge P\left(
x\right) \right) \vee \left( P\left( x\right) \wedge \left( P\left( x\right)
\vee P\left( x\right) \right) \right) \Leftrightarrow P\left( x\right)
\end{equation*}が成り立ちます。実際、\begin{eqnarray*}
\left( \left( P\left( x\right) \vee P\left( x\right) \right) \wedge P\left(
x\right) \right) \vee \left( P\left( x\right) \wedge \left( P\left( x\right)
\vee P\left( x\right) \right) \right) &\Leftrightarrow &\ \left( P\left(
x\right) \wedge P\left( x\right) \right) \vee \left( P\left( x\right) \wedge
P\left( x\right) \right) \quad \because \text{ベキ等律} \\
&\Leftrightarrow &\ P\left( x\right) \vee P\left( x\right) \quad \because
\text{ベキ等律} \\
\ &\Leftrightarrow &\ P\left( x\right) \quad \because \text{ベキ等律}
\end{eqnarray*}となります。
ベキ等律の一般化
論理式\(A\)に対して、論理積\(\wedge \)のベキ等律より、\begin{equation*}
\left( A\wedge A\right) \wedge A\Leftrightarrow A\wedge \left( A\wedge
A\right)
\end{equation*}が成り立ちます。つまり、3つの\(A\)の間にある2つの\(\wedge \)のどちらを最初に作用させても最終的に得られる論理式は論理的に同値です。そこで、これら 2 つの論理式を区別せずに\(A\wedge A\wedge A\)で表します。論理和\(\vee \)についても同様に考えると、\(\left( A\vee A\right) \vee A\)と\(A\vee \left( A\vee A\right) \)を区別せずに\(A\vee A\vee A\)で表します。
4つの\(A\)に関しても、それらの間にある3つの\(\wedge \)のどれを最初に作用させるかという問題がありますが、\(\wedge \)に関するベキ等律を繰り返し適用することにより、\begin{align*}
\left( \left( A\wedge A\right) \wedge A\right) \wedge A& \Leftrightarrow
\left( A\wedge \left( A\wedge A\right) \right) \wedge A\quad \because \text{ベキ等律} \\
& \Leftrightarrow A\wedge \left( \left( A\wedge A\right) \wedge A\right)
\quad \because \text{ベキ等律} \\
& \Leftrightarrow A\wedge \left( A\wedge \left( A\wedge A\right) \right)
\quad \because \text{ベキ等律}
\end{align*}が成立するため、\(\wedge \)の作用の順番に関わらず同値な命題が得られます。したがって、これら 4 つの論理積を区別せずに\(A\wedge A\wedge A\wedge A\)で表します。論理和についても同様に考えると、上と同様の4つの論理和を区別せずに\(A\vee A\vee A\vee A\)で表します。
任意個の論理式\(A\)の論理積についても同様の議論が成立します。つまり、有限\(n\)個の論理式\(A\)の間にある\(n-1\)個の\(\wedge \)の中のどれを最初に作用させる場合でも、最終的に得られる論理式はいずれも同値であるため、それらの論理積を区別せずに、\begin{equation*}
\bigwedge\limits_{i=1}^{n}A=A\wedge \cdots \wedge A
\end{equation*}で表します。論理和についても同様に考えることで、\begin{equation*}
\bigvee\limits_{i=1}^{n}A=A\vee \cdots \vee A
\end{equation*}で表します。
次回は交換律について学びます。
質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定) 次へ進む
プレミアム会員だけが質問やコメントを投稿・閲覧できます。