《第三章复习ppt课件.pptx》由会员分享，可在线阅读，更多相关《第三章复习ppt课件.pptx（38页珍藏版）》请在三一办公上搜索。
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
2、1)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 A - (BC)所以 (A
3、- 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) = (ABA) (ABC) (ACA)
4、(ACB) = (ABC) (ABC),习题3-3(p100),(5)A1: 学数学，A2：学物理，A3：学生物 |A1|=67, |A2|=47, |A3|=95|A1 A3|=26, |A1 A2|=28, |A2 A3|=27N = 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) 下列各式中哪些成立？哪些不成立？为什么？b) (A B)
5、(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）反之，设 YY,则 XX，y X，Y X；所以X=Y,习题3-5(p11
6、0),(5) 对式中所给出A上的二元关系，试给出关系图 |0 x y 3，A=0,1,2,3,4R = , , , , , , , , , ,习题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,4ran P=2,3,4, ran Q = 2,3,4dom(P Q )=2, ran(P Q)=4,习题3-
7、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)设R是集合X上的一个自反关系。求证：R是对称和传递的，当且仅当和在R之中则有在R之中。证明：（1）若R是对
8、称的，则由和在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=, 则R1R2=, 无对称性。,习题3-7(p119),(5) R是A上的一个二元关系，如果R是自反的，则Rc一定是自反的吗？如果
9、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),矩阵运算，(加法为析取)自反M1 = M+Ix, 对称M2=M+Mc，传递M3=M1+M12+M13+M14b),习题3-8(p12
10、7),(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=，这是因为若有Ai Aj不为空，设共同元素有x，因此Ai中的元素ai和Aj中的元素aj，由题意有 R, R，由对称和传递，可以得到 R, 因此ai，aj在一个集合
11、中，因此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,52 = , ,关系图分为三部分，为两个完全2边形和一个完全0边形（用画笔画一下）,习题3-10(p135),(6) 设R是集合A上的对称和传递关系，
12、证明如果对于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(p139),(2) 题目省略。解答：完全覆盖为(最大相容类集合)：x1,x2,x3,x1,x3,x6x3,x5,x6,x3,x4,x5,习题3-11(p139)
13、,(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，偏序关系为整除，画出这些集合的偏序关系图，并指出哪些是全序关系。第3个图代表全序,习题3-12(p146),(6)题见书本 极大元 最大元 极小元 最小元 P x1 x1 x4、x5 无 上界 上确界 下界 下确界
14、x2,x3,x4 x1 x1 x4 x4x3,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）分别为
15、从X到Y存在入射的必要条件，条件1）、2）合起来是充要条件,习题4-2 (p156),(1) 题目省略解答：f要有f-1，f必须为双射，构造f = ,f2 = , f3 = f f2=fI=ff-1=, = ff f-1=,令g=f，g2=f2=I,习题4-2 (p156),(3) 要证明c，只需要证明a）、b），a）比较明显，按定义即可。对于b）用反证法，就可以得到；即若g不是入射的，那么存在不同的x1,x2，使得g(x1)=g(x2), 那么有f(g(x1)=f(g(x2)，说明f复合g的函数不是入射的，矛盾。由a）、b），并且双射的定义（既是满射，也是入射）就可以证明了。,习题4-4 (p164),(1) 构造双射函数，说明等势a) A = (0,1) ，B=(0,2)解答：a) y = 2x,习题4-4 (p170、173),(1) 都为0(1) p171例题1讲解一下。,
