中央广播电视大学2008--2009学年度第二学期期末考试
离散数学(本) 试题
2009年 1月
题号一二三四五六总分得分 一、单项选择题（每小题3分，本题共15分）
1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )．
A．A?B，且A?B B．B?A，且A?B
C．A?B，且A?B D．A?B，且A?B
2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( )．
图一
A．（a）是强连通的 B．（b）是强连通的
C．（c）是强连通的 D．（d）是强连通的
3．设图G的邻接矩阵为
则G的边数为( )．
A．6 B．5 C．4 D．3
4．无向简单图G是棵树，当且仅当( )．
A．G连通且边数比结点数少1 B．G连通且结点数比边数少1
C．G的边数比结点数少1 D．G中没有回路．
5．下列公式 ( )为重言式．
A．?P??Q?P?Q B．(Q?(P?Q)) ?(?Q?(P?Q))
C．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q
二、填空题（每小题3分，本题共15分）
6．命题公式的真值是 ．
7．若图G=
8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．
9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 ．
10．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为 ．
三、逻辑公式翻译（每小题4分，本题共12分）
11．将语句"他不去学校．"翻译成命题公式．
12．将语句"他去旅游，仅当他有时间．"翻译成命题公式．
13．将语句"所有的人都学习努力．"翻译成命题公式．
四、判断说明题（每小题7分，本题共14分）
判断下列各题正误，并说明理由．
14．设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则f是单射．
15．设G是一个有6个结点14条边的连通图，则G为平面图．
五．计算题（每小题12分，本题共36分）
16．试求出（P∨Q）→R的析取范式，合取范式，主合取范式．
17．设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算
（1）（A?B） （2）（A∪B） （3）（A∪B）?（A∩B）．
18．图G=
（1）画出G的图形；
（2）写出G的邻接矩阵；
（3）求出G权最小的生成树及其权值．
六、证明题（本题共8分）
19．试证明集合等式A? (B?C)=(A?B) ? (A?C)．
中央广播电视大学 学年度第 学期期末考试
计算机科学与技术专业 级第二学期离散数学
试题解答
(供参考)
一、单项选择题（每小题3分，本题共15分）
1．A 2．D 3．B 4．A 5．C
二、填空题（每小题3分，本题共15分）
6．T （或1）
7．W?|S|
8．0
9．5
10．R(x，y )中的y
三、逻辑公式翻译（每小题4分，本题共12分）
11．设P：他去学校， （1分）
? P． （4分）
12．设 P：他去旅游，Q：他有时间， （1分）
P ?Q． （4分）
13．设P(x)：x是人，Q(x)：x学习努力， （1分）
（?x）(P(x)?Q(x))． （3分）
四、判断说明题（每小题7分，本题共14分）
14．正确． （3分）
设x1，x2为自然数且x1?x2，则有f(x1)= x1+6? x2+6= f(x2)，故f为单射． （7分）
15．错误． （3分）
不满足"设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．"
（7分）
五．计算题（每小题12分，本题共36分）
16．（P∨Q）→R?┐(P∨Q)∨R? (┐P∧┐Q)∨R（析取范式） （3分）
? (┐P∨R)∧ (┐Q∨R)（合取范式） （6分）
? ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P))
? (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P)
∧(┐Q∨R∨┐P)
? (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R)
（主合取范式） （12分）
17．（1）（A?B）={{a, b}, 2} （4分）
（2）（A∪B）={{a, b}, 1, 2, a, b, {1}} （8分）
（3）（A∪B）?（A∩B）={{a, b}, 2, a, b, {1}} （12分）
18．（1）G的图形表示为：
（3分）
（2）邻接矩阵：
（6分）
（3）粗线表示最小的生成树，
（10分）
权为7： （12分）
六、证明题（本题共8分）
19．证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C，
也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以S?T． （4分）
反之，若x∈T，则x∈A∩B 或 x∈A∩C，
即x∈A且x∈B 或 x∈A且x∈C
也即x∈A且x∈B∪C，即x∈S，所以T?S．
因此T=S． （8分）
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
阅读诗句“蒹葭苍苍，白露为霜。”想象着诗中04-27
斯金纳认为“凡是使反应概率增加，或维持某种反应水平的04-27
下列选项中不属于资源管理策略的是04-27
创造性思维是人类思维的高级形式。许多心理学家认为，创04-27
个体自我意识的发展经历了从生理自我到社会自我，再到心04-27
下列选项中不是影响对时间知觉的因素有04-27