《第三章复习ppt课件.pptx》由会员分享，可在线阅读，更多相关《第三章复习ppt课件.pptx（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 集合与关系(1). 组织结构是明确的，但是内容比较多组织结构是明确的，但是内容比较多(2). 集合、直积、关系这些概念是简单的集合、直积、关系这些概念是简单的(3). 主要难点在于：复合、闭包和特殊关系主要难点在于：复合、闭包和特殊关系 （等价关系、相容关系、序关系）（等价关系、相容关系、序关系）习题习题3-1(p86)3-1(p86)（6）确定）确定下列集合的幂集下列集合的幂集a) a,a b) 1,2,3解答：解答：a) a,a, a,a, b) , 1,2,3这种题目通常通过这种题目通常通过|P(A)|=2|A|来计算幂来计算幂集中元素的个数，然后验证解答是否正集中元素的个数，然
2、后验证解答是否正确，抓住这个，我们可以计算难题确，抓住这个，我们可以计算难题习题习题3-1(p86)3-1(p86)（6）确定下列集合的幂集）确定下列集合的幂集d) P() e) P(P() (习题习题)解答：解答：d) 没有元素，所以没有元素，所以|P()|=20 =1， P() = ，P(P() = , (21)e) P(P(P() = P(P()=P(,) = , , (22)习题习题3-1(p86)3-1(p86)(7) 设设A=, B= P(P(A)。问：。问：a) 是否是否 B ？是否是否 B ?b) 是否是否 B ？是否？是否 B ？c) 是否是否 B ? 是否是否 B ? 解答
3、：由上题得到：解答：由上题得到： P(P() = , , 所以所以a) B ， B ；b) B , B ; c) B, B (拆括号法拆括号法) 习题习题3-2(p95)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 - B) - C = A - (BC)习题习题3-2(p95)3-2(p95)8. a) 已知已知AB = AC，是否必须，是否必须B=C ？ b) 已知已知
4、A B = A C，是否必须，是否必须B=C ？ c) 已知已知A B = A C，是否必须，是否必须B=C ？a). A=1,2 , B=3, C=2,3为反例为反例b). A=1,2, B=1, C=2为反例为反例c). A B = A C A A B =A A C B= C B=C习题习题3-2(p95)3-2(p95)a) A (B C) = (A B) (A C)左边左边= A (B-C)(C-B) = A(BC)(C B) = (ABC) (ABC)右边右边= (AB) (AC)(AC) (AB) = (ABA) (ABC) (ACA) (ACB) = (ABC) (ABC)习题习
5、题3-3(p100)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-4(p105)(3) 下列各式中哪些成立？哪些不成
6、立？为下列各式中哪些成立？哪些不成立？为什么？什么？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)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)3-4(p105)(4) 证明：若证明：若XX = YY，则，则X=Y证
7、证：（：（1） XX，则，则 YY，所以，所以xY，X Y；（2）反之，设）反之，设 YY,则则 XX，y X，Y X；所以所以X=Y 习题习题3-5(p110)3-5(p110)(5) 对式中所给出对式中所给出A上的二元关系，试给出上的二元关系，试给出关系图关系图 |0 x y 3，A=0,1,2,3,4R = , , , , , , , , , ,习题习题3-5(p110)3-5(p110)(6) 对对0,1,2,3,4,5,6上的二元关系，上的二元关系，|xy x是质数是质数，写出关系矩阵。，写出关系矩阵。解：解：R =, , , , , , , , ,R0111111001111111
8、11111M = 1111111000001111111110000000习题习题3-5(p110)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-6(p113)3-6(p113)(1) 分析集合分析集合A=1,2,3上的下述五个关系。上的下述五个关系。R=,S=,T=,判断判断A中的上述关系
9、是不是中的上述关系是不是a)自反的，自反的，b)对称对称的，的，c)可传递的，可传递的，d)反对称的。反对称的。解答：（解答：（1）R满足反对称性和传递性；满足反对称性和传递性；（2）S满足自反、对称和传递性满足自反、对称和传递性（3）T满足反对称性。满足反对称性。,破坏传递破坏传递习题习题3-6(p113)3-6(p113)(2)给定给定A=1,2,3,4,考虑考虑A上的关系上的关系R，若，若R = ,a) 在在AA的坐标图中标出的坐标图中标出R，并绘出它的，并绘出它的关系图；关系图；b)R是自反的，对称的，可传递的，是自反的，对称的，可传递的，反对称的吗？反对称的吗？解答：解答：1234可
10、传递的，可传递的，反对称反对称的的习题习题3-6(p114)3-6(p114)(6)设设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(p11
11、8)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)3-7(p119)(5) R是是A上的一个二元关系，如果上的一个二元关系，如果R是自
12、反的，是自反的，则则Rc一定是自反的吗？如果一定是自反的吗？如果R是对称的，则是对称的，则Rc一定是对称的吗？如果一定是对称的吗？如果R是传递的，则是传递的，则Rc一定一定是传递的吗？是传递的吗？解答解答：（：（1）R自反，自反， R，所以，所以 Rc，Rc自反；（自反；（2）R对称，对称，Rc=R，也对称；，也对称；（3）, R , Rc, 因此满足传递性因此满足传递性习题习题3-8(p127)3-8(p127)(2)设集合设集合A=a,b,c,d, A上的关系上的关系R=,a) 用矩阵运算和作图方法求出用矩阵运算和作图方法求出R的自反闭包、的自反闭包、对称闭包和传递闭包。对称闭包和传递闭包
13、。b) 用用Warshall算法求出算法求出R的传递闭包的传递闭包解答：解答：0100101000010000M图略，直接解说图略，直接解说传递性，要解说传递性，要解说一步边、两步边、一步边、两步边、三步边、四步边三步边、四步边abcd习题习题3-8(p1273-8(p127) )矩阵运算，矩阵运算，(加法为析取加法为析取)自反自反M1 = M+Ix, 对称对称M2=M+Mc，传递传递M3=M1+M12+M13+M14b)0100010011101111101011101110111100010001000100010000000000000000习题习题3-8(p1273-8(p127) )
14、(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)3-9(p130)(4)题略。题略。证明证明：（：（1）Ai不包含于不包含于Aj，因此，因此Ai不可能为不可能为空集；（空集；（2）有）有Ai Aj=，这是因为若有，这是因为若有Ai Aj不为空
15、，设共同元素有不为空，设共同元素有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
16、A2 Ak = A习题习题3-10(p134)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)3-10(p135)(6) 设设R是集合是集合A上的对称和传递关系，证上的对称和传递关系，证明如果对于明如果对于A中的每一个元素中的每一个元素a，在，在A中同时
17、中同时也存在一个也存在一个b，使，使在在R中，则中，则R是一个是一个等价关系。等价关系。证明：只需证明证明：只需证明R是自反的。对于任意的是自反的。对于任意的a，存在存在b，有，有 R，由对称性，由对称性 R；由传递性，由传递性， R，因此，因此R是自反的，是自反的，所以所以R是一个等价关系。是一个等价关系。习题习题3-11(p139)3-11(p139)(1) 设设R是是X上的二元关系，试证明上的二元关系，试证明r=Ix R Rc是是X上的相容关系。上的相容关系。证明证明：（：（1） Ix，因此，因此 r，r自反；（自反；（2） R , 则则 Rc，因此因此 r并且并且 r, r是对称的。是
18、对称的。因此因此r是相容关系。是相容关系。习题习题3-11(p139)3-11(p139)(2) 题目省略。题目省略。解答：完全覆盖为解答：完全覆盖为(最大相容类集合最大相容类集合)：x1,x2,x3,x1,x3,x6x3,x5,x6,x3,x4,x5x3x5x4x2x6x1习题习题3-11(p139)3-11(p139)(4) 设设C=A1,A2,An为集合为集合A的覆盖，试的覆盖，试由此覆盖确定由此覆盖确定A上的一个相容关系。并说明上的一个相容关系。并说明在什么条件下，此相容关系为等价关系。在什么条件下，此相容关系为等价关系。R = A1A1 A2A2 AnAn当当R满足传递性，此相容关系
19、为等价关系，满足传递性，此相容关系为等价关系，一般的，只要一般的，只要C不仅是一个覆盖，还是一个不仅是一个覆盖，还是一个划分的时候，划分的时候，R就能满足传递性，就能满足传递性，R就是等就是等价关系。价关系。习题习题3-12(p145)3-12(p145)(1) 设集合为设集合为3,5,15, 1,2,3,6,12, 3,9,27,54，偏序关系为整除，画出这些集合，偏序关系为整除，画出这些集合的偏序关系图，并指出哪些是全序关系。的偏序关系图，并指出哪些是全序关系。第第3个图代表全序个图代表全序习题习题3-12(p146)3-12(p146)(6)题见书本题见书本 极大元极大元 最大元最大元
20、极小元极小元 最小元最小元 P x1 x1 x4、x5 无无 上界上界 上确界上确界 下界下界 下确界下确界x2,x3,x4 x1 x1 x4 x4x3,x4,x5 x1,x3 x3 无无 无无 x1,x2,x3 x1 x1 x4 x4习题习题3-12(p146)3-12(p146)(7)题目省略题目省略画哈斯图，注意先看出射点和入射点，全画哈斯图，注意先看出射点和入射点，全序和良序只为（序和良序只为（c）图）图习题习题4-1 (p151)4-1 (p151)(1) 题目省略题目省略解答：解答：(a)都不是；都不是；(b)都不是都不是; (c)是满射是满射(d)都不是都不是, (i=-1和和i
21、=1,值相同值相同)(e) 是双射是双射习题习题4-1 (p151)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 4-2 ( (p156)p156)(1) 题目省略题目省略解答：解答：f要有要有f-1，f
22、必须为双射，构造必须为双射，构造f = ,f2 = , f3 = f f2=fI=ff-1=, = ff f-1=,令令g=f，g2=f2=I习题习题4-2 (p156)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 4-4 ( (p164)p164)(1) 构造构造双射双射函数，说明等势函数，说明等势a) A = (0,1) ，B=(0,2)解答：解答：a) y = 2x习题习题4-4 (4-4 (p170p170、173)173)(1) 都为都为?0(1) p171例题例题1讲解一下。讲解一下。