離散習(xí)題答案 馮偉森

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

2、這個(gè)整數(shù)能被2和3整除。PQ設(shè)R：一個(gè)整數(shù)能被3整除，S：這個(gè)整數(shù)的個(gè)位數(shù)之和也能被3整除。RS2、（1）命題 T（2）命題 T/F（3）不是命題，因?yàn)檎嬷禑o法確定。（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。因?yàn)楫?dāng)Q=T時(shí)，PQQR恒成立。如果PQQR，不能斷定PR。因?yàn)楫?dāng)Q=F時(shí)，PQQR恒成立。如果PR，則PR。8

3、、 把下列各式用等價(jià)表示出來：（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可知，“”對(duì)應(yīng)的真值

4、表含2個(gè)1和2個(gè)0，而“”對(duì)應(yīng)的真值表也含2個(gè)1和2個(gè)0，對(duì)應(yīng)的真值表含3個(gè)1和1個(gè)0，對(duì)應(yīng)的真值表含1個(gè)1和3個(gè)0，所以，“”無法用“”和“”來表示，同樣“”也無法用“”和“”來表示，因此，不是功能完備集。10、 解：（1） a）真值表法由表中可以看出，14、 解：由題設(shè)A：A去，B：B去，C：C去，D：D去則滿足條件的選派應(yīng)該是如下范式：（A（CD）（BC）（CD）構(gòu)造和以上范式等價(jià)的主析取范式共有八個(gè)極小項(xiàng)，但根據(jù)題意，需根據(jù)題意，需派出兩人出差，所以，只有其中三項(xiàng)滿足要求：（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：珍寶藏在附近（后院）對(duì)語句符號(hào)化后得到以下蘊(yùn)含式：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、會(huì)結(jié)束；除非罷工超過一年，并且資方撤換了經(jīng)理；現(xiàn)在資方拒絕了增加工資，罷工剛開始，判斷罷工能否停止。（2）某公司發(fā)生了一起盜竊案，經(jīng)仔細(xì)偵查，掌握了如下一些事實(shí)：被盜現(xiàn)場沒留下任何痕跡；失竊時(shí)，小花或者小英正在卡拉OK廳；如果失竊時(shí)小胖正在附近，他就會(huì)習(xí)慣性的破門而入偷走東西后揚(yáng)長而去；如果小花正在卡拉OK廳唱歌，那么金剛是最大的嫌疑者；如果失竊時(shí)小胖不再附近，那么他的女友小英會(huì)和他一起外出旅游；如果失竊時(shí)小英正在卡拉OK廳唱歌，那么瘦子是最大的嫌疑者。根據(jù)以上事實(shí)，請(qǐng)通過演繹推理找出偷竊者。22、（1）不相容（2）相容（P=1，R=Q=S=0）（3）不相容（4）不相容23、（1）證：（PQ）

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

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

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

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

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

13、（1）G無割邊；（2）G中任何兩個(gè)結(jié)點(diǎn)位于同一回路中；（3）G中任何一結(jié)點(diǎn)和任何一邊都位于同一回路中；（4）G中任何兩邊都在痛一回路中。證明：（1）=（2）因?yàn)镚連通，且G無割邊，所以任意兩個(gè)結(jié)點(diǎn)u，v，都存在簡單道路p=u.wv。又因?yàn)镚無割邊，所以，刪除邊wv后，子圖依然連通，即w，v存在簡單道路p，以此類推，可以找到一個(gè)核p每條邊都不相同的p=v.u，這樣p和p就構(gòu)成了一條回路。證明：（2）=（3）因?yàn)镚中任意兩個(gè)結(jié)點(diǎn)都位于同一回路中，所以任意結(jié)點(diǎn)u和任意邊e的兩個(gè)端點(diǎn)v1,v2都分別在兩個(gè)回路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，在其中將重復(fù)邊剔除，得到新的回路C3，其中包含v1，v2結(jié)點(diǎn)，可以講回路中v1.v2用v1v2=e替換，就得到新的回路，并滿足要求。證明：（3）=（4）對(duì)任意兩條邊e1,e2其端點(diǎn)分別為u1,u2,v1,v2.根據(jù)（3）存在回路C1=u1.v1v2.u1,C2=u2.v1v1.u2.那么可以形成新的閉道路P=u1.v1v2.u2.v1v2.u1，在其中將重復(fù)邊剔除，得到新的回路C3，其中包含e2和u1,u2結(jié)點(diǎn)，可以將回路中u1.u2用u1u2=e1替換，就得到新的回路

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

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

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

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

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

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

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

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