離散習題答案 馮偉森

1、習題參考解答習題一 1、（1）設(shè)P：他是本片的編劇， Q：他是本片的導演。 PQ（2）設(shè)P：銀行利率很低， Q：股價上揚。 PQ（3）設(shè)P：銀行利率很低， Q：股價上升。 （PQ）（4）設(shè)P：這個對象是占空間的，Q：這個對象是有質(zhì)量的，R：這個對象是不斷變化的，S：這個對象稱為物質(zhì)。PQRS（5）設(shè)P：他今天乘火車去了北京，Q：他今天隨旅行團去了九寨溝。PQ（6）設(shè)P：小張身體單薄，Q：小張極少生病，R：小張頭腦好使。PQR（7）設(shè)P：這個人不識廬山真面目，Q：這個人身在廬山中。PQ（8）設(shè)P：兩個三角形相似，Q：兩個三角形的對應角相等或者對應邊成比例。PQ（9）設(shè)P：一個整數(shù)能被6整除，Q：

2、這個整數(shù)能被2和3整除。PQ設(shè)R：一個整數(shù)能被3整除，S：這個整數(shù)的個位數(shù)之和也能被3整除。RS2、（1）命題 T（2）命題 T/F（3）不是命題，因為真值無法確定。（4）命題 T（5）不是命題。（6）命題 T（7）命題 T/F（8）不是命題，是悖論。5、（1）證：（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（P（QQ）（PQ）（P（PQ）P（3）證：P（QR）P（QR） PQRR （PQ）（RR） （PQ）（PR） 6、 解：如果PQQR，不能斷定PR。因為當Q=T時，PQQR恒成立。如果PQQR，不能斷定PR。因為當Q=F時，PQQR恒成立。如果PR，則PR。8

3、、 把下列各式用等價表示出來：（1）解：（PQ）P（PQ）（ PQ）（PP） （PQ）（ PQ）（PQ）（PQ）（PP）（PP） （1）解：（P（QR）P（P（QR）P（PP）（Q（RR）（PP）（PP）（QQ）（RR）（PP）（PP）（PP）（QQ）（RR）（RR）（QQ）（RR）（PP）（PP）（PP）（QQ）（RR）（RR）（QQ）（RR）（RR）（PP）（PP)（PP）（QQ）（RR）（RR）（QQ）（RR）（RR）（PP）9、 證：PQPQ（P）QPQ（PQ）（PQ）而，是功能完備集，是功能完備集，不能互相表示，故，是最小功能完備集。10、 證：由書上的表1.16可知，“”對應的真值

4、表含2個1和2個0，而“”對應的真值表也含2個1和2個0，對應的真值表含3個1和1個0，對應的真值表含1個1和3個0，所以，“”無法用“”和“”來表示，同樣“”也無法用“”和“”來表示，因此，不是功能完備集。10、 解：（1） a）真值表法由表中可以看出，14、 解：由題設(shè)A：A去，B：B去，C：C去，D：D去則滿足條件的選派應該是如下范式：（A（CD）（BC）（CD）構(gòu)造和以上范式等價的主析取范式共有八個極小項，但根據(jù)題意，需根據(jù)題意，需派出兩人出差，所以，只有其中三項滿足要求：（ABCD），（ABCD），（ABCD）即有三種方案：A和C去或者A和D去或者B和D去。15、 證：（1）由定理1

5、.11，需證（PQ）（P（PQ）為永真式（3）由定理1.11，需證PPRS為永真式16、 證：（1）性質(zhì)1 由定理1.11和“”的定義，AA是永真式，所以A=A。（2）性質(zhì)2 由定理1.11，A=B，B=A，AB和B是永真式，即A是永真式，由定理1.3，AB成立。（3）性質(zhì)3 由定理1.11，A=B，AB是永真式，又A是永真式，根據(jù)“”的定義，B必是永真式。17、 證：“=”，A=B，AB是永真式，“A，必有A=B。18、 解： 設(shè) P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在還原正中地下T：后院栽有香樟樹M：珍寶藏在附近（后院）對語句符號化后得到以下蘊含式：Q

6、P，RP，Q，RS，TM=?所以S為真，即珍寶藏在花園正中地下。19、 解：（1）不成立（P=0，Q=1）（2）不成立（P=1，Q=R=0）（3）不成立（P=0，Q=1）（4）不成立（P=0，Q=1，R=0）（5）不成立（P=1，Q=1，R=0）20、 證：（1）利用CP規(guī)則P P（附加前提規(guī)則）PQ PQ TRQ P QR TE23R TPR CP規(guī)則（2）利用CP規(guī)則P P（附加前提規(guī)則）PQ TE3（PQ）（RS） PRS TI5S TE4SE TE3（SE）B PB TI5PB CP規(guī)則（4）（反證法）21、 把下列句子防疫成邏輯形式，并給出證明。（1）如果資方拒絕增加工資，那么罷工不

7、會結(jié)束；除非罷工超過一年，并且資方撤換了經(jīng)理；現(xiàn)在資方拒絕了增加工資，罷工剛開始，判斷罷工能否停止。（2）某公司發(fā)生了一起盜竊案，經(jīng)仔細偵查，掌握了如下一些事實：被盜現(xiàn)場沒留下任何痕跡；失竊時，小花或者小英正在卡拉OK廳；如果失竊時小胖正在附近，他就會習慣性的破門而入偷走東西后揚長而去；如果小花正在卡拉OK廳唱歌，那么金剛是最大的嫌疑者；如果失竊時小胖不再附近，那么他的女友小英會和他一起外出旅游；如果失竊時小英正在卡拉OK廳唱歌，那么瘦子是最大的嫌疑者。根據(jù)以上事實，請通過演繹推理找出偷竊者。22、（1）不相容（2）相容（P=1，R=Q=S=0）（3）不相容（4）不相容23、（1）證：（PQ）

8、（QS）（SQ）（PQ）P習題 二6、（1）F，（2）A為F；B為T；C為T，E為F。7、（1）F，（2）T，（3）F，（4）T8、解：個體域D：實數(shù)集：17、(1) 錯誤，應換元，即(2) 正確(3) 錯誤，a、b應是同一個常元18、(2) 證：首先，將結(jié)論否定作為前提加入到原有前提中習題 三習題 四習題 五4、解：每個集合的劃分就可以確定一個等價關(guān)系集合有多少個劃分就可以確定多少個等價關(guān)系不同的劃分的個數(shù)為：不同的等價關(guān)系個數(shù)等于不同的劃分個數(shù)，所以不同的等價關(guān)系個數(shù)為15.習題 六習題 十1、設(shè)G是一個（n，m）簡單圖。證明：，等號成立當且僅當G是完全圖。2、設(shè)G是一個（n，n+1）的無

9、向圖，證明G中存在頂點u，d(u)3。證明：反證法，假設(shè)，則G的總點度上限為max（d(u)）2n，根據(jù)握手定理，圖邊的上限為max（m）2n/2=n。與題設(shè)m=n+1矛盾，因此，G中存在頂點u，d(u )3。3、確定下面的序列中哪些是圖的序列，若是圖的序列，畫出一個對應的圖來：（1）（3,2,0,1,5）； （2）（6,3,3,2,2）（3）（4,4,2,2,4）； （4）（7,6,8,3,9,5）解：除序列（1）不是圖序列外，其余的都是圖序列。因為在（1）中，總和為奇數(shù)，不滿足圖總度數(shù)為偶數(shù)的握手定理?？梢园慈缦路椒?gòu)造滿足要求的圖：序列中每個數(shù)字ai對應一個點，如果序列數(shù)字是偶數(shù)，那么就

10、在對應的點上畫ai/2個環(huán)，如果序列式奇數(shù)，那么在對應的點上畫（ai-1）/2個環(huán)。最后，將奇數(shù)序列對應的點兩兩一組，添加連線即可。下面以（2）為例說明：每個節(jié)點對應的環(huán)數(shù)（6/2，（3-1）/2，（3-1）/2，2/2，2/2）=（3,1,1,1,1）將奇數(shù)3,3對應的節(jié)點V2，V3一組，畫一條連線其他序列可以類似作圖，當然大家也可以畫圖其他不同的圖形。4、證明：在（n，m）圖中2m/n。證明：圖的點度數(shù)是一組非負整數(shù)d(v1),d(v2).d(vn)，那么這組數(shù)的算術(shù)平均值一定大于等于其中的最小值，同時小于等于其中的最大值。對應到圖的術(shù)語及為：最大值為，最小值為，平均值=（d(v1)+d(

11、v2).+d(vn)）/n=2m/n，所以2m/n。5、證明定理10.2?！径ɡ?0.2】對于任何（n，m）有向圖G=（V,E），證明：有向圖中，每條有向邊為圖貢獻一度出度，同時貢獻一度入度，所以總出度和入度相等，并和邊數(shù)相等。因此，上述關(guān)系等式成立。7、無向圖G有21條邊，12個3度數(shù)結(jié)點，其余結(jié)點的度數(shù)均為2，求G的階數(shù)n。解：根據(jù)握手定理有：21=（312+2（n-12）/2，解次方程得n=15。10、判斷圖10.29中的兩個圖是否同構(gòu)，并說明理由。解：題中兩個圖不同構(gòu)，因為左邊圖的唯一3度點有2個1度點為其鄰接點，而右圖唯一的3度點只有1個1度點為其鄰接點。因此這兩個圖不可能同構(gòu)。13

12、、設(shè)有向圖D=如下圖10.31所示。（1）在圖中找出所有長度分別為1,2,3,4的（至少用一種表示法寫出它們，并以子圖形式畫出它們。）（2）在圖中找出所有長度分別為3,4,5,6的回路，并以子圖形式畫出它們。解：（1）15、若u和v是圖G中僅有的兩個奇度節(jié)點，證明u和v必是連通的。證明：反證法，假設(shè)u和v不連通，那么它們必然分布于此圖的兩個連通分支中。那么它們將分別是各連通分支中唯一的奇數(shù)度節(jié)點。根據(jù)握手定理，一個圖中奇度點的個數(shù)為偶數(shù)。而兩個連通分支中，奇度點的個數(shù)為奇數(shù)。矛盾。矛盾的產(chǎn)生是由于假設(shè)不連通導致的，因此，題設(shè)結(jié)論成立。18、設(shè)G施階數(shù)不小于3的連通圖。證明下面四條命題相互等價：

13、（1）G無割邊；（2）G中任何兩個結(jié)點位于同一回路中；（3）G中任何一結(jié)點和任何一邊都位于同一回路中；（4）G中任何兩邊都在痛一回路中。證明：（1）=（2）因為G連通，且G無割邊，所以任意兩個結(jié)點u，v，都存在簡單道路p=u.wv。又因為G無割邊，所以，刪除邊wv后，子圖依然連通，即w，v存在簡單道路p，以此類推，可以找到一個核p每條邊都不相同的p=v.u，這樣p和p就構(gòu)成了一條回路。證明：（2）=（3）因為G中任意兩個結(jié)點都位于同一回路中，所以任意結(jié)點u和任意邊e的兩個端點v1,v2都分別在兩個回路C1，C2中，如果C1-C2=u.v1.v2.u，那么將回路中v1.v2，用v1v2=e替換，

14、就得到新的回路，并滿足要求。如果C1C2，C1=u.v1.u,C2=u.v2.u，那么構(gòu)成新的道路P=u.v1.u.v2.u，在其中將重復邊剔除，得到新的回路C3，其中包含v1，v2結(jié)點，可以講回路中v1.v2用v1v2=e替換，就得到新的回路，并滿足要求。證明：（3）=（4）對任意兩條邊e1,e2其端點分別為u1,u2,v1,v2.根據(jù)（3）存在回路C1=u1.v1v2.u1,C2=u2.v1v1.u2.那么可以形成新的閉道路P=u1.v1v2.u2.v1v2.u1，在其中將重復邊剔除，得到新的回路C3，其中包含e2和u1,u2結(jié)點，可以將回路中u1.u2用u1u2=e1替換，就得到新的回路

15、，包含e1,e2,滿足要求。證明：（4）=（1）因為任意兩條吧都在同一回路中，所以不存在割邊。假設(shè)邊e是割邊，那么刪除此邊，圖不連通，分支中的任何一對不再同一分支中的邊，不能構(gòu)成回路，與條件矛盾。所以，G中無割邊。23、證明：在具有n（n2）個結(jié)點的簡單無向圖G中，至少有兩個結(jié)點的度數(shù)相同。證明：此題可用鴿巢原理，因為n個結(jié)點的簡單無向圖G中，結(jié)點的度數(shù)只可能是0,1,2.n-1這n個數(shù)，又因為如果有結(jié)點的度數(shù)為0，那么就不可能有結(jié)點的度為n-1，反之亦然。所以n個結(jié)點，最多有n-1中度數(shù)，其中必有至少2個結(jié)點的度數(shù)相同。24、設(shè)G是2的簡單圖。證明：G中必有長度至少為+1的圖。證明：設(shè)p=u

16、. v是滿足題設(shè)要求圖G中的最長基本道路，那么d(u),d(v)都應該大于等于。那么u,v的鄰接點都應該在道路p上，否則此道路可以延長，與其是最長路假設(shè)矛盾。如果u,v是鄰接點，那么可以構(gòu)成一個圈c=u.vu，其長度+1.如果u,v不是鄰接點，那么從p的終點開始刪除點，知道其為u的鄰接點為止，得到道路p,可知道路p，依然保持u的所有鄰接點都在p上的性質(zhì)，所以可構(gòu)成一個圈c=u.uu,其長度+1，證畢。25、證明：G是單向連通圖當且僅當存在一條包含G中全部結(jié)點的有向道路。證明：假設(shè)不存在包含全部結(jié)點的有向道路，那么設(shè)p=v1v2.v,k是G中最長的有向道路，且u結(jié)點不包含在此有向道路中。u和此道

17、路中任何中間結(jié)點都不可能雙向可達，且u不能到達V1，且vk也不能到達u，否則，此最長路克擴充。那么憂郁道路上的每個結(jié)點和u都單向可達,所以此最長路和u之間的可達關(guān)系必然如下圖所示：當k為偶數(shù)時，道路克擴充為，而當k為奇數(shù)時，不管與u之間是如火熱單向可達的，都可以構(gòu)造出更長的有向道路，矛盾，所以G中一定存在包含所有結(jié)點的有向道路。26、無向圖G如圖10.32所示，先將此圖頂點和邊標出，然后求同種的全部割點和割邊。圖10.32解：標注如下所示：根據(jù)標記后的圖，可求得割點分別為：u4，u7，u8，割邊分別為：u4u5,u7u8,u8u9。27、求圖10.33的全部強分圖和單向分圖。解：標圖重新標記如

18、下：因此，此圖有兩個強分圖，一個包含一個結(jié)點v9，一個包含其他的8個結(jié)點。由于兩個強分圖之間存在有向道路，因此全部9個結(jié)點，構(gòu)成了單向分圖。28、證明：一個聯(lián)通無向簡單圖中，任意兩條邊最長路至少有一個公共頂點。證明：假設(shè)兩條最長路p1=v1v2.vk,p2=u1u2.uk沒有公共點，那么鏈條道路上的點集之間就有道路相連，否則就不是連通圖了。設(shè)此道路起點是p1上m點，終點是p2上w點，可根據(jù)如下情況進行調(diào)論：（1）m,w是p1,p2的中間結(jié)點，那么可構(gòu)成新道路p=v1v2.m.w.uk，此路至少比p1長1,矛盾。（2）假設(shè)m和w不能均分p1,p1，那么可以將兩個長路段和m,w之間的道路進行拼接，

19、那么可得到比p1長的道路，與p1,p2是最長路矛盾。因此任意兩條最長路至少有一個公共點。29、證明：若G是n階無向簡單圖，G中每一對不相鄰的頂點的度數(shù)之和至少是n-1,則G 是連通圖。證明：假設(shè)G不是連通圖，G1，G2是G的兩個連通分支，分別為n1,n2階連通無向簡單子圖，則n1+n2n。對G1中任意結(jié)點v1和G2中任意結(jié)點v2而言，v1的最大點度為n1-1，v2的最大點度為n2-1；則v1,v2的點度之和，最大為n1+n2-2n-1.與題設(shè)條件矛盾，因此，原題設(shè)結(jié)論成立。30、求出圖10.34的鄰接矩陣、可達矩陣、強分圖和關(guān)聯(lián)矩陣。解：對圖的結(jié)點和邊進行編號如下：習題 十一19、給定權(quán)1,4

20、,9,1,2,6,4,6,8,10構(gòu)造一個最優(yōu)二叉樹。解：根據(jù)帶權(quán)最優(yōu)二叉樹定理構(gòu)造過程如下：21、證明：正則二叉樹必有奇數(shù)個結(jié)點，且樹葉數(shù)t與結(jié)點數(shù)n之間有：t=（n-1）/2。證明：因為正則二叉樹的邊數(shù)m與分支點數(shù)i的關(guān)系為：m=2i，又因為是樹，因此結(jié)點數(shù)n滿足：n=m-1=2i-1，必為奇數(shù)。葉結(jié)點數(shù)t和枝結(jié)點數(shù)之和為n，即：t+i=n，因此t=(n-1)/2習題 十二1、證明下面3個圖都是平面圖。證明：因為所給圖都可以以平面圖的方式畫出來，如下：2、下面3個圖都是平面圖，先給圖中各邊標定順序，然后求出圖中各面的邊界和面度。解：略5、證明：少于30條邊的簡單平面圖至少有一個頂點的度不大

21、于4。證明：假設(shè)圖G（n，m）的每個結(jié)點的度到大于等于5，根據(jù)握手定理及平面圖的判定定理有：5n2m60 （1）握手定理m3n-6 （2）根據(jù)（1）得：n12結(jié)合（1）（2）得：5n/23n-6，所以n12，矛盾。因此假設(shè)不成立，題設(shè)結(jié)論成立。習題 十三1、構(gòu)造（n，m）歐拉圖使?jié)M足條件：（1）m和n奇偶性相同；（2）m和n奇偶性相反。解：5、在圖13.10中求中國郵遞員問題的解。解：略，請參考書中解法。6、設(shè)G施有兩個奇度點的連通圖，設(shè)計一個構(gòu)造G的歐拉道路的算法。解：step1：添加鏈接兩個奇度點的邊step2：調(diào)用一般的歐拉回路的算法step3：在回路中刪除添加的邊8、n（n2）個結(jié)點的

22、有向完全圖中，哪些是歐拉圖？解：n（n2）個結(jié)點的有向完全圖中,每個都是歐拉圖，因為每個結(jié)點都有相同的入讀和出度，可以找到有向歐拉回路。9、證明：凡有割點的圖都不是哈密頓圖。10、證明：4k+1階的所有2k正則簡單圖都是哈密頓圖。11、在無向完全圖中Kn中有多少條沒有公共邊的哈密爾頓回路？12、11個學生打算幾天都在一張圓桌上共進午餐，并且希望每次午餐時每個學生兩旁所坐的人都不相同，問11人共進午餐最多能有多少天？解：將11個學生分別用結(jié)點表示，由于每個同學都可能鄰座，因此每兩個結(jié)點之間都有一條邊，因此得到無向完全圖K11，每次午餐時學生都按照一條哈密爾頓回路落座，如果兩條哈密爾頓回路有公共邊，則公共邊端點所代表的學生就是相鄰的。因此上述問題轉(zhuǎn)化為求K11有多少條無公共邊的哈密爾頓回路問題，利用11題的結(jié)論，共有（11-1）/2=5條無公共邊的哈密