離散數(shù)學-尹寶林版-第6章作業(yè)答案

第六章習題答案2.設P={<1,2>,<2,4>,<3,3>}，Q={<1,3>,<2,4>,<4,2>}找出PQ,PQ,dom(P),dom(Q),ran(P)及ran(Q)，并證明：dom(PQ)=dom(P)dom(Q)ran(PQ)ran(P)ran(Q)解PQ={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}，PQ={<2,4>}dom(P)={1,2,3}，dom(Q)={1,2,4}，ran(P)={2,3,4}，ran(Q)={2,3,4}。 xdom(PQ) y(<x,y>?PQ) y(<x,y>?P<x,y>?Q) y(<x,y>?P)y(<x,y>?Q) xdom(P)xdom(Q) xdom(P)dom(Q) yran(PQ) x(<x,y>?PQ) x(<x,y>?P<x,y>?Q) x(<x,y>?P)x(<x,y>?Q) yran(P)yran(Q) yran(P)ran(Q)如上例，ran(PQ)={4}{2,3,4}=ran(P)ran(Q)3.若關系R和S自反的，對稱的和傳遞的，證明：R?S也是自反的，對稱的和傳遞的。證明設R和S是集合A上的關系。因為R和S是自反的，所以，對于A中的任意元素x，有<x,x>?R和<x,x>?S。因此<x,x>?R?S，即R?S是自反的。因為R和S是對稱的，所以對于任意<x,y>，<x,y>?R?S?<x,y>?Rù<x,y>?S?<y,x>?Rù<y,x>?S?<y,x>?R?S因此，R?S是對稱的。因為R和S是傳遞的，所以對于任意<x,y>和<y,z>，<x,y>?R?Sù<y,z>?R?S?<x,y>?Rù<x,y>?Sù<y,z>?Rù<y,z>?S?(<x,y>?Rù<y,z>?R)ù(<x,y>?Sù<y,z>?S)T<x,z>?Rù<x,z>?S?<x,z>?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={<i,j>|j=i+1或j=i/2}，R2={<i,j>|i=j+2}求復合關系： (1)R1R2 (2)R2R1 (3)R1R2R1 (4)并給出各復合關系的關系矩陣。解R1={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>} R2={<2,0>,<3,1>} R1R2={<1,0>,<2,1>} R2R1={<2,0>,<2,1>,<3,2>} R1R2R1={<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上的二元關系，并設R1R2，試證明下列關系式。(3)t(R1)t(R2)證明R1R2t(R2)，t(R2)是包含R1的傳遞關系，由傳遞閉包定義知道，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)不一定成立。證明因為R1R1èR2，所以t(R1)t(R1èR2)。因為R2R1è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)è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}121213264824481263712510911(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.圖6.21上給出了集合A={1,2,3,4}上的四個偏序關系，試畫出它們的哈斯圖。并判別哪一個是全序或良序關系。(a)去掉關系圖中的自環(huán)，沒有進入頂點4的有向邊，將4畫在最下面，去掉從4發(fā)出的有向邊，沒有進入頂點1的有向邊，將1畫在第二層，去掉從1發(fā)出的有向邊，剩下兩個孤立點2和3，將2和3畫在最上面。連接4和1，1和2，1和3，得到哈斯圖。2244224444111122333323.令T是笛卡爾平面RR上的關系，T的定義如下：<x1,y1>T<x2,y2>當且僅當x1x2y1y2請據(jù)此判斷下面哪個斷言是真哪個是假，如果斷言是假，說明理由。(1)T是偏序的。 (2)T是線序的。 (3)T是良序的。答T是偏序，不是線序，更不是良序。<0,1>和<1,0>不可比。25.正整數(shù)集合上的關系R被定義為niRnj?ni/nj能夠被表達成2m的指數(shù)形式，其中m是任意整數(shù)。(1)證明關系R是等價關系。(2)等價類是什么？解(1)任取正整數(shù)x，x/x=1=20，所以xRx，R是自反的。 若xRy，則有整數(shù)m使得x/y=2m，y/x=2-m，-m也是整數(shù)，所以yRx，R是對稱的。 若xRy且yRz，則有整數(shù)m,n使得x/y=2m，y/z=2n， x/z=(x/y)*(y/z)=2m*2n=2m+n m+n也是整數(shù)，所以xRz，R是傳遞的。R是等價關系。 (2)對于每個正奇數(shù)k，{x|$m(m?Nùx=k′2m)}是等價類。[1]R={1,2,4,8,16,…}[3]R={3,6,12,24,48,…}…26.設R表示正整數(shù)的有序偶集合上的關系，并且<x,y>R<u,v>當且僅當xv=yu，證明R是等價關系。證明任取正整數(shù)的有序偶<x,y>，因為xy=yx，

所以<x,y>R<x,y>，R是自反的。 若<x,y>R<u,v>，則xv=yu，故uy=vx，

所以<u,v>R<x,y>，R是對稱的。 若<x,y>R<u,v>且<u,v>R<w,t>，

則xv=yu且ut=vw，因而xvut=yuvw，

故xt=yw，<x,y>R<w,t>，R是傳遞的。

R是等價關系。27.設A={a,b,c,d}，而且p1,