第三章复习-(2)

第三章集合与关系(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(Ø))={Ø,{Ø}}(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-(B∪C)证明：x∈(A-B)–Cx∈(A-B)∧x∉Cx∈A∧x∉B∧x∉Cx∈A∧x∉(B∪C)x∈A-(B∪C)所以(A-B)-C=A-(B∪C)习题3-2(p95)8.a)已知A∪B=A∪C，是否必须B=C？b)已知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)a)A∩(B⊕C)=(A∩B)⊕(A∩C)左边=A∩((B-C)∪(C-B))=A∩((B∩~C)∪(C∩~B))=(A∩B∩~C)∪(A∩~B∩C)右边=((A∩B)∩~(A∩C))∪((A∩C)∩~(A∩B))=(A∩B∩~A)∪(A∩B∩~C)∪(A∩C∩~A)∪(A∩C∩~B)=(A∩B∩~C)∪(A∩~B∩C)习题3-3(p100)(5)A1:学数学，A2：学物理，A3：学生物|A1|=67,|A2|=47,|A3|=95|A1∩A3|=26,|A1∩A2|=28,|A2∩A3|=27N=200，|~(A1∪A2∪A3)|=50又|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A3|-|A1∩A2|-|A2∩A3|+|A1∩A2∩A3|所以200-50=67+47+95-26-28-27+|A1∩A2∩A3|，因此|A1∩A2∩A3|=22习题3-4(p105)(3)下列各式中哪些成立？哪些不成立？为什么？b)(A–B)×(C–D)=(A×C)–(B×D)d)(A–B)×C=(A×C)–(B×C)b)A={1,2},B={1},C={1,2},D={1}(A–B)×(C–D)={2,2}(A×C)–(B×D)={1,2,2,1,2,2}习题3-4(p105)d)x,y∈(A–B)×C(x∈A∧x∉B∧y∈C)∨(x∈A∧y∉C∧y∈C)(x∈A∧y∈C)∧(x∉B∧y∉C)x,y∈A×C∧x,y∉B×Cx,y∈(A×C)–(B×C)所以(A–B)×C=(A×C)–(B×C)习题3-4(p105)(4)证明：若X×X=Y×Y，则X=Y证：（1）x,x∈X×X，则x,x∈Y×Y，所以x∈Y，X⊆Y；（2）反之，设y,y∈Y×Y,则y,y∈X×X，y∈X，Y⊆X；所以X=Y习题3-5(p110)(5)对式中所给出A上的二元关系，试给出关系图{x,y|0≤x∧y≤3}，A={0,1,2,3,4}R={0,0,0,1,0,2,0,3,1,0,1,1,1,2,1,3,2,0,2,1,2,2,2,3,3,0,3,1,3,2,3,3,4,0,4,1,4,2,4,3}习题3-5(p110)(6)对{0,1,2,3,4,5,6}上的二元关系，{x,y|xy∨x是质数}，写出关系矩阵。解：R={0,1,0,2,0,3,0,4,0,5,0,6,1,2,1,3,1,4,1,5,1,6,2,3,2,4,2,5,2,6,3,4,3,5,3,6,4,5,4,6,5,6,2,0,2,1,2,2,3,0,3,1,3,2,3,3,5,0,5,1,5,2,5,3,5,4,5,5}R011111100111111111111M=1111111000001111111110000000习题3-5(p110)(7)设P={1,2,2,4,3,3}和Q={1,3,2,4,4,2}找出P∪Q,P∩Q,domP,domQranP,ranQ,dom(P∩Q),ran(P∩Q)解：P∪Q={1,2,1,3,2,4,3,3,4,2}P∩Q={2,4},domP={1,2,3},domQ={1,2,4}ranP={2,3,4},ranQ={2,3,4}dom(P∩Q)={2},ran(P∩Q)={4}习题3-6(p113)(1)分析集合A={1,2,3}上的下述五个关系。R={1,1,1,2,1,3,3,3}S={1,1,1,2,2,1,2,2,3,3}T={1,1,1,2,2,2,2,3}判断A中的上述关系是不是a)自反的，b)对称的，c)可传递的，d)反对称的。解答：（1）R满足反对称性和传递性；（2）S满足自反、对称和传递性（3）T满足反对称性。1,2,2,3破坏传递习题3-6(p113)(2)给定A={1,2,3,4},考虑A上的关系R，若R={1,3,1,4,2,3,2,4,3,4}a)在A×A的坐标图中标出R，并绘出它的关系图；b)R是自反的，对称的，可传递的，反对称的吗？解答：1234可传递的，反对称的习题3-6(p114)(6)设R是集合X上的一个自反关系。求证：R是对称和传递的，当且仅当a,b和a,c在R之中则有b,c在R之中。证明：（1）若R是对称的，则由a,c和c,a在R中，因此c,a,a,b在R中，R是传递的，因此c,b在R中，由对称，b,c在R中；（2）a,b,c任意，a取c，c,b、c,c和b,c在R中，故R对称；因此由a,b在R中知道b,a在R中，b,a,a,c,b,c在R中，推出R传递。习题3-7(p118)(1)设R1和R2是A上的任意关系，说明以下命题的真假，并予以证明a)若R1和R2是自反的,则R1○R2也是自反的c)若R1和R2是对称的,则R1○R2也是对称的解答：a）成立，在R1中有x,x∈R1，在R2中有x,x∈R2,因此x,x∈R1○R2，有自反性。c）不成立，设R1={1,1},R2={2,2,2,1},则R1○R2={1,2},无对称性。习题3-7(p119)(5)R是A上的一个二元关系，如果R是自反的，则Rc一定是自反的吗？如果R是对称的，则Rc一定是对称的吗？如果R是传递的，则Rc一定是传递的吗？解答：（1）R自反，x,x∈R，所以x,x∈Rc，Rc自反；（2）R对称，Rc=R，也对称；（3）x,y,y,z,x,z∈Ry,x,z,y,z,x∈Rc,因此满足传递性习题3-8(p127)(2)设集合A={a,b,c,d},A上的关系R={a,b,b,a,b,c,c,d}a)用矩阵运算和作图方法求出R的自反闭包、对称闭包和传递闭包。b)用Warshall算法求出R的传递闭包解答：0100101000010000M图略，直接解说传递性，要解说一步边、两步边、三步边、四步边abcd习题3-8(p127)矩阵运算，(加法为析取)自反M1=M+Ix,对称M2=M+Mc，传递M3=M1+M1^2+M1^3+M1^4b)0100010011101111101011101110111100010001000100010000000000000000习题3-8(p127)(7)设R1和R2是A上的关系，证明：a)r(R1∪R2)=r(R1)∪r(R2)b)s(R1∪R2)=s(R1)∪s(R2)解答：a）左边=R1∪R2∪I，右边=R1∪I∪R2∪I=R1∪R2∪Ib）左边=R1∪R2∪(R1∪R2)c=R1∪R2∪R1c∪R2c右边=R1∪R1c∪R2∪R2c，两边相等习题3-9(p130)(4)题略。证明：（1）Ai不包含于Aj，因此Ai不可能为空集；（2）有Ai∩Aj=Ø，这是因为若有Ai∩Aj不为空，设共同元素有x，因此Ai中的元素ai和Aj中的元素aj，由题意有x,ai∈R,x,aj∈R，由对称和传递，可以得到ai,aj∈R,因此ai，aj在一个集合中，因此Ai=Aj，这和Ai、Aj互不包含相排斥。（3）a∈A，由自反性，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,2}^2∪{3}^2∪{4,5}^2={1,1,1,2,2,1,2,2,3,3,4,4,4,5,5,4,5,5}关系图分为三部分，为两个完全2边形和一个完全0边形（用画笔画一下）习题3-10(p135)(6)设R是集合A上的对称和传递关系，证明如果对于A中的每一个元素a，在A中同时也存在一个b，使a,b在R中，则R是一个等价关系。证明：只需证明R是自反的。对于任意的a，存在b，有a,b∈R，由对称性b,a∈R；由传递性，a,a∈R，因此R是自反的，所以R是一个等价关系。习题3-11(p139)(1)设R是X上的二元关系，试证明r=Ix∪R∪Rc是X上的相容关系。证明：（1）x,x∈Ix，因此x,x∈r，r自反；（2）x,y∈R,则y,x∈Rc，因此x,y∈r并且y,x∈r,r是对称的。因此r是相容关系。习题3-11(p139)(2)题目省略。解答：完全覆盖为(最大相容类集合)：{{x1,x2,x3},{x1,x3,x6}{x3,x5,x6},{x3,x4,x5}}x3x5x4x2x6x1习题3-11(p139)(4)设C={A1,A2,…,An}为集合A的覆盖，试由此覆盖确定A上的一个相容关系。并说明在什么条件下，此相容关系为等价关系。R=A1×A1∪A2×A2…∪An×An当R满足传递