《离散数学 Discrete Mathematics》课程教学资源（习题集）《集合论与图论》课堂练习1-（2006级）

《集合论与图论》课堂练习1 (2007年4月11日13:30-15:10复且大学计算机科学与工程系06级) 学号 姓名 成绩 、填空题(30分,每格2分) 1.设A为一个集合,若 A为有限集。 则称A为可列集。 2.已知集合A和B,且F=n,|B=m,由A到B有 个不同的 关系,有 个不同的函数。若n=5,则A上有 全序关系。若n=m=3,则从A到B可产生 个不同的双射 3.集合A的递归(归纳)定义由三部分组成: (1) (2) (3) 4.设A、B为集合,则A⌒B=B的充要条件是: A⊕B=B的充要条件是_ 5.函数fNxN→刈N,的(x,y=x2+y2。f(0以= 6.函数fA→B可逆的充要条件是 7.A,B是集合,P4,PB为其幂集,且AB=,则P4)P(B 8.A,B是集合,N0=B=N,则4-B= 二、是非判断题(24分,每题6分,其中判断3分,论述3分) 1.设A,B,C,D是任意集合;∫是从A到B的双射,g是从C到D的双射。h AxC→BD,其中对于任意的a,c∈AxC,ha,c)=(u),gc)成立。则h是双射

1 《集合论与图论》课堂练习 1 （2007 年 4 月 11 日 13:30-15:10 复旦大学计算机科学与工程系 06 级） 学号 姓名 成绩 一、 填空题（30 分，每格 2 分） 1．设 A 为一个集合，若 A 为有限集。 若 ，则称 A 为可列集。 2．已知集合 A 和 B，且|A|=n，|B|=m，由 A 到 B 有 个不同的 关系，有 个不同的函数。若n =5, 则A上有 个 全序关系。若 n =m=3, 则从 A 到 B 可产生 个不同的双射。 3．集合 A 的递归（归纳）定义由三部分组成： （1）_ _ _; （2）_ _ ; （3）_ _ _。 4．设 A、B 为集合，则 AB=B 的充要条件是： ； AB=B 的充要条件是 _____。 5．函数 f:NN→N，f((x, y))=x2+y2。f -1 ({0})= 。 6. 函数 f: A→ B 可逆的充要条件是 。 7. A, B 是集合， P(A), P(B) 为 其 幂集，且 AB= ， 则 P(A)P(B) = 。 8. A, B 是集合，0=|B|<|A|=，则|A-B|= 。 二、是非判断题（24 分，每题 6 分，其中判断 3 分，论述 3 分） 1．设 A, B, C, D 是任意集合；f 是从 A 到 B 的双射，g 是从 C 到 D 的双射。h: AC→BD，其中对于任意的(a, c)AC, h((a, c))=(f(a), g(c))成立。则 h 是双射

2.设R是A上的二元关系,则t(s(R)=s(t(R) 3.设A,B是集合,若存在A到B的满射,则Bl

2 （ ） 2．设 R 是 A 上的二元关系，则 t(s(R))=s(t(R))。 （ ） 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ ）

4.设A是集合,R是A的幂集P(4上的二元关系,对所有的S,T∈P4),③S,T∈R。 R是偏序关系当且仅当s。 () 综合题(46分) 1.设有双射fA→B,试构造从P闭A4)到P(B的一个双射,并证明之。(15分,给 出双射5分,证明10分)

3 4．设 A 是集合，R 是 A 的幂集 P(A)上的二元关系，对所有的 S, TP(A)，(S, T)R。 R 是偏序关系当且仅当|S||T|。 （） 三、综合题（46 分） 1．设有双射 f: A→B，试构造从 P(A)到 P(B)的一个双射，并证明之。（15 分，给 出双射 5 分，证明 10 分）

2.某一个市镇只有一家旅馆,这个旅馆与通常旅馆没有不同,只是房间数不是 有限而是无穷多间,房间号码为1,2,3,4,……我们不妨管它叫希尔伯特旅 馆。这个旅馆的房间可排成一列的无穷集合(1,2,3,4,…),称为可列集。 有一天,所有房间都住满了。后来来了一位客人,坚持要住房间。旅馆老 板于是引用“旅馆公理”说:“满了就是满了,非常对不起!”。正好这时候,恥 明的旅馆老板的女儿来了,她看见客人和她爸爸都很着急,就说:“这好办,请 每位顾客都搬一下,从这间房搬到下一间”。于是1号房间的客人搬到2号房间 2号房间的客人搬到3号房间…依此类推。最后1号房间空出来,请这位迟到 的客人住下了。 第二天,希尔伯特旅馆又来了一个庞大的代表团要求住旅馆,他们声称有 可数无穷多位代表一定要住,这又把旅馆经理难住了。老板的女儿再一次来解围, 她说:“您让1号房间客人搬到2号,2号房间客人搬到4号……,k号房间客人 搬到2k号,这样,1号,3号,5号,……房间就都空出来了,代表团的代表都 能住下了。” 第三天,这个代表团每位代表又出新花招,他们想每个人占可数无穷多间 房来安排他们的亲戚朋友,这回不仅把老板难住了,连老板的女儿也被难住了。 (1)现在您担任希尔伯特旅馆的客房经理,您准备采取什么方法解决当前的住宿 问题? (2)后来老板的女儿进了大学数学系。有一天,康托尔教授来上课,他问老板的 女儿:“要是区间[0,1上每一点都占一个房间,是不是还能安排?”也请您 回答康托尔教授的这一问题,并论证。 (15分,第1小题6分,第2小题9分,其中论证为6分)

4 2．某一个市镇只有一家旅馆，这个旅馆与通常旅馆没有不同，只是房间数不是 有限而是无穷多间，房间号码为 1，2，3，4，……我们不妨管它叫希尔伯特旅 馆。这个旅馆的房间可排成一列的无穷集合(1，2，3，4，…)，称为可列集。 有一天，所有房间都住满了。后来来了一位客人，坚持要住房间。旅馆老 板于是引用“旅馆公理”说：“满了就是满了，非常对不起！”。正好这时候，聪 明的旅馆老板的女儿来了，她看见客人和她爸爸都很着急，就说：“这好办，请 每位顾客都搬一下，从这间房搬到下一间”。于是 1 号房间的客人搬到 2 号房间， 2 号房间的客人搬到 3 号房间……依此类推。最后 1 号房间空出来，请这位迟到 的客人住下了。 第二天，希尔伯特旅馆又来了一个庞大的代表团要求住旅馆，他们声称有 可数无穷多位代表一定要住，这又把旅馆经理难住了。老板的女儿再一次来解围， 她说：“您让 1 号房间客人搬到 2 号，2 号房间客人搬到 4 号……，k 号房间客人 搬到 2k 号，这样，1 号，3 号，5 号，……房间就都空出来了，代表团的代表都 能住下了。” 第三天，这个代表团每位代表又出新花招，他们想每个人占可数无穷多间 房来安排他们的亲戚朋友，这回不仅把老板难住了，连老板的女儿也被难住了。 (1) 现在您担任希尔伯特旅馆的客房经理，您准备采取什么方法解决当前的住宿 问题？ (2) 后来老板的女儿进了大学数学系。有一天，康托尔教授来上课，他问老板的 女儿：“要是区间[0，1]上每一点都占一个房间，是不是还能安排？”也请您 回答康托尔教授的这一问题，并论证。 （15 分，第 1 小题 6 分，第 2 小题 9 分，其中论证为 6 分）

3.R是集合A上的等价关系,4|=n,|R=s。对于A关于R的商集AR,MA/R=r。 证明:rsn。(16分)

5 3．R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。 证明：rsn 2。（16 分）