離散數(shù)學(xué)第四版課后答案(第4章)

第4章習(xí)題解答4．1A：⑤；B：③；C：①；D：⑧；E：⑩4．2A：②；B：③；C：⑤；D：⑩；E：⑦4．3A：②；B：⑦；C：⑤；D：⑧；E：④分析題4.1-4.3都涉及到關(guān)系的表示。先根據(jù)題意將關(guān)系表示成集合表達(dá)式，然后再進(jìn)行相應(yīng)的計(jì)算或解答，例如，題4.1中的I{1,1,2,2},E{1,1,1,2,2,1,2,2}ssI{1,1,1,2,2,2};s而題4.2中的R{1,1,1,4,2,1,3,4,4,1}.為得到題4.3中的R須求解方程x3y12，最終得到R{3,3,6,2,9,1}.求有三種方法，即集合表達(dá)式、關(guān)系矩陣和關(guān)系圖RR的主法。下面由題4.2的關(guān)系分別加以說明。1°集合表達(dá)式法將domR,domRran,ranR的元素列出來，如圖4.3所示。然后檢查R的每個有序?qū)?，若，則從domR中的x到x,yRranR中的y畫一個箭頭。若danR中的x經(jīng)過2步有向路徑到達(dá)ranR中的y，則x,yRR。由圖4.3可知RR{1,1,1,44,1,4,4,2,1,2,4,3,1}.

如果求，則將對應(yīng)于G中的有序?qū)Φ募^畫在左邊，F(xiàn)G而將對應(yīng)于F中的有序?qū)Φ募^畫在右邊。對應(yīng)的三個集合分別為domG,randomF,ranF，然后，同樣地尋找到的2domGranF步長的有向路徑即可。2°矩陣方法若M是R的關(guān)系矩陣，則的關(guān)系矩陣就是M·M，也RR可記作M2，在計(jì)算乘積時的相加不是普通加法，而是邏輯加，即0+0=0，0+1=1+0=1+1=1，根據(jù)已知條件得100110011001100010001001M2000100011000100010001001M2中含有7個1，說明RR中含有7個有序?qū)ΑD4.3圖4.43°關(guān)系圖方法設(shè)G是R的關(guān)系圖。為求的關(guān)系圖G'，無將G的結(jié)點(diǎn)Rn復(fù)制到中，然后依次檢查G的每個結(jié)點(diǎn)。如果結(jié)點(diǎn)x到y(tǒng)G'有一條n步長的路徑，就在中從x到y(tǒng)加一條有向邊。當(dāng)G'所有的結(jié)點(diǎn)檢查完畢，就得到圖。以題4.2為例。圖4.4G'（1）表示R的關(guān)系圖G。依次檢查結(jié)點(diǎn)1，2，3，4。從1出發(fā)，沿環(huán)走2步仍回到1，所以，中有過1的環(huán)。從1G'出發(fā)，經(jīng)<1,1>和<1,4>，2步可達(dá)4，所以，中有從1到4G'的邊。結(jié)點(diǎn)1檢查完畢。類似地檢查其他3個結(jié)點(diǎn)，2步長的路徑還有2→1→1，2→1→4，3→4→1，4→1→1，4→1→4。將這些路徑對應(yīng)的邊也加到中，G最終得到的關(guān)系圖。R2'這個圖給在圖4.4(2).4．4A：④；B：⑧；C：⑨；D：⑤；E：⑩分析根據(jù)表4.1中關(guān)系圖的特征來判定的性質(zhì)，R,R,R512如表4.2所示。表4.2自反對反傳反自反稱對稱遞R√1R2√R3R√√√√√√√4R5√從表中可知和不是傳遞的，理上如下：在中有RR,RR1231邊<3,1>和<1,2>，但缺少邊<3,2>.在中有邊<1,3>和<3,2>，R2但缺少邊<1,2>。在中有邊<1,2>和<2,1>，但缺少過1的環(huán)。R34.5A：①；B：③；C：⑧；D：⑨；E：⑤分析等價關(guān)系和劃分是兩個不同的概念，有著不同的表示方法，等價關(guān)系是有序?qū)Φ募希鴦澐质亲蛹募?，切不可混淆起來，但是對于給定的集合A，A上的等價關(guān)系R和A的劃分中一一對應(yīng)的，這種對應(yīng)的含義是x,yRx和y在的同一劃分塊里。換句話說，等價說系R的等價類就是劃分的劃分塊，它們表示了對A中元素的同一種分類方式。給定劃分，求對應(yīng)的等價關(guān)系R的方法和步驟說明如下：1°設(shè)中含有兩個以上元素的劃分塊有塊，記作l。若{,,,}，j2，則12jB,B,.BBxxx12ti求出。x,xR,s,t1,2,,j,st.R,R,,R12tsti2°RRRRIA.12t本題中的的劃分塊都是單元集，沒有含有個以上元素1的劃分塊，所以，含有兩個劃分塊，故對應(yīng)地等價關(guān)RI,A2系含有兩個等價類。中只有一個劃分塊包含了集合Z.Z3中的全體元素，這說明因此，這個劃分塊x,yRx,yZ,1對應(yīng)的關(guān)系就上的R全域關(guān)系，從而得到也是RRIZZ11A上的全域關(guān)系。4．6A：③；B：⑩；C：⑤；D：⑩；E：⑤

分析畫哈斯圖的關(guān)鍵在于確定結(jié)點(diǎn)的層次和元素間的蓋住關(guān)系，下面討論一下畫圖的基本步驟和應(yīng)該注意的問題。畫圖的基本步驟是：1°確定偏序集A,中的極小元，最底層，記為第0層。2°若第n層的元素完畢，從A中剩余的元素中選取至少能蓋住第n層中一個元素的元素，將這些元素放在哈斯圖的第n+1層。在排列第n+1層結(jié)點(diǎn)的位置時，注意把蓋住較多元素的結(jié)點(diǎn)放在中間，個元素的結(jié)點(diǎn)放在兩邊，3°將相鄰兩層的結(jié)點(diǎn)以本題的偏序集為例，1可以整除S中的全體整數(shù)，故1是最小元，也是唯一的極小元應(yīng)該放在第0層。是1的倍并將這些極小元放在哈斯圖的已確定將只蓋住一以減少連線的交叉。根據(jù)蓋住關(guān)系進(jìn)行連線。數(shù)，即2，3，5，7，S中剩下的元素是4，6，8，9，10。哪些應(yīng)該放在第2層呢？根據(jù)蓋住關(guān)系，應(yīng)該是4，6，9和10。因?yàn)?蓋住，2，6蓋住2和3，9蓋住3，10蓋住2和5.8不蓋住2，3，5，7中的任何一個元素，最后只剩下一個8放在第3層。圖4.5給出了最終得到的哈斯圖。在整除關(guān)系的哈斯圖中，蓋住關(guān)系體現(xiàn)為最小的倍數(shù)或最小的公倍數(shù)關(guān)系。

如果偏序集是P(A),，那么哈斯圖的結(jié)構(gòu)將呈現(xiàn)出十分規(guī)則的形式。第0層是空集，第1層是所有的單元集，第2層是所有的2元子集，…，直到最高層的集合A。這里的蓋住關(guān)系就體現(xiàn)為包含關(guān)系。在畫哈斯圖時應(yīng)該注意下面幾個問題。1°哈斯圖中不應(yīng)該出現(xiàn)三角形，如果出現(xiàn)三角形，一定是蓋住關(guān)系沒有找對。糾正的方法是重新考察這3個元素在偏序中的順序中的順序，然后將不滿足蓋住關(guān)系的那條邊去掉。請看圖4.6(1)中的哈斯圖。圖中有兩個三角形，即三角形abc和abd。根據(jù)結(jié)點(diǎn)位置可以看出滿足如下的偏序關(guān)系：ab,ac,bc,ad,bd從而得到和abd。這就說明c和d不蓋住a，abc應(yīng)該把a(bǔ)c邊和ad邊從圖中去掉，從而得到正確的哈斯圖，如圖4.6(2)所示。2°哈斯圖中不應(yīng)該出現(xiàn)水平線段。根據(jù)哈斯圖的層次結(jié)構(gòu)，處在同一水平位置的結(jié)點(diǎn)是同一層的，它們沒有順序上的“大小”關(guān)系，是不可比的。出現(xiàn)這種錯誤的原因在于沒有將“較大”的元素放在“較小”元素的上方。糾正時只要根據(jù)“大小”順序?qū)ⅰ拜^大”的元素放到更高的一層，將水平線改為斜線就可以了。3°哈斯圖中應(yīng)盡量減少線的交叉，以使得圖形清晰、易讀，也便于檢查錯誤，圖形中線的交叉多少主要取決于同一層結(jié)點(diǎn)的排列順序，如果出現(xiàn)交叉過多，可以適當(dāng)調(diào)正結(jié)點(diǎn)的排列順序，注意變動結(jié)點(diǎn)時要同時移動連線。最后談?wù)勗鯓哟_定哈斯圖中的極大元、極小元、最大元、最小元、最小上界和最大下界，具體的方法是：1°如果圖中有孤立結(jié)點(diǎn)，那么這個結(jié)點(diǎn)既是極小元，也是極大元，并且圖中既無最小元，也無最大元（除了圖中只有唯一孤立結(jié)點(diǎn)的特殊情況）。2°除了孤立結(jié)點(diǎn)以外，其他的極小元是圖中有所向下通路的終點(diǎn)，其他的極大元是圖中有所向上通路的終點(diǎn)。3°圖中唯一的極小元是最小元，唯一的極大元是最大元；否則最小元和最大元不存在。4°設(shè)B為偏序集A,的子集，若B中存在最大元，它就是B的最小上界；否則，從A-B中選擇那些向下可達(dá)B中每一個元素的結(jié)點(diǎn)，它們都是B的上界，其中的最小元是B的最小上界。類似地可以確定B的最大下界。觀察圖4.5,1是有所向下通路的終點(diǎn)，是極小元，也是最小元，向上通路的終點(diǎn)有9，6，8，10和7，這些是極大

元。由于極大元不是唯一的，所以，沒有最在元。地于整個偏序集的最小上界和最大下界，就是它的最在元和最小元，因此，該偏序集沒有最小上界，最大下界是1。4.7A：④；B：⑤；C：③；D：①；E：⑦4.8A：②；B：①；C：④；D：②；E：⑨分析給定函數(shù)f:AB，怎樣判別它是否滿足單射性呢？通常是根據(jù)函數(shù)的種類采取不同的方法。1°若f:AB是實(shí)數(shù)區(qū)間上的連續(xù)函數(shù)，那么，可以通過函數(shù)的圖像來判別它的單射性。如果f的圖像是嚴(yán)格單調(diào)上升（或下升）的，則f是單射的。如果在的f圖像中間有極大或極小值，則f不是單射的。2°若f不是通常的初等函數(shù)。那么，就須檢查在的對f應(yīng)關(guān)系中是否存在著多對一的形式，如果存在x,xA,xx1212但，這就是二對一，即兩個自變量對應(yīng)于一個函f(x)f(x)12數(shù)值，從而判定不是單射的。f下面考慮滿射性的判別，滿射性的判別可以歸結(jié)為f的值域ranf的計(jì)算。如果ranfB，則f:AB是滿射的，否則不是滿射的。求ranf的方法說明如下：1°若f:AB是實(shí)數(shù)區(qū)間上的初等函數(shù)，為了求ranf首先要找到f的單調(diào)區(qū)間。針對f的每個單調(diào)區(qū)間求出f的該區(qū)音的最小和最大值，從而確定在這個區(qū)間的局部值。域franf就是所有局部值的域并集。對于分段的初等函數(shù)也可以采用

這種方法處理。2°若f是用列元素的方法給出的，那么ranf就是所有有序?qū)Φ牡诙貥?gòu)成的集合。本題中只有f是定義于實(shí)數(shù)區(qū)間上的初等函數(shù)。易見，1指數(shù)函數(shù)的圖像是嚴(yán)格單調(diào)上升的，并且所有的函數(shù)值都大于0。從而知道f是單射的，但不是滿射的。對于f，由12可知，它不是單射的。但，所ranfNf(1)f(1)1222以，它是滿射的。既不是單射的，也不是滿射的，因?yàn)閒3且是單射的，但不是滿射的。因?yàn)閒(3)f(0)0,f{0,1,2}.f3334mn時,必有m,m1n,n1,但1,1ranf.44.10A：③；B：①；C：⑦；D：⑤；E：⑨分析（1）先求出T的特征函數(shù)，{a,1,b,1,c,0}T它是從S到{0,1}的函數(shù)。而Ss中的函數(shù)是從{a,b,c}到{a,b,c}的函數(shù)，這就是說該函數(shù)應(yīng)包含3個有序?qū)?，有序?qū)Φ牡谝辉厥莂,b,c，而第二元素應(yīng)該從a,b,c中選?。梢灾貜?fù)選取）。不難年出只有①滿足要求。（2）等價關(guān)系R對應(yīng)的劃分就是商集S/R。檢查R的表達(dá)式，如果x,yR，那么x,y就在同一個等價類。不難看出S中的元素被劃分成兩個等價類：{a,b},{c}，因而對應(yīng)的劃分有2個劃分。塊考慮自然映射g:SS/R,它將S中的元素所在的等價類，即將a映到[a]{a,b}，將b映到[b]{a,b}，將c映到[c]{c}，

將g寫成集合表達(dá)式就是g{a,{a,b},b,{a,b},c{c}}.通常的自然映射是滿射的，但不一定是單射的，除非等價關(guān)系為恒等關(guān)系，這時每個等價類只含有一個元素，不同元素的等價類也不同，g就成為雙射函數(shù)了。4.11(1)R{1,1,1,2,1,3,1,4,1,5,1,6,2,2,2,4,2,6,3,3,3,64,4,5,5,6,6}.(2)R{1,1,2,1,2,2,3,1,3,3,4,1,4,2,4,4,5,1,5,5,6,16,2,6,3,`6,6}.(3)R{1,2,1,3,2,1,2,3,2,4,3,1,3,2,3,4,3,5,4,2,4,34,5,4,6,5,3,5,6,6,4,6,5}.]4.12對稱性4.13RR{c,d},RR{a,d,a,c},1221R2{a,a,a,b,a,d},R3{b,c,c,b,b,d},124.14圖4.7分析根據(jù)閉包的計(jì)算公式r(R)RR0,s(R)RR1,t(R)RR2可以得到由關(guān)系圖求閉包的方法.設(shè)G是R的關(guān)系圖,G的結(jié)點(diǎn)記為n的x,x,,x,r(R),s(R),t(R)12關(guān)系圖分別記作和.G,GrGts為求,先將圖G的結(jié)點(diǎn)和邊拷貝到中，缺少環(huán)的結(jié)GGrr點(diǎn)都加上環(huán)就得到了的關(guān)系圖.r(R)為求,也須將圖G拷貝到,然后檢查的每一對結(jié)點(diǎn)GGGsss和.如果在和之間只存在一條單向的邊,就在這xx(ij)xxijij兩個結(jié)點(diǎn)間加上一條方向相反的邊.當(dāng)中所有的單向邊都Gs變成雙向邊以后，就得到了的關(guān)系圖.s(R)最后考慮.首先將圖G拷貝到,然后從開始依次檢xGGtt1查.在檢查結(jié)點(diǎn)時，要找出從出發(fā)經(jīng)過x(i1,2,,n)ix,x,,xxi12n有限步（至少1步，至多n步）可達(dá)的所結(jié)點(diǎn)（包括自己xi在內(nèi)）。如果從到這種結(jié)點(diǎn)之間缺少邊，就把這條邊加到xiGt中，當(dāng)n個結(jié)點(diǎn)全部處理完畢，就得到的關(guān)系圖。t(R)以本題為例，依次檢查結(jié)點(diǎn)從a出發(fā)可達(dá)四a,b,c,d.b,c,d,e個結(jié)點(diǎn)，所以圖中應(yīng)該加上ac,ad和的邊。從b出發(fā)可Gt達(dá)三個結(jié)點(diǎn)，所以，圖中G應(yīng)該加上的邊。從c出c,d,ebdt發(fā)可達(dá)c和d，在中G應(yīng)該加上邊，即通過c的環(huán)，類cct似地分析可以知道，在中還應(yīng)該加上過d的環(huán)。Gt4．15若S不是單元集，則P(S){}不構(gòu)成S的劃分。

4．16在圖4.8（1）中極小元、最小元是1，極大元、最大元是24，在圖4.8(2)中極小元、最小元是1，極大元是5，6，7，8，9，沒有最大元。4．17（1）不能；（2）能；（3）不能。分析函數(shù)和關(guān)系的區(qū)別在于它們的對應(yīng)法則。在關(guān)系R的表達(dá)式中，如果x,yR，就說x對應(yīng)到y(tǒng)，對于二元關(guān)系R，這種對應(yīng)可以是一對一的，多對一的和一對多的。這里的一對多指的是一個x對應(yīng)到多個y，但是對于函數(shù)，則不允許這種一對多的對應(yīng)。至于單射函數(shù)，不但不允許一對多，也不允許多對一，只能存在一對一的對應(yīng)。為了判別一個關(guān)系是否為函數(shù)，就要檢查關(guān)系的對應(yīng)中是否存在一對多的情況。如本題中的（1）式，<1,2>和<1,1>同時在關(guān)系中出現(xiàn)，因此不是函數(shù)。又如（3）式，<1,1>和<1,-1>也同時在關(guān)系中出現(xiàn)，破壞了函數(shù)定義。4．18當(dāng)RI時滿足要求。S4．19ff,gf,fg,hg,fghNN，且ff(n)n2.gf(n)2n2,fg(n)2n1.0n為偶數(shù)hg(n)0,gh2n為奇數(shù),1n為偶數(shù)fgh(n)3n為奇數(shù).分析注意合成的正確表示方法。表示和合成的方法fg有兩種：1°說明fg是從哪個集合fg(x)的計(jì)算公式。2°給出fg的集合表到個集合的函數(shù)，然后給出達(dá)式。本題中的結(jié)果都采用了第一種表示方法，先說明地果函數(shù)是從N到N的函數(shù)，然后分別給出函數(shù)值的計(jì)算公式。也可以彩用第二種方法，如,ff{n,n2|nN}fgh{x,1,y,3z|x,yN且x為偶數(shù),y為奇數(shù)}.但是，如果寫成ffn2就錯了，因?yàn)閒f是函數(shù)，是有序?qū)Φ募希c函數(shù)值ff(n)是根本不同的兩回事，不能混為一談。4．20f1:RRRR,f(x,y)xy,xy.122分析首先由f的雙射性確定f1一定存在，然后通過f的定義求出反函數(shù)的對應(yīng)法則。設(shè)f將x,y對應(yīng)到u,v。根據(jù)f的定義有u,vxy,xyxyuxyv2xuv2yuvxuvyuv.22uv,uv因而反函數(shù)的對應(yīng)法則是u,v對應(yīng)到。224．21（1）如下列出的對應(yīng)關(guān)系gf012345678…x123405678…f(x)313203334…g(f(x))從而得到gf:NN3x0,2或大于等于5的奇數(shù)1x1gf(x)2x3xx6且x為偶數(shù)20x4是滿射的，但不是單射的。gf（2）gf({0,1,2}){1,3}.4．22（1）P(A){,{a},,{a,b}},其中BA{f,f,f,f},1234f{a,0,{b,0,f{a,0b,1},12f{a,1,{b,0,f{a,1b,1},24（2）令f:P(A)BA，且f()f,f({a})f,f()f,f({a,b})f4123分析對于任意集合A，都可以構(gòu)造從到的雙射P(A){0,1}A函數(shù)，任取A的子集BP(A),B的特征函數(shù):A{0,1}定義為B1xB0xABB(x)不同的子集的特征函數(shù)也不同，因此，令:P(A){0,1}A(B)B是到的雙射，在本題的實(shí)例中的是P(A){0,1}A()f,({a})f,13()f,({a,b})f.244．23（1）f:AB,f(x)2x（2）f:AB,f(x)sinx.分析給定集合A，B，如何構(gòu)造從A到B的雙射？一般可采用下面的方法處理。1°若A，B都是有窮集合，可以先用列元素的方法表示A，B，然后順序?qū)中的元素與B中的元素建立對應(yīng)，如習(xí)題4.22.1°若A，B都是有窮集合，可以先用列元素的方法表示A，B，然后順序?qū)中的元素與B中的元素建立對應(yīng)，如習(xí)題4.22。2°若A，B是實(shí)數(shù)區(qū)間，可以采用直線方程作為從A到B的雙射函數(shù)。例如，A[1,2],B[2,6]是實(shí)數(shù)區(qū)間。如圖4.9所示，先將A，B區(qū)間分別標(biāo)記在直角坐標(biāo)系的x軸和y軸上，過（1，2）和（2，6）兩點(diǎn)的直線方程將A中的每個數(shù)映到B中的每個數(shù)，因此，該直線方程所代表的一次函數(shù)就是從A到B的雙射函數(shù)。由解析幾何的知識可以得到雙射函數(shù)f:AB,f(x)4x2.這種通過直線方程構(gòu)造雙射函數(shù)的方法對任意兩個同類型的實(shí)數(shù)區(qū)間(同為閉區(qū)間、開區(qū)間或音開半閉的區(qū)間)都是適用的。但對半開半閉的區(qū)間要注意開端點(diǎn)與開端點(diǎn)對應(yīng)，閉端點(diǎn)與閉端點(diǎn)對應(yīng)。此外還要說明一點(diǎn)，對于某些特殊的實(shí)數(shù)區(qū)間可能選擇其他嚴(yán)格單調(diào)的初等函數(shù)更方便，例如，，