WIIS

命題論理

命題論理における結合律

目次

Mailで保存
Xで共有

結合律

論理式\(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\)に対して、\begin{align*}& \left( a\right) \ \left( A\wedge B\right) \wedge C\Leftrightarrow A\wedge
\left( B\wedge C\right) \\
& \left( b\right) \ \left( A\vee B\right) \vee C\Leftrightarrow A\vee \left(
B\vee C\right)
\end{align*}が成り立つ。

証明

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

論理式\(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*}と表記できるものと定めます。

例(結合律)
命題変数\(P,Q,R\)を任意に選んだとき、命題変数は論理式であるため、結合律より、\begin{align*}& \left( a\right) \ (P\wedge Q)\wedge R\Leftrightarrow P\wedge \left(
Q\wedge R\right) \\
& \left( b\right) \ (P\vee Q)\vee R\Leftrightarrow P\vee \left( Q\vee
R\right)
\end{align*}がともに成り立ちます。

例(結合律)
命題変数\(P,Q,R,S\)を任意に選んだとき、含意\begin{eqnarray*}P &\rightarrow &Q \\
Q &\rightarrow &R \\
R &\rightarrow &S
\end{eqnarray*}はいずれも論理式であるため、結合律より、\begin{align*}
& \left( a\right) \ (\left( P\rightarrow Q\right) \wedge \left( Q\rightarrow
R\right) )\wedge \left( R\rightarrow S\right) \Leftrightarrow \left(
P\rightarrow Q\right) \wedge \left( \left( Q\rightarrow R\right) \wedge
\left( R\rightarrow S\right) \right) \\
& \left( b\right) \ (\left( P\rightarrow Q\right) \vee \left( Q\rightarrow
R\right) )\vee \left( R\rightarrow S\right) \Leftrightarrow \left(
P\rightarrow Q\right) \vee \left( \left( Q\rightarrow R\right) \vee \left(
R\rightarrow S\right) \right)
\end{align*}がともに成り立ちます。

 

結合律の一般化

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}で表記します。

命題(結合律の一般化)

有限\(n\)個の論理式\(A_{1},\cdots,A_{n}\)を任意に選んだ上で、これらの相対的な順番を変えないまま論理積をとるとき、論理積を作用させる順番とは関係なく最終的に得られる論理式はいずれも論理的に同値である。また、これらの相対的な順番を変えないまま論理和をとるとき、論理和を作用させる順番とは関係なく最終的に得られる論理式はいずれも論理的に同値である。

証明

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

 

交換律と結合律の一般化

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*}と論理的に同値になります。

命題(交換律と結合律の一般化)
有限\(n\)個の論理式\(A_{1},\cdots,A_{n}\)を任意に選ぶ。これらの論理積をとる際、論理式の相対的な順番や論理積を作用させる順番とは関係なく、最終的に得られる論理式はいずれも、\begin{equation*}\bigwedge\limits_{i=1}^{n}A_{i}
\end{equation*}と論理的に同値である。また、これらの論理和をとる際、論理式の相対的な順番や論理和を作用させる順番とは関係なく、最終的に得られる論理式はいずれも、\begin{equation*}
\bigvee\limits_{i=1}^{n}A_{i}
\end{equation*}と論理的に同値である。

 

演習問題

問題(論理的同値)
任意の命題変数\(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*}が成り立つことを論理的同値変形により示してください。

解答を見る

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

問題(論理的同値)
任意の命題変数\(P,Q,R\)について、\begin{equation*}P\wedge Q\wedge R\Leftrightarrow Q\wedge R\wedge P
\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*}と表現できますが、これは成り立つでしょうか。理由とともに答えてください。

解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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