教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における結合律

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

結合律

論理式\(A,B,C\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)で、\(C\)から得られる命題を\(\overline{C}\)でそれぞれ表記します。すると命題論理における\(\wedge \)に関する結合律より、\begin{align*}& \left( a\right) \ (\overline{A}\wedge \overline{B})\wedge \overline{C}\Leftrightarrow \overline{A}\wedge \left( \overline{B}\wedge \overline{C}\right) \\
& \left( b\right) \ (\overline{A}\vee \overline{B})\vee \overline{C}\Leftrightarrow \overline{A}\vee \left( \overline{B}\vee \overline{C}\right)
\end{align*}が成り立ちます。任意の解釈において同様の議論が成立するため、\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\)に対して、\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\left( x\right) \)と\(Q\left( x,y\right) \)と\(R\left( y\right) \)をそれぞれ任意に選んだとき、結合律より、\begin{equation*}\left( P\left( x\right) \wedge Q\left( x,y\right) \right) \wedge R\left(
y\right) \Leftrightarrow P\left( x\right) \wedge \left( Q\left( x,y\right)
\wedge R\left( y\right) \right)
\end{equation*}が成り立ちます。

例(結合律)
命題変数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、結合律より、\begin{equation*}\forall x\in X:\left( \left( P\left( x\right) \wedge Q\left( x\right)
\right) \wedge R\left( x\right) \right) \Leftrightarrow \forall x\in
X:\left( P\left( x\right) \wedge \left( Q\left( x\right) \wedge R\left(
x\right) \right) \right)
\end{equation*}が成り立ちます。

例(結合律)
任意の論理式\(A,B,C,D\)について、\begin{eqnarray*}\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{eqnarray*}が成り立ちます。

例(結合律)
任意の論理式\(A,B,C\)について、\begin{equation*}\left( A\vee B\right) \vee \left( A\vee C\right) \Leftrightarrow A\vee
\left( B\vee C\right)
\end{equation*}が成り立つことを証明します。実際、\begin{eqnarray*}
\left( A\vee B\right) \vee \left( A\vee C\right) &\Leftrightarrow &A\vee
\left( B\vee \left( A\vee C\right) \right) \quad \because \text{結合律} \\
&\Leftrightarrow &A\vee \left( \left( B\vee A\right) \vee C\right) \quad
\because \text{結合律} \\
&\Leftrightarrow &A\vee \left( \left( A\vee B\right) \vee C\right) \quad
\because \text{交換律} \\
&\Leftrightarrow &A\vee \left( A\vee \left( B\vee C\right) \right) \quad
\because \text{結合律} \\
&\Leftrightarrow &\left( A\vee A\right) \vee \left( B\vee C\right) \quad
\because \text{結合律} \\
&\Leftrightarrow &A\vee \left( B\vee C\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*}が成り立ちます。これは3つの論理式\(A,B,C\)の論理積をとるとき、隣り合う\(A,B\)と\(B,C\)のどちらに対して先に論理積を作用させる場合でも、最終的に得られる論理式はいずれも論理的に同値になることを意味します。そこで、これら2つの論理式を区別せずに、\begin{equation*}A\wedge B\wedge C
\end{equation*}で表記します。論理和についても同様に考え、\((A\vee B)\vee C\)と\(A\vee \left( B\vee C\right) \)を区別せずに、\begin{equation*}A\vee B\vee C
\end{equation*}で表記します。

4つの論理式\(A,B,C,D\)に対して、隣り合うどの2つの論理式に対して先に論理積を作用させるかによって最終的に様々な論理積が得られますが、\(\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つの論理積を区別せずに、\begin{equation*}A\wedge B\wedge C\wedge D
\end{equation*}で表記します。論理和についても同様に考え、上と同様な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}と表記します。論理和についても同様に考えて、\begin{equation}
\bigvee\limits_{i=1}^{n}A_{i}=A_{1}\vee \cdots \vee A_{n} \quad \cdots (2)
\end{equation}と表記します。

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

 

演習問題

問題(結合律)
論理式\(A_{1},A_{2},A_{3}\)が与えられたとき、\begin{equation*}A_{1}\wedge A_{2}\wedge A_{3}\Leftrightarrow A_{2}\wedge A_{3}\wedge A_{1}
\end{equation*}が成り立つことを証明してください。

証明

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

問題(結合律)
論理式\(A,B,C\)を任意に選んだとき、排他的論理和\(\veebar \)に関する結合律は、\begin{equation*}\left( A\veebar B\right) \veebar C\Leftrightarrow A\veebar \left( B\veebar
C\right)
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

証明

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

問題(結合律)
論理式\(A,B,C\)を任意に選んだとき、含意\(\rightarrow \)に関する結合律は、\begin{equation*}\left( A\rightarrow B\right) \rightarrow C\Leftrightarrow A\rightarrow
\left( B\rightarrow C\right)
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

証明

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

問題(結合律)
論理式\(A,B,C\)を任意に選んだとき、同等\(\leftrightarrow \)に関する結合律は、\begin{equation*}\left( A\leftrightarrow B\right) \leftrightarrow C\Leftrightarrow
A\leftrightarrow \left( B\leftrightarrow C\right)
\end{equation*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

証明

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

次回は分配律について学びます。

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

合成写像
合成写像

集合 A から集合 B への写像 f:A→B と、集合 B から集合 C への写像 g:B→C が与えられたとき、A のそれぞれの要素 a に対して C の要素である g(f(a)) を像として定める写像を作ることができるため、これを f と g の合成写像と呼びます。

結合律
命題論理における結合律

論理式 A,B,C が与えられたとき、隣り合う A,B に対して論理積 ∧ を作用させれば A∧B を得ます。これは論理式ですから、これと残された C に対して再び論理積 ∧ を作用させれば (A∧B)∧C という論理式を得ます。一方、最初に B,C に対して論理積 ∧ を作用させれば最終的に A∧(B∧C) という論理式を得ます。この 2 つの論理式の値が一致するというのが結合律の主張です。

結合律
集合演算における結合律

集合 A,B,C が与えられたとき、その中から隣り合う 2 つの集合 A,B を選んで共通部分を適用すれば A∩B を得ます。この集合と残された集合 C に対して再び共通部分を作用させれば (A∩B)∩C を得ます。一方、最初に B,C に対して共通部分を作用させれば最終的に A∩(B∩C) を得ます。この 2 つの集合が一致するというのが結合律の主張です。和集合∪に関しても同様の性質が成り立ちます。

述語論理