論理式\(A\)と変数\(x\in X\)に対して量化記号\(\exists \)を作用させることで得られる\(\exists x\in X\ A\)もまた\(D\)の論理式です。\(\exists \)は存在記号と呼ばれる量化記号であり、存在記号を作用させて得られる論理式\(\exists x\in X\ A\)を存在命題と呼びます。
< 前のページ
次のページ >

存在命題

論理式の定義より、論理式\(A\)と変数\(x\in X\)に対して量化記号\(\exists \)を作用させることで得られる\(\exists x\in X\ A\)もまた論理式です。\(\exists \)は存在記号(existential quantifier)と呼ばれる量化記号であり、存在記号を作用させて得られる論理式\(\exists x\in X\ A\)を存在命題(existential propositioin)と呼びます。これは「\(A\)であるような値\(x\)が\(X\)の中に存在する(there exists \(x\) in \(X\) such that \(A\))」や「\(X\)のある値\(x\)について\(A\)(for some \(x\) in \(X\), \(A\))」などの表現に対応する論理式です。

存在命題\(\exists x\in X\ A\)において変数\(x\)の定義域\(X\)が文脈から明らかであるとき、それを省略して\(\exists x\ A\)と表記することができます。また、見やすさを考慮して\(\exists x\in X\ A\)を\(\exists x\in X:A\)と表記する場合もあります。

例(存在命題)
以下の主張\begin{equation}
1\text{に足すと}0\text{になるような整数が存在する} \tag{1}
\end{equation}はどのような論理式として表現できるでしょうか。命題変数\(P\left( x\right) \)を、\begin{equation*}
P\left( x\right) :1+x=0
\end{equation*}とおきます。ただし、変数\(x\)の定義域\(X\)はすべての整数からなる集合です。\(\left( 1\right) \)の主張は「命題\(P\left( x\right) \)が真になるような値\(x\)が\(X\)の中に存在する」というものであるため、\(\left( 1\right) \)を定式化すると、\begin{equation*}
\exists x\in X\ P\left( x\right)
\end{equation*}となります。
例(存在命題)
以下の主張\begin{equation}
\text{偶数ではない整数が存在する} \tag{1}
\end{equation}はどのような論理式として表現できるでしょうか。命題変数\(P\left( x\right) \)を、\begin{equation*}
P\left( x\right) :x\text{は偶数である}
\end{equation*}とおきます。ただし、変数\(x\)の定義域\(X\)はすべての整数からなる集合です。\(\left( 1\right) \)の主張は「命題\(\lnot P\left( x\right) \)が真になるような値\(x\)が\(X\)の中に存在する」というものであるため、\(\left( 1\right) \)を定式化すると、\begin{equation*}
\exists x\in X\ \lnot P\left( x\right)
\end{equation*}となります。
例(存在命題)
以下の主張\begin{equation}
\text{任意の実数は平方根を持つ} \tag{1}
\end{equation}はどのような論理式として表現できるでしょうか。命題変数\(P\left( x,y\right) \)を、\begin{equation*}
P\left( x,y\right) :x=y^{2}
\end{equation*}とおきます。ただし、変数\(x\)の定義域\(X\)と変数\(y\)の定義域\(Y\)はともにすべての実数からなる集合です。特定の実数\(\overline{x}\in X\)に注目したとき、「実数\(\overline{x}\)は平方根を持つ」という主張は、\begin{equation}
\exists y\in Y\ P\left( \overline{x},y\right) \tag{2}
\end{equation}として定式化されます。\(\left( 1\right) \)の主張は、「\(\left( 2\right) \)が任意の実数\(x\)について成立する」というものであるため、\(\left( 1\right) \)を定式化すると、\begin{equation*}
\forall x\in X\ \left( \exists y\in Y\ P\left( x,y\right) \right)
\end{equation*}となります。
例(存在命題)
以下の主張\begin{equation}
\text{加藤が持っているモノの中に鈴木が持っていないモノがある} \tag{1}
\end{equation}はどのような論理式として表現できるでしょうか。命題変数\(P\left( x,y\right) \)を、\begin{equation*}
P\left( x,y\right) :x\text{は}y\text{を持っている}
\end{equation*}とおきます。ただし、変数\(x\)の定義域\(X\)はすべての人間からなる集合、変数\(y\)の定義域\(Y\)はすべてのモノからなる集合です。\(x\)の値である「加藤」と「鈴木」、さらに特定のモノ\(\overline{y}\in Y\)に注目したとき、「加藤が\(\overline{y}\)を持っているが鈴木は\(\overline{y}\)を持っていない」という言明は、\begin{equation}
P\left( \text{加藤},\overline{y}\right) \wedge \lnot P\left(
\text{鈴木},\overline{y}\right) \tag{2}
\end{equation}として定式化されます。\(\left( 1\right) \)の主張は「\(\left( 2\right) \)が成立するようなモノ\(y\)が存在する」というものであるため、\(\left( 1\right) \)を定式化すると、\begin{equation*}
\exists y\in Y\ \left( P\left( \text{加藤},y\right) \wedge \lnot
P\left( \text{鈴木},y\right) \right)
\end{equation*}となります。
例(存在命題)
以下の主張\begin{equation}
\text{この町の住人の中にはお互いに知り合いでない人たちがいる} \tag{1}
\end{equation}はどのような論理式として定式化できるでしょうか。命題変数\(P\left( x,y\right) \)を、\begin{equation*}
P\left( x,y\right) :x\text{と}y\text{は知り合い}
\end{equation*}とおきます。ただし、変数\(x\)の定義域\(X\)と変数\(y\)の定義域\(Y\)はいずれも問題としている町のすべての住人からなる集合です。ある住人\(\overline{x}\in X\)に注目したとき、この人と知り合いでない住人がいるという主張は、\begin{equation}
\exists y\in Y\ \lnot P\left( \overline{x},y\right) \tag{2}
\end{equation}と定式化されます。\(\left( 1\right) \)の主張は、\(\left( 2\right) \)が特定の住人\(\overline{x}\)についてだけではなく、任意の住人\(x\in X\)について成り立つという主張であるため、\begin{equation*}
\forall x\in X\ \left( \exists y\in X\ \lnot P\left( x,y\right) \right)
\end{equation*}と定式化されます。

 

存在命題の解釈

論理式\(A\)が変数\(x,y_{1},\cdots ,y_{n}\)の自由な現れを持つ開論理式\(A\left( x,y_{1},\cdots ,y_{n}\right) \)であるとき、変数\(x\)に関する存在\(\exists x\in X\ A\)は変数\(y_{1},\cdots ,y_{n}\)の自由な現れを持つ開論理式\begin{equation}
\left( \exists x\in X\ A\right) \left( y_{1},\cdots ,y_{n}\right) \tag{1}
\end{equation}であるものと定めた上で、これを以下の論理和\begin{equation}
\bigvee\limits_{x\in X}A\left( x,y_{1},\cdots ,y_{n}\right) \tag{2}
\end{equation}と同一視します。論理和についてはすでに解説した通りです。開論理式を解釈することとは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}
\end{eqnarray*}を具体的に特定することを意味し、解釈を任意に選ぶと論理式\(\left( 1\right) \)からは以下の命題\begin{equation*}
\left( \exists x\in X\ A\right) \left( \overline{y}_{1},\cdots ,\overline{y}_{n}\right)
\end{equation*}が得られ、論理式\(\left( 2\right) \)からは以下の命題\begin{equation*}
\bigvee\limits_{x\in X}A\left( x,\overline{y}_{1},\cdots ,\overline{y}_{n}\right)
\end{equation*}がそれぞれ得られますが、任意の解釈においてこれらの命題の値は一致するものと定めるということです。

例(存在命題の解釈)
以下の主張\begin{equation}
x^{2}=2\ \text{を満たす実数 }x\ \text{が存在する} \tag{1}
\end{equation}について考えます。変数\(x\)の定義域\(X\)がすべての実数を要素とする集合であるとき、上の主張は以下の存在命題\begin{equation}
\exists x\in X:x^{2}=2 \tag{2}
\end{equation}として定式化されます。存在命題の定義より、これは以下の論理和\begin{equation}
\bigvee\limits_{x\in X}x^{2}=2 \tag{3}
\end{equation}と同一視されます。実数\(x=\sqrt{2}\)について\(x^{2}=2\)は真であるため、論理和の定義より\(\left( 3\right) \)は真です。したがって、\(\left( 3\right) \)と同一視される\(\left( 2\right) \)さらには\(\left( 1\right) \)もまた真です。
例(存在命題の解釈)
以下の主張\begin{equation}
x^{2}=2\ \text{を満たす整数 }x\ \text{が存在する} \tag{1}
\end{equation}について考えます。変数\(x\)の定義域\(X\)がすべての整数を要素とする集合であるとき、上の主張は以下の存在命題\begin{equation}
\exists x\in X:x^{2}=2 \tag{2}
\end{equation}として定式化されます。存在命題の定義より、これは以下の論理和\begin{equation}
\bigvee\limits_{x\in X}x^{2}=2 \tag{3}
\end{equation}と同一視されます。任意の整数\(x\)について\(x^{2}=2\)は偽であるため、論理和の定義より\(\left( 3\right) \)は偽です。したがって、\(\left( 3\right) \)と同一視される\(\left( 2\right) \)さらには\(\left( 1\right) \)もまた偽です。
例(存在命題の解釈)
以下の主張\begin{equation*}
\text{出生地が日本ではない日本人が存在する}
\end{equation*}について考えます。変数\(x\)の定義域\(X\)がすべての人間を要素とする集合であるとき、上の主張は以下の存在命題\begin{equation}
\exists x\in X:\left( \lnot \left( x\ \text{の出生地は日本}\right) \wedge x\ \text{の国籍は日本}\right) \tag{2}
\end{equation}として定式化されます。存在命題の定義より、これは以下の論理和\begin{equation}
\bigvee\limits_{x\in X}\left( \lnot \left( x\ \text{の出生地は日本}\right) \wedge x\ \text{の国籍は日本}\right) \tag{3}
\end{equation}と同一視されます。日本は出生地主義ではなく血統主義を採用しているため、出生地が日本ではない日本人が存在します。そのような人を\(x=\overline{x}\)で表すとき、以下の命題\begin{equation*}
\lnot \left( \overline{x}\ \text{の出生地は日本}\right) \wedge \overline{x}\ \text{の国籍は日本}
\end{equation*}は真であるため、論理和の定義より\(\left( 3\right) \)は偽です。したがって、\(\left( 3\right) \)と同一視される\(\left( 2\right) \)さらには\(\left( 1\right) \)もまた真です。
例(存在命題の解釈)
変数\(x\)の定義域\(X\)と変数\(y\)の定義域\(Y\)がいずれもすべての自然数からなる集合であるものとします。このとき、以下の論理式\begin{equation*}
\forall x\in X,\ \exists y\in Y:x<y
\end{equation*}について考えます。これは、「自然数\(x\)を任意に選んだとき、それに対して\(x<y\)を満たす自然数\(y\)が存在する」という命題です。\(y=x+1\)とすればよいためこの論理式は真です。続いて、以下の論理式\begin{equation*}
\exists y\in Y,\ \forall x\in X:x<y
\end{equation*}について考えます。これは、「ある自然数\(y\)が存在して、それに対して任意の自然数\(x\)が\(x<y\)を満たす」という命題です。言い換えると、任意の自然数\(x\)よりも大きい自然数\(y\)が存在するという主張ですが、実際には、どのような自然数に対してもそれより大きい自然数が存在するため、この論理式は偽です。続いて、以下の論理式\begin{equation*}
\forall y\in Y,\ \exists x\in X:x<y
\end{equation*}について考えます。これは、「自然数\(y\)を任意に選んだとき、それに対して\(x<y\)を満たす自然数\(x\)が存在する」という命題です。\(y=1\)に対して\(x<y\)を満たす自然数\(y\)は存在しないため、この論理式は偽です。最後に、以下の論理式\begin{equation*}
\exists x\in X,\ \exists y\in Y:x<y
\end{equation*}について考えます。これは、「\(x<y\)を満たす自然数\(x,y\)が存在する」という命題です。\(x=1\)と\(y=2\)などいくらでも例が存在するため、この論理式は真です。

論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)であるとき、\(A\)において自由な現れが存在しない変数\(y\in Y\)を任意に選んだ上で存在命題\(\exists y\in Y\ A\)を作ることができますが、これは変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\begin{equation}
\left( \exists y\in Y\ A\right) \left( x_{1},\cdots ,x_{n}\right) \tag{1}
\end{equation}であるものと定めた上で、これをもとの開論理式\begin{equation}
A\left( x_{1},\cdots ,x_{n}\right) \tag{2}
\end{equation}と同一視します。開論理式を解釈することとは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}
\end{eqnarray*}を具体的に特定することを意味し、解釈を任意に選ぶと論理式\(\left( 1\right) \)からは以下の命題\begin{equation*}
\left( \exists y\in Y\ A\right) \left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right)
\end{equation*}が得られ、論理式\(\left( 2\right) \)からは以下の命題\begin{equation*}
A\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right)
\end{equation*}がそれぞれ得られますが、任意の解釈においてこれらの命題の値は一致するものと定めるということです。

例(存在命題の解釈)
命題関数\(P\left( x\right) \)は変数\(x\)の自由な現れを持つ開論理式です。このとき、\(x\)とは異なる変数\(y\)に注目した上で存在命題\begin{equation*}
\exists y\in Y\ P\left( x\right)
\end{equation*}を作ることができますが、これは\(P\left( x\right) \)と同一視されます。
例(存在命題の解釈)
命題関数\(P\left( x,y\right) \)は変数\(x,y\)の自由な現れを持つ開論理式です。このとき、\begin{equation}
\exists x\in X\ P\left( x,y\right) \tag{1}
\end{equation}は変数\(y\)の自由な現れを持つ開論理式であり、変数\(x\)の自由な現れを持ちません。したがって、以下の存在命題\begin{equation*}
\exists x\in X\ \left( \exists x\in X\ P\left( x,y\right) \right)
\end{equation*}は\(\left( 1\right) \)と同一視されます。

論理式\(A\)が閉論理式であるとき、変数\(x\in X\)を任意に選んだ上で存在命題\(\exists y\in Y\ A\)を作ることができますが、これもまた閉論理式であるものと定めた上で、もとの論理式\(A\)と同一視します。閉論理式を解釈することとは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式を構成するすべての命題関数の形状}
\end{eqnarray*}を具体的に特定することを意味しますが、任意の解釈において、論理式\(A\)から得られる命題と論理式\(\exists y\in Y\ A\)から得られる命題の真理値が一致するものと定めるということです。

例(存在命題の解釈)
命題関数\(P\left( x\right) \)は変数\(x\)の自由な現れを持つ開論理式です。このとき、\begin{equation}
\exists x\in X\ P\left( x\right) \tag{1}
\end{equation}は変数の自由な現れを持たない閉論理式です。したがって、\begin{equation*}
\exists x\in X\ \left( \exists x\in X\ P\left( x\right) \right)
\end{equation*}は\(\left( 1\right) \)と同一視されます。同様に、\begin{equation*}
\exists y\in Y\ \left( \exists x\in X\ P\left( x\right) \right)
\end{equation*}もまた\(\left( 1\right) \)と同一視されます。

次回は論理式の解釈について学びます。

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

プレミアム会員サービス

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

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

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