《離散數(shù)學課件第四章二元關系習題.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學課件第四章二元關系習題.ppt（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第四章 二元關系習題,,練習,、(79頁第題) R1,R2是集合中的關系，試證明： (1)r(R1R2)=r(R1) r(R2) (2)s(R1R2)=s(R1) s(R2) (3)t(R1R2)t(R1) t(R2)（書上是等號） 證明(1)左邊=r(R1R2) =R1R2 Ix 右邊= r(R1) r(R2) =R1 Ix R2 Ix =R1R2 Ix (1)式得證。,2,,證(2)左邊=s(R1R2) =(R1R2) (R1 R2) = R1R2 R1 R2 = (R1 R1) (R2 R2) =s(R1) s(R2) (2)得證。,3,,證(3)t(R1R2)t(R1) t(R2
2、) t(R1R2)=(R1R2) (R1R2)2 (R1R2)n 而(R1R2)2= (R1R2)o (R1R2) =((R1R2)oR1) ((R1R2)oR2) = R12R2oR1R1oR2R22R12 R22 (R1R2)n R1n R2n 于是有(R1R2) (R1R2)2 (R1R2)n R1 R12 R1n R2 R22,4,, R22 R2n 即t(R1R2)t(R1) t(R2) (3)得證 、(85頁第題) 設1,2, ,n是集合的劃分，試證明：1，2, ,n 是集合 的劃分 證明：因為1 2 ,5,,n 于是有1BB 2 B B
3、 n B B 并且1B2B n B =(1 2 n) B = AB. 對任何(iB) (jB)=(ij) B=B= (ij),6,,3.(85頁第題） 把n個元素的集合劃分為兩個類，共有多少種不同的分法？ 解：個元素的有種分法： 即1a1, a2,即2(2-1)-1 3個元素的有種分法： 即1a1, a2 ,a3 2a2, a1 ,a3 3a3, a1 ,a2即2(-1)-1,7,,4個元素的有種： 即1a1, a2 ,a3 ,a4 2a2, a1 ,a3 ,a4 3a3, a1 ,a2, a4 4a4, a1 ,a2 ,a3 5a1,a2, a3
4、,a4 6a1,a3, a2, a4 7a1,a4, a2 ,a3 即2(4-1)-1 一般具有n個元素的集合分成兩堆的分法有2(n-1)-1種,8,,4.(85頁第題) 在等價關系圖中，應如何識別等價類？ 解：關系圖中如果有孤立的結(jié)點，則它是一個等價類； 都不與其它結(jié)點相關聯(lián)的相互聯(lián)結(jié)的兩個結(jié)點構(gòu)成一個等價類； 都不與其它結(jié)點相關聯(lián)的相互聯(lián)結(jié)的三個結(jié)點構(gòu)成一個等價類； 都不與其它結(jié)點相關聯(lián)對角線相關聯(lián)的四個結(jié)點構(gòu)成一個等價類,9,,都不與其它結(jié)點相關聯(lián)的正五角星構(gòu)成一個等價類； 都不與其它結(jié)點相關聯(lián)的正六角星構(gòu)成一個等價類；,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
5、,,,,10,,上述圖例中，省略了各結(jié)點上的自環(huán)，用一條無向邊代替一對方向相反的有向邊 5.(85頁第題) 設是集合中的關系，對于所有的xi,xj和xk屬于，如果xixj和xjxk就有xkxi 則稱是循環(huán)關系，試證明當且僅當是一個等價關系，才是自反的和循環(huán)的 證明：充分性設是等價關系，來證明是循環(huán)的(自反性是明顯的),11,,對任何xi,xj和xk屬于和xixj ，xjxk有 xixk及xkxi(由的可傳遞性和對稱性得) 即是循環(huán)的 必要性：設是自反的和循環(huán)的來證是個等價關系實際上只要證是對稱的和可傳遞的即可 對任何xi,xj和xk屬于和xixj ，xjxk有 xkxi及xixi于是有xixk
6、即是對稱的和可傳遞的 綜上問題得證,12,,6.(86頁第題) 設1和R2是集合中的等價關系，試證明：當且僅當1中的每一個等價類都包含于2中的某一個等價類中，才有R1 R2 證明：設1和R2造成的劃分分別是 1=c11 ,c12,, c1n 2=c21 ,c22,, c2m 對任意的c1i1(i=1,...,n),在2中都存在 某一個c2j(j=1,2,...,m)并且c1ic2j,13,,對于任何x,yc1i則x,yc2j 于是有1則R2 即1R2充分性得證 再證必要性： 設1R2，于是對任意1(等價于x,y應屬于1造成的劃分1 的某一個類c1i中,i=1,2,...n) 則R2，(等價于x
7、,y一定屬于2造成的劃分2 的某一個類c2j中,j=1,2,...m) 必要性得證,14,,.(86頁第題) 設1和R2是集合中的等價關系，并分別有秩r1和r2，試證明：1R2也是集合X中的等價關系，它的秩至多是r1r2。而 1R2不一定是集合X中的等價關系 證明：首先證明1R2是等價關系 1)(x)(xX R1R2) =(x)(xX(R1R2)) =(x)((xXR1)(xX R2)),15,,=(x)(xXR1) (x)(xXR2) =T T=T利用全稱量詞對與的可分配性 自反性得證 再來證1R2是對稱的 用反證法，假設1R2是不對稱的，即 (x)(y)(x,yX1R2 1R2 ) =(x
8、)(y)(x,yX1 2 (12)),16,,=(x)(y)((x,yX1 2 1)(x,yX1 R22)) =(x)(y)(x,yX1 2 1) (x)(y) (x,yX1 R22)(利用存在量詞對的可分配性) =F F=F即假設不成立，對稱性得證,17,,使用反證法同樣可以證明1R2 是可傳遞的即它是等價關系 再來證1R2 至多有r1r2個類 因為對任意的x,yX和R1 R2x,y C1i x,y C2j 其中i=1,2,,r1, j=1,2,,r2至多為r1r2 證畢,18,,.(89頁第題) 給定集合=A1 ,A2,, An的覆蓋，如何確定此覆蓋的相容關系。 解：其對應的相
9、容關系為： R= A1x A1 A2x A2 Anx An 9.(90頁第題) 設集合=1,2,3,求出中的等價關系R1 R2,使得R1OR2也是個等價關系 解：令R1是任何等價關系, R2是個恒等關系即可,19,,例如令R1= , , , , , , , , R2=Ix R1oR2為所求 10.(95頁第題) 如果是集合中的偏序關系,且X,試證明R(AXA)是A中的偏序關系 證明：即證R(AXA)是自反的，反對稱的和可傳遞的。,20,,)證自反性，即證對(x)(xA R(AXA))為真，而 (x)(xA R(AXA)) (x)(xA R(AXA)) (x)(xA( R (AXA))) (x
10、)((xAR) (xA(AXA))) (x)(xAR) (x)(xA(AXA)) （全稱量詞對的可分配性） (x)(xAR) (x)(xA(AXA)) TT=T自反性得證,21,,)證反對稱性即證對 (x)(y)(x,yAR(AXA) R(AXA) x=y)為真 上式= (x)(y)((x,yAR(AXA) R(AXA))x=y) =(x)(y)((x,yA)R (AXA)R (AXA)x=y) =(x)(y)(( (x,yA)R Rx=y)((x,yA)(AXA) (AXA)x=y)) 而上式可由(x)(y)(( (x,yA)R Rx=y) (x)(y)(((x,yA)(AXA) (AXA)x=y))邏輯地推出,22,,顯然此式為真(已知條件)，于是(x)(y)(x,yAR(AXA) R(AXA) x=y)為真 )再證R(AXA)是可傳遞的，即證 (x)(y)(z)((x,y,zAR(AXA)R(AXA) R(AXA))為真,而上式 = (x)(y)(z)((x,y,zA)R (AXA)R (AXA)(R(AXA))),23,,對上式使用對的分配律，再利用全稱量詞對的可分配性及已知條件，問題可得證,24,
離散數(shù)學課件第四章二元關系習題.ppt
