命題論理における結合律

結合律

論理式\(A,B,C\)を任意に選んだとき、論理積\(\wedge \)と論理和\(\vee \)に関して以下の恒真式\begin{align*}& \left( a\right) \ (A\wedge B)\wedge C\Leftrightarrow A\wedge \left(
B\wedge C\right) \\
& \left( b\right) \ (A\vee B)\vee C\Leftrightarrow A\vee \left( B\vee
C\right)
\end{align*}が成り立ちます。以上の性質を結合律（associative law）と呼びます。

論理式\(A,B,C\)が与えられたとき、隣り合う\(A,B\)に対して論理積\(\wedge \)を作用させれば\(A\wedge B\)を得ます。これは論理式であるため、これと残された\(C\)に対して再び論理積\(\wedge \)を作用させれば\((A\wedge B)\wedge C\)という論理式を得ます。一方、最初に\(B,C\)に対して\(\wedge \)を作用させれば最終的に\(A\wedge \left( B\wedge C\right) \)という論理式を得ます。この2つの論理式の値が一致するというのが\(\left( a\right) \)の主張です。また、論理和\(\vee \)に関する同様の主張が\(\left(b\right) \)です。

論理式\(A,B,C\)が任意に与えられたとき、\(\wedge \)の結合律より、\begin{equation*}\left( A\wedge B\right) \wedge C\Leftrightarrow A\wedge \left( B\wedge
C\right)
\end{equation*}が成り立つことが明らかになりました。つまり、\(\left( A\wedge B\right) \wedge C\)と\(A\wedge \left( B\wedge C\right) \)の真理値は常に一致するため両者を区別する必要はなく、これらをまとめて、\begin{equation*}A\wedge B\wedge C
\end{equation*}と表記できるものと定めます。同様に、\(\vee \)の結合律より、\begin{equation*}\left( A\vee B\right) \vee C\Leftrightarrow A\vee \left( B\vee C\right)
\end{equation*}が成り立つため、\(\left(A\vee B\right) \vee C\)と\(A\vee \left( B\vee C\right) \)を区別する必要はなく、これらをまとめて、\begin{equation*}A\vee B\vee C
\end{equation*}と表記できるものと定めます。

結合律の一般化

4つの論理式\(A,B,C,D\)が与えられたとき、\(\wedge \)に関する結合律を繰り返し適用することにより、\begin{align*}\left( \left( A\wedge B\right) \wedge C\right) \wedge D& \Leftrightarrow
\left( A\wedge \left( B\wedge C\right) \right) \wedge D\quad \because \text{結合律} \\
& \Leftrightarrow A\wedge \left( \left( B\wedge C\right) \wedge D\right)
\quad \because \text{結合律} \\
& \Leftrightarrow A\wedge \left( B\wedge \left( C\wedge D\right) \right)
\quad \because \text{結合律}
\end{align*}を得ます。つまり、4つの論理式\(A,B,C,D\)の間にある3個の\(\wedge \)の中のどれを最初に作用させる場合でも、最終的に得られる論理式はいずれも同値であるため、これら4つの論理式を区別せずに、\begin{equation*}A\wedge B\wedge C\wedge D
\end{equation*}で表記します。論理和についても、\begin{align*}
\left( \left( A\vee B\right) \vee C\right) \vee D& \Leftrightarrow \left(
A\vee \left( B\vee C\right) \right) \vee D\quad \because \text{結合律} \\
& \Leftrightarrow A\vee \left( \left( B\vee C\right) \vee D\right) \quad
\because \text{結合律} \\
& \Leftrightarrow A\vee \left( B\vee \left( C\vee D\right) \right) \quad
\because \text{結合律}
\end{align*}が成り立つため、これら4つの論理式を区別せずに、\begin{equation*}
A\vee B\vee C\vee D
\end{equation*}で表記します。

任意の有限個の論理積についても同様の議論が成立します。つまり、有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)の間にある\(n-1\)個の\(\wedge \)の中のどれを最初に作用させる場合でも、最終的に得られる論理式はいずれも同値であるため、それらの論理積を区別せずに、\begin{equation}\bigwedge\limits_{i=1}^{n}A_{i}=A_{1}\wedge \cdots \wedge A_{n} \quad \cdots (1)
\end{equation}で表記します。論理和についても同様です。有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)の間にある\(n-1\)個の\(\vee \)の中のどれを最初に作用させる場合でも、最終的に得られる論理式はいずれも同値であるため、それらの論理和を区別せずに、\begin{equation}\bigvee\limits_{i=1}^{n}A_{i}=A_{1}\vee \cdots \vee A_{n} \quad \cdots (2)
\end{equation}で表記します。

交換律と結合律の一般化

3つの論理式\(A,B,C\)が任意に与えられたとき、\(\wedge \)に関する交換律を繰り返し適用することにより、\begin{eqnarray*}\left( A\wedge B\right) \wedge C &\Leftrightarrow &\left( B\wedge A\right)
\wedge C\quad \because \text{交換律} \\
&\Leftrightarrow &C\wedge \left( B\wedge A\right) \quad \because \text{交換律} \\
&\Leftrightarrow &C\wedge \left( A\wedge B\right) \quad \because \text{交換律}
\end{eqnarray*}を得ます。つまり、3つの論理式\(A,B,C\)の論理積をとる場合、括弧が指定するように、\(A\)と\(B\)に優先的に論理積を作用させる形で同値変形を行う限りにおいて、論理式の順序を自由に入れ替えても論理式の値は変わりません。同様に、\begin{eqnarray*}A\wedge \left( B\wedge C\right) &\Leftrightarrow &A\wedge \left( C\wedge
B\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( C\wedge B\right) \wedge A\quad \because \text{交換律} \\
&\Leftrightarrow &\left( B\wedge C\right) \wedge A\quad \because \text{交換律}
\end{eqnarray*}を得ます。つまり、3つの論理式\(A,B,C\)の論理積をとる場合、括弧が指定するように、\(B\)と\(C\)に優先的に論理積を作用させる形で同値変形を行う限りにおいて、論理式の順序を自由に入れ替えても論理式の値は変わりません。加えて、結合律より、\begin{equation*}\left( A\wedge B\right) \wedge C\Leftrightarrow A\wedge \left( B\wedge
C\right)
\end{equation*}が成り立つため、以上の8個の論理式がすべて論理的に同値であることが保証されます。つまり、3個の論理式\(A,B,C\)の論理積をとる場合には、論理式の相対的な順番を自由に入れ替えられるとともに、論理積を作用させる順番も自由に選ぶことができます。したがって、以下の関係\begin{eqnarray*}A\wedge B\wedge C &\Leftrightarrow &A\wedge C\wedge B \\
&\Leftrightarrow &B\wedge A\wedge C \\
&\Leftrightarrow &B\wedge C\wedge A \\
&\Leftrightarrow &C\wedge A\wedge B \\
&\Leftrightarrow &C\wedge B\wedge A
\end{eqnarray*}が成り立ちます。論理和についても同様です。つまり、3個の論理式\(A,B,C\)の論理和をとる場合には、論理式の相対的な順番を自由に入れ替えられるとともに、論理和を作用させる順番も自由に選ぶことができます。したがって、以下の関係\begin{eqnarray*}A\vee B\vee C &\Leftrightarrow &A\vee C\vee B \\
&\Leftrightarrow &B\vee A\vee C \\
&\Leftrightarrow &B\vee C\vee A \\
&\Leftrightarrow &C\vee A\vee B \\
&\Leftrightarrow &C\vee B\vee A
\end{eqnarray*}が成り立ちます。

任意の有限個の論理積についても同様の議論が成立します。つまり、有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)の論理積をとる場合には、交換律より、論理式の順序を自由に入れ替えることができ、結合律より、括弧の位置を自由に変えることができます。その結果、論理式の相対的な順番を入れ替えても、また、論理積を作用させる順番を変えても、最終的に得られる論理式はいずれも、\begin{equation*}\bigwedge\limits_{i=1}^{n}A_{i}
\end{equation*}と論理的に同値になります。論理和についても同様です。有限\(n\)個の論理式\(A_{1},\cdots ,A_{n}\)の論理和をとる場合には、論理式の相対的な順番を入れ替えても、また、論理和を作用させる順番を変えても、最終的に得られる論理式はいずれも、\begin{equation*}\bigvee\limits_{i=1}^{n}A_{i}
\end{equation*}と論理的に同値になります。

演習問題