《离散数学》习题集 下载本文

R={ | a?A∧b?A∧a能整除b}

是A上的偏序关系,试求盖住关系COV A,画出哈斯图,确定下列集合的上界和下界。 ⑴ B1={2,3,6} ⑵ B2={12,24,36}

29设N为自然数集合,N上的大于等于关系定义为

R≥={ | x?N∧y?N∧x≥y } 证明R≥是全序关系。

30设P={?,{a},{a,b},{a,b,c}},P上的包含关系

R?={ | x?P∧y?P∧x?y}

验证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页