参考答案及评分细则
西南科技大学2009——2010学年第 2学期
《离散数学B》期末考试试卷（A卷）
课程代码 1 4 3 9 9 0 2 4 0 命题单位 计算机学院：数学与算法课程组 一、 （10分）求p→(p∧(q→r))的主析取范式和主合取范式（不能采用真值表技术）。
解：p→(p∧(q→r))
┐p∨(p∧(┐q∨r )) ┐p∨(p∧┐q)∨(p∧r )
(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧┐r) ∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(p∧q∧r) （主析取范式） (┐p∨p)∧(┐p∨┐q∧r ) ┐p∨┐q∧r （主合取范式）
二、 （12分）将下列命题符号化并给出形式证明。
如果王华来上离散数学，若地球不是方的，则太阳从西方升起；如果王华在学校，那么王华一定来上离散数学；地球不是方的。所以，如果王华在学校，太阳从西方升起。
令P：王华来上离散数学，Q：地球是方的，R：太阳从西方升起，S：王华在学校。 解：符号化（4分）
前提：P→（¬Q→R）或者（P∧¬Q）→R， S→P， ¬Q。 结论： S→R 证明：（8分） 步骤 断言 根据 1 S P，附加前提 2 S→P P， 3 P T，1，2，假言推理 4 P→（¬Q→R） P 5 ¬Q→R T，3，4，假言推理 6 ¬Q P 7 R T，5，6，假言推理 8 S→R T，1，7，CP规则
三、 （12分）将下列推理符号化并用推理规则证明推理的有效性：
所有运动的物体都是没有生命的，有些物体是运动的，故有些物体没有生命。 令P(x):x是运动的物体，Q(x):x是有生命的。
解：符号化（4分） (x)(P(x) ¬Q(x))，(x)P(x)(x) ¬Q(x)
第 1 页 共 6 页
*密*
参考答案及评分细则
西南科技大学2009——2010学年第2学期
《 离散数学B 》期末考试试卷（A卷）
证明：（8分） (1)(x)P(x) P (2)P(c) ES，(1) (3)(x)(P(x) ¬Q(x)) P (4)(P(c) ¬Q(c)) US,(3) (5)¬Q(c) T,(2),(4),I (6)(x) ¬Q(x) EG,(5) 四、 （10分）设集合X＝{X1,X2,X3,X4}，R是定义在X上的关系： R＝{ 求r(R),s(R),t(R)。 解： r(R)＝R∪IA ＝{ s(R)＝R∪R-1 ＝{ ＝{ （1） (4分)写出该偏序关系≤的集合表达式； （2） (6分)求B={x1,x2,x3,x4}上的极大元、极小元、最大元、最小元、上界和下 界。 解： （1）偏序关系≤：｛ （2）极大元：x1,x2，极小元：x3,x4,最大元：无,最小元：x5,上界：无，下界：x5 第 2 页 共 6 页 *密* 参考答案及评分细则 西南科技大学2009——2010学年第2学期 《 离散数学B》期末考试试卷（A卷） 六、 (10分) （1）（6分）判断图a是否是哈密尔顿回路，若是，请画出一条哈密顿回路；若不是，请说明原因； （2）（4分）判断图b是否欧拉图，并说明原因。 (a) (b) 解： （1）用标记法可以判断该图不是哈密尔顿图； （2）不是欧拉图，因为奇度节点个数不是0个。 七、 (10分)用Dijkstra算法求下图所示带权图中v1到其余各顶点的最短路径。（要求写 出计算过程） 解：Dijkstra算法过程概括于下表中： S {v1} {v1,v2} { v1,v2,v6} { v1,v2,v6,v3} { v1,v2,v6,v3,v4} { v1,v2,v6,v3,v4,v5} x - v2 v6 v3 v4 V5 d(x) d(v2) - 6 7 9 15 15 6 6 6 6 6 6 d(v3) ∞ 9 9 9 9 9 d(v4) d(v5) d(v6) ∞ ∞ 15 15 15 15 15 15 15 15 15 15 7 7 7 7 7 7 第 3 页 共 6 页 *密* 参考答案及评分细则 西南科技大学2009——2010学年第2学期 《 离散数学B》期末考试试卷（A卷） 八、 （10分）对如下所示有向图D， （1）(2分) 写出D的邻接矩阵； （2）（2分）利用邻接矩阵求D中长度为2的路径的总数； （3）(6分) 利用邻接矩阵求出可达性矩阵P和强分图。 解：（1）D的邻接矩阵A为： v1 v2 v3 v4 v5 (2) （2）A为： v1 0 1 0 0 0 v2 0 0 1 0 0 v3 1 0 0 0 0 v4 1 0 1 0 1 v5 1 0 0 0 0 0 1 0 2 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 所以，D中长度为2的路径的总数为7条。 第 4 页 共 6 页 *密* 参考答案及评分细则 西南科技大学2009——2010学年第2学期 《 离散数学B》期末考试试卷（A卷） 2 （3）A为： 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A3为： 1 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 A4为： 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 A5为： 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 可达性矩阵P为：A1∨ A2∨ A3∨A4∨ A5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 第 5 页 共 6 页 *密* 参考答案及评分细则 西南科技大学2009——2010学年第2学期 《 离散数学B》期末考试试卷（A卷） PT为： 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 P∧PT为： 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 所以各强分图的顶点集为：｛v1,v2,v3｝，｛v4｝，｛v5｝。 九、 (10分)用克鲁斯卡尔算法求下图所示带权图的最小生成树。（要求画出生成过程） 解：生成过程如下图所示： 十、 （6分）史密斯夫妇邀请4对夫妇参加晚会，每个人来的时候，房间里有些人会与来 的人握手，当然，每个人都不会与自己的配偶握手，也不会跟同一个人握手两次。人到齐后，史密斯先生问每个人和别人握了几次手，他们每个人的握手次数都不一样。问：史密斯夫人和别人握了几次手？（要写出分析过程。） 解：4次（应用图论知识解,只要分析正确，均可得分。） 第 6 页 共 6 页 因篇幅问题不能全部显示，请点此查看更多更全内容