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

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

習(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)系必須滿足所有形如的序偶包含在關(guān)系中，而形如的序偶有n個。即|AA-|=n2-n在構(gòu)造A上的自反關(guān)系的時候可以先將所有的放到這些關(guān)系中再考慮其他序偶的組合。即|(AA-)|=2n2-n,(3)共有種定義在A上的不同的反自反關(guān)系；說明:A上的反自反關(guān)系必須滿足所有形如的序偶不能包含在關(guān)系中，在構(gòu)造A上的反自反關(guān)系的時候可以先將所有的拿出后再考慮其他序偶的組合。即(AA-)=2n2-n,(4)共有種定義在A上的不同的對稱關(guān)系;說明:A上的對稱關(guān)系必須滿足：如果在這個關(guān)系中，則也必須在這個關(guān)系中。在構(gòu)造A上的對稱關(guān)系的時候可以先將所有的和（其中xy）看成是一個整體。要考慮的序偶的個數(shù)有：n+(n2-n)/2=n(n+1)/2(+(AA-)/2)=2(n2+n)/2,(5)共有種定義在A上的不同的反對稱，其中，。,4.,(1)自反關(guān)系矩陣的主對角線上元素全為1；而關(guān)系圖中每個結(jié)點上都有圈（即若關(guān)系R是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是1，在關(guān)系圖上每個結(jié)點都有自回路）。(2)反自反關(guān)系矩陣的主對角線上元素全為0;而關(guān)系圖中每個結(jié)點上均無圈（即若關(guān)系R是反自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是0，在關(guān)系圖上每個結(jié)點都沒有自回路）。,(3)對稱關(guān)系矩陣為對稱矩陣;而關(guān)系圖中任何兩個結(jié)點之間的有向弧是成對出現(xiàn)的,方向相反。（即若關(guān)系R是對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣是對稱的，且在關(guān)系圖上任兩個結(jié)點若有定向弧線，則定向弧線必定是成對出現(xiàn)的）反對稱關(guān)系矩陣的元素滿足：當(dāng)ij時，。而關(guān)系圖中任何兩個結(jié)點之間的有向弧是單向的。（即若關(guān)系R是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以對角線對稱的元素不能同時為1，在關(guān)系圖上任兩個結(jié)點的定向弧線不可能成對出現(xiàn)）,5.,RS=,SR=;R2=,;S2=,.,6.,設(shè)R=,T=,S=,P=,7.,(1)正確。因為對任意xA，有xRx，xSx,所以x(RS)x。故RS是自反的。(2)錯誤。例如，設(shè)x,yA，xy,且xRy，ySx，于是x(RS)x。故RS不是反自反的。,(3)錯誤。例如，設(shè)對稱關(guān)系R=,S=,。則RS=,故RS不是對稱的。,(4)錯誤。例如，設(shè)反對稱關(guān)系R=,S=,xy。于是，RS=,。故RS不是反對稱的。(5)錯誤。例如，設(shè)傳遞關(guān)系R=,S=,wv。于是，RS=,，顯然，RS不是一個傳遞關(guān)系。,思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。,思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。,8.,(3)由定義，,于是存在z1,z2,zn-1,滿足：,R1R1R2,舉例說明“”成立。設(shè),9.,設(shè)R1和R2是集合A上的二元關(guān)系。注意到,(3)由定義，,t(R1R2)=(R1R2)(R1R2)2于是t(R1)t(R2)=(R1R2)(R1R22)(R12R22)(R12R2)下證對任意的n1,有(R1R2)n(R1nR2n)證明:任取(R1R2)n,則存在n-1個元素z1,z2zn-1滿足R1R2,R1R2,R1R2。從而有R1,R1,R1并且R2,R2,R2。,所以有R1n并且R2n，即R1nR2n所以(R1R2)n(R1nR2n)例如：設(shè)A=1，2，3，R1=,R2=則t(R1)=,t(R2)=,t(R1)t(R2)=,R1R2=,t(R1R2)=,10.說法不正確.這是因為自反性要求對任意的x和x都有關(guān)系R,x和y有沒有關(guān)系R,我們不考慮；但是,我們題目中得出的結(jié)論x和x具有關(guān)系R,是以對稱性為前提條件的,所以我們知道該論述不正確。,11.,設(shè)R是等價關(guān)系。若,R，則由R的對稱性知,R。再由R的傳遞性有R。反之,假設(shè)只要,R，就有R。(1)對稱性。設(shè)R，由自反性有R。于是R。(2)傳遞性。設(shè),R。由對稱性有R,再由假設(shè)有R。,12.,而由A/R1=A/R2,有對任意xA,因為xR1A/R2并且xxR1xR2，所以xR1=xR2。產(chǎn)生矛盾。,13.,14.,故S是X的一個劃分,15.,設(shè)A=1,2,3,4,則A上的等價關(guān)系數(shù)目即A上的劃分的數(shù)目共有15個(1)最大劃分1,2,3,4(2)最小劃分1,2,3,4(3)將A分成兩個集合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上的全部等價關(guān)系數(shù)目,則,因為En是將n個元素的集合進(jìn)行劃分的方法數(shù)，對任何一個劃分來說，b總是在劃分的某一個塊中，也就是某一個子集中。不妨設(shè)這個子集有k個元素(k=1,n),則在此子集中的另外k-1個元素將從n-1個元素中選取。然后對剩下的n-k個元素進(jìn)行劃分。故有,16.,15,3,5,12,6,2,3,1,54,27,9,3,17.,(1)最(極)大元x1,無最小元;(2)上界下界上確界下確界x2,x3,x4x1x4x1x4x3,x4,x5x1,x3無x3無x1,x2,x3x1x4x1x4,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中不存在極大(小)元,則對任何xB,則存在yB,使得xy(yx),如此下去,得出B為無限集.矛盾.故結(jié)論成立。,21.,設(shè)B是A上的一個非空有限集,由上題知,B中至少有一個極大(小)元。又因為全序集,故B的極大(小)元均唯一,且就是最大(小)元。,