うさぎでもわかる離散数学　第3羽　述語論理編 - 工業大学生ももやまのうさぎ塾

修正：2019/6/10(Mon)
例題1-(2)の解答、解説を修正。

こんにちは、ももやまです！
$\forall$ , $\exists$ が入った論理式って理解するのが少し難しいですよね。
今日は、述語論理について説明しようと思います。

１．述語論理がなぜ必要なの？
２．述語論理の記号
- (1) 　for all　全称記号
- (2) 　for exist　存在記号
３．述語論理記号の組み合わせ
- パターン1　
- パターン2　
４．述語論理記号の変形
５．ちょっと練習
- 例題1
- 解答1
６．さらなる練習問題
７．さいごに

前回（第2羽）の「命題・真理値表編」はこちらから↓

１．述語論理がなぜ必要なの？

例えば $(1 \leqq 3 \land 3 \leqq 5) \to 1\leqq 5$ というのは常に正しいですよね。もちろん、実際の数字ではなくても変数 $a,b,c$ を使って、 $(a \leqq b \land b \leqq c) \to a \leqq c$ としても正しくなることはわかりますよね。なら、 $(p \land q) \to r$ も常に正しいとは言えるでしょうか。試しに真理値表を書いてみましょう。

$p$	$q$	$r$	$p \land q$	$p \land q \to r$
0	0	0	0	1
0	0	1	0	1
0	1	0	0	1
0	1	1	0	1
1	0	0	0	1
1	0	1	0	1
1	1	0	1	0
1	1	1	1	1

真理値表を見るとわかるのですが、 $(p,q,r) = (1,1,0)$ のときは0 (False) になってしまうので恒真とは言えませんね。

$(a \leqq b \land b \leqq c) \to a \leqq c$ の場合、変数 $b$ が関連しているから常に正しいと言えるのですが、 $(p \land q) \to r$ の場合、関連している変数がないため、常に正しいとは言えなくなってしまうのです。

そこで、関連する変数を指定して命題の真偽を判定するために述語論理が使われます。

２．述語論理の記号

ここで、述語論理に使われる記号をいくつか紹介しましょう。

(1) $\forall$ 　for all　全称記号

このAの記号の向きを変えた記号が全称記号となります。英語だと for Any と呼ばれます。さてこの記号、見たことある人が多いんじゃないでしょか。

ﾄﾞﾔｧｧｧｧ ( (｀･∀･´) )

みたいに。実は、上の顔文字の $\forall$ の記号って全称記号だったんですよ！

それはいいとして、この記号は下のように使います。変数 $x$ を用いた命題を $P(x)$ とし、命題を $x \leqq 5$ とします。（なお $x \in \mathbb{R}$ 、つまり $x$ は実数とします。）

$\forall x (P(x))$ というのは、実数範囲すべての $x$ について、 $P(x)$ が真となる。という意味になります。この命題の真偽を調べてみましょう。

$\forall x (P(x))$ の場合、 $P(x)$ を満たさない $x$ が1つでもあればそれが反例（今回の場合、例えば $x \not= 6$ ）となり、 $P(x)$ は偽ということができます。

$x \leqq 5$ なので、例えば $x = 6$ のときは命題 $P$ は満たせませんよね。なので、この命題は偽であると言うことができます。

ちなみに、 $\forall x (P(x))$ を満たせる命題 $P$ の例としては、 $\sin^{2}x + \cos^{2}x = 1$ が挙げられます。この式は $x$ がどんな値であろうが必ず成立しますよね。なのでこのパターンの場合は真ということができます。

(2) $\exists$ 　for exist　存在記号

このEの記号の向きを変えた記号が存在記号となります。英語だと for Exist と呼ばれます。ヨじゃないですよ。

(1)と同じように、変数 $x$ を用いた命題を $P(x)$ とし、命題を $x \leqq 5$ とします。

$\exists x (P(x))$ というのは、実数範囲の中の1つ以上の値 $x$ について、 $P(x)$ が真となる。という意味になります。この命題の真偽を調べてみましょう。

$\exists x (P(x))$ の場合、 $P(x)$ を満たす $x$ が1つでもあれば（今回の命題の場合、例えば $x = 3$ ）、 $P(x)$ は真ということができます。

$x \leqq 5$ なので、例えば $x = 3$ のときは命題 $P$ は満たしますよね。なので、この命題は真と言うことができます。

逆に偽というためには、すべての $x$ に対して成り立たないことを示さなければなりません。

３．述語論理記号の組み合わせ

２で紹介した記号を組み合わせた数式の命題も判定することができます。

述語論理を組み合わせられていた場合、必ず記号を左から順番に読んでください。
順番が大切になってきます。

パターン1　 $\forall x \exists y \ P(x,y)$

意味：すべての範囲の $x$ に対して、ある（1つ以上）の $y$ が存在し、 $P(x,y)$ が成立する。

この場合は、 $P(x,y)$ が真になるためには、すべての範囲の $x$ において、1つ以上成立する $y$ の値がある必要があります。

$x,y$ の範囲を1以上5以下の自然数としたのときの図のイメージはこのようになります。

f:id:momoyama1192:20190607095923g:plain

パターン2　 $\exists x \forall y \ P(x,y)$

意味：ある（1つ以上の） $x$ に対して、すべての $y$ が成立し、 $P(x,y)$ となる。

この場合は、 $P(x,y)$ が真になるためには、ある（1つ以上）の $x$ において、すべての $y$ の範囲で成立する必要があります*1。

$x,y$ の範囲を1以上5以下の自然数としたのときの図のイメージはこのようになります。

f:id:momoyama1192:20190607095920g:plain

この2つが違うことを実感していただくため、さらに1つ例を用意してみました。

$\forall x \exists y \ (x = y)$
$\exists x \forall y \ (x = y)$

この2つは、述語論理の順番を変えただけですが、実は真偽が異なります。

上の $\forall x \exists y \ (x = y)$ の場合、すべての $x$ の範囲内で $y$ が1つでも成り立てば真になりますね。 $x = y$ なので、それぞれの $x$ の範囲で成立する $y$ は必ず1つありますね。なのでこの命題は真となります。

一方 $\exists x \forall y \ (x = y)$ の場合、ある1つの $x$ の範囲内ですべての $y$ が成立しなければ真になりませんね。 $x = y$ の場合、それぞれの $x$ で成立する $y$ はたったの1つしかないのですべての $y$ において成立するとはいえませんね。なのでこの命題は偽となります。

ではここからはまた違う例題で述語論理が複数個ある場合の真偽判定を練習しましょう。

述語例えば、 $\exists x \forall y (x \lt y)$ という命題が領域 $\mathbb{N}$ （自然数）のもとで真になるか、というのを判断してみましょう。

この場合、全ての $y$ 、つまり $y = 1,2,3,\cdots$ において、 $x$ が成り立つ値がそれぞれ1つ以上あれば真となります。しかし、例えば $y = 1$ （下限）のときは、 $x$ で成り立つ値はありませんよね（下限より小さい数、つまり1未満の自然数は存在しない）。なので $\exists x \forall y (x \lt y)$ は偽となることがわかります。

一方 $\forall x \exists y (x \lt y)$ の場合、全ての $x$ 、つまり $x = 1,2,3,\cdots$ において、 $y$ が成り立つ値がそれぞれ1つ以上あれば真となります。

この式の場合、 $x$ の値がいくらであろうと、それより大きい値 $y$ は必ず存在するので（上限がないため） $\forall x \exists y (x \lt y)$ は真ということができます。

このような問題の場合、集合の上限（集合の中で自分以外の要素）と下限に注意する必要がある。ここで、有限な集合 $S$ を $S = \{1,2,3\}$ 、自然数の集合 $\mathbb{N}$ 、整数の集合 $\mathbb{Z}$ 、実数の集合 $\mathbb{R}$ の上限と下限を示したので参考までにどうぞ。

なお、上限と下限について簡単に説明すると、

上限：集合の中で自分以外の要素より大きい数がない要素
下限：集合の中で自分以外の要素より小さい数がない要素

です。厳密な定義ではないので、詳しい定義は第5羽を参考にしてください。

	下限	上限
$S$	1	3
$\mathbb{N}$	1	なし
$\mathbb{Z}$	なし	なし
$\mathbb{R}$	なし	なし

４．述語論理記号の変形

$\forall x P(x)$ の否定、 $\lnot \forall x P(x)$ について考えましょう。
$\forall x P(x)$ は、 $P(x)$ を満たす $x$ が1つでもなかったらその時点で偽となり、 $\lnot \forall x P(x)$ となりますよね。ということは、 $\exists x \lnot P(x)$ と言い換えることができます。つまり、

$\lnot \forall x P(x) \equiv \exists x \lnot P(x)$

が成立します。

同じようにして、 $\exists x P(x)$ の否定、 $\lnot \exists x P(x)$ について考えましょう。
$\exists x P(x)$ は、 $P(x)$ を満たす $x$ が1つでもあったらその時点で真となりますよね。これを言い換えると、すべての $x$ に対して、 $P(x)$ が成り立たなかったら偽となりますよね。ということは、 $\forall x \lnot P(x)$ と言い換えることができます。つまり、

$\lnot \exists x P(x) \equiv \forall x \lnot P(x)$

が成立します。

５．ちょっと練習

最後に少しだけ練習してみましょう。

例題1

つぎの(1),(2)の論理式の (a) $S= \{1,2,3\}$ の領域 (b) 自然数 $\mathbb{N}$ の領域 (c) 整数 $\mathbb{Z}$ の領域における真偽を判定しなさい。

(1) $\forall x \forall y \exists z \exists w \ \ (x \lt z) \lor (y \lt w \land x = z)$
(2) $\exists x \exists y \forall z \forall w \ \ (x \lt z) \lor (y \lt w \land x = z)$

解答1

(a),(b),(c) の領域の上限と下限を表す。

	下限	上限
(a)	1	3
(b)	1	なし
(c)	なし	なし

(1)

$\forall x \forall y \exists z \exists w$ ということは、すべての範囲 $x,y$ に対して、それぞれ1つ以上の $z,w$ を満たせばOK。

(a) のとき、 $(x,y,z) = (3,3,3)$ のとき、3が上限なため、3より大きい数を満たす $w$ が1つも存在しない。よって偽。

(b) のとき、上限がないため、すべての $x$ において、 $x$ より1だけ大きい数も存在する。よって $z$ の値は1つ以上存在する。よって真。

(2)

$\exists x \exists y \forall z \forall w$ ということは、ある1つ以上の $x,y$ が、すべての範囲で $z,w$ を満たせばOK。

(a),(b),(c)

(i) $x \lt z$ を考えます。ある $x$ に対して、 $z = x$ とします。このとき、 $x \lt z$ なので、どのような $x$ に対しても必ず $x = z$ においては成立しませんね。

(ii) $y \lt w \land x = z$ の場合を考えます。たとえ $x = z$ だとしても、 $y \lt w$ の場合も(i)と同様にある $y$ に対して、 $w = y$ とします。このとき、 $y \lt w$ なので、どのような $y$ に対しても必ず $y = w$ においては成立しませんね。