湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題2

習(xí)題1?確定下列二兀關(guān)系：］(IA=&,2,3lB=務(wù),3,51R=vx,y|x,yeAB°uAxBA=^0,1,2,3,4,5,6,8}R={x,=2yAxA分析：本題主要運(yùn)用知識為集合的交、關(guān)系以及笛卡爾積的定義。解：(1)R={<1,1>,<1,3>,<3,1>,<3,3>}R={<1,0>,<2,1>,<4,2>,<&3>}2?請分別給出滿足下列要求的二元關(guān)系的例子：(1)既是自反的，又是反自反的；既不是自反的，又不是反自反的；(3)既是對稱的，又是反對稱的；(4)既不是對稱的，又不是反對稱的?分析本題主要考察關(guān)系的5個性質(zhì)(自反性、反自反性、對稱性、反對稱性、傳遞性)。解：設(shè)R是定義在集合A上的二元關(guān)系。令A(yù)=0，則R=0，于是R既是自反又是反自反的；令A(yù)={1,2},R={<1,1>}，于是R既不是自反又不是反自反的；令A(yù)={1,2},R={<1,1>,<2,2>}，于是R既是對稱又是反對稱的；令A(yù)={1,2,3},R={<1,2>,<2,1>,<1,3>}，于是R既不是對稱又不是反對稱的。3.設(shè)集合A有n個元素，試問：共有多少種定義在A上的不同的二元關(guān)系？共有多少種定義在A上的不同的自反關(guān)系？共有多少種定義在A上的不同的反自反關(guān)系？共有多少種定義在A上的不同的對稱關(guān)系？共有多少種定義在A上的不同的反對稱關(guān)系？分析：本題主要考察知識為二元關(guān)系的自反性、反自反性、對稱性、反對稱性所對應(yīng)的關(guān)系矩陣之性質(zhì)，本題可以在做完第四題(根據(jù)滿足某個性質(zhì)的關(guān)系之關(guān)系矩陣)之后再來考慮。解：設(shè)|A|=n，于是共有2n種定義在A上的不同的二元關(guān)系；共有2n-n種定義在A上的不同的自反關(guān)系；共有2n-n種定義在A上的不同的反自反關(guān)系；共有2n-2n(n-1)/2=2n(n+1)/2種定義在A上的不同的對稱關(guān)系；共有2n￡Ck*2m-k=2n?3m種定義在A上的不同的反對稱關(guān)系，其中，m=—m2k=04?請分別描述自反關(guān)系，反自反關(guān)系，對稱關(guān)系和反對稱關(guān)系的關(guān)系矩陣以及關(guān)系圖的特征分析：本題主要是根據(jù)自反關(guān)系、反對稱關(guān)系、對稱關(guān)系和反對稱關(guān)系之定義來確定關(guān)系矩陣以及關(guān)系圖。解：(1)自反關(guān)系矩陣的主對角線上元素全為1；而關(guān)系圖中每個結(jié)點(diǎn)上都有圈。(2)反自反關(guān)系矩陣的主對角線上元素全為0;而關(guān)系圖中每個結(jié)點(diǎn)上均無圈。

對稱關(guān)系矩陣為對稱矩陣;而關(guān)系圖中任何兩個結(jié)點(diǎn)之間的有向弧是成對出現(xiàn)的方向相反。5．當(dāng)°豐j時，『二°。2,3；：,；2,4；,32；J試求R-S,S-R,R2,⑷反對稱關(guān)系矩陣Mr=5．當(dāng)°豐j時，『二°。2,3；：,；2,4；,32；J試求R-S,S-R,R2,及S2.分析主要考察關(guān)系的復(fù)合運(yùn)算之定義。解：R?S={<1,4>,<1,3>},S?R={<3,4>}R2={<1,1>,<1,2>,<1,4>},S2={<2,2>,<3,4>,<3,3>}。6.試舉出使R-(SnT)u(R-S)n(R-T)(snt)?pu(s-p)n6*p)成立的二元關(guān)系R,S,T,P的實例.分析本題主要說明關(guān)系的復(fù)合與關(guān)系的交運(yùn)算不滿足分配率。解：設(shè)R={<3,1>,<3,2>},T={<1,3>,<3,2>},S={<1,2>,<2,3>},P={<2,1>,<3,1>},于是，有SnT=0,R-(SnT)=0,R-S二{<3,2>,<3,3>},R-T={<3,3>},R-(R-(SnT)u(R-S)n(R-T)。T-P={<3,1>,<1,1>}，因此,(SnT)-Pu(S-P)n(T-P)。(R-S)n(R-T)={<3,3>}豐0從而,又，(SnT)-P=0,S-P={<1,1>},(S-P)n(T-P)={<1,1>}H0，從而,7.設(shè)R和S是集合A上的二元關(guān)系.下面的說法正確嗎?請說出理由.若R和S是自反的，則R-S也是自反的；若R和S是反自反的，則R-S也是反自反的；若R和S是對稱的，則R*S也是對稱的；⑷若R和S是反對稱的，則R-S也是反對稱的；(5)若R和S是傳遞的，則R-S也是傳遞的分析本題主要是考察兩個滿足同一種性質(zhì)的關(guān)系之復(fù)合運(yùn)算是否保該性質(zhì)，是的可以根據(jù)定義給出證明，不正確請給出反例，一般如果正確相對容易證明，不正確給出反例相對較難。解：⑴正確。因為對任意xgA，有xR,xSx,所以x(R-S)x。故R-S是自反的。(2)錯誤。例如，設(shè)x,ygA,x豐y，且xRy,ySx,于是x(R-S)x。故R-S不是自反的。⑶錯誤。例如，設(shè)對稱關(guān)系R={<x,z>,<z,x>},S={<z,y>,<y,z>}。于是，<x,y>gR-S，但<y,x>《R-S。故R-S不是對稱的。錯誤。例如，設(shè)反對稱關(guān)系R={<x,z>,<y,w>},S={<z,y>,<w,x>},x豐y。于是，<x,y>,<y,x>gR-S。故R-S不是反對稱的。錯誤。例如，設(shè)傳遞關(guān)系R={<x,w>,<y,v>},S={<w,y>,<v,z>},w豐v。于是，x(R-S)y,y(R-S)z，但因為w豐v，所以，<x,z>gR-S。8?設(shè)R1和R2是集合A上的二元關(guān)系，試證明:

(1)r(RUR)=r(R)Ur(R)；⑵s(RUR)=s(R)Us(R)；⑶t(R；UR；Lt(R；)Ut(R2)并舉出使＞1時使t(RUR)二t(R)Ut(R)的實例.1212分析：(1)本小題根據(jù)自反閉包的定義，它一個關(guān)系R的自反閉包應(yīng)該包含R0，然后根據(jù)(RuR)o=R0oR0即可證得。(2)本小題根據(jù)對稱閉包的定義，它一個關(guān)系R的對稱閉1212包應(yīng)該包含R-1，然后根據(jù)(RoR)-1二R-1uR-1即可證得。(3)由于傳遞閉包的特殊性，1212它不滿足類似與(1)(2)的情形，所以要進(jìn)行相對麻煩的證明，主要運(yùn)用集合的包含關(guān)系的證明方法。解：⑴r(RoR)二(RoR)o(RoR)oR2R2)o(R10oR20)R10)o(R2oR20)=(R1o=(R1o二r(RJor(R2)(2)s(R1oR2(2)s(R1oR2)=(R1oR2)o(R1oR2)-1=(R1oR2)o(R1-1oR2-1)oR1-1)o(R2oR2-1)=s(R])os(R2)(3)由定義，t(R])=R]oRfo…,于是，t(R2)=R2oR2o…，t(R]oR2)=(R]oR2)o(R]t(R])=R]oRfo…,于是，t(R])ot(R2)=R]oR]2o???oR2oR22o???=(R]oR2)o(R]2oR22)o…。下證對任意n>1，有R]noR2nu(R]oR2)n。任取<x,y>eR]noRJ，不妨設(shè)<x,y>eR]n。于是，存在z],z2,…znga,使得<x,Z[>gR[匸R[oR2,<Z[,z2>gR[匸R[oR2,…，<z.,z>gR.匸R.oR2,<z,y>g111212112n-1n112n從而，<x,y>g(R]oR2)n。舉例說明“u”成立。設(shè)A={1,2,3},R]={<1,2>},R2={<2,3>}，于是，tt(R1oR2)二{<1,2>,<1,3>,<2,3>}二t(R])ot(R2)二{<1,2>,<1,3>}9.設(shè)R和R2是集合A上的二元關(guān)系，試證明：(1)r(RA卞)=r(R)Ar(R)；⑵s(RAR)us(R)As(R)；(3)t(RAR)ut(R)At(R)并請給出IA>1時使s(RAR)us(R)As(R)和t(RAR)ut(R)At(R)的實例.12121212分析：(1)本題主要是根據(jù)自反關(guān)系的定義得到一個特殊的等式R]o=R20=(R]cR2)0進(jìn)行變換，只要想到這個等式，下面的工作就比較容易做。(2)本題主要是根據(jù)對稱關(guān)系的定義及定理的定義及定理2.2.6得到如下三個公式：s(R]cR2)=(R]cR2)o(R]cR2)-1,R2oR2-]s(R])=R]oR]-i,s(R2)=s(R])cs(R2)=(R]oR]-1)c(R2oR2-]R2oR2-]方法就可得到結(jié)論。(3)本小題根據(jù)傳遞閉包的定義及定理2.2.6得t(R)=RoR2o…，t(R)=RoR2o…，t(RcR)=(RcR)o(RcR)2o…,]]]222]2]2]2有了上面三個等式以及集合之間包含關(guān)系證明方法可得結(jié)論。解：設(shè)的和R2是集合a上的二元關(guān)系。注意到R]0=R20=(R1cR2)0，于是，r(R1cR2)=(R1cR2)o(R1cR2)0=(R1cR2)oR10=(R1oR10)c(R2oR10)=(R1oR10)c(R2oR20)=t(R1)ct(R2)s(R1cR2)=(R1cR2)o(R1cR2)-1,s(R1)=R1oR1-1,s(R2)=R2oR2-1,s(R])cs(R2)=(R]oR]-1)c(R2oR2-1)。任取x,y>es(R]cRJ=(R1cRJo(R、cRJ-1，若<x,y>e(R]cR)則<x,y>eR1cR1oR1-1,且x,y>eR2cR2oR2-1,從而，x,y>e(R]oR]-])c(R2oR2-1=s(R])cs(R2)；若<x,y>e(R]cR2)-1,則<y,x>g(R]cR2),即y,x>eR],且<y,x>eR2,從而，x,y>eR]-1cR]oR]-1,且<x,y>eR2-1cR2oR2-1,于是，x,y>e(R]oR]-])c(R2oR2-]=s(R])cs(R2)故s(R]cR2)cs(R])cs(R2)。舉例說明“u”成立。={<1,2>,<2,1>},)us(R])cs(R2)。證明：因為t(R1)=R1oR20…,t(R2)=r2or；o…，t(RcR)=(RcR)o(RcR)20…，121212于是t(R)ct(R)=(R0R20…)c(R0R2o…)=o(RicRm)121122皿112設(shè)A={1,2},={<1,2>,<2,1>},)us(R])cs(R2)。證明：因為t(R1)=R1oR20…,t(R2)=r2or；o…，t(RcR)=(RcR)o(RcR)20…，121212于是t(R)ct(R)=(R0R20…)c(R0R2o…)=o(RicRm)121122皿112V<x,y>et(RnR)=(RnR)u(RnR)2u…，121212則存在i,有<x,y>((RnR》也就有z,z，…,z使得<x,z>eRnR,TOC\o"1-5"\h\z1212i112<x,z>eRnR，…,<x,z>eRnR，因為RnR匸R且212i12121RnR匸R，所以就有<x,z>eR,<x,z>eR，…,<x,z>eR,1221121i1所以有<x,y>eRi同時也有<x,z>eR,<x,z>eR，…,<x,z>eR,11222i2所以也有<x,y>eR/就有<x,y>wRjnR/，即(RnR)匸RjnR/,2121212又因為Ri1nRi2匸u(RinRm2),所以結(jié)論成立。1212l,m>1又設(shè)A={1,2,3},叫={<1,2>,<2,3>},R2={<1,3>},于是，rnr=0,t(rnr)=0,而，1212t(R)={<1,2>,<2,3>,<1,3>},1t(R)=R={<1,3>},22t(R)nt(R)={<1,3>}12故t(RnR)Ut(R)nt(R).121210.有人說，“如果集合a上的二元關(guān)系R是對稱和傳遞的，則R必是自反的.因此，等價關(guān)系定義中的自反性可以去掉”.并給出如下證明，如果{x,y；eR,由R的對稱性有]y,x；eR,再由R的傳遞性知，■:x,x]eR且「y,y：eR，即R是自反的.你的看法如何？分析：本題主要是沒有弄明白對稱和傳遞都是滿足一定前提條件的，而自反關(guān)系則是A中每個元素都必須滿足這個條件。解：說法不正確。對任意xeA，對稱性并不要求一定有<x,y>eR,因此也就不一定有<y,x>。于是<x,xR。例如：設(shè)A={1，2,3},R={<1,2>,<2,1>,<1,1>}，則R是對稱和傳遞的，但是R不是自反的，因為R中不包含<2,2>,<3,3>，這是因為R如果是自反的必須包含R0。11.設(shè)R是集合A上的自反關(guān)系.試證明R是等價關(guān)系當(dāng)且僅當(dāng)若：；x,y：,：：x,zeR，則::y,z；eR.分析：本題主要是利用等價關(guān)系中自反性、對稱性、傳遞性的定義來證明。44解：設(shè)R是等價關(guān)系。若vx,y>,<x,z>wR,則由R的對稱性知,<y,x>wR。再由R的傳遞性有vy,z>wR。反之，假設(shè)只要vx,y>,vx,z>wR,就有vy,z>wR。對稱性。設(shè)vx,y>wR,由自反性有vx,x>wR。于是vy,x>wR。傳遞性。設(shè)vx,y>,vy,z>wR。由對稱性有vy,x>wR,再由假設(shè)有vx,z>wR。設(shè)R和R都是集合A上的等價關(guān)系，試證明R=R當(dāng)且僅當(dāng)A/R=A/R.121212分析：本題主要是根據(jù)等價類的定義及性質(zhì)可以得到。證明：設(shè)R=R,則顯然A/R=A/R。1212反之，設(shè)A/R=A/R。若R豐R,則不妨設(shè)vx,y>wR但vx,y>纟R.121212于是[x]二[y],[x]主[y].R1R1R2R2由劃分之定義得知A/R豐A/R,矛盾.。故R=R。1212設(shè)R二fx,y；|x三y(mod5甘是定義在整數(shù)集Z上的模5同余關(guān)系，求Z/R.分析：本題主要是等價類的定義及性質(zhì)可以得到。解：設(shè)R={vy,x>lx=y(mod5)}.于是[0]={...-15,-10,-5,0,5,10,15...}R={.??-14,-9,-4,1,6,11,16,???}R={.??-13,-8,-3,2,7,12,17,???}R={???-12,-7,-2,3,8,13,18,?..}R={???-11,-6,-1,4,9,14,19,??.}RA/R={[0],[1],[2],[3],[4]}.RRRRR設(shè)A=^A,A，…,A}和B={B,B，…,R}是集合X的兩個劃分，令12r12s

S兀nB|anB工0,1<i<r,1<j<s}ijij試證明S也是X的一個劃分.證明：本題主要是根據(jù)劃分的定義以及集合的性質(zhì)可以得到證明：?/S二{AnBIAnB鼻0}.iiii(1)由S定義知，AnB鼻0；ii⑵任取AnBgS和AnBgS,1<=i,jv=r,1v=j,mv=s.TOC\o"1-5"\h\ziilm（anb）n（anb）二（ana）n（bnb）=0n0=0iilmimjm（3）x=xnx=（au....ua）n（bu...ub）=U（anb）=U（Anb）=smijij11<<ij11<<ij,<js<r1<j<sa.nb.主0ij故S是x的一個劃分.15.定義在4個元素的集合A之上的等價關(guān)系共有多少個？若|A|=n呢？分析：本題是根據(jù)等價關(guān)系與劃分的一一對應(yīng)關(guān)系，利用劃分來處理，由特殊推到一般。有幾種證明方法。解：設(shè)A={1,2,3,4},則A上的等價關(guān)系數(shù)目即A上的劃分的數(shù)目共有15個.最大劃分{{1},{2},{3},{4}}最小劃分{{1,2,3,4}}將A分成兩個集合S={q,A2},共有兩種可能：⑴|A|=|A|，共有1/2C2=3種，即124{{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}}。(ii)|A|=1,|A|=3,共C3=4種，即124{{1},{2,3,4}},{{2},{1,3,4}},{{3},{1,2,4},{{4},{1,2,3}}將A分成三個集合，則恰有一個集合為2個元素，故共有C2=6種分法，即

{{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è)E表示可k元集合A上的全部等價關(guān)系數(shù)目,則kE=￡E,?Cn-1-knkn-1<k=0E=10本公式還有下面一個推導(dǎo)方法：解:設(shè)f(n,k)表示將n個元素分成k塊的劃分?jǐn)?shù)。則f(n,1)=f(n,n)=1,設(shè)n>1,且1<k<n,設(shè)b是A的某個元素，若組成一個塊，則有f(n-1,k-1)種方法能將A\分成k-1塊，另一方面，A\分成塊的每個劃分允許b被接納到一塊中，有k種方法，因此我們有f(n,k)=f(n-1,k-1)+kf(n-1,k).16.設(shè)A=&5，15}A=b，2,3,6，12}A=&9,27,54},偏序關(guān)系<為整除.試分別畫出1,23解：（A］，-），（A2,，以及解：（A］，-），（A2,，以及（A3,-）的Hasse圖.<A1,<>27<A2,<>圖2.317．{x,x,x,x,x1234517．{x,x,x,x,x12345的Hasse圖如圖2.3所示：（1）求A的最大（?。┰瑯O大（.?。籌（2）分別求tx,x,xJ，lx,x,x［和lx,x,x［的上（下）界，上（下）確界.234345123分析：本題主要是根據(jù)極大（?。┰畲螅ㄐ。┰?，上（下）界，上（下）確界的定義進(jìn)行