離散數(shù)學(xué)課后答案(四)

1、第六章習(xí)題答案2. 設(shè)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

2、, 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 (< x, y > Î P È Q)Û$y (< x, y > Î P Ú < x, y > Î Q)Û$y (< x, y > Î P) 

3、8; $y (< x, y > Î Q)Û xÎ dom(P) Ú xÎ dom(Q)Û xÎ dom(P) È dom(Q)yÎ ran(PÇ Q)Û$x (< x, y > Î PÇQ)Û$x (< x, y > Î P Ù < x, y > Î Q)Þ$x (< x, y > Î P) Ù $x (< x, y > &#

4、206; Q)Û yÎ ran(P) Ù yÎ ran(Q)Û yÎ ran(P) Ç ran(Q)如上例，ran(PÇ Q) = 4 Ì 2, 3, 4 = ran(P) Ç ran(Q)3. 若關(guān)系R和S自反的，對(duì)稱的和傳遞的，證明：RÇS也是自反的，對(duì)稱的和傳遞的。證明 設(shè)R和S是集合A上的關(guān)系。因?yàn)镽和S是自反的，所以，對(duì)于A中的任意元素x，有< x, x >ÎR和< x, x >ÎS。因此< x, x >ÎR&

5、#199;S，即RÇS是自反的。因?yàn)镽和S是對(duì)稱的，所以對(duì)于任意< x, y >， < x, y >ÎRÇSÛ < x, y >ÎR Ù < x, y >ÎSÛ < y, x >ÎR Ù < y, x >ÎSÛ < y, x >ÎRÇS因此，RÇS是對(duì)稱的。因?yàn)镽和S是傳遞的，所以對(duì)于任意< x, y >和< y, z >，< x,

6、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)Þ

7、; < x, z >ÎR Ù < x, z >Î SÛ < x, z >ÎRÇS因此，RÇS是傳遞的。5設(shè)A = 1, 2, 3，A上的關(guān)系R1, R2, R3, R4, R5分別由圖6.17給出，試問：R1, R2, R3, R4, R5各有哪些性質(zhì)？解R1：自反、對(duì)稱、反對(duì)稱、傳遞。R2：對(duì)稱。R3：反自反、反對(duì)稱。R4：反自反、對(duì)稱、反對(duì)稱、傳遞。R5：自反、傳遞。8. 設(shè)R1和R2是集合X = 0, 1, 2, 3上的關(guān)系，而R1 = < i, j > | j = i

8、+ 1或j = i /2，R2 = < i, j > | i = j + 2求復(fù)合關(guān)系：(1) R1 ° R2(2) R2 ° R1(3) R1 ° R2 ° R1(4)并給出各復(fù)合關(guān)系的關(guān)系矩陣。解 R1 = < 0, 1>, < 1, 2 >, < 2, 3 >, < 0, 0 >, < 2, 1 >R2 = < 2, 0 >, < 3, 1 >R1 ° R2 = < 1, 0 >, < 2, 1 >R2 ° R

9、1 = < 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的自反、對(duì)稱、傳遞閉包的關(guān)系圖。R2及其自反、對(duì)稱、傳遞閉包的關(guān)系圖從左至右排列如下。14. 令R1, R2是集合A上的二元關(guān)系，并設(shè)R1 Í

10、R2，試證明下列關(guān)系式。(3) t (R1) Í t (R2)證明 R1 Í R2 Í t (R2)，t(R2)是包含R1的傳遞關(guān)系，由傳遞閉包定義知道，t(R1)是包含R1的最小傳遞關(guān)系，所以，t(R1)Í t(R2)。15. 設(shè)R1, R2是A上的二元關(guān)系，試證明(3) t (R1 È R2) Ê t (R1) È t (R2)并用反例說明t (R1ÈR2) = t (R1) È t (R2) 不一定成立。證明 因?yàn)镽1 Í R1 ÈR2 ，所以t(R1)Í t(R1&#

11、200;R2)。因?yàn)镽2 Í R1ÈR2 ，所以t(R2)Í t(R1ÈR2)。因此，t (R1) È t (R2) Í t (R1ÈR2)。令A(yù) =1, 2，R1 =< 1, 2 >，R2 =< 2, 1 >。因?yàn)镽1是傳遞的，故t (R1) = R1。因?yàn)镽2是傳遞的，故t(R2)= R2。因此，t (R1) È t (R2) = R1 ÈR2 =< 1, 2 >, < 2, 1 >，而t (R1ÈR2) = < 1, 2 >, &

12、lt; 2, 1 >, < 1, 1 >, < 2, 2 >。18. 對(duì)于下列集合上的整除關(guān)系，畫出哈斯圖。(1) A = 1, 2, 3, 4, 6, 8, 12, 24(2) B = 1, 2, 3, 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上的四個(gè)偏序關(guān)系，試畫出它們的哈斯圖。并判別哪一個(gè)是全序或良序關(guān)系。(a) 去掉關(guān)系圖中的自環(huán)，沒有進(jìn)入頂點(diǎn)4的有向邊，將4畫在最下面，去掉從4發(fā)出的有向邊，沒有進(jìn)入頂點(diǎn)1的有向邊，將1畫在第二層，去掉從1發(fā)出的有向邊，剩下兩個(gè)孤立點(diǎn)2和3，將2和3畫在最上面。連接4和1，1和2，1和3，得到哈斯圖。224444111122333323. 令T是笛卡爾平面 R´R