试卷库13及答案

第 1 页

： 号 学 线 封 ： 名 姓 密 ： 级 班 重 庆 科 技 学 院

200 5 /200 6 学年第 2 学期考试试卷

课程名称： 离散数学 课程代码： 专业班级： 计科普2004级 教学班号： 本卷为 大补考卷，共 4 页，考试方式： 闭卷 ，考试时间： 120 分钟 题 号 一 二 三 四 五 六 七 八 九 十 总 分 复核人 得 分 阅卷人 一、基本题：（每小题2分共20分）

1、填空：设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为（ ）

2、填空题：解释（0，0）使命题公式A?(p?(p?q))?q的真值为（ ） 3、选择题：用P表示：天下大雨；Q表示：他乘公共汽车上班。将“只有天下大雨，他才乘公共汽车上班。”符号化正确的是（ ）

A、P?Q B、 Q?P C、P?Q D、 P?Q

4、选择题：给定下列各序列，不能构成无向简单图的度数序列是（ ）

A 、1，1，1，2，3； B、 2，2，2，2； C、 3，3，3，3； D 、1，3，3，3。 5、经过图中每个顶点一次且仅一次的通路，称为（ ）通路。 6、选择题：设Ａ＝???，Ｂ＝P(P(A))，以下不正确的是（ ）。 Ａ、{???,?}?Ｂ Ｂ、{???}∈Ｂ

Ｃ、{???}包含于Ｂ Ｄ、｛｛｛｛?｝｝，?｝｝包含于Ｂ 7、判断：设R集合是A上的等价关系, L是由A/R诱导A上的等价关系，则 （。 ）

8、填空题：写出(P?Q)??P?R?的对偶式（

）。

9、填空题：设 是我校本科生全体构成的集合，两位同学等价当且仅当他们在同一个班，则等价类的个数为（ ），同学小王所在的等价类为（ ）。 10、填空题：在n阶图中初级通路的长度不大于（ ）。 二、解答题（每小题6分共36分）

1、判断命题公式p?(p?q?r)的类型，方法不限，要求有过程。

第 2 页

2、设有向简单图D的度数列为2，2，3，3， 入度列为0，0，2，3，试求D的出度列。（说明原因）

3、设R为一个偏序集，其中A={1，2，3，4，6，9，24，，27，72}R是A上的整除关系。（1）画出的哈斯图；（2）求R关于A的极大元；（3）求B={4,6,9}的最小上界和最大下界。 4、（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，（1）应该有几片树叶？（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2。

5、设A={a,b,c,d}，给定A上的两个关系R和L分别为 (1)写出R和L的关系矩阵。（２）求R?L及 t(R?L)

6、说明下图是否为欧拉图,哈密尔顿图,平面图(写明原因)

三、证明题

第 3 页

1、（7分）对任何集合 A，B，?是空集，E是全集 求证：A?B?A?B?E

2、（7分）证明：?x(P(x)→Q(x))?(?xP(x)→?xQ(x))是永真式。 3、（7分）对任何集合 A，B求证：A?(B?C)?(A?B)?(A?c)

四、应用题

第 4 页

1、（8分）用命题推理理论来论证 下述推证是否有效？

甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 2、（8分）用谓词推理理论来论证下述推证。

任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论域是人)。 3、（6分）画一棵带权为1，1，2，3，3，4，5，8的最优二元树T，并计算它的权W（T）和相应的二元前缀码

答案

第 5 页

一、 基本题

1、p?q 2、D 3、B 4、D 5、哈密尔顿通路 6、D 7、正确 8、(P?Q)???P?R? 9、全校本科生班级数， 同班同学 10、n-1 二、解答题

1、解：真值表法或等值演算法或说明当前提为真时结论不可能为假 永真式 （6分）

2、解：因为有向图的出度总和等于入度总和且度总和等于边数的两倍（3分） 所以D的出度列2，2，1，0 3、解：（1）哈斯图略（2分）（2）27，72（2分）（3），71，1 （2分） 4、解：（1）设有x片树叶，则（1分）

2?2?4?3?x??2?4?x?1??2（2分）得x=6即有6片树叶

（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2图略（3分） 5、解：（1）（2分）

?0??0R??1??0?100001000??0??0??0,L??0?1???10???010000111??0? 0??0??（2）R?L?a,b,b,a,b,c,c,d??（2分）

?1t(R?L)??R?L???R?L?（2分）

6、解：是欧拉图（2分）,哈密尔顿图（2分）不是平面图（2分） 三、证明题

1、证明：?A?B?A?A?A?B?E?A?B(A?B?E)

?A?B?A?B?E（3分）

?A?B?E?A?B?B??A?B??B???B??B?A???B?B??B??B?A??E?B?B?A?B(A?B?A)?A?B（4分） 所以A?B?A?B?E

2、证明：?x?P?x??Q?x????x??P?x??Q?x??（2分）

??x?P?x???xQ?x?（2分）???xP?x???xQ?x?（2分）??xP?x???xQ?x? ?A?(B?C)?A???B?C???C?B????A?B?C???A?C?B?（3分） 又?(A?B)?(A?c)??A?B?C???A?C?B?（4分） 所以A?(B?C)?(A?B)?(A?c)

四、应用题 1、有效

解：P：甲获胜，Q：乙获胜，R：丙获胜，S：丁不失败 前提：P??Q,R?Q,?P?S（3分） 3、证明：

又

第 6 页

结论：R?S（1分） 证明得此推理有效（4分） 2、解：P（x）：x喜欢步行，：P（x）：x喜欢步行，R（x）：x喜欢骑自行车 前提：??x??P?x???Q?x??,??x??Q?x??R?x??,??x??R?x?（3分） 结论：??x??P?x?（1分） 证明：此推理有效（4分）

（1） (?x)?R(x) P (2) ?R(c) (1)ES (3) (?X)(Q(x)?R(x)) P (4) Q(c)?R(c) (3) US (5) Q(c) (2)(4)T,I (6) (?X)(P(X)??Q(x)) P (7) P(c)??Q(c)) (6)US (8) ?P(c) (5)(7)T,I

(9) (?x)?P(x) (8)EG 3、解：运用哈夫曼算法得 最上端结点为27（2分），W（T）为74（2分），左0右1得前缀码（2分）

第 6 页

结论：R?S（1分） 证明得此推理有效（4分） 2、解：P（x）：x喜欢步行，：P（x）：x喜欢步行，R（x）：x喜欢骑自行车 前提：??x??P?x???Q?x??,??x??Q?x??R?x??,??x??R?x?（3分） 结论：??x??P?x?（1分） 证明：此推理有效（4分）

（1） (?x)?R(x) P (2) ?R(c) (1)ES (3) (?X)(Q(x)?R(x)) P (4) Q(c)?R(c) (3) US (5) Q(c) (2)(4)T,I (6) (?X)(P(X)??Q(x)) P (7) P(c)??Q(c)) (6)US (8) ?P(c) (5)(7)T,I

(9) (?x)?P(x) (8)EG 3、解：运用哈夫曼算法得 最上端结点为27（2分），W（T）为74（2分），左0右1得前缀码（2分）

本文来源：https://www.bwwdw.com/article/lraa.html