離散數(shù)學(xué)（第五版）清華大學(xué)出版社第4章習(xí)題解答

本文格式為Word版，下載可任意編輯——離散數(shù)學(xué)（第五版）清華大學(xué)出版社第4章習(xí)題解答離散數(shù)學(xué)（第五版）清華大學(xué)出版社第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)的計算或解答，例如，題4.1中的Is={,},Es={,,,}Is={,,};而題4.2中的

R={,,,,}.

為得到題4.3中的R須求解方程x+3y=12，最終得到R={,,}.

求RoR有三種方法，即集合表達(dá)式、關(guān)系矩陣和關(guān)系圖的主法。下面由題4.2的關(guān)系分別加以說明。1°集合表達(dá)式法

將domR,domRUran,ranR的元素列出來，如圖4.3所示。然后檢查R的每個有序?qū)?，若∈R，則從domR中的x到ranR中的y畫一個箭頭。若danR中的x經(jīng)過2步有向路徑到達(dá)ranR中的y，則∈RoR。由圖4.3可知RoR={,,,,,}.

假使求FoG，則將對應(yīng)于G中的有序?qū)Φ募^畫在左邊，而將對應(yīng)于F中的有序?qū)Φ募^畫在右邊。對應(yīng)的三個集合分別為domG,ranUdomF,ranF，然后，同樣地尋覓domG到ranF的2步長的有向路徑即可。2°矩陣方法

若M是R的關(guān)系矩陣，則RoR的關(guān)系矩陣就是M·M，也可記作M，在計算248

乘積時的相加不是普通加法，而是規(guī)律加，即0+0=0，0+1=1+0=1+1=1，根據(jù)已知條件得

?1001??1001??1001??1000??1000??1001?

2??????M=?????=??

?0001??0001??1000??1000??1000??1001?M2中含有7個1，說明RoR中含有7個有序?qū)?。圖4.3圖4.43°關(guān)系圖方法n''

設(shè)G是R的關(guān)系圖。為求R的關(guān)系圖G，無將G的結(jié)點(diǎn)復(fù)制到G中，然后依次檢查G的每個結(jié)點(diǎn)。假使結(jié)點(diǎn)x到y(tǒng)有一條n步長的路徑，就在G'中從x到y(tǒng)加一條有向邊。當(dāng)所有的結(jié)點(diǎn)檢查完畢，就得到圖G'。以題4.2為例。圖4.4（1）表示R的關(guān)系圖G。依次檢查結(jié)點(diǎn)1，2，3，4。從1出發(fā)，沿環(huán)走2步仍回到1，所以，G'中有過1的環(huán)。從1出發(fā)，經(jīng)和，2步可達(dá)4，所以，'中有從1到4的邊。結(jié)點(diǎn)1檢查完畢。類似地檢查其他3個結(jié)點(diǎn)，2G

步長的路徑還有2→1→1，2→1→4，3→4→1，4→1→1，4→1→4。將這些路徑'2

對應(yīng)的邊也加到G中，最終得到R的關(guān)系圖。這個圖給在圖4.4(2).4．4A：④；B：⑧；C：⑨；D：⑤；E：⑩

分析根據(jù)表4.1中關(guān)系圖的特征來判定R1,R2,LR5的性質(zhì)，如表4.2所示。表4.249

自反反自反對稱反對稱傳遞R√1R2R√3√√√√R4R5√√√√

從表中可知R1,R2和R3不是傳遞的，理上如下：在R1中有邊和，但缺少邊.在R2中有邊和，但缺少邊。在R3中有邊和，但缺少過1的環(huán)。

4.5A：①；B：③；C：⑧；D：⑨；E：⑤

分析等價關(guān)系和劃分是兩個不同的概念，有著不同的表示方法，等價關(guān)系是有序?qū)Φ募希鴦澐质亲蛹募?，切不可混淆起來，但是對于給定的集合A，A上的等價關(guān)系R和A的劃分π中一一對應(yīng)的，這種對應(yīng)的含義是∈R?x和y在π的同一劃分塊里。

拘句話說，等價說系R的等價類就是劃分π的劃分塊，它們表示了對A中元素的同一種分類方式。

給定劃分π，求對應(yīng)的等價關(guān)系R的方法和步驟說明如下：

1°設(shè)π中含有兩個以上元素的劃分塊有l(wèi)塊，記作B1,B2,L.Bt。若Bi={x1,x2,L,xj}，j≥2，則∈Ri,s,t=1,2,L,j,s≠t.求出R1,R2,L,Rt。2°R=R1UR2ULURtUIA.

此題中的π的劃分塊都是單元集，沒有含有個以上元素的劃分塊，所以，1

R=IA,π2含有兩個劃分塊，故對應(yīng)地等價關(guān)系含有兩個等價類。π3中只有一個劃分塊Z+.Z+包含了集合中的全體元素，這說明∈R?x,y∈Z+,因此，1

這個劃分塊對應(yīng)的關(guān)系R就Z+上的全域關(guān)系，從而得到R=RUI也是Z+上的11A全域關(guān)系。

4．6A：③；B：⑩；C：⑤；D：⑩；E：⑤50

分析畫哈斯圖的關(guān)鍵在于確定結(jié)點(diǎn)的層次和元素間的蓋住關(guān)系，下面探討一下畫圖的基本步驟和應(yīng)當(dāng)注意的問題。畫圖的基本步驟是：

1°確定偏序集中的微小元，并將這些微小元放在哈斯圖的最底層，記為第0層。

2°若第n層的元素已確定完畢，從A中剩余的元素中選取至少能蓋住第n層中一個元素的元素，將這些元素放在哈斯圖的第n+1層。在排列第n+1層結(jié)點(diǎn)的位置時，注意把蓋住較多元素的結(jié)點(diǎn)放在中間，將只蓋住一個元素的結(jié)點(diǎn)放在兩邊，以減少連績的交織。

3°將相鄰兩層的結(jié)點(diǎn)根據(jù)蓋住關(guān)系進(jìn)行連線。

以此題的偏序集為例，1可以整除S中的全體整數(shù)，故1是最小元，也是唯一的微小元應(yīng)當(dāng)放在第0層。是1的倍數(shù)，即2，3，5，7，S中剩下的元素是4，6，8，9，10。哪些應(yīng)當(dāng)放在第2層呢？根據(jù)蓋住關(guān)系，應(yīng)當(dāng)是4，6，9和10。由于4蓋住，2，6蓋住2和3，9蓋住3，10蓋住2和5.8不蓋住2，3，5，7中的任何一個元素，最終只剩下一個8放在第3層。圖4.5給出了最終得到的哈斯圖。在整除關(guān)系的哈斯圖中，蓋住關(guān)系表達(dá)為最小的倍數(shù)或最小的公倍數(shù)關(guān)系。假使偏序集是，那么哈斯圖的結(jié)構(gòu)將浮現(xiàn)出十分規(guī)則的形式。第0層是空集?，第1層是所有的單元集，第2層是所有的2元子集，…，直到最高層的集合A。這里的蓋住關(guān)系就表達(dá)為包含關(guān)系。在畫哈斯圖時應(yīng)當(dāng)注意下面幾個問題。

1°哈斯圖中不應(yīng)當(dāng)出現(xiàn)三角形，假使出現(xiàn)三角形，一定是蓋住關(guān)系沒有找51

對。改正的方法是重新考察這3個元素在偏序中的順序中的順序，然后將不滿足蓋住關(guān)系的那條邊去掉。請看圖4.6(1)中的哈斯圖。圖中有兩個三角形，即三角形abc和abd。根據(jù)結(jié)點(diǎn)位置可以看出滿足如下的偏序關(guān)系：apb,apc,bpc,apd,bpd

從而得到apbpc和apbpd。這就說明c和d不蓋住a，應(yīng)當(dāng)把a(bǔ)c邊和ad邊從圖中去掉，從而得到正確的哈斯圖，如圖4.6(2)所示。

2°哈斯圖中不應(yīng)當(dā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為偏序集的子集，若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。52

4.7A：④；B：⑤；C：③；D：①；E：⑦4.8A：②；B：①；C：④；D：②；E：⑨

分析給定函數(shù)f:A→B，怎樣判別它是否滿足單射性呢？尋常是根據(jù)函數(shù)的種類采取不同的方法。

1°若f:A→B是實數(shù)區(qū)間上的連續(xù)函數(shù)，那么，可以通過函數(shù)的圖像來判別它的單射性。假使f的圖像是嚴(yán)格單調(diào)上升（或下升）的，則f是單射的。假使在f的圖像中間有極大或微小值，則f不是單射的。

2°若f不是尋常的初等函數(shù)。那么，就須檢查在f的對應(yīng)關(guān)系中是否存在著多對一的形式，假使存在x1,x2∈A,x1≠x2但f(x1)=f(x2)，這就是二對一，即兩個自變量對應(yīng)于一個函數(shù)值，從而判定f不是單射的。

下面考慮滿射性的判別，滿射性的判別可以歸結(jié)為f的值域ranf的計算。假使ranf=B，則f:A→B是滿射的，否則不是滿射的。求ranf的方法說明如下：

1°若f:A→B是實數(shù)區(qū)間上的初等函數(shù)，為了求ranf首先要找到f的單調(diào)區(qū)間。針對f的每個單調(diào)區(qū)間求出f的該區(qū)音的最小和最大值，從而確定f在這個區(qū)間的局部值域。ranf就是所有局部值域的并集。對于分段的初等函數(shù)也可以采用這種方法處理。

2°若f是用列元素的方法給出的，那么ranf就是所有有序?qū)Φ钠浯卧貥?gòu)成的集合。

此題中只有f1是定義于實數(shù)區(qū)間上的初等函數(shù)。易見，指數(shù)函數(shù)的圖像是嚴(yán)格單調(diào)上升的，并且所有的函數(shù)值都大于0。從而知道f1是單射的，但不是滿射的。對于f2，由

f2(1)=f2(?1)=1可知，它不是單射的。但ranf2=N，所以，它是滿射的。f3既不是單射的，也不是滿射的，由于f3(3)=f3(0)=0,且f3={0,1,2}.f4是53

單射的，但不是滿射的。由于m≠n時,必有≠,但?ranf4.4.9A：③；B：①；C：⑦；D：⑤；E：⑨

分析1）先求出T的特征函數(shù)χT={,,}，它是從S到{0,1}的函數(shù)。而Ss中的函數(shù)是從{a,b,c}到{a,b,c}的函數(shù)，這就是說該函數(shù)應(yīng)包含3個有序?qū)?，有序?qū)Φ牡谝辉厥莂,b,c，而其次元素應(yīng)當(dāng)從a,b,c中選?。梢灾貜?fù)選取）。不難年出只有①滿足要求。

（2）等價關(guān)系R對應(yīng)的劃分就是商集S/R。檢查R的表達(dá)式，假使∈R，那么x,y就在同一個等價類。不難看出S中的元素被劃分成兩個等價類：{a,b},{c}，因而對應(yīng)的劃分有2個劃分塊。

考慮自然映射g:S→S/R它將,S中的元素所在的等價類，即將a映到[a]={a,b}，將b映到[b]={a,b}，將c映到[c]={c}，將g寫成集合表達(dá)式就是g={,,}.

尋常的自然映射是滿射的，但不一定是單射的，除非等價關(guān)系為恒等關(guān)系，這時每個等價類只含有一個元素，不同元素的等價類也不同，g就成為雙射函數(shù)了。4.11(1)

R={,,,,,,,,,,,,}.(2)

R={,,,,,,,,,,,,}.

(3)R={,,,,,,,,,,,,,,,}.]54

4.12對稱性4.13R1oR2={},R2oR1={,},R2={,,},1

R3={,,},24.14圖4.7

分析根據(jù)閉包的計算公式

r(R)=RUR0,s(R)=RUR?1,t(R)=RUR2UL可以得到由關(guān)系圖求閉包的方法.

設(shè)G是R的關(guān)系圖,G的結(jié)點(diǎn)記為x1,x2,L,xn,r(R),s(R),t(R)的關(guān)系圖分別記作Gr,Gs和Gt.

為求Gr,先將圖G的結(jié)點(diǎn)和邊拷貝到Gr中缺少環(huán)的結(jié)點(diǎn)都加上環(huán)就得到了r(R)的關(guān)系圖.

為求Gs,也須將圖G拷貝到Gs,然后檢查Gs的每一對結(jié)點(diǎn)xi和xj(i≠j).假使在xi和xj之間只存在一條單向的邊,就在這兩個結(jié)點(diǎn)間加上一條方向相反的邊.當(dāng)Gs中所有的單向邊都變成雙向邊以后就得到了s(R)的關(guān)系圖.

最終拷慮Gt.首先將圖G拷貝到Gt,然后從x1開始依次檢查x1,x2,L,xn.在55

檢查結(jié)點(diǎn)xi(i=1,2,L,n時，要找出從xi出發(fā)經(jīng)過有限步（至少1步，至多n步）)可達(dá)的所結(jié)點(diǎn)（包括xi自己在內(nèi)）。假使從xi到這種結(jié)點(diǎn)之間缺少邊，就把這條邊加到G中，當(dāng)n個結(jié)點(diǎn)全部處理完畢，就得到t(R)的關(guān)系圖。t

以此題為例，依次檢查結(jié)點(diǎn)a,b,c,d從a出發(fā)可達(dá)b,.c,d,e四個結(jié)點(diǎn)，所以圖Gt中應(yīng)當(dāng)加上a→c,a→d和的邊。從b出發(fā)可達(dá)c,d,e三個結(jié)點(diǎn)，所以，圖Gt中應(yīng)當(dāng)加上b→d的邊。從c出發(fā)可達(dá)c和d，在Gt中應(yīng)當(dāng)加上邊c→c，即通過c的環(huán)，類似地分析可以知道，在Gt中還應(yīng)當(dāng)加上過d的環(huán)。4．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á)式中，假使∈R，就說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）式，和同時在關(guān)系中出現(xiàn)，因此不是函數(shù)。又如（3）式，和也同時在關(guān)系中出現(xiàn)，破壞了函數(shù)定義。

4．18當(dāng)R=IS時滿足要求。56

4．19fof,gof,fog,hog,fogoh∈NN，且fof(n)=n+2.gof(n)=2n+2,fog(n)=2n+1.hog(n)=0,goh=?0n為偶數(shù)?2n為奇數(shù),?

?1n為偶數(shù)fogoh(n)=??3n為奇數(shù).

分析注意合成的正確表示方法。表示f和g合成的方法有兩種：1°說明fog是從哪個集合到個集合的函數(shù)，然后給出fog(x)的計算公式。

2°給出fog的集合表達(dá)式。

此題中的結(jié)果都采用了第一種表示方法，先說明地果函數(shù)是從N到N的函數(shù)，然后分別給出函數(shù)值的計算公式。也可以彩用其次種方法，如fof={|n∈N},

fogoh={,z|x,y∈N且x為偶數(shù),y為奇數(shù)}.

但是，假使寫成fof=n+2就錯了，由于fof是函數(shù)，是有序?qū)Φ募?，與函數(shù)值fof(n)是根本不同的兩回事，不能混為一談。4．20f?1:R×R→R×R,?1x+yx?y

f()=.

分析首先由f的雙射性確定f?1一定存在，然后通過f的定義求出反函數(shù)的對應(yīng)法則。設(shè)f將對應(yīng)到。根據(jù)f的定義有=?x+y=u∧x?y=v?2x=u+v∧2y=u?v?x=u+v∧y=u?v.22

因而反函數(shù)的對應(yīng)法則是對應(yīng)到u+v,u?v。22

4．21（1）如以下出gof的對應(yīng)關(guān)系57

x012345678…f(x)123405678…g(f(x))3