離散数学演習問題(1)解答

離散数学演習問題 (1) 解答
1. A = {a, b, c}, P = {1, 2, 3}, Q = {2, c} のとき
(a) A ∩ P = φ
(b) A ∪ P = {a, b, c, 1, 2, 3}
(c) A ∪ Q = {a, b, c, 2}
(d) A × Q = {(a, 2), (b, 2), (c, 2), (a, c), (b, c), (c, c)}
(e) n (A ∪ (P ∩ Q)) = 4
(f) (A ∪ P ) \ Q = {a, b, 1, 3}
2. 素数の個数は無限個である。6780 の倍数は，6780 に任意の整数を掛けたものすべ
てであるから，個数は無限個になる。答えは
(a), (b), (c), (h)
である。
3. 魚の好きな人の集合を F ，野菜が好きな人の集合を V ，肉が好きな人の集合を M
とする。そうすると，題意より
n(F ) = 25,
n(V ) = 38,
n(M ∩ V ) = 16,
n(M) = 50,
n(M ∩ F ) = 12,
n(F ∩ V ) = 10,
n(F c ∩ V c ∩ M c ) = 5
となる。
求めるものは n(M ∩ V ∩ V ) であり，それは公式
n(F ∪ V ∪ M) = n(F ) + n(V ) + n(M)
− n(M ∩ V ) − n(M ∩ F ) − n(F ∩ V ) + n(M ∩ V ∩ V )
よりであるから
n(F ∩ V ∩ M) = n(F ∪ V ∪ M) − n(F ) − n(V ) − n(M)
+ n(M ∩ V ) + n(M ∩ F ) + n(F ∩ V )
として求まる。したがって，上式右辺の未知量 n(F ∪ V ∪ M) (少なくともどれか一
つが好きな人の数) を求める必要がある。
少なくともどれか一つ好きな人の集合は，全てが嫌いな人の余集合であるから
n(F ∪ V ∪ M) = 90 − n(F c ∩ V c ∩ M c ) = 85
となる。したがって，
n(F ∩ V ∩ M) ＝ 85 − 25 − 38 − 50 + 16 + 12 + 10 = 10
を得る。
4. (a) R = {(2, 5), (4, 4), (6, 3), (8, 2), (10, 1)}
(b) R の定義域は {2, 4, 6, 8, 10}，値域は {5, 4, 3, 2, 1}
(c) R−1 = {(5, 2), (4, 4), (3, 6), (2, 8), (1, 10)}
(d) R ◦ R = {(4, 4)}
5. (a) 関係 “x は y 以下” は反射的，反対称的でかつ推移的
(b) 関係 “x + y = 12” は対称的
(c) 関係 “x y はある整数の二乗である” は反射的，対称的かつ推移的
6. (a)
n
a r k−1 =
k=1
a (1 − r n )
1−r
解答： n = 1 のときは，左辺=右辺=a となり明らかに成り立っている。任意の
n で成り立っているものとすと，n + 1 のときは
n+1
k=1
ar
k−1
=
n
a r k−1 + a r n =
k=1
a (1 − r n )
a (1 − r n+1 )
+ a rn =
1−r
1−r
となり等式は成立している。
(b) 省略
(c) 省略
1 1
1 n
(d) A =
のとき An =
0 1
0 1
解答：n = 1 のときは明らかに成立している。任意の n で成り立っているもの
とすると，n + 1 のときは
1
n
1
1
1
n
+
1
An+1 = An · A =
=
0 1
0 1
0
1
あるいは
An+1 = A · An =
1 1
0 1
1 n
1 n+1
=
0 1
0
1
(e) 省略
n
x sin nx
sin n+1
2
x 2
(f)
sin kx =
sin 2
k=1
解答：n = 1 のときは明らに成り立っている。任意の n で成り立っているもの
と仮定すると，和を積に，積を和に変換する公式を用いて，n + 1 のときは
nx n+1
sin n+1
x
sin
2
x 2 + sin(n + 1)x
sin kx =
sin
2
k=1
n+1 sin 2 x sin n2 x + sin(n + 1) x sin x2
=
sin x2
x
1
cos 2 − cos(n + 12 )x + 12 cos(n + 12 )x − cos(n + 32 )x
2
=
sin x2
cos x2 − cos(n + 32 )x
=
2 sin x2
sin n+2
x sin n+1
x
2
2
=
sin x2
(g) 省略
(h) n = 1 のとき成り立つのは明らかである。任意の n で成り立つとする。ここで，
In = xn dx と置くと，帰納法の仮定より
In =
xn+1
n+1
となる。In+1 は，部分積分を行うことにより
n+1
In+1 = x dx = xn · x dx
n+1
x
xn+1
·x−
dx
=
n+1
n+1
I
xn+2
=
− n+1
n+1 n+1
となる。これを In+1 について解くことによって
In+1 =
xn+2
n+2
となり，すべての n について成り立つ。

Download Report