离散数学试题答案_离散数学期末试题答案

离散数学试题答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学期末试题答案”。

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

一、单项选择题(每小题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){,}(B){,}(C){,}(D){,}

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= {，}, 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.{, }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分)