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

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既是對稱又是反對稱的； (4). 令A(yù)=1,2,3,R=, 于是R既不是對稱又不是反對稱的。3. 設(shè)A=X1,X2 ,Xn，于是定義在A上的二元關(guān)系R中的元素來自于下列矩陣： . (1)共有2n2 種定義在A上的不同的二元關(guān)系； 說明: |A|=n |AA|=n2 |(AA)|=2n2 (2)共有 種定義在A上的不同的自反關(guān)系；說明: A上的自反關(guān)系必須滿足所有形

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

3、偶的個(gè)數(shù)有： n+(n2-n)/2=n(n+1)/2 (+(AA-)/2)=2(n2+n)/2 2/ )1(2/ )1(222nnnnn (5)共有 種定義在A上的不同的反對稱， 其中， 。 kmmkkmnC2202) 1( nnm4. (1) 自反關(guān)系矩陣的主對角線上元素全為1；而關(guān)系圖中每個(gè)結(jié)點(diǎn)上都有圈（即若關(guān)系R是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是1，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自回路）。 (2) 反自反關(guān)系矩陣的主對角線上元素全為0; 而關(guān)系圖中每個(gè)結(jié)點(diǎn)上均無圈（即若關(guān)系R是反自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是0，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都沒有自回路） 。 (3

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

5、()(TRSR因此)()()(TRSRTSR從而,1 , 1,)(PSPTS又1 , 1,1 , 3PT1 , 1)()(PTPS因此)()()(PTPSPTS從而7. (1) 正確。因?yàn)閷θ我鈞A，有xRx，xSx,所以x(RS)x。故RS是自反的。 (2) 錯(cuò)誤。例如，設(shè)x,yA，xy,且xRy，ySx，于是x(R S)x。故R S不是反自反的。(3)錯(cuò)誤。例如，設(shè)對稱關(guān)系R=,S=,。則RS=故RS不是對稱的。(4) 錯(cuò)誤。例如，設(shè)反對稱關(guān)系R=,S=,xy。于是，RS=,。故RS不是反對稱的。 (5) 錯(cuò)誤。例如，設(shè)傳遞關(guān)系R=,S=,wv。于是，RS=,，顯然， RS不是一個(gè)傳遞關(guān)系

6、。思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。自反性反自反 對稱性 反對稱 傳遞性R-1RSRSR-SR.S思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。8.0212121)()()() 1 (RRRRRRr)()(020121RRRR)()(022011RRRR)()(21RrRr1212121)()()()2(RRRRRRs)()(121121RRRR)()(122111RRRR)()(21RsRs(3)由定義，,)(,)(22222111RRRtRRR

7、t,)()()(2212121RRRRRRt22221121)()(RRRRRtRt于是)()(222121RRRRnnnRRRRn)(12121 有下證對任意nnRRyx21,任取nRyx1, 不妨設(shè),211212111RRRzzRRRzx于是存在z1,z2,zn-1,滿足：R1 R1R2nRRyx)(,21從而舉例說明“ ”成立。設(shè)于是3 , 2,2 , 1,3 , 2 , 121RRA3 , 2,3 , 1,2 , 1)(21 RRt3 , 1,2 , 1)()(21RtRt9.設(shè)R1和R2是集合A上的二元關(guān)系。注意到 ，于是0210201)(RRRR0212121)()()() 1 (

8、RRRRRRr0121)(RRR)()(012011RRRR)()(022011RRRR)()(21RrRr1212121)()()()2(RRRRRRs12221111)(,)(RRRsRRRs任取)()()()(12211121RRRRRsRs1212121)()()(,RRRRRRsyx),(,)(21RRyxi若從而,1222RRRyx)()(,122111RRRRyx且則,1111RRRyx)()(21RsRs,)(,)(121RRyxii 若即則),(,21RRxy,21從而且RxyRxy,11111且RRRyx,12212于是RRRyx)()(,122111RRRRyx).()(

9、)(2121RsRsRRs故)()(21RsRs:成立舉例說明 ,1 , 2,2 , 1,2 , 121于是設(shè)RRA1212121)()()(RRRRRRs而,1,1 , 2,2 , 1)(1111RRRs1 , 2,2 , 1)(1222RRRs,1 , 2,2 , 1)()(,21RsRs因此)()()(2121RsRsRRs故(3)由定義，,)(,)(22222111RRRtRRRtt(R1R2)=(R1R2)(R1R2)2于是 t(R1)t(R2)=(R1R2)(R1R22) (R12R22)(R12R2) ) 下證對任意的n1,有(R1R2)n (R1nR2n)證明:任取(R1R2)

10、n, 則存在n-1個(gè)元素z1,z2zn-1滿足R1R2, R1R2,R1R2。從而有R1 , R1, R1并且R2 , 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)= w 10.說法不正確. 這是因?yàn)樽苑葱砸髮θ我獾膞和x都有關(guān)系R, x和y有沒有關(guān)系R,我們不考慮；但是,我們題目中得出的結(jié)論x和x具有關(guān)系R,是以對稱性為前提條件的,所以我們知道該論述不正確。11.設(shè)R是等價(jià)關(guān)系。若,R，則由R的對稱性知, R。再

11、由R的傳遞性有R。反之, 假設(shè)只要, R，就有R。 (1)對稱性。 設(shè)R，由自反性有R。于是R。 (2)傳遞性。 設(shè), R。由對稱性有R, 再由假設(shè)有R。12.2121/,RARARR則顯然設(shè)21/,RARA設(shè)反之121,RyxRR則不妨設(shè)若2,Ryx但2211 ,RRRRyxyx于是21RR 故而由A/R1=A/R2 ,有對任意xA,因?yàn)閤R1 A/R2并且x xR1 xR2，所以xR1=xR2。產(chǎn)生矛盾。13.于是設(shè)),5(mod|,yxxyR4 ,3 ,2 ,1 ,0/.19,14,9 ,4, 1,6,11.4.18,13,8 , 3 ,2,7,12.3.17,12,7 ,2, 3,8,

12、13.2.16,11,6 , 1 ,4,9,14.1 .15,10,5 ,0 ,5,10,15.0RRRRRRRRRRBA14.|jijiBABAS證明jiBAS,) 1 (定義知由)()()()(,1 ,1,)2(mjmimljimliiBBAABABAsmjrjiSBASBA和任取SBABABBAAjiBAsjrijisjrjijimjr111,11)()().().()3(故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，有兩種

13、可能： 2,31,4, , 2,41,3, , 3,41,2, ,31/2|,A|A| (i) 2421即種共有C1,2,34,1,2,4,3, , 1,3,42, 2,3,41, ,4 . 3|A|1,|A| (ii)3421即種共C即種分法故共有元素個(gè)則恰有一個(gè)集合為個(gè)集合分成將,6C,2,3A(4)24 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)系數(shù)目, 則101101nkknnnCkEEEw 因?yàn)镋n是將n個(gè)元素的集合進(jìn)行劃分的方法數(shù)，對任何一個(gè)劃分來說，b總是在劃分的某一個(gè)塊中，也就是

14、某一個(gè)子集中。不妨設(shè)這個(gè)子集有k個(gè)元素(k=1,n),則在此子集中的另外k-1個(gè)元素將從n-1個(gè)元素中選取。然后對剩下的n-k個(gè)元素進(jìn)行劃分。故有1011011211101nkkknnnnnnnnnECECECECE16.A1,1535A2,12623154 2793A3,17.(1) 最(極)大元x1, 無最小元;(2) 上界 下界 上確界 下確界x2, x3, x4 x1 x4 x1 x4x3, x4, x5 x1,x3 無 x3 無x1, x2, x3 x1 x4 x1 x418.(2)題16中的A1,子集3 ,5無最大元;(3)題16中的A2,子集2,3,6有下確界但無最小元;(4)題16中的A2,子集1 有上界2,3,6,12,但是無上確界。0|,) 1 (mZmZZZ