第一篇：離散數(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的等價類。

5.R是A上的等價關(guān)系，A/R={{1,2}，{3}},求A，R。6.請分別判斷以下結(jié)論是否一定成立，如果一定成立請證明，否則請舉出反例。

①如果A∪B?C，則A?C或者B?C。②如果A×B=A×C且A??，則B=C。

27.如果R是A上的等價關(guān)系，R,r(R)是否一定是A上的等價關(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是對稱的，則r(R)也是對稱的。

15.I是整數(shù)集，R={(x,y)|x-y是3的倍數(shù)}，證明：R是I上的等價關(guān)系。

16.如果R是A上的等價關(guān)系，則A/R一定是A的劃分。17.R是集合A上的自反關(guān)系，S是A上的自反和對稱關(guān)系，證明t(R∪S)是A上的等價關(guān)系。18.I是正整數(shù)集合，R是I×I上的二元關(guān)系，R={<,>|xv=yu},證明：R是等價關(guān)系。

19.f:A?B，R是B上的等價關(guān)系，令S={|x?A且y?A且?R}，證明：S是A上的等價關(guān)系。

20.R是集合A上的自反關(guān)系，S是A上的自反和對稱關(guān)系，證明t(R∪S)是A上的等價關(guān)系。

21.P和Q都是集合A上的劃分，請問P∪Q，P-Q是否是A上的劃分，22.R?AXA,R[irref]且R[tra],證明：r(R)是A上的偏序關(guān)系。

23.畫出{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),畫出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。

25.f:A→B,g:B→C都是單（滿）射，證明：復(fù)合映射gof一定是單（滿）射。

26.f:A→B,g:B→C，gof是單射，請問f和g是否一定是單射？請證明或舉出反例。27.R是實數(shù)集，f:R×R?R×R,f()=,請問f是否為單射？是否為滿射？分別證明或舉反例。28.已知B∩C=?,令f：P(B∪C)?P(B)×P(C)，對X?P(B∪C),令f(X)=(B∩X,C∩X),證明：f是雙射。

代數(shù)系統(tǒng)

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的單位元、每個元素的逆元、所有的生成元和所有的子群。

2.求的單位元，零元，每個元素的逆元，每個元素的階，它是循環(huán)群嗎？求出它所有的子群。

3.R是實數(shù)集，在R上定義運(yùn)算*為x*y=x+y+xy,問：是代數(shù)系統(tǒng)嗎？有單位元嗎？每個元素都有逆元嗎？ ***4.R是非零實數(shù)集合，是代數(shù)系統(tǒng)，對于R中元素*x,y，令xoy=2x+2y-2。請問中是否存在單位元、零元、哪些元素有逆元？運(yùn)算o是否滿足交換律和結(jié)合律。分別說明理由。

5.R是實數(shù)集，R上的6運(yùn)算定義如下：對R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。問：哪些滿足交換律、結(jié)合律、有單位元、有零元？說明理由。

6.是一個群，證明：G是交換群當(dāng)且僅當(dāng)對任意G中222元素x,y,都有等式(xy)=xy成立。

7.證明：如果群G中每個元素的逆元素都是它自已，則G是交換群。

8.循環(huán)群一定是交換群。

9.證明：階為素數(shù)的群一定是循環(huán)群。

-110.是一個群，u?G,定義運(yùn)算*：x*y=xouoy, 證明：是一個群。

11.整數(shù)集Z上定義運(yùn)算*：對任意整數(shù)x和y,x*y=x+y-4,其中+，-為普通加減法。證明：是一個群。

12.證明：如果群G中至少有兩個元素，則群中沒有零元。13.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分

14.是一個群,a?G,n是a的階(周期)，證明：k<{a|k=0,2,…,n-1},o>是的一個子群。

15.H，K都是群G的子群，請問H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的兩個子群，a?G, 試證：aH?aK當(dāng)且僅當(dāng)H?K。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請問(G,*)是否構(gòu)成群？

n18.是群，e是單位元，a?G,a的階為k,證明：a=e當(dāng)且僅當(dāng) n是k的倍數(shù)。

19.S是G的子群，證明：{x|x是S的左陪集}是G的一個劃分

20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21.是偶數(shù)階群，則G中必存在2階元素。22.證明：6個元素的群在同構(gòu)意義下只有兩個。

++23.R為實數(shù)集，R為正實數(shù)集，與是否同構(gòu)？ 24.是有限群，證明：G不可能表示成兩個真子群的并。25.圖論

1.如何判斷二部圖？完全圖、完全二部圖的邊數(shù)。2.如何求E回路？

3.Petersen圖是否為E圖或H圖。

4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時輪圖為H圖？ 6.如何求最小生成樹。

7.證明：奇數(shù)個頂點的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數(shù)個頂點的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。并由此證明K5不是平面圖。

11.證明：有6個頂點的簡單無向圖G和它的補(bǔ)圖中至少有一個三角形。

12.證明：在至少有兩個頂點的無向樹中，至少有2個一度頂點。

13.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？

14.證明：簡單無向圖G和它的補(bǔ)圖中至少有一個是連通圖。15.證明：無向圖中奇度點（度數(shù)為奇數(shù)的點）有偶數(shù)個。16.證明：n個頂點的無向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點集，證明：對任意頂點集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數(shù)目。18.一棵無向樹有3個3次點，1個頂點次數(shù)為2，其余頂點次數(shù)為1，問它有幾個次數(shù)為1的頂點？寫出求解過程。19.證明：每個簡單平面圖都包含一個次至多為5的頂點。20.連通平面圖G有n個頂點，m條邊和f個面，證明：n-m+f=2。21.如果圖G的最大頂點次數(shù)≤ρ，證明：G是ρ+1可點著色的。

22.G是無向簡單連通圖，G有n個頂點，則G最少有幾條邊，最多有幾條邊？

23.如果一個簡單圖G和它的補(bǔ)圖同構(gòu)，則稱G是自補(bǔ)圖，求所有4個頂點自補(bǔ)圖。

24.G是平面圖，G有m條邊，n個頂點，證明：m?3n-6。如果G中無三角形，則m?2n-4。數(shù)理邏輯

1.如果今天是星期一，則要進(jìn)行英語或數(shù)理邏輯考試。

沒有不犯錯誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。

不存在最大的整數(shù)。有且只有一個偶數(shù)是素數(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é)生，他一定會學(xué)好數(shù)學(xué)。如果小王不是文科學(xué)生，他一定是理科學(xué)生。小王沒學(xué)好數(shù)學(xué)。所以小王是文科學(xué)生。

5.判斷各公式在給定解釋時的真假值，并且改變論域使該公式在新的解釋下取值相反。論域：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)

第二篇：離散數(shù)學(xué)習(xí)題及答案

離散數(shù)學(xué)考試試題（A卷及答案）

一、（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？

(1)若A去，則C和D中要去1個人；

(2)B和C不能都去；

(3)若C去，則D留下。

解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時成立。因此

(A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))

?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T

故有三種派法：B∧D，A∧C，A∧D。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。S(x)：x是專家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為：

?x(S(x)∧W(x))，?xY(x)?x(S(x)∧Y(x))

下面給出證明：

(1)?xY(x)P

(2)Y(c)T(1)，ES

(3)?x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)?x(S(x)∧Y(x))T(6)，EG

三、（10分）設(shè)A、B和C是三個集合，則A?B??(B?A)。

證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)

???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)

??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))

??(B?A)。

四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i?1?4232－

15>}。

五、（10分）R是非空集合A上的二元關(guān)系，若R是對稱的，則r(R)和t(R)是對稱的。

證明對任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對稱的。

下證對任意正整數(shù)n，R對稱。

因R對稱，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對稱。若Rn對稱，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對稱。因此，對任意正整數(shù)n，Rn對稱。對任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是對稱的。

六、（10分）若f：A→B是雙射，則f：B→A是雙射。

證明因為f：A→B是雙射，則f是B到A的函數(shù)。下證f是雙射。

對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。

對任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因為f：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。

綜上可得，f：B→A是雙射。

七、（10分）設(shè)是一個半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明因為是一個半群，對任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因為S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j(luò)－i，則bj＝bp*bj。所以對q≥i，有bq＝bp*bq。

因為p≥1，所以總可找到k≥1，使得kp≥i。對于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，則a∈S且a*a＝a。

八、（20分）（1）若G是連通的平面圖，且G的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點數(shù)n有如下關(guān)系：

m≤

rl(n－2)。l?2l證明設(shè)G有r個面，則2m＝

2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii?

1（2）設(shè)平面圖G＝是自對偶圖，則| E|＝2(|V|－1)。

證明設(shè)G＝是連通平面圖G＝的對偶圖，則G? G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

離散數(shù)學(xué)考試試題（B卷及答案）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明因為S∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R附加前提

(2)P?RP

(3)?PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)Q?SP

(7)ST(5)(6)，I

(8)?R?SCP

(9)S∨RT(8)，E

二、（15分）根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。

(1)??x(P(x)?Q(x))P

(2)??x(?P(x)∨Q(x))T(1)，E

(3)?x(P(x)∧?Q(x))T(2)，E

(4)P(a)∧?Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)?Q(a)T(4)，I

(7)?x(P(x)?(A(x)∨B(x))P

(8)P(a)?(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)?x(A(x)?Q(x))P

(11)A(a)?Q(a)T(10)，US

(12)?A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)?x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。

解設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因為|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不會打這三種球的共5人。

四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和

i?1

3A3產(chǎn)生的小項。試證由A1、A2和A3所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。

證明小項共8個，設(shè)有r個非空小項s1、s2、…、sr(r≤8)。

對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。

i?1i?1i?1i?1rrrr

任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個劃分。

五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。

證明(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點數(shù)、邊數(shù)和面數(shù)。證明對G的邊數(shù)m作歸納法。

當(dāng)m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結(jié)論自然成立。

假設(shè)對邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對e分為下列情況來討論：

若e為割邊，則G?有兩個連通分支G1和G2。Gi的結(jié)點數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學(xué)歸納法知，結(jié)論成立。

七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：

(1)f?g是A到C的函數(shù)；

(2)對任意的x∈A，有f?g(x)＝f(g(x))。

證明(1)對任意的x∈A，因為g：A→B是函數(shù)，則存在y∈B使∈g。對于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因為g：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個元素對應(yīng)C中惟一的元素。

綜上可知，f?g是A到C的函數(shù)。

(2)對任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函數(shù)，則可寫為f?g(x)＝f(g(x))。

八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－

一個等價關(guān)系，且[a]R＝aH。

證明對于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，則a1*b∈H。因為H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，則a1*b∈H，b1*c∈H。因為H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

綜上可得，R是G中的一個等價關(guān)系。

對于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]R?aH。對任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R－

＝aH。

第三篇：離散數(shù)學(xué)習(xí)題五

習(xí)題五

1.設(shè)個體域D={a,b,c}，在D中消去公式?x(F(x)??yG(y))的量詞。甲乙用了不同的演算過程：

甲的演算過程如下： ?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))乙的演算過程如下：

?x(F(x)??yG(y))??xF(x)??yG(y)?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))

顯然，乙的演算過程簡單，試指出乙在演算過程中的關(guān)鍵步驟。

解：乙在演算中的關(guān)鍵步驟是，在演算開始就利用量詞轄域收縮與擴(kuò)張等值式，將量詞的轄域縮小，因而演算簡單。

2.設(shè)個體域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é)果都比較簡單

3.設(shè)個體域D={1,2}，請給出兩種不同的解釋I1和I2，使得下面公式在I1下都是真命題，而在I2下都是假命題。（1）?x(F(x)?G(x))（2）?x(F(x)?G(x))解：

解釋I1為：個體為實數(shù)集合R，F(xiàn)(x)：x為自然數(shù)，G(x)：x為整數(shù)。在I1下，（1）為自然數(shù)都是整數(shù)，（2）為存在整數(shù)為自然數(shù)。他們都是真命題

解釋I2為：個體域仍為實數(shù)集R，F(xiàn)(x)：x是無理數(shù)，G(x)：x能表示成分?jǐn)?shù)，在I2下，（1）為無理數(shù)都能表示成分?jǐn)?shù)，（2）為存在能表示成分?jǐn)?shù)的無理數(shù)，他們都是假命題

4.給定公式A??xF(x)??xF(x)

（1）在解釋I1中，個體域D1={a}，證明公式A在I1下的真值為1.（2）在解釋I2中，個體域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，此時，蘊(yùn)涵式前件為真，后件為假，故蘊(yùn)含式為假，若令F(x)；x為整數(shù)，則蘊(yùn)含式前后件均為真，所以（2）中公式在I2下為可滿足式

5.給定解釋I如下：（a）個體域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)

乙說甲錯了，乙說的對嗎？為什么？

解：乙說的對，甲錯了，全稱量詞?的指導(dǎo)變元x，轄域為(F(x)?G(x,y))，其中F(x)與G(x,y)都是x的約束變元，因而不能講量詞的轄域變小

7.請指出下面等值運(yùn)算的兩處錯誤

??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ò)張算值式時丟掉了否定連接詞?，演算的第二步，在原錯的基礎(chǔ)上又用錯了等值式

(F(x)?G(y)?H(x,y))和(F(x)?G(y)?H(x,y))不等值

8.在一階邏輯中將下列命題符號化，要求用兩種不同的等值形式（1）沒有小于負(fù)數(shù)的正數(shù)

（2）相等的兩個角未必都是對頂角 解：

（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是對頂角

9.設(shè)個體域D為實數(shù)集合，命題“有的實數(shù)既是有理數(shù)又是無理數(shù)”，這顯然是個假命題。可是某人卻說這是真命題，其理由如下

設(shè)F(x)：x是有理數(shù)，G(x）：x是無理數(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ù)這個人的結(jié)論對嗎？為什么？ 解：存在量詞對?無分配律

10.在求前束范式時有人說??x(F(x)?G(x,y))已是前束范式，理由是量詞已在公式的前面，他說的對嗎？為什么？

解：在前束范式中，否定聯(lián)結(jié)詞不能在量詞前面出現(xiàn) 11.有人說無法求公式

?x(F(x)?G(x))??xG(x,y)的前束范式，因為公式中的兩個量詞的指導(dǎo)變元相同。他的理由對嗎？為什么？ 換名規(guī)則可以使兩個指導(dǎo)變元不相同 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.將下列命題符號化，要求符號化的公式權(quán)威前束范式：（1）有點火車比有的汽車跑的快（2）有的火車比所有的汽車跑的快

（3）說有的火車比所有汽車跑得快是不對的（4）說有的飛機(jī)比有的汽車慢也是不對的 解：

（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中，指出下面各證明序列中的錯誤：（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）對F(x)??xG(x)不能使用EI規(guī)則，它不是前束范式，首先化成前束范式F(x)??xG(x)??x(F(y)?G(x))，因為量詞轄域(F(y)?G(x)中，除了x還有自由出現(xiàn)的y所以不能用EI規(guī)則

（2）對?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為個體常項，不能對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化簡

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.找一個解釋I，在I下，使得?xF(x)??xG(x)為真，而使得?x(F(x)??G(x))為假，從而說明?xF(x)??xG(x)??x(F(x)??G(x))。解：取個體域為自然數(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題可知兩公式并不等價。

①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且說，由附加前提證明法可知，推理正確，請指出以上證明的錯誤。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))化簡

?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)造下面推理的證明：

沒有白色的烏鴉，北京鴨都是白色的。因此，北京鴨都不是烏鴉。

設(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）每個有理數(shù)都是實數(shù)。有的有理數(shù)是整數(shù)。因此，有的實數(shù)是整數(shù)9（2）有理數(shù)，無理數(shù)都是實數(shù)。虛數(shù)不是實數(shù)。因此，虛數(shù)既不是有理數(shù)也不是無理數(shù)。

（1）設(shè)F(x):x是有理數(shù)，G(x)：x實數(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是無理數(shù)，H(x):x是實數(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)造下面推理的證明：

每個喜歡不行的人都不喜歡騎自行車。每個人或者喜歡騎自行車或者喜歡乘汽車。有的人不喜歡乘汽車，所以有的人不喜歡步行。（個體域為人類集合）

設(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)造下列推理的證明（個體域為人類集合）：

每個科學(xué)工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(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假言推論

第四篇：離散數(shù)學(xué)課后習(xí)題答案

第一章部分課后習(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．判斷下面一段論述是否為真：“?是無理數(shù)。并且，如果3是無理數(shù)，則2也是無理數(shù)。另外，只有6能被2整除，6才能被4整除。”

答：p: ?是無理數(shù)

q: 3是無理數(shù)

0

r: 2是無理數(shù)

s: 6能被2整除t: 6能被4整除

0

命題符號化為： 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.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.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 ①化簡律 ③q?s 前提引入 ④s?t 前提引入

⑤q?t ③④等價三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡 ⑧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 ④化簡律 ⑥r(nóng)?￢s 前提引入 ⑦r ⑥化簡律 ⑧r?﹁r ⑤⑦ 合取

由于最后一步r?﹁r 是矛盾式,所以推理正確.

第五篇：《離散數(shù)學(xué)》圖論部分習(xí)題

《離散數(shù)學(xué)》圖論部分習(xí)題

1.已知無向圖G有12條邊，6個3度頂點，其余頂點的度數(shù)均小于3，問G至少有幾個頂點？并畫出滿足條件的一個圖形.（24-3*6）/2 +6=9 2.是否存在7階無向簡單圖G，其度序列為1、3、3、4、6、6、7.給出相應(yīng)證明.不存在；7階無向簡單圖G中最大度≤6 3.設(shè)d1、d2、…、dn為n個互不相同的正整數(shù).證明：不存在以d1、d2、…、dn為度序列的無向簡單圖.Max{d1，d2，…，dn}≥n，n階無向簡單圖G中最大度≤n-1 4.求下圖的補(bǔ)圖.5.1)試畫一個具有5個頂點的自補(bǔ)圖

2)是否存在具有6個頂點的自補(bǔ)圖，試說明理由。

對于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ù))階無向簡單圖，證明：G與G的補(bǔ)圖中奇度頂點個數(shù)相等.n(n>2且為奇數(shù))，奇度點成對出現(xiàn)

7.無向圖G中只有2個奇度頂點u和v，u與v是否一定連通.給出說明或證明。

只有2個奇度頂點u和v，如果不連通，在u和v在2個連通分支上，每個分支上僅有一個奇度頂點，與握手引理相矛盾。

8.圖G如下圖所示：

1)寫出上圖的一個生成子圖.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.說明：δ(G)=min{ d(v)| v?V } ；κ(G)=min{ |V’| |V’是圖G的點割集} ； λ(G)=min{ |E’| |E’是圖G的邊割集} 9.在什么條件下無向完全圖Kn為歐拉圖？

n為奇數(shù)時

10.證明：有橋的圖不是歐拉圖.假設(shè)是歐拉圖：橋的端點是u和v，并且圖各頂點度均為偶數(shù)； 橋為割邊，刪除橋，圖不再連通，u和v應(yīng)該在2各不同的連通分支上；且u和v度數(shù)變?yōu)槠鏀?shù)；由于其他頂點度數(shù)均為偶數(shù)，則u和v所在的連通分支上只有一個奇度頂點，與握手引理矛盾。

11.證明：有橋的圖不是哈密爾頓圖.若G是K2，顯然不是哈密爾頓圖；

否則n≥3，則橋的兩個端點u和v至少有一個不是懸掛頂點（容易證明懸掛頂點不是割點）；設(shè)u不是懸掛點，則u是割點，存在割點顯然不是哈密爾頓圖。

12.樹T有2個4度頂點，3個3度頂點，其余頂點全為樹葉，問T有幾片樹葉？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.證明：最大度Δ（T）≥k的樹T至少有k片樹葉。

設(shè)有n個頂點，其中x片樹葉

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3個連通分支的平面圖G有4個面，9條邊，求G的階數(shù).n-9+4=3+1

n=9

15.給出全部互不同構(gòu)的4階簡單無向圖的平面圖形。

16.如果G是平面圖, 有n個頂點、m條邊、f個面，G有k個連通分支。試?yán)脷W拉公式證明:：n-m+f=k+1.