试卷代号:1009
国家开放大学（中央广播电视大学）2016年春季学期“开放本科”期末考试
离散数学（本）试题（半开卷）
2016年7月
题号 一 二 三 四 五 ^1- 总分
分数
得分评卷人
一、单项选择题（每小题3分,本题共15分）
1.若集合A = {1,2,3,4},B = {1,3,5},则下列表述正确的是( ).
A.A = B B. B U A
C. B^A D. BOA
2.设 A = {1,2,3},B = {2,4,6},A 到 8 的关系 R = {(x \ 2x =_y},则 R =( ).
A.{<1,3>,<2,4>,<3,5>}
B.(<2,1>,<4,3>,<6,5>}
C.{<1,1>,<2,2>,<3,3>)
D.{<1,2>,<2,4>,<3,6>)
3.无向图G是棵树，边数是10,则G的结点度数之和是（）・
A.20B. 9
C.10D. 11
4.下面的推理正确的是（）.
A.(1)(Vz)FG1GG)前提引入
(2)F(y)fG3)US(1).
B.(l)Ox)F(x)^GU)前提引入
(2)F(j0fG(y)US(1).
C,⑴(D(FG)fG&))前提引入
(2)F(j/)-*G(x)ES(1).
D.⑴(Vz)(FG)fGG))前提引入
(2)F(y)fG3)US(1).
5.设个体域为整数集,则公式V^3j-（x+> = 2）的解释可为（ ）.
A.任一整数z,对任意整数丿满足x+> = 2
B.对任一整数z,存在整数了满足x+> = 2
C.存在一整数z,对任意整数了满足x + y = 2
D.存在一整数工，有整数）满足z+】=2
得分评卷人
二、填空题（每小题3分,本题共15分）
6.设集合 A = {1,2,3},B = {2,3,4},C={3,4,5},则 B U (A – C)等于 .
7.设 A = {1,2},B = {2,3},C={3,4},从 A 到 B 的函数/= {<1,2>,<2,3>},从 B 到 C 的函数 g = {V2,3>,<3,4>},则 Ran(g。”等于 .
8.两个图同构的必要条件包括结点数相等、边数相等与
9.设G是连通平面图,p,e,r分别表示G的结点数,边数和面数,，值为5,e值为4则r 的值为 .
10.设个体域D = {1,2,3,4},则谓词公式（3x）A（x）消去量词后的等值式为
得 21.评卷入 三、逻辑公式翻译（每小题6分,本题共12分）
11.将语句“昨天下雨,今天仍然下雨翻译成命题公式.
12.将语句“若不下雨，我们就去参加比赛.”翻译成命题公式.
得 分 评卷人
四、判断说明题（判断各题正误，并说明理由.每小题7分，本题共14
分）
13.若图G是一个欧拉图，则图G中存在欧拉路.
14.无向图G的结点数比边数多1,则G是树.
碍 分 评卷入 五、计算题(每小题12分,本题共36分)
15.设集合A = {1,2,3,4)上的关系：
R = {V1,2>,V2,3>,V3,4>},S = {V1,1>,V2,2>,V3,3>},
试计算(1)R・S； (2)RT； (3)r(I?nS).
16.图 G = <V,E>，其中 V = {a , b, c, d \, E =《a , b) , (a , c) ,〈a , d) , (b, c) , (b, d),(cM)},对应边的权值依次为1、1、5、2、3及4,请画出G的图形、写出G的邻接矩阵并求 出G权最小的生成树及其权值.
17.求r(PVQ)VR的析取范式与主合取范式.
得分|评卷人
六、证明题(本题共8分)
18.设 A,B,C 均为任意集合，试证明:ACl(B-C) = (AnB)-(AnC).
试卷代号:1009
国家开放大学［中央广播电视大学）2016年春季学期“开放本科”期末考试
离散数学（本）试题答案及评分标准（半开卷）
（供参考）
2016年7月
一、 单项选择题（每小题3分,本题共15分；
I.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分）
II.没P*昨天下雨,Q*今天下雨. （2分）
则命题公式为:PAQ. （6分）
苴.设P：下雨,Q：我们去参加比赛. （2分）
则命题公式为：rPfQ.（或rQfF） （6分）
四、 判断说明题（每小题7分,本题共14分）
13.正确. （3分）
因为若图G是一个欧拉图，则图中存在欧拉回路. （5分）
按定义知，欧拉回路也是欧拉路. （7分）
14.错误. （3分）
反例:如图G的结点数比边数多1,但不是树•
（或:按定义有:无向图G是树当巨仅当无向图G是连通图且边数比结点数少1.） （7分） 说明:举出符合条件的反例灼给分•
五、计算题(毎小题12分，本题共36分)
15.解：(1)R • S = = {<1,2>,<2,3>)；
(2)RT = {V2,1>,V3,2>,V4,3>}；
(3)r(7?nS) = {<l,l>,<2,2>,<3,3>,<4,4>)
16.解:G的图形表示为：
17,解:r(PVQ)VR
0(rF/\rQ)VR 析取范式
冃 OP VR)A(rQVR)
0((rpVR)V(QA rQ))/\(rQVR)
0((rF VR)V(Q/\ rQ))/\((rQVR)V(FA – P ))
0(rPVRVQ)/\(rFVRV rQ)/\(rQVR VP)/\(rQVR V “) ⑴分)
<=>(PV rQVR)人(rF VQVR)/\(rPV rQVR) 主合取范式 (12 分) 六、证明题（本题共8分）
18.证明：
设 S =An（B-c）,r =（AnB）-（Anc）,
若z£S,则xG A且z£B — C，即xGA，并且且工WC, （2分）
所以 xGCADB）且 zWCADC）,得工 £T, （3 分）
所以SUT. （4分）
反之，若xer,则工ecACiB）且工任（acic）, （5分）
即 x G A ,x GB ,且:cWC,则得 xEB~C, （6 分）
即得 ^eAn（B-C）,即 所以 TQS. （7 分）
因此T = S. （8分）
另，可以用恒等式替换的方法证明.
点点赞赏，手留余香
给TA打赏
评论0