山东大学离散数学期末试题答案

第一篇：山东大学离散数学期末试题答案

数学建模作业

姓名：

王士彬 学院：

计算机科学与技术

班级：

2014级计科2班 学号：

201400130070

1.在区域x[-2,2],y[-2,3]内绘制函数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.已知一组观测数据，如表1所示.(1)试用差值方法绘制出x[-2,4.9]区间内的光滑曲线，并比较各种差值算法的优劣.(2)试用最小二乘多项式拟合的方法拟合表中的数据，选择一个能较好拟合数据点的多项式的阶次，给出相应多项式的系数和偏差平方和.(3)若表中数据满足正态分布函数y(x)221e(x)/2.试用最小二乘非线性拟合2的方法求出分布参数,值，并利用锁求参数值绘制拟合曲线，观察拟合效果.解：(1)分别用最领近插值，分段线性插值（缺省值），分段三次样条插值，保形分段三次插值方法绘制在x[-2,4.9]的光滑曲线，图形如下：

样条插值效果最好，其次线性插值，最近点插值效果最差，在这里效果好像不太明显。最近点插值优点就是速度快，线性插值速度稍微慢一点，但效果好不少。所以线性插值是个不错的折中方法。样条插值，它的目的是试图让插值的曲线显得更平滑，为了这个目的，它们不得不利用到周围若干范围内的点，不过计算显然要比前两种大许多。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),从图形可以看出曲线函数遵从幂函数的形式，设幂函数形式为：yx可化为lnylnlnx.即把非线性函数转化为线性函数，原线性函数形式为p(x)a1xa0

由此我们可以得出p(x)等价于lny;x等价于lnx;a1，lna0 我们可以先求出a1,a0。

求一个线性多项式p(x)a1xa0使之在最小二乘准则下拟合这些观测值，问题即化为

m求a0,a1使E(a0,a1)=min[yi(a1xia0)]利用多元函数极值原理可知，若目标函数a0,a1i12E(a0,a1)的极小值存在，一定有结果。>> 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 即系数a0为

-2.5891e+050.3558i 其相应多项式的系数和偏差平方和.我们可以求出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

即其相应多项式的系数和偏差平方和.为

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

3.将某物体放置在空气中，在t=0时刻测得其温度u0=150度，10min后测得温度u1=87度，假设空气的温度为24度。试建立数学模型给出物体的温度u与时间t的关系，并计算20min后物体的温度。

解：为了解决上述问题，我们首先需要了解有关热力学的一些基本规律：比如：热量总是从温度高的物体向温度低的物体传导的；在一定的温度范围（其中包括了上述问题的温度在内），一个物体的温度与这物体的温度和其所在介质的温度的差值成正比例。这是已为实验证明了的牛顿冷却定律。

设空气的温度为ua ,物体在时刻t的温度为uu(t)，则温度的变化速度du。注意热量总是从温度高的物体向温度低的物体传导的，因而初始温dt度大于空气温度，即（u0>ua），所以温差u-ua恒正；又因为物体的温度将随

du时间而逐渐冷却，故温度变化速度恒负。因此，由牛顿冷却定律得到

dtduK(uua)............(1)dt这里的K>0是比例常数。此（1）方程就是冷却过程的数学模型。

为了确定温度u与时间t的关系，我们需要从上面（1）的方程中解出u。又因为ua是常数，并且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)根据初始条件：t=0时，u=u0代入上式得 c=u0-ua 于是u=u0+(u0-ua)e^(-Kt)

又根据条件，当t=10时，u=u1代入上式得

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

1Kln[(u0-ua)/(u1-ua)] 10根据题意我们可知u0=150，u1=87,ua=24,代入得到

1150241K=ln=ln2=0.069 10872410从而u=24+126e^(-0.069t)这就是物体冷却时温度u随着时间t的变化规律。用t=20代入得u=55.7度

4.假设在某商场中，某种商品在t时刻的价格为P(t)，若假定其变化率与商品的需求量D和供给量S之差成正比(比例系数为k),若

DabP,ScdP

其中a,b,c,d均为正常数，若已知初始价格为Po,求任意时刻t时该商品的价格。

解：一般情况下，某种商品的价格主要服从市场供求关系，由题意我们可知商品需求量D是价格P的单调递减函数，商品供给量S是价格P的单调递增函数，即

DabP,ScdP----(1)其中a,b,c,d均为常数，且b>0,d>0.当需求量与供给量相等时，由(1)可得供求平衡时的价格Pe=

ac，并称Pe

bd为均衡价格。

由题意得：

dpk[D(p)S(p)] dt其中比例系数k>0，用来反应价格的调整进度。将(1)式代入方程可得

其中常数=k(b+d)>0，所以此方程的通解为 P(t)=Pe+Ce^(-t)

由于初始价格P(0)=P0代入上式，得C=P0-Pe于是我们可以求出任意时刻价格P与时刻t之间的函数为：

P(t)=Pe+(P0-Pe)^(-t)，并且我们可以得出，因为>0知，t时P(t)Pe，说明随着时间的不断推延，实际价格P(t)将逐渐趋近均衡价格Pe。

5.农场种植计划问题

某农场根据土地的肥沃程度，把耕地分为I II III三等，相应的耕地面积分别为100、300和200km2,计划种植水稻、大豆和玉米.要求三种作物的最低收获量分别为190、130和350吨(t).I、II、III等耕地种植三种作物的单产如表所示.若三种作物的售价分别为水稻1.2元/kg,大豆1.50元/kg，玉米0.80元/kg.那么

(1)如何制订种植计划，才能使总产量最大？(2)如何制订种植计划，才能使总产值最大？

解：

(1):问题分析：

确定种植最佳土地分配，即每种等级耕地分别种植水稻、大豆、玉米的面积

模型建立：

1，决策变量：令x1,x2,x3分别为I II III三等耕地上种植的水稻面积，令x4,x5,x6分别为I II III三等耕地上种植的大豆面积，令x7,x8,x9分别为I II III三等耕地上种植的玉米面积。且令为xi（1<=i<=9）面积的耕地上的产量为ci.2,目标函数：总产量最大，即max=i1cixi

3,约束条件：

最低产量限制：最低水稻产量190吨，最低大豆产量130吨，最低玉米产量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

非负条件：x1，x2，x3，x4，x5，x6，x7，x8，x9≧0

数学模型：

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

即，模型的最优解为(17.2727 0.0 0.0 82.7273 300.0 165.0

0.0 0.0 35.0)T,目标函数最优值为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，此时才能使总产量最大。(2)问题分析：

根据题(1),当要求得产值最大时,目标函数只需变成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

即，模型的最优解(17.2727 0.0 0.0 0.0 19.1176 0.0 82.7273 280.8824 200.0)T目标函数最优值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，此时才能使总产值最大。

第二篇：离散数学试题答案[范文]

《计算机数学基础》离散数学试题

一、单项选择题(每小题2分，共10分)1.命题公式(PQ)Q为()

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

2.设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()

(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.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A)1A(B){1,2, 3}A

(C){{4,5}}A(D)A

4.设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.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝

8.图G如第8题图所示，那么图G的割点是－abfced第8题图

9.连通有向图D含有欧拉回路的充分必要条件是.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为MR＝100100

三、化简解答题(每小题8分，共24分)11.简化表达式(((A(BC))A)(B(BA)))(CA).12.设代数系统(R*, )，其中R*是非0实数集，二元运算为：a,bR, ab=ab.试问是否满足交换律、结合律，并求单位元以及可逆元素的逆元.13.化简布尔表达式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.设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}试用关系矩阵求R1R2的集合表达式.v

217图G如第17题图

求图G的最小生成树.v4v

3第17题图

五、证明题(第18题10分，第19题9分)18.证明(PQ)((QR)R)(PS))S19.设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点.《计算机数学基础》离散数学试题

之五解答

一、单项选择题(每小题2分，共15分)1.B2.D3.C4.A5.C

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

7.{<6,3>,<8,4> }8.a, f9.D中每个结点的入度＝出度.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)，可结合.(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分)

表中最后一列的数中，每对1个数得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中度数为5的结点个数只能是0,2,4,6,8五种情况；(3分)此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个，(6分)

以上五种对应情况(0,9),(2,7),(4,5),(6,3),(8,1)，每对情况，两数之和为9，且满足第2个数大于或等于5，或者第1个数大于或等于6，意即满足至少有度数为6的结点5个，或者至少有度数为5的结点6个,(9分)

第三篇：2002年4月离散数学试题答案

www.xiexiebang.com 专注于收集各类历年试卷和答案

更多试卷答案下载 免费试听网校课程

2002年4月离散数学试题答案

课程代码：02324

一、单项选择题(本大题共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的路总数为18，长度为2的回路总数为6。27.当n是偶数时，x∈P(A),xn=

当n是奇数时，x∈P(A),x=x



于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=(｛a｝-1)n｛b｝n｛a｝n=

当n是奇数时，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)偏序关系R的哈斯图为

www.xiexiebang.com 专注于收集各类历年试卷和答案

(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上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=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.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的

xy

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

i又树叶的度为1，任一分支点的度大于等于2

且度最大的顶点必是分支点，于是

www.xiexiebang.com 专注于收集各类历年试卷和答案

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.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元

(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有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)

五、应用题

35.令p：他是计算机系本科生

q：他是计算机系研究生

r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

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

结论：p→t

证①p

P(附加前提)

②p∨q

T①I

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

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

T⑤⑥I 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2…Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

第四篇：《离散数学》期末复习

《离散数学》期末复习

内容：第一章~第七章 题型：

一、选择题（20%，每题2分）二．填空题（20%，每题2分）

三、计算题（20%，每题5分）

四、证明题（20%，每题5分）

五、判断题（20%，每题2分）

第1章 数学语言与证明方法

1.1 常用的数学符号

1.计算常用的数学符号式子 1.2 集合及其表示法

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

2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集

5.求集合的运算：并、交、相对补、对称差、绝对补

6.用文氏图表示集合的运算 7.证明集合包含或相等

方法一： 根据定义, 通过逻辑等值演算证明

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

1.3 证明方法概述

1、用如下各式方法对命题进行证明。 直接证明法：AB为真

 间接证明法：“AB为真”  “ ¬B ¬A为真”  归谬法(反证法)： A¬B0为真

 穷举法： A1B, A2B,…, AkB 均为真

 构造证明法：在A为真的条件下, 构造出具有这种性质的客体B  空证明法：“A恒为假”  “AB为真” 平凡证明法：“B恒为真”  “AB为真”  数学归纳法： 第2章 命题逻辑

2.1 命题逻辑基本概念

1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, , , , )

2、判断命题公式的类型

赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算

1、用真值表判断两个命题公式是否等值

2、用等值演算证明两个命题公式是否等值

3、证明联结词集合是否为联结词完备集 2.3 范式

1、求命题公式的析取范式与合取范式

2、求命题公式的主析取范式与主合取范式（两种主范式的转换）

3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论

1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑

3.1 一阶逻辑基本概念

1、用谓词公式符号命题（正确使用量词）

2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算

1、证明谓词公式的等值式

2、求谓词公式的前束范式 第4章 关系

4.1 关系的定义及其表示

1、计算有序对、笛卡儿积

2、计算给定关系的集合

3、用关系图和关系矩阵表示关系 4.2 关系的运算

1、计算关系的定义域、关系的值域

2、计算关系的逆关系、复合关系和幂关系

3、证明关系运算满足的式子 4.3 关系的性质

1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系

3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系

1、判断关系是否为等价关系

2、计算等价关系的等价类和商集

3、计算集合的划分

4、判断关系是否为偏序关系

5、画出偏序集的哈期图

6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界

7、求偏序集的拓扑排序 第5章 函数

1.判断关系是否为函数 2.求函数的像和完全原像

3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数

6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图

1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度

2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根据握手定理顶点数、边数等

4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图

6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性

1.求图中给定顶点通路、回路的距离

2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示

1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵

5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图

1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树

1.判断一个无向图是否为树

2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用

1.判断一个有向图是否为根树

2.求根树的树根、树叶、内点、树高 3.求最优树

4.判断一个符号串集合是否为前缀码 5.求最佳前缀码

6.用三种方法遍历根树

第五篇：离散数学期末试题

离散数学考试试题（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名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？

解 设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：P∧Q 乙：Q∧P 丙：Q∧R

王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有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的且具有自反性、对称性和传递性的最小关系。

证明 设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。

若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)R。则 ''sr(R)s(R)＝R，进而有tsr(R)t(R)＝R。

综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。

四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{，，，，，，，，，，，，，}，(1)写出R的关系矩阵。

(2)判断R是不是偏序关系，为什么？ 解(1)R的关系矩阵为： ''''10M(R)000111111010101

00110001(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：

10M(R2)000由以上矩阵可知R是传递的。

111111010101M(R)

00110001

五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。证明：因为

∈(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分）设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恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由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分）设是一代数系统，运算*满足交换律和结合律，且a*x＝a*yx＝y，证明：若G有限，则G是一群。

证明 因G有限，不妨设G＝{a1，a2，…，an}。由a*x＝a*yx＝y得，若x≠y，则a*x≠a*y。于是可证，对任意的a∈G，有aG＝G。又因为运算*满足交换律，所以aG＝G＝Ga。令e∈G使得a*e＝a。对任意的b∈G，令c*a＝b，则b*e＝(c*a)*e＝c*(a*e)＝c*a＝b，再由运算*满足交换律得e*b＝b，所以e是关于运算*的幺元。对任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由运算*满足交换律得b*a＝e，所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。

八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。

证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。

设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边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若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝

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

23m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。离散数考试试题（B卷及答案）

一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。证明：因为(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不愉快。

解 设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分）设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分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。

(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为：

10M(R)11反自反的；由于矩阵不对称，R不是对称的；

经过计算可得

1011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是10M(R2)111011101100M(R)，所以R是传递的。00

六、（15分）设函数f：R×RR×R，f定义为：f()＝。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f。

(4)求复合函数ff和ff。

证明(1)对任意的x，y，x1，y1∈R，若f()＝f()，则＝，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故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。

因为a*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个结点的连通图G中，至少有n－1条边。

证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。

设G中结点为v1、v2、…、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、…、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、…、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。

（2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝是不连通的例子。解 下图满足条件但不连通。

12344

333334

34333

4333

133

113

122244 6