論理式\(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\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)で、\(B\)から得られる命題を\(\overline{C}\)でそれぞれ表記します。すると\(\wedge \)に関する結合律より、\begin{equation*}
\left( \overline{A}\wedge \overline{B}\right) \wedge \overline{C}\Leftrightarrow \overline{A}\wedge \left( \overline{B}\wedge \overline{C}\right)
\end{equation*}が成り立ちます。任意の解釈において同様の議論が成立するため、\begin{equation*}
\left( a\right) \ \left( A\wedge B\right) \wedge C\Leftrightarrow A\wedge
\left( B\wedge C\right)
\end{equation*}が成り立つことが示されました。\(\left( a\right) \)において\(\wedge \)を\(\vee \)に置き換えると、\begin{equation*}
\left( b\right) \ \left( A\vee B\right) \vee C\Leftrightarrow A\vee \left(
B\vee C\right)
\end{equation*}を得ますが、これが成り立つことも同様にして示されます。つまり、述語論理においても論理積や論理和について結合律(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\ \left( \left( P\left( x\right) \wedge Q\left( x\right) \right)
\wedge R\left( x\right) \right) \Leftrightarrow \forall x\ \left( P\left(
x\right) \wedge \left( Q\left( x\right) \wedge R\left( x\right) \right)
\right)
\end{equation*}が成り立ちます。
例(結合律)
任意の論理式\(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*}が成り立ちます、これは\(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} \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}\)の順番を自由に入れ替えても、その前後の論理式は論理的に同値であることが保証されます。

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

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

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

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

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

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

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

述語論理