第一篇：山東大學(xué)離散數(shù)學(xué)期末試題答案

數(shù)學(xué)建模作業(yè)

姓名：

王士彬 學(xué)院：

計算機(jī)科學(xué)與技術(shù)

班級：

2014級計科2班 學(xué)號：

201400130070

1.在區(qū)域x?[-2,2],y?[-2,3]內(nèi)繪制函數(shù)z=exp^(-x2-y2)曲面圖及等值線圖。解：

曲面圖如下：

>> x=-2:0.5:2;>> y=-2:0.5:3;>> [X,Y]=meshgrid(x,y);

>> Z=exp(-X.^2-``Y.^2);>> mesh(X,Y,Z)>>

等值線圖如下：

>> x=-2:0.5:2;>> y=-2:0.5:3;>> [X,Y]=meshgrid(x,y);

>> Z=exp(-X.^2-Y.^2);>> mesh(X,Y,Z)>> surf(X,Y,Z)>> surf(X,Y,Z)>> contour(X,Y,Z)>>

2.已知一組觀測數(shù)據(jù)，如表1所示.(1)試用差值方法繪制出x?[-2,4.9]區(qū)間內(nèi)的光滑曲線，并比較各種差值算法的優(yōu)劣.(2)試用最小二乘多項(xiàng)式擬合的方法擬合表中的數(shù)據(jù)，選擇一個能較好擬合數(shù)據(jù)點(diǎn)的多項(xiàng)式的階次，給出相應(yīng)多項(xiàng)式的系數(shù)和偏差平方和.(3)若表中數(shù)據(jù)滿足正態(tài)分布函數(shù)y(x)?221e?(x??)/2?.試用最小二乘非線性擬合2??的方法求出分布參數(shù)?,?值，并利用鎖求參數(shù)值繪制擬合曲線，觀察擬合效果.解：(1)分別用最領(lǐng)近插值，分段線性插值（缺省值），分段三次樣條插值，保形分段三次插值方法繪制在x?[-2,4.9]的光滑曲線，圖形如下：

樣條插值效果最好，其次線性插值，最近點(diǎn)插值效果最差，在這里效果好像不太明顯。最近點(diǎn)插值優(yōu)點(diǎn)就是速度快，線性插值速度稍微慢一點(diǎn)，但效果好不少。所以線性插值是個不錯的折中方法。樣條插值，它的目的是試圖讓插值的曲線顯得更平滑，為了這個目的，它們不得不利用到周圍若干范圍內(nèi)的點(diǎn)，不過計算顯然要比前兩種大許多。MATLAB文件如下： >> x0=-2:0.3:4.9;>> y0=[0.10289 0.11741 0.13158 0.14483 0.15656 0.16622 0.17332 0.17750 0.17853...0.17635 0.17109 0.16302 0.15255 0.1402 0.12655 0.11219 0.09768 0.08353...0.07015 0.05876 0.04687 0.03729 0.02914 0.02236];>> cx=-2:0.3:4.9;>> y1=interp1(cx,y0,cx,'nearest');>> y2=interp1(cx,y0,cx,'linear');>> y3=interp1(cx,y0,cx,'spline');>> y4=interp1(cx,y0,cx,'cubic');>> subplot(2,2,1),plot(cx,y0,'o',cx,y1,'-r'),title('Nearest Interpolant');

>> subplot(2,2,2),plot(cx,y0,'o',cx,y1,'-k'),title('Linear

Interpolant');>> subplot(2,2,3),plot(cx,y0,'o',cx,y1,'-b'),title('Spline Interpolant');>> subplot(2,2,4),plot(cx,y0,'o',cx,y1,'-k'),title('Cubic Interpolant');>> subplot(2,2,1),plot(cx,y0,'o',cx,y1,'-r'),title('Nearest Interpolant');(2),從圖形可以看出曲線函數(shù)遵從冪函數(shù)的形式，設(shè)冪函數(shù)形式為：y??x?可化為lny?ln???lnx.即把非線性函數(shù)轉(zhuǎn)化為線性函數(shù)，原線性函數(shù)形式為p(x)?a1x?a0

由此我們可以得出p(x)等價于lny;x等價于lnx;??a1，ln??a0 我們可以先求出a1,a0。

求一個線性多項(xiàng)式p(x)?a1x?a0使之在最小二乘準(zhǔn)則下擬合這些觀測值，問題即化為

m????求a0,a1使E(a0,a1)=min?[yi?(a1xi?a0)]利用多元函數(shù)極值原理可知，若目標(biāo)函數(shù)a0,a1i?12E(a0,a1)的極小值存在，一定有結(jié)果。>> log(x0);>> log(y0);>> x0=log(x0);>> y0=log(y0);>> n=length(x0);>> a=sum(x0);>> b=sum(y0);>> c=sum(x0.*y0);>> d=sum(x0.^2);>> a0=(d*b-c*a)*(n*d-a^2);>> a1=(n*c-a*b)/(n*d-a^2);>> a0,a1 a0 =-2.5891e+050.3558i 即系數(shù)a0為

-2.5891e+050.3558i 其相應(yīng)多項(xiàng)式的系數(shù)和偏差平方和.我們可以求出E=-7.2019e+13 + 2.1767e+13i 其MATLAB文件如下： >> Y=a1*x0+a0;>> e=Y-y0;>> E=sum(e.^2)E =

-7.2019e+13 + 2.1767e+13i

即其相應(yīng)多項(xiàng)式的系數(shù)和偏差平方和.為

-7.2019e+13 + 2.1767e+13i(3)？

3.將某物體放置在空氣中，在t=0時刻測得其溫度u0=150度，10min后測得溫度u1=87度，假設(shè)空氣的溫度為24度。試建立數(shù)學(xué)模型給出物體的溫度u與時間t的關(guān)系，并計算20min后物體的溫度。

解：為了解決上述問題，我們首先需要了解有關(guān)熱力學(xué)的一些基本規(guī)律：比如：熱量總是從溫度高的物體向溫度低的物體傳導(dǎo)的；在一定的溫度范圍（其中包括了上述問題的溫度在內(nèi)），一個物體的溫度與這物體的溫度和其所在介質(zhì)的溫度的差值成正比例。這是已為實(shí)驗(yàn)證明了的牛頓冷卻定律。

設(shè)空氣的溫度為ua ,物體在時刻t的溫度為u?u(t)，則溫度的變化速度du。注意熱量總是從溫度高的物體向溫度低的物體傳導(dǎo)的，因而初始溫dt度大于空氣溫度，即（u0>ua），所以溫差u-ua恒正；又因?yàn)槲矬w的溫度將隨

du時間而逐漸冷卻，故溫度變化速度恒負(fù)。因此，由牛頓冷卻定律得到

dtdu??K(u?ua)............(1)dt這里的K>0是比例常數(shù)。此（1）方程就是冷卻過程的數(shù)學(xué)模型。

為了確定溫度u與時間t的關(guān)系，我們需要從上面（1）的方程中解出u。又因?yàn)閡a是常數(shù)，并且u-ua>0,所以我們可以將上述式子改寫成

d(u?ua)??Kdt

將此式積分可得到如下式子

u?ua為ln(u?ua)??Kt?c1

u?ua?e^(?Kt?c1)?ce^(?Kt)即u=ua+ce^(-Kt)根據(jù)初始條件：t=0時，u=u0代入上式得 c=u0-ua 于是u=u0+(u0-ua)e^(-Kt)

又根據(jù)條件，當(dāng)t=10時，u=u1代入上式得

u1=ua+(u0-ua)e^(-10K)?

1K?ln[(u0-ua)/(u1-ua)] 10根據(jù)題意我們可知u0=150，u1=87,ua=24,代入得到

1150?241K=ln=ln2=0.069 1087?2410從而u=24+126e^(-0.069t)這就是物體冷卻時溫度u隨著時間t的變化規(guī)律。用t=20代入得u=55.7度

4.假設(shè)在某商場中，某種商品在t時刻的價格為P(t)，若假定其變化率與商品的需求量D和供給量S之差成正比(比例系數(shù)為k),若

D?a?bP,S??c?dP

其中a,b,c,d均為正常數(shù)，若已知初始價格為Po,求任意時刻t時該商品的價格。

解：一般情況下，某種商品的價格主要服從市場供求關(guān)系，由題意我們可知商品需求量D是價格P的單調(diào)遞減函數(shù)，商品供給量S是價格P的單調(diào)遞增函數(shù)，即

D?a?bP,S??c?dP----(1)其中a,b,c,d均為常數(shù)，且b>0,d>0.當(dāng)需求量與供給量相等時，由(1)可得供求平衡時的價格Pe=

a?c，并稱Pe

b?d為均衡價格。

由題意得：

dp?k[D(p)?S(p)] dt其中比例系數(shù)k>0，用來反應(yīng)價格的調(diào)整進(jìn)度。將(1)式代入方程可得

其中常數(shù)=k(b+d)?>0，所以此方程的通解為 P(t)=Pe+Ce^(-?t)

由于初始價格P(0)=P0代入上式，得C=P0-Pe于是我們可以求出任意時刻價格P與時刻t之間的函數(shù)為：

P(t)=Pe+(P0-Pe)^(-?t)，并且我們可以得出，因?yàn)?>0知，t???時P(t)?Pe，說明隨著時間的不斷推延，實(shí)際價格P(t)將逐漸趨近均衡價格Pe。

5.農(nóng)場種植計劃問題

某農(nóng)場根據(jù)土地的肥沃程度，把耕地分為I II III三等，相應(yīng)的耕地面積分別為100、300和200km2,計劃種植水稻、大豆和玉米.要求三種作物的最低收獲量分別為190、130和350噸(t).I、II、III等耕地種植三種作物的單產(chǎn)如表所示.若三種作物的售價分別為水稻1.2元/kg,大豆1.50元/kg，玉米0.80元/kg.那么

(1)如何制訂種植計劃，才能使總產(chǎn)量最大？(2)如何制訂種植計劃，才能使總產(chǎn)值最大？

解：

(1):?問題分析：

確定種植最佳土地分配，即每種等級耕地分別種植水稻、大豆、玉米的面積

?模型建立：

1，決策變量：令x1,x2,x3分別為I II III三等耕地上種植的水稻面積，令x4,x5,x6分別為I II III三等耕地上種植的大豆面積，令x7,x8,x9分別為I II III三等耕地上種植的玉米面積。且令為xi（1<=i<=9）面積的耕地上的產(chǎn)量為ci.2,目標(biāo)函數(shù)：總產(chǎn)量最大，即max=?i?1cixi

3,約束條件：

最低產(chǎn)量限制：最低水稻產(chǎn)量190噸，最低大豆產(chǎn)量130噸，最低玉米產(chǎn)量350噸

11x1+9.5x2+9x3≧190

8x4+6.8x5+6x6≧130

14x7+12x8+10x9≧350

耕地面積恒定：x1 +x4+x7=100

x2+x5+x8=300

x3+x6+x9=200

非負(fù)條件：x1，x2，x3，x4，x5，x6，x7，x8，x9≧0

?數(shù)學(xué)模型：

max=11x1+9.5x2+9x3+8x4+6.8x5+6x6+14x7+12x8+10x9?-11x1-9.5x2-9x3??190?-8x4-6.8x5-6x6??130??-14x7-12x8-10x9??350??x1 +x4+x7=100? ?x2+x5+x8=300?x3+x6+x9=200?，x2，x3，x4，x5，x6，x7，x8，x9?0?x1???? 用MATLAB求解，用命令格式III，文件如下：

>>c=[11 9.5 9 8 6.8 6 14 12 10];>> A=[-11-9.5-9 0 0 0 0 0 0 0 0 0-8-6.8-6 0 0 0 0 0 0 0 0 0-14-12-10];>> b=[-190;-130;-350];>> Aeq=[1 0 0 1 0 0 1 0 0

0 1 0 0 1 0 0 1 0

0 0 1 0 0 1 0 0 1];>> beq=[100;300;200];>> vlb=[0;0;0;0;0;0;0;0;0];>> vub=[];>> [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)Optimization terminated.x =

17.2727

0.0000

0.0000

82.7273

300.0000

165.0000

0.0000

0.0000

35.0000 fval =

4.2318e+03

即，模型的最優(yōu)解為(17.2727 0.0 0.0 82.7273 300.0 165.0

0.0 0.0 35.0)T,目標(biāo)函數(shù)最優(yōu)值為4.231?103

即：x1，x2，x3，x4，x5，x6，x7，x8，x9值分別為17.2727 0.0 0.0 82.7273 300.0 165.0

0.0 0.0 35.0，此時才能使總產(chǎn)量最大。(2)問題分析：

根據(jù)題(1),當(dāng)要求得產(chǎn)值最大時,目標(biāo)函數(shù)只需變成Max

=1.2(11x1+9.5x2+9x3)+1.5(8x4+6.8x5+6x6)+0.8(14x7+12x8+10x9)

=13.2x1+11.4x2+10.8x3+12x4+10.2x5+9x6+11.2x7+9.6x8+8x9 MATLAB求解，部分文件如下：

>> c=[13.2 11.4 10.8 12 10.2 9 11.2 9.6 8];>> [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)Optimization terminated.x =

17.2727

0.0000

0.0000

0.0000

19.1176

0.0000

82.7273

280.8824

200.0000 fval =

5.6460e+03

即，模型的最優(yōu)解(17.2727 0.0 0.0 0.0 19.1176 0.0 82.7273 280.8824 200.0)T目標(biāo)函數(shù)最優(yōu)值5.646?103

即：x1，x2，x3，x4，x5，x6，x7，x8，x9值分別為17.2727 0.0 0.0 0.0 19.1176 0.0 82.7273 280.8824 200.0，此時才能使總產(chǎn)值最大。

第二篇：離散數(shù)學(xué)試題答案[范文]

《計算機(jī)數(shù)學(xué)基礎(chǔ)》離散數(shù)學(xué)試題

一、單項(xiàng)選擇題(每小題2分，共10分)1.命題公式(P?Q)?Q為()

(A)矛盾式(B)可滿足式(C)重言式(D)合取范式

2.設(shè)C(x): x是國家級運(yùn)動員，G(x): x是健壯的，則命題“沒有一個國家級運(yùn)動員不是健壯的”可符號化為()

(A)??x(C(x)??G(x))(B)??x(C(x)??G(x))

(C)??x(C(x)??G(x))(D)??x(C(x)??G(x))

3.設(shè)集合A={{1,2,3}, {4,5}, {6,7,8}}，則下式為真的是()

(A)1?A(B){1,2, 3}?A

(C){{4,5}}?A(D)??A

4.設(shè)A＝{1,2},B={a,b,c},C={c,d}, 則A×(B?C)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.如第5題圖所示各圖，其中存在哈密頓回路的圖是()

二、填空題(每小題3分，共15分)

6.設(shè)集合A={?,{a}}，則A的冪集P(A7.設(shè)集合A={1,2,3,4 }, B={6,8,12}, A到B的關(guān)系R＝{?x,y?y?2x,x?A,y?B},那么R1＝

8.圖G如第8題圖所示，那么圖G的割點(diǎn)是－abfced第8題圖

9.連通有向圖D含有歐拉回路的充分必要條件是.10.設(shè)X＝{a,b,c}，R是X上的二元關(guān)系，其關(guān)系矩陣為

?101??，那么R的關(guān)系圖為MR＝?100????100??

三、化簡解答題(每小題8分，共24分)11.簡化表達(dá)式(((A?(B?C))?A)?(B?(B?A)))?(C?A).12.設(shè)代數(shù)系統(tǒng)(R*, ?)，其中R*是非0實(shí)數(shù)集，二元運(yùn)算?為：?a,b?R, a?b=ab.試問?是否滿足交換律、結(jié)合律，并求單位元以及可逆元素的逆元.13.化簡布爾表達(dá)式a?a?b(c?a?b).四．計算題(每小題8分，共32分)

14.求命題公式(P?Q)?(?P??Q)的真值表.15.試求謂詞公式?x(P(x)??xQ(x,y)??yR(x,y))?A(x,y)中，?x,?x,?y的轄域，試

問R(x,y)和A(x,y)中x,y是自由變元，還是約束變元？16.設(shè)R1是A1＝{1,2}到A2＝(a,b,c)的二元關(guān)系，R2是A2到A3＝{?,?}的二元關(guān)系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}試用關(guān)系矩陣求R1?R2的集合表達(dá)式.v

217圖G如第17題圖

求圖G的最小生成樹.v4v

3第17題圖

五、證明題(第18題10分，第19題9分)18.證明(P?Q)?((?Q?R)??R)?(P??S))??S19.設(shè)G為9個結(jié)點(diǎn)的無向圖，每個結(jié)點(diǎn)的度數(shù)不是5就是6，試證明G中至少有5個度數(shù)為6的結(jié)點(diǎn)，或者至少有6個度數(shù)為5的結(jié)點(diǎn).《計算機(jī)數(shù)學(xué)基礎(chǔ)》離散數(shù)學(xué)試題

之五解答

一、單項(xiàng)選擇題(每小題2分，共15分)1.B2.D3.C4.A5.C

二、填空題(每小題3分，共15分)6.{?,{?},{{a}},{?,{a}}}

7.{<6,3>,<8,4> }8.a, f9.D中每個結(jié)點(diǎn)的入度＝出度.10.見第10題答案圖.三、化簡解答題(每小題8分，共24分)(((A?(B?C))?A)?(B?(B?A)))?(C?A)

c第10題答案圖

?(A?(B?(~B?A)))?(C?A)（2分）

?(A?(A?B))?(C?A)?A?C?~A)??

（4分）

（6分）（8分）

12.?a,b,c?R*, a?b=ab=ba=b?a，可交換；(2分)(a?b)?c=ab?c=abc=a(bc)=a?(bc)=a?(b?c)，可結(jié)合.(4分)易見，單位元為1.(6分)

對?a?R*, a?a1=aa1=1=a1a＝a1?a，故a的逆元：a?1?

－

－

－

－

(8分)a

13.a?a?b(c?a?b)

＝a?a?b?c?a?a?b(2分)

＝a?a?b(5分)＝(a?a)?(a?b)?a?b(8分)

四、計算題(每小題8分，共32分)

表中最后一列的數(shù)中，每對1個數(shù)得2分.15.?x的轄域：(P(x)??xQ(x,y)??yR(x,y))(2分)?x的轄域：Q(x,y)(4分)?y的轄域：R(x,y)(6分)R(x,y)中的x,y是約束變量，A(x,y)中的x,y是自由變量.(8分)

?110?

16.MR1???,(2分)

001??

?01?

?(4分)MR2??01????00??

?01?

?110?????01?(6分)MR1?R2??01?????

?001??00??00?

??

R1?R2?{?1,??}(8分)

v217圖G的最小生成樹，如第17題答案圖.首先選對邊(v 1, v 2)得2分，再每選對一條邊得分.v4v

3第17題答案圖

五、證明題(第18題10分，第19題9分，共19分)18.①?Q?RP（2分）②?RP(4分)

③?Q①，②析取三段論

④P?QP(7分)

⑤?P③，④拒取式⑥P??SP

⑦?S⑤，⑥析取三段論(10分)

19.由第5章定理1(握手定理)的推論，G中度數(shù)為5的結(jié)點(diǎn)個數(shù)只能是0,2,4,6,8五種情況；(3分)此時，相應(yīng)的結(jié)點(diǎn)度數(shù)為6的結(jié)點(diǎn)個數(shù)分別為9，7，5，3，1個，(6分)

以上五種對應(yīng)情況(0,9),(2,7),(4,5),(6,3),(8,1)，每對情況，兩數(shù)之和為9，且滿足第2個數(shù)大于或等于5，或者第1個數(shù)大于或等于6，意即滿足至少有度數(shù)為6的結(jié)點(diǎn)5個，或者至少有度數(shù)為5的結(jié)點(diǎn)6個,(9分)

第三篇：2002年4月離散數(shù)學(xué)試題答案

004km.cn 專注于收集各類歷年試卷和答案

更多試卷答案下載 免費(fèi)試聽網(wǎng)校課程

2002年4月離散數(shù)學(xué)試題答案

課程代碼：02324

一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)

1.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空題 16.0 17.1

0 18.單位元

19.x∩y

x∪y 20.入射

滿射

21.［x］R=［y］R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)24.可滿足式

永假式(或矛盾式)25.陳述句

真值

三、計算題

?1??126.M=??1?0??2?2?2M=??2?1?442ij***10??0??1?1??

0??1?? 1?1????Mi?1j?1?18, ?Mij?6

i?1

2G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。27.當(dāng)n是偶數(shù)時，?x∈P(A),xn=?

當(dāng)n是奇數(shù)時，?x∈P(A),x=x

?

于是：當(dāng)n是偶數(shù)，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=??(｛a｝-1)n｛b｝n｛a｝n=???

當(dāng)n是奇數(shù)時，??n



(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

-1-1nnn

=｛a｝｛b｝｛a｝?(｛a｝)｛b｝｛a｝

-1-=｛a｝｛b｝｛a｝?｛a｝｛b｝｛a｝=? 28.(1)偏序關(guān)系R的哈斯圖為

004km.cn 專注于收集各類歷年試卷和答案

(2)B的最大元：無，最小元：無；

極大元：2，5，極小元：1，3

下界：4，下確界4；

上界：無，上確界：無

29.原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命題為真的賦值是P=1,Q=0和P=1,Q=1 30.令e1=(v1,v3)，e2=(v4,v6)

e3=(v2,v5)，e4=(v3,v6)

e5=(v2,v3)，e6=(v1,v2)

e7=(v1,v4)，e8=(v4,v3)

e9=(v3,v5)，e10=(v5,v6)

令ai為ei上的權(quán)，則

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=15 31.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2)

(換名)

?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2)

??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2)

??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、證明題

32.設(shè)T中有x片樹葉，y個分支點(diǎn)。于是T中有x+y個頂點(diǎn)，有x+y-1 條邊，由握手定理知T中所有頂點(diǎn)的度數(shù)之的

x?y

?d(vi)=2(x+y-1)。

i?又樹葉的度為1，任一分支點(diǎn)的度大于等于2

且度最大的頂點(diǎn)必是分支點(diǎn)，于是

004km.cn 專注于收集各類歷年試卷和答案

x?y

?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i?1

從而2(x+y-1)≥x+2y+2k-4

x≥2k-2 33.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空

(1)?f,g∈F,因?yàn)閒和g都是A到A的雙射函數(shù)，故f?g也是A到A的雙射函數(shù)，從而集合F關(guān)于運(yùn)算?是封閉的。

(2)?f,g,h∈F,由函數(shù)復(fù)合運(yùn)算的結(jié)合律有f?(g?h)=(f?g)?h故運(yùn)算?是可結(jié)合的。

(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，?〉中的幺元

(4)?f∈F,因?yàn)閒是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有f?f=f?f=IA,因此f-1是f的逆元

由此上知〈F，?〉是群 34.證明(?x)(A(x)→B(x))?

?x(┐A(x)∨B(x))

?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨…∨(┐A(an)∨B(an)))

?(┐A(a1)∨A(a2)∨…∨┐A(an)∨(B(a1)∨B(a2)∨…∨(B(an))

?┐(A(a1)∧A(a2)∧…∧A(an))∨(┐B(a1)∨B(a2)∨…∨(B(an))

?┐(?x)A(x)∨(?x)B(x)?(?x)A(x)→(?x)B(x)

五、應(yīng)用題

35.令p：他是計算機(jī)系本科生

q：他是計算機(jī)系研究生

r：他學(xué)過DELPHI語言

s:他學(xué)過C++語言

t:他會編程序

前提：(p∨q)→(r∧s),(r∨s)→t

結(jié)論：p→t

證①p

P(附加前提)

②p∨q

T①I

③(p∨q)→(r∧s)

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r(nóng)∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

T⑤⑥I 36.可以把這20個人排在圓桌旁，使得任一人認(rèn)識其旁邊的兩個人。

根據(jù)：構(gòu)造無向簡單圖G=,其中V={v1,v2,…，V20}是以20個人為頂點(diǎn)的集合，E中的邊是若任兩個人vi和vj相互認(rèn)識則在vi與vj之間連一條邊。

Vi∈V,d(vi)是與vi相互認(rèn)識的人的數(shù)目，由題意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在漢密爾頓回路。?

設(shè)C=Vi1Vi2…Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。

第四篇：《離散數(shù)學(xué)》期末復(fù)習(xí)

《離散數(shù)學(xué)》期末復(fù)習(xí)

內(nèi)容：第一章~第七章 題型：

一、選擇題（20%，每題2分）二．填空題（20%，每題2分）

三、計算題（20%，每題5分）

四、證明題（20%，每題5分）

五、判斷題（20%，每題2分）

第1章 數(shù)學(xué)語言與證明方法

1.1 常用的數(shù)學(xué)符號

1.計算常用的數(shù)學(xué)符號式子 1.2 集合及其表示法

1.用列舉法和描述法表示集合

2.判斷元素與集合的關(guān)系(屬于和不屬于)3.判斷集合之間的包含與相等關(guān)系，空集(E)，全集(?)4.計算集合的冪集

5.求集合的運(yùn)算：并、交、相對補(bǔ)、對稱差、絕對補(bǔ)

6.用文氏圖表示集合的運(yùn)算 7.證明集合包含或相等

方法一： 根據(jù)定義, 通過邏輯等值演算證明

方法二： 利用已知集合等式或包含式, 通過集合演算證明

1.3 證明方法概述

1、用如下各式方法對命題進(jìn)行證明。? 直接證明法：A?B為真

? 間接證明法：“A?B為真” ? “ ?B? ?A為真” ? 歸謬法(反證法)： A??B?0為真

? 窮舉法： A1?B, A2?B,…, Ak?B 均為真

? 構(gòu)造證明法：在A為真的條件下, 構(gòu)造出具有這種性質(zhì)的客體B ? 空證明法：“A恒為假” ? “A?B為真” ?平凡證明法：“B恒為真” ? “A?B為真” ? 數(shù)學(xué)歸納法： 第2章 命題邏輯

2.1 命題邏輯基本概念

1、判斷句子是否為命題、將命題符號化、求命題的真值（0或1）。

命題的定義和聯(lián)結(jié)詞(?, ?, ?, ?, ?)

2、判斷命題公式的類型

賦值或解釋.成真賦值,成假賦值；重言式(永真式)、矛盾式(永假式)、可滿足式:。2.2 命題邏輯等值演算

1、用真值表判斷兩個命題公式是否等值

2、用等值演算證明兩個命題公式是否等值

3、證明聯(lián)結(jié)詞集合是否為聯(lián)結(jié)詞完備集 2.3 范式

1、求命題公式的析取范式與合取范式

2、求命題公式的主析取范式與主合取范式（兩種主范式的轉(zhuǎn)換）

3、應(yīng)用主析取范式分析和解決實(shí)際問題 2.4 命題邏輯推理理論

1、用直接法、附加前提、歸謬法、歸結(jié)證明法等推理規(guī)則證明推理有效 第3章 一階邏輯

3.1 一階邏輯基本概念

1、用謂詞公式符號命題（正確使用量詞）

2、求謂詞公式的真值、判斷謂詞公式的類型 3.2 一階邏輯等值演算

1、證明謂詞公式的等值式

2、求謂詞公式的前束范式 第4章 關(guān)系

4.1 關(guān)系的定義及其表示

1、計算有序?qū)?、笛卡兒積

2、計算給定關(guān)系的集合

3、用關(guān)系圖和關(guān)系矩陣表示關(guān)系 4.2 關(guān)系的運(yùn)算

1、計算關(guān)系的定義域、關(guān)系的值域

2、計算關(guān)系的逆關(guān)系、復(fù)合關(guān)系和冪關(guān)系

3、證明關(guān)系運(yùn)算滿足的式子 4.3 關(guān)系的性質(zhì)

1、判斷關(guān)系是否為自反、反自反、對稱、反對稱、傳遞的2、判斷關(guān)系運(yùn)算與性質(zhì)的關(guān)系

3、計算關(guān)系自反閉包、對稱閉包和傳遞閉包 4.4 等價關(guān)系與偏序關(guān)系

1、判斷關(guān)系是否為等價關(guān)系

2、計算等價關(guān)系的等價類和商集

3、計算集合的劃分

4、判斷關(guān)系是否為偏序關(guān)系

5、畫出偏序集的哈期圖

6、求偏序集的最大元、最小元、極小元、極大元、上界、下界、上確界、下確界

7、求偏序集的拓?fù)渑判?第5章 函數(shù)

1.判斷關(guān)系是否為函數(shù) 2.求函數(shù)的像和完全原像

3.判斷函數(shù)是否為滿射、單射、雙射 4.構(gòu)建集合之間的雙射函數(shù) 5.求復(fù)合函數(shù)

6.判斷函數(shù)的滿射、單射、雙射的性質(zhì)與函數(shù)復(fù)合運(yùn)算之間的關(guān)系 7.判斷函數(shù)的反函數(shù)是否存在，若存在求反函數(shù) 第6章 圖

1.指出無向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的度數(shù)、最大度、最小度

2.指出有向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根據(jù)握手定理頂點(diǎn)數(shù)、邊數(shù)等

4.指出圖的平行邊、環(huán)、弧立點(diǎn)、懸掛頂點(diǎn)和懸掛邊 5.判斷給定的度數(shù)列能否構(gòu)成無向圖

6.判斷圖是否為簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補(bǔ)圖、生成子圖、導(dǎo)出子圖 8.判斷兩個圖是否同構(gòu) 6.2 圖的連通性

1.求圖中給定頂點(diǎn)通路、回路的距離

2.計算無向圖的連通度、點(diǎn)割集、割點(diǎn)、邊割集、割邊 3.判斷有向圖的類型：強(qiáng)連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示

1.計算無向圖的關(guān)聯(lián)矩陣 2.計算有向無環(huán)圖的關(guān)聯(lián)矩陣 3.計算有向圖的鄰接矩陣 4.計算有向圖的可達(dá)矩陣

5.計算圖的給定長度的通路數(shù)、回路數(shù) 6.4 幾種特殊的圖

1、判斷無向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹及其應(yīng)用 7.1 無向樹

1.判斷一個無向圖是否為樹

2.計算無向樹的樹葉、樹枝、頂點(diǎn)數(shù)、頂點(diǎn)度數(shù)之間的關(guān)系 3.給定無向樹的度數(shù)列，畫出非同構(gòu)的無向樹 4.求生成樹對應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng) 5.求最小生成樹 7.2 根樹及其應(yīng)用

1.判斷一個有向圖是否為根樹

2.求根樹的樹根、樹葉、內(nèi)點(diǎn)、樹高 3.求最優(yōu)樹

4.判斷一個符號串集合是否為前綴碼 5.求最佳前綴碼

6.用三種方法遍歷根樹

第五篇：離散數(shù)學(xué)期末試題

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

一、（10分）求(P?Q)?(P∧?(Q∨?R))的主析取范式 解：(P?Q)?(P∧?(Q∨?R))??(?(P∨Q))∨(P∧?Q∧R))

?(P∨Q)∨(P∧?Q∧R))

?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R)?(P∨Q)∧(P∨Q∨R)

?(P∨Q∨(R∧?R))∧(P∨Q∨R)?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R)?M0∧M1

?m2∨m3∨m4∨m5∨m6∨m7

二、（10分）在某次研討會的休息時間，3名與會者根據(jù)王教授的口音分別作出下述判斷： 甲說：王教授不是蘇州人，是上海人。乙說：王教授不是上海人，是蘇州人。丙說：王教授既不是上海人，也不是杭州人。

王教授聽后說：你們3人中有一個全說對了，有一人全說錯了，還有一個人對錯各一半。試判斷王教授是哪里人？

解 設(shè)設(shè)P：王教授是蘇州人；Q：王教授是上海人；R：王教授是杭州人。則根據(jù)題意應(yīng)有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R

王教授只可能是其中一個城市的人或者3個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因?yàn)?，若甲全錯了，則有?Q∧P，因此，乙全對。同理，乙全錯則甲全對。所以丙必是一對一錯。故王教授的話符號化為：

((?P∧Q)∧((Q∧?R)∨(?Q∧R)))∨((?Q∧P)∧(?Q∧R))?(?P∧Q∧Q∧?R)∨(?P∧Q∧?Q∧R)∨(?Q∧P∧?Q∧R)?(?P∧Q∧?R)∨(P∧?Q∧R)??P∧Q∧?R ?T 因此，王教授是上海人。

三、（10分）證明tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。

證明 設(shè)R是非空集合A上的二元關(guān)系，則tsr(R)是包含R的且具有自反性、對稱性和傳遞性的關(guān)系。

若R是包含R的且具有自反性、對稱性和傳遞性的任意關(guān)系，則由閉包的定義知r(R)?R。則 ''sr(R)?s(R)＝R，進(jìn)而有tsr(R)?t(R)＝R。

綜上可知，tsr(R)是包含R的且具有自反性、對稱性和傳遞性的最小關(guān)系。

四、（15分）集合A＝{a，b，c，d，e}上的二元關(guān)系R為R＝{，，，，，，，，，，，，，}，(1)寫出R的關(guān)系矩陣。

(2)判斷R是不是偏序關(guān)系，為什么？ 解(1)R的關(guān)系矩陣為： ''''?1??0M(R)??0??0?0?1111??1101?0101?

?0011?0001??(2)由關(guān)系矩陣可知，對角線上所有元素全為1，故R是自反的；rij＋rji≤1，故R是反對稱的；可計算對應(yīng)的關(guān)系矩陣為：

?1??0M(R2)??0??0?0?由以上矩陣可知R是傳遞的。

1111??1101?0101??M(R)

?0011?0001??

五、（10分）設(shè)A、B、C和D為任意集合，證明(A－B)×C＝(A×C)－(B×C)。證明：因?yàn)?/p>

∈(A－B)×C?x∈(A－B)∧y∈C

?(x∈A∧x?B)∧y∈C

?(x∈A∧y∈C∧x?B)∨(x∈A∧y∈C∧y?C)?(x∈A∧y∈C)∧(x?B∨y?C)?(x∈A∧y∈C)∧?(x∈B∧y∈C)?∈(A×C)∧?(B×C)?∈(A×C)－(B×C)所以，(A－B)×C＝(A×C－B×C)。

六、（10分）設(shè)f：A?B，g：B?C，h：C?A，證明：如果h?g?f＝IA，f?h?g＝IB，g?f?h＝IC，則f、g、h均為雙射，并求出f、g和h。

解 因IA恒等函數(shù)，由h?g?f＝IA可得f是單射，h是滿射；因IB恒等函數(shù)，由f?h?g＝IB可得g是單射，f是滿射；因IC恒等函數(shù)，由g?f?h＝IC可得h是單射，g是滿射。從而f、g、h均為雙射。

由h?g?f＝IA，得f＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。－

1－1

－1－1－1

－1

七、（15分）設(shè)是一代數(shù)系統(tǒng)，運(yùn)算*滿足交換律和結(jié)合律，且a*x＝a*y?x＝y(tǒng)，證明：若G有限，則G是一群。

證明 因G有限，不妨設(shè)G＝{a1，a2，…，an}。由a*x＝a*y?x＝y(tǒng)得，若x≠y，則a*x≠a*y。于是可證，對任意的a∈G，有aG＝G。又因?yàn)檫\(yùn)算*滿足交換律，所以aG＝G＝Ga。令e∈G使得a*e＝a。對任意的b∈G，令c*a＝b，則b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由運(yùn)算*滿足交換律得e*b＝b，所以e是關(guān)于運(yùn)算*的幺元。對任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由運(yùn)算*滿足交換律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每個元素都存在逆元。故G是一群。

八、（20分）（1）證明在n個結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。

證明 不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對應(yīng)的無向圖）。

設(shè)G中結(jié)點(diǎn)為v1、v2、…、vn。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結(jié)點(diǎn)相鄰，得新邊en?1，由此可見G中至少有n－1條邊。

2（2）給定簡單無向圖G＝，且|V|＝m，|E|＝n。試證：若n≥Cm?1＋2，則G是哈密爾頓圖。

2證明 若n≥Cm。?1＋2，則2n≥m－3m＋6（1）

2若存在兩個不相鄰結(jié)點(diǎn)u、v使得d(u)＋d(v)＜m，則有2n＝

w?V?d(w)＜m＋(m－2)(m－3)＋m＝m－

23m＋6，與（1）矛盾。所以，對于G中任意兩個不相鄰結(jié)點(diǎn)u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密爾頓圖。離散數(shù)考試試題（B卷及答案）

一、（10分）使用將命題公式化為主范式的方法，證明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。證明：因?yàn)?P?Q)?(P∧Q)??(?P∨Q)∨(P∧Q)

?(P∧?Q)∨(P∧Q)(Q?P)∧(P∨Q)?(?Q∨P)∧(P∨Q)?(P∧?Q)∨(?Q∧Q)∨(P∧P)∨(P∧Q)?(P∧?Q)∨P

?(P∧?Q)∨(P∧(Q∨?Q))?(P∧?Q)∨(P∧Q)∨(P∧?Q)?(P∧?Q)∨(P∧Q)所以，(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。

二、（10分）證明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，則D不愉快。

解 設(shè)A：A努力工作；B、C、D分別表示B、C、D愉快；則推理化形式為： A?B∨C，B??A，D??CA??D

(1)A 附加前提(2)A?B∨C P(3)B∨C T(1)(2)，I(4)B??A P(5)A??B

T(4)，E(6)?B T(1)(5)，I(7)C T(3)(6)，I(8)D??C P(9)?D T(7)(8)，I(10)A??D CP

三、（10分）證明?x?y(P(x)?Q(y))?(?xP(x)??yQ(y))。?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y))??x(?P(x)∨?yQ(y))??x?P(x)∨?yQ(y)???xP(x)∨?yQ(y)?(?xP(x)??yQ(y))

四、（10分）設(shè)A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}}

五、（15分）設(shè)X＝{1，2，3，4}，R是X上的二元關(guān)系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關(guān)系圖。(2)寫出R的關(guān)系矩陣。

(3)說明R是否是自反、反自反、對稱、傳遞的。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：

?1??0M(R)??1??1?反自反的；由于矩陣不對稱，R不是對稱的；

經(jīng)過計算可得

101110110??0? 0??0??(3)對于R的關(guān)系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是?1??0M(R2)??1??1?101110110??0??M(R)，所以R是傳遞的。?0?0??

六、（15分）設(shè)函數(shù)f：R×R?R×R，f定義為：f()＝。(1)證明f是單射。(2)證明f是滿射。(3)求逆函數(shù)f。

(4)求復(fù)合函數(shù)f?f和f?f。

證明(1)對任意的x，y，x1，y1∈R，若f()＝f()，則＝，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y(tǒng)1，故f是單射。

(2)對任意的∈R×R，令x＝－1－

1u?wu?wu?wu?wu?w，y＝，則f()＝<＋，－22222u?w>＝，所以f是滿射。2(3)f()＝<－1－1u?wu?w，>。22－1

－1(4)f?f()＝f(f())＝f()＝<

x?y?x?yx?y?(x?y)，>＝

444

55f?f()＝f(f())＝f()＝＝<2x，2y>。

七、（15分）給定群，若對G中任意元a和b，有a*b＝(a*b)，a*b＝(a*b)，a*b＝(a*b)，3試證是Abel群。

證明 對G中任意元a和b。

因?yàn)閍*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。

于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。

由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。

八、（15分）（1）證明在n個結(jié)點(diǎn)的連通圖G中，至少有n－1條邊。

證明 不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對應(yīng)的無向圖）。

設(shè)G中結(jié)點(diǎn)為v1、v2、…、vn。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號），連接v1和v2，得邊e1，還是由連通性，在v3、v4、…、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與v1、v2、…、vn?1中的某個結(jié)點(diǎn)相鄰，得新邊en?1，由此可見G中至少有n－1條邊。

（2）試給出|V|＝n，|E|＝(n－1)(n－2)的簡單無向圖G＝是不連通的例子。解 下圖滿足條件但不連通。

12344

333334

34333

4333

?133

?1?13

?122244 6