論理式中の全称記号どうし、存在記号どうしを入れ替えて得られる論理式はもとの論理式と同値です。一方、論理式中の全称記号と存在記号を入れ替えて得られる論理式はもとの論理式と同値であるとは限りません。

量化記号 順番 置換 入れ替え

2019年6月1日:公開

同一種類の量化記号の置換

論理式中の全称記号どうし、存在記号どうしを入れ替えて得られる論理式はもとの論理式と同値です。

命題(量化記号の置換)
任意の論理式\(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*}
証明を見る(プレミアム会員限定)

 

1変数の命題関数に関する特殊ケース

上の命題において論理式\(A\)を命題関数\(P\left( x,y\right) \)として特定することで、以下のような特殊ケースを得ます。

系(量化記号の置換)
任意の命題関数\(P\left( x,y\right) \)と変数\(x\in X,\ y\in Y\)に対して以下が成り立つ。\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*}
例(量化記号の置換)
変数\(x,y\)がいずれもすべての自然数を値としてとり得るとき、上の命題より、以下の2つの論理式は同値です。\begin{eqnarray*}
&&\left( a\right) \ \forall x\ \forall y\ \left( x<y\right) \\
&&\left( b\right) \ \forall y\ \forall x\ \left( x<y\right)
\end{eqnarray*}ちなみに、\(\left( a\right) \)は「自然数\(x\)を任意に選んだとき、それに対して任意の自然数\(y\)は\(x<y\)を満たす」という意味であり、これは偽です。一方、\(\left( b\right) \)は「自然数\(y\)を任意に選んだとき、それに対して任意の自然数\(x\)は\(x<y\)を満たす」という意味であり、これも偽です。

 

異なる種類の量化記号の置換

論理式中の全称記号と存在記号を入れ替えて得られる論理式はもとの論理式と同値であるとは限りません。例えば、命題関数\(P\left( x,y\right) \)と変数\(x\in X,\ y\in Y\)に対して、\begin{eqnarray*}
&&\left( a\right) \ \forall x\in X\ \exists y\in Y\ P\left( x,y\right) \ \Leftrightarrow \ \exists y\in Y\ \forall x\in X\ P\left( x,y\right) \\
&&\left( b\right) \ \exists x\in X\ \forall y\in Y\ P\left( x,y\right) \ \Leftrightarrow \ \forall y\in Y\ \exists x\in X\ P\left( x,y\right)
\end{eqnarray*}という関係は成り立ちません。以下に反例を示します。

変数\(x,y\)がいずれもすべての自然数を値としてとり得るとき、以下の2つの論理式\begin{eqnarray*}
&&\left( 1\right) \ \forall x\ \exists y\ \left( x<y\right) \\
&&\left( 2\right) \ \exists y\ \forall x\ \left( x<y\right)
\end{eqnarray*}は同値ではありません。\(\left( 1\right) \)は「任意の自然数\(x\)に対して、\(x<y\)を満たす自然数\(y\)が存在する」という主張ですが、自然数\(x\)を任意に選んだとき、それに対して\(y=x+1\)とすればよいため\(\left( 1\right) \)は真です。他方の\(\left( 2\right) \)は「ある自然数\(y\)が存在して、それと任意の自然数\(y\)の間に\(x<y\)が成り立つ」という主張ですが、どのような自然数\(y\)に対してもそれ以上の自然数\(x\)は存在するため\(\left( 2\right) \)は偽です。\(\left( 1\right) \)は真で\(\left( 2\right) \)は偽であるため、両者は同値ではなく、したがって\(\left( a\right) \)は成り立ちません。\(\left( b\right) \)についても同様です。

次回から推論について学びます。

次へ進む 演習問題(プレミアム会員限定)