试卷代号：1009
中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试（半开卷）
离散数学（本）试题
2008年7月
题号 一 二 三 四 五 六 总分
分数
得 分 评卷入 一、单项选择题（毎小题3分,本题共15分）
1.设 A={a,3},B={l,2},R,Rz，R3 是 A 到B 的二元关系，且 R. = {<a,2> ,<b,2>}, R2 = {<a,l> ,<a,2> ,<b,l>} ,R3 = {<a,l> ,<b,2>},则（ ）不是从 A 到B 的函数.
A. Ri 和 Ri B. 7?2
C. R3 D. Ri 和 R3
2.设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
3.若集合A的元素个数为10,则其舞集的元素个数为（ ）.
A.1024 B. 10
C. 100 D. 1
4.设完全图K”有〃个结点（n>2）,m条边，当（ ）时,K“中存在欧拉回路.
A. m为奇数 B.”为偶数
C. ”为奇数 D.,m为偶数
B. 6点，7边
D. 5点，7边
碍 分 评卷人. 二、填空题（毎小题3分,本题共15分）
6.设集合A^{a9b}，那么集合A的蓦集是 ■
7.如果R和R是A上的自反关系，则R】UR DR ,R —R中自反关系有—个.
8.设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去_ 条边后使之 变成树.
9.设连通平面图G的结点数为5,边数为6,则面数为—・
10. 设个体域D={a3},则谓词公式（Vz）A&）/\（抄消去量词后的等值式为
碍 分 评吐 三、逻辑公式翻译（每小题4分，本题共12分）
11.将语句“如果所有人今天都去参加活动，则明天的会议取消.”翻译成谓词公式•
12.将语句“今天没有人来.”翻译成命题公式.
13.将语句“有人去上课.”翻译成谓词公式.
得 分 评卷人 四、判断说明题(每小题7分,本题共14分)
判断下列各题正误,并说明理由.
14.r p A (Pf r Q) V P 为永真式.
15.若偏序集VA,R>的哈斯图如图一所示，则集合A的最大元为a ,最小元不存在.
16. 设集合 A=(1,2,3,4} ,R={<x, y>\x, |x—y| = 1 或 x—^=0},试
(1)写出R的有序对表示；
(2)画出R的关系图；
(3)说明R满足自反性，不满足传递性.
17.求Pf QVR的析取范式，合取范式、主析取范式，主合取范式.
18.设图 G= <V,E>, V= ( Vt,v2,v3,vt,vs},E={(功，v2), ( Vi, v3), ( v2, v3 ), (v2, q),(处,a),(防，vs),(vt» v5) }，试
(1)画出G的图形表示；
(2)写出其邻接矩阵；
(3)求出每个结点的度数；
(4)画出图G的补图的图形.
得 分 评卷入 六、证明题(本题共8分)
19.试证明(3 我(P(z) A R(x))=>( 3 x)P(x) A ( 3 z)R(工).
试卷代号:1009
中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试（半开卷）
离散数学（本）试题答案及评分标准
（供参考）
2008年7月
一、 单项选择题（毎小题3分,本题共15分）
1. B 2. B 3. A 4. C 5. D
二、 填空题（毎小题3分，本题共15分）
6. {0 ,{a}, {6}, {a,b}}
7.2
8.4
9.3
10.（A （a） AA （6）） A（B（a） VB（6））
三、 逻辑公式翻译（毎小题4分,本题共12分）
11.设P：所有人今天都去参加活动,Q：明天的会议取消， （1分）
F—Q. （4 分）
12.设P：今天有人来， （1分）
P. （4 分）
13.设P（x）：x是人,Q&）：工去上课， （1分）
（3x）（PU） AQU））. （4 分）
四、 判断说明题（毎小题7分,本题共14分）
14. 正确. （3分）
rP/\（Pf rQ） V P是由rp/\（Pf rQ）与P组成的析取式，
如果P的值为真，则rQ）VP为真， （5分）
如果P的值为假，则rP与P-rQ为真，即rPA/f rQ）为真，
也即 rP/\（Pf rQ）VP 为真，
所以rP/\（PfrQ）V P是永真式. （7分）
67
另种说明：
-PA(P~*-Q) VP是由rPMPfrQ)与P组成的析取式，
只要其中一项为真，则整个公式为真. (5分)
可以看到，不论P的值为真或为假，’ (P-> rQ)与p总有一个为真，
所以rP/\(FfrQ) VP是永真式. (7分)
或用等值演算-PA (Ff r Q) v P^T
15. 正确. (3分) 对于集合A的任意元素工，均有V工,a>£R(或工Ra),所以a是集合A中的最大元.
(5分) 按照最小元的定义,在集合A中不存在最小元. (7分)
五、计算题(每小题12分，本题共36分)
16.(1)R =(<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,
<3,2>,<3,4>,<4,3>) (3 分)
(2)关系图为
（6分）
(3)因为V1,1>,V2,2>,<3,3>,<4,4>均属于R,即A的每个元素构成的有序对均 在R中，故R在厶上是自反的. (9分)
因有V2,3>与V3,4>属于R,但<2,4>不属于R,所以R在厶上不是传递的.(12分)
17.Pf(RVQ) ‘
0rpV(RVQ)
0rFVQVR(析取、合取、主合取范式) (9分)
C(rp/\rQ/\-,R)V(rp/\-,Q/\R)V(rp/\Q/\R)V(P/\rQ/\rR)V(F/\ rQ/\R)V(P/\Q/\ rR)V(P/\Q/\R)(主析取范式) (12 分)
18.(1)关系图
%
（3分）
（2）邻接矩阵
■0 1 10O’
1 0 110
1 1 011（6分）
0 1 101
0 0 110.
(3)deg(%) = 2
deg(P2)= 3’f
deg(TJ3)=4
degm ) = 3
deg(费)~~2 （9分）
（4 •汴图Vl
o\)
V：i v4 (12 分)
六、证明题（本题共8分）
19.证明：
(1)(D(PS)/\R(Q)P
(2)P(a) Al?(a) ES(1) （2分）
(3)P(a)T(2)I
(4)(3x)PU) EG(3) (4分)
(5)R(q)T(2)I
(6)(如)R(z) EG(5) (6分)
(7)(%)PM)/\(DRGc) T(5)(6)； （8分）
点点赞赏，手留余香
给TA打赏
评论0