第一篇：離散數(shù)學(xué)圖論習(xí)題
第4章圖論
綜合練習(xí)
一、單項(xiàng)選擇題
1．設(shè)L是n階無(wú)向圖G上的一條通路，則下面命題為假的是()．
(A)L可以不是簡(jiǎn)單路徑，而是基本路徑
(B)L可以既是簡(jiǎn)單路徑,又是基本路徑
(C)L可以既不是簡(jiǎn)單路徑，又不是基本路徑
(D)L可以是簡(jiǎn)單路徑，而不是基本路徑
答案：A
2．下列定義正確的是()．
(A)含平行邊或環(huán)的圖稱為多重圖(B)不含平行邊或環(huán)的圖稱為簡(jiǎn)單圖
(C)含平行邊和環(huán)的圖稱為多重圖(D)不含平行邊和環(huán)的圖稱為簡(jiǎn)單圖答案：D
3．以下結(jié)論正確是()．
(A)僅有一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖是零圖
(B)無(wú)向完全圖Kn每個(gè)結(jié)點(diǎn)的度數(shù)是n
(C)有n(n>1)個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖是平凡圖
(D)圖中的基本回路都是簡(jiǎn)單回路
答案：D
4．下列數(shù)組中，不能構(gòu)成無(wú)向圖的度數(shù)列的數(shù)組是()．
(A)(1,1,1,2,3)(B)(1,2,3,4,5)(C)(2,2,2,2,2)(D)(1,3,3,3)
答案：B
5．下列數(shù)組能構(gòu)成簡(jiǎn)單圖的是()．
(A)(0,1,2,3)(B)(2,3,3,3)(C)(3,3,3,3)(D)(4,2,3,3)
答案：C
6．無(wú)向完全圖K3的不同構(gòu)的生成子圖的個(gè)數(shù)為（）．
(A)6(B)5(C)4(D)
3答案：C
7．n階無(wú)向完全圖Kn中的邊數(shù)為（）．(A)n(n?1)n(n?1)(B)(C)n(D)n(n+1)2
2答案：B
8．以下命題正確的是()．
(A)n(n?1)階完全圖Kn都是歐拉圖
(B)n(n?1)階完全圖Kn都是哈密頓圖
(C)連通且滿足m=n－1的圖
(D)n(n?5)階完全圖Kn都是平面圖
答案：C
10．下列結(jié)論不正確是()．
(A)無(wú)向連通圖G是歐拉圖的充分必要條件是G不含奇數(shù)度結(jié)點(diǎn)
(B)無(wú)向連通圖G有歐拉路的充分必要條件是G最多有兩個(gè)奇數(shù)度結(jié)點(diǎn)
(C)有向連通圖D是歐拉圖的充分必要條件是D的每個(gè)結(jié)點(diǎn)的入度等于出度
(D)有向連通圖D有有向歐拉路的充分必要條件是除兩個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的入度等
1于出度 答案：D
11．無(wú)向完全圖K4是（）．
（A）歐拉圖（B）哈密頓圖（C）樹(shù)答案：B
12．有4個(gè)結(jié)點(diǎn)的非同構(gòu)的無(wú)向樹(shù)有()個(gè)．
(A)2(B)3(C)4(D)5 答案：A
13．設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的()條邊，才能確定G的一棵生成樹(shù)．
(A)m?n?1(B)n?m(C)m?n?1(D)n?m?1 答案：A
14．設(shè)G是有6個(gè)結(jié)點(diǎn)的完全圖，從G中刪去()條邊，則得到樹(shù)．(A)6(B)9(C)10(D)15 答案：C
二、填空題
1．?dāng)?shù)組{1，2，3，4，4}是一個(gè)能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(shù)序列，此命題的真值是.答案：0
2．無(wú)向完全圖K3的所有非同構(gòu)生成子圖有個(gè)． 答案：
43．設(shè)圖G??V,E?，其中?V??n,?E??m．則圖G是樹(shù)當(dāng)且僅當(dāng)G是連通的，且m?． 答案：n－
14．連通圖G是歐拉圖的充分必要條件是 答案：圖G無(wú)奇數(shù)度結(jié)點(diǎn)
5．連通無(wú)向圖G有6個(gè)頂點(diǎn)9條邊，從G中刪去G的一棵生成樹(shù)T． 答案：4
6．無(wú)向圖G為歐拉圖，當(dāng)且僅當(dāng)G是連通的，且G中無(wú) 答案：奇數(shù)度
7．設(shè)圖G??V,E?是簡(jiǎn)單圖，若圖中每對(duì)結(jié)點(diǎn)的度數(shù)之和，則G一定是哈密頓圖． 答案：?
8．如圖1所示帶權(quán)圖中最小生成樹(shù)的權(quán)是．
答案：1
2三、化簡(jiǎn)解答題
1．設(shè)無(wú)向圖G＝
圖
1圖
2(2)寫(xiě)出結(jié)點(diǎn)v2, v4，v6的度數(shù)；(3)判斷圖G是簡(jiǎn)單圖還是多重圖．解：(1)圖G的圖形如圖5所示．
(2)deg(v2)?4,deg(v4)?3,deg(v6)?0．
(3)圖G是多重圖．作圖如圖2.2．設(shè)圖G＝
V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d),(a,e)}
試作出圖G的圖形，并指出圖G是簡(jiǎn)單圖還是多
重圖？是連通圖嗎？說(shuō)明理由.be
解：圖G如圖8所示．.圖G中既無(wú)環(huán)，也無(wú)平行邊，是簡(jiǎn)單圖． cd 圖G是連通圖．G中任意兩點(diǎn)都連通.圖
3所以，圖G有9個(gè)結(jié)點(diǎn)．作圖如圖3．
四、計(jì)算題
1．設(shè)簡(jiǎn)單連通無(wú)向圖G有12條邊，G中有2個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)為3．求G中有多少個(gè)結(jié)點(diǎn)．試作一個(gè)滿足該條件的簡(jiǎn)單無(wú)向圖．
解：設(shè)圖G有x個(gè)結(jié)點(diǎn)，由握手定理
2?1+2?2+3?4+3?（x?2?2?3）＝12?
23x?24?21?18?27x＝9 故圖G有9個(gè)結(jié)點(diǎn)． 圖
4滿足該條件的簡(jiǎn)單無(wú)向圖如圖4所示
2．設(shè)圖G(如圖5表示)是6個(gè)結(jié)點(diǎn)a,b,c, d,e,f的圖，試求，圖G的最小生成樹(shù)，并計(jì)算它的權(quán)．
c 解：構(gòu)造連通無(wú)圈的圖，即最小生成樹(shù)，用
克魯斯克爾算法：
第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9圖5第五步： 取bc=2
3如圖6．權(quán)為1+4+3+9+23=40
3．一棵樹(shù)T有兩個(gè)2度頂點(diǎn)，1個(gè)3度頂點(diǎn)；3個(gè)4
問(wèn)它有幾片樹(shù)葉？
解：設(shè)T有n頂點(diǎn)，則有n－1條邊．T中有2個(gè) 2度頂點(diǎn)，1個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，其余n－2－1-3個(gè)1度頂
點(diǎn)．
由握手定理： 2·2+1·3+3·4+(n－2－1-3)=2(n－1)解得 n=15．于是T有15-6=9片樹(shù)葉
五、證明題
1．若無(wú)向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的．
證：用反證法．設(shè)G中的兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u和v．假若u和v不連通．
即它們之間無(wú)任何通路，則G至少有兩個(gè)連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個(gè)奇數(shù)度結(jié)點(diǎn)．這與握手定理的推論矛盾．因而u和v一定是連通的．
第二篇：《離散數(shù)學(xué)》圖論部分習(xí)題
《離散數(shù)學(xué)》圖論部分習(xí)題
1.已知無(wú)向圖G有12條邊，6個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于3，問(wèn)G至少有幾個(gè)頂點(diǎn)？并畫(huà)出滿足條件的一個(gè)圖形.（24-3*6）/2 +6=9 2.是否存在7階無(wú)向簡(jiǎn)單圖G，其度序列為1、3、3、4、6、6、7.給出相應(yīng)證明.不存在；7階無(wú)向簡(jiǎn)單圖G中最大度≤6 3.設(shè)d1、d2、…、dn為n個(gè)互不相同的正整數(shù).證明：不存在以d1、d2、…、dn為度序列的無(wú)向簡(jiǎn)單圖.Max{d1，d2，…，dn}≥n，n階無(wú)向簡(jiǎn)單圖G中最大度≤n-1 4.求下圖的補(bǔ)圖.5.1)試畫(huà)一個(gè)具有5個(gè)頂點(diǎn)的自補(bǔ)圖
2)是否存在具有6個(gè)頂點(diǎn)的自補(bǔ)圖，試說(shuō)明理由。
對(duì)于n階圖，原圖與其補(bǔ)圖同構(gòu)，邊數(shù)應(yīng)相等，均為(n*(n-1)/2)/2，即n*(n-1)/4且為整 數(shù)，n=4k或n=4k+1，不存在6階自補(bǔ)圖。
6.設(shè)圖G為n(n>2且為奇數(shù))階無(wú)向簡(jiǎn)單圖，證明：G與G的補(bǔ)圖中奇度頂點(diǎn)個(gè)數(shù)相等.n(n>2且為奇數(shù))，奇度點(diǎn)成對(duì)出現(xiàn)
7.無(wú)向圖G中只有2個(gè)奇度頂點(diǎn)u和v，u與v是否一定連通.給出說(shuō)明或證明。
只有2個(gè)奇度頂點(diǎn)u和v，如果不連通，在u和v在2個(gè)連通分支上，每個(gè)分支上僅有一個(gè)奇度頂點(diǎn)，與握手引理相矛盾。
8.圖G如下圖所示：
1)寫(xiě)出上圖的一個(gè)生成子圖.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.說(shuō)明：δ(G)=min{ d(v)| v?V } ；κ(G)=min{ |V’| |V’是圖G的點(diǎn)割集} ； λ(G)=min{ |E’| |E’是圖G的邊割集} 9.在什么條件下無(wú)向完全圖Kn為歐拉圖？
n為奇數(shù)時(shí)
10.證明：有橋的圖不是歐拉圖.假設(shè)是歐拉圖：橋的端點(diǎn)是u和v，并且圖各頂點(diǎn)度均為偶數(shù)； 橋?yàn)楦钸?，刪除橋，圖不再連通，u和v應(yīng)該在2各不同的連通分支上；且u和v度數(shù)變?yōu)槠鏀?shù)；由于其他頂點(diǎn)度數(shù)均為偶數(shù)，則u和v所在的連通分支上只有一個(gè)奇度頂點(diǎn)，與握手引理矛盾。
11.證明：有橋的圖不是哈密爾頓圖.若G是K2，顯然不是哈密爾頓圖；
否則n≥3，則橋的兩個(gè)端點(diǎn)u和v至少有一個(gè)不是懸掛頂點(diǎn)（容易證明懸掛頂點(diǎn)不是割點(diǎn)）；設(shè)u不是懸掛點(diǎn)，則u是割點(diǎn)，存在割點(diǎn)顯然不是哈密爾頓圖。
12.樹(shù)T有2個(gè)4度頂點(diǎn)，3個(gè)3度頂點(diǎn)，其余頂點(diǎn)全為樹(shù)葉，問(wèn)T有幾片樹(shù)葉？
X+2*4+3*3=2*（2+3+x-1）
x=9 13.證明：最大度Δ（T）≥k的樹(shù)T至少有k片樹(shù)葉。
設(shè)有n個(gè)頂點(diǎn)，其中x片樹(shù)葉
2*（n-1）≥1*K+（n-x-1）*2+x*1
x≥k 14.已知具有3個(gè)連通分支的平面圖G有4個(gè)面，9條邊，求G的階數(shù).n-9+4=3+1
n=9
15.給出全部互不同構(gòu)的4階簡(jiǎn)單無(wú)向圖的平面圖形。
16.如果G是平面圖, 有n個(gè)頂點(diǎn)、m條邊、f個(gè)面，G有k個(gè)連通分支。試?yán)脷W拉公式證明:：n-m+f=k+1.
第三篇：離散數(shù)學(xué)習(xí)題
集合論
1.A={?,1}，B={{a}}求A的冪集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x 4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b關(guān)于R的等價(jià)類。 5.R是A上的等價(jià)關(guān)系，A/R={{1,2}，{3}},求A，R。6.請(qǐng)分別判斷以下結(jié)論是否一定成立，如果一定成立請(qǐng)證明，否則請(qǐng)舉出反例。 ①如果A∪B?C，則A?C或者B?C。②如果A×B=A×C且A??，則B=C。 27.如果R是A上的等價(jià)關(guān)系，R,r(R)是否一定是A上的等價(jià)關(guān)系？證明或舉例。 8.已知A∩C?B∩C,A-C?B-C,證明：A?B。9.證明：AX(B∩C)=(AXB)∩(AXC)10.證明：P(A)∪P(B)?P(A∪B)-111.證明：R[sym] iff R=R -1212.證明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.證明：s(R∪S)=s(R)∪s(S)14.R是A上的關(guān)系，證明：如果R是對(duì)稱的，則r(R)也是對(duì)稱的。 15.I是整數(shù)集，R={(x,y)|x-y是3的倍數(shù)}，證明：R是I上的等價(jià)關(guān)系。 16.如果R是A上的等價(jià)關(guān)系，則A/R一定是A的劃分。17.R是集合A上的自反關(guān)系，S是A上的自反和對(duì)稱關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。18.I是正整數(shù)集合，R是I×I上的二元關(guān)系，R={< 19.f:A?B，R是B上的等價(jià)關(guān)系，令S={ 20.R是集合A上的自反關(guān)系，S是A上的自反和對(duì)稱關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。 21.P和Q都是集合A上的劃分，請(qǐng)問(wèn)P∪Q，P-Q是否是A上的劃分，22.R?AXA,R[irref]且R[tra],證明：r(R)是A上的偏序關(guān)系。 23.畫(huà)出{1,2,3,4,6}上整除關(guān)系的哈斯圖，求{2,3,6}的4種元素。 24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),畫(huà)出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。 25.f:A→B,g:B→C都是單（滿）射，證明：復(fù)合映射gof一定是單（滿）射。 26.f:A→B,g:B→C，gof是單射，請(qǐng)問(wèn)f和g是否一定是單射？請(qǐng)證明或舉出反例。27.R是實(shí)數(shù)集，f:R×R?R×R,f( 代數(shù)系統(tǒng) 1. 2.求 3.R是實(shí)數(shù)集，在R上定義運(yùn)算*為x*y=x+y+xy,問(wèn)： 5.R是實(shí)數(shù)集，R上的6運(yùn)算定義如下：對(duì)R中元素x,y，f1( 6. 7.證明：如果群G中每個(gè)元素的逆元素都是它自已，則G是交換群。 8.循環(huán)群一定是交換群。 9.證明：階為素?cái)?shù)的群一定是循環(huán)群。 -110. 11.整數(shù)集Z上定義運(yùn)算*：對(duì)任意整數(shù)x和y,x*y=x+y-4,其中+，-為普通加減法。證明： 12.證明：如果群G中至少有兩個(gè)元素，則群中沒(méi)有零元。13.S是G的子群，證明：{x|x是S的左陪集}是G的一個(gè)劃分 14. 15.H，K都是群G的子群，請(qǐng)問(wèn)H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的兩個(gè)子群，a?G, 試證：aH?aK當(dāng)且僅當(dāng)H?K。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請(qǐng)問(wèn)(G,*)是否構(gòu)成群？ n18. 19.S是G的子群，證明：{x|x是S的左陪集}是G的一個(gè)劃分 20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21. ++23.R為實(shí)數(shù)集，R為正實(shí)數(shù)集， 1.如何判斷二部圖？完全圖、完全二部圖的邊數(shù)。2.如何求E回路？ 3.Petersen圖是否為E圖或H圖。 4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時(shí)輪圖為H圖？ 6.如何求最小生成樹(shù)。 7.證明：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個(gè)頂點(diǎn)，證明：m?3n-6。并由此證明K5不是平面圖。 11.證明：有6個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖G和它的補(bǔ)圖中至少有一個(gè)三角形。 12.證明：在至少有兩個(gè)頂點(diǎn)的無(wú)向樹(shù)中，至少有2個(gè)一度頂點(diǎn)。 13.G是無(wú)向簡(jiǎn)單連通圖，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？ 14.證明：簡(jiǎn)單無(wú)向圖G和它的補(bǔ)圖中至少有一個(gè)是連通圖。15.證明：無(wú)向圖中奇度點(diǎn)（度數(shù)為奇數(shù)的點(diǎn)）有偶數(shù)個(gè)。16.證明：n個(gè)頂點(diǎn)的無(wú)向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點(diǎn)集，證明：對(duì)任意頂點(diǎn)集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數(shù)目。18.一棵無(wú)向樹(shù)有3個(gè)3次點(diǎn)，1個(gè)頂點(diǎn)次數(shù)為2，其余頂點(diǎn)次數(shù)為1，問(wèn)它有幾個(gè)次數(shù)為1的頂點(diǎn)？寫(xiě)出求解過(guò)程。19.證明：每個(gè)簡(jiǎn)單平面圖都包含一個(gè)次至多為5的頂點(diǎn)。20.連通平面圖G有n個(gè)頂點(diǎn)，m條邊和f個(gè)面，證明：n-m+f=2。21.如果圖G的最大頂點(diǎn)次數(shù)≤ρ，證明：G是ρ+1可點(diǎn)著色的。 22.G是無(wú)向簡(jiǎn)單連通圖，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？ 23.如果一個(gè)簡(jiǎn)單圖G和它的補(bǔ)圖同構(gòu)，則稱G是自補(bǔ)圖，求所有4個(gè)頂點(diǎn)自補(bǔ)圖。 24.G是平面圖，G有m條邊，n個(gè)頂點(diǎn)，證明：m?3n-6。如果G中無(wú)三角形，則m?2n-4。數(shù)理邏輯 1.如果今天是星期一，則要進(jìn)行英語(yǔ)或數(shù)理邏輯考試。 沒(méi)有不犯錯(cuò)誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。 不存在最大的整數(shù)。有且只有一個(gè)偶數(shù)是素?cái)?shù)。2.求真值表及范式：P?(┓Q?R)、(┓Q?R)?(P?R)3.推理： p?(q?r)，┓s∨p，q ├ s?r p?r，q?s，p∨q ├ r∨s p∨q，p?┓r，s?t，┓s?r，┓t ├ q p?(┓(r∧s)?┓q),p,┓s ├ ┓q 4.如果小王是理科學(xué)生，他一定會(huì)學(xué)好數(shù)學(xué)。如果小王不是文科學(xué)生，他一定是理科學(xué)生。小王沒(méi)學(xué)好數(shù)學(xué)。所以小王是文科學(xué)生。 5.判斷各公式在給定解釋時(shí)的真假值，并且改變論域使該公式在新的解釋下取值相反。論域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①?x(F(x)∨G(x))②?y?yR(x,y) 習(xí)題五 1.設(shè)個(gè)體域D={a,b,c}，在D中消去公式?x(F(x)??yG(y))的量詞。甲乙用了不同的演算過(guò)程： 甲的演算過(guò)程如下： ?x(F(x)??yG(y))??x(F(x)?(G(a)?G(b)?G(c)))?(F(a)?(G(a)?G(b)?G(c))) ?(F(b)?(G(a)?G(b)?G(c)))?(F(c)?(G(a)?G(b)?G(c)))?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))乙的演算過(guò)程如下： ?x(F(x)??yG(y))??xF(x)??yG(y)?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c)) 顯然，乙的演算過(guò)程簡(jiǎn)單，試指出乙在演算過(guò)程中的關(guān)鍵步驟。 解：乙在演算中的關(guān)鍵步驟是，在演算開(kāi)始就利用量詞轄域收縮與擴(kuò)張等值式，將量詞的轄域縮小，因而演算簡(jiǎn)單。 2.設(shè)個(gè)體域D={a,b,c}，消去下列各式的量詞： (1)?x?y(F(x)?G(y))(2)?x?y(F(x)?G(y))(3)?xF(x)??yG(y)(4)?（xF(x,y)??yG(y)) 解： （1）(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))（2）(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))（3）(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))（4）(F(a,y)?F(b,y)?F(c,y))?(G(a)?G(b)?G(c))在（1）（2）（4）中均將量詞的轄域縮小，所以演算結(jié)果都比較簡(jiǎn)單 3.設(shè)個(gè)體域D={1,2}，請(qǐng)給出兩種不同的解釋I1和I2，使得下面公式在I1下都是真命題，而在I2下都是假命題。（1）?x(F(x)?G(x))（2）?x(F(x)?G(x))解： 解釋I1為：個(gè)體為實(shí)數(shù)集合R，F(xiàn)(x)：x為自然數(shù)，G(x)：x為整數(shù)。在I1下，（1）為自然數(shù)都是整數(shù)，（2）為存在整數(shù)為自然數(shù)。他們都是真命題 解釋I2為：個(gè)體域仍為實(shí)數(shù)集R，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x能表示成分?jǐn)?shù)，在I2下，（1）為無(wú)理數(shù)都能表示成分?jǐn)?shù)，（2）為存在能表示成分?jǐn)?shù)的無(wú)理數(shù)，他們都是假命題 4.給定公式A??xF(x)??xF(x) （1）在解釋I1中，個(gè)體域D1={a}，證明公式A在I1下的真值為1.（2）在解釋I2中，個(gè)體域D2={a1,a2,?,an}，n?2,A在I2下的真值還一定是1嗎？為什么？ 解： （1）在I1下，?xF(x)??xF(x)?F(a)?F(a)??F(a)?F(a)?1（2）在I2下 ?xF(x)??xF(x)?(F(a1)?F(a2)???F(an))?(F(a1)?F(a2)???F(an)) 為可滿足式，設(shè)F(x)：x為奇數(shù)，ai?i,i?1,2,?n,n?2，此時(shí)，蘊(yùn)涵式前件為真，后件為假，故蘊(yùn)含式為假，若令F(x)；x為整數(shù)，則蘊(yùn)含式前后件均為真，所以（2）中公式在I2下為可滿足式 5.給定解釋I如下：（a）個(gè)體域D={3,4}；（b）f(x)為f(3)?4,f(4)?3; （c）F(x,y)為F(3,3)?F(4,4)?0,F(3,4)?F(4,3)?1.試求下列公式在I下的真值。 (1)?x?yF(x,y)(2)?x?yF(x,y)(3)?x?yF(x,y)?F(f(x),f(y))) 解： （1） ?x?yF(x,y)??x(F(x,3)?F(x,4))?(F(3,3)?F(3,4))?(F(4,3)?F(4,4))?1?1?1（2） ??x(F(x,3)?F(x,4))?(F(3,3)?F(3,4))?(F(4,3)?F(4,4)?0（3） ??x((F(x,3)?F(f(x),f(3)))?(F(x,4)?F(f(x),f(4))))?(((F(3,3)?F(f(3),f(3)))?(F(3,4)?F(f(3),f(4))))?(((F(4,3)?F(f(4),f(3)))?(F(4,4)?F(f(4),f(4))))?1 6.甲使用量詞轄域收縮與擴(kuò)張等值式進(jìn)行如下演算 ?x(F(x)?G(x,y))??xF(x)?G(x,y) 乙說(shuō)甲錯(cuò)了，乙說(shuō)的對(duì)嗎？為什么？ 解：乙說(shuō)的對(duì)，甲錯(cuò)了，全稱量詞?的指導(dǎo)變?cè)獂，轄域?yàn)?F(x)?G(x,y))，其中F(x)與G(x,y)都是x的約束變?cè)?，因而不能講量詞的轄域變小 7.請(qǐng)指出下面等值運(yùn)算的兩處錯(cuò)誤 ??x?y(F(x)?(G(y)?H(x,y))??x?y(F(x)?(G(y)?H(x,y))??x?y((F(x)?G(y))?H(x,y)) 解： 演算的第一步，應(yīng)用量詞轄域收縮與擴(kuò)張算值式時(shí)丟掉了否定連接詞?，演算的第二步，在原錯(cuò)的基礎(chǔ)上又用錯(cuò)了等值式 (F(x)?G(y)?H(x,y))和(F(x)?G(y)?H(x,y))不等值 8.在一階邏輯中將下列命題符號(hào)化，要求用兩種不同的等值形式（1）沒(méi)有小于負(fù)數(shù)的正數(shù) （2）相等的兩個(gè)角未必都是對(duì)頂角 解： （1）??x(F(x)?G(x))??x(G(x)??F(x)) 其中F(x)：x小于負(fù)數(shù)，G(x)：x是正數(shù) （2）??x?y(F(x)?F(y)?H(x,y)?L(x,y)??x?y(F(x)?F(y)?H(x,y)??L(x,y))其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是對(duì)頂角 9.設(shè)個(gè)體域D為實(shí)數(shù)集合，命題“有的實(shí)數(shù)既是有理數(shù)又是無(wú)理數(shù)”，這顯然是個(gè)假命題?？墒悄橙藚s說(shuō)這是真命題，其理由如下 設(shè)F(x)：x是有理數(shù)，G(x）：x是無(wú)理數(shù)。?xF(x),?xG(x)都是真命題，于是，?xF(x)??xG(x)??x(F(x)?G(x))由于?xF(x)??xG(x)是真命題，故?x(F(x)?G(x))也是真命題，即有的實(shí)數(shù)是有理數(shù)，也是無(wú)理數(shù)這個(gè)人的結(jié)論對(duì)嗎？為什么？ 解：存在量詞對(duì)?無(wú)分配律 10.在求前束范式時(shí)有人說(shuō)??x(F(x)?G(x,y))已是前束范式，理由是量詞已在公式的前面，他說(shuō)的對(duì)嗎？為什么？ 解：在前束范式中，否定聯(lián)結(jié)詞不能在量詞前面出現(xiàn) 11.有人說(shuō)無(wú)法求公式 ?x(F(x)?G(x))??xG(x,y)的前束范式，因?yàn)楣街械膬蓚€(gè)量詞的指導(dǎo)變?cè)嗤?。他的理由?duì)嗎？為什么？ 換名規(guī)則可以使兩個(gè)指導(dǎo)變?cè)幌嗤?12.求下列各式的前束范式：(1)?xF(x)??yG(x,y)(2)?x(F(x,y)??yG(x,y,z))(3)?xF(x,y)??xG(x,y) (4)?x1(F(x1)?G(x1,x2))?(?x2H(x2)??x3L(x2,x3))(5)?x1F(x1,x2)?(F(x1)???x2G(x1,x2))解： （1）?x?y(F(x)?G(z,y))（2）?x?t(F(x,t)?G(x,t,z)) （3）?x1?x2?x3?x4((F(x1,y)?G(x2,y))?(G(x3,y)?F(x4,y)))（4）?y1?y2?y3((F(y1)?G(y1,x2))?(H(y2)?L(x2,y3)))（5）?y1?y2(F(y1,x2)?(F(x1)??G(x1,y2))) 13.將下列命題符號(hào)化，要求符號(hào)化的公式權(quán)威前束范式：（1）有點(diǎn)火車比有的汽車跑的快（2）有的火車比所有的汽車跑的快 （3）說(shuō)有的火車比所有汽車跑得快是不對(duì)的（4）說(shuō)有的飛機(jī)比有的汽車慢也是不對(duì)的 解： （1）?x?y(F(x)?G(y)?H(x,y))其中F(x)：x是汽車 G(y):y是 火車 H(x,y)：x比y跑得快（2）?x?y(F(x)?(G(y)?H(x,y)))其中F(x)：x是火車 G(y):y是 汽車 H(x,y)：x比y跑得快 （3)?x?y(F(x)?G(y)??H(x,y))其中F(x)：x是火車 G(y):y是 汽車H(x,y)：x比y跑得快 （4）?x?y(F(x)?G(y)??H(x,y))其中F(x)：x是飛機(jī) G(y):y是 汽車 H(x,y)：x比y跑得慢 14.在自然推理系統(tǒng)F中，指出下面各證明序列中的錯(cuò)誤：（1）①F(x)??xG(x)前提引入 ②F(c)?G(c)①EI規(guī)則（2）①?xF(x)??yG(y)前提引入 ②F(a)?F(b)①EI規(guī)則（3）①F(y)?G(y)前提引入 ②?x(F(x)?G(x))①EG規(guī)則（4）①F(a)?F(b)前提引入 ②?x(F(x)?G(x))①EG規(guī)則（5）①F(c)?G(c)前提引入 ②?x(F(x)?G(x))①UG規(guī)則 解：（1）對(duì)F(x)??xG(x)不能使用EI規(guī)則，它不是前束范式，首先化成前束范式F(x)??xG(x)??x(F(y)?G(x))，因?yàn)榱吭~轄域(F(y)?G(x)中，除了x還有自由出現(xiàn)的y所以不能用EI規(guī)則 （2）對(duì)?xF(x)??yG(y)也應(yīng)該先化成前束范式才能消去量詞，其前束范式為?x?y(F(x)?G(y))，要消去量詞，既要用UI規(guī)則，又要用EI規(guī)則（3）這里A(y)=F(y)?G(y)滿足要求 （4）這里，使F(a)為真的a不一定使G(a)為真，同樣的，使G(b)為真的b不一定使F(b)為真 （5）這里，c為個(gè)體常項(xiàng)，不能對(duì)F(c)?G(c)引入全稱量詞 15.在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：（1）前提：?xF(x)??y((F(y)?G(y))?R(y)),?xF(x) 結(jié)論：?xR(x) （2）前提：?x(F(x)?(G(a)?R(x))),?xF(x) 結(jié)論：?x(F(x)?R(x))（3）前提：?x(F(x)?G(x)),??xG(x) 結(jié)論：?xF(x) （4）前提：?x(F(x)?G(x)),?x(?G(x)??R(x)),?xR(x) 結(jié)論：?xF(x) （1）證明：1 ?xF(x) 前提引入 ?xF(x)??y((F(y)?G(y))?R(y)) 前提引入 ?y((F(y)?G(y))?R(y) 2假言推理 F(c)EI(F(c)?G(c))?R(c) UI F(c)?G(c) 附加 R(c)6假言推理 ?xR(x) 7EG （2）證明：1 ?xF(x) 前提引入 ?x(?H(x)),?x?F(x)?x(F(a)?G(a))?),G(a)I(y)H(a)????x(F(x)?(G(a)?R(x))) ?x(G(a)?H(a)?I(a))前提引入 F(c)EI F(c)?(G(a)?R(c)) UI G(a)?R(c)4假言推理 R(c) 5化簡(jiǎn) F(c)?R(c)6合取 ?x(F(x)?R(x)) 7EG （3）證明：1 ??xF(x) 前提引入?x?F(x) 1置換?F(c) 2UI ?x(F(x)?G(x)) 前提引入F(c)?G(c) 4UI 6F(c)5析取三段論?xF(x) 6EG(4)證明：1 ?x(F(x)?G(x)) 前提引入 F(y)?G(y)UI ?x(?G(x)??R(X)) 前提引入 ?G(y)??R(y) UI ?xR(x) 前提引入 R(y) 5UI ?G(y) 6析取三段論 8F(y) 27析取三段論 ?xF(x) UG 16.找一個(gè)解釋I，在I下，使得?xF(x)??xG(x)為真，而使得?x(F(x)??G(x))為假，從而說(shuō)明?xF(x)??xG(x)??x(F(x)??G(x))。解：取個(gè)體域?yàn)樽匀粩?shù)集合N，F(xiàn)(x):x為奇數(shù)，G(x):x 為偶數(shù)。顯然在以上解釋下?xF(x)??xG(x)為真而?x(F(x)?G(x))為假。 17.給定推理如下： 前提：?x(F(x)??G(x)),?x(H(x)?G(x)) 結(jié)論：?x(H(x)??F(x))。 有些人給出的證明如下： 證明： ①?xH(x)附加前提引入 ②H(y) ③?x(H(x)?G(x)) ④H(y)?G(y) ⑤G(y) ⑥?x(F(x)??G(x)) ⑦F(y)??G(y) ⑧?F(y) ⑨?x?F(x) 解：根據(jù)16題可知兩公式并不等價(jià)。 ①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且說(shuō)，由附加前提證明法可知，推理正確，請(qǐng)指出以上證明的錯(cuò)誤。18.給出上題（17）推理的正確證明（注意，不能使用附加前提證明法）。 證明：1 ?x(F(x)??G(x)) 前提引入 ?x(H(x)?G(x)) 前提引入 F(y)??G(y)UI H(y)?G(y) 2UI G(y)??F(y) 3置換H(y)??F(y)5假言三段論?x(H(x)??F(x))UG 19.在自然推理系統(tǒng)F中，構(gòu)造下列推理的證明： 前提：?xF(x)??xG(x) 結(jié)論：?x(F(x)?G(x)) 證明：1?xF(x)??xG(x) 前提引入 ?yF(y)??xG(x) 換名規(guī)則 ?y?x(F(x)?G(x))化簡(jiǎn) ?x(F(x)?G(x))EI 20.在自然推理系統(tǒng)F中，構(gòu)造下列推理的證明（可以使用附加前提證明法）：（1）前提：?x(F(x)?G(x)) 結(jié)論：?xF(x)??xG(x)（2）前提：?x(F(x)?G(x)) 結(jié)論：??xF(x)??xG(x) 證明：（1）.1?xF(x) 附加前提引入 F(y)UI ?x(F(x)?G(x)) 前提引入 F(y)?G(y) 3UI G(y)3假言推理 ?xG(x) （2）1 ??xF(x) 附加前提引入?x?F(x) 置換原則?F(c) 2EI ?x(F(x)?G(x)) 前提引入 F(c)?G(c) UI G(c) 5析取三段論?xG(x) EG 21.在自然推理系統(tǒng)中，構(gòu)造下面推理的證明： 沒(méi)有白色的烏鴉，北京鴨都是白色的。因此，北京鴨都不是烏鴉。 設(shè)F(x):x是烏鴉，G(x)：x是北京鴨，H(x):x是白色的。前提 ??x(F(x)?H(x)),?x(G(x)?H(x))結(jié)論 ?x(G(x)??F(x)) 證明：1 ??x(F(x)?H(x)) 前提引入 2 ?x?(F(x)?H(x)) 置換原則 3 ?x(?F(x)??H(x)) 置換原則 4 ?x(?H(x)??F(x)) H(y)??F(y) 4UI 6 ?x(G(x)?H(x)) 前提引入 7 G(y)?H(y) 5UI 8 G(y)??F(y) 7假言三段論 9 ?x(G(x)??F(x)) 8UG 22.在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明： (1)偶數(shù)都能被2整除。6是偶數(shù)。所以6能被2整除。 (2)凡大學(xué)生都是勤奮的。王曉山不勤奮，所以王曉山不是大學(xué)生。 （1）設(shè)F(x):x為偶數(shù)，G(x)：x能被2整除 前提 ?x(F(x)?G(x)),F(6)結(jié)論 G(6)證明：1 ?x(F(x)?G(x)) 前提引入 F(6)?G(6) 1UI F(6) 前提引入 G(6) 3假言推理 (2)設(shè)F(x):x是大學(xué)生，G(x)：x是勤奮的，a 王曉山 前提 ?x(F(x)?G(x)),?G(a)，結(jié)論 ?F(a) 證明：1 ?x(F(x)?G(x)) 前提引入 F(a)?G(a) 1UI ?G(a) 前提引入 ?F(a)3 據(jù)取式 23.在自然推理系統(tǒng)F中，證明下面推理： （1）每個(gè)有理數(shù)都是實(shí)數(shù)。有的有理數(shù)是整數(shù)。因此，有的實(shí)數(shù)是整數(shù)9（2）有理數(shù)，無(wú)理數(shù)都是實(shí)數(shù)。虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)既不是有理數(shù)也不是無(wú)理數(shù)。 （1）設(shè)F(x):x是有理數(shù)，G(x)：x實(shí)數(shù)，H(x):x是整數(shù) 前提 ?x(F(x)?G(x))，?x(F(x)?H(x)) 結(jié)論 ?x(G(x)?H(x)) (2)設(shè)F(x):x是有理數(shù)，G(x)：x是無(wú)理數(shù)，H(x):x是實(shí)數(shù)，I(x):x是虛數(shù) 前提 ?x((F(x)?G(x))?H(x)),?x(I(x)??H(x))結(jié)論 ?x(I(x)?(?F(x)?G(x))) 證明：1 ?x(I(x)??H(x)) 前提引入 I(y)??H(y) UI ?x((F(x)?G(x))?H(x)), 前提引入 4(F(y)?G(y))?H(y)UI ?H(y)?(?F(y)??G(y)) 置換 I(y)?(?F(y)??G(y)) 5假言三段論 ?x(I(x)?(?F(x)??G(x)) UG 24.在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明： 每個(gè)喜歡不行的人都不喜歡騎自行車。每個(gè)人或者喜歡騎自行車或者喜歡乘汽車。有的人不喜歡乘汽車，所以有的人不喜歡步行。（個(gè)體域?yàn)槿祟惣希?/p> 設(shè)F(x):x喜歡步行，G(x)：x喜歡騎自行車，H(x):x喜歡乘汽車 前提 ?x(F(x)?G(x)，?x(G(x)?H(x)),??xH(x)結(jié)論 ??xF(x) 證明：1 ??xH(x) 前提引入 ?H(c) UI x(G(x)?H(x)) 前提引入 G(c)?H(c)UI G(c) 4析取三段論 ?x(F(x)??G(x)) 前提引入 F(c)??G(c) UI ?F(c) 57拒取式 ?x?F(x) 8UG 25.在自然推理系統(tǒng)F中，構(gòu)造下列推理的證明（個(gè)體域?yàn)槿祟惣希?/p> 每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且是聰明的，所以王大海在他的事業(yè)中將獲得成功。 設(shè)F(x):x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x):x是聰明的，I(x):x在事業(yè)中獲得成功 前提 ?x(F(x)?G(x))，?x(G(x)?H(x)?I(x))，a:王大海，F(xiàn)(a),H(a)結(jié)論 I(a)證明：1 F(a) 前提引入 ?x(F(x)?G(x)) 前提引入 F(a)?G(a) 2UI G(a)3假言推論 H(a) 前提引入 ?x(G(x)?H(x)?I(x)) 前提引入 G(a)?H(a)?I(a) 6UI G(a)?H(a)5合取 I(a)8假言推論 第一章部分課后習(xí)題參考答案 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p∨(q∧r)? 0∨(0∧1)?0（2）（p?r）∧(﹁q∨s)?（0?1）∧(1∨1)?0∧1?0.（3）（?p∧?q∧r）?(p∧q∧﹁r)?（1∧1∧1）?(0∧0∧0)?0(4)（?r∧s）→(p∧?q)?（0∧1）→(1∧0)?0→0?1 17．判斷下面一段論述是否為真：“?是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則2也是無(wú)理數(shù)。另外，只有6能被2整除，6才能被4整除。” 答：p: ?是無(wú)理數(shù) q: 3是無(wú)理數(shù) 0 r: 2是無(wú)理數(shù) s: 6能被2整除t: 6能被4整除 0 命題符號(hào)化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（4）(p→q)→(?q→?p)（5）(p∧r)?(?p∧?q)（6）((p→q)∧(q→r))→(p→r)答： （4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 0 0 0 0 0 0 0 0 所以公式類型為永真式 （5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例） 第二章部分課后習(xí)題參考答案 3.用等值演算法判斷下列公式的類型，對(duì)不是重言式的可滿足式，再用真值表法求出成真賦值.1(1)?(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1 所以公式類型為永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 所以公式類型為可滿足式 4.用等值演算法證明下面等值式：(2)(p→q)∧(p→r)?(p→(q∧r))(4)(p∧?q)∨(?p∧q)?(p∨q)∧?(p∧q)證明（2）(p→q)∧(p→r)?(?p∨q)∧(?p∨r)??p∨(q∧r))?p→(q∧r)（4）(p∧?q)∨(?p∧q)?(p∨(?p∧q))∧(?q∨(?p∧q)?(p∨?p)∧(p∨q)∧(?q∨?p)∧(?q∨q)?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q)5.求下列公式的主析取范式與主合取范式，并求成真賦值 (1)(?p→q)→(?q∨p)(2)?(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解： （1）主析取范式 (?p→q)→(?q?p)?????(p?q)?(?q?p)(?p??q)?(?q?p)(?p??q)?(?q?p)?(?q??p)?(p?q)?(p??q)(?p??q)?(p??q)?(p?q)?m0?m2?m3 ?∑(0,2,3)主合取范式： (?p→q)→(?q?p)???(p?q)?(?q?p)(?p??q)?(?q?p)?(?p?(?q?p))?(?q?(?q?p))?1?(p??q)?(p??q)? M1 ?∏(1)(2)主合取范式為： ?(p→q)?q?r??(?p?q)?q?r ?(p??q)?q?r?0 所以該式為矛盾式.主合取范式為∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式為 0(3)主合取范式為： (p?(q?r))→(p?q?r)??(p?(q?r))→(p?q?r)??(?p?(?q??r))?(p?q?r)(?p?(p?q?r))?((?q??r))?(p?q?r))?1?1 ?1 所以該式為永真式.永真式的主合取范式為 1 主析取范式為∑(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案 14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：(2)前提：p?q,?(q?r),r 結(jié)論：?p(4)前提：q?p,q?s,s?t,t?r 結(jié)論：p?q 證明：（2） ①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊(yùn)含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p（3）⑤⑥拒取式 證明（4）： ①t?r 前提引入 ②t ①化簡(jiǎn)律 ③q?s 前提引入 ④s?t 前提引入 ⑤q?t ③④等價(jià)三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡(jiǎn) ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取 15在自然推理系統(tǒng)P中用附加前提法證明下面各推理： 4(1)前提：p?(q?r),s?p,q 結(jié)論：s?r 證明 ①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統(tǒng)P中用歸謬法證明下面各推理： (1)前提：p??q,?r?q,r??s 結(jié)論：?p 證明： ①p 結(jié)論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡(jiǎn)律 ⑥r(nóng)?￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r?﹁r ⑤⑦ 合取 由于最后一步r?﹁r 是矛盾式,所以推理正確.第四篇：離散數(shù)學(xué)習(xí)題五
第五篇：離散數(shù)學(xué)課后習(xí)題答案
![下載離散數(shù)學(xué)圖論習(xí)題[優(yōu)秀范文5篇]word格式文檔](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
點(diǎn)擊咨詢 