试卷代号：1009 座位号E
中央广播电视大学2011-2012学年度第一学期“开放本科”期末考试（半开卷）
离散数学（本）试题
2012年1月
题号 一 二 三 四 五 总分
分数
得分评卷人
、单项选择题（每小题3分,本题共15分）
1.若集合A的元素个数为10,则其慕集的元素个数为（ ）.
A. 10 B. 100
C. 1024 D. 1
2.设 A={a,b},B={1,2},Ri,R2,R3 是厶到 B 的二元关系，且 R = {Va,2>, Va, 1>},
R = { Va,l>, Va,2>,V3,l>} ,R3 = {<a,1>,<b,2>}，则（ ）是从 A 到 B 的函数.
A. R和尾 B.尾
C. R3 D. R 和 R3
3.设A= {1,2,3,4,5,6,7,8},R是A上的整除关系，B= {2,4,6},则集合B的最大元、
最小元、上界、下界依次为（ ）.
A. 8、2、8、2 B.无、2、无、2
C.6、2、6、2 D.8、l、6、l
4.若完全图G中有”个结点（”》2）,m条边，则当（ ）时，图G中存在欧拉回路.
A.”为奇数 B.”为偶数
C. m为奇数 D. m为偶数
5.已知图G的邻接矩阵为
则。有（ ）.
A.6点，8边
C. 5点，8边 得分评巻人
二、填空题（毎小题3分，本题共15分）
6.设集合A={a）,那么集合A的藉集是 .
7.若R和死是A上的对称关系，则RiURz’RmRz’R—死，&一R中对称关系有 个.
8.设图G是有5个结点的连通图，结点度数总和为10,则可从G中删去 条边后 使之变成树.
9.设连通平面图G的结点数为5,边数为6,则面数为 .
10.设个体域D^{a,b},则谓词公式（V工）（A （工）AB（x））消去量词后的等值式为
11.将语句“今天有联欢活动，明天有文艺晚会翻译成命题公式.
12.将语句“如果小王来，则小李去.”翻译成命题公式.
判断下列各题正误，并说明理由.
13.若偏序集<A,R >的哈斯图如图一所示，则集合A的最大元为a,极小元不存在.
图一
14.r p人(P- r Q) V P为永假式.
得分评卷人 五、计算题(毎小题12分，本题共36分)
15.设集合 A={1,2,3,4} ,R={〈H,y> |工,\x~y\ = 1 或工一y = 0}，试
(1)写出R的有序对表示；
(2)画出R的关系图；
(3)说明R满足自反性，不满足传递性.
16.设图 G=<V,E>,V= 31 ，03 ,04 ,05 }，E = {(S ,此)，(S ,03),(女，04)，(03,05)，
(t?4 >^S ) )，试
(1)画出G的图形表示；
(2)写出其邻接矩阵；
(3)求出每个结点的度数；
(4)画出图G的补图的图形.
17.求P->QAR的合取范式与主析取范式.
得分评卷人
六、证明题(本题共8分)
18.设连通无向图G有14条边,3个4度顶点，4个3度顶点，其它顶点的度数均小于3, 试说明G中可能有的顶点数.
试卷代号:1009
中央广播电视大学2011-2012学年度第一学期“开放本科”期末考试（半开卷）
离散数学（本）试题答案及评分标准
（供参考）
2012年1月
一、 单项选择题（毎小题3分,本题共15分）
I.C 2. C 3. B 4. A 5. D
二、 填空题（毎小题3分，本题共15分）
6.{0,{a}}
7.4
8.1
9.3
10.（A（a） AB（W） A（A（a） AB（6））
三、 逻辑公式翻译（毎小题6分,本题共12分）
II. 设P：今天有联欢活动,Q：明天有文艺晚会， （2分）
PAQ. （6 分）
12.设P：小王来,Q：小李去 （2分）
P-Q. （6 分）
四、 判断说明题（毎小题7分,本题共14分）
13.错误. （3分）
对于集合A的任意元素工，均有Vx,a>£R（或工Ra）,所以a是集合A中的最大元.（5分） 但按照极小元的定义，在集合A中b,c,d均是极小元. （7分）
14.错误. （3分）
rP/\（Pf rQ）V P是由rp/\（Pf rQ）与P组成的析取式，
如果P的值为真，则rP/\（P—rQ）V P为真, （5分）
如果P的值为假，则rP与P – rQ为真，即rp/\（Pf rQ）为真，
也即 rP/\（Pf rQ）VP 为真，
所以rP/\（Pf rQ）VP是永真式.
0 1 1 0 o-
1 0 0 1 0
1 0 0 0 1
0 1 0 0 1
0 0 1 1 0_
(3)deg(p】)= 2
deg(^2)— 2
deg(s)= 2
deg(P4)= 2
deg(刃 5)=2
（4）补图如图四
17. F-(RAQ)
AFVCRAQ)
(-■FAQA2?) V((-FVF) A (2?AQ))
0（rP/\-iQ/\-,R）V（rp/\rQ/\R）V（rP/\Q/\rR）V （-FAQA2?）V（FA2?AQ） （主析取范式） （12 分）
说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分.
六、证明题（本题共8分）
18.证明：可利用数列可图化及握手定理解答
顶点度数和为2X14 = 28, （2分）
28—（3X4+4X3）=4,则知其他顶点度数和为4, （4分）
对于有限图，若无零度顶点，则除4度及3度顶点外，可能的顶点情况有：
2个2度点；
1个2度点和2个1度点；
4个1度点； （6分）
即对应图的顶点数分别至少为9、10、11. （8分）
点点赞赏，手留余香
给TA打赏
评论0