《答案-离散数学2010-2011-a》由会员分享，可在线阅读，更多相关《答案-离散数学2010-2011-a（4页珍藏版）》请在金锄头文库上搜索。
1、 A 卷 总 4 页 第 1 页上海交通大学试卷（ A 卷）答案与评分标准（ 20 10 至 20 11 学年 第 1 学期 ）班级号_ 学号_ 姓名 课程名称 离散数学 成绩 一、选择题（26 分，每题 2 分。每题只有一个选项是正确的，请将答案写在题号前的括号 里）CCDDABA BBADCA二、填空题（20 分，每题 2 分）乙 1(xy)( xy)0 ( ( )( ( )( , )x P xy Q yR x y （）（）adcba4奇数n(n-1)/227A 卷 总 4 页 第 2 页班级号_ 学号_ 姓名_三、 (14 分，第一、二题 4 分，第三题 6 分)解答下列各题：(1) 求
2、命题公式(xz)(yz)的主析取范式。解法一：真值表2 分(xyz)( xyz)(xyz) 2 分解法二：用等值演算求解，只要正确同样给分！（2）求公式的前束范式。()( () ( , )() ( , )xy F x yz G x z 答：()()()( ( , )( , )xyz F x yG x z注：没有写出范式的扣 1 分。(3) 给定解释如下：a)2,3D b)2a c)(2)3,(3)2ffd)( ):(2)0,(3)1F xFF( , ):( , )1,2,3G x yG i ji j( , ): (2,2)(3,3)1;(2,3)(3,2)0L x yLLLL求下列各式的真值，
3、并说明理由：a)()( )( , )xF xG x ab)()( ( )( ,( )xF f xG x f xc)()() ( , )xy L x y答：（每个答：（每个 2 分，共分，共 6 分）分）a)原式真值为原式真值为，因为，因为。0(2)0Fb)原式真值为原式真值为 ，因为当，因为当时，时，与与同时真值为同时真值为 。12x ( ( )F f x( ,( )G x f x1c)原式真值为原式真值为 。1A 卷 总 4 页 第 3 页班级号_ 学号_ 姓名_四、 （16 分，每题 8 分）构造下面推理的证明（其中至少有一题用归结推理证明） 。（1）只要 A 曾到过受害者房间并且 11
4、点以前没离开，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）每个喜欢步行的人都不喜欢坐汽车，每个人或喜欢坐汽车或喜欢骑自行车，有的人不喜欢骑自 行车，因而有的人不喜欢步行。证：设论域为所有的人。:“喜欢步行”
5、 ；:“喜欢坐汽车” ；：“喜欢骑自行车” 。( )P xx( )Q xx( )R xx则原命题可以形式化表示为()( ( )( ), ()( ( )( ), ()( )()( )x P xQ xx Q xR xxR xxP x 可形式化证明如下：(1) P()( )xR x(2) ES, (1)( )R a(3) P()( ( )( )x Q xR x(4) US, (3)( )( )Q aR a(5) T (2)、（4）( )Q a(6) P()( ( )( )x P xQ x (7) US, (6)( )( )P aQ a (8) T(5)(7)( )P a(9) EG()( )xP x
6、注：这两题证明部分需要有一个用归结推理证明。如都用归结推理证明，只要正确同样给分！A 卷 总 4 页 第 4 页班级号_ 学号_ 姓名_五、(8 分) 证明：小于 30 条边的简单平面图中有一个顶点的度数小于等于 4.证明：假设每个顶点的度数均大于 4，即因为( )5.id v即3 分12( )5 ,vi imd vn2,5nm由于代入后得到 即有与边数小于 30 相矛盾。5 分36,mn66,5mm30,m 六、(8 分) 证明：在任何完全图中，对每条边定向后，所有顶点入度的平方之和等于所有顶点出度的平方之和。证明： 设该图具有 n 个顶点。对任一顶点都与其余 n-1 个结点相连，则有vi(
7、 )( )1iidvdvn又因为边数 4 分111(1)( )( ),2nnii iimn ndvdv故而有4 分22112211122121( )(1)( )(1)2(1)( )( )1(1)2(1)(1)( )2( ) .nnii iinnnii iiini ini idvndvnndvdvn nnn ndvdv七、(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=P2+e，则 e 一定是两个 圈的惟一的共同边界。这样，P1+ P2就成了树的一个圈。这与树无圈相矛盾。4 分
