離散習題答案 馮偉森

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

2、這個整數能被2和3整除。PQ設R：一個整數能被3整除，S：這個整數的個位數之和也能被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、 解：由題設A：A去，B：B去，C：C去，D：D去則滿足條件的選派應該是如下范式：（A（CD）（BC）（CD）構造和以上范式等價的主析取范式共有八個極小項，但根據題意，需根據題意，需派出兩人出差，所以，只有其中三項滿足要求：（ABCD），（ABCD），（ABCD）即有三種方案：A和C去或者A和D去或者B和D去。15、 證：（1）由定理1

5、.11，需證（PQ）（P（PQ）為永真式（3）由定理1.11，需證PPRS為永真式16、 證：（1）性質1 由定理1.11和“”的定義，AA是永真式，所以A=A。（2）性質2 由定理1.11，A=B，B=A，AB和B是永真式，即A是永真式，由定理1.3，AB成立。（3）性質3 由定理1.11，A=B，AB是永真式，又A是永真式，根據“”的定義，B必是永真式。17、 證：“=”，A=B，AB是永真式，“A，必有A=B。18、 解： 設 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、會結束；除非罷工超過一年，并且資方撤換了經理；現在資方拒絕了增加工資，罷工剛開始，判斷罷工能否停止。（2）某公司發(fā)生了一起盜竊案，經仔細偵查，掌握了如下一些事實：被盜現場沒留下任何痕跡；失竊時，小花或者小英正在卡拉OK廳；如果失竊時小胖正在附近，他就會習慣性的破門而入偷走東西后揚長而去；如果小花正在卡拉OK廳唱歌，那么金剛是最大的嫌疑者；如果失竊時小胖不再附近，那么他的女友小英會和他一起外出旅游；如果失竊時小英正在卡拉OK廳唱歌，那么瘦子是最大的嫌疑者。根據以上事實，請通過演繹推理找出偷竊者。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：實數集：17、(1) 錯誤，應換元，即(2) 正確(3) 錯誤，a、b應是同一個常元18、(2) 證：首先，將結論否定作為前提加入到原有前提中習題 三習題 四習題 五4、解：每個集合的劃分就可以確定一個等價關系集合有多少個劃分就可以確定多少個等價關系不同的劃分的個數為：不同的等價關系個數等于不同的劃分個數，所以不同的等價關系個數為15.習題 六習題 十1、設G是一個（n，m）簡單圖。證明：，等號成立當且僅當G是完全圖。2、設G是一個（n，n+1）的無

9、向圖，證明G中存在頂點u，d(u)3。證明：反證法，假設，則G的總點度上限為max（d(u)）2n，根據握手定理，圖邊的上限為max（m）2n/2=n。與題設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）中，總和為奇數，不滿足圖總度數為偶數的握手定理?？梢园慈缦路椒嬙鞚M足要求的圖：序列中每個數字ai對應一個點，如果序列數字是偶數，那么就

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

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

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

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

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

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

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

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

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

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

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

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