1、得 分一、单项选择题(每小题3分，本题共15分)100试卷代号：1009座位号 国家开放大学(中央广播电视大学)2016年春季学期“开放本科”期末考试离散数学(本) 试题(半开卷)2016年7月题号m#+二三四五六总 分分数评卷人1. 若集合A=1,2,3,4,B=1,3,5, 则下列表述正确的是( ). A. A=B B. BCAC. BA D. BSA2. 设 A=1,2,3,B=2,4,6,A 到 B 的关系R=|2x=y, 则 R=( ).A. ,B. ,C. ,D. ,3. 无向图G 是棵树，边数是10,则G 的结点度数之和是( ).A. 20 B. 9C. 10 D. 114. 下
2、面的推理正确的是( ).A.(1)(Vx)F(x)G(x)前提引入(2)F(y)G(y)US(1).B.(1)(3x)F(x)G(x)前提引入(2)F(y)G(y)US(1),C.(1)(3x)(F(x)G(x) 前提引入(2)F(y)G(x) ES(1),D.(1)(Vx)(F(x)G(x) 前提引入(2)F(y)G(y) US(1).得 分二、填空题(每小题3分，本题共15分)得 分三、逻辑公式翻译(每小题6分，本题共12分)5. 设个体域为整数集，则公式Vx3y(x+y=2) 的解释可为( ).A. 任一整数x, 对任意整数 y 满足x+y=2B. 对任一整数x, 存在整数 y 满足x+
3、y=2C. 存在一整数x, 对任意整数 y 满足x+y=2D. 存在一整数x, 有整数y 满足x+y=2评卷人6. 设集合A=1,2,3,B=2,3,4,C=3,4,5, 则 BU(A -C)等于7. 设 A=1,2,B=2,3,C=3,4, 从 A 到 B 的函数f=, 从 B到 C 的函数g=, 则 Ran(g f)等于8. 两个图同构的必要条件包括结点数相等、边数相等与分别表示G 的结点数，边数和面数，v 值为5 ,e 值 为 4 则r9. 设 G 是连通平面图，v,e,r的值为则谓词公式(3x)A(x) 消去量词后的等值式为10. 设个体域 D=1,2,3,4,评卷人11. 将语句“昨
4、天下雨，今天仍然下雨. ”翻译成命题公式，12. 将语句“若不下雨，我们就去参加比赛. ”翻译成命题公式，得 分评卷人四、判断说明题(判断各题正误，并说明理由，每小题7分，本题共14分)13.若图 G 是一个欧拉图，则图G 中存在欧拉路.14. 无向图G 的结点数比边数多1,则G 是树 .101评卷人得 分五、计算题(每小题12分，本题共36分)得 分评卷人15. 设集合A=1,2,3,4 上的关系：R=,S=,试计算(1)R S; (2)R- ; (3)r(RS).16. 图 G=, 其 中 V=a,b,c,d,E=(a,b),(a,c),(a,d),(b,c),(b,d),(c,d), 对
5、应边的权值依次为1、1、5、2、3及4,请画出G 的图形、写出G 的邻接矩阵并求出G 权最小的生成树及其权值.17. 求 -(PVQ)VR 的析取范式与主合取范式.六、证明题(本题共8分)18. 设 A,B,C 均为任意集合，试证明：A(B-C)=(AB)- (AC).102试 卷 代 号 ：1009国家开放大学(中央广播电视大学)2016年春季学期“开放本科”期末考试离 散 数 学 ( 本 ) 试 题 答 案 及 评 分 标 准 ( 半 开 卷 )103(供参考)一、单项选择题(每小题3分，本题共15分)1.C 2.D 3.A 4.D二、填空题(每小题3分，本题共15分)6. 1,2,3,4
6、7. 3,48. 度数相同的结点数相等 9.110.A(1)VA(2)VA(3)VA(4)三、逻辑公式翻译(每小题6分，本题共12分)11.设P: 昨天下雨，Q: 今天下雨.则命题公式为：PAQ.12.设 P: 下雨，Q: 我们去参加比赛.则命题公式为： -PQ. (或-QP)四、判断说明题(每小题7分，本题共14分)13.正确.因为若图G 是一个欧拉图，则图中存在欧拉回路，按定义知，欧拉回路也是欧拉路.14.错误.反例：如图G 的结点数比边数多1,但不是树。2016年7月5.B(2分)(6分) ( 2 分 ) ( 6 分 )(3分) ( 5 分 )(7分) (3分)(或：按定义有；无向图G
7、是树当且仅当无向图G 是连通图且边数比结点数少1.)(7分)说明：举出符合条件的反例均给分。104五、计算题(每小题12分，本题共36分)15. 解：(1)R S=,;(2)R- =,;(3)r(RS)=,16.解：G 的图形表示为：d邻接矩阵：粗线表示的图是最小生成树，权为5:d17.解： -(PVQ)VR分(-PA-Q)VR 析取范式台( -PVR)A(-QVR)(-PVR)V(QA-Q)A(-QVR)台( -PVR)V(QA-Q)A(-QVR)V(PA-P)分( -PVRVQ)A(-PVRV-Q)A(-QVRVP)A(-QVRV-P)台 (PV-QVR)A(-PVQVR)A(-PV-QV
8、R)(4分) (8分)(12分)(3分)(6分)(9分)(12分)主合取范式(5分) (7分) (9分) (10分) (11 分)(12分)六、证明题(本题共8分)18. 证明：设 S=A(B-C),T=(AB)- (AC),若xS, 则xA 且 xB-C, 即 xA, 并且xB 且xC, , (2分)所以x(AB) 且x(AC), 得xT, ( 3 分 )所以 SCT. ( 4 分 )反之，若xT, 则x(AB) 且x(AC), ( 5 分 )即 xA,xB, 且xC, 则得xB-C, ( 6 分 )即得xA(B-C), 即xS, 所以TSS. ( 7 分 )因此 T=S. ( 8 分 )另，可以用恒等式替换的方法证明，105
