发布时间 : 星期日 文章《离散数学》习题集更新完毕开始阅读d85c627e53d380eb6294dd88d0d233d4b14e3ff3
R={
是A上的偏序关系，试求盖住关系COV A，画出哈斯图，确定下列集合的上界和下界。 ⑴ B1={2,3,6} ⑵ B2={12,24,36}
29设N为自然数集合，N上的大于等于关系定义为
R≥={
30设P={?,{a},{a,b},{a,b,c}}，P上的包含关系
R?={
验证R?是全序关系。
第49页 共53页
第五章 无限集合
5.1 可数和不可数集合
1. 若A和B都是无限集合，C是有限集合，回答下述问题，对肯定的回答要讲出理由，对
否定的回答要举出反例。 (a) AB是无限集合吗？
(b) A?B是无限集合吗？ (c) AC是无限集合吗？
2. 确定下述集合哪些是有限的，哪些是无限的。若集合是有限的，对它的基数找出表达式。 (a) 在{a,b}*中，质数长度的所有串的集合； (b) 在{a,b,c}*中，长度不大于k的所有串的集合； (c) n个结点的所有关系图集合； (d) 矩阵的项取自{0,1,2,,k}的所有m?n矩阵集合，这里m,n,k是给定的正整数。
(e) 命题变元P,Q,R和S上所有命题公式集合； (f) 从{0,1}到I的所有函数的集合； (g) N。
3. 证明下述集合的每一个是可数无限的。 (a) ?，这里??{a}； (b) {?x1,x2,x3?|xi?I}； (c) {a,b}*的所有有限子集的集合； (d) 所有整系数的一次多项式集合。 (e) 具有自然数结点的所有关系图集合。
4. 构造从[0,1]到下述各集合的一个双射函数以证明它们有基数c。 (a) (a,b)，这里a?b，a,b?R； (b) {x|x?R?x?0}；
第50页 共53页
*?(c) (0,1]
(d) {?x,y?|x,y?R?x2?y2?1}。
5. 设|A|?c，|B|?c，|D|??0，|E|?n?0，这里A,B,D和E是不相交的，证明下
列各式。 (a) |A(b) |AB|?c； D|?c；
(c) |D?E|??0。
6. 证明由0和1构成的序列的集合，其基数是c。
7. 以下是从N到N不存在双射函数的证明。试指出其错误。
假设f从N到N的一个双射函数，f(k)?ik，对每一ik，颠倒ik的数字并放小数点于左边以构成一个在[0,1]中的数。例如若ik?123，则被构成0.32100一个从N到N的单射函数g。例如g(123)?0.32100应用康脱对角线技术于数组
，
。这样，定义了
gf(0)?0.x00x01x02gf(1)?0.x10x11x12
， ，
来构造y?[0,1]。现在把y的数字颠倒，并把小数点放在右边。其结果是一个不出现在表f(0),f(1),f(2),射函数。
中的数，着与断言f是满射函数矛盾。因此，从N到N没有双
5.2 基数的比较
8. 证明如果A??A，那么|A?|?|A|。
9. 证明如果|A|?|B|和|C|?|A|，那么|C|?|B|。
10. 设f:A?B是一单射函数，假设A是无限的，试证明B是无限的。 11. 设A和B是集合，A是无限的，试应用上一题的结果，证明
第51页 共53页
(a) ?(A)是无限的；
(b) 若B??，则A?B是无限的； (c) 若B??，则A是无限的。
12. 证明如果存在一个从A到B的满射函数，那么|B|?|A|。 13. 设?1和?2是A的划分，使?1细分?2，证明|?2|?|?1|。 14. 证明|[0,1]?[0,1]|?c。
15. 找出下述集合的基数，并证明之。 (a)Q（有理数集合）； (b) R?R；
(c) x坐标轴上所有闭区间集合； (d)?(Q)；(e) R?Q。
16. (a) 证明存在一个不可计算的数在任何两个有理数之间，此二有理数在[0,1]中；
(b) 证明所有在[0,1]中的有理数都是可计算的。 17. 证明：如果A是有限集，B是无限集，那么|A|?|B|。 18. 证明可数集合的每一无限子集是可数的。
19. 证明集合A是无限集合的充分必要条件是对于从A到A的每个映射f，有A的非空真
子集B，使f(B)?B。
20. 记|?([0,1])|为2，找出其它集合有基数2的例子。 21. 证明或否定下列各式：
(a) |A|?|B|?|?(A)|?|?(B)|； (b) |A|?|B|?|C|?|D|?|A|?|B|； (c) |A|?|B|?|C|?|D|?|A?C|?|B?D|； (d) |A|?|B|?|C|?|D|?|ACDccBC|?|BD|。
A22. 设A是非空集合，|B|?1，证明|A|?|B|。
第52页 共53页