交換律
論理式\(A,B\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)でそれぞれ表記します。すると命題論理における交換律より、\begin{align*}& \left( a\right) \ \overline{A}\wedge \overline{B}\Leftrightarrow \overline{B}\wedge \overline{A} \\
& \left( b\right) \ \overline{A}\vee \overline{B}\Leftrightarrow \overline{B}\vee \overline{A}
\end{align*}を得ます。任意の解釈において同様の議論が成立するため、\begin{align*}
& \left( a\right) \ A\wedge B\Leftrightarrow B\wedge A \\
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}がともに成り立つことが示されました。つまり、述語論理においても論理積や論理和について交換律（commutative law）が成り立つということです。
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}が成り立つ。
\wedge P\left( x\right) \\
P\left( x\right) \vee Q\left( x\right) &\Leftrightarrow &Q\left( x\right)
\vee P\left( x\right)
\end{eqnarray*}がともに成り立ちます。
&\Leftrightarrow &P\left( x\right) \vee \left( R\left( x\right) \vee Q\left(
x\right) \right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( R\left( x\right) \vee Q\left( x\right) \right) \vee
P\left( x\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( Q\left( x\right) \vee R\left( x\right) \right) \vee
P\left( x\right) \quad \because \text{交換律}
\end{eqnarray*}などが成り立ちます。
\right) &\Leftrightarrow &P\left( x\right) \wedge \left( R\left( x\right)
\vee Q\left( x\right) \right) \quad \because \text{交換律}
\\
&\Leftrightarrow &\left( R\left( x\right) \vee Q\left( x\right) \right)
\wedge P\left( x\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\left( Q\left( x\right) \vee R\left( x\right) \right)
\wedge P\left( x\right) \quad \because \text{交換律}
\end{eqnarray*}などが成り立ちます。
X:Q\left( x\right) \right) \Leftrightarrow \left( \exists x\in X:Q\left(
x\right) \right) \wedge \left( \forall x\in X:P\left( x\right) \right)
\end{equation*}が成り立ちます。
\end{equation*}が与えられたとき、交換律より、これは以下の論理式\begin{equation*}
y\text{は奇数であり、なおかつ}x\text{は偶数である}
\end{equation*}と論理的に同値です。
交換律の一般化
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つの論理式がすべて論理的に同値であることもまた保証されます。
論理和についても同様に考えます。また、4つ以上の論理式についても同様に考えます。
有限\(n\)個の論理式\(A_{1},\cdots,A_{n}\)の論理積\(A\)が与えられているものとする。このとき、その論理式\(A\)に含まれる\(n-1\)個の論理積演算子\(\wedge \)のそれぞれについて、左右の論理式を交換するかどうかを任意に選んで得られる\(2^{n-1}\)通りの論理式はいずれも、もとの論理式\(A\)と論理的に同値である。また、論理和についても同様の主張が成り立つ。
R\left( x\right) \right) \wedge S\left( x\right)
\end{equation*}が与えられているものとします。この論理式に含まれる3個の演算子\(\wedge \)のそれぞれについて、その左右の論理式を交換するかどうかを選ぶことにより\(2^{3}=8\)通りの論理式\begin{eqnarray*}&&\left( \left( P\left( x\right) \wedge Q\left( x\right) \right) \wedge
R\left( x\right) \right) \wedge S\left( x\right) \\
&&\left( \left( Q\left( x\right) \wedge P\left( x\right) \right) \wedge
R\left( x\right) \right) \wedge S\left( x\right) \\
&&\left( R\left( x\right) \wedge \left( P\left( x\right) \wedge Q\left(
x\right) \right) \right) \wedge S\left( x\right) \\
&&S\left( x\right) \wedge \left( \left( P\left( x\right) \wedge Q\left(
x\right) \right) \wedge R\left( x\right) \right) \\
&&\left( R\left( x\right) \wedge \left( Q\left( x\right) \wedge P\left(
x\right) \right) \right) \wedge S\left( x\right) \\
&&S\left( x\right) \wedge \left( \left( Q\left( x\right) \wedge P\left(
x\right) \right) \wedge R\left( x\right) \right) \\
&&S\left( x\right) \wedge \left( R\left( x\right) \wedge \left( P\left(
x\right) \wedge Q\left( x\right) \right) \right) \\
&&S\left( x\right) \wedge \left( R\left( x\right) \wedge \left( Q\left(
x\right) \wedge P\left( x\right) \right) \right)
\end{eqnarray*}が得られますが、先の命題よりこれらは論理的に同値です。
量化と交換律
交換律を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
\forall x\in X:\left( B\wedge A\right) \\
&&\left( b\right) \ \forall x\in X:\left( A\vee B\right) \Leftrightarrow
\forall x\in X:\left( B\vee A\right) \\
&&\left( c\right) \ \exists x\in X:\left( A\wedge B\right) \Leftrightarrow
\exists x\in X:\left( B\wedge A\right) \\
&&\left( d\right) \ \exists x\in X:\left( A\vee B\right) \Leftrightarrow
\exists x\in X:\left( B\vee A\right)
\end{eqnarray*}が成り立つ。
\Leftrightarrow \forall x\in X:\left( Q\left( x\right) \wedge P\left(
x\right) \right) \\
\forall x &\in &X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\Leftrightarrow \forall x\in X:\left( Q\left( x\right) \vee P\left( x\right)
\right) \\
\exists x &\in &X:\left( P\left( x\right) \wedge Q\left( x\right) \right)
\Leftrightarrow \exists x\in X:\left( Q\left( x\right) \wedge P\left(
x\right) \right) \\
\exists x &\in &X:\left( P\left( x\right) \vee Q\left( x\right) \right)
\Leftrightarrow \exists x\in X:\left( Q\left( x\right) \vee P\left( x\right)
\right)
\end{eqnarray*}がいずれも成り立ちます。
\forall x\in \mathbb{Z} :\left( x\text{は奇数}\vee x\text{は偶数}\right)
\end{equation*}となります。ただし、\(\mathbb{Z} \)はすべての整数からなる集合です。交換律より、これは、\begin{equation*}\forall x\in \mathbb{Z} :\left( x\text{は偶数}\vee x\text{は奇数}\right)
\end{equation*}と論理的に同値ですが、これは「任意の整数は偶数または奇数である」という主張です。
全称命題は論理積を用いて、存在命題は論理和を用いてそれぞれ定義されますが、以上の事実と交換律を踏まえると、論理式\(A\)と変数\(x\in X\)および\(y\in Y\)をそれぞれ任意に選んだときに、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X,\ \forall y\in Y:A\Leftrightarrow \forall
y\in Y,\ \forall x\in X:A \\
&&\left( b\right) \ \exists x\in X,\ \exists y\in Y:A\Leftrightarrow \exists
y\in Y,\ \exists x\in X:A
\end{eqnarray*}がともに成り立つことが示されます。つまり、全称記号どうしは入れ替え可能であり、存在記号どうしは入れ替え可能です。
y\in Y,\ \forall x\in X:A \\
&&\left( b\right) \ \exists x\in X,\ \exists y\in Y:A\Leftrightarrow \exists
y\in Y,\ \exists x\in X:A
\end{eqnarray*}が成り立つ。
\Leftrightarrow \forall y\in Y,\ \forall x\in X:P\left( x,y\right) \\
&&\left( b\right) \ \exists x\in X,\ \exists y\in Y:P\left( x,y\right)
\Leftrightarrow \exists y\in Y,\ \exists x\in X:P\left( x,y\right)
\end{eqnarray*}がともに成り立ちます。
&&\left( b\right) \ \forall y\in \mathbb{R} ,\ \forall x\in \mathbb{R} :x<y
\end{eqnarray*}に注目します。\(\left( a\right) \)は「実数\(x\)を任意に選んだとき、それに対して任意の実数\(y\)は\(x<y\)を満たす」という主張であり、\(\left( b\right) \)は「実数\(y\)を任意に選んだとき、それに対して任意の実数\(x\)は\(x<y\)を満たす」という主張です。先の命題より\(\left(a\right) \)と\(\left( b\right) \)は論理的に同値です。ちなみに、\(\left( x,y\right) =\left( 2,1\right) \)に注目すると\(\left( a\right) \)より\(2<1\)を得ますが、これは偽です。したがって\(\left(a\right) \)は偽であり、\(\left( x,y\right)=\left( 2,1\right) \)は反例になっています。\(\left( a\right) \)と論理的に同値な\(\left( b\right) \)も偽です。
演習問題
\right) \\
&&\left( Q\left( x\right) \vee R\left( x\right) \right) \vee P\left(
x\right)
\end{eqnarray*}が論理的に同値であることを、交換律だけを用いて示してください。
- 任意の整数について、「\(3\)の倍数または\(3\)で割ると\(1\)余る数である」、または\(3\)で割ると\(2\)余る数である。
- 任意の整数について、\(3\)の倍数であるまたは「\(3\)で割ると\(1\)余る数または\(3\)で割ると\(2\)余る数である」。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。