離散数学 (10) 2016 年 7 月 1 日演習問題岡本吉央

離散数学 (10)
演習問題
2016 年 7 月 1 日
岡本吉央
提出締切： 2016 年 7 月 8 日講義終了時
ととする．このとき，≡p が同値関係であることを証
復習問題 10.1 次に挙げるそれぞれの集合 A とそ
の上の関係 R に対して，R を表現するグラフを描け．明せよ．
また，それぞれの関係 R が (a) 反射性を持つか，(b)
完全性を持つか，(c) 対称性を持つか，(d) 反対称性
追加問題 10.7 集合 A = {−1, −2, 0, 1, 2} 上の次の
を持つか，(e) 推移性を持つか，それぞれ答えよ．
関係 R1 , R2 , R3 に対して，その関係を表現するグラ
フを描け．また，それぞれの関係が (a) 反射性を持
1. 集合 A = {1, 2, 3, 6} 上の関係 R で，任意の
つか，(b) 完全性を持つか，(c) 対称性を持つか，(d)
x, y ∈ A に対して x R y であることを x が y の
約数であることと定義する．
反対称性を持つか，(e) 推移性を持つか，それぞれ答
えよ．
2. 集合 A = {∅, {a}, {b}, {a, b}} 上の関係 R で，
任意の X, Y ∈ A に対して X R Y であること
を X ⊆ Y と定義する．
1. 任意の x, y ∈ A に対して，x R1 y であること
を x − y ≤ 1 であることとする．
2. 任意の x, y ∈ A に対して，x R2 y であること
を |x − y| ≤ 1 であることとする．
3. 集合 A = {1, 2, 3, 4, 5} 上の関係 R で，任意の
x, y ∈ A に対して x R y であることを x < y と
定義する．
3. 任意の x, y ∈ A に対して，x R3 y であること
を x2 − y 2 = 0 であることとする．
4. 集合 A = {1, 2, 3, 4, 5} 上の関係 R で，任意の
x, y ∈ A に対して x R y であることを x = y と
定義する．
追加問題 10.8 R2 上の関係を次のように定義す
る．すなわち，任意の (x, x0 ), (y, y 0 ) ∈ R2 に対して，
(x, x0 ) (y, y 0 ) であることを x ≤ y かつ x0 ≤ y 0 で
あることとする．このとき，が半順序となること
5. 集合 A = {1, 2, 3, 4, 5} 上の関係 R で，任意の
x, y ∈ A に対して x R y であることを x ≡ y
を証明せよ．
(mod 3) と定義する．
追加問題 10.9 任意の集合 A, B と任意の写像 f : A →
復習問題 10.2 R 上の大小関係 ≤ が全順序であるこ
B を考える．A 上の関係 R を次のように定義する．
とを証明せよ．
すなわち，任意の x, y ∈ A に対して，x R y であるこ
復習問題 10.3 任意の集合 A に対して，その冪集合
とを f (x) = f (y) であることとする．このとき，R
2A 上の関係 ⊆ が半順序であることを証明せよ．
が同値関係となることを証明せよ．
復習問題 10.4 1 以上の整数全体の集合を Z+ と書
追加問題 (発展) 10.10 R2 上の関係を次のよう
くことにする．Z+ 上の関係 | を次のように定義する．に定義する．すなわち，任意の (x, x0 ), (y, y 0 ) ∈ R2
すなわち，任意の a, b ∈ Z+ に対して a | b であるこに対して，(x, x0 ) (y, y 0 ) であることを
とは a が b の約数であることとする．このとき，| が
x ≥ y ならば「x = y かつ x0 ≤ y 0 」
半順序であることを証明せよ．
であることとする．このとき，が全順序となるこ
復習問題 10.5 R 上の関係 = が同値関係であること
とを証明せよ．(ヒント：R 上の大小関係 ≤ が完全
を証明せよ．
性，すなわち，任意の x, y ∈ R に対して「x ≤ y ま
復習問題 10.6 p を 1 以上の整数として，N を 0 以
たは y ≤ x」が成り立つ，ということを使って，場
上の整数全体の集合とする．N 上の関係 ≡p を次の
合分けを行ってみよ．) (補足：これは R2 上の辞書
ように定義する．すなわち，任意の m, n ∈ N に対し
式順序と呼ばれるものである．)
て m ≡p n であることは m ≡ n (mod p) であるこ
1

Download Report