【記号論理】3 述語論理～「すべての」、「ある」を記号で表現する～

こんにちは、これが322本目の記事となったすうじょうです。今日は、大学数学の解説記事です。今回の内容は、大学数学の基礎となる記号論理より述語論理を解説します。

この記事は、以下の記事の続きです。

述語論理

述語論理の必要性

「1 命題論理の基礎」において、命題に変数を含む文を入れなかった。これは、命題論理だけでは以下のような問題が発生するためだ。

$${x}$$は奇数である

上の文は、命題ではない。この文の真偽を判断するためには、情報が不足しているからだ。その情報というのは、変数$${x}$$がどんな値を取るのかというものだ。それがわからないと、文の真偽が判断できない。

また、命題論理式だけでは、以下のような少し複雑な文を簡潔に表現することができない。

任意の自然数$${x}$$に対して、$${x < y}$$となる自然数$${y}$$が存在する

そこで、後に説明する限定記号を利用すると、この文を簡潔に表現することができる。

述語とは

数学において、文中の変数に要素を代入することで真偽が判断でき、命題となる文を述語または条件といい、$${P(x)}$$(変数が1個の述語)や$${P(x,y)}$$(変数が2個の述語)などと表す。

述語について、各変数のとりうる値の集合を変域または対象領域という。ふつう変数とともに明示されるが、文脈などから変域が明らかであるときは省略できる。

述語論理式とは

数学で「すべての」または「任意の」、「存在する」または「ある」という表現が使われるが、これを限定記号(限量子)で表し、命題変数と論理記号、限定記号のみで述語(命題)を表現したものを述語論理式という。その定義は以下のように帰納的に定義される。

述語論理式の帰納的定義

1. 述語は述語論理式である

2. $${F,G}$$が述語論理式のとき, $${(\lnot F), (F \land G), (F \lor G), (F \to G), (F \leftrightarrow G)}$$は述語論理式である

3. $${F}$$が述語論理式で$${x}$$がその変数のとき,$${\forall x F}$$, $${\exists x F}$$は述語論理式である 

4. 以上で定義されるもののみが述語論理式である

※この定義の説明は、命題論理式と同様なので省略する。また、述語論理の具体例は後で示す。

限定記号の意味

ここからは、単純な述語論理式を例にして、各論理記号の意味を理解するために解釈の仕方などを説明していく。

全称記号

例えば、 $${\forall x, P(x)}$$のように書き、「すべての$${x}$$に対して$${P(x)}$$が成り立つ」や「任意の$${x}$$に対して$${P(x)}$$が成り立つ」などと読む。$${\forall}$$は、英語で「for all」や「for any」と読む。

この意味を理解するために、変域を明示してこの述語論理式と論理的同値である命題論理式を示す。

$${U=\{x_1,x_2,…,x_n\}}$$のとき
$${\forall x \in U, P(x) \equiv P(x_1) \land P(x_2) \land … \land P(x_n)}$$

つまり、全称記号を含む命題はその変域すべてで成り立つとき真で、変域の中に反例が1つでもあれば偽である。

存在記号

例えば、 $${\exists x, P(x)}$$のように書き、「$${P(x)}$$が成り立つような$${x}$$が存在する」や「ある$${x}$$に対して$${P(x)}$$が成り立つ」などと読む。$${\exists}$$は、英語で「there exists」などと読む。ここでの存在するとは、少なくとも1つあるということである。

この意味を理解するために、変域を明示してこの述語論理式と論理的同値である命題論理式を示す。

$${U=\{x_1,x_2,…,x_n\}}$$のとき
$${\exists x \in U, P(x) \equiv P(x_1) \lor P(x_2) \lor … \lor P(x_n)}$$

つまり、存在記号を含む命題はその変域の中で成り立つ例が1つでもあればとき真で、変域すべてで成り立たないとき偽である。

限定記号の否定

全称記号や存在記号の否定には、以下のような論理的同値関係が成り立つ。

$${\lnot \forall x, P(x) \equiv \exists x, \lnot P(x)}$$
$${\lnot \exists x, P(x) \equiv \forall x, \lnot P(x)}$$

この証明は、述語論理式と命題論理式の論理的同値関係を用いるとできる。(問題6)

全称記号と存在記号の併用

全称記号と存在記号をともに用いるときは注意する必要がある。例えば、以下の2つの命題は記号の順番が異なるだけだがまったく意味が異なる。

①$${\forall x, \exists y, P(x,y)}$$
②$${\exists y, \forall x, P(x,y)}$$

①は「すべての$${x}$$に対して、それぞれ$${P(x,y)}$$が成り立つ$${y}$$が存在する」という意味である。それに対して、②は「ある$${y}$$が存在して、その$${y}$$はすべての$${x}$$に対して$${P(x,y)}$$が成り立つ」という意味になる。限定記号の順番どおりに解釈する必要があり、日本語の文にして主述の関係を考える必要がある。抽象的な話ではわからないと思うので、この具体例は問題7に入れた。

述語論理式(命題)の実際

述語論理式の様々な書き方が存在するので、その一部の例を紹介する。

$${\forall x \in A, \exists y \in B, x+y=1}$$
$${\forall x \in A \space \exists y \in B \space (x+y=1)}$$
$${\forall x \in A \space \exists y \in B \space :(x+y=1)}$$
$${\forall x \in A, \exists y \in B \space [x+y=1]}$$
$${\exists x \in A \space s.t. \space x^2 = 2}$$

※$${s.t.}$$は「そのような」という意味の「such that」の略で、$${s.t.}$$以後の条件を満たす変数が存在する、などというときに用いられる。
※変域が自明なときは、$${\in A}$$などは省略されることがある。

また、$${\forall x \in A, \forall y \in A}$$という意味で$${\forall x, y \in A}$$や$${\forall x, \forall y \in A}$$と書かれることがある。

演習問題3

問題6 $${U=\{x_1,x_2,\cdots ,x_n\}}$$のとき、次の論理的同値関係が成り立つことを証明せよ。
(1)$${\lnot \forall x \in U, P(x) \equiv \exists x \in U, \lnot P(x)}$$
(2)$${\lnot \exists x \in U, P(x) \equiv \forall x \in U, \lnot P(x)}$$

[方針]
限定記号の命題論理式への変形とド・モルガンの定理を用いる

(1)
[証明]

$$
\begin{aligned}
\lnot \forall x \in U, P(x)&\equiv \lnot (P(x_1) \land P(x_2) \land … \land P(x_n))\\
&\equiv \lnot P(x_1) \lor \lnot P(x_2) \lor … \lor \lnot P(x_n)\\
&\equiv \forall x \in U, \lnot P(x) \qquad \qquad \qquad \qquad \qquad \Box\\
\end{aligned}
$$

(2)
[証明]

$$
\begin{aligned}
\lnot \exists x \in U, P(x)&\equiv \lnot (P(x_1) \lor P(x_2) \lor … \lor P(x_n))\\
&\equiv \lnot P(x_1) \land \lnot P(x_2) \land … \land \lnot P(x_n)\\
&\equiv \exists x \in U, \lnot P(x) \qquad \qquad \qquad \qquad \qquad \Box\\
\end{aligned}
$$

問題7 次の命題の真偽を答えよ。ただし、$${\N}$$には0を含まないものとする。
(1)$${\forall x \in \N, x^2=1}$$
(2)$${\exists x \in \N, x^2=1}$$
(3)$${\forall x \in \R, \forall y \in \R, \forall z \in \R, (x \leq y) \land (y \leq z) \to (x \leq z)}$$
(4)$${\forall x \in \N, \exists y \in \N, x < y}$$
(5)$${\exists y \in \N, \forall x \in \N, x < y}$$
(6)$${\exists x \in \Z, \forall y \in \Z, x < y}$$
(7)$${\forall x \in \N, \exists y \in \N, x+y=3}$$
(8)$${\forall x \in \R, \exists y \in \R, x+y=3}$$

[方針]
ここに各命題を日本語にしたものを示していく。
(1)すべての自然数$${x}$$に対して、$${x^2=1}$$が成り立つ
(2)$${x^2=1}$$が成り立つような自然数$${x}$$が存在する
(3)すべての実数$${x,y,z}$$に対して、 $${x \leq y}$$かつ $${y \leq z}$$ ならば$${x \leq z}$$が成り立つ
(4)すべての自然数$${x}$$に対して、それぞれ$${x < y}$$が成り立つ自然数$${y}$$が存在する
(5)ある自然数$${y}$$が存在して、その$${y}$$はすべての自然数$${x}$$に対して$${x < y}$$が成り立つ
(6)ある整数$${x}$$が存在して、その$${x}$$はすべての整数$${y}$$に対して$${x < y}$$が成り立つ
(7)すべての自然数$${x}$$に対して、それぞれ$${x+y=3}$$が成り立つ自然数$${y}$$が存在する
(8)すべての実数$${x}$$に対して、それぞれ$${x+y=3}$$が成り立つ実数$${y}$$が存在する
[解答]
(1)偽, 反例:$${x=2(2^2 \neq 1)}$$
(2)$${x=1}$$のとき, $${x^2=1}$$なので真
(3)実数は緻密に存在するので真
(4)自然数は無限に存在するので真
(5)最大の自然数は存在しないので偽
(6)最小の整数は存在しないので偽
(7)偽, 反例:$${x=3}$$
(8)$${x}$$が実数のとき, $${3-x}$$は実数なので真

問題8 次の命題の否定を答えよ。
(1)$${\forall x \in \N, \exists y \in \R, \sqrt{x}=y}$$
(2)$${\exists x \in \Z, 0 < x \leq 2}$$
(3)$${\forall k > 0, \exists q \in \Bbb{Q}, \frac{1}{k} = q}$$
(4)$${\exists x \in \{0,1,2\}, \forall y \in \R, (xy=0) \lor (x+y>0)}$$
(5)$${\forall x \in \R, \forall y \in \R, x=y=0 \to x^2+y^2=0}$$

[解答]
(1)$${\exists x \in \N, \forall y \in \R, \sqrt{x} \neq y}$$
(2)$${\forall x \in \Z, (x \leq 0) \lor (x > 2)}$$
(3)$${\exists k > 0, \forall q \in \Bbb{Q}, \frac{1}{k} \neq q}$$
(4)$${\forall x \in \{0,1,2\}, \exists y \in \R, (xy \neq 0) \land (x+y \leq 0)}$$
(5)$${\exists x \in \R, \exists y \in \R, (x=y=0) \land  (x^2+y^2 \neq 0)}$$

※(5)では、$${P→Q≡¬P∨Q}$$を用いて変形をした。

最後に

今回は、大学数学・記号論理の解説記事として、述語論理について解説しました。今回登場した記号は、大学数学の教科書などの命題で実際に目にするもので、大学数学を理解するためには重要な内容です。

ここまでの計3回で記号論理の基本的な内容を解説しました。このシリーズでは、理解の助けとなるように難しすぎないレベルの演習問題を付けています。これ以上の内容としては、論理学や論理回路などがあります。論理回路については、情報系の内容ですがそのうち記事を書きたいと思っています。では。