1. No category

2014 年度離散数学入門 c 中間テスト（演習問題）
答のみでなく、理由・証明もつけること。このテストは成績には関係ありません。
1
f : X → Y を関数とし、次の に ⊆, ⊇, = のどれを入れれば正しい式になるか、証明
を付けて答え、= でない場合には、= にならない例を挙げよ。
(1) f (A1 ∩ A2 ) f (A1 ) ∩ f (A2 )
(2) f −1 (B1 ∩ B2 ) f −1 (B1 ) ∩ f −1 (B2 )
2
(A1 , A2 ⊆ X)
(B1 , B2 ⊆ Y )
N, Z, Q をそれぞれ自然数の集合、整数の集合、有理数の集合とする。以下の真偽を答えよ。
(1) ∀x ∈ N ∀y ∈ N ∃z ∈ Q [x = y − z]
(2) ∀x ∈ N ∃y ∈ N ∀z ∈ Z [x = y − z]
(3) ∃x ∈ N ∀y ∈ Q ∃z ∈ Q [x = y − z]
3
s1 = {4, 8}, s2 = {2, 3}, s3 = {6, 9}, s4 = {5, 7}, S = {s1 , s2 , s3 , s4 } とおく。S の関係 R を
si R sj ⇐⇒ ∃x ∈ si ∃y ∈ sj [x|y ∨ y|x]
（ただし、l|m とは l が m を割り切ること）で定める。R は同値関係か？
4
グラフ G = (V, E) を V = {v1 , v2 , v3 , v4 }, {vi , vj } ∈ E ⇐⇒ i ̸= j ∧ si R sj , ただし、R は
上の問題で定義したもの、で与える。このグラフの隣接行列をもとめよ。
˜ = (R ∪ R−1 )∗
Z2 の関係 R を (x, y)R(x′ , y ′ ) ⇐⇒ x′ = x ± 1 & y ′ = y + 2 で定める。R
−1
˜ 0)} を求めよ。
（R ∪ R の反射推移閉包）とおく。S = {(ξ, η) | (ξ, η)R(0,
5
2014 年度離散数学入門 c 中間テスト（演習問題）解答
1
(1) f (A1 ∩ A2 ) ⊆ f (A1 ) ∩ f (A2 )
(2) f −1 (B1 ∩ B2 ) = f −1 (B1 ) ∩ f −1 (B2 )
2
(1) 真
(2) 偽
(3) 真
3
推移律が成立しないので、同値関係ではない。

1
0
0
1
1
0
0
0

0

0 

0 

0
4
0

 1

 0

0
4
S = {(ξ, η) | η ≡ 2ξ (mod 4)}