离散数学第七章

第七章部分课后习题参考答案7.列出集合A={2,3,4}上的恒等关系IA,全域关系EA,小于或等于关系LA,整除关系DA.解：IA={2，2,3,3,4,4}EA={2,2,2,3,2,4,3,4,4,4,3,2,3,3,4,2,4,3}LA={2,2,2,3,2,4,3,3,3,4,4,4}DA={2,4}13.设A={1,2,2,4,3,3}B={1,3,2,4,4,2}求AB,AB,domA,domB,dom(AB),ranA,ranB,ran(AB),fld(A-B).解：AB={1,2,2,4,3,3,1,3,4,2}AB={2,4}domA={1,2,3}domB={1,2,4}dom(A∨B)={1,2,3,4}ranA={2,3,4}ranB={2,3,4}ran(AB)={4}fldR=domRranRA-B={1,2,3,3}，fld(A-B)={1,2,3}14.设R={0,10,2,0,3,1,2,1,3,2,3}求RR,R-1,R{0,1,},R[{1,2}]解：RR={0,2,0,3,1,3}R-1,={1,0,2,0,3,0,2,1,3,1,3,2}R{0,1}={0,1,0,2,0,3,1,2,1,3}R[{1,2}]=ran(R{1,2})={2,3}16．设A={a,b,c,d}，1R，2R为A上的关系，其中1R=,,,,,aaabbd2,,,,,,,Radbcbdcb求23122112,,,RRRRRR。解:R1R2={a,d,a,c,a,d}R2R1={c,d}R12=R1R1={a,a,a,b,a,d}1243R22=R2R2={b,b,c,c,c,d}R23=R2R22={b,c,c,b,b,d}22、给定1,2,3,4A，A上的关系1,3,1,4,2,3,2,4,3,4R，试（1）画出R的关系图；（2）说明R的性质。解：（1）●●●●（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。26设1,2,3,4,5,6A，R为A上的关系，R的关系图如图7.13所示：（1）求23,RR的集合表达式；（2）求r(R),s(R),t(R)的集合表达式。解：（1）由R的关系图可得1,5,2,5,3,1,3,3,4,5R所以23,1,3,3,3,5RRR，323,1,3,3,3,5RRR，可得3,1,3,3,3,5,n=2nR当；（2）Ar(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6，1()R1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4sRR232()RR...R1,5,2,5,3,1,3,3,4,5,3,5tRRR36．设A={1，2，3，4}，在AA上定义二元关系R，u,v,x,yAA，〈u,vRx,yu+y=x+v.(1)证明R是AA上的等价关系.(2)确定由R引起的对AA的划分.（1）证明：∵任意u,vA,有u+v=u+v,∴所以u,v,u,vR,既R是自反的任意的u,v,x,y∈A×A如果u,vRx,y，那么u-v=x-y∴x-y=u-v∴x,yRu,v∴R是对称的任意的u,v,x,y,a,b∈A×A若u,vRx,y,x,yRa,b则u-v=x-y,x-y=a-b∴u-v=a-b∴u,vRa,b∴R是传递的∴R是A×A上的等价关系(2)∏={{1,1,2,2,3,3,4,4},{2,1,3,2,4,3},{3,1,4,2},{4,1},{1,2,2,3,3,4},{1,3,2,4},{1,4}}41.设A={1，2，3，4}，R为AA上的二元关系,〈a，b〉，〈c，d〉AA,〈a，b〉R〈c，d〉a+b=c+d(1)证明R为等价关系.(2)求R导出的划分.(1)证明：a，b〉AAa+b=a+b∴a,bRa,b∴R是自反的任意的a,b,c,d∈A×A设a,bRc,d，则a+b=c+d∴c+d=a+b∴c,dRa,b∴R是对称的任意的a,b,c,d,x,y∈A×A若a,bRc,d,c,dRx,y则a+b=c+d,c+d=x+y∴a+b=x+y∴a,bRx,y∴R是传递的∴R是A×A上的等价关系(2)∏={{1,1},{1,2,2,1},{1,3,2,2,3,1},{1,4,4,1,2,3,3,2},{2,4,4,2,3,3},{3,4,4,3},{4,4}}43.对于下列集合与整除关系画出哈斯图:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12}解:1234681224123456789101112(1)(2)45.下图是两个偏序集A,R的哈斯图.分别写出集合A和偏序关系R的集合表达式.abcdefgabcdefg(a)(b)解:(a)A={a,b,c,d,e,f,g}R={a,b,a,c,a,d,a,e,a,f,a,g,b,d,b,e,c,f,c,g}AI(b)A={a,b,c,d,e,f,g}R={a,b,a,c,a,d,a,e,a,f,d,f,e,f}AI46.分别画出下列各偏序集A,R的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e}R={a,d,a,c,a,b,a,e,b,e,c,e,d,e}IA.(2)A={a,b,c,d,e},R={c,d}IA.解:abcdeabcde(1)(2)项目(1)(2)极大元:ea,b,d,e极小元:aa,b,c,e最大元:e无最小元:a无48、设,B,SAR和为偏序集，在集合AB上定义关系T如下：112211221212,,,AB,,,abababTabaRabSb证明T为AB上的偏序关系。证明：（1）自反性：1111111111112212121111,ABRRSbSbRbSb,,,,TabaaaaabTabaRabSbabTab任取，则：为偏序关系，具有自反性，为偏序关系，具有自反性，又，，故满足自反性（2）反对称性：112211222211121221211221121221121122,,,AB,,,,RSbb,,TabababTababTabaRabSbaRabSbaRaaRaaabSbbSbabab任取，若且，则有：（1）（2），又为偏序关系，具有反对称性，所以，又为偏序关系，具有反对称性，所以，故满足反对称性（3）传递性：11223311222233112212122233232312231312231313131133,,,,AB,,,,,,,,,R,SbSbbSb,,TababababTababTababTabaRabSbabTabaRabSbaRaaRaaRabSbbSbaRaabTab任取，，若且，则有：又为偏序关系，具有传递性，所以又为偏序关系，具有传递性，所以，故满足传递性。综合（1）（2）（3）知T满足自反性、反对称性和传递性，故T为AB上的偏序关系。