离散数学第6章作业答案

《离散数学第6章作业答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章习题答案2.设P={<1,2>,<2,4>,<3,3>}，Q={<1,3>,<2,4>,<4,2>}找出PÈQ,PÇQ,dom(P),dom(Q),ran(P)及ran(Q)，并证明：dom(PÈQ)=dom(P)Èdom(Q)ran(PÇQ)Íran(P)Çran(Q)解PÈQ={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}，PÇQ={<2,4>}dom(P)={1,2,3}，dom(Q)={1,2,4}，ran(P)={2,3,4}，ran(Q)={2,3,4}。xÎdom(PÈQ)Û$y(ÎPÈQ)Û$y(<

2、x,y>ÎPÚÎQ)Û$y(ÎP)Ú$y(ÎQ)ÛxÎdom(P)ÚxÎdom(Q)ÛxÎdom(P)Èdom(Q)yÎran(PÇQ)Û$x(ÎPÇQ)Û$x(ÎPÙÎQ)Þ$x(ÎP)Ù$x(ÎQ)ÛyÎran(P)ÙyÎran(Q)ÛyÎran(P)Çran(Q)如上例，ran(PÇQ)={4}Ì{2,3,4}=ran(P)Çran(Q)3.若关系R和S自反的，对称的和传递的，证明：RÇS也是自反的，对称的和传递的。证明设R和S是集合A上的关系。因为R和S是自反

3、的，所以，对于A中的任意元素x，有ÎR和ÎS。因此ÎRÇS，即RÇS是自反的。因为R和S是对称的，所以对于任意，ÎRÇSÛÎRÙÎSÛÎRÙÎSÛÎRÇS因此，RÇS是对称的。因为R和S是传递的，所以对于任意和，ÎRÇSÙÎRÇSÛÎRÙÎSÙÎRÙÎSÛ(ÎRÙÎR)Ù(ÎSÙÎS)ÞÎRÙÎSÛÎ

4、RÇS因此，RÇS是传递的。5．设A={1,2,3}，A上的关系R1,R2,R3,R4,R5分别由图6.17给出，试问：R1,R2,R3,R4,R5各有哪些性质？解R1：自反、对称、反对称、传递。R2：对称。R3：反自反、反对称。R4：反自反、对称、反对称、传递。R5：自反、传递。8.设R1和R2是集合X={0,1,2,3}上的关系，而R1={

5、j=i+1或j=i/2}，R2={

6、i=j+2}求复合关系：(1)R1°R2(2)R2°R1(3)R1°R2°R1(4)并给出各复合关系的关系矩阵。解R1={<0,1>,<1,2>,<

7、2,3>,<0,0>,<2,1>}R2={<2,0>,<3,1>}R1°R2={<1,0>,<2,1>}R2°R1={<2,0>,<2,1>,<3,2>}R1°R2°R1={<1,1>,<1,0>,<2,2>}={<1,1>,<0,0>,<0,2>,<2,2>,<0,1>,<1,3>}13.求R2的自反、对称、传递闭包的关系图。R2及其自反、对称、传递闭包的关系图从左至右排列如下。14.令R1,R2是集合A上的二元关系，并设R1ÍR2，试证明下列关系式。(3)t(R1)Ít(R2)证明R1ÍR2Ít(R2)，t(R2)是包含R1的传递关系，由传递

8、闭包定义知道，t(R1)是包含R1的最小传递关系，所以，t(R1)Ít(R2)。15.设R1,R2是A上的二元关系，试证明(3)t(R1ÈR2)Êt(R1)Èt(R2)并用反例说明t(R1ÈR2)=t(R1)Èt(R2)不一定成立。证明因为R1ÍR1ÈR2，所以t(R1)Ít(R1ÈR2)。因为R2ÍR1ÈR2，所以t(R2)Ít(R1ÈR2)。因此，t(R1)Èt(R2)Ít(R1ÈR2)。令A={1,2}，R1={<1,2>}，R2={<2,1>}。因为R1是传递的，故t(R1)=R1。因为R2是传递的，故t(R2)=R2。因此，t(R1)È

9、t(R2)=R1ÈR2={<1,2>,<2,1>}，而t(R1ÈR2)={<1,2>,<2,1>,<1,1>,<2,2>}。18.对于下列集合上的整除关系，画出哈斯图。(1)A={1,2,3,4,6,8,12,24}(2)B={1,2,3,…,12}1213264824481263712510911(1){2,3,4}没有最大元、最小元，极大元为3和4，极小元为2和3，上界为12和24，上确界为12，下界为1，下确界为1。(2){2,3,4}没有最大元、最小元，极大元为3和4，极小元为2和3，上界为12，上确界为12，下界为1，下确界为1。20.

10、图6.21上给出了集合A={1,2,3,4}上的四个偏序关系，试画出它们的哈斯图。并判别哪一个是全序或良序关系。(a)去掉关系图中的自环