试卷代号：1009 座位号■ 国家开放大学（中央广播电视大学）2015年秋季学期“开放本科”期末考试 离散数学（本）试题（半开卷） 2016年1月 题 号 二 四 五 六 总 分 分 数 得分 评卷人 一、单项选择题（每小题3分，本题共15分） 1.若集合A={1,2,3,4),则下列表述正确的是(). A.{1,2}∈A B.{1,2,3}二A C.{1,2,3}A D.{1,2,3}∈A 2.已知无向图G的结点度数之和为10，则G的边数为(). A.10 B.20 C.30 D.5 3.无向图G是棵树，结点数为10，则G的边数是(). A.5 B.10 C.9 D.12 4.设A(x):x是人，B(x):x是学生，则命题“有的人是学生”可符号化为( A.(Hx)(A(x)∧B(x)) B.(Vx)(A(z)--B(x)) C.(3x)(A(z)AB(x)) D.(3x)(A(x)A-B(x)) 5.下面的推理正确的是(). A.(1)(3x)(F(x)G(x)) 前提引人 (2)F(y)+G(y) ES(1). B.(1)(Hx)F(x)→G(x) 前提引入 (2)F(y)+G(y) US(1). C.(1)(3x)F(x)+G(x) 前提引入 (2)F(y)+G(y) US(1). D.(1)(3x)(F(x)→G(x)) 前提引人 (2)F(y)→G(x) ES(1). 94
试卷代号 :1009 座位号 94 国家开放大学(中央广播电视大学 )2015 年秋季学期"开放本科"期末考试 离散数学(本) 试题(半开卷} 2016 时斗二十三|四十二斗叫 一、单项选择题(每小题 分，本题共 15 分} 1.若集合 A= {l， 4} ，则下列表述正确的是( ). A. {1， 2}ε A B. {1 3} C. {1 3} D. {1 , 2 ,3}EA 2. 已知元向图 的结点度数之和为 10 ，则 的边数为( ). A. 10 B. 20 C. 30 D. 5 3. 元向图 是棵树，结点数为 10 ，则 的边数是). A. 5 B. 10 C. 9 D. 12 4. A(x) :x 是人，职工) :x 是学生，则命题"有的人是学生"可符号化为( ). A. (V x)(A(x) R(x) ) c. (3 x)(A(x) ^ B(x)) 5. 下面的推理正确的是). A. (1) ( 3 x)(F(x)• G(x)) (2)F(y)• G(y) B. (]) ( V x)F(x)• G(x) (2) F(y)• G(y) C. (I )(3x)F(x)• G(x) (2)F(y)• G(y) D. (1)(丑 x)(F(x) G(x)) (2)F(y)• G(x) B. -, ( V x) (A(x)• B(x)) D. -, ( 3 x) (A(x) ^ -, B(x)) 前提引入 ES(l). 前提引入 US(l). 前提引人 US(l). 前提引人 ES(l)
得 分 评卷人 二、填空题（每小题3分，本题共15分） 6.设A={1,2},B={a,b,c},则A×B的元素个数为 7.有n个结点的无向完全图的边数为 8.设无向图G中存在欧拉路，则G的奇数度数的结点数为 9.设G是有10个结点的连通图，边数为20，则可从G中删去 条边后使之变成 树. 10.设个体域D=1,2,3,4},则谓词公式(Hx)A(x)消去量词后的等值式为 得 灭 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“小明是个学生.”翻译成命题公式. 12.将语句“他上午去教室上课，下午去体育馆参加比赛，”翻译成命题公式· 得 分 评卷人 四、判断说明题（判断各题正误，并说明理由·每小题7分，本题共 14分) 13.存在集合A与B,可以使得A∈B与A二B同时成立. 14:完全图K。不是平面图. 得 分 评卷人 五、计算题（每小题12分，本题共36分）】 15.设关系R的关系图如下，试 d b (1)写出R的关系表达式； (2)判断R是否为等价关系，并说明理由· 95
二、填空题{每小题 分，本题共 15 分} 6. A= {1 , 2} ,B= {a ，c}， AXB 的元素个数为 7. 个结点的无向完全图的边数为 8. 设元向图 中存在欧拉路，则 的奇数度数的结点数为 9. 是有 10 个结点的连通图，边数为 20. 9! 可从 中删去 树. 条边后使之变成 10. 设个体域 D={ 1， ，川，则谓词公式 (V x)A(x)~肖去量词后的等值式为 三、逻辑公式翻译{每小题 分，本题共 12 分) 1.将语句"小明是个学生"翻译成命题公式. 12. 将语句"他上午去教室上课，下午去体育馆参加比赛"翻译成命题公式. 四、判断说明题(判断各题正误，并说明理由.每小题 分，本题共 14 分} 13. 存在集合 ，可以使得 AEB ACB 雨时成立. 14. 完全图凡不是平面图. |主主 五、计算题(每小题 12 分，本题共 36 分) 15. 设关系 的关系图如下，试 d b C (1)写出 的关系表达式; (2) 判断 是否为等价关系，并说明理由. 95
16.设图G=,V={1,2,3,Ua》,E={(1,2),(u),(2,4)},试 (1)画出G的图形表示： (2)写出其邻接矩阵； (3)求出每个结点的度数： (4)画出图G的补图的图形. 17.求PV(QAR)的合取范式与主合取范式. 得分 评卷人 六、证明题（本题共8分】 18.对任意集合A,B和C,试证明A×(BUC)=(A×B)U(AXC). 96
16. 设图 G= V={ 叫，屿，叫，叫} , E = { (Vj , V2 ) , ( Vj • V , ) , (V2 叫)} ，试 (1)画出 的图形表示; (2) 写出其邻接矩阵; (3) 求出每个结点的度数 (4) 画出图 的补图的图形. 17. 求-， PV (Q 八灿的合取范式与主合取范式. 户半空| 六、证明题(本题共 分} 18. 对任意集合 A.B C. 试证明 X (BUC) =(AXB) U CAXC). 96
试卷代号：1009 国家开放大学（中央广播电视大学）2015年秋季学期“开放本科”期末考试 离散数学（本）试题答案及评分标准（半开卷） (供参考) 2016年1月 一、单项选择题（每小题3分，本题共15分） 1.B 2.D 3.C 4.C 5.A 二、填空题（每小题3分，本题共15分） 6.6 7.n(n-1)/2 8.两个或零个（注：答“两个”也给3分） 9.11 10.A(1)∧A(2)∧A(3)∧A(4) 三、逻辑公式翻译（每小题6分，本题共12分） 11.设P:小明是个学生· (2分) 则命题公式为：P. (6分) 12.设P:他上午去教室上课， Q:他下午去体育馆参加比赛. (2分) 则命题公式为：P∧Q (6分) 四、判断说明题（每小题7分，本题共14分】 13.正确. (3分) 例：设A={a},B={a,{a}} (5分) 则有A∈B且A二B. (7分) 说明：举出符合条件的实例均给分， 14.错误. (3分) 完全图K,是平面图， (5分) 如K可以如下图示嵌入平面， (7分) 97
试卷代号 :1009 国家开放大学(中央广播电视大学 )2015 年秋季学期"开放本科"期末考试 离散数学(本) 试题答案及评分标准(半开卷) (供参考) 一、单项选择题(每小题 分，本题共 15 分} 1. B 2. D 3. C 二、填空题{每小题 分，本题共 15 分} 7. n(n 一1) /2 8. 两个或零个(注 答"两个"也给 分) 10. (l)八 A(2) A(3) A(4) 三、逻辑公式翻译{每小题 分，本题共 12 分} 1.设 p. 小明是个学生. 则命题公式为 :P. 12. p. 他上午去教室上课， Q: 他下午去体育馆参加比赛. 则命题公式为 :P^Q 四、判断说明题{每小题 分，本题共 14 分) 13. 正确. 例:设 A={ α} B= 怡， {a} } 则有 AEB ACB. 说明:举出符合条件的实例均给分. 14. 错误. 完全图 K4 是平面图， 如几可以如下图示嵌入平面. 4. C 5. A 2016 (2 分) (6 分) (2 分) (6 分) (3 分) (5 分) (7 分) (3 分) (5 分) (7 分) 97
五、计算题（每小题12分，本题共36分） 15.解：(1)R={,,,,,}. (4分) (2)不是等价关系 (8分) 因为该关系不满足自反性（或答：不满足传递性） (12分) 16.解：(1)关系图 V2 O (3分) (2)邻接矩阵 01017 1001 (6分) 0000 1100 (3)deg(v,)=2 deg(v2)=2 deg(v3)=0 deg(v)=2 (9分) (4)补图 VI O (12分) 17.解：PV(QAR)H(PVQ)A(PVR) 合取范式 (2分) 台(PVQ)V(R∧R)A(PVR) (5分) (PVQ)V(R∧R)∧(PVR)V(Q∧Q) (7分) (-PVQVR)A(-PVQV-R)A(-PVRVQ)A(-PVRV-Q) (10分) (-PVQVR)A(-PVQV-R)A(-PV-QVR) 主合取范式 (12分) 98
五、计算题{每小题 12 分，本题共 36 分} 98 15. 解: (1 )R= { , ... }. (2) 不是等价关系 因为该关系不满足自反性(或答:不满足传递性〉 16. 解: (1)关系图 Vl o V3 (2) 邻接矩阵 O 1 0 11OO1 1 o 0 O o 0 1 1 0 (3)deg( Vl) = 2 deg(V2) =2 deg(V3) =0 deg(V4) =2 (4) 补图 Vl 17. 解:-， PV(Q R) 仲( -, P V Q) ^ ( -, P V R) 仲(( -, P V Q) V (R 八-， R)) 八( -, P V R) V4 丰功(( -, P V Q) V (R -, R)) 八((-， PVR)V(Q -, Q)) V3 合取范式 (-'PVQVR) (-'PVQV -， R) 八(-， PV RV Q) 八( -, P V R V -, Q) (-'PVQVR) (-'PVQV -, R)^( -, PV -, QVR) 主合取范式 (4 分) (8 分) (1 分) (3 分) (6 分〉 (9 分) (1 分) (2 分) (5 分) (7 分〉 (1 分) (1 分)
六、证明题（本题共8分） 18.证明：设S=A×(BUC),T=(A×B)U(A×C), 若∈S,则有x∈A且y∈(BUC),即x∈A且y∈B或y∈C, (1分) 即有x∈A且y∈B,或x∈A且y∈C, (2分) 可得∈(AXB),或∈(AXC), (3分) 则有∈(AXB)U(AXC),即∈T, (4分) 所以S二T. (5分) 反之，若∈T,则有∈(AXB),或∈(AXC), 则有x∈A且y∈B,或x∈A且y∈C,即有x∈A且y∈B或y∈C, (6分) 则有x∈A且y∈(BUC),即有∈S, 所以T三S (7分) 得证AX(BUC)=(AXB)U(AXC) (8分) 99
六、证明题{本题共 分} 18. 证明:设 S=AX (BU C), T=(AXB) UES 则有 xEA (BUC) ，即 zεA yEB εC ， (1分) 即有 zεA 或工仨 εC ， (2 分) 可得 ε(AX 盼，或〈工， y>E(AXC) (3 分) 则有 E (AX B) U (AXC) ，即 (4 分〉 所以 SCT. (5 分) 反之，若 则有 (AXB) E(AXC) , 则有 zεA zεA yEC ，即有 zεA yEB εC ， (6 分) 则有 zεA ε(BUC) ， I! εS 所以 TCS. (7 分) 得证 AX (BUC)=(AXB) U (AXC). (8 分〉 99