論理式\(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 つの論理式の値が一致するというのが結合律の主張です。
< 前のページ
次のページ >

結合律

論理式\(A,B,C\)を任意に選んだとき、以下の真理値表が得られます。
$$\begin{array}{ccccc}
\hline
A & B & C & (A\wedge B)\wedge C & A\wedge (B\wedge C) \\ \hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 0 & 0 \\ \hline
1 & 0 & 1 & 0 & 0 \\ \hline
1 & 0 & 0 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 0 \\ \hline
0 & 1 & 0 & 0 & 0 \\ \hline
0 & 0 & 1 & 0 & 0 \\ \hline
0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:結合律

つまり、任意の解釈のもとで\((A\wedge B)\wedge C\)と\(A\wedge (B\wedge C)\)の値は一致するため、\begin{equation*}
\left( a\right) \ (A\wedge B)\wedge C\Leftrightarrow A\wedge \left( B\wedge
C\right)
\end{equation*}が成り立ちます。論理式\(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) \)の主張であり、これを\(\wedge \)に関する結合律(associative law)と呼びます。

論理和\(\vee \)に関しても同様の議論が成り立ちます。つまり、\(\vee \)に関する結合律は、\begin{equation*}
\left( b\right) \ (A\vee B)\vee C\Leftrightarrow A\vee \left( B\vee C\right)
\end{equation*}となりますが、これもまた成り立ちます。

命題(結合律)
任意の論理式\(A,B,C\)に対して以下が成り立つ。\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*}
証明を見る(プレミアム会員限定)
例(結合律)
任意の命題変数\(P,Q,R,S\)について、\begin{eqnarray*}
\left( \left( P\wedge Q\right) \wedge R\right) \wedge S &\Leftrightarrow &\
\left( P\wedge \left( Q\wedge R\right) \right) \wedge S\quad \because \text{結合律} \\
&\Leftrightarrow &\ P\wedge \left( \left( Q\wedge R\right) \wedge S\right)
\quad \because \text{結合律} \\
&\Leftrightarrow &\ P\wedge \left( Q\wedge \left( R\wedge S\right) \right)
\quad \because \text{結合律}
\end{eqnarray*}が成り立ちます。
例(結合律)
任意の命題変数\(P,Q,R\)について、\begin{equation*}
\left( P\vee Q\right) \vee \left( P\vee R\right) \Leftrightarrow P\vee
\left( Q\vee R\right)
\end{equation*}が成り立つことを証明します。実際、\begin{eqnarray*}
\left( P\vee Q\right) \vee \left( P\vee R\right) &\Leftrightarrow &P\vee
\left( Q\vee \left( P\vee R\right) \right) \quad \because \text{結合律} \\
&\Leftrightarrow &P\vee \left( \left( Q\vee P\right) \vee R\right) \quad
\because \text{結合律} \\
&\Leftrightarrow &P\vee \left( \left( P\vee Q\right) \vee R\right) \quad
\because \text{交換律} \\
&\Leftrightarrow &P\vee \left( P\vee \left( Q\vee R\right) \right) \quad
\because \text{結合律} \\
&\Leftrightarrow &\left( P\vee P\right) \vee \left( Q\vee R\right) \quad
\because \text{結合律} \\
&\Leftrightarrow &P\vee \left( Q\vee R\right) \quad \because \text{ベキ等律}
\end{eqnarray*}となります。

 

結合律の一般化

論理式\(A,B,C\)に対して、\(\wedge \)の結合律より、\begin{equation*}
(A\wedge B)\wedge C\Leftrightarrow A\wedge \left( B\wedge C\right)
\end{equation*}が成り立ちます、これは\(A,B,C\)の間にある 2 つの\(\wedge \)のどちらを最初に作用させても最終的に得られる論理式は同値であることを意味します。そこで、これら 2 つの論理式を区別せずに\(A\wedge B\wedge C\)で表します。論理和についても同様に考えると、\((A\vee B)\vee C\)と\(A\vee \left( B\vee C\right) \)を区別せずに\(A\vee B\vee C\)で表します。

論理式\(A,B,C,D\)に対して、隣り合う論理式の間にある 3 つの\(\wedge \)の中のどれを最初に作用させるかという問題に対しても、\(\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*}が成立するため、\(\wedge \)の作用の順番に関わらず同値な命題が得られます。したがって、これら 4 つの論理積を区別せずに\(A\wedge B\wedge C\wedge D\)で表します。論理和についても同様に考えると、上と同様な 4 つの論理和を区別せずに\(A\vee B\vee C\vee D\)で表します。

任意の有限個の論理積についても同様の議論が成立します。つまり、有限\(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} \tag{1}
\end{equation}で表します。論理和についても同様に考えることで、\begin{equation}
\bigvee\limits_{i=1}^{n}P_{i}=A_{1}\vee \cdots \vee A_{n} \tag{2}
\end{equation}で表します。

結合律に加えて交換律が成り立つ場合には、\(\left( 1\right) \)や\(\left( 2\right) \)において論理式\(A_{1},\cdots ,A_{n}\)の順番を自由に入れ替えても、その前後の論理式は論理的に同値であることが保証されます。

 

他の論理演算に関する結合律

排他的論理和\(\veebar \)に関する結合律は、任意の論理式\(A,B,C\)に対して、\begin{equation*}
\left( A\veebar B\right) \veebar C\ \Leftrightarrow \ A\veebar \left(
B\veebar C\right)
\end{equation*}が成り立つものとして定義されますが、以下の真理値表より、これは成り立ちます。
$$\begin{array}{ccccc}
\hline
A & B & C & (A\veebar B)\veebar C & A\veebar (B\veebar C) \\ \hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 0 & 0 \\ \hline
1 & 0 & 1 & 0 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 & 0 \\ \hline
0 & 1 & 0 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:結合律

含意\(\rightarrow \)に関する結合律は、任意の論理式\(A,B,C\)に対して、\begin{equation*}
\left( A\rightarrow B\right) \rightarrow C\ \Leftrightarrow \ A\rightarrow
\left( B\rightarrow A\right)
\end{equation*}が成り立つものとして定義されますが、これは成り立ちません。実際、\(\rightarrow \)の定義より、\(A\)の値が\(0\)、\(B\)の値が\(1\)、\(C\)の値が\(0\)のとき、\(\left( A\rightarrow B\right) \rightarrow C\)の値は\(0\)ですが、\(A\rightarrow \left( B\rightarrow A\right) \)の値は\(1\)です。

同等\(\leftrightarrow \)に関する結合律は、任意の\(A,B,C\)に対して、\begin{equation*}
\left( A\leftrightarrow B\right) \leftrightarrow C\ \Leftrightarrow \
A\leftrightarrow \left( B\leftrightarrow C\right)
\end{equation*}と定義されますが、以下の真理値表より、これは成り立ちます。
$$\begin{array}{ccccc}
\hline
A & B & C & (A\leftrightarrow B)\leftrightarrow C & A\leftrightarrow (B\leftrightarrow C) \\ \hline
1 & 1 & 1 & 1 & 1 \\ \hline
1 & 1 & 0 & 0 & 0 \\ \hline
1 & 0 & 1 & 0 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 & 0 \\ \hline
0 & 1 & 0 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:結合律

次回は分配律について学びます。
次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)

Share on facebook
Share on twitter
Share on email
Share on print
< 前のページ
次のページ >

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するためにはログインが必要です
ログイン

命題論理
アカウント
ログイン