量化記号の置換

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

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

論理式\(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
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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

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