第三章集合与关系复习2

1、第三章 集合与关系,(1). 组织结构是明确的，但是内容比较多 (2). 集合、直积、关系这些概念是简单的 (3). 主要难点在于：复合、闭包和特殊关系 （等价关系、相容关系、序关系）,习题3-1(p86),（6）确定下列集合的幂集 a) a,a b) 1,2,3 解答： a) a,a, a,a, b) , 1,2,3,这种题目通常通过|P(A)|=2|A|来计算幂集中元素的个数，然后验证解答是否正确，抓住这个，我们可以计算难题,习题3-1(p86),（6）确定下列集合的幂集 d) P() e) P(P() (习题) 解答： d) 没有元素，所以|P()|=20 =1， P() = ，P(P(

2、) = , (21) e) P(P(P() = P(P()=P(,) = , , (22),习题3-1(p86),(7) 设A=, B= P(P(A)。问： a) 是否 B ？是否 B ? b) 是否 B ？是否 B ？ c) 是否 B ? 是否 B ? 解答：由上题得到： P(P() = , , 所以a) B ， B ；b) B , B ; c) B, B (拆括号法),习题3-2(p95),(5) 证明： 对任意集合A，B，C，有 a) (A - B) - C = A - (BC) 证明：x (A - B) C x (A - B) x C x A x B x C x A x (BC) x

3、A - (BC) 所以 (A - B) - C = A - (BC),习题3-2(p95),8. a) 已知AB = AC，是否必须B=C ？ b) 已知A B = A C，是否必须B=C ？ c) 已知AB = AC，是否必须B=C ？ a). A=1,2 , B=3, C=2,3为反例 b). A=1,2, B=1, C=2为反例 c). AB = AC AAB =AAC B= C B=C,习题3-2(p95),a) A (BC) = (A B)(A C) 左边= A (B-C)(C-B) = A(BC)(C B) = (ABC) (ABC) 右边= (AB) (AC)(AC) (AB)

4、= (ABA) (ABC) (ACA) (ACB) = (ABC) (ABC),习题3-3(p100),(5)A1: 学数学，A2：学物理，A3：学生物 |A1|=67, |A2|=47, |A3|=95 |A1 A3|=26, |A1 A2|=28, |A2 A3|=27 N = 200， |(A1A2A3)|=50 又|A1A2A3|=|A1|+|A2|+|A3|- |A1 A3| - |A1 A2|- |A2 A3|+|A1 A2A3 | 所以200-50 = 67+47+95-26-28-27+ |A1 A2A3|， 因此|A1 A2A3|=22,习题3-4(p105),(3) 下列各

5、式中哪些成立？哪些不成立？为什么？ b) (A B)(C D) = (AC) (BD) d) (A B)C = (AC) (BC) b) A = 1 ,2 , B = 1, C =1,2, D =1 (A B)(C D) = (AC) (BD) = ,习题3-4(p105),d) (A B)C (x A x B y C ) (x A y C y C ) (x A y C ) (x B y C ) AC BC (AC ) (BC) 所以(A B)C = (AC) (BC),习题3-4(p105),(4) 证明：若XX = YY，则X=Y 证：（1） XX，则 YY，所以xY，X Y； （2）反之

6、，设 YY, 则 XX，y X，Y X； 所以X=Y,习题3-5(p110),(5) 对式中所给出A上的二元关系，试给出关系图 |0 x y 3，A=0,1,2,3,4 R = , , , , , , , , , ,习题3-5(p110),(6) 对0,1,2,3,4,5,6上的二元关系， |x, , , , , , , , ,习题3-5(p110),(7)设P=,和Q=, ,找出PQ , P Q , dom P, domQ ran P, ran Q, dom(P Q), ran(P Q) 解： PQ =, PQ = , domP = 1,2,3, domQ=1,2,4 ran P=2,3,4

7、, ran Q = 2,3,4 dom(P Q )=2, ran(P Q)=4,习题3-6(p113),(1) 分析集合A=1,2,3上的下述五个关系。 R=, S=, T=, 判断A中的上述关系是不是a)自反的，b)对称的，c)可传递的，d)反对称的。 解答：（1）R满足反对称性和传递性； （2）S满足自反、对称和传递性 （3）T满足反对称性。,破坏传递,习题3-6(p113),(2)给定A=1,2,3,4,考虑A上的关系R，若 R = , a) 在AA的坐标图中标出R，并绘出它的关系图；b)R是自反的，对称的，可传递的，反对称的吗？ 解答：,可传递的，反对称的,习题3-6(p114),(6

8、)设R是集合X上的一个自反关系。求证：R是对称和传递的，当且仅当和在R之中则有在R之中。 证明：（1）若R是对称的，则由和在R中，因此,在R中，R是传递的，因此在R中，由对称，在R中；（2）a,b,c任意，a取c，、和在R中，故R对称；因此由在R中知道在R中，,在R中，推出R传递。,习题3-7(p118),(1)设R1和R2是A上的任意关系，说明以下命题的真假，并予以证明 a) 若R1和R2是自反的,则R1R2也是自反的 c) 若R1和R2是对称的,则R1R2也是对称的 解答：a）成立，在R1中有R1， 在R2中有 R2, 因此 R1R2，有自反性。 c）不成立，设R1=, R2=, 则R1R

9、2=, 无对称性。,习题3-7(p119),(5) R是A上的一个二元关系，如果R是自反的，则Rc一定是自反的吗？如果R是对称的，则Rc一定是对称的吗？如果R是传递的，则Rc一定是传递的吗？ 解答：（1）R自反， R，所以 Rc，Rc自反；（2）R对称，Rc=R，也对称； （3）, R , Rc, 因此满足传递性,习题3-8(p127),(2)设集合A=a,b,c,d, A上的关系 R=, a) 用矩阵运算和作图方法求出R的自反闭包、对称闭包和传递闭包。 b) 用Warshall算法求出R的传递闭包 解答：,图略，直接解说 传递性，要解说一步边、两步边、三步边、四步边,习题3-8(p127),

10、矩阵运算，(加法为析取) 自反M1 = M+Ix, 对称M2=M+Mc， 传递M3=M1+M12+M13+M14 b),习题3-8(p127),(7) 设R1和R2是A上的关系，证明： a) r(R1R2) = r(R1)r(R2) b) s(R1R2) = s(R1)s(R2) 解答：a）左边=R1 R2 I ， 右边=R1 I R2 I = R1 R2 I b）左边=R1R2 (R1R2 )c = R1R2 R1cR2c 右边= R1R1cR2 R2c ，两边相等,习题3-9(p130),(4)题略。 证明：（1）Ai不包含于Aj，因此Ai不可能为空集；（2）有Ai Aj=，这是因为若有A

11、i Aj不为空，设共同元素有x，因此Ai中的元素ai和Aj中的元素aj，由题意有 R, R，由对称和传递，可以得到 R, 因此ai，aj在一个集合中，因此Ai=Aj，这和Ai、Aj互不包含相排斥。 （3） a A，由自反性， R, 因此a和a在某个子集As中，由a的任意性，遍历s，得到a A1 A2 Ak 。（a A1 A2 Ak推出a A显然， 上面可以证明a A 推出a A1 A2 Ak ），因此A1 A2 Ak = A,习题3-10(p134),(3) 给定集合S=1,2,3,4,5，找出S上的等价关系R，此关系R能够产生划分1,2,3,4,5并画出关系图。 R = 1,22 32 4,

12、52 = , , 关系图分为三部分，为两个完全2边形和一个完全0边形（用画笔画一下）,习题3-10(p135),(6) 设R是集合A上的对称和传递关系，证明如果对于A中的每一个元素a，在A中同时也存在一个b，使在R中，则R是一个等价关系。 证明：只需证明R是自反的。对于任意的a，存在b，有 R，由对称性 R；由传递性， R，因此R是自反的，所以R是一个等价关系。,习题3-11(p139),(1) 设R是X上的二元关系，试证明 r=Ix R Rc是X上的相容关系。 证明：（1） Ix，因此 r，r自反；（2） R , 则 Rc， 因此 r并且 r, r是对称的。 因此r是相容关系。,习题3-11

13、(p139),(2) 题目省略。 解答：完全覆盖为(最大相容类集合)： x1,x2,x3,x1,x3,x6 x3,x5,x6,x3,x4,x5,习题3-11(p139),(4) 设C=A1,A2,An为集合A的覆盖，试由此覆盖确定A上的一个相容关系。并说明在什么条件下，此相容关系为等价关系。 R = A1A1 A2A2 AnAn 当R满足传递性，此相容关系为等价关系，一般的，只要C不仅是一个覆盖，还是一个划分的时候，R就能满足传递性，R就是等价关系。,习题3-12(p145),(1) 设集合为3,5,15, 1,2,3,6,12, 3,9,27,54，偏序关系为整除，画出这些集合的偏序关系图，

14、并指出哪些是全序关系。 第3个图代表全序,习题3-12(p146),(6)题见书本 极大元 最大元 极小元 最小元 P x1 x1 x4、x5 无 上界 上确界 下界 下确界 x2,x3,x4 x1 x1 x4 x4 x3,x4,x5 x1,x3 x3 无 无 x1,x2,x3 x1 x1 x4 x4,习题3-12(p146),(7)题目省略 画哈斯图，注意先看出射点和入射点，全序和良序只为（c）图,习题4-1 (p151),(1) 题目省略 解答：(a)都不是；(b)都不是; (c)是满射 (d)都不是, (i=-1和i=1,值相同) (e) 是双射,习题4-1 (p151),(5) 假定X和Y是有穷集合, 找出从X到Y存在入射的必要条件是什么? 解答：1）x1x2, 则f(x1)f(x2), 即y1 y2 2）Y集合的点多，X集合的点少，即 |Y| |X| 条件1）、2）分别为从X到Y存在入射的必要条件，条件1）、2）合起来是充要条件,习题4-2 (p156),(1) 题目省略 解答：f要有f-1，f必须为双射，构造 f = , f2 = , f3 = f f2=fI=f f-1=, = f f f-1=, 令g=f，g2=f2=I,习题4-2 (p156),(3) 要证明c，只需要证明a）、b），a）比较明显，按定