国开大学2016年07月1009《离散数学（本）》期末考试参考答案.pdf

1、试卷代号：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=(x,y)I 23:=y，则R=()A.(,B.(,C.(c1,1,c2,2,D.,3无向图G是棵树，边数是10，则G的结点度数之和是（).A.20?B.9 C.10?D.11 4下面的

2、推理正确的是（).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任一整

3、数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)，

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的邻接矩阵并求出

5、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)三、逻辑公式翻译（每

6、小题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

7、(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(AflB）且.r诺(AflC),即xEA,xEB，且I诺C，则得xEB一C,即得xEAfl(B一C)，即xES，所以T二s.因此T一5.另，可以用恒等式替换的方法证明(2分）(3分）(4分）(5分）(6分）(7分）(8分）105