レポートの解答例 (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 30 0} f (0,1) {( 0 1) 2 30 1} f (1,0) {(1 0 ) 2 31 0} 2 f (0,2) f (1,1) 2 1 2 2 {( 0 2 ) 2 30 2} 2 {(11) 2 311} f (2,0) 0 2 3 4 {( 2 0 ) 2 32 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
© Copyright 2024 ExpyDoc