第一篇：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.陈述句
真值
三、计算题
1126.M=10222M=21442ij***10011
01 11Mi1j118, Mij6
i1
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) (换名) ┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2) x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2) x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2) 四、证明题 32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的 xy d(vi)=2(x+y-1)。 i又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是 www.xiexiebang.com 专注于收集各类历年试卷和答案 xy d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1 从而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的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。 (2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。 (3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元 (4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff=ff=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= Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。 设C=Vi1Vi2…Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。 《计算机数学基础》离散数学试题 一、单项选择题(每小题2分，共10分)1.命题公式(PQ)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)1A(B){1,2, 3}A (C){{4,5}}A(D)A 4.设A＝{1,2},B={a,b,c},C={c,d}, 则A×(BC)=() (A){<1,c>,<2,c>}(B){ 5.如第5题图所示各图，其中存在哈密顿回路的图是() 二、填空题(每小题3分，共15分) 6.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝ 8.图G如第8题图所示，那么图G的割点是－abfced第8题图 9.连通有向图D含有欧拉回路的充分必要条件是.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为 101，那么R的关系图为MR＝100100 三、化简解答题(每小题8分，共24分)11.简化表达式(((A(BC))A)(B(BA)))(CA).12.设代数系统(R*, )，其中R*是非0实数集，二元运算为：a,bR, ab=ab.试问是否满足交换律、结合律，并求单位元以及可逆元素的逆元.13.化简布尔表达式aab(cab).四．计算题(每小题8分，共32分) 14.求命题公式(PQ)(PQ)的真值表.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={ 217图G如第17题图 求图G的最小生成树.v4v 3第17题图 五、证明题(第18题10分，第19题9分)18.证明(PQ)((QR)R)(PS))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(BC))A)(B(BA)))(CA) c第10题答案图 (A(B(~BA)))(CA)（2分） (A(AB))(CA)AC~A) （4分） （6分）（8分） 12.a,b,cR*, ab=ab=ba=ba，可交换；(2分)(ab)c=abc=abc=a(bc)=a(bc)=a(bc)，可结合.(4分)易见，单位元为1.(6分) 对aR*, aa1=aa1=1=a1a＝a1a，故a的逆元：a1 － － － － (8分)a 13.aab(cab) ＝aabcaab(2分) ＝aab(5分)＝(aa)(ab)ab(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分)MR20100 01 11001(6分)MR1R201 0010000 R1R2{1,}(8分) v217图G的最小生成树，如第17题答案图.首先选对边(v 1, v 2)得2分，再每选对一条边得分.v4v 3第17题答案图 五、证明题(第18题10分，第19题9分，共19分)18.①QRP（2分）②RP(4分) ③Q①，②析取三段论 ④PQP(7分) ⑤P③，④拒取式⑥PSP ⑦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分) 数学建模作业 姓名： 王士彬 学院： 计算机科学与技术 班级： 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),从图形可以看出曲线函数遵从幂函数的形式，设幂函数形式为：yx可化为lnylnlnx.即把非线性函数转化为线性函数，原线性函数形式为p(x)a1xa0 由此我们可以得出p(x)等价于lny;x等价于lnx;a1，lna0 我们可以先求出a1,a0。 求一个线性多项式p(x)a1xa0使之在最小二乘准则下拟合这些观测值，问题即化为 m求a0,a1使E(a0,a1)=min[yi(a1xia0)]利用多元函数极值原理可知，若目标函数a0,a1i12E(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的温度为uu(t)，则温度的变化速度du。注意热量总是从温度高的物体向温度低的物体传导的，因而初始温dt度大于空气温度，即（u0>ua），所以温差u-ua恒正；又因为物体的温度将随 du时间而逐渐冷却，故温度变化速度恒负。因此，由牛顿冷却定律得到 dtduK(uua)............(1)dt这里的K>0是比例常数。此（1）方程就是冷却过程的数学模型。 为了确定温度u与时间t的关系，我们需要从上面（1）的方程中解出u。又因为ua是常数，并且u-ua>0,所以我们可以将上述式子改写成 d(uua)Kdt 将此式积分可得到如下式子 uua为ln(uua)Ktc1 uuae^(Ktc1)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) 1Kln[(u0-ua)/(u1-ua)] 10根据题意我们可知u0=150，u1=87,ua=24,代入得到 1150241K=ln=ln2=0.069 10872410从而u=24+126e^(-0.069t)这就是物体冷却时温度u随着时间t的变化规律。用t=20代入得u=55.7度 4.假设在某商场中，某种商品在t时刻的价格为P(t)，若假定其变化率与商品的需求量D和供给量S之差成正比(比例系数为k),若 DabP,ScdP 其中a,b,c,d均为正常数，若已知初始价格为Po,求任意时刻t时该商品的价格。 解：一般情况下，某种商品的价格主要服从市场供求关系，由题意我们可知商品需求量D是价格P的单调递减函数，商品供给量S是价格P的单调递增函数，即 DabP,ScdP----(1)其中a,b,c,d均为常数，且b>0,d>0.当需求量与供给量相等时，由(1)可得供求平衡时的价格Pe= ac，并称Pe bd为均衡价格。 由题意得： dpk[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=i1cixi 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-9x3190-8x4-6.8x5-6x6130-14x7-12x8-10x9350x1 +x4+x7=100 x2+x5+x8=300x3+x6+x9=200，x2，x3，x4，x5，x6，x7，x8，x90x1 用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.231103 即：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.646103 即：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，此时才能使总产值最大。 离散数学课件作业 第一部分 集合论 第一章集合的基本概念和运算 1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是[ B ] A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} A。 1-2 A,B,C 为任意集合，则他们的共同子集是[ D ] A．C；B．A；C．B；D．Ø。 1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？ （1）N Q，Q ∈S，则 N S［不成立］ （2）-1 ∈Z，Z ∈S，则-1 ∈S［不成立］ 1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø，C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，Ø，3，3}，试问哪两个集合之间可用等号表示 ？ 答：A = E；B = C；D = F 1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 } （2）A = { x│x ∈N 且 3－x 〈 3 } 答：（1）A = { 0，1，2，3 }； （2）A = { 1，2，3，4，……} = Z+； 第二章二元关系 2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈X 且 x≤ y } 求：(1)domR =?;(2)ranR =?;(3)R 的性质。 答：R = {<2，3>，<1,2>，<1,3>}； DomR={R中所有有序对的x}={2,1,1}={2,1}; RanR={R中所有有序对的y}={3,2,3}={3,2}； R 的性质:反自反,反对称,传递性质.2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，试求： （1）R 的列元表达式；（2）给出 dom（R。R）。 答：根据方程式有：y=4-x/3，x 只能取 3，6,9。 （1）R = {〈3，3〉,〈6，2〉,〈9，1〉}； 至于(2),望大家认真完成合成运算 R。R={<3,3>}.然后,给出 R。R 的定义域,即 （2）dom（R。R）= {3}。 2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→B 指出他的性质，即 是否单射、满射和双射，并说明为什么。 （1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。 （2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。 （3）A = B = R，f=x。 （4）A = B = N，f=x2。 （5）A = B = N，f = x + 1。 答：（1）是 A 到 B 的函数，是满射而不是单射； （2）是双射； （3）是双射； （4）是单射，而不是满射； （5）是单射而不是满射。 2-4 设 A ={1，2，3，4}，A 上的二元关系 R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1)=[C] A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。 2-5 设 A ={1，2，3}，则商集A/IA =[D] A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。 2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C] A．x+1；B．x-1；C．x；D．x2。 第三章 结构代数(群论初步) 3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？ （1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 *是普通乘法。 （2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ； 二元运算。定义如下：对于所有 ai，aj ∈S2，都有 ai。aj = ai。 （3）S3 = {0，1}，二元运算 * 是普通乘法。 答：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统。 （2）由二元运算的定义不难知道。在 S2 内是封闭的，所以，〈S2。〉构成代数 系统；然后看该代数系统的类型：该代数系统只是半群。 （3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异 点；而 0 为零元；结论：仅为独异点，而不是群。 3-2 在自然数集合上，下列那种运算是可结合的［A］ A．x*y = max(x,y)；B．x*y = 2x+y ； C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 设 Z 为整数集合，在 Z 上定义二元运算。，对于所有 x，y ∈Z都有 x。y=x + y，试问〈Z。〉能否构成群，为什麽 ？ 答：由题已知，集合Z满足封闭性；二元运算满足结合律，依此集合Z为半群；有幺元为 －5，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e。x= e + x，一个方程来自该特殊元素的定义的性质,即e。x = x.由此而来的两个方程联立结果就有: e+x=x 成立.削去 x,e=0 的结果不是就有了吗!；每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；结论是：代数系统〈 Z。〉构成群。 第二部分图论方法 第四章 图 4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？ 答：因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图 G 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有 10-4＝6 个奇数度顶点。 4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[是] 4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为[2] 第五章树 5-1握手定理的应用（指无向树） （1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有(有1个4度顶点)个？ （2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有(9个1度顶点)片？ 5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x= 答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = Σi（i—2）i + 2，（i = 2，3，……k）。 5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）T 的权 W（T）？（2）树高几层 ？ 答：用 Huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 T ；然后，计算并回答所求问题：（1）T 的权 W（T）= 61；（2）树高几层：4 层树高。 5-4以下给出的符号串集合中，那些是前缀码？将结果填入[]内.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非] 5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [非] 5-6(是非判断题)二元正则树有奇数个顶点。[是] 5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。 1、最优二元树 T；2.每个字母的码字； 答：每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号 出现次数即为权，如右下图).。100（近似）7.。563..4。282..2..2。..1..14141414111 1所以，得到编码如下：G（000），D（001），B（100），E（101），Y（01），O（11）。 第三部分逻辑推理理论 第六章 命题逻辑 6-1 判断下列语句是否命题，简单命题或复合命题。 （1）2月 17 号新学期开始。[真命题] （2）离散数学很重要。[真命题] （3）离散数学难学吗 ？[真命题] （4）C 语言具有高级语言的简洁性和汇编语言的灵活性。[复合命题] （5）x + 5 大于 2。[真命题] （6）今天没有下雨，也没有太阳，是阴天。[复合命题] 6-2 将下列命题符号化.（1）2 是偶素数。 （2）小李不是不聪明，而是不好学。 （3）明天考试英语或考数学。（兼容或） （4）你明天不去上海，就去北京。（排斥或） 答：（1）符号化为： p ∧ q。 （2）符号化为：p ∧ ﹃q。 （3）符号化为：p ∨ q。 （4）符号化为：（﹃p ∧ q）∨（p ∧ ﹃q）。 6-3分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0； （2）Σ（0，1，2，3）； （3）Σ（1，3）。 以下两题(6-4;6-5)为选择题,将正确者填入[]内.6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B] A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p 6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为［B］ A． p→q；B．q→p；C．p∧q；D．﹁q→p 6-6证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。 如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：将公式分成前提及结论。 前提：（p→﹃q），p； 结论：﹃q； 证明：（1）（p→﹃q）前提引入 （2）p前提引入 （3）（p→﹃q）∧p（1）（2）假言推理 （4）﹃q 要证明的结论与证明结果一致，所以推理正确。 第七章谓词逻辑 7-1 在谓词逻辑中用 0 元谓词将下列命题符号化 （1）这台机器不能用。 （2）如果 2 ＞ 3，则 2 ＞ 5。 答：（1）﹃F（a）。 （2）L（a，b）→ H（a，z）。 7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为（0） 7-3在谓词逻辑中将下列命题符号化 （1）有的马比所有的牛跑得慢。 （2）人固有一死。 答：（1）符号化为：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。 （2）与（1）相仿，要注意量词、联结词间的搭配： x（F（x）→y（G（y）→ H（x，y）））。 《附录》习题符号集 Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。 2010年8月12号。 浅谈离散数学 【摘要】离散数学是一门理论性强,知识点多,概念抽象的基础课程,学生学习起来普遍感到难度很高。本文从离散数学内容、学生学习兴趣的激发、教学内容的安排、教学方式方法的使用等方面,探讨了如何上好、学好离散数学课。 【关键词】离散数学教学方法教师 学生 离散数学研究的是离散量，是计算机科学与技术系各专业的核心课程。课程内容具有知识点多、散、抽象等特点,加之学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。因此,创新教学方法,提高学生自主学习的积极性,对提高学生的能力、提升教学质量和水平具有重要的意义。通过一学期的学习和专研,我积累了少许经验,总结了一些关于离散数学的教学方法，仅供大家参考。 一、离散数学的特点 本课程介绍计算机科学与技术系各专业所需要的离散数学基础知识,主要有以下两点特点： 1、知识点集中，概念和定理多：《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。培养学生抽象思维能力、逻辑推理能力、缜密概括能力以及分析和解决实际问题能力的主干课程,对学习其他诸多课程,具有重要的指导作用。《离散数学》的证明题多，不同的题型会需要不同的证明方法，同一个题也可能有几种方法，具有很强的方法性。 二、教学困难所在1、离散数学是一门理论性强,知识点多,概念抽象的基础课程, 内容具有知 识点多、散、抽象等特点，学生学者困难； 2、学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。 3、离散数学课程在课堂教学难度、教学时间等方面的原因,很多学校都出现师生、学生之间的交流较少，从而使学生学习困难。 三、离散数学的教学方法引导学生提高对离散数学课程应用性的认识,激发学生学习的兴趣和爱好,增强汲取知识的自主性 离散数学课程是一门基础性课程,学习离散数学课程对学生今后的学习和工作,具有重要的作用,例如培养学生的抽象思维能力和缜密的逻辑推理能力,为学生今后处理离散信息,提高专业理论水平,从事计算机的实际工作提供必备的数学工具;通过学习,可以掌握数理逻辑,集合论,代数结构和图论的基本概念和原理,并会运用离散数学的方法,分析和解决计算机理论和应用中的一些问题等。学习主动性是学生的力量之源,因此,引导学生充分认识学习离散数学课程的作用,能够激发学生学习的爱好和热情,提升学生学习的积极性和主动性,从而使学生学有成效。认真备课,合理准备教学内容和安排教学环节,优化教学方式方法 备好课是教学取得预期效果的前提和基础,针对学生学习具体情况,合理准备教学内容和安排教学环节,使用恰当的教学方法,在教学中可以起到事半功倍的效果。 (1)合理地准备教学内容。根据课程教学大纲和离散数学课程定理定义比较多、知识比较抽象的特点以及学生的实际情况,准备深度和广度适合学生特点的教学内容。 (2)合理地讲解课程内容,重难点突出讲解,注意轻重缓急。对于离散数学中比较重要、比较抽象的概念和定理,如逻辑的推理理论、关系的性质、群、图等,认真分析,用多种方式和方法深入 讲解,可以使用解析法、图示法、矩阵法举实例等多种方法讲解。对于比较容易理解和掌握的内容,可以一笔带过。这样,学生对所学内容就会有重点地学习,主次分明,学生不仅可以对所学内容掌握透彻,更能熟练把握离散数学中分析问题和解决问题的思路、方式和方法。 (3)启发式教学和教师讲授相结合。很多人认为,大学教学课时紧,内容多,关键靠学生自主学习,我却认为并不完全是这样的。如果教师不顾学生的理解情况,只顾在讲台上讲授知识,课堂氛围会很沉闷,很多同学不能专注于该门课程的学习,经常走神,教学很难达到预期的效果。因此,有针对性地提问和展开讨论,不仅能够培养学生的思考能力,更能调动学生学习的兴趣和积极性,从而使教学达到最佳效果。也可以引进有趣生动的例子说明概念，既活跃课堂，又巩固了学生的记忆。3 合理布置作业,认真批改作业,有针对性地安排习题课和课后答疑 学数学就要做数学，《离散数学》的学习也不例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学思维方法。为了强化学生能力的训练,培养学生的抽象思维能力、逻辑推理能力、实际问题的解决能力等,在保证作业数量的同时,更要提高布置作业的质量,增加典型简答题、讨论题、推理题、实际应用题等习题在作业中的分量,使学生在掌握各种基本知识和基本技能的同时,提高自身的综合能力。 认真检查和批改作业,是督促学生学习的主要途径,也是教师了解学生理解和掌握所学课程情况的主渠道。必要时,教师可以批改一部分作业,其他作业让同学们之间互相检查和批改,不仅可以督促学生学习,更能让学生在批改其他同学作业时逐步认识到自身的缺陷和不足,以备今后更有针对性地学习。 教师在作业检查和批改过程中发现的主要问题和疑难以及学生提出的有代表性的问题,有必要安排习题课进行讲解,帮助学生对解决疑难,加深对所知识的理解。对于学生比较争论的问题,可以展开讨论,鼓励学生大胆发言,培养学生探索未知的精神和创造性解决实际问题的能力。 四、总结 从此上看，上好离散数学课,关键是根据学生具体实际,有针 对性地安排教学内容,合理使用教学方式方法,最大限度地激发学生的学习兴趣,充分发挥教师的主导作用和学生的主体作用,达到教与学和谐。 参考文献 [1] 屈婉玲,耿素云,张立昂.离散数学[M].北京:高等教育出版社.2008.[2] 黄巍,金国祥.”离散数学”课程教学改革的探讨[J].中国电力教育,2009(8):82-83.[3] 周小燕,胡丰华.对提高离散数学教学质量的探讨[J].浙江科技学院学报,2007,19(2):156-158.[4] 龙浩,张佳佳.怎样教好《离散数学》课[J].贵阳学院学报,2007,2(1):53-57.[5] 廖仲春.离散数学的教学探讨[J].湖南工业职业技术学院学报,2008,8(5)http://第二篇：离散数学试题答案[范文]
第三篇：山东大学离散数学期末试题答案
第四篇：离散数学
第五篇：浅谈离散数学专题
点击咨询 