離散數(shù)學(xué)(劉任任版)第2章答案.ppt

《離散數(shù)學(xué)(劉任任版)第2章答案.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)(劉任任版)第2章答案.ppt（45頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、習(xí)題二,1.,(1). R=,,,,(2). R=,,,,2.,設(shè)R是定義在集合A上的二元關(guān)系。 (1). 設(shè)A= ，則R= 既是自反的又是反自反的. (2). 令A(yù)=1，2，R=，于是R既不是自反又不是反自反的； (3). 令A(yù)=1，2，R=,,于是R既是對(duì)稱又是反對(duì)稱的；,(4). 令A(yù)=1,2,3,R=,,, 于是R既不是對(duì)稱又不是反對(duì)稱的。,3.,設(shè)A=X1,X2 ,,Xn，于是定義在A上的二元關(guān)系R中的元素來自于下列矩陣： . ,,,(1)共有2n2 種定義在A上的不同的二元關(guān)系； 說明: |A|=n |AA|=n2 |(AA)|=2n2,(2)共有

2、 種定義在A上的不同的自反關(guān)系；說明: A上的自反關(guān)系必須滿足所有形如的序偶包含在關(guān)系中，而形如的序偶有n個(gè)。即|AA-|=n2-n 在構(gòu)造A上的自反關(guān)系的時(shí)候可以先將所有的放到這些關(guān)系中再考慮其他序偶的組合。即|(AA-)|=2n2-n,(3)共有 種定義在A上的不同的反自反關(guān)系；說明: A上的反自反關(guān)系必須滿足所有形如的序偶不能包含在關(guān)系中， 在構(gòu)造A上的反自反關(guān)系的時(shí)候可以先將所有的拿出后再考慮其他序偶的組合。即(AA-)=2n2-n,(4)共有 種定義在A上的不同的對(duì)稱關(guān)系; 說明: A上的對(duì)稱關(guān)系必須滿足：如果在這個(gè)關(guān)系中，則也必須在這個(gè)關(guān)系中。 在構(gòu)造A

3、上的對(duì)稱關(guān)系的時(shí)候可以先將所有的和（其中xy）看成是一個(gè)整體。 要考慮的序偶的個(gè)數(shù)有： n+(n2-n)/2=n(n+1)/2 (+(AA-)/2)=2(n2+n)/2,(5)共有 種定義在A上的不同 的反對(duì)稱， 其中， 。,4.,(1) 自反關(guān)系矩陣的主對(duì)角線上元素全為1；而關(guān)系圖中每個(gè)結(jié)點(diǎn)上都有圈（即若關(guān)系R是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對(duì)角線上的所有元素都是1，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自回路）。 (2) 反自反關(guān)系矩陣的主對(duì)角線上元素全為0; 而關(guān)系圖中每個(gè)結(jié)點(diǎn)上均無圈（即若關(guān)系R是反自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對(duì)角線上的所有元素都是0，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都沒有

4、自回路） 。,(3) 對(duì)稱關(guān)系矩陣為對(duì)稱矩陣; 而關(guān)系圖中任何兩個(gè)結(jié)點(diǎn)之間的有向弧是成對(duì)出現(xiàn)的, 方向相反。 （即若關(guān)系R是對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣是對(duì)稱的，且在關(guān)系圖上任兩個(gè)結(jié)點(diǎn)若有定向弧線，則定向弧線必定是成對(duì)出現(xiàn)的） 反對(duì)稱關(guān)系矩陣 的元素滿足： 當(dāng)ij 時(shí) ， 。 而關(guān)系圖中任何兩個(gè)結(jié)點(diǎn)之間的有向弧是單向的。（即若關(guān)系R是反對(duì)稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以對(duì)角線對(duì)稱的元素不能同時(shí)為1，在關(guān)系圖上任兩個(gè)結(jié)點(diǎn)的定向弧線不可能成對(duì)出現(xiàn)）,5.,RS=,,SR=; R 2=,,; S 2=,,.,6.,設(shè)R=,,T=,,S=,,P=,,,7.,(1) 正確。因?yàn)閷?duì)任意

5、xA，有xRx，xSx,所以x(RS)x。故RS是自反的。 (2) 錯(cuò)誤。例如，設(shè)x,yA，xy,且xRy，ySx，于是x(R S)x。故R S不是反自反的。,(3)錯(cuò)誤。例如，設(shè)對(duì)稱關(guān)系 R=,,S=,。 則RS=,故RS不是對(duì)稱的。,(4) 錯(cuò)誤。例如，設(shè)反對(duì)稱關(guān)系R=,,S=,,xy。于是，RS=,。故RS不是反對(duì)稱的。 (5) 錯(cuò)誤。例如，設(shè)傳遞關(guān)系R=,,S=,,wv。于是，RS=,，顯然， RS不是一個(gè)傳遞關(guān)系。,思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。,思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性

6、質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。,8.,(3)由定義，,于是存在z1,z2,zn-1,滿足：,R1 R1R2,舉例說明“ ”成立。設(shè),9.,設(shè)R1和R2是集合A上的二元關(guān)系。注意到,(3)由定義，,t(R1R2)=(R1R2)(R1R2)2 于是 t(R1)t(R2)=((R1R2)(R1R22)) ((R12R22)(R12R2) ) 下證對(duì)任意的n1,有(R1R2)n (R1nR2n) 證明:任取(R1R2)n, 則存在n-1個(gè)元素z1, z2zn-1滿足R1R2, R1R2,, R1R2。從而有R1 , R1,, R1并且R2 ,

7、 R2,, R2。,所以有R1n 并且R2n，即 R1n R2n 所以(R1R2)n (R1nR2n) 例如：設(shè)A=1，2，3，R1=,, R2= 則t(R1)=,,, t(R2)=, t(R1)t(R2)=, R1R2= , t(R1R2)= ,,10.說法不正確. 這是因?yàn)樽苑葱砸髮?duì)任意的x和x都有關(guān)系R, x和y有沒有關(guān)系R,我們不考慮；但是,我們題目中得出的結(jié)論x和x具有關(guān)系R,是以對(duì)稱性為前提條件的,所以我們知道該論述不正確。,11.,設(shè)R是等價(jià)關(guān)系。若,R，則由R的對(duì)稱性知, R。再由R的傳遞性有R。 反之, 假設(shè)只要, R，就有R。 (1)對(duì)稱性。 設(shè)R，由

8、自反性有R。于是R。 (2)傳遞性。 設(shè), R。由對(duì)稱性有R, 再由假設(shè)有R。,12.,而由A/R1=A/R2 ,有對(duì)任意xA,因?yàn)閤R1 A/R2并且x xR1 xR2，所以xR1=xR2。產(chǎn)生矛盾。,13.,14.,故S是X的一個(gè)劃分,15.,設(shè) A=1,2, 3,4 , 則A上的等價(jià)關(guān)系數(shù)目即A上的劃分的數(shù)目共有15個(gè) (1) 最大劃分 1,2,3,4 (2) 最小劃分 1,2,3,4 (3) 將A分成兩個(gè)集合S=A1，A2，有兩種可能：,1,2,3,4, 1,3,2,4, 1,4,2,3, 2,3,1,4, 2,4,1,3, 3,4,1,2 . 設(shè)Ek表示k元集合A上的全部等價(jià)關(guān)

9、系數(shù)目, 則,因?yàn)镋n是將n個(gè)元素的集合進(jìn)行劃分的方法數(shù)，對(duì)任何一個(gè)劃分來說，b總是在劃分的某一個(gè)塊中，也就是某一個(gè)子集中。不妨設(shè)這個(gè)子集有k個(gè)元素(k=1,,n),則在此子集中的另外k-1個(gè)元素將從n-1個(gè)元素中選取。然后對(duì)剩下的n-k個(gè)元素進(jìn)行劃分。故有,16.,,,,,15,3,5,,,,,,,,12,6,2,3,1,,,,54,27,9,3,,17.,(1) 最(極)大元x1, 無最小元; (2) 上界 下界 上確界 下確界 x2, x3, x4 x1 x4 x1 x4 x3, x4, x5 x1,x3 無 x3 無 x1, x2, x3 x1 x4 x1 x4,18.,(2)題16中的,子集3 ,5無最大元; (3)題16中的,子集2,3,6有下確界但無最小元; (4)題16中的,子集1 有上界2,3,6,12,但是無上確界。,19.,設(shè)為全序集, 且|A| = n。,因此, B中必有最小元a.故為良序集,20.,設(shè)B是A的非空有限集。若B中不存在極大(小)元,則對(duì)任何xB, 則存在yB,使得xy(yx),如此下去,得出B為無限集.矛盾.故結(jié)論成立。,21.,設(shè)B是A上的一個(gè)非空有限集,由上題知,B中至少有一個(gè)極大(小)元。 又因?yàn)槿蚣?故B的極大(小)元均唯一, 且就是最大(小)元。,