結合律
論理式\(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）が成り立つということです。
B\wedge C\right) \\
& \left( b\right) \ (A\vee B)\vee C\Leftrightarrow A\vee \left( B\vee
C\right)
\end{align*}が成り立つ。
y\right) \Leftrightarrow P\left( x\right) \wedge \left( Q\left( x,y\right)
\wedge R\left( y\right) \right)
\end{equation*}が成り立ちます。
\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*}が成り立ちます。
\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*}となります。
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*}は論理的に同値です。
結合律の一般化
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}\)を任意に選んだ上で、これらの相対的な順番を変えないまま論理積をとる限り、括弧の付け方、すなわち論理積を作用させる順番をどのように定めても、最終的に得られる論理式はいずれも論理的に同値である。また、論理和についても同様である。
R\left( x\right) \right) \wedge S\left( s\right) \\
&&\left( P\left( x\right) \wedge \left( Q\left( x\right) \wedge R\left(
x\right) \right) \right) \wedge S\left( s\right) \\
&&\left( P\left( x\right) \wedge Q\left( x\right) \right) \wedge \left(
R\left( x\right) \wedge S\left( s\right) \right) \\
&&P\left( x\right) \wedge \left( \left( Q\left( x\right) \wedge R\left(
x\right) \right) \wedge S\left( s\right) \right) \\
&&P\left( x\right) \wedge \left( Q\left( x\right) \wedge \left( R\left(
x\right) \wedge S\left( s\right) \right) \right)
\end{eqnarray*}先の命題より、これらの論理式は同値です。
交換律と結合律の一般化
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*}と論理的に同値になります。
量化と結合律
結合律を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
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*}が成り立つ。
\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*}がともに成り立つことが示されます。つまり、論理積の全称命題は全称命題の論理積と論理的に同値であり、論理和の存在命題は存在命題の論理和と論理的に同値です。
\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*}がともに成り立つ。
\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(
\exists x\in X:Q\left( x\right) \right)
\end{eqnarray*}などが成り立ちます。
\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 y\in Y: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 y\in Y:Q\left( x,y\right) \right)
\end{eqnarray*}などが成り立ちます。
\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*}となるため証明が完了しました。
\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\)が成り立つ」と言い換え可能です。
\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\)の倍数であるような整数が存在する」と言い換え可能です。
演習問題
x\right) \\
&&R\left( x\right) \vee \left( P\left( x\right) \vee Q\left( x\right)
\right)
\end{eqnarray*}が論理的に同値であることを、交換律と結合律を用いて示してください。
- 任意の自然数\(n\)について、\(n\geq 0,n+1\geq 0\)および\(n^{2}\geq 0\)が成り立つ。
- 任意の自然数\(n\)について、\(n\geq 0\)および\(n+1\geq0,n^{2}\geq 0\)が成り立つ。
- \(5\)の倍数または\(7\)の倍数であるような自然数が存在する。
- \(5\)の倍数であるような自然数が存在する、または\(7\)の倍数であるような自然数が存在する。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。