答案-离散数学2010-2011-A.doc

上海交通大学试卷（ A 卷）答案与评分标准 （ 20 10 至 20 11 学年 第 1 学期 ）班级号_ 学号_ 姓名 课程名称 离散数学 成绩 一、 选择题（26分，每题2分。每题只有一个选项是正确的，请将答案写在题号前的括号里）CCDDABABBADCA二、 填空题（20分，每题2分）乙 1(xy)( xy)0adcba4奇数n(n-1)/227班级号_ 学号_ 姓名_三、 (14分，第一、二题4分，第三题6分)解答下列各题：(1) 求命题公式(xz)(yz)的主析取范式。解法一：真值表2分(xyz)( xyz)(xyz) 2分解法二：用等值演算求解，只要正确同样给分！（2）求公式的前束范式。答：注：没有写出范式的扣1分。(3) 给定解释如下：a)b)c)d)求下列各式的真值，并说明理由：a)b)c)答：（每个2分，共6分）a) 原式真值为，因为。b) 原式真值为，因为当时，与同时真值为。c) 原式真值为。班级号_ 学号_ 姓名_四、（16分，每题8分）构造下面推理的证明（其中至少有一题用归结推理证明）。（1）只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。解：假设 P：“A曾到过受害者房间” Q：“A11点以前离开” R：“A犯谋杀罪” S：“看门人看见他”需要证明：（PQR，P，QS，SR2分(1) QS P(2) S P(3) Q T(1)(2) ，(4) P P (5) PQ T(3)(4)，(6)（PQ）R P (7) R T(5)(6)， 6分（2）每个喜欢步行的人都不喜欢坐汽车，每个人或喜欢坐汽车或喜欢骑自行车，有的人不喜欢骑自行车，因而有的人不喜欢步行。证：设论域为所有的人。:“喜欢步行”；:“喜欢坐汽车”；：“喜欢骑自行车”。则原命题可以形式化表示为可形式化证明如下：(1) P(2) ES, (1)(3) P(4) US, (3)(5) T (2)、（4）(6) P(7) US, (6)(8) T(5)(7)(9) EG注：这两题证明部分需要有一个用归结推理证明。如都用归结推理证明，只要正确同样给分！班级号_ 学号_ 姓名_五、(8分) 证明：小于30条边的简单平面图中有一个顶点的度数小于等于4.证明：假设每个顶点的度数均大于4，即因为即3分由于代入后得到 即有与边数小于30相矛盾。5分六、(8分) 证明：在任何完全图中，对每条边定向后，所有顶点入度的平方之和等于所有顶点出度的平方之和。证明： 设该图具有n个顶点。对任一顶点都与其余n-1个结点相连，则有又因为边数 4分故而有 4分七、(8分) 设G是一个连通图，其中T是G的一棵生存树（支撑树）。设e是G - T中的任意一条边。证明：T + e中有且仅有一个圈（初级回路）。证明：设e=(u,v)。（a） 圈C的存在性：由于树T中从u到v存在一条初级道路P，所以加上边e后，得到的P+e一定是一个圈。4分（b） 圈C的惟一性：反证法。如果存在两个不同的圈C1P1+e和C2