《离散数学》习题集
目 录
第一章 数理逻辑 .................................................................. 2 第二章 集合 ....................................................................... 14 第三章 第三章 第五章 二元关系 ................................................................ 22 二元关系 ................................................................ 36 无限集合 ................................................................ 50
第1页 共53页
第一章 数理逻辑
1.1 命题
1. 设P是命题“天下雪”；Q是命题“我去镇上”；R是命题“我有时间”。 (a) 用逻辑符号写出以下命题：
(i) 如天不下雨和我有时间，那么我去镇上； (ii) 我去镇上，仅当我有时间； (iii) 天不下雪；
(iv) 天正在下雪，我也没去镇上。 (b) 对下述命题用中文写出语句： (i) Q?(R??P)； (ii) R?Q；
(iii) (Q?R)?(R?Q)； (iv) ?(R?Q)。 2. 否定下列命题： (a) 上海处处清洁； (b) 每一个自然数都是偶数。
3. 说出下述每一命题的逆命题和逆反命题： (a) 如果天下雨，我将不去； (b) 仅当你去我将逗留；
(c) 如果n是大于2的正整数，则方程xn?yn?zn无正整数解（费尔马最后定理）； (d) 如果我不获得更多帮助，我不能完成这个任务。
4. 给P和Q指派真值T，给R和S真值F，求下列命题的真值： (a) P?Q?R??((P?Q)?(R?S))； (b) ?(P?Q)??R?((Q??P)?R??S)； (c) P?(Q?R??P)?Q??s。 5. 构成下列公式的真值表： (a) Q?(P?Q)?P；
第2页 共53页
(b) (P?Q?Q?R)?P??R。
6. 证明下列公式的真值与它们的变元值无关： (a) P?(P?Q)?Q；
(b) (P?Q)?(Q?R)?(P?R)。
7. 对P和Q的所有值，证明P?Q与?P?Q有同样的真值。证明(P?Q)?(?P?Q)总是
真的。
8. 设?是具有两个运算对象的逻辑运算符，如果(x?y)?z与x?(y?z)逻辑等价，那么运算
符?是可以结合的，
(a) 确定逻辑运算符?、?、?、?哪些是可结合的； (b) 用真值表证明你的断言。
9. 指出一下各式哪些不是命题公式，如果是命题公式，请说明理由：
((?P)?(P?Q))?R)； (a) ((Q?(P?Q))?P)。 (b) (
1.2 重言式
10．指出下列那些命题是重言式、偶然式和矛盾式： (a) P??P； (b) P??P； (c) P??(?P)；
(d) ?（P?Q)?(?Q??P)；
（P?Q)?(?P??Q)； (e)
(f) （P?Q)?(Q?P)； (g) P?(Q?R)?(P?Q?P?R)；
（P?Q?P)?(P?Q)； (h)
(i) (（P?Q)?(R?S))?((P?R)?(Q?S))。
11. 对下述每一表达式，找出仅用?和?的等价表达式，并尽可能简单： (a) P?Q??R； (b) P?(?Q?R?P)； (c) P?(Q?P)。
第3页 共53页
对下述每一表达式，找出仅用?和?的等价表达式，并尽可能简单： (a) P?Q??P；
(b) (P?(Q??R))??P?Q； (c) ?P??Q?(?R?P)。
12. 用化简联结词?的左边成右边的方法，证明以下是重言式：
(P?Q)?P)?T； (a) ((b) (Q?P)?（?P?Q)?(Q?Q)?P。 13. 证明下列等价关系：
(a) P?（Q?P)??P?(P??Q)； (b) (P?Q)?(R?Q)?(P?R?Q)；
(c) ?（P?Q)?(P?Q)??(P?Q)?(P??Q)?(?P?Q)； (d) ?（P?Q)?P??Q。 14. 求出下列公式的最简等价式：
(P?Q)?(?Q??P))?R； (a) ((b) P??P?(Q??Q)；
(c) （P?（Q?S))?(?P?(Q?S))。 15. 证明下列蕴含式： (a) P?Q?(P?Q)； (b) P?(Q?P)；
(c) （P?（Q?R))?(P?Q)?(P?R)；
（P?Q)?Q?P?Q； (d)
（(P??P)?Q)?（(P??P)?R)?(Q?R)。 (e)
16. (a) 与非运算符（又叫悉菲（Sheffer）记号）用下述真值表定义，可以看出
P?Q??（P?Q)，试证明
（i）P?P??P；
（ii）；(P?P)?(Q?Q)?P?Q； （iii）（P?Q）?(P?Q)?P?Q。
第4页 共53页
(b) 或非运算符（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与?（P?Q)逻辑等价。对下述每一式，找出仅用?表示的等价式。 （i）?P； （ii）P?Q； （iii）P?Q。
0 0 0 1 1 0 1 1 P Q P?Q 1 1 1 0 P Q 0 0 0 1 1 0 1 1 P?Q 1 0 0 0 17. (a) 用真值表证明?和?互相可分配；
(b) ?、?和?对自己可分配吗？ 18. 求出下列各式的代入实例：
(a) (((P?Q)?P)?P)：用P?Q代P，用((P?Q)?R)代Q； (b) ((P?Q)?(Q?P))；用Q代P，用P??P代Q。
1.3 范式
19. 对任一指派，i?j时，为什么mi和mj不能同时为真？为什么Mi和Mj不能同时为假？ 20. 求下列各式的主合取范式：
(a) P?Q?R??P?Q?R??P??Q??R； (b) P?Q??P?Q?P??Q； (c) P?Q??P?Q?R。
21. 求下列各式的主析取范式和主合取范式： (a) ； （?P??Q）?（P??Q）(b) P?(?P?(Q?(?Q?R)))； (c) （P?Q?R)?(?P?(?Q??R))； (d) P??Q?S??P?Q?R。
1.4 联结词的扩充与归约
第5页 共53页
22. 仅用?表达P?Q；再用?表达它。 23. 仅用?表达P?Q；仅用?表达P?Q。
24. 试证明等价式：?(P?Q)??P??Q和?(P?Q)??P??Q。 25. 写出一个仅含?且等价于P?(Q?R)的公式来。 26. 证明{?},{?},{?,?}都不是全功能联结词集合。 27. 证明{?,?}，{?,T}是全功能联结词集合。 28. 证明联结词?可交换，可结合，且?在?上可分配。 29. 证明联结词?可交换，可结合，且?在?上可分配。
1.5 推理规则和证明方法
30. 用真值表证明下列推理规则的重言式形式都是重言式： (a) 拒取式； (b) 析取三段论； (c)构造性二难定理； (d) 破坏性二难推理。 31. H1,H2,是前提，C是结论，用真值表判断下列结论是否有效：
(a) H1:P?Q，H2:?Q，C:P；
(b) H1:P?Q，H2:P?R，H3:Q?R，C:R； (c) H1:P?(Q?R)，H2:P?Q，C:R； (d) H1:?P，H2:P?Q，C:P?Q。 32. 给出一个指派，证明以下结论是非有效的：
(a) 前提是A?B,B?(C?D),C?(A?E),A?E，结论是A?E。 (b) 前提是A?(B?C),B?(?A??C),C?(A??B),B，结论是A?C。 33. 对下列每一个前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。 (a) 如果我跑，我喘气。我没有喘气。
(b) 天气是晴朗或阴暗，天气晴朗使我愉快而天气阴暗使我烦恼。
(c) 如果考试及格了，那么我很高兴。如果我很高兴，那么我的饭量增加。我的饭量减少。
第6页 共53页
34. 对下述每一论证构造一个证明，给出所有必须增加的断言，指出用于每一步的推理规则。 (a) 从语句“今天下雨或明天后天都下雨”和“明天不下雨或后天不下雨而今天下雨”
可推出“今天下雨”。
(b) 如果李敏来通信工程学院，若王军不生病，则王军一定去看望李敏。如果李敏出差
到南京，那么李敏一定来通信工程学院。王军没有生病。所以，如果李敏出差到南京，王军一定去看望李敏。
35. 确定下列论证哪些是有效的论证，为有效论证构造证明，对非有效论证，表明为什么结
论不能从前提得出。
A?BA?BA?B
A?CA?CA?C(a) ； (b) ； (c) 。
?C?B?C?B?C?B
36. 仅用E4,E5,E8,E18,E21,I2证明?P?(P?Q)?Q。 37. 证明下列论证的有效性：
(a) (A?B)?(A?C)，?(B?C)，D?A推得D； (b) P?Q?R，?R?S，?S推得?P??Q； (c) (P?Q)?R，R?S，Q?T推得R。 38. 证明下列结论“
(a) ?P?Q，?Q?R，R?S ?P?S； (b) P?Q?R?P?Q?R； (c) P?Q?P?P?Q；
(d) P?Q?R，Q?(R?S)， ?P?(Q?S)。 39. 试说明“从假的前提出发，能证明任何命题”。 40. 证明下列各式的有效性：
(a) R??Q，R?S，S??Q，P?Q推得?P； (b) S??Q，S?R，?R，?R?Q推得?P；
(c) ?(P?Q)?(?R?S)，((Q?P)??R)，R推得P?Q。
1.6 谓词和量词
第7页 共53页
41. 下列表达式哪些是命题？ (a) ?x(P(x)?Q(x))?R； (b) ?x(P(x)?Q(x))?S(x)。
42. 设谓词S(x,y,z)表示“x?y?z”，谓词M(x,y,z)表示“xy?z”，论述域是整数，用以
上谓词表示下述断言：
(a) 对每一x和y，有一z，使x?y?z； (b) 对每一x和y，有一z，使x?z?y； (c) 从任何整数减去0，其结果是原整数； (d) 对所有x，对所有y，xy?y。
43. 论述域是整数，对下列每一个断言找出谓词P使蕴含式是假。 (a) ?x?!yP(x,y)??!y?xP(x,y)； (b) ?!y?xP(x,y)??x?!yP(x,y)。
44. 指定一个论述域使下列命题是真。要使指定得论述域是尽可能大的整数的一个子集。 (a) ?x(x?0)； (b) ?x(x＝5)； (c) ?y?x(x?y＝3)； (d) ?y?x(x?y?0)。
(,)45. 设论述域是自然数，P(x,y,z)表示“x＋y?z”，Lxy表示“x?y”，用逻辑符表示下
列断言：
(a) 对每一x和y，有一z，使x＋y?z； (b) (b) 没有x小于0；(c) 4加3得7。 46. 将苏格拉底论证符号化。
47. 设P(x,y,z)表示xy?z，E(x,y)表示x＝y，G(x,y)表示x?y，论述域是整数，将下列
断言译成逻辑符。（提示：要注意数学上习惯写法和逻辑符表示的差异，例如加法交换律在数学中写成：x＋y?y?x，翻译成逻辑符时，要按照实际意义翻译成：
?x?y(x?y?y?x)），即要自动加上全称量词，使整个式子成为命题。）
(a) 如果xy?0，那么x＝0，或y＝0； (b) 如果xy?0，那么x?0，并且y?0； (c) x?z是x?y并且y?z的必要条件；
第8页 共53页
(d) x＝y和x?y不能同时出现；
(e) 存在一x，对每一y和z，使xy?xz。
48. 将下列断言译为逻辑符号，选用的谓词应使逻辑符号中至少含有一个量词： (a) 有一个且仅有一个偶数是质数； (b) 没有一个奇数是偶数；
(c) 某些卡车慢于所有火车，但是至少有一辆火车，快于每一卡车； (d) 所有步行的，骑马的或乘车的人，凡是口渴的都喝泉水。
49. 设E(x)表示“x是偶数”，O(x)表示“x是奇数”，P(x)表示“x是质数”，N(x)表示“x是负数”，I(x)表示“x是整数”和一些中缀表示的谓词诸如y?x2?1等，将下列各句翻译成逻辑符。
(a) 一个整数是奇数，如果它的平方是奇数； (b) 有两个奇数它们的和是偶数； (c) 不存在一个整数x使x2?1是负数； (d) 任何两个质数之和是质数；
(e) 对任何整数，如果它的平方是负的，那么1＝1。 50. 如果论述域是{a,b,c}，试消去下列公式中的量词： (a) ?xR(x)??xS(x)； (b) ?x(P(x)?Q(x))。 51. 试说明下列公式是合式公式： (a) (?x(F(x)?Q(x))； (b) (F(x,y)?(?xG(x,y)))。
1.7 谓词演算的永真公式
52. 证明永真公式Q14,Q15,Q16,Q17,Q19。
53. 下列断言如果是真的证明它们，如果是假的，找出P和Q的解释以证明公式是假。 (a) ?x(P(x)?Q(x))?(?xP(x)??xQ(x))； (b) (?xP(x)??xQ(x))??x(P(x)?Q(x))； (c) (?x(P(x)??xQ(x))??x(P(x)?Q(x))； (d) ?x(P(x)?Q(x))?(?xP(x)??xQ(x))。
第9页 共53页
54. 设论述域是{a0,a1,a2,,an}，试证明下列关系式：
(a) ?xA(x)?P??x(A(x)?P)； (b) ?x(A(x)?B(x))??xA(x)??xB(x)。
55. 对一个仅含元素0和1的论述域，试证明：?x(P(x)?Q(x))?(?xP(x)??xQ(x))，并
证明蕴含式之逆不是有效的。
1.8 谓词演算的推理规则
56. 对下列每一前提集合，列出能得到的恰当结论和应用于这一情况的推理规则。 (a) 所有三角形函数都是周期函数，而所有周期函数都是连续函数； (b) 所有偶数都被2除尽。整数4是偶数，但3不是；
(c) 对汽车工业的好事就是对国家的好事，对国家的好事就是对你的好事。你去买一辆
高价卡车是对汽车工业的好事。
57. 下列推导步骤为什么是错误的？ (a) (i) ?xP(x)?Q(x) P (ii) P(x)?Q(x) T，1，US (b) (i) ?x（P(x)?Q(x)) P
(ii) ?P(a)?Q(b) T，1，US (c) (i) ?xP(x)??x(Q(x)?R(x)) P
(ii) P(a)??x(Q(x)?R(x) T，1，US ）58. 证明下列各断言：
(a) ?(?xP(x)?Q(a))推得?xP(x)??Q(a))； (b) ?x(P(x)?Q(x)),?x?P(x)，推得?xQ(x)。 59. 考虑蕴含式?x(P(x)?Q(x))??xP(x)??xQ(x) (a) 证明它不是有效的。
(b) 下面是一个论证，企图证明上式有效，试找出不正确的地方。
?x(P(x)?Q(x))???x?(P(x)?Q(x))???x(?P(x)??Q(x))??(?x?P(x)??x?Q(x))???x?P(x)???x?Q(x)??xP(x)??xQ(x)
60. 判断下列结论C能否有效的从给定的前提得出： (a) ?x(P(x)?Q(x)),?yP(y) C:?zQ(z)；
第10页 共53页
(b) ?xP(x),?xQ(x) C:?x(P(x)?Q(x))。
补充习题：
1判断以下语句是否为命题。若是命题，确定其真值。
⑴上海是个小村庄。 ⑵存在外星人。 ⑶禁止吸烟！ ⑷北京是中国的首都。
⑸4是素数或6是素数。⑹今天你吃了吗？ ⑺11+1=100 ⑻我正在说谎。 2将下列命题符号化：
⑴2008年将在北京举办奥运会并且中国是世界四大文明古国之一。 ⑵如果小王努力学习，那么他的学习成绩就优秀。 ⑶张华是三好学生当且仅当德、智、体全优秀。 ⑷他或者骑自行车去学校，或者乘公共汽车去学校。 3构造命题公式?p∨q，(p∧q)∨(?p∧?q)的真值表。
4根据等价的定义，用真值表证明p→(q→p)??p→(p→?q)。 5用真值表证明德摩根律 ?(A∨B)??A∧?B。 6用等价演算法证明p?q ?(p∧q)∨(?p∧?q)。 7用等价演算法判断下列公式的类型。
⑴ q∨? ((?p∨q)∧p) ⑵ (p∨?p)→((q∨?q)∧r) ⑶ (p→q)∧?p
8利用代入规则证明((p∨q)∧r)∨?((p∨q)∧r)为重言式。 9求命题公式(p∨q)?p的合取范式和析取范式。 10用真值表法，求(p→q)→r的主析取范式。
11用等价演算法求(p∧q)∨(?p∧r)∨(q∧r)的主析取范式。
第11页 共53页
12用真值表法求(p→q)→r的主合取范式。 13用等价演算法求(p→q)→r的主合取范式。
14证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。 15推证?p∧(p∨q)?q。
16分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。
17用直接推理法证明(p→q)∧(q→r)∧p ?r。 18用CP规则证明：p→(q→r)，?t∨p，q ?t→r。
19用间接法（反证法）证明：(p∧q)→r，?r∨s，?s，p ??q。 20将下列命题符号化，并讨论它们的真值。
⑴ 2与3都是偶数。
⑵ 如果5大于3，则2大于6。 21个体域是人类集合，对下列命题符号化。
⑴ 凡人要死。 ⑵ 有的人是研究生。
22对下列命题符号化，并在①，②，③三个个体域中考察命题的真值。
命题：⑴ 所有数小于5。
⑵ 至少有一个数小于5。 个体域：
① {-1，0，1，2，4} ② {3，-2，7，8} ③ {15，20，24}
23对下列命题在①，②两个个体域中符号化。
命题：⑴ 所有老虎是要吃人。
⑵ 存在一个老虎要吃人。 个体域：
① 所有老虎组成的集合。 ② 全总个体域。
24用谓词公式表达下列自然语言中的命题：
第12页 共53页
⑴并非每个实数都是有理数。 ⑵没有不犯错误的人。
⑶并不是所有的兔子都比所有的乌龟跑得快。 25说明下列各式量词的辖域，找出约束变元和自由变元。
⑴ (?x)P(x)→Q(y) ⑵ (?x) (P(x)∧(?y)Q(x,y)) ⑶ (?x) P(x)∧(?y)Q(x,y)
⑷ (?x)(?y)(P(x,y)∧Q(y,z))? (?x) R(x,y) ⑸ (?x) P(x)∨R(x,y)
26对(?x)(?y)(P(x,y)∧Q(y,z))?(?x) R(x,y)中的约束变元y换名。 27对(?x)(P(y)∧R(x,y))→(?y)Q(y) 中的自由变元y进行代入。 28证明：
⑴(?x)(A(x)→B)?(?x)A(x)→B
⑵(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x) ⑶(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) 29求公式(?x)F(x)→(?x)G(x) 的前束范式。
30将((?x)F(x)∨(?x)G(x))→(?x)(F(x)∨G(x))化为与其等价的前束合取范式。 31证明：苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。 32证明：(?x)(H(x)→M(x))，(?x)H(x)?(?x)M(x)。 33证明：(?x)(A(x)∨B(x))，(?x)?A(x)?(?x)B(x)。
34用CP规则证明：(?x)(F(x)∨G(x))?(?x)F(x)∨(?x)G(x)。
35设个体域为全总个体域。证明推理：学术会的成员都是工人并且是专家。有些成员是青年人。所以有的成员是青年专家。
第13页 共53页
第二章 集合
2.1 集合论的基本概念
1. 用列举法表示下列集合： (a) 小于20的质数集合； (b) 构成evening的字母集合； (c) {x|x2?x?6?0}。 2. 列出下列集合的成员： (a) {x|x是36的因子}； (b) {x|x?a?x?b}。
3. 证明：若a,b,c,d是任意客体，则{{a},{a,b}}?{{c},{c,d}}当且仅当a?c和b?d。 4. 列举下列集合的全部子集： (a) {?}； (b) {?,{?}}； (c) {{?,a},{a}}；
(d) {{a,b},{a,a,b},{b,a,b}}。
5. 设A,B,C是集合，证明或否定以下断言： (a) [A?B?B?C]?A?C； (b) [A?B?B?C]?A?C； (c) [A?B?B?C]?A?C。 6. 确定下列各命题的真和假： (a) ???； (b) ???；
(c) {a,b}?{a,b,c,{a,b,c}}； (d) {a,b}?{a,b,{{a,b}}}。
2.2 集合上的运算
7. 给定自然数集合N的下列子集：
第14页 共53页
A?{1,2,7,8}B?{i|i2?50}C?{i|i可被30整除}D?{i|i?2k?k?I?0?k?6}
求出下列集合 (a) A(B(C(b) A(B(CD))； D))；
(c) B?(AC)。
8. 设x和y是实数，定义运算xy是x（x的y次幂） (a) 证明运算既非可交换的也非可结合的。
(b) 设?代表乘法运算，确定下列分配律哪些是成立的：
(i) x?(yz)?(x?y)(x?z)；
（y?z)x?(yx)?(zx)。 (ii)
y9. 设A,B,C是任意集合，把ABC表示成不相交集合之并。
10. (a) 证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，
使A?B?B?A；
(b) A?B?B?A可能吗？刻画此式出现的全部条件； (c) “相对补”是一个可结合的运算吗？证明你的断言。 11. 设A,B,C是论述域U的任意子集，证明下列各式： (a) A(B?A)??；
(b) A?(BC)?(A?B)(A?C)； (c) A?(BC)?(A?B)(A?C)。
12. 证明A?B，AB，AB??三者是等价的。 13. 在下列命题中找出
S?CS和
S?CS：
(a) C?{?}； (b) C?{?,{?}}； (c) C?{{i}|i?I}。
14. 设C是一非空的某论述域U的子集的搜集，B是U的子集，证明下列分配律的推广：
___(a)
S?CS＝S?CS；
第15页 共53页
___(b)
S?CS?S?CS。
15. 指出下列集合的幂集合： (a) {a,b,c}；(b) {{a,b},{c}}。 16. 证明下列各式： (a) A?A?B?B； (b) (A?B)?B?AB； (c) C(A?B)?(C
A)?(CB)。
2.1 归纳法和自然数
17. 对下列集合给出归纳定义：
(a) 十进制无符号整数集合，定义集合将包含6，235，0045等等；
(b) 十进制的以小数部分为结束的实数集合，定义的集合包含5.3，453.，01.2700，0.480； (c) 二进制形式的不以0开头的正偶数和0组成的集合，定义的集合包含0,110,1010等； (d) 把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串。例如
[],[[]],[][],[[[]][]]等都是成形括号串（例中用[]代（）是为了明晰），试定义成形括号串集合。
18. 用{a}代替N的定义中的?，但仍用这一定义，可否生成自然数集合？有何不同？ 19. 证明成形括号串的左右括号个数相等。
20. 我们有3分和5分两种不同票值的邮票，试证明用这两种邮票就足以组成8分或者更多
的任意邮资。
21. 用归纳法证明：对一切n?I?，(1?2?22. 对所有n?N，证明下列每一关系式： (a) ?i2?n(n?1)(2n?1)/6；
i?0nn?n)2?13?23??n3。
(b) ?(2i?1)?(n?1)2；
i?0n(c) ?i(i!)?(n?1)!?1；
i?0第16页 共53页
n(n?1)??n2?i(d) ?ir??n?2n?1i?0?nr?(n?1)r?r?(r?1)2?r?1；
r?1(e) 1?2n?3n。
23. 如果每根直线连接多边形的两个点，且位于多边形上，那么这个多边形叫凸的，证明对
一切n?3，n边的凸多边形内角之和等于(n?2)180。（提示：多边形能用连结两个非邻接的顶角划分为两部分。）
24. 找出自然域上的两个谓词P和Q一证明归纳证明的基础步骤和归纳步骤是独立的，也
就是没有一个逻辑地蕴含另一个。特别，要找出一谓词P使P(0)是真而
?n(P(n)?P(n?1))是假，和一谓词Q，使Q(0)是假，而?n(Q(n)?Q(n?1))是真。
25. 我们意欲证明，对一切n和一切S，如果S是n个人的集合，那么在S中的所有人都有
同样的身材。下面“所有人都有同样的身材”的证明错在那里？
(a) （基础）设S是一空集合，那么对所有的x和y，如果x?S和y?S，那么x和y有
同样的身材。
(b) （归纳）假定对所有包含n个人的集合断言是真。我们证明对包含n?1个人的集合也
真。任何由n?1个人组成的集合包含两个n个人组成的不同的但交搭的子集合。用
S?和S??表示这两个子集合。那么根据归纳前提，在S?中的所有人有相同的身材，
在S??中的所有人有相同的身材，因为S?和S??是交搭的，所以，所有在S?S??S??中的人都有相同的身材。
26. 设{A1,A2,nn,An}是集合的非空搜集，对n作归纳证明下述推广的德摩根定律：
(a)
i?1nAi?i?1nAi； Ai。
i?1(b)
i?1Ai?27. 证明对所有大于1的整数n都能写成若干个质数之积。
28. 如果a?(b?c)?(a?b)?c，那么二元运算?称为可结合的。从它可推出更强的结果，即
在任何仅含运算?的表达式中，括号的位置不影响结果，就是，仅仅出现于表达式中的运算对象和次序是重要的。为了证明这个“推广的结合律”，我们定义“?表达式集合”如下：
(a) （基础）单个运算对象a1是?表达式；
(b) （归纳）设e1和e2是?表达式，那么(e1,e2)是?表达式；
第17页 共53页
(c) （极小性）只有有限次应用（a）和（b）构成的式子才是?表达式。 设e是一个表达式，它有a1,a2,,an个运算对象，且此次序出现于表达式中，那么
e?(a1?(a2?(a3?((an?1?an)))))
证明这个推广的结合律。（提示：用数学归纳法第二原理。）
2.5 集合的笛卡儿乘积
29. 如果A?{a,b}和B?{c}，试确定下列集合： (a) A?{0,1}?B； (b) B2?A； (c) (A?B)2。
30. 设A?{0,1}，构成集合?(A)?A。 31. 设A,B,C和D是任意集合，试证明：
(AB)?(CD)?(A?C)(B?D)。
32. 试证明：A?B?B?A?A???B???A?B。 33. 指出下列各式是否成立：
(a) (AB)?(CD)?(A?C)(B?D)； (b) (A?B)?(C?D)?(A?C)?(B?D) (c) (A?B)?(C?D)?(A?C)?(B?D)； (d) (A?B)?C?(A?C)?(B?C)； (e) (A?B)?C?(A?C)?(B?C)。
补充习题：
1令A?{1,2}，B?{1,2,O}，C?{2,2,1}，D?{2,O,O,1}，E?{x|x?3x?2?0}。试指出哪些集合是相等的？哪些集合是不相等的？
2设S?{2,a,{3},4}，R?{{a},3,4,1}，判断下列各命题真或假：
（1）{a}?S； （2）{3}?S； （3）{O}?S； （4）O?{{3},4}； （5）O?{{a}}?R； （6）O?R； （7）O?R； （8）{{a},1,3,4}?R
3第18页 共53页
3试指出下列命题哪些为真？哪些为假？
（1）O?O； （2）O?{O}； （3）O?{{O}}； （4）O?{O,{O}}； （5）O?O； （6）O?{O}； （7）O?{{O}}； （8）O?{O,{O}} 4设A={a,b,c}，A是空集，试求P(A)，P(P(A))。 5 求下列集合的幂集：
（1）O； （2）{O}； （3）{O,{O}}； （4）{O,1,{2}}； （5）{{1},{O,1}}； （6）{{1,2},{1,1,2},{2,1,2}} 6设A,B,C是集合，试回答下列问题： （1）若A （2）若AB?AC，是否必须B?C？ B?AC，是否必须B?C？
（3）若A?B?A?C，是否必须B?C？ 7设A,B是任意的集合，求证: A-B= A∩(~B)。
8设A,B是任意的集合，求证: A?B=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。
9设集合E?{1,2,3,4,5}，A，B和C是E的子集，A?{1,3},B?{2,3,5}，C?{2,4}，试求： （1）A?~B （2）?A?B??~C （3）~?A?C? （4）??A????B? （5）C???C?
10设A，B，C是任意集合，证明：(A11设A，B是集合，证明： （1）若A?B，则 （2）(AB)C?A(BC)?C?A。
A?B
B)?(A)(B)
A
（3）若A?B且(?C)(C?A)，则B?第19页 共53页
（4）
A?A
12设A，B，C是任意集合，证明： A??B?C??A???B?A???A?C??
13某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为优的有多少人？
14用命题定律中的吸收律A∨(A∧B)?A和A∧(A∨B)?A，证明集合恒等式：
⑴A∩(A∪B)=A ⑵A∪(A∩B)=A
15用命题定律中的德摩根律? (A∨B)??A∧?B，? (A∧B)??A∨?B，证明集合恒等式：
⑴ ~ (A∪B)= ~A∩~B ⑵ ~ (A∩B)= ~A∪~B
16设A，B是任意集合，用已知的集合恒等式证明：A-B=A-(A∩B)。 17设A={a,b,c}，以下是A的子集构成的集合：
S={{a,b},{b,c}} Q={{a},{a,b},{a,c}} D={{a},{b,c}} G={{a,b,c
E={{a},{b},{c}} F={{a},{a,c}}
试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？ 18设A={1,2,3}，试确定A的所有划分。 19设A={a,b}，B={1,2,3}，
⑴试求A×B和B×A
⑵验证|A×B|=|A||B|和|B×A|=|B||A|
20设A={1,2}，B={a,b}，A={x,y}，求：A×B×C，A×(B×C)。 21设A?{a,b},B?{c}，求下列各集合： （1）A?{0,1}?B （2）B?A （3）(A?B)
第20页 共53页
2222设A?{a,b}，求P(A)?A。 23证明：若A?A?B?B，则A?B。
24证明：若A?B?A?C，且A?O，则B?C。
第21页 共53页
第三章 二元关系
3.1 基本概念
1. 用列举法表示下列A?B上的二元关系S：
(a) A?{0,1,2}，B?{0,2,4}，S?{?x,y?|x,y?AB}；
(b) A?{1,2,3,4,5}，B?{1,2,3}，S?{?x,y?|x?y2?x?A?y?B}。 2. 设A?{0,1,2,3,4}，试用列举法表达由下列谓词确定的A上的n元关系，如果是二元关
系，画出其关系图。 (a) P(x)?x?1； (b) P(x)?3?2； (c) P(x)?2?3； (d) P(x,y)?x?y?4；
(e) P(x,y)??k(x?ky?k?2)； (f) P(x,y,z)?x2?y?z。 3. 对下列关系R，求出关系矩阵MR：
(a) A?{1,2,3}，R?{?2,2?,?1,2?,?3,1?}； (b) A?{0,1,2,3}，R?{?x,y?|x?2?y?1}；
(c) A?{5,6,7,8}，B?{1,2,3}，R?{?x,y?|x?A?y?B?3?x?y?y}； (d) A?{0,1,2,3,4,5,6}，R?{?x,y?|x?y?x是质数}。 4. 对下列每一个N上关系R给出一归纳定义，用你的定义证明x?R。 (a) R?{?a,b?|a?b}，x??3,1?； (b) R?{?a,b?|a?2b}，x??6,3?； (c) R?{?a,b,c?|a?b?c}，x??1,1,2?。
第22页 共53页
5. 设A?{1,2,3,4}，R?{?1,2?,?2,4?,?3,3?}，S?{?1,3?,?2,4?,?4,2?}， (a) 求出RS，RS，R?S，R；
(b) 求出D(R)，R(R)，D(RS)，R(RS)。
6. 证明对任意集合A和A上的二元关系R和S，有
D(RS)?D(R)D(S)，R(R7. 设A是n个元素的集合，证明 (a) A上有2个一元关系； (b) A上有2个二元关系。
n2nS)?R(R)R(S)。
8. 设P1(x,y)?xy?0，P2(x,y)?|x?y|?4，P3(x,y)?x?y?10，
IP1(x,y)?x整除y，试确定由这些谓词所定义的整数集合上的二元关系是否具有以
下特性，将结果用Y(yes)和N(no)填入下表。
自反的 反自反的 对称的 反对称的 传递的 P1 P2 P3 P4 9. 确定整数集合I上的相等关系、?关系、?关系、全域关系、空关系具有哪些特性？试
将结果用类似于上题的表列出。
10. 设A?{1,2,3,4}，A上的下列关系是否可传递？如果不是可传递的，举出反例证明它，
然后找出一个具有最少序偶的关系R，使R包含原关系，并且是可传递的。 (a) R?{?1,1?}； (b) R?{?1,2?,?2,2?}；
(c) R?{?1,2?,?2,3?,?1,3?,?2,1?}；
第23页 共53页
(d) R?{?1,2?,?4,3?,?2,2?,?2,1?,?3,1?}。
11. (a) 找出一个非空的最小集合，并在其上定义一个既不是自反的，也不是反自反的关系；
(b) 找出一个非空的最小集合，并在其上定义一个既不是对称的，也不是反对称的关系； (c) 若(a)，(b)二题中允许用空集合，结果将怎样？
12. 考虑任意集合A上的二元关系的集合，如果某一集合运算施于关系后，所得关系仍具
有相同的性质，那么说一个关系的性质在该运算下是保持的。例如自反性质在二元运算并之下是保持的，因为两个自反关系的并是自反的。然而，自反性质在集合的求补运算下是不保持的，因为非空集合上的一个自反关系的绝对补不是一个自反关系。按照在指定的集合运算下给出的性质是否保持，填充下表。对每一非(N)的回答，给出反例。 自反的 反自反的 对称的 反对称的 传递的 2并R1 R2 交R1 R2 相对补R1?R2 绝对补A?A?R1 13. 在R平面上画出下述关系的图，确定对每一关系成立哪些性质。 (a) {?x,y?|x?y}；
(b) {?x,y?|x2?1?0?y?0}； (c) {?x,y?||x|?1?|y|?1}。
3.2 关系的合成
14. 设R1和R2是集合A?{a,b,c,d}上的关系，这里
R1?{?b,b?,?b,c?,?c,a?}，R2?{?b,a?,?c,d?,?c,a?,?d,c?}，
3求出R1R2，R2R1，R1R2R1，R12，R2。
第24页 共53页
15. 设R1和R2是集合A?{0,1,2,3}上的关系，这里
R1?{?i,j?|j?i?1?j?i/2}，R2?{?i,j?|i?j?2}，
3求出R1R2，R2R1，R1R2R1，R12，R2。
16. 证明：如果R是集合A上的空关系或全域关系，则R?R。
2R是如图3.3所示的A上的二元关系，17. 设A?{a,b,c,d,e,f,g}，试找出最小的整数m和n，使得m?n，且R?R。
18. 设R1和R2是集合A上的任意关系，证明或否定下列断言： (a) 如果R1和R2是自反的，那么R1R2是自反的； (b) 如果R1和R2是反自反的，那么R1R2是反自反的； (c) 如果R1和R2是对称的，那么R1R2是对称的； (d) 如果R1和R2是反对称的，那么R1R2是反对称的； (e) 如果R1和R2是传递的，那么R1R2是反传递的。
19. R1,R2,R3是集合A上的二元关系，试证明如果R1?R2，那么 (a) R1R3?R2R3； (b) R3R1?R3R2。
20. 设A?{1,2,3,4,5}，R?{?1,2?,?3,4?,?2,2?}，S?{?4,2?,?2,5?,?3,1?}，试求出MRS。
mn?0?021. 设A?{1,2,3,4}，MR???1??0001000011??0?，求MRn，n?N。 ?0?0?3.3 关系上的闭包运算
22. 试证明如果关系R是自反的，那么R也是自反的；如果R是可传递的、反自反的、对
称的或反对称的，则R亦然。
第25页 共53页
23. 如果关系R是反对称的，则在关系RR的关系矩阵中有多少个非零记入值。
24. 设A?{a,b,c}，R和S是A上的二元关系，其关系矩阵是
?110??110?????MR??010?，MS??010?，
?001??011?????试求出MR,MS,MRS,MRR。
25. 设R是A?{1,2,3,4}上的二元关系，其关系矩阵是
?1?0?MR??1??1000011110??1?， 0??0?试求出(a) Mr(R)；(b) Ms(R)；(c) MR2,MR3,MR4和Mt(R)。 26. 设R1和R2是集合A上的关系，且R1?R2，证明下列各式 (a) r(R1)?r(R2)； (b) s(R1)?s(R2)； (c) t(R1)?t(R2)。
27. 设R1和R2是集合A上的关系，证明下列各式 (a) r(R1(b) s(R1(c) t(R1R2)?r(R1)r(R2)； R2)?s(R1)s(R2)； R2)?t(R1)t(R2)；
R2)?t(R1)t(R2)。
2(d) 用反例证明t(R128. 找出n个元素的集合A和A上的二元关系R，使R,R,可能吗？如有可能，试举出例子。
,Rn,Rn?1都是有区别的，这
29. (a) 用反例证明语句“如果R是传递的，那么s(R)也是传递的”为假；
(b) 举一实例证明即使R是一有限集，st(R)和ts(R)也可以不相等。
第26页 共53页
30. 设R是集合A上的关系，证明下列各式 (a) (R?)??R?； (b) RR?R?RR； (c) (R?)??R?。
???3.4 次序关系
31. 设集合A?{a,b,c,d,e}上的关系R为
{?b,a?,?c,a?,?d,a?,?d,a?,?d,c?,?e,a?,?e,c?}IA
(a) 作出关系R的哈斯图和有向图；
(b) 求出A的最小元素和最大元素，如果不存在，请指出； (c) 求出A的极小元素和极大元素；
(d) 求出子集{b,c,d}，{c,d,e}和{a,b,c}的上界和下界，再指出这些子集的最小上界
和最大下界，如果存在的话。
32. 对下述每一条件，构造有限集和无限集的例子各一个： (a) 非空偏序集合，其中某些子集没有最大元素；
(b) 非空偏序集合，其中有一子集存在最大下界，但没有最小元素； (c) 非空偏序集合，其中有一子集存在上界，但没有最小下界。 33. 下述4个集合偏序集合、拟序集合、线序集合、良序集合？ (a) ??(N),??； (b) ??(N),??； (c) ??({a}),??； (d) ??(?),??。
34. 对集合I?I分别构造一良序和一拟序。 35. 证明下列断言：
(a) 如果R是拟序，那么R也是拟序； (b) 如果R是偏序，那么R也是偏序；
第27页 共53页
(c) 如果R是线序，那么R也是线序；
(d) 存在一集合S和S上的关系R，使?S,R?是良序集合，但?S,R?不是。 36. 设R是集合S上的关系，S?是S的子集，定义S?上的关系R?如下：
R??R(S??S?)，
确定下述每一断言是真还是假。
(a) 如果R在S上是传递的，那么R?在S?上是传递的； (b) 如果R是S的偏序，那么R?是S?上的偏序； (c) 如果R是S的拟序，那么R?是S?上的拟序； (d) 如果R是S的线序，那么R?是S?上的线序； (e) 如果R是S的良序，那么R?是S?上的良序。 37. (a) 证明R是一拟序当且仅当R(b) 证明R是一偏序当且仅当R38. 证明下述断言：
(a) 对任意线序集合，每一子集的极小元素是最小元素，每一极大元素是最大元素； (b) 一线序集合的每一非空有限子集有一最小和最大元素。
39. 设?A,??是非空有限线序集合，|A|?2，R是A?A上的关系，根据R的不同定义，
指出?A?A,R?是拟序集合、偏序集合、线序集合、良序集合，还是其他集合？ 对任意?a1,b1?,?a2,b2??A?A，
(a) ?a1,b1?R?a2,b2??a1?a2?b1?b2；
(b) ?a1,b1?R?a2,b2??a1?a2?a1?a2?b1?b2； (c) ?a1,b1?R?a2,b2??a1?a2； (d) ?a1,b1?R?a2,b2??a1?a2。 40. 设??{a,b,c}，规定a?b?c，
(a) 求出??,词典序?中下列各串的直接后继者和直接前驱者，如果它们存在的话： (i) x?abc； (ii) y?abaa； (iii) z?bb；
第28页 共53页
?R??，且R?R?； R?E，且R?R?。
(b) 对???,标准序?，重复上一题。
3.5 等价关系
41. 设R是A上的等价关系，将A的元素按R的等价类顺序排列，则等价关系的关系矩阵
MR有何特征？
42. 证明集合A上的全域关系A?A是等价关系。 43. 假设A是含n各元素的有限集合（n?N），问 (a) 有多少个元素在A上的最大等价关系中？ (b) A上的最大等价关系的秩是什么？ (c) 有多少个元素在A上的最小等价关系中？ (d) A上的最小等价关系的秩是什么？ 44. 设R和R?是集合A上的等价关系， (a) 证明RR?是集合A上的等价关系；
R?不一定是集合A上的等价关系，要尽可能小地选取集合A。
(b) 用例子证明R45. 设R1和R2是非空集合A上的等价关系，确定下述各式，哪些是A上的等价关系，对不
是的举例说明。 (a) A?A?R1； (b)R1?R2； (c)R12；
(d)r(R1?R2)（R1?R2的自反闭包）； (e) R1R2。
46. R是整数集合I上的等价关系，将R中的每一序偶?x,y?标在I?I笛卡儿平面上，
所得图形有何特点？
47. 应用上题结论说明下述I集合上的二元关系是否是等价关系，对不是的说明为什么，并
找出R诱导的等价关系。 (a) R??；
(b) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；
第29页 共53页
(c) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；
(d) R?{?a,b?|?x(x?I?10x?a?10(x?1)?10x?b?10(x?1))}； (e) R?{?a,b?|a整除b}。
Ra，48. R是集合A上的二元关系，对于所有的a,b,c?A，如果aRb,bRc，则c那么称R是循环的，试证明R是自反的和循环的当且仅当R是一等价关系。
49. 下述论证一位着每一对称的何传递的关系是一等价关系。设R是一对称的何传递关系， (i) 因为R是对称的，如果?x,y??R，那么?y,x??R；
(ii) 因为R是传递的，如果?y,x??R??x,y??R，那么?x,x??R，所以R是自
反的。这得出R是一等价关系。 这个论证有什么错误？
50. 设A?{a,b,c}，求出A的所有划分；设A的所有划分构成的集合是P，画出
?P,细分?的哈斯图。
51. 设A?{a,b,c,d}，?1是A的划分，?1?{{a,b,c},{d}}。 (a) 列出?1诱导出的等价关系的序偶；
(b) 对划分?2?{{a},{b},{c},{d}}，?2?{{a,b,c,d}}，做同样工作； (c) 画出偏序集合?{?1,?2,?3},细分?的哈斯图。
52. 设?1和?2是非空集合A的划分，说明下列各式哪些是A的划分，哪些可能是A的划分，
哪些不是A的划分？ (a) ?1(b) ?1?2； ?2；
(c) ?1??2； (d) (?1(?2??1))?2。
,Am}是集合A的划分，若AiB??，i?1,2,,m，试证明
53. 设{A1,A2,第30页 共53页
{A1B,A2B,,AmB}是AB的划分。
,?k是A上划分序列，使?i?1真细分?i，找
54. 设A是n个元素的有限集，假设?1,?2,出最大可能的序列长度。
55. 设A?I，定义A上的R1,R2,R3如下：
aR1b?a?b(mod3)，aR2b?a?b(mod5)，aR3b?a?b(mod6)，
(a) 对偏序集合?{A/R1,A/R2,A/R3},细分?画出哈斯图； (b) 描述一下各式所诱导的等价关系，它们的秩是什么？
A/R1A/R2，A/R1A/R3，A/R1?A/R2，A/R1?A/R3。
56. 设Rj表示I上模j等价，设Rk表示I上模k等价， (a) 证明I/Rk细分I/Rj当且仅当k是j的整数倍； (b) 描述划分I/Rk?I/Rj； (c) 描述划分I/RkI/Rj。 57. 证明如果?1细分?2，那么?1?2??1和?1??2??2。
58. 设P表示非空集合A的所有划分的集合，考虑偏序集合?P,细分?，设?1和?2是P的
成员， (a) 证明?1?2是集合{?1,?2}的最大下界；
(b) 证明?1??2是集合{?1,?2}的最小上界。
59. 设R是集合A上的二元关系，如果R是自反的和对称的，则称R是相容关系。设
A?{316,347,204,678}，R?{?x,y?|x?A?y?A?x和y有相同的数字}，
(a) R是相容关系吗？ (b) 画出R的关系图。
(c) 所有等价关系都是相容关系吗？
(d) 相容关系的关系图和等价关系的关系图有何不同？
第31页 共53页
补充习题：
1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。 2设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：
R={
3设A={1,2,3,4}，R是A的二元关系，定义为：
R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>} 写出A上二元关系R的关系矩阵。
4设X={1,2,3,4}，X上的二元关系H和S定义如下：
x?y是整数} 2x?yS={
3H={
试求H∪S，H∩S，~H，S-H。
5X={1,2,3,4,5}，X上的二元关系R和S定义如下：
R={<1,2>,<3,4>,<2,2} S={<4,2>,<2,5>,<3,1>,<1,3>}
试求R°S，S°R，R°(S°R)，(R°S)°R，R°R，S°S，R°R°R 。 6A={ 1,2,3,4}，A上的二元关系R定义如下：
R={<1,2>,<2,1>,<2,3>,<3,4>} 求二元关系R的各次幂。
7A={1,2,3,4,5}，A上的二元关系R和S定义如下：
R={<1,2>,<2,2>,<3,4>} S={<1,3>,<2,5>,<3,1>,<4,2>} 试求MR °
S和
MR ° MS，它们是否相等 ?
8设X={1,2,3,4}，Y={a,b,c}，X到Y二元关系
R={<1,a>,<2,b>,<4,c>}，
⑴试求RC，写出MR和MRC，验证MRC=MRT
⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。 9设R是实数集合，
第32页 共53页
＞={
是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。 10设A={1,2,3}，定义A上的二元关系如下：
R={<1,1>,<2,2>,<3,3>,<1,3>} S={<1,3>} T={<1,1>}
试说明R，S，T是否是A上的自反关系或反自反关系。 11设A={1,3,5,7}，定义A上的二元关系如下：
R={
R={<1,1>,<2,2>} S={<1,1>,<1,2>,<2,1>} T={<1,2>,<1,3>} U={<1,3>,<1,2>,<2,1>}
试说明R，S，T，U是否是A上的对称关系和反对称关系。 13设R是实数集合，
S={
是实数集合上的等于关系。证明实数集合上的等于关系是传递的。 14设R，S是X上的二元关系，证明
⑴若R，S是自反的，则R∪S和R∩S也是自反的。 ⑵若R，S是对称的，则R∪S和R∩S也是对称的。 ⑶若R，S是传递的，则R∩S也是传递的。 15设A={1,2,3}，定义A上的二元关系R为：
R={<1,2>,<2,3>,<3,1>} 试求：r(R)，s(R)，t(R)。
16设A={1,2,3}，定义A上的二元关系R为：
R={<1,2>,<2,3>,<3,1>} 试用关系矩阵求传递闭包t(R)。
217设集合 A?{a,b,c,d}， A上的二元关系 R?{(a,a),(a,c),(b,d)}，求R。
第33页 共53页
18设A={1,2,3,4,5}，R是A上的二元关系，
R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>} 证明R是A上的等价关系。
19设R={
R???1,1?,?1,3?,?1,6?,?2,2?,?2,5?,?3,1?,?3,3?,?3,6?,?4,4?,?5,2?,?5,5?,?6,1?,?6,3?,?6,6??，
（1）验证R是等价关系； （2）给出R的关系图．
23设A={316,347,204,678,770}，A上的二元关系R定义为：R={
24设X={1,2,3,4}，S1={{1,2,3},{3,4}}，S2={{1,2},{2,3},{1,3},{3,4}}是X的两个覆盖。试写出S1和S2 导出的相容关系R1和R2。
25设A是集合，P (A)是A的幂集合，P (A)上的包含关系?定义如下：
?={
试证明?是P (A)上偏序关系。
26设A={2,5,6,10,15,30}，A上的整除关系R定义如下：
R={
验证R是A上的偏序关系，分析哪些元素盖住了另一些元素，哪些元素没有盖住了另一些元素。
27设A={a,b,c,d,e,f,g,h}，A上的二元关系
R={
验证R是A上的偏序关系。写出盖住关系COV A，画出哈斯图。找出集合A的极大元和极小元。
28设A={2,3,6,12,24,36}，其上的整除关系
R={
是A上的偏序关系，试求盖住关系COV A，画出哈斯图，确定下列集合的上界和下界。
第34页 共53页
⑴ B1={2,3,6} ⑵ B2={12,24,36}
29设N为自然数集合，N上的大于等于关系定义为
R≥={
30设P={?,{a},{a,b},{a,b,c}}，P上的包含关系
R?={
验证R?是全序关系。
第35页 共53页
第三章 二元关系
3.1 基本概念
1. 用列举法表示下列A?B上的二元关系S：
(a) A?{0,1,2}，B?{0,2,4}，S?{?x,y?|x,y?AB}；
(b) A?{1,2,3,4,5}，B?{1,2,3}，S?{?x,y?|x?y2?x?A?y?B}。 2. 设A?{0,1,2,3,4}，试用列举法表达由下列谓词确定的A上的n元关系，如果是二元关
系，画出其关系图。 (a) P(x)?x?1； (b) P(x)?3?2； (c) P(x)?2?3； (d) P(x,y)?x?y?4；
(e) P(x,y)??k(x?ky?k?2)； (f) P(x,y,z)?x2?y?z。 3. 对下列关系R，求出关系矩阵MR：
(a) A?{1,2,3}，R?{?2,2?,?1,2?,?3,1?}； (b) A?{0,1,2,3}，R?{?x,y?|x?2?y?1}；
(c) A?{5,6,7,8}，B?{1,2,3}，R?{?x,y?|x?A?y?B?3?x?y?y}； (d) A?{0,1,2,3,4,5,6}，R?{?x,y?|x?y?x是质数}。 4. 对下列每一个N上关系R给出一归纳定义，用你的定义证明x?R。 (a) R?{?a,b?|a?b}，x??3,1?； (b) R?{?a,b?|a?2b}，x??6,3?； (c) R?{?a,b,c?|a?b?c}，x??1,1,2?。
第36页 共53页
5. 设A?{1,2,3,4}，R?{?1,2?,?2,4?,?3,3?}，S?{?1,3?,?2,4?,?4,2?}， (a) 求出RS，RS，R?S，R；
(b) 求出D(R)，R(R)，D(RS)，R(RS)。
6. 证明对任意集合A和A上的二元关系R和S，有
D(RS)?D(R)D(S)，R(R7. 设A是n个元素的集合，证明 (a) A上有2个一元关系； (b) A上有2个二元关系。
n2nS)?R(R)R(S)。
8. 设P1(x,y)?xy?0，P2(x,y)?|x?y|?4，P3(x,y)?x?y?10，
IP1(x,y)?x整除y，试确定由这些谓词所定义的整数集合上的二元关系是否具有以
下特性，将结果用Y(yes)和N(no)填入下表。
自反的 反自反的 对称的 反对称的 传递的 P1 P2 P3 P4 9. 确定整数集合I上的相等关系、?关系、?关系、全域关系、空关系具有哪些特性？试
将结果用类似于上题的表列出。
10. 设A?{1,2,3,4}，A上的下列关系是否可传递？如果不是可传递的，举出反例证明它，
然后找出一个具有最少序偶的关系R，使R包含原关系，并且是可传递的。 (a) R?{?1,1?}； (b) R?{?1,2?,?2,2?}；
(c) R?{?1,2?,?2,3?,?1,3?,?2,1?}；
第37页 共53页
(d) R?{?1,2?,?4,3?,?2,2?,?2,1?,?3,1?}。
11. (a) 找出一个非空的最小集合，并在其上定义一个既不是自反的，也不是反自反的关系；
(b) 找出一个非空的最小集合，并在其上定义一个既不是对称的，也不是反对称的关系； (c) 若(a)，(b)二题中允许用空集合，结果将怎样？
12. 考虑任意集合A上的二元关系的集合，如果某一集合运算施于关系后，所得关系仍具
有相同的性质，那么说一个关系的性质在该运算下是保持的。例如自反性质在二元运算并之下是保持的，因为两个自反关系的并是自反的。然而，自反性质在集合的求补运算下是不保持的，因为非空集合上的一个自反关系的绝对补不是一个自反关系。按照在指定的集合运算下给出的性质是否保持，填充下表。对每一非(N)的回答，给出反例。 自反的 反自反的 对称的 反对称的 传递的 2并R1 R2 交R1 R2 相对补R1?R2 绝对补A?A?R1 13. 在R平面上画出下述关系的图，确定对每一关系成立哪些性质。 (a) {?x,y?|x?y}；
(b) {?x,y?|x2?1?0?y?0}； (c) {?x,y?||x|?1?|y|?1}。
3.2 关系的合成
14. 设R1和R2是集合A?{a,b,c,d}上的关系，这里
R1?{?b,b?,?b,c?,?c,a?}，R2?{?b,a?,?c,d?,?c,a?,?d,c?}，
3求出R1R2，R2R1，R1R2R1，R12，R2。
第38页 共53页
15. 设R1和R2是集合A?{0,1,2,3}上的关系，这里
R1?{?i,j?|j?i?1?j?i/2}，R2?{?i,j?|i?j?2}，
3求出R1R2，R2R1，R1R2R1，R12，R2。
16. 证明：如果R是集合A上的空关系或全域关系，则R?R。
2R是如图3.3所示的A上的二元关系，17. 设A?{a,b,c,d,e,f,g}，试找出最小的整数m和n，使得m?n，且R?R。
18. 设R1和R2是集合A上的任意关系，证明或否定下列断言： (a) 如果R1和R2是自反的，那么R1R2是自反的； (b) 如果R1和R2是反自反的，那么R1R2是反自反的； (c) 如果R1和R2是对称的，那么R1R2是对称的； (d) 如果R1和R2是反对称的，那么R1R2是反对称的； (e) 如果R1和R2是传递的，那么R1R2是反传递的。
19. R1,R2,R3是集合A上的二元关系，试证明如果R1?R2，那么 (a) R1R3?R2R3； (b) R3R1?R3R2。
20. 设A?{1,2,3,4,5}，R?{?1,2?,?3,4?,?2,2?}，S?{?4,2?,?2,5?,?3,1?}，试求出MRS。
mn?0?021. 设A?{1,2,3,4}，MR???1??0
001000011??0?，求MRn，n?N。 ?0?0?3.3 关系上的闭包运算
22. 试证明如果关系R是自反的，那么R也是自反的；如果R是可传递的、反自反的、对
第39页 共53页
称的或反对称的，则R亦然。 23. 如果关系R是反对称的，则在关系RR的关系矩阵中有多少个非零记入值。
24. 设A?{a,b,c}，R和S是A上的二元关系，其关系矩阵是
?110??110?????MR??010?，MS??010?，
?001??011?????试求出MR,MS,MRS,MRR。
25. 设R是A?{1,2,3,4}上的二元关系，其关系矩阵是
?1?0MR???1??1000011110??1?， ?0?0?试求出(a) Mr(R)；(b) Ms(R)；(c) MR2,MR3,MR4和Mt(R)。 26. 设R1和R2是集合A上的关系，且R1?R2，证明下列各式 (a) r(R1)?r(R2)； (b) s(R1)?s(R2)； (c) t(R1)?t(R2)。
27. 设R1和R2是集合A上的关系，证明下列各式 (a) r(R1(b) s(R1(c) t(R1R2)?r(R1)r(R2)； R2)?s(R1)s(R2)； R2)?t(R1)t(R2)；
R2)?t(R1)t(R2)。
2(d) 用反例证明t(R128. 找出n个元素的集合A和A上的二元关系R，使R,R,可能吗？如有可能，试举出例子。
,Rn,Rn?1都是有区别的，这
29. (a) 用反例证明语句“如果R是传递的，那么s(R)也是传递的”为假；
第40页 共53页
(b) 举一实例证明即使R是一有限集，st(R)和ts(R)也可以不相等。 30. 设R是集合A上的关系，证明下列各式 (a) (R?)??R?； (b) RR?R?RR； (c) (R?)??R?。
???3.4 次序关系
31. 设集合A?{a,b,c,d,e}上的关系R为
{?b,a?,?c,a?,?d,a?,?d,a?,?d,c?,?e,a?,?e,c?}IA
(a) 作出关系R的哈斯图和有向图；
(b) 求出A的最小元素和最大元素，如果不存在，请指出； (c) 求出A的极小元素和极大元素；
(d) 求出子集{b,c,d}，{c,d,e}和{a,b,c}的上界和下界，再指出这些子集的最小上界
和最大下界，如果存在的话。
32. 对下述每一条件，构造有限集和无限集的例子各一个： (a) 非空偏序集合，其中某些子集没有最大元素；
(b) 非空偏序集合，其中有一子集存在最大下界，但没有最小元素； (c) 非空偏序集合，其中有一子集存在上界，但没有最小下界。 33. 下述4个集合偏序集合、拟序集合、线序集合、良序集合？ (a) ??(N),??； (b) ??(N),??； (c) ??({a}),??； (d) ??(?),??。
34. 对集合I?I分别构造一良序和一拟序。 35. 证明下列断言：
第41页 共53页
(a) 如果R是拟序，那么R也是拟序； (b) 如果R是偏序，那么R也是偏序； (c) 如果R是线序，那么R也是线序；
(d) 存在一集合S和S上的关系R，使?S,R?是良序集合，但?S,R?不是。 36. 设R是集合S上的关系，S?是S的子集，定义S?上的关系R?如下：
R??R(S??S?)，
确定下述每一断言是真还是假。
(a) 如果R在S上是传递的，那么R?在S?上是传递的； (b) 如果R是S的偏序，那么R?是S?上的偏序； (c) 如果R是S的拟序，那么R?是S?上的拟序； (d) 如果R是S的线序，那么R?是S?上的线序； (e) 如果R是S的良序，那么R?是S?上的良序。 37. (a) 证明R是一拟序当且仅当R(b) 证明R是一偏序当且仅当R38. 证明下述断言：
(a) 对任意线序集合，每一子集的极小元素是最小元素，每一极大元素是最大元素； (b) 一线序集合的每一非空有限子集有一最小和最大元素。
39. 设?A,??是非空有限线序集合，|A|?2，R是A?A上的关系，根据R的不同定义，
指出?A?A,R?是拟序集合、偏序集合、线序集合、良序集合，还是其他集合？ 对任意?a1,b1?,?a2,b2??A?A，
(a) ?a1,b1?R?a2,b2??a1?a2?b1?b2；
(b) ?a1,b1?R?a2,b2??a1?a2?a1?a2?b1?b2； (c) ?a1,b1?R?a2,b2??a1?a2； (d) ?a1,b1?R?a2,b2??a1?a2。 40. 设??{a,b,c}，规定a?b?c，
第42页 共53页
R??，且R?R?； R?E，且R?R?。
(a) 求出???,词典序?中下列各串的直接后继者和直接前驱者，如果它们存在的话： (i) x?abc； (ii) y?abaa； (iii) z?bb； (b) 对???,标准序?，重复上一题。
3.5 等价关系
41. 设R是A上的等价关系，将A的元素按R的等价类顺序排列，则等价关系的关系矩阵
MR有何特征？
42. 证明集合A上的全域关系A?A是等价关系。 43. 假设A是含n各元素的有限集合（n?N），问 (a) 有多少个元素在A上的最大等价关系中？ (b) A上的最大等价关系的秩是什么？ (c) 有多少个元素在A上的最小等价关系中？ (d) A上的最小等价关系的秩是什么？ 44. 设R和R?是集合A上的等价关系， (a) 证明RR?是集合A上的等价关系；
R?不一定是集合A上的等价关系，要尽可能小地选取集合A。
(b) 用例子证明R45. 设R1和R2是非空集合A上的等价关系，确定下述各式，哪些是A上的等价关系，对不
是的举例说明。 (a) A?A?R1； (b)R1?R2； (c)R12；
(d)r(R1?R2)（R1?R2的自反闭包）； (e) R1R2。
46. R是整数集合I上的等价关系，将R中的每一序偶?x,y?标在I?I笛卡儿平面上，
所得图形有何特点？
47. 应用上题结论说明下述I集合上的二元关系是否是等价关系，对不是的说明为什么，并
找出R诱导的等价关系。
第43页 共53页
(a) R??；
(b) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}； (c) R?{?a,b?|(a?0?b?0)?(a?0?b?0)}；
(d) R?{?a,b?|?x(x?I?10x?a?10(x?1)?10x?b?10(x?1))}； (e) R?{?a,b?|a整除b}。
Ra，48. R是集合A上的二元关系，对于所有的a,b,c?A，如果aRb,bRc，则c那么称R是循环的，试证明R是自反的和循环的当且仅当R是一等价关系。
49. 下述论证一位着每一对称的何传递的关系是一等价关系。设R是一对称的何传递关系， (i) 因为R是对称的，如果?x,y??R，那么?y,x??R；
(ii) 因为R是传递的，如果?y,x??R??x,y??R，那么?x,x??R，所以R是自
反的。这得出R是一等价关系。 这个论证有什么错误？
50. 设A?{a,b,c}，求出A的所有划分；设A的所有划分构成的集合是P，画出
?P,细分?的哈斯图。
51. 设A?{a,b,c,d}，?1是A的划分，?1?{{a,b,c},{d}}。 (a) 列出?1诱导出的等价关系的序偶；
(b) 对划分?2?{{a},{b},{c},{d}}，?2?{{a,b,c,d}}，做同样工作； (c) 画出偏序集合?{?1,?2,?3},细分?的哈斯图。
52. 设?1和?2是非空集合A的划分，说明下列各式哪些是A的划分，哪些可能是A的划分，
哪些不是A的划分？ (a) ?1(b) ?1?2； ?2；
(c) ?1??2； (d) (?1(?2??1))?2。
第44页 共53页
53. 设{A1,A2,,Am}是集合A的划分，若AiB,,AmB??，i?1,2,,m，试证明
{A1B,A2B}是AB的划分。
,?k是A上划分序列，使?i?1真细分?i，找
54. 设A是n个元素的有限集，假设?1,?2,出最大可能的序列长度。
55. 设A?I，定义A上的R1,R2,R3如下：
aR1b?a?b(mod3)，aR2b?a?b(mod5)，aR3b?a?b(mod6)，
(a) 对偏序集合?{A/R1,A/R2,A/R3},细分?画出哈斯图； (b) 描述一下各式所诱导的等价关系，它们的秩是什么？
A/R1A/R2，A/R1A/R3，A/R1?A/R2，A/R1?A/R3。
56. 设Rj表示I上模j等价，设Rk表示I上模k等价， (a) 证明I/Rk细分I/Rj当且仅当k是j的整数倍； (b) 描述划分I/Rk?I/Rj； (c) 描述划分I/RkI/Rj。 57. 证明如果?1细分?2，那么?1?2??1和?1??2??2。
58. 设P表示非空集合A的所有划分的集合，考虑偏序集合?P,细分?，设?1和?2是P的
成员， (a) 证明?1?2是集合{?1,?2}的最大下界；
(b) 证明?1??2是集合{?1,?2}的最小上界。
59. 设R是集合A上的二元关系，如果R是自反的和对称的，则称R是相容关系。设
A?{316,347,204,678}，R?{?x,y?|x?A?y?A?x和y有相同的数字}，
(a) R是相容关系吗？ (b) 画出R的关系图。
(c) 所有等价关系都是相容关系吗？
(d) 相容关系的关系图和等价关系的关系图有何不同？
第45页 共53页
补充习题：
1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。 2设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：
R={
3设A={1,2,3,4}，R是A的二元关系，定义为：
R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>} 写出A上二元关系R的关系矩阵。
4设X={1,2,3,4}，X上的二元关系H和S定义如下：
x?y是整数} 2x?yS={
3H={
试求H∪S，H∩S，~H，S-H。
5X={1,2,3,4,5}，X上的二元关系R和S定义如下：
R={<1,2>,<3,4>,<2,2} S={<4,2>,<2,5>,<3,1>,<1,3>}
试求R°S，S°R，R°(S°R)，(R°S)°R，R°R，S°S，R°R°R 。 6A={ 1,2,3,4}，A上的二元关系R定义如下：
R={<1,2>,<2,1>,<2,3>,<3,4>} 求二元关系R的各次幂。
7A={1,2,3,4,5}，A上的二元关系R和S定义如下：
R={<1,2>,<2,2>,<3,4>} S={<1,3>,<2,5>,<3,1>,<4,2>} 试求MR °
S和
MR ° MS，它们是否相等 ?
8设X={1,2,3,4}，Y={a,b,c}，X到Y二元关系
R={<1,a>,<2,b>,<4,c>}，
⑴试求RC，写出MR和MRC，验证MRC=MRT
第46页 共53页
⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。 9设R是实数集合，
＞={
是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。 10设A={1,2,3}，定义A上的二元关系如下：
R={<1,1>,<2,2>,<3,3>,<1,3>} S={<1,3>} T={<1,1>}
试说明R，S，T是否是A上的自反关系或反自反关系。 11设A={1,3,5,7}，定义A上的二元关系如下：
R={
R={<1,1>,<2,2>} S={<1,1>,<1,2>,<2,1>} T={<1,2>,<1,3>} U={<1,3>,<1,2>,<2,1>}
试说明R，S，T，U是否是A上的对称关系和反对称关系。 13设R是实数集合，
S={
是实数集合上的等于关系。证明实数集合上的等于关系是传递的。 14设R，S是X上的二元关系，证明
⑴若R，S是自反的，则R∪S和R∩S也是自反的。 ⑵若R，S是对称的，则R∪S和R∩S也是对称的。 ⑶若R，S是传递的，则R∩S也是传递的。 15设A={1,2,3}，定义A上的二元关系R为：
R={<1,2>,<2,3>,<3,1>} 试求：r(R)，s(R)，t(R)。
16设A={1,2,3}，定义A上的二元关系R为：
R={<1,2>,<2,3>,<3,1>}
第47页 共53页
试用关系矩阵求传递闭包t(R)。
217设集合 A?{a,b,c,d}， A上的二元关系 R?{(a,a),(a,c),(b,d)}，求R。
18设A={1,2,3,4,5}，R是A上的二元关系，
R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>} 证明R是A上的等价关系。
19设R={
R???1,1?,?1,3?,?1,6?,?2,2?,?2,5?,?3,1?,?3,3?,?3,6?,?4,4?,?5,2?,?5,5?,?6,1?,?6,3?,?6,6??，
（1）验证R是等价关系； （2）给出R的关系图．
23设A={316,347,204,678,770}，A上的二元关系R定义为：R={
24设X={1,2,3,4}，S1={{1,2,3},{3,4}}，S2={{1,2},{2,3},{1,3},{3,4}}是X的两个覆盖。试写出S1和S2 导出的相容关系R1和R2。
25设A是集合，P (A)是A的幂集合，P (A)上的包含关系?定义如下：
?={
试证明?是P (A)上偏序关系。
26设A={2,5,6,10,15,30}，A上的整除关系R定义如下：
R={
验证R是A上的偏序关系，分析哪些元素盖住了另一些元素，哪些元素没有盖住了另一些元素。
27设A={a,b,c,d,e,f,g,h}，A上的二元关系
R={
验证R是A上的偏序关系。写出盖住关系COV A，画出哈斯图。找出集合A的极大元和极小元。
28设A={2,3,6,12,24,36}，其上的整除关系
第48页 共53页
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页
补充习题：
1设I是整数集，N是自然数集。试证明I~N。
2设N为自然数集，证明集合M={x|x=10n∧n?N}是可数集。
3在直角坐标系下，两坐标x，y均为整数的点(x,y)称为格点。证明全体格点构成可数集。 4证明有理数全体是可数集。 5证明区间[0,1]与(0,1)有相同的基数。
6设A是自然数集合，B=(0,1)，|A|＝|N|=So，|B|=S，求证|A×B|=S。 7对下述每组集合A和B，试构造从A到B的双射函数，说明A和B等势。 （1）A?N,B?N?N （2）A?Z,B?N 8设A19设AB1,A2C,BB2，且A1A2?B1B2?O，证明A1A2B1B2。
D，证明A?BC?D。
10证明：若A是不可数无穷集，B是A的可数子集，则(A?B)11证明：若A是任意无穷集，B是一个可数集，则(A
A。
B)A。
第53页 共53页