国开大学2019年07月1009《离散数学(本)》期末考试参考答案.docx

1、试卷代号：1009 座位号 国 家 开 放 大 学 2 0 1 9 年 春 季 学 期 期 末 统 一 考 试离散数学(本) 试题(半开卷)2019年7月题号二三四五六总 分分数得 分评卷人一、单项选择题(每小题3分，本题共15分)1. 若集合A=1,2,3, 则下列表述正确的是( ).A. 1,2,3 A B. AC1,2 C.1,2,3SA D. 1.2 A2. 设 A=1,2,3,B=1,2,3,4,A 到 B 的关系R=ix A,v B,xy,则 R=( ).A. ,B. ,C. ,D. ,3. 无向图G 的边数是10,则图G 的结点度数之和为( ).A. 10 B.20C. 30 D

2、. 54. 如图一所示，以下说法正确的是( ).A.e 是割点B. a,e 是点割集C. b,e 是点割集D. d 是点割集 图一13得 分二、填空题(每小题3分，本题共15分)5. 设个体域为整数集，则公式Vx3y(x+y=2) 的解释可为( )。A. 任意整数x, 对任意整数 y 满 足x+y=2B. 对任意整数x, 存在整数y 满 足x+y=2C. 存在一整数x, 对任意整数 y 满足x+y=2D. 存在一整数x, 有整数y 满 足x+y=2评卷人6. 设集合 A=a,b,c,B=b,c,C=c,d, 则 A(BUC) 等于 7. 设 A=1,2,B=2,3,C=3,4, 从 A 到 B

3、 的函数f=, 从 B到 C 的函数 g=, 则 Ran(g 。f) 等于 8. 设 G 是汉密尔顿图，S 是其结点集的一个子集，若S 的元素个数为6,则在G-S 中的连通分支数不超过 .9. 设 G 是有8个结点的连通图，结点的度数之和为24,则可从G 中删去 条边后使之变成树 .10. 设个体域 D=1,2,3,4, 则 谓 词 公 式(Vx)A(x) 消去量词后的等值式为得 分评卷人三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“昨天下雨，今天仍然下雨. ”翻译成命题公式.12. 将语句“我们下午2点或者去礼堂看电影或者去教室看书. ”翻译成命题公式.得 分评卷人四 、判断说

4、明题(判断各题正误，并说明理由.每小题7分，本题共14 分 )13.不存在集合A 与B, 使得A B 与ACB 同时成立.14. 如图二所示的图G 存在一条欧拉回路，V图二14评卷人五、计算题(每小题12分，本题共36分)得 分评卷人得 分15. 设 A=1,2,3,R=|x A,y A 且 x+y=4,S=|x A,y A 且x=y, 试求R,S,R- ,r(S).16. 设图G=,V=vj,v,v,v,E=(v,vz),(v,v;),(v,;), 试(1)画出 G 的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图 G 的补图的图形.17. 求(PVQ)VR 的析取范

5、式与主合取范式，六、证明题(本题共8分)18. 试证明： PVQ=P(PV-Q).15试卷代号：1009国家开放大学2019年春季学期期末统 一 考试离散数学(本) 试题答案及评分标准(半开卷)16(供参考)一、单项选择题(每小题3分，本题共15分)1.C 2.D 3.B 4.A二、填空题(每小题3分，本题共15分)6. b,c7.3,4(或C)8.69.510.A(1)AA(2)AA(3)AA(4)三、逻辑公式翻译(每小题6分，本题共12分)11. 设P: 昨天下雨，Q:今天下雨.则命题公式为：PAQ.12.设P: 我们下午2点去礼堂看电影，Q:我们下午2点去教室看书.则命题公式为： (PQ

6、).注：或者(PAQ)V(PA-Q)四、判断说明题(每小题7分，本题共14分)13.错误.例：设A=a,B=a,a则有AB 且ACB.说明：举出符合条件的反例均给分.14.正确.因为图G 为连通的，且其中每个顶点的度数均为偶数.如果具体指出一条欧拉回路也同样给分，5.B2019年7月(2分) (6分)(2分)(6分)(3分) (5分)(7分)(3分)(7分)v17五、计算题(每小题12分，本题共36分)15. 解：R=,S=,R- =,r(S)=,说明：对于每一个求解项，如果部分正确，可以给对应1分.16. 解：(1)O(2)邻接矩阵(3)deg(v)=2 deg(v)=2 deg(w)=0

7、deg(v)=2(4)补图(3分) (6分) (9分)(12分)(3分)(6分)(9分)(12分)1817.解：(PVQ)VR (PAQ)VR 析取范式(PVR)A( QVR)(5分)(7分) ( PVR)V(QA Q)A(QVR)(PVR)V(QA-Q)A(QVR)V(PAP)分(PVRVQ)A( PVRV Q)A(QVRVP)A(QVRVP) (PV-QVR)A( PVQVR)A(PV-QVR) 主合取范式六、证明题(本题共8分)(9分) (10分) (11分)(12分)18.证明：(1)PVQ(2)P(3)Q(4)PAQ(5)(PVQ)(6)P(PVQ)PP (附加前提)T(1)(2)IT(2)(3)IT(4)ECP 规则(1分) (3分) (5分) (6分) (7分)(8分)说明：(1)因证明过程中，公式引用的次序可以不同， 一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分.(2)可以用真值表验证.采用反证法可参照给分.