離散数学　述語論理の補足＋演習問題 - 工業大学生ももやまのうさぎ塾

こんにちは、ももやまです！

今回は、多くの人が苦手としている2変数以上の述語論理の読み方の練習問題をもってきました！

１．基本的な述語論理読み方のルール
２．練習1
- 問題1
- 解答1
３．練習2
- 問題1
- 解説1
４．練習3
５．さいごに

１．基本的な述語論理読み方のルール

$\forall x \ P(x)$ は、範囲内すべての $x$ で成立すれば $P(x)$ が真
$\exists x \ P(x)$ は、範囲内のある（1つ以上の） $x$ で成立すれば $P(x)$ が真
$\forall x \exists y \ Q(x,y)$ のような、複数の述語論理がある場合は、必ず左側から読むこと

述語論理について、まだよくわかっていない人はこちらの記事で復習しましょう…！

www.momoyama-usagi.com

次の演習から出てくる記号 $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ , $\mathbb{R}$ はそれぞれ、

$\mathbb{N}$ ：自然数範囲
$\mathbb{Z}$ ：整数範囲
$\mathbb{Q}$ ：有理数範囲
$\mathbb{R}$ ：実数範囲

を表します。

自然数は0を含まないスタイル（高校数学は必ずこっち）と0を含むスタイル（一部の大学の先生など）がありますが、どちらでやっても支障のでないように両者の場合の答えを載せています。

２．練習1

問題1

つぎの(1)〜(4)

(1) 自然数 $\mathbb{N}$
(2) 整数 $\mathbb{Z}$
(3) 有理数 $\mathbb{Q}$
(4) 実数 $\mathbb{R}$

において、論理式 $A,B,C,D$ が成立する場合はYを、成立しない場合はNを書きなさい。

論理式一覧 \[
A = \forall a \exists b \ (a + b = a) \\
B = \forall a \exists b \ (a + b = 0) \\
C = \exists a \forall b \ (a + b = 0) \\
D = \exists a \exists b \ (a \lt b \land \lnot \exists c ( (a < c ) \land (c < b) ) \]

解答1

まずは、それぞれの領域の上限、下限、と連続性*1を調べます。
この問題の場合は、自然数を1スタートにするか0スタートにするかで答えが変わってくるので注意してください。

領域	下限	上限	連続性
$\mathbb{N}$	1	なし	No
$\mathbb{Z}$	なし	なし	No
$\mathbb{Q}$	なし	なし	Yes
$\mathbb{R}$	なし	なし	Yes

論理式 A

すべての $a$ に対しある1つ以上の $b$ が存在し、 $a + b = a$ を満たせばOK。

$\mathbb{N}$ 自然数領域

式 $a + b = a$ は、 $b = 0$ のときのみ成立する。

自然数が1スタートの場合：0は自然数ではないため、 $b = 0$ を代入することができない。
よって答えはN。

自然数が0スタートの場合：0も自然数となるため、 $b = 0$ を代入することができる。
よって答えはY。

$\mathbb{Z},\mathbb{Q},\mathbb{R}$ それ以外の領域

たとえば、 $b = 0$ の場合は $a = a$ となり、すべての $a$ の範囲で題意を満たすことができる。よってすべてY。

論理式 B

$\mathbb{N}$ 自然数領域

自然数範囲なので $a,b \gt 0$ となる。例えば、 $a = 1$ のときは $b$ が成立するような値が存在しないため*2、自然数範囲ではNとなる。

$\mathbb{Z},\mathbb{Q},\mathbb{R}$ それ以外の領域

式を変形すると、 $a = -b$ となる。 $a$ がどのような値であっても1つ $b$ の値を求めることができる。よって答えはY。

論理式 C

すべての領域

述語論理は左から読む必要があり、その順番の大切さがわかる問題だ。
$\exists a \forall b$ なので、ある1つ以上の値 $a$ に対して、すべての $b$ の範囲で題意が満たせればOKとなる。しかし、今回の題意は $a + b = a$ である。

どんな $a$ の値でも、それを満たせるような $b$ はたかが1つしか存在しない。よって、今回の領域ではすべてNとなる。

論理式 D

この問題を日本語化すると、

ある1つ以上の $a,b$ に対し、 $a \lt b$ が成立かつ $a,b$ の間にある変数 $c$ が1つも入らない。

となります。

$\mathbb{N}, \mathbb{Z}$ 連続性がない領域

連続性がない領域の場合を考えましょう。
たとえば、 $a = 2$ , $b = 3$ を考えます。
このとき、2と3の間に入る変数なんてありませんよね。

なので、答えはYとなります。

$\mathbb{Q}, \mathbb{R}$ 連続性がある領域

次に連続性がある領域の場合を考えましょう。
連続性がある場合、どんなに近い数字でも、その間にあてはまる数はありますよね。*3。

よって答えはNとなります。

以上4つの答えをまとめると、以下のようになります。

領域	$A$	$B$	$C$	$D$
$\mathbb{N}$	*	N	N	Y
$\mathbb{Z}$	Y	Y	N	Y
$\mathbb{Q}$	Y	Y	N	N
$\mathbb{R}$	Y	Y	N	N

*部分：自然数が1スタートなら N、0スタートなら Y。

３．練習2

問題1

領域 $X_1 = \{1,2,3,4\}$ , $X_2 = \mathbb{N}$ , $X_3 = \mathbb{Z}$ とする。

また、 $X_1 \times X_1$ , $X_2 \times X_2$ , $X_3 \times X_3$ 上の関係 $\preceq$ をつぎのように定義する。\[ (x,y) \preceq (z,w) \Leftrightarrow (x \lt z) \lor (x=z \land y \leqq w)\]このとき、以下の論理式 $A,B,C,D$ が領域 $X_1$ , $X_2$ , $X_3$ のもとでの真となる場合はYを、偽となる場合をNと答えなさい。

論理式一覧 \[
A = \forall a \forall b \exists c  \exists d \ \left( (a,b) \preceq (c,d) \right) \\
B = \forall a \forall b \exists c  \exists d \ \left( (c,d) \preceq (a,b) \right) \\
C = \exists a \exists b \forall c  \forall d \ \left( (a,b) \preceq (c,d) \right) \\
D = \exists a \exists b \forall c  \forall d \ \left( (c,d) \preceq (a,b) \right) \]

解説1

このような問題では、それぞれの領域の上限値と下限値があるかがポイントになってきます。それぞれの領域 $X_1$ , $X_2$ , $X_3$ の上限と下限はつぎのとおりになります。

連続性は、 $X_1$ , $X_2$ , $X_3$ すべてにないため、今回は表にしていません。

領域	下限	上限
$X_1$	1	4
$X_2$	1	なし
$X_3$	なし	なし

上限値、下限値が存在するかしないかがポイントなので、上限値の数値、下限値の数値は関係ありません。なので自然数を1スタートとしようが0スタートにしようが答えの結果は変わりません。

論理式 A

すべての $a,b$ に対して、ある1つ以上の $c,d$ が存在し、つぎの式を満たす。\[ (a \lt c) \lor (a=c \land b \leqq d)\]つまり、領域内すべての $a,b$ に対して、1つの $c,d$ が上の式を満たせばよい。

$X_1$ 上限も下限もある場合

$a \lt c$ は、 $a,c$ の上限値である $(a,c) = (2,2)$ で成立しなくなってしまう。しかし、 $(a=c \land b \leqq d)$ の部分では、 $(a,c) = (2,2)$ でも成立する可能性がある。 $b \leqq d$ は $b$ がどんな値であっても最低1つは $d$ を満たす可能性がある*4。なので答えはY。

$X_2$ 上限がなくて下限がある場合。

上限がないため、 $a \lt c$ は、 $a$ をいくら大きくしても、それより1だけ大きい値 $c = a + 1$ が必ず存在する。なので答えはY。

$X_3$ 上限も下限もない場合。

$X_2$ と同じく上限がないため、 $X_2$ と同じ理由でY。

論理式 B

すべての $a,b$ に対して、ある1つの $c,d$ が存在し、つぎの式を満たす。\[ (c \lt a) \lor (c=a \land d \leqq b)\]つまり、領域内すべての $a,b$ に対して、1つの $c,d$ が上の式を満たせばよい。

$X_1$ 上限も下限もある場合

$c \lt a$ は、 $a,c$ の下限値である $(c,a) = (0,0)$ で成立しなくなってしまう。しかし、 $(c=a \land d \leqq b)$ の部分では、 $(a,c) = (0,0)$ でも成立する可能性がある。 $d \leqq b$ は $b$ がどんな値であっても最低1つは $d$ を満たす数がある*5。なので答えはY。

$X_2$ 上限がなくて下限がある場合。

下限は $X_1$ と同様に設けられているため、 $X_1$ と同じ考えで解く。よって答えはY。

$X_3$ 上限も下限もない場合。

下限がないため、 $c \lt a$ は、 $a$ をいくら小さくしても、それより1だけ小さい値 $c = a - 1$ が必ず存在する。なので答えはY。

論理式 C

ある（1つの） $a,b$ に対して、すべての $c,d$ が成立、つぎの式を満たす。\[ (a \lt c) \lor (a=c \land b \leqq d)\]つまり、領域内の1つの $a,b$ に対して、すべての領域内で $c,d$ が上の式を満たせばよい。

$X_1$ 上限も下限もある場合

$a \lt c$ だけで考えることができます。例えば下限値である $a$ が1のときを考えましょう。このとき、 $c$ は1以外のすべての領域で存在しますね。

なので、 $(a,c) = (1,1)$ のとき $a=c \land b \leqq d$ が成立するかどうかを考えましょう。 $a = c$ は明らかに成立するので $b \leqq d$ だけを考えればいいですね。 $b$ が下限値(1)のとき、それより小さい $d$ の値は存在しませんね。なので、 $b \leqq d$ は、 $b$ が下限値のときはすべての $d$ の範囲で成立すると言えます。よって答えはY。

$X_2$ 上限がなくて下限がある場合

下限値が存在するので、 $X_1$ と同じ考え方で解くことができます。
答えはY。

$X_3$ 上限がなくて下限がある場合

$a \lt c$ を考えます。ある1つの $a$ の値に対して、それより1だけ小さい $c$ は必ず存在しますね。なので、どんなに $a$ を小さくしてもそれより小さい値 $c = a - 1$ が存在します。なので、ある1つの $a$ に対して、すべての $c$ を満たすような $a \lt c$ は存在しません。

つぎに $a=c \land b \leqq d$ の $a = c$ を考えます。
ある1つの $a$ の値に対して、すべての $c$ を満たせるようにすることなんてできませんよね……*6。

よって、 $c = a- 1$ のとき、いずれの2つも満たせないので答えはNとなる。

論理式 D

ある（1つの） $a,b$ に対して、すべての $c,d$ が成立、つぎの式を満たす。\[ (c \lt a) \lor (c=a \land d \leqq b)\]つまり、領域内の1つの $a,b$ に対して、すべての領域内で $c,d$ が上の式を満たせばよい。

$X_1$ 上限も下限もある場合

$c \lt a$ の場合を考えます。例えば上限値である $a$ が3のときを考えましょう。このとき、 $c$ は3以外のすべての領域で成立しますね。

つぎに $(a,c) = (3,3)$ のとき $c=a \land d \leqq b$ が成立するかどうかを考えましょう。 $c = a$ は明らかに成立するので $d \leqq b$ だけを考えればいいですね。
$b$ が上限値(3)のとき、それより大きい $d$ の値 $d = b + 1$ は存在しませんね。なので、 $b \leqq d$ は、 $b$ が上限値のときはすべての $d$ の範囲で成立すると言えます。

よって答えはY。

$X_2$ 上限がなくて下限がある場合

$c \lt a$ を考えます。ある1つの $a$ の値に対して、それより1だけ大きい数 $c$ は必ず存在しますね。なので、どんなに $a$ を大きくしても、それより大きい値 $c = a + 1$ が存在します*7。なので、ある1つの $a$ に対して、すべての $c$ を満たすような $a \lt c$ は存在しません。

つぎに $c=a \land d \leqq b$ の $c = a$ を考えます。
ある1つの $a$ の値に対して、すべての $c$ を満たせるようにすることなんてできませんよね……*8。

よって、 $c = a + 1$ のとき、いずれの2つも満たせないので答えはNとなる。

$X_3$ 上限も下限もない場合

上限値が存在しないので、 $X_2$ と同じ解き方で解くことができます。
よって答えはN。

以上4つの答えをまとめると、以下のようになります。

領域	$A$	$B$	$C$	$D$
$X_1$	Y	Y	Y	Y
$X_2$	Y	Y	Y	N
$X_3$	Y	Y	N	N

４．練習3

最後にもう1問練習してみましょう！

領域 $S_1 = \{1,2,3\}$ , $S_2 = \mathbb{N}$ , $S_3 = \mathbb{Z}$ とする。
（ただし自然数は1以上とする）

次の論理式A,B,C,Dが成り立つならばYesを、成り立たないならばNoと答えなさい。

ただし、\[P(x,y) = ( ( |x - y| \leqq 1) \land (|x| + |y| = |x+y| ) ) \]とする。

論理式一覧 \[
A = \forall x \exists y \ \mathrm{s.t.} \ P(x,y) \\
B = \forall x \exists y \ \mathrm{s.t.} \ P(y,x) \\
C = \exists x \forall y \ \mathrm{s.t.} \ P(x,y) \\
D = \exists x \forall y \ \mathrm{s.t.} \ P(y,x) \\
\] ※ s.t. は such that の略、「となるような」などと訳す

この問題の答えはこちらで受け付けています。
回答を入力すると採点され、採点結果と解説を自動でお返しします。

チャレンジお待ちしております！