试卷代号：1009 座位号■■ 国家开放大学（中央广播电视大学）2016年春季学期“开放本科”期末考试 离散数学（本）试题（半开卷） 2016年7月 题 号 三 四 五 六 总分 分数 得分 评卷人 一、单项选择题（每小题3分，本题共15分） 1.若集合A={1,2,3,4},B={1,3,5},则下列表述正确的是( A.A=B B.BCA C.B≠A D.BCA 2.设A={1,2,3},B={2,4,6},A到B的关系R={x,y)|2x=y},则R=(). A.{,,} B.{,,} C.{,,} D.{,,} 3.无向图G是棵树，边数是10，则G的结点度数之和是(). A.20 B.9 C.10 D.11 4.下面的推理正确的是(). A.(1)(Hx)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)(Hx)(F(x)→G(x) 前提引人 (2)F(y)-*G(y) US(1). 100
试卷代号 :1009 座位号 国家开放大学(中央广播电视大学)2016 年春季学期"开放本科"期末考试 离散数学(本) 试题(半开卷) 2016 E 一、单项选择题(每小题 分，本题共 15 分} 1.若集合 = {1, 2 , 3, 4} ,B = {1, 3 5} ，则下列表述正确的是( ). A.A=B B. BcA c. D. BCA 2. A={ 1， 3} B={2 的关系 = { , ,} B. {,,} c. {, ,} D. { , ,} 3. 元向图 是棵树，边数是 10 ，则JG 的结点度数之和是( ). A. 20 B. 9 C. 10 D. 11 4. 下面的推理正确的是( ). A. (1) ( 'v' x) 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)( 'v' x)(F(x)• G(x)) 前提引人 (2)F(y)• G(y) US(1). 100
5.设个体域为整数集，则公式Hx3y(x十y=2)的解释可为(). A,任一整数x,对任意整数y满足x十y=2 B.对任一整数x,存在整数y满足x十y=2 C.存在一整数x,对任意整数y满足x十y=2 D.存在一整数x,有整数y满足x十y=2 得分 评卷人 二、填空题（每小题3分，本题共15分） 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(gf)等于 8.两个图同构的必要条件包括结点数相等、边数相等与 9.设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，v值为5，e值为4则r 的值为 10.设个体域D=(1,2,3,4},则谓词公式(3x)A(x)消去量词后的等值式为 得分 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“昨天下雨，今天仍然下雨.”翻译成命题公式· 12.将语句“若不下雨，我们就去参加比赛.”翻译成命题公式· 得分 评卷人 四、判断说明题（判断各题正误，并说明理由.每小题7分，本题共14 分) 13.若图G是一个欧拉图，则图G中存在欧拉路. 14.无向图G的结点数比边数多1，则G是树. 101
5. 设个体域为整数集，则公式 x 3 y(x+y=2) 的解释可为( ). A. 任一整数 对任意整数 满足 x+y=2 B. 对任一整数 存在整数 满足 x+y=2 c. 存在一整数 对任意整数 满足 x+y=2 D.存在一整数 有整数 满足 x+y=2 |得分|评卷人| | 二、填空题{每小题 分，本题共 15 分) 6. 设集合 = {l , 2 , 3} ,B = {2 ，的， c= {3 ,4 5} ，则 B U (A - C) 等于 7. A= {l， 2} B={2 3} C={3 4} ，从 的函数 f={ } 的函数 g= { } ，则 Ran(go j)等于 8. 两个图同构的必要条件包括结点数相等、边数相等与 9. 是连通平面图 分别表示 的结点数，边数和面数 值为 值为 的值为 10. 设个体域 D= {l， 4} ，则谓词公式 (3x)A(x) 消去量词后的等值式为 |得分|评卷人| | 三、逻辑公式翻译{每小题 分，本题共 12 分} 1.将语句"昨天下雨，今天仍然下雨"翻译成命题公式. 12. 将语句"若不下雨，我们就去参加比赛"翻译成命题公式. |得分|评卷人| | 四、判断说明题(判断各题正误，并说明理由.每小题 分，本题共 14 分} 13. 若图 是一个欧拉图，则图 中存在欧拉路. 14. 元向图 的结点数比边数多1，贝UG 是树. 101
得分 评卷人 五、计算题（每小题12分，本题共36分） 15.设集合A={1,2,3,4}上的关系： R={,,},S={,,}, 试计算(1)R·S; (2)R-1; (3)r(R∩S). 16.图G=,其中V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c),(b, d),(c,d)},对应边的权值依次为1、1、5、2、3及4，请画出G的图形、写出G的邻接矩阵并求 出G权最小的生成树及其权值， 17.求(PVQ)VR的析取范式与主合取范式. 得 分 评卷人 六、证明题（本题共8分） 18.设A,B,C均为任意集合，试证明：A∩(B-C)=(A∩B)-(A∩C) 102
五、计算题{每小题 12 分，本题共 36 分} 15. 设集合 A={1 4} 上的关系: R={ , ,} ,S={, ,} , 试计算 (l )R • S; (2)R- J ; (3)r (R n S). 16. G= 其中 V={ d} E= {(a 的， (a 仆， (α d) ， (b , c) , (b , d) (c d)} 对应边的权值依次为 ，请画出 的图形、写出 的邻接矩阵并求 权最小的生成树及其权值. 17. 求-， (P V Q) V 的析取范式与主合取范式. |得分|评卷人| | 六、证明题{本题共 分} 18. 均为任意集合，试证明 :A (B-C)=(AnB) (A C). 102
试卷代号：1009 国家开放大学中央广播电视大学)2016年春季学期“开放本科”期末考试 离散数学（本）试题答案及评分标准（毕开卷） (供参考) 2016年7月 一、单项选择题{每小题3分，本题共15分 1.C 2.D 3.A 4.D 5.B 二、填空题（每小题3分，本题共15分）】 6.{1,2,3,4} 7.{3,4} 8.度数相同的结点数相等 9.1 10.A(1)VA(2)VA(3)VA(4) 三、逻辑公式翻译（每小题6分，本题共12分 11.设P:昨天下雨，Q:今天下雨 (2分) 则命题公式为：P八Q. (6分) 12.设P:下雨，Q:我们去参加比赛. (2分) 则命题公式为：一P+Q.(或Q→P) (6分) 四、判断说明题（每小题7分，本题共14分） 13.正确. (3分) 因为若图G是一个欧拉图，则图中存在欧拉回路· (5分) 按定义知，欧泣回路也是欧拉路· (7分) 14.错误. (3分) 反例：如图G的结点数比边数多1，但不是树， (或：按定义有：无向图G是树当E仅当无向图G是连通图且边数比结点数少1.)(7分) 说明：举出符合条件的反例均给分， 103
试卷代号 :1009 国家开放大学{中央广播电视大学 )2016 年春季学期"开放本科"期末考试 离散数学(本) 试题答案及评分标准(半开卷〉 (供参考〉 -、单项选择题{每小题 分，本题共 15 1. C 2.D .A 二、填空题{每小题 分，本题共 15 分} 6. {1 .2 ,3,4} 7. {3 ,4} 8. 度数相同的结点数相等 9. 1 10. A (1) VA(2) VA(3) VA(4) 三、逻辑公式翻译{每小题 分，本题共 12 1.设 p: 昨天下雨 Q: 今天下雨， 则命题公式为 :P Q. 12. p: 下雨 Q: 我们去参加比赛. 则命题公式为 :.p Q. (或 -:Q P) 四、判断说明题{每小题 分，本题共 14 分} 13. 正确. 4.D 臣为若图 是一个欧拉医，则图中存在欧捡回路. 按定义知，欧拉回路也是欧拉路. 14. 错误. 反倒 如图 j<J结点数比边数多 ，但不是树. 5. B 2016 (2 分〉 (6 分〉 (2 分〉 (6 分〉 (3 分〉 (5 分) (7 分〉 (3 分) 〈或 按定义有 元向图 是树当旦仅当元向图 是连通图且边数比结点数少1.) (7 分) 说明 举出符合条件的反倒均给分. 103
五、计算题（每小题12分，本题共36分） 15.解：(1)R·S=={,}； (4分) (2)R-1={,,}: (8分) (3)r(R∩S)={,,,} (12分) 16.解：G的图形表示为： 3 (3分) 邻接矩阵： 01117 1011 (6分) 1101 1110 粗线表示的图是最小生成树，权为5： (9分) (12分) 17.解：(PVQ)VR 台(P∧Q)VR 析取范式 (5分) 台(PVR)∧(QVR) (7分) 台(PVR)V(QAQ)(QVR) (9分) ((-PVR)V(QA-Q))A((-QVR)V(PA-P)) (10分) (-PVRVQ)A(-PVRV-Q)A(-QVRVP)A(-QVRV-P) (11分) 台(PV-QVR)∧(PVQVR)(PV-QVR) 主合取范式 (12分) 104
五、计算题{每小题 12 分，本题共 36 分} 15. :(1 )R. S=={ ,}; (2)R ={, ,}; (3)r(R nS)= {, , ,} 16. :G 的图形表示为 邻接矩阵 b 1 1 1 101 1 1 101 1 1 1 0 b 粗线表示的图是最小生成树，权为 5. 17. 解: -, (P V Q) V R 件(-， P ^ -, Q) V R 件(-， P V R) ^ (-, Q V R) b 析取范式 件((-， PVR)V(Q^ -, Q))^( -, QVR) d d 丰功((-， PVR)V(Q^ -'Q)) 八( ( -, Q V R) V (P ^ -, P) ) 件(-， P V R V Q) 八(-， P V R V -, Q) ^ (-, Q V R V P) 八(-， QVRV -'P) (PV -'QVR)^( -, PVQVR)^( -, PV -, QVR) 主合取范式 104 (4 分〉 (8 分〉 (1 分〉 (3 分) (6 分〉 (9 分〉 (1 分〉 (5 分〉 (7 分〉 (9 分〉 (1 分〉 (1 分〉 (1 分〉
六、证明题（本题共8分） 18.证明： 设S=A∩(B-C),T=(A∩B)-(A∩C), 若x∈S,则x∈A且x∈B一C,即x∈A,并且x∈B且xC, (2分) 所以x∈(A∩B)且x任(A∩C),得x∈T, (3分) 所以S二T. (4分) 反之，若x∈T,则x∈(A∩B)且x(A∩C), (5分) 即x∈A,x∈B,且x任C,则得x∈B一C, (6分) 即得x∈A∩(B一C),即x∈S,所以T二S. (7分) 因此T=S. (8分) 另，可以用恒等式替换的方法证明. 105
六、证明题{本题共 分} 18. 证明 S=A n (B-C) , T=(A nB) (A C) , εS ，则 εA B-C 并且 εB f/: 所以 (AnB) f/: (A n C) εT ， 所以 SCT. 反之，若 εT ，则 (AnB) f/: (A n C) , xEB ，则得 B-C ， 即得 εA (B-C) εS ，所以 TCS. 因此 T=S. 另，可以用恒等式替换的方法证明. (2 分) (3 分) (4 分) (5 分〉 (6 分) (7 分) (8 分〉 105