2001年度情報数学

レポートの解答例
(2006年度 後藤担当)
• 以下に解答例を示します。
• なお今回のレポートの問題は過去の定期試験
問題から出題しています。
問1: 2004年度 定期試験 問題1(a)
問2: 2004年度 定期試験 問題2(b)
問3: 2005年度 定期試験 問題 G2 関連
(2004年度 定期試験 問題2 関連あり)
問4: 2004年度 定期試験 問題4
1
問1 集合の要素
• 次の集合に属するすべての要素を列挙せよ。
例: {0,1}{a}   0, a ,  1, a 
[1-1]
2
2{}
(または
P
(P
(f
g )) )
{a, {a}, {a, {a}}}  {a, {a}}
[1-2]
ヒント: [1-2]では+の左と右の集合の要素の数を、まず数えてみる。
これは有限集合である。
2
[1-1] 集合の要素(解答)
• まず空集合の冪集合を求める 2{ }
この冪集合は一つの要素を持つ {{ }} .
次に空集合の冪集合の冪集合を求める 2{{ }}
この集合は二つの要素を持つ {{ }, {{ }} }.
よって解答は、 { }, {{ }}.
• 確認:空集合は有限集合である。
|{ }|=0. | 2{ } |=20=1 が成立つ。
{}
{}
2
同様に、 2 2  2  21  2 となる。
解答が二つの要素から成るのは当然である。
3
[1-2] 集合の要素(解答)
• [1-2]
直和を表現するタグとして {0, 1}を用いる。
<0,a>, <0,{a}>, <0,{a,{a}}>, <1,a>, <1,{a}>
• 確認:左側の { a, {a}, {a,{a}} } という集合が
少し複雑に見えるが、要素の数は 3である。
右側の集合 {a, {a} }の要素の数は 2である。
いずれも有限集合であるから直和の要素の
数は 5となる。
{a, {a}, {a, {a}}}  {a, {a}}  {a, {a}, {a, {a}}}  {a, {a}}
4
問2 関数
• 次の集合に属する要素を具体的に一つ挙げよ。
N{0,1}×{2,3}
ヒント: まず集合 {0, 1}×{2, 3} の要素を具体的に書いてみる。
5
問2 関数(解答)
• まず直積 {0,1}×{2,3}の要素を求める
{0,1}×{2,3}={<0,2>,<0,3>,<1,2>,<1,3>}
N{0,1}×{2,3} という集合は、{0,1}×{2,3} から自然数
の集合 N への関数(写像)の集合のことである。
ここでは関数の値を具体的に定めて関数を一つ
定めればよい。関数の一例のグラフを挙げる。
{<<0,2>,0>, <<0,3>,1>, <<1,2>,2>, <<1,3>,3>}
これが N{0,1}×{2,3}の要素の一つである。
6
問3 集合の濃度(可算集合)
• 自然数の集合 N={0,1,2,…}の直積 N2=N×N
から N への関数 f(x,y)={(x+y)2+3x+y}÷2 を考
える。
(3-1) f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0)
の値を計算せよ。
(3-2) N2は可算集合であることを説明せよ。
7
(3-1) 解答
f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0)の値
f (0,0) 
{( 0  0 ) 2  30  0}
f (0,1) 
{( 0 1) 2  30 1}
f (1,0) 
{(1 0 ) 2  31 0}
2
f (0,2) 
f (1,1) 
2
1
2
2
{( 0  2 ) 2  30  2}
2
{(11) 2  311}
f (2,0) 
0
2
3
4
{( 2  0 ) 2  32  0}
2
5
8
(3-2) 解答
N  N  N は自然数の集合の直積である。
2
N  N の要素<x,y>に自然数 {( x  y)  3x  y} 2
を対応づける関数は全単射である。よって N と
2
N  N  N とは対等で同じ濃度をもつ。
集合 N が可算無限集合であるから N 2 も可算
無限集合である。
2
9
問4 二項関係の反射推移的閉包
• 集合A = {p, q, r, s} 上の二項関係
R = {<p, q>, <q, r>, <r, s>, <r,r>} の
反射推移閉包(すなわち R * )を求めよ.
ヒント
p
s
R0
R1
R2
R3
R4
p
p
q
r
r,s
r,s
q
q
r
r,s
r,s
r,s
r
r
r,s
r,s
r,s
r,s
s
s
q
r
10
問4 二項関係の反射推移的閉包
(解答)
• グラフの上で各点から長さ n の道(経路)で到達で
きる点を求めれば良い。
p
s
q
r
{<p,p>, <q,q>, <r,r>, <s,s>, <p,q>, <q,r>, <r,s>, <p,r>, <q,s>, <p,s>}
11
問4 反射推移的閉包 (別解)
• 解答: R = {<p, q>, <q, r>, <r, s>, <r,r>}
の隣接行列を考える。
1

0
0
R 
0

0

0

0
2
R 
0

0

0 0 0
0


1 0 0
0
,R

0 1 0
0


0
0 0 1 

0 1 0
0


0 1 1 3 0
,R 

0 1 1
0


0
0 0 0 

1 0 0

0 1 0
,

0 1 1

0 0 0 
0 1 1
0 0


0 1 1 4 0 0
R 

0 1 1
0 0


0 0
0 0 0 

p
s
q
r
1 1

1 1
,

1 1

0 0 
(R0+R1+R2+R3+R4+‥)の0でない成分 =
{<p,p>, <q,q>, <r,r>, <s,s>, <p,q>, <q,r>, <r,s>, <p,r>, <q,s>, <p,s>} 12