交換律
論理式\(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）が成り立つということです。
命題（交換律）
任意の論理式\(A,B\)に対して、\begin{align*}& \left( a\right) \ A\wedge B\Leftrightarrow B\wedge A \\
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}が成り立つ。
& \left( b\right) \ A\vee B\Leftrightarrow B\vee A
\end{align*}が成り立つ。
例（交換律）
命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ任意に選んだとき、交換律より、\begin{eqnarray*}P\left( x\right) \wedge Q\left( x\right) &\Leftrightarrow &Q\left( x\right)
\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*}がともに成り立ちます。
\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*}がともに成り立ちます。
例（交換律）
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}P\left( x\right) \vee \left( Q\left( x\right) \vee R\left( x\right) \right)
&\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*}などが成り立ちます。
&\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*}などが成り立ちます。
例（交換律）
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)と\(R\left( x\right) \)をそれぞれ任意に選んだとき、\begin{eqnarray*}P\left( x\right) \wedge \left( Q\left( x\right) \vee R\left( x\right)
\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*}などが成り立ちます。
\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*}などが成り立ちます。
例（交換律）
命題関数である\(P\left( x\right) \)と\(Q\left( x\right) \)をそれぞれ任意に選んだとき、交換律より、\begin{equation*}\left( \forall x\in X:P\left( x\right) \right) \wedge \left( \exists x\in
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*}が成り立ちます。
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*}が成り立ちます。
例（交換律）
変数\(x\)の定義域\(X\)はすべての整数からなる集合であるものとします。論理式\begin{equation*}x\text{は偶数であり、なおかつ}y\text{は奇数である}
\end{equation*}が与えられたとき、交換律より、これは以下の論理式\begin{equation*}
y\text{は奇数であり、なおかつ}x\text{は偶数である}
\end{equation*}と論理的に同値です。
\end{equation*}が与えられたとき、交換律より、これは以下の論理式\begin{equation*}
y\text{は奇数であり、なおかつ}x\text{は偶数である}
\end{equation*}と論理的に同値です。
量化と交換律
交換律を踏まえると、全称命題や存在命題に関して以下が成り立ちます。
命題（量化と交換律）
任意の論理式\(A,B\)と変数\(x\in X\)に対して、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( A\wedge B\right) \Leftrightarrow
\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*}が成り立つ。
\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*}が成り立つ。
例（量化と交換律）
命題関数\(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 \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*}がいずれも成り立ちます。
\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*}がいずれも成り立ちます。
例（量化と交換律）
「任意の整数は奇数または偶数である」という主張を論理式として表現すると、\begin{equation*}
\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*}と論理的に同値ですが、これは「任意の整数は偶数または奇数である」という主張です。
\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*}がともに成り立つことが示されます。つまり、全称記号どうしは入れ替え可能であり、存在記号どうしは入れ替え可能です。
命題（量化と交換律）
任意の論理式\(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*}が成り立つ。
例（量化と交換律）
命題関数\(P\left( x,y\right) \)を任意に選んだとき、先の命題より、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X,\ \forall y\in Y:P\left( x,y\right)
\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*}がともに成り立ちます。
\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*}がともに成り立ちます。
例（量化と交換律）
すべての実数からなる集合\(\mathbb{R} \)を定義域とする変数\(x,y\)に関する以下の2つの命題\begin{eqnarray*}\left( a\right) \ \forall x &\in &\mathbb{R} \ \forall y\in \mathbb{R} :x<y \\
\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) \)も偽です。
\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) \)も偽です。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】