中央广播电视大学2007--2008学年度第二学期期末考试
离散数学(本) 试题
2008年 7月
题号一二三四五六总分得分
一、单项选择题（每小题3分，本题共15分）
1．设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=,
A．R1和R2 B．R2 C．R3 D．R1和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、1、6、1
3．若集合A的元素个数为10，则其幂集的元素个数为（ ）．
A．1024 B．10 C．100 D．1
4．设完全图K有n个结点(n≥2)，m条边，当（ ）时，K中存在欧拉回路．
A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数
5．已知图G的邻接矩阵为
，
则G有（ ）．
A．5点，8边 B．6点，7边
C．6点，8边 D．5点，7边
二、填空题（每小题3分，本题共15分）
6．设集合A＝a，b，那么集合A的幂集是 ．
7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 个．
8．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树．
9．设连通平面图G的结点数为5，边数为6，则面数为 ．
10．设个体域D＝a, b，则谓词公式(?x)A(x)∧（?x）B（x）消去量词后的等值式为 ．
三、逻辑公式翻译（每小题4分，本题共12分）
11．将语句"如果所有人今天都去参加活动，则明天的会议取消．"翻译成命题公式．
12．将语句"今天没有人来．" 翻译成命题公式．
13．将语句"有人去上课．" 翻译成谓词公式．
四、判断说明题（每小题7分，本题共14分）
判断下列各题正误，并说明理由．
14．┐P∧（P→┐Q）∨P为永真式．
15．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．
图一
五．计算题（每小题12分，本题共36分）
16．设集合A=1，2，3，4，R=x, y?A；，试
（1）写出R的有序对表示；
（2）画出R的关系图；
（3）说明R满足自反性，不满足传递性．
17．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式．
18．设图G=
(1) 画出G的图形表示；
(2) 写出其邻接矩阵；
(3) 求出每个结点的度数；
(4) 画出图G的补图的图形．
六、证明题（本题共8分）
19．试证明（?x）（P（x）∧R（x））==> （?x）P（x）∧（?x）R（x）．
中央广播电视大学2007--2008学年度第二学期期末考试
离散数学(本) 试题解答及评分标准
(供参考)
一、单项选择题（每小题3分，本题共15分）
1．B 2．B 3．A 4．C 5．D
二、填空题（每小题3分，本题共15分）
6．{?,a,b,a,b}
7．2
8．4
9．3
10．(A (a)∧A (b))∧(B（a）∨B（b）)
三、逻辑公式翻译（每小题3分，本题共12分）
11．设P：所有人今天都去参加活动，Q：明天的会议取消， （1分）
P? Q． （4分）
12．设 P：今天有人来， （1分）
? P． （4分）
13．设P(x)：x是人，Q(x)：x去上课， （1分）
(?x)(P(x) ?Q(x))． （4分）
四、判断说明题（每小题7分，本题共14分）
14．正确． （3分）
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
如果P的值为真，则┐P∧（P→┐Q）∨P为真， （5分）
如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，
也即┐P∧（P→┐Q）∨P为真，
所以┐P∧（P→┐Q）∨P是永真式． （7分）
另种说明：
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
只要其中一项为真，则整个公式为真． （5分）
可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，
所以┐P∧（P→┐Q）∨P是永真式． （7分）
或用等价演算┐P∧（P→┐Q）∨P?T
15．正确． （3分）
对于集合A的任意元素x，均有
按照最小元的定义，在集合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）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 （9分）
因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。
（12分）
17．P→（R∨Q）
?┐P∨(R∨Q)
? ┐P∨Q∨R （析取、合取、主合取范式） （9分）
?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R)
∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式） （12分）
18．（1）关系图
（3分）
（2）邻接矩阵
（6分）
（3）deg(v1)=2
deg(v2)=3
deg(v3)=4
deg(v4)=3
deg(v5)=2 （9分）
（4）补图
（12分）
六、证明题（本题共8分）
19．证明：
（1）（$x）（P（x）∧R（x）） P
（2）P（a）∧R（a） ES(1) （2分）
（3）P（a） T(2)I
（4）（$x）P（x） EG(3) （4分）
（5）R（a） T(2)I
（6）（$x）R（x） EG(5) （6分）
（7）（$x）P（x）∧（$x）R（x） T(5)(6)I （2分）
3
1
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
以下德育途径，属于基本途径的是(04-27
阅读诗句“蒹葭苍苍，白露为霜。”想象着诗中04-27
斯金纳认为“凡是使反应概率增加，或维持某种反应水平的04-27
下列选项中不属于资源管理策略的是04-27
创造性思维是人类思维的高级形式。许多心理学家认为，创04-27
个体自我意识的发展经历了从生理自我到社会自我，再到心04-27
下列选项中不是影响对时间知觉的因素有04-27