离散数学(本)试题(半开卷).pdf

试卷代号：1009 座位号口口 国家开放大学（中央广播电视大学）2016年春季学期“开放本科”期末考试 离散数学（本）试题（半开卷） 2016年7月 题号 四 五 六 总分 分数 得分 评卷人l 一、单项选择题【每小题3分本题共15分） 1若集合A一(1,2 ,3 , 4) ,B= (1,3 , 5)，则下列表述正确的是（). A. A=B ?B. BCA C. B并A ?D.B二A 2设A=1,2,3),B=(2,4,6,A到B的关系R = (,c2,2, D., 3无向图G是棵树，边数是10，则G的结点度数之和是（). A.20 ?B.9 C. 10 ?D. 11 4下面的推理正确的是（). A.(1)(V二）F (x ) -G (x）前提引人 (2)F(y)-G(y) ?US(1). B.(1)(日x ) F (x ) -G (x）前提引人 (2)F(y)-.G(y) ?USU). C.(1)(日x)(F（二）G(x)）前提引人 (2)F(y)-G(x) ?ES(1). D.(1)(Vx)(F(x)-.G(x)）前提引人 (2)F(y)-G(y) ?US(1). 100 11 .l2 1314. 四、判断说明题（判断各题正误并说明理由每小题7分，本题共14 分） 若图C是一个欧拉图，则图G中存在欧拉路 无向图C的结点数比边数多1，则G是树 5设个体域为整数集，则公式Vx Ry(x+y一2)的解释可为（) A任一整数x，对任意整数y满足x +y = 2 B对任一整数x，存在整数y满足x+y二2 C存在一整数I，对任意整数y满足x+y=2 D存在一整数I，有整数y满足-I十y=2 二、坟空题（每小题3分，本题共巧分） 得分 l 评卷人 设集合A=1,2,3,B=2,3,4),C=3,4,5)，则BU(A一C）等于 设A= 1, 2) ,B= (2, 3) , C= (3, 4)，从A到B的函数1= (, )，从B 到C的函数g= , )，则Ran(g of）等于 8两个图同构的必要条件包括结点数相等、边数相等与 9设G是连通平面图，V ,e , r分别表示C的结点数，边数和面数，V值为5,e值为4则r 的值为 10设个体域D=1,2,3,4)，则谓词公式（Jx)A(x）消去量词后的等值式为 三、逻辑公式翻译【每小题6分，本题共12分） 得分 评卷人 .得分评卷人 将语句“昨天下雨，今天仍然下雨”翻译成命题公式 将语句“若不下雨，我们就去参加比赛”翻译成命题公式 101 得分 评卷人 得分 评卷人 五、计算题（每小题12分，本题共36分） 15设集合A=(1,2,3,4上的关系： R丈,hS=, 试计算(1)RS,(2)R一，;(3)r(R门S). 16.图G=，其中V=(a, b,c,d,E一 (a , b), (a ,c), (a, ci), (b, c), (b, d),(c,d)，对应边的权值依次为1、1,5、2.3及4,请画出G的图形、写出G的邻接矩阵并求 出C权最小的生成树及其权值 17求，(PVQ)VR的析取范式与主合取范式 六、证明题【本题共8分） 18，设A.13,C均为任意集合，试证明：Afl(B一C)=(AflB）一（A flC). 102 试卷代号：1009 国家开放大学i中央广播电视大学）2016年春季学期“开放本科”期末考试 离散数学（本）试题答案及评分标准（半开卷） （供参考） 2016年7月 一、单项选择题每小题3分，本题共15分） LC ?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) 三、逻辑公式翻译（每小题0分，本题共12分） n设尸：昨天下雨，Q：今天下雨 则命题公式为：FAQ. 12设尸：下雨，Q：我们去参加比赛 则命题公式为：，尸Q.（或，Q尸） 四、判断说明题【每小题7分本题共14分） 13正确 因为若图G是一个欧拉图，则图中存在欧拉回路 按定义知，欧拉回路也是欧拉路 14.错误 反例：如图G的结点数比边数多1，但不是树 只O (2分） (6分） (2分） (6分） (3分） (5分） (7分） (3分） （或：按定义有：无向图G是树当且仅当无向图G是连通图且边数比结点数少1.) (7分） 说明：举出符合条件的反例均给分 103 五、计算题每小题12分，本题共36分） 15解：(DRS=(,; (2)R一= ,; (3)r(RnS)= ,cz2,2, 16解：G的图形表示为： (4分） (8分） (12分） (3分） 邻接矩阵： ，工 11 CU 11 11 C 11 11 仍 f卜卜门厂 卜口 (6分） 粗线表示的图是最小生成树，权为5: (9分） (12分） 17解：,(P VQ)VR =(-PA Q)VR析取范式 片（-PVR)A(,QVR) =(-iPVR)V(QA Q)A(,QVR) 4=(-PVR)V(QA Q)A(QVR)V(PA -F) 骨（,P VR V Q) A(-PVRV -Q)A(-QVR VP) A(-QVRV -iP) 4=(PV -QVR)A(P VQVR) A(-PV -QVR) 104 主合取范式 (5分） (7分） (9分） (10分） (11分） (12分） 六、证明题（本题共8分） 18证明： 设S=A门(B一C),T=(A门B）一（A自C), 若Es，则xEA且xEB一C,即zEA，并且x任B且I诺C, 所以x E (A门B）且.1任(A门C)，得zET, 所以5CT. 反之，若xET，则xE(Af