教材一覧
教材一覧
教材検索

述語論理

述語論理における結合律

目次

Twitterで共有
メールで共有

結合律

論理式\(A,B,C\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)で、\(C\)から得られる命題を\(\overline{C}\)でそれぞれ表記します。すると命題論理における結合律より、\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*}が成り立ちます。

例(結合律)
任意の論理式\(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*}となります。

例(結合律)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、結合律より、以下の2つの命題\begin{eqnarray*}&&\left( a\right) \ \left( \forall x\in X:P\left( x\right) \wedge \forall
x\in X:Q\left( x\right) \right) \wedge \forall x\in X:R\left( x\right) \\
&&\left( b\right) \ \forall x\in X:P\left( x\right) \wedge \left( \forall
x\in X:Q\left( x\right) \wedge \forall x\in X:R\left( x\right) \right)
\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}と表記します。証明では完全帰納法の原理(強数学的帰納法の原理)を利用します。

命題(結合律の一般化)

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

証明

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

ちなみに、結合律に加えて交換律が成り立つことを踏まえると、\(n\)個の論理式\(A_{1},\cdots,A_{n}\)を任意に選んだとき、論理積を適用する順番とは関係なく、また、これらの論理式の相対的な順番を自由に入れ替えてもなお、最終的に得られる論理式が論理的に同値であることが保証されます。論理和についても同様です。

 

量化と結合律

結合律を踏まえると、全称命題存在命題に関して以下が成り立ちます。

命題(量化と結合律)
任意の論理式\(A,B,C\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( \left( A\wedge B\right) \wedge
C\right) \Leftrightarrow \forall x\in X:\left( A\wedge \left( B\wedge
C\right) \right) \\
&&\left( b\right) \ \forall x\in X:\left( \left( A\vee B\right) \vee
C\right) \Leftrightarrow \forall x\in X:\left( A\vee \left( B\vee C\right)
\right) \\
&&\left( c\right) \ \exists x\in X:\left( \left( A\wedge B\right) \wedge
C\right) \Leftrightarrow \exists x\in X:\left( A\wedge \left( B\wedge
C\right) \right) \\
&&\left( d\right) \ \exists x\in X:\left( \left( A\vee B\right) \vee
C\right) \Leftrightarrow \exists x\in X:\left( A\vee \left( B\vee C\right)
\right)
\end{eqnarray*}が成り立つ。

証明

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

例(結合律)
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、結合律より、\begin{eqnarray*}\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) \\
\exists x &\in &X:\left( \left( P\left( x\right) \wedge Q\left( x\right)
\right) \wedge R\left( x\right) \right) \Leftrightarrow \exists x\in
X:\left( P\left( x\right) \wedge \left( Q\left( x\right) \wedge R\left(
x\right) \right) \right)
\end{eqnarray*}などが成り立ちます。

全称命題は論理積を用いて、存在命題は論理和を用いてそれぞれ定義されますが、以上の事実と結合律を踏まえると、論理式\(A,B\)と変数\(x\in X\)をそれぞれ任意に選んだときに、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\wedge B\right) \Leftrightarrow
\left( \forall x\in X:A\right) \wedge \left( \forall x\in X:B\right) \\
&&\left( b\right) \ \exists x\in X:\left( A\vee B\right) \Leftrightarrow
\left( \exists x\in X:A\right) \vee \left( \exists x\in X:B\right)
\end{eqnarray*}がともに成り立つことが示されます。つまり、論理積の全称命題は全称命題の論理積と論理的に同値であり、論理和の存在命題は存在命題の論理和と論理的に同値です。

命題(量化と結合律)
任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\wedge B\right) \Leftrightarrow
\left( \forall x\in X:A\right) \wedge \left( \forall x\in X:B\right) \\
&&\left( b\right) \ \exists x\in X:\left( A\vee B\right) \Leftrightarrow
\left( \exists x\in X:A\right) \vee \left( \exists x\in X:B\right)
\end{eqnarray*}がともに成り立つ。

証明

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

例(量化と結合律)
命題関数\(P\left( x\right) ,Q\left( x\right) \)は論理式であるため、先の命題より、\begin{eqnarray*}\forall x &\in &X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \left( \forall x\in X:P\left( x\right) \right) \wedge \left(
\forall x\in X:Q\left( x\right) \right) \\
\exists x &\in &X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\Leftrightarrow \left( \exists x\in X:P\left( x\right) \right) \vee \left(
\forall x\in X:Q\left( x\right) \right)
\end{eqnarray*}などが成り立ちます。

例(量化と結合律)
命題関数\(P\left( x,y\right) ,Q\left( x,y\right) \)は論理式であるため、先の命題より、\begin{eqnarray*}\forall x &\in &X:\left( P\left( x,y\right) \wedge Q\left( x,y\right)
\right) \Leftrightarrow \left( \forall x\in X:P\left( x,y\right) \right)
\wedge \left( \forall x\in X:Q\left( x,y\right) \right) \\
\forall y &\in &Y:\left( P\left( x,y\right) \wedge Q\left( x,y\right)
\right) \Leftrightarrow \left( \forall y\in Y:P\left( x,y\right) \right)
\wedge \left( \forall x\in X:Q\left( x,y\right) \right) \\
\exists x &\in &X:\left( P\left( x,y\right) \vee Q\left( x,y\right) \right)
\Leftrightarrow \left( \exists x\in X:P\left( x,y\right) \right) \vee \left(
\exists x\in X:Q\left( x,y\right) \right) \\
\exists y &\in &Y:\left( P\left( x,y\right) \vee Q\left( x,y\right) \right)
\Leftrightarrow \left( \exists y\in Y:P\left( x,y\right) \right) \vee \left(
\exists x\in X:Q\left( x,y\right) \right)
\end{eqnarray*}などが成り立ちます。

例(量化と結合律)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)が与えられたとき、別の変数\(y\in Y\)を任意に選ぶと、先の命題より、\begin{equation*}\forall y\in Y:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \left( \forall y\in Y:P\left( x\right) \right) \wedge \left(
\forall y\in Y:Q\left( x\right) \right)
\end{equation*}がともに成り立つはずです。実際、全称命題の定義より、\begin{eqnarray}
\forall y &\in &Y:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow P\left( x\right) \wedge Q\left( x\right) \quad \cdots (1) \\
\forall y &\in &Y:P\left( x\right) \Leftrightarrow P\left( x\right)
\quad \cdots (2) \\
\forall y &\in &Y:Q\left( x\right) \Leftrightarrow Q\left( x\right)
\quad \cdots (3)
\end{eqnarray}がいずれも成り立つことを踏まえると、\begin{eqnarray*}
\forall y\in Y:\left( P\left( x\right) \wedge Q\left( x\right) \right)
&\Leftrightarrow &P\left( x\right) \wedge Q\left( x\right) \quad \because
\left( 1\right) \\
&\Leftrightarrow &\left( \forall y\in Y:P\left( x\right) \right) \wedge
\left( \forall y\in Y:Q\left( x\right) \right) \quad \because \left(
2\right) ,\left( 3\right)
\end{eqnarray*}となるため証明が完了しました。

例(量化と結合律)
「任意の実数\(x\)について\(x^{2}\not=-1\)かつ\(x^{2}\geq 0\)が成り立つ」という主張について考えます。変数\(x\)の定義域はすべての実数からなる集合\(\mathbb{R} \)です。主張を定式化すると、\begin{equation*}\forall x\in \mathbb{R} :\left( x^{2}\not=-1\wedge x^{2}\geq 0\right)
\end{equation*}となりますが、先の命題より、この論理式は、\begin{equation*}
\left( \forall x\in \mathbb{R} :x^{2}\not=-1\right) \wedge \left( \forall x\in \mathbb{R} :x^{2}\geq 0\right)
\end{equation*}と論理的に同値です。したがって、もとの主張は「任意の実数\(x\)について\(x^{2}\not=-1\)が成り立ち、なおかつ任意の実数\(x\)について\(x^{2}\geq 0\)が成り立つ」と言い換え可能です。
例(量化と結合律)
「\(2\)の倍数または\(3\)の倍数であるような整数が存在する」という主張について考えます。変数\(x\)の定義域\(X\)はすべての整数からなる集合です。先の主張を定式化すると、\begin{equation*}\exists x\in X:\left( x\text{は}2\text{の倍数}\vee x\text{は}3\text{の倍数}\right)
\end{equation*}となりますが、先の命題より、この論理式は、\begin{equation*}
\left( \exists x\in X:x\text{は}2\text{の倍数}\right) \vee \left( \exists x\in X:x\text{は}3\text{の倍数}\right)
\end{equation*}と論理的に同値です。したがって、もとの主張は「\(2\)の倍数であるような整数が存在するか、または\(3\)の倍数であるような整数が存在する」と言い換え可能です。
Twitterで共有
メールで共有