计算机数学基础离散数学试题.doc

《计算机数学基础》离散数学试题 一、单项选择题 每小题2分，共10分 1. 命题公式为 A 矛盾式 B 可满足式 C 重言式 D 合取范式 2. 设C x : x是国家级运动员，G x : 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 c,1 , 2,c C c,1 c,2 , D 1,c , c,2 5. 如第5题图所示各图，其中存在哈密顿回路的图是 二、填空题 每小题3分，共15分 6. 设集合A , a ，则A的幂集P A 7. 设集合A 1,2,3,4 , B 6,8,12 , A到B的关系R＝,那么R－1＝ 8.图G如第8题图所示， 那么图G的割点是 9. 连通有向图D含有欧拉回路 的充分必要条件是 . 10.设X＝ a,b,c ，R是X上的二元关系，其关系矩阵为 MR＝，那么R的关系图为 三、化简解答题 每小题8分，共24分 11. 简化表达式. 12. 设代数系统 R*, ，其中R*是非0实数集，二元运算 为： a,b R, a b ab. 试问 是否满足交换律、结合律，并求单位元以及可逆元素的逆元. 13. 化简布尔表达式. 四．计算题 每小题8分，共32分 14. 求命题公式的真值表. 15.试求谓词公式中， 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 a, , b, 试用关系矩阵求R1 R2的集合表达式. v1 v2 v5 v6 v8 v7 v4 v3 第17题图 五、证明题 第18题10分，第19题9分 18. 证明 19. 设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点. 《计算机数学基础》离散数学试题解答 一、单项选择题 每小题2分，共15分 1.B 2.D 3. C 4.A 5.C 二、填空题 每小题3分，共15分 6. 7. 6,3 , 8,4 8.a, f 9. D中每个结点的入度＝出度. 10. 见第10题答案图. 三、化简解答题 每小题8分，共24分 11 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 a－1 aa－1 1 a－1a＝a－1 a，故a的逆元： 8分 13. ＝ 2分 ＝ 5分 ＝ 8分 四、计算题 每小题8分，共32分 14. P Q P Q P Q P Q P Q P Q 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 表中最后一列的数中，每对1个数得2分. 15. x的辖域： 2分 x的辖域：Q x,y 4分 y的辖域：R x,y 6分 R x,y 中的x,y是约束变量，A x,y 中的x,y是自由变量. 8分 16. 2分 4分 6分 8分 v1 v2 v5 v6 v8 v7 v4 v3 第17题答案图 五、证明题 第18题10分，第19题9分，共19分 18. ① Q R P （2分） ② R P 4分 ③ Q ①，②析取三段论 ④P Q P 7分 ⑤ ③，④拒取式 ⑥P S P ⑦ 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分 1 3 A B C D 第5题图 7 4 a b f c e d 第8题图 a