論理式中の全称記号どうし、存在記号どうしを入れ替えて得られる論理式はもとの論理式と同値です。一方、論理式中の全称記号と存在記号を入れ替えて得られる論理式はもとの論理式と同値であるとは限りません。
量化記号 順番 置換 入れ替え
< 前のページ
次のページ >

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

論理式\(A\)と変数\(x\in X\)と\(y\in Y\)がそれぞれ任意に与えられたとき、解釈を任意に選ぶと、\begin{eqnarray*}
\forall x\in X,\ \forall y\in Y:A &\Leftrightarrow &\forall x\in X:\left(
\bigwedge\limits_{y\in Y}A\right) \quad \because \forall \text{の定義} \\
&\Leftrightarrow &\bigwedge\limits_{x\in X}\left( \bigwedge\limits_{y\in
Y}A\right) \quad \because \forall \text{の定義} \\
&\Leftrightarrow &\bigwedge\limits_{y\in Y}\left( \bigwedge\limits_{x\in
X}A\right) \quad \because \text{交換律} \\
&\Leftrightarrow &\forall y\in Y:\left( \bigwedge\limits_{x\in X}A\right)
\quad \because \forall \text{の定義} \\
&\Leftrightarrow &\forall y\in Y,\ \forall x\in X:A\quad \because \forall
\text{の定義}
\end{eqnarray*}すなわち、\begin{equation*}
\left( a\right) \ \forall x\in X,\ \forall y\in Y:A\Leftrightarrow \forall
y\in Y,\ \forall x\in X:A
\end{equation*}が成り立ちます。つまり、論理式中の全称記号どうしを入れ替えて得られる論理式はもとの論理式と同値です。\(\left( a\right) \)において全称記号\(\forall \)を存在記号\(\exists \)に入れ替えると、\begin{equation*}
\left( b\right) \ \exists x\in X,\ \exists y\in Y:A\Leftrightarrow \exists
y\in Y,\ \exists x\in X:A
\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*}
証明を見る(プレミアム会員限定)
例(同一種類の量化記号の置換)
変数\(x\in X\)と\(y\in Y\)に関する命題関数\(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*}などが成り立ちます。
例(同一種類の量化記号の置換)
変数\(x\in X\)と\(y\in Y\)に関する命題関数\(P\left( x,y\right) \)が与えられたとき、別の変数\(z\in Z\)を任意に選ぶと、先の命題より、例えば、\begin{equation*}
\forall x\in X,\ \forall z\in Z:P\left( x,y\right) \Leftrightarrow \forall
z\in Z,\ \forall x\in X:P\left( x,y\right)
\end{equation*}が成り立つはずです。実際、全称記号\(\forall \)の定義より、\begin{eqnarray*}
\forall x\in X,\ \forall z\in Z:P\left( x,y\right) &\Leftrightarrow
&\forall x\in X:P\left( x,y\right) \\
&\Leftrightarrow &\forall z\in Z,\ \forall x\in X:P\left( x,y\right)
\end{eqnarray*}が成り立ちます。
例(同一種類の量化記号の置換)
変数\(x\)の定義域\(X\)と変数\(y\)の定義域\(Y\)がいずれもすべての自然数からなる集合であるとき、先の命題より、以下の2つの論理式\begin{eqnarray*}
\left( a\right) \ \forall x &\in &X,\ \forall y\in Y:x<y \\
\left( b\right) \ \forall y &\in &Y,\ \forall x\in X:x<y
\end{eqnarray*}は論理的に同値です。\(\left( a\right) \)は「自然数\(x\)を任意に選んだとき、それに対して任意の自然数\(y\)は\(x<y\)を満たす」という主張ですが、これは偽です。実際、\(\left( x,y\right) =\left( 2,1\right) \)が反例になっています。\(\left( b\right) \)は「自然数\(y\)を任意に選んだとき、それに対して任意の自然数\(x\)は\(x<y\)を満たす」という主張ですが、これも偽です。先と同様、\(\left( x,y\right) =\left( 2,1\right) \)が反例になっています。

 

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

論理式中の全称記号どうし、ないし存在記号どうしを入れ替えて得られる論理式はもとの論理式と論理的に同値であることが明らかになりました。では、全称記号と存在記号を入れ替える場合にも、入れ替えの前後の論理式は論理的に同値であることが保証されるのでしょうか。つまり、論理式\(A\)と変数\(x\in X\)と\(y\in Y\)がそれぞれ任意に与えられたとき、\begin{equation*}
\forall x\in X,\ \exists y\in Y:A\Leftrightarrow \exists y\in Y,\ \forall
x\in X:A
\end{equation*}は成り立つのでしょうか。まず、\(\Leftarrow \)は成り立ちます。実際、解釈を任意に選ぶと、\begin{eqnarray*}
\exists y\in Y,\ \forall x\in X:A &\Leftrightarrow &\exists y\in Y:\left(
\bigwedge\limits_{x\in X}A\right) \quad \because \forall \text{の定義} \\
&\Leftrightarrow &\bigvee\limits_{y\in Y}\left( \bigwedge\limits_{x\in
X}A\right) \quad \because \exists \text{の定義} \\
&\Rightarrow &\bigwedge\limits_{x\in X}\left( \bigvee\limits_{y\in
Y}A\right) \quad \because \text{分配律} \\
&\Leftrightarrow &\forall x\in X,\ \exists y\in Y:A\quad \because \forall
\text{の定義}
\end{eqnarray*}となります。

命題(異なる種類の量化記号の置換)
任意の論理式\(A\)と変数\(x\in X\)と\(y\in Y\)に対して、\begin{equation*}
\exists y\in Y,\ \forall x\in X:A\Rightarrow \forall x\in X,\ \forall y\in
Y:A
\end{equation*}以下が成り立つ。
証明を見る(プレミアム会員限定)

一方、上の命題の逆は成り立つとは限りません。これは以下の例から明らかです。

例(異なる種類の量化記号の置換)
変数\(x\in X\)と\(y\in Y\)に関する命題関数\(P\left( x,y\right) \)に関する以下の2つの論理式\begin{eqnarray*}
&&\left( a\right) \ \forall x\in X,\ \exists y\in Y:P\left( x,y\right) \\
&&\left( b\right) \ \exists y\in Y,\ \forall x\in X:P\left( x,y\right)
\end{eqnarray*}について考えます。\(X,Y\)がいずれもすべての自然数からなる集合であり、命題関数\(P\left( x,y\right) \)の形状が、\begin{equation*}
P\left( x,y\right) :x<y
\end{equation*}であるような解釈において、\(\left( a\right) \)は真である一方で\(\left( b\right) \)は偽です(確認してください)。したがって、\begin{equation*}
\forall x\in X,\ \exists y\in Y:P\left( x,y\right) \Rightarrow \exists y\in
Y,\ \forall x\in X:P\left( x,y\right)
\end{equation*}が成り立たないことが明らかになりました。

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

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

述語論理
アカウント
ログイン