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

《集合论与图论》课堂练习1 (2007年4月11日13:30-15:10复且大学计算机科学与工程系06级) 学号 姓名 成绩 、填空题(30分,每格2分) 1.设A为一个集合,若A为空集或与集合(012n-1}的基数相同_,则A为 有限集。若_存在从N到A的双射 则称A为 可列集。 2.已知集合A和B,且4n,|B|m,由A到B有 nm 个不同的关 系,有 个不同的函数。若n=5,则A上 个全 序关系。若n=m=3,则从A到B可产生6个不同的双射。 3.集合A的递归(归纳)定义由三部分组成: (1)基础某些元素属于我们正在定义的集合A中说明集合A是非空的 递归(归纳)·使用当前集合A中的现有元素来产牛含在此集合中的更多 即建立产生集合A中新元素的一种方法 3)闭团合:只有在集合A中的元素是通过有限次应用(1和(2)得到的 4.设A、B为集合,则A⌒B=B的充要条件是:Bc4 AGB=B的充要条件是A=② 充分性:若A=⑦,则AB=∞B=B 必要性:若A≠⑦,则存在ⅹ∈A,可分两种情况 1)x∈B,则x∈A∩B,所以x∈A④B,则AB≠B 2)x∈B,则x∈A⊕B,则AGB≠B。 5.函数 f NxN-N,f(x,y=x2+y2。f(0以={(0.0 6.函数fA→B可逆的充要条件是 7.A,B是集合,P4,P(B为其幂集,且AB=,则PA4)⌒P(B)=

1 《集合论与图论》课堂练习 1 （2007 年 4 月 11 日 13:30-15:10 复旦大学计算机科学与工程系 06 级） 学号 姓名 成绩 一、 填空题（30 分，每格 2 分） 1．设 A 为一个集合，若 A 为空集或与集合{0,1,2,…,n-1}的基数相同 ，则 A 为 有限集。若 存在从 N 到 A 的双射 ，则称 A 为 可列集。 2．已知集合 A 和 B，且|A|=n，|B|=m，由 A 到 B 有 2 nm 个不同的关 系，有 mn 个不同的函数。若 n =5, 则 A 上有 5! 个全 序关系。若 n =m=3, 则从 A 到 B 可产生 6 个不同的双射。 3．集合 A 的递归（归纳）定义由三部分组成： （1）_基础: 某些元素属于我们正在定义的集合 A 中,说明集合 A 是非空的 _ _; （2）_递归（归纳）: 使用当前集合 A 中的现有元素来产生含在此集合中的更多 元素, 即建立产生集合 A 中新元素的一种方法 _ ; （3）_闭合: 只有在集合 A 中的元素是通过有限次应用(1)和(2)得到的 _ _。 4．设 A、B 为集合，则 AB=B 的充要条件是： BA ； AB=B 的充要条件是 A= _____。 充分性：若 A=，则 AB=B=B 必要性：若 A，则存在 xA，可分两种情况： 1）xB，则 xAB，所以 xAB，则 ABB； 2）xB，则 xAB，则 ABB。 5．函数 f:NN→N，f((x, y))=x2+y2。f -1 ({0})= {(0, 0)} 。 6. 函数 f: A→ B 可逆的充要条件是 f 为双射 。 7. A, B 是集合， P(A), P(B) 为其幂集，且 AB= ， 则 P(A)P(B) = {}

8.A,B是集合,No=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是双射 (真) /*武汉大学1999年试题* (1)证明h是满射。 对于任意的b,d∈BxD,则beB,dD,因为/是从A到B的双射,g是从C到D 的双射,所以存在a∈A,ceC,使得fa=b,g(c)=d成立;即存在la,c)∈Ax,使 得ha,c)=0u),g(c)=(,d成立。所以h是满射 (2)证明h是内射。 对于任意的a,c)eAxC,a,ey)eAxC,若h(,cm)=ha2,c),所以a g(em)=(,g(2)。所以fa)=f(.,ge=g(e)。因为f是从A到B的双射,g 是从C到D的双射,所以a1=a2,c1=c2。则a,c)=a2,c)。所以h是内射。 所以h是双射。 2.设R是A上的二元关系,则t(s(R)=sR) (假) 定理2.12(3) 3.设A,B是集合,若存在A到B的满射,则B≤ 真) 设存在A到B的满射f,对任意b∈B,存在x∈A,ma)=b 而由函数的定义,=b,fa)=b,若b地b,则a和2。则B≤l4l。 4.设A是集合,R是A的幂集P(4)上的二元关系,对所有的S,T∈P(4),(S,TER。 R是偏序关系当且仅当s。 (假) 对于R是A的幂集P(4上的二元关系来说,S≤1,R是偏序关系既不是充分条 件,也不是必要条件 取A={a,b},S={a},T={b}。因为s并且7sS,所以S,D∈R,并且(T,S)∈R; 因为S,R不是反对称的。所以R不是偏序关系。所以s不是充分条件 令R={(,∞,({a},{a})({b},{b},({a,b},{a,b},({a,b},{a})},R是偏序关系。 因为({a,b},{a})∈R,|S7不成立。所以S≤1不是必要条件 综合题(46分) 1.设有双射fA→B,试构造从P(4到PB的一个双射,并证明之。(15分,给 出双射5分,证明10分) 构造性证明* 解:构造函数g:P4PB),欧eP团4),令g=y,满足:hax,都有fa)ey, 且对于e,都有f(b)ex,即y为仅由x中各元素在∫作用下的象组成的集合 证明:g是从P4到P/B)的一个双射

2 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 是双射。 （ 真 ） /*武汉大学 1999 年试题*/ （1）证明 h 是满射。 对于任意的(b, d)BD, 则 bB, dD, 因为 f 是从 A 到 B 的双射，g 是从 C 到 D 的双射，所以存在 aA, cC, 使得 f(a)= b, g(c)=d 成立；即存在(a, c)AC, 使 得 h((a, c))=(f(a), g(c))= (b, d)成立。所以 h 是满射。 （2）证明 h 是内射。 对于任意的(a1, c1)AC, (a2, c2)AC, 若 h((a1, c1))=h( (a2, c2))，所以(f(a1), g(c1))= (f(a2), g(c2))。所以 f(a1)= f(a2), g(c1)= g(c2)。因为 f 是从 A 到 B 的双射，g 是从 C 到 D 的双射，所以 a1=a2, c1=c2。则(a1, c1)= (a2, c2)。所以 h 是内射。 所以 h 是双射。 2．设 R 是 A 上的二元关系，则 t(s(R))=s(t(R))。 （假） 定理 2.12(3)。 3．设 A, B 是集合，若存在 A 到 B 的满射，则|B||A|。 （ 真 ） 设存在 A 到 B 的满射 f，对任意 bB，存在 xA，f(a)=b。 而由函数的定义，f(a1)=b1，f(a2)=b2，若 b1b2，则 a1a2。则|B||A|。 4．设 A 是集合，R 是 A 的幂集 P(A)上的二元关系，对所有的 S, TP(A)，(S, T)R。 R 是偏序关系当且仅当|S||T|。 （假） 对于 R 是 A 的幂集 P(A)上的二元关系来说，|S||T|，R 是偏序关系既不是充分条 件，也不是必要条件。 取 A={a, b}, S={a}, T={b}。因为|S||T|并且|T||S|，所以(S, T)R，并且(T, S)R； 因为 ST，R 不是反对称的。所以 R 不是偏序关系。所以|S||T|不是充分条件。 令 R={(, ), ({a}, {a}), ({b}, {b}), ({a, b}, {a, b}), ({a, b}, {a})}，R 是偏序关系。 因为({a, b}, {a})R，|S||T|不成立。所以|S||T|不是必要条件。 三、综合题（46 分） 1．设有双射 f: A→B，试构造从 P(A)到 P(B)的一个双射，并证明之。（15 分，给 出双射 5 分，证明 10 分） /**构造性证明**/ 解：构造函数 g: P(A)→P(B)，xP(A)，令 g(x)=y，满足：ax，都有 f(a)y， 且对于by，都有 f -1 (b)x，即 y 为仅由 x 中各元素在 f 作用下的象组成的集合。 证明：g 是从 P(A)到 P(B)的一个双射

(1)g是从P(4到P/B)的一个满射。 h∈P(B,则彐x∈P(A),对于b曰,都有f(b)ax,即x为仅由y中各元素在f 作用下的象组成的集合。这样的x总是存在的。所以g是从P4)到P(B的一个 满射。 (2)g是从P)到P(B的一个内射。 b,x2∈P(4),若g(x=g(x)=y,则hex1,fa=g(x)y,而g(xy)=y,所以fa ∈g(x),由g的定义,aex2,所以xgx2,同理xgx,所以x=x。所以g是从 P(4到PB的一个内射 因此,g是从P4到P(B)的一个双射。 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分) (1)定义双射 f: NXN-N(参考教材68页) (2)[0,1是不可列集(参考教材69页) 3.R是集合A上的等价关系,4=n,|R=。对于A关于R的商集AR,MA/R=r 证明:r22。(16分) *中国科学院计算所2000* 习题解析: R、A和AR三者的基数之间存在什么关系 1)R是集合A上的等价关系→R对A形成的一个划分,这个划分就是商集AR 2)取划分的一个块,若块中元素k个,则该块产生的有序对为k2个

3 （1）g 是从 P(A)到 P(B)的一个满射。 yP(B)，则xP(A) ，对于by，都有 f -1 (b)x，即 x 为仅由 y 中各元素在 f -1 作用下的象组成的集合。这样的 x 总是存在的。所以 g 是从 P(A)到 P(B)的一个 满射。 （2）g 是从 P(A)到 P(B)的一个内射。 x1, x2P(A)，若 g(x1)=g( x2)=y，则ax1，f(a)= g(x1)y，而 g( x2)=y，所以 f(a)  g( x2)，由 g 的定义，ax2，所以 x1x2，同理 x2x1，所以 x1=x2。所以 g 是从 P(A)到 P(B)的一个内射。 因此，g 是从 P(A)到 P(B)的一个双射。 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 分） (1) 定义双射 f: NN→N (参考教材 68 页) (2) [0，1]是不可列集(参考教材 69 页) 3．R 是集合 A 上的等价关系，|A|=n，|R|=s。对于 A 关于 R 的商集 A/R，|A/R|=r。 证明：rsn 2。（16 分） /*中国科学院计算所 2000*/ 习题解析： • R、A 和 A/R 三者的基数之间存在什么关系？ 1）R 是集合 A 上的等价关系 R 对 A 形成的一个划分，这个划分就是商集 A/R。 2）取划分的一个块，若块中元素 k 个，则该块产生的有序对为 k 2 个

3)r个块的有序对相加,和等于s。r个块中所含元素的个数相加,和等于n。 证明思路和过程: 设AR的r个等价类集合的元素个数分别是m1,m2,…,mr。则m+m2+...+mr n, mr+mr +m2=s。因此,问题转换为证明(m2+m2+ m2加2(m+m2+….…+m)∥m2,即证明rmr2+m2+….+m2)2(m+m2+… n)2。(可以用数学归纳法进行证明)。 数学归纳法证明:r(m2+mx2+,…+m2)≥m+m2+.…+my2。 归纳基础: 当r=1时,左式=m2,右式=mr2,左式≥右式,命题成立 归纳步骤: 设当r=k时,命题成立。即,kmr2+m2++mk)(m1+m2+.…+my2。 则当r=k+1时,左式= k+D)mr2+m2+……+mk+12) k(mi+m2 +mk+12) k(m2+m2+….….+m2)+kmk+r2+m2+m2+…..+mk2)+mk+r2 =kmr2+m2+…….+mk)+(mr2+mk+12)+(m2+mk+2)+……,+(m2+m+)+mk+ 右式=(m+m2+….…,+mkx+ =(m1+m2+…+mk)2+2mk+(m1+m2 +mk)+ mk+ =(m1+m2+……+mk)2+2mk+1m1+2mk+1m2+….….+2mk+1mk+mk+12 由归纳假设km2+m2+..…+mk)2(m+m+…+my2,以及基本不等式,左 式≥右式,命题成立。 所以

4 3）r 个块的有序对相加，和等于 s。r 个块中所含元素的个数相加，和等于 n。 证明思路和过程： 设 A/R 的 r 个等价类集合的元素个数分别是 m1, m2, …, mr。则 m1+m2+… … +mr =n ， m1 2+m2 2+… … +mr 2 =s 。 因 此 ， 问 题 转 换 为 证 明 (m1 2+m2 2+… … +mr 2 )/r(( m1+m2+… … +mr)/r)2，即证明 r (m1 2+m2 2+… … +mr 2 ) ( m1+m2+… … +mr) 2。（可以用数学归纳法进行证明）。 数学归纳法证明：r (m1 2+m2 2+… … +mr 2 ) ( m1+m2+… … +mr) 2。 归纳基础： 当 r=1 时，左式= m1 2，右式= m1 2，左式右式，命题成立。 归纳步骤： 设当 r=k 时，命题成立。即，k (m1 2+m2 2+… … +mk 2 ) ( m1+m2+… … +mk) 2。 则当 r=k+1 时，左式= (k+1) (m1 2+m2 2+… … +mk+12 ) =k(m1 2+m2 2+… … +mk+12 )+ (m1 2+m2 2+… … +mk+12 ) =k(m1 2+m2 2+… … +mk 2 )+kmk+12+(m1 2+m2 2+… … +mk 2 ) + mk+12 =k (m1 2+m2 2+… … +mk 2 )+( m1 2+mk+12 )+ ( m2 2+mk+12 )+……+( mk 2+mk+12 )+ mk+12 右式=( m1+m2+… … +mk+1) 2 =( m1+m2+… … +mk) 2+2 mk+1 ( m1+m2+… … +mk)+ mk+12 =( m1+m2+… … +mk) 2+2 mk+1 m1+2 mk+1 m2+… … +2 mk+1 mk+ mk+12 由归纳假设 k (m1 2+m2 2+… … +mk 2 ) ( m1+m2+… … +mk) 2，以及基本不等式，左 式右式，命题成立。 所以 rsn 2