1、国家开放大学电大本科离散数学期末试题题库及答案（试卷号：1009)题库一一、 单项选择题（每小题3分，本题共15分）1. 若集合A =I,2,3，则下列表述正确的是（） A. 1,2,3EAB. ACl,2C. 1,2,3)A D. 1, 2) EA2. 设A=1,2,3),B= l,2,3,4),A到B的关系R=I工EA,yEB，工y),则R=().A. ,B. ,C. ,0. ,3. 无向图G的边数是10，则图G的结点度数之和为（） A. 10c.304. 如图一所示，以下说法正确的是（A. e是割点B. a,e)是点割栠C. b,e)是点割集D. d)是点割集5. 设个体域为整数集，则公
2、式V工3y釭y=2)的解释可为（） A.任意整数工对任意整数y满足工y=2B.对任意整数工，存在整数y满足工y=2c.存在一整数工，对任意整数y满足工y=2D.存在一整数工，有整数y满足工y=2B. 20D. 5） b d图一答案：J.C2. D3. B4. A5. B二、 填空题（每小题3分 本题共15分）6. 设集合A=1,2,3,B= (2,3,4),C=3,4,5，则BU(A -C)等于7. 设A=I.2,B= 2,3,C= 3,4)，从A到B的函数J=.，从B到C的函数g=,，则Ran(g寸）等于8. 两个图同构的必要条件包括结点数相等、边数相等与9. 设G是连通平面图，v,e,.分
3、别表示G的结点数， 边数和面数，1J值为5,e 值为4则r的值为10. 设个体域D=l.2,3,4，则谓词公式(3分A（工）消去量词后的等值式为答案：6. 1,2,3,4)7. 3,4)8. 度数相同的结点数相等9. l10. A(l) VA(2) VA(3) VA(4)三、 逻辑公式翻译（每小题6分， 本题共12分）11. 将语句“昨天下雨， 今天仍然下雨， “翻译成命题公式12将语句“若不下雨， 我们就去参加比赛， “翻译成命题公式答案：11. 设P：昨天下雨，Q ：今天下雨（2分）则命题公式为：p /Q.(6分）12. 设P:下雨，Q：我们去参加比赛（2分）则命题公式为:P一Q.（或寸.
4、:1-+P)(6分）四、 判断说明题（判断各题正误， 并说明理由， 每小题7分本题共14分）13.若图G是一个欧拉图，则图G中存在欧拉路14. 无向图G的结点数比边数多1，则G是树答案：13. 正确因为若图G是一个欧拉图，则图中存在欧拉回路按定义知，欧拉回路也是欧拉路14. 错误反例：如图G的结点数比边数多1，但不是树乙五、计算题（每小题12分， 本题共36分）15. 设集合A =l,2,3,4上的关系：R= ,S = , 试计算(l)RS1(2)R一1,(3)r(RnS).(3分）(5分）(7分）(3分）16. 图G=，其中V =a, b, c, d), E = (a, b), (a, c)
5、, (a, d), (b, c), (b,d),(c,d)，对应边的权值依次为1、1、5、2、3及4，请画出G的图形、写出G的邻接矩阵并求出G权朵小的生成树及其权值17. 求勹(PVQ)VR的析取范式与主合取范式答案：15. O)A UB=a,b,c,d);(2)A-B=(c,d; (4分）(8分）(3)A XB=,)(12分）16. (l)G的图形表示如图一所示：V1 勹图一(2)邻接矩阵：-01 I 11 0 I 0 1 I 0 1 0 I 0 (3)deg(v1)=3. deg(v1) =2, deg(v,) = 3, deg(v,)=2 (4)补图如图二所示：10 v (3分）(6分）
6、(9分）,.图二17. 用Kruskal算法求产生的最小生成树步骤为：切（v1,v,)=1，选e1=v1v,心(v3,V)3，选e2=v,“切(v,v,)仁选e,=v1v,u（v,v,)=9，选e,=v,v, w(v,v,)=18，选e，叭也w(v1,v,)=22，选e，=v“(12分）(6分）最小生成树如出三所示：. IH ,I) 图三最小生成树的权C(T)= I +3+4 +9+ 18+22=57. 六、 证明题（本题共8分）18. 设A,B,C均为任意集合，试证明：An(B-C)（AnB)一(AnC)答案：18. 证明：设工EA则x,工EAXA, 因AXA=BXB，故x,:,;EBXB，
7、则有rEB,因此A巨B.设xEB，则x，工EBXB,因AXA=BXB，故r,.rEAXA，则有工EA，因此B竺A.故得A=B.(9分）(12分）(l分）(3分）(5分）(6分）(7分）(8分）题库二一、 单项选择题（每小题3分， 本题共15分） 设A=0.3,5,7,9,B=(2，从6,A到B的关系R=I.ry=I则R=). A. ,)B. ,C. ,D. ,2. 若集合A=a,b,c，则下列表述正确的是（） A. a,bAC. a,bEAB. aEAD. 0EA3. 设个体域为集合1,2,3,4,5，则公式(Vx)(3y)（工y=5)的解释可为（） A. 存在一整数工有整数y满足工y=5B
8、对任一整数工存在整数y满足工y=5c.存在一整数工对任意整数y满足工y=5D. 任一辂数工对任竞骆哟v满足工十v=54.设G为连通无向图，则（）时，G中存在欧拉回路A.G存在两个奇数度数的结点B.G存在一个奇数度数的结点C.G不存在奇数度数的结点D.G存在偶数度数的结点s.11阶无向完全图K的边数及每个结点的度数分别是（） A. n(n-l)与nC.n一与n答案：1.D尸尸2. A3.8 B. n(n-1)/2与n-1D. n(n-l)与n-14.C二、填空题（每小题3分，本题共15分）6. 设集合A位比是小于4的正整数，用集合的列举法A=5. B7. 设A=l,2),B=a,b,C=l,2，
9、从A到B的函数/=,)，从B到C的函数g=,，则复合函数g.J=8. 设G=是一个图，结点度数之和为30，则G的边数为9. 设G是具有n个结点m条边k个面的连通平面图，则n+k-2=10. 设个体域D=Z,3,4,A（心为工小于3”，则谓词公式(V心A(x)的真值为答案：6. l.2,3)7. ,)8. 159.m10. 假（或F，或0)尸三、逻辑公式翻译（每小题6分，本题共12分）11. 将语句“如果今天下雨，那么明天的比赛就要延期“翻译成命题公式12. 将语句“地球是圆的，太阳也是圆的“翻译成命题公式答案：11. 设P：今天下雨，Q：明天的比赛就要延期则命题公式为：P一Q.12. 设P:地
10、球是圆的，Q：太阳是圆的则命题公式为：PAQ.(2分）(6分）(2分）(6分）三四、判断说明题（判断各题正误，井说明理由每小题7分，本题共14分）13. 设A=a,b,c,d),R=,），则R是等价关系14. V工）（P(x)/Q(y)）-R（工）中釐词V的辖域为(P（工）八Q(y).答案：13. 错误R不是等价关系，因R中不含，故不满足自反性14正确辖域为紧接蜇词V之后的最小子公式(P(x)AQ(y). 三五、计算题（每小题2分，本题共36分）(3分）(7分）(3分）(7分）15. 设集合A=a,h,c,B=b,c,d)，试计算(DAUB; (2)A-B,(3)AXB.16. 设G=,V=
11、v1,v2,v,v,), E= (v1,Vz), (v, v,), (v1,v,), (vz,v,),(v1,v)，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；（4）画出其补图的图形17. 试利用Kruskal算法求出如下所示赋权图中的最小生成树（妥求与出求隅步骤），开求此最小生成树的权V6 ,VJ 8 答案：15. 解：（l)R S=,) 1(Z)R-1 =,;(3)r(R nS)= ,16. 解：（l)G的图形表示为：4万）(8分）(12分）(3分）5(2)邻接矩阵：() l l 1 1 0 1 1 1 1 0 1 .1l1 O_ (3)粗线与结点表示的是最小
12、生成树，(6分）(10分）权值为917.解：P一(QAR)台，PV(QAR) 析取范式仁 V CR A, R) A (, P V R) 仁, PVQ)V(RA, R)A, PVR)VCQA, Q) 仁, PVQVR)A, PVQV, R)A, PVRVQ)AC, PVRV, Q) 台（勹PVQVR)A(7 PVQV7 R)Ah PV7 QVR) 主合取范式(12分）(2分）(5分）(7分）(9分）(11分）(12分）三六、证明题（本题共8分）18. 试证明：P-QP-.(P-+-.Q).答案：18. 证明：(1门PVQp (I分）(2)P P（附加前提）(3分）(3)Q T(l)(2)1 (5
13、分）(4)PAQ T(2)(3)/ (6分）(5)7GP V7 Q) T(4)E (7分）(6)P一7G P归Q)CP规则( 8分）说明：（1）因证明过程中 ，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出 结论得2或1分(2)可以用其值表验证采用反证法可参照给分题库三一、 单项选择题（每小题3分， 本题共15分）1. 设A= 1,2,3,4),B= 2,3,4),A到B的关系R=工，y巨EA,yEB，且工y=5)，则R=() .A. ,B. ,C. ,D. ,2. 若集合A=a,b,c,d，则下列表述正确的是（） A.(2)EA B. (aEAC
14、. a.,b,c,dEAD. a,b竺A3. 设个体域为整数集，则公式(V心(3y)(工-y=2)的解释可为（） A. 存在一整数x有整数y满足x-y=2B. 存在一整数x对任意整数y满足工y=2C.对任一整数x存在整数y满足x-y=2D. 任一整数工对任意整数y满足:e-y=21.n阶无向完全图K.的边数及每个结点的度数分别是（） A. n(n-1)与nC. n-l与nB. n(n-1)与n一1D. n(n-1)/2与n-15. 设G为连通无向图，则（）时，G中存在欧拉回路答案：1.8 A.G不存在奇数度数的结点8.G存在一个奇数度数的结点C.G存在两个奇数度数的结点D.G存在偶数度数的结点
15、2. D 3. C 4. D5. A二、 填空题（每小题3分， 本题共15分）6. 设集合A= 1.2.3,B= 2.3),C= 3,4，则AU (B-C)7. 设A=a,b),B=l.2.C=a,b.从A到B的函数f=，从2，从B到C的函数g气、2正），则g寸等于8. 设G=是一个图11=10则G的结点度数之和为9. 设G是具有n个结点m条边k个面的连通平面图则，1k-2=10. 设个体域O=, I.2.3.C.i)为万的2倍大千2.贝lji肖词公式A(yl的且值为答案：6.1,2,3 7. (,)8.20（或：2IE|)9. m10. 假（或F，或0)三、 逻辑公式翻译（每小题6分， 本题
16、共12分）11. 将语句“如果他掌握了计算机的用法， 那么他就能完成这项工作“翻译成命题公式12. 将语句“前天下雨，昨天还是下雨“翻译成命题公式答案：I I. 设P:他掌握了计算机的用法，Q：他能完成这项工作（2分）则命题公式为：P-Q.(6分）12. 设P:前天下雨，Q：昨天还是下雨（2分）则命题公式为：p f,.Q.(6分）四、 判断说明题（判断各题正误， 并说明理由每小题7分，本题共14分）13. 设A=(a,b,c,R= -, , , ,，则R是等价关系14, （V:,:）(P(:,:)/Q(y)一R(:r）中屈词V的辖域为(P（工）/Q(y).答案：13. 错误J方丿R不是等价关系
17、，因R中包含与，但不包含，故不满足传递性14. 错误辖域为紧接拉词V之后的最小子公式(P(:r）/Q(y)-+R（工）五、计算题（每小题12分， 本题共36分）15. 设集合A=a,b,c,d),B=a,b)，试计打(l)ALJB;(2)A-B;(3)AXB.(7分）(3分）(7分）16. 设G=,V=压，巧，V1,v,),= (v,v2), (v1,v3), (v1令v)(v2, V3)(v,v)，试(I)给出G的图形表示；(3)求出每个结点的度数；(2)写出其邻接矩阵；(4)画出其补图的图形17试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的
18、权.” II 答案：15. 解：（I)R S=,;(4分）(2)R一1=,(8分）(3)r(R ns=,(12分）16. 解：G的图形表示为：b d 邻接矩阵：f 1 1 1 1 0 1 1 l1 0 11 1 1 0 粗线表示的图是最小生成树，权为5:b :; (3分）(6分）(9分）d (12分）17. 解：气PVQ)V R台(-,p /-,Q) VR 析取范式台(-,PV R) / (-,QVR) (5分）(7分）台(-,PVRV (QA-,Q) AP-+-,（p-.-,Q)答案：18. 证明：(1)., 7 (P一Q)p (2)P-QT(l)E (3)(Q-+R) p (4)7 Rp
19、(5归QT(3)（4)I (6h P T(2) (5) I 说明：(1分）(3分）(4分）(5分）(6分）(8分）(1)因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分(2)另，可以用真值表验证题库四一、 单项选择题（每小题3分，本题共15分）1. 若集合A= 1,2,3,4,B= 1,3,5，则下列表述正确的是（） A. A=BB. BCAC. BAD. B竺A2. 设A=(1,2,3),B = 2,4,6),A到B的关系R=（位，y|2工y)，则R=(). A. ,B. (,C. (,D. ,3. 无向图G是棵树，边数
20、是10，则G的结点度数之和是（） 0021 AC B. 9D. 114.下面的推理正确的是（） A. (l)(t/心F(x)-G（工）前提引入(2)F(y)-G(y)USO). B. 0)(3工）F（工）一G（工）前提引人(2)F(y)-G(y)US(l). C. (1)(3心(F(x)一G（心）前提引人(2)F(y)一G（工）ES(l).D.(1) (t/心(F（心一G（工）前提引人(2)F(y)一G(y)US(l). 5. 设个体域为整数集，则公式V工3y(工+y=2)的解释可为（） A.任一整数工，对任意整数y满足工y=2B.对任一整数工，存在整数y满足工y=2C.存在一整数x，对任意整
21、数y满足工y2D.存在一整数x，有整数y满足工y=2答案：l. C2. D3. A4. D5. B三二、填空题（每小题3分，本题共15分）6.设栠合A= a,b,c),B=b,c),C=(c,d，则An (BUC)等于7.设A=1,2,B =2,3,C= 3,4，从A到B的函数f=,)，从 B到C 的函数g=,，则Ran(g.f)等千8.设G是汉密尔顿图，S是其结点集的 一个子集，若S的元素个数为6，则在G-S中的连通分支数不超过9. 设G是有8个结点的连通图，结点的度数之和为 24，则可从G中删去使之变成树条边后10. 设个体 域D=l,2, 3, 4，则谓词公 式( V.r）A (.r)消
22、去社词后的 等值式 为答案：6. b,c)7. 3,4（或C)8. 69. 510. A(l) AA(2) AA(3) AA(4) 三三、逻辑公式翻译（每小题6分，本题共12分）11. 将语句“昨天下雨，今天仍然下雨“翻译成命题公式12. 将语句“我们下午2点或者去礼堂看电影或者去教室看书“翻译市命颐小寸答案：11.设P：昨天下雨，Q：今天下雨则命题公式为：PAQ.12. 设P：我们下午2点去礼堂看电影，Q：我们下午2点去教室看书则命题公式为：7 (P-Q). 注：或者h PAQ)V(P/7 Q) (2分）(6分）(2分）(6分）勹四、判断说明题（判断各题正误，井说明理由每小题7分，本题共14
23、分）13. 不存在集合A与B，使得AEB与A竺B同时成立14. 如图二所示的图G存在一条欧拉回路V5 d内v,团二答案：13. 错误例：设A=a,B=a,a)则有AEB且AB.说明：举出符合条件的反例均给分14. 正确因为图G为连通的，且其中每个顶点的度数均为偶数如果具体指出一条欧拉回路也同样给分c(3分）(5分）(7分）(3分）(7分）勹三五、计算题（每小题12分，本题共36分）15设A=l心3),R=工，yI工EA,yEA且工y=4),S=工，yI工EA,yEA且工y，试求R.S.R-1,r(S).16.设图G=,V=们心2,v,v,),=I (v1, v2), (v,v,), (v2,v
24、,)，试(1)画出G 的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的团形17.求,(P VQ) V R的析取范式与主合取范式答案：15. (l)f=i,.,. (I分）(2)关系图(3)渠合B无最大元，极大元为b与c无上界16.解：(1)关系图(8分）(12分）Mii(2)邻接矩阵O 1 0 1 I 1 0 l O 00 1 0 0 1 1 0 0 0 0 I O 1 0 0 (6分）v I (3)deg(v1)=3deg(v2)=2 deg(vl)=2 deg(v,)=1 deg(vs)一2(4)补OO17. P一(Q/R)仁-,PV(Q/R) I J 已
25、(-,PVQ)/(,PVR)合取范式已AC-PVQV勹R)A（勹PV.,QVR)主合取范式(9分）(12分）(2分l(5分）(7分）(9分）(11分）(12分）三六、证明题（本题共8分）18. 试证明：勹PVQP-（勹G PV勹Q).答案：(1)F-Q p (2)P P（附加前提）(3)Q T(1)(2)I (4)P/Q T(2) (3) I (5)-,(-,PV-,Q) T(4)E (6)-,（P-,Q) T(S)E (1分）(2分）(4分）(5分）(6分）(7分）(7)P-+,(P-,Q) CP规则(8分）说明，因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出
26、有效结论得1或2分，最后得出结论得2或1分另可以用艾优表验证题库五一、 单项选择题（每小题3分， 本题共15分）1. 若集合A=l,2,3,4，则下列表述不正确的是（） A. lEAC. 1,2,3EAB.l,2,3CAD. 0竺A2. 若R,和凡是A上的对称关系 ，则 R,UR,R, nR,R,-R.，凡R1中对称关系有（）个A. 1B. 2C. 3D. 43. 设G为连通无向团，则（）时，G中存在欧拉回路A G不存在奇数度数的结点B. G存在偶数度数的结点C. G存在一个奇数度数的结点D. G存在两个奇数度数的结点4. 无向图G是棵树 ， 边 数是 10，则G的结点 度数之和是(). 00
27、 21ACB. 9D. 115.设个体域为整数集，则公式V工3y(x+y=O)的解释可为(). A.存在一整数工有整数y满足工y=OB对任意整数工存在整数y满足工y=OC. 存在一整数工对任意整数y满足工y=OD.任意整数工对任意整数y满足工y=O答案：l. c2. D3. A4. A5.B二、 填空题（每小题3分， 本题共15分）6. 设A=0,2,B=l,2,3)，则A到B上不同的函数个数为7. 有n个结点的无向完全图的边数为8.若无向图G中存在欧拉路但不存在欧拉回路，则G的奇数度数的结点有个9. 设G 是有10个 结点的无 向连通图， 结点的度 数 之 和 为30，则从G 中删去条边后使
28、之变成树10 . 设个体 域0=1,2,3,1)， 则谓词公式(3工）A （.:r）消去贷词后的等值式为答案：6. 97. n(n -1)/2（或 C!)8. 29. 6LO. A(l) V /(2) V /(3) V /(4) 三、 逻辑公式翻译（每小题6分， 本题共12分）11. 将语句“昨天下雨”翻译成命题公式12. 将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式答案：11. 设P：昨天下雨则命题公式为：P.12. 设P：小飞今天上午去石电影Q：小工今天上午去打球则命题公式为：气P.Q).或者(-,P /Q) V (P / -,Q) 四、 判断说明题（判断各题正误， 并说明理
29、由每小题7分， 本题共 14分）13. 存在集合A与B，使得AEB与AB同时成立M 完全图K1是平面图答案：13. 正确例：设A=(a),B=a,al)则有AEB且AB.说明：举出符合条件的例均给分14. 正确完全图此是平面图、如凡可以如下图示嵌人平面五、 计算题（每小题12分， 本题共36分）(2分）(6分）(2分）(fi分(3分）(5分）(7分）(3分）(5分）15. 设偏序梨的哈斯图如下，B为A的子集，其中B=b,c试d b c(1)写出R的关系表达式；(2)画出关系R的关系图；(3)求出B的最大元、极大元、上界16.设图G=,V= v1.v,v,v,vs),= (v1心l),(Vt叩）
30、，（v1.v5),(v,v,),(v3,vs)，试(1)画出G的图形表示；(Z)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形17.求P-+(Q /R)的合取范式与主合取范式答案：15.解：R=, S=, R-1 =,r(S)= , 说明：对于每一个求解项，如果部分正确，可以给对应1分16.解：（l)(3分）(6分）(9分）(12分）VI 0 V3 V4 (3分）(2)邻接矩阵0 l O 1 1 0 0 1 0 0 0 0 1 1 0 0 (6分）(3)deg(v,)=2deg(v1) =2deg(v,)=Odcg(v,)=2(4)补图17. 解：勹(PVQ)VR内台(-
31、,p I-,Q)VR 析取范式台(-,PVR)/(-,QVR)台(-,PVR)V(Q/-,Q)/ (-,QVR) V3 Ov仁(-,PVR)V(Q/-,Q)/(-,QVR)V(P/-,P)仁(-,PV RV Q) / (-,PVRV-,Q)/(-,QVRVP)八(-,QVRV-,P)仁(PV-,QVR)/(-,PVQVR)/(-,PV-,QVR) 六、 证明题（本题共8分）主合取范式18.设A,B是任意集合，试证明：若AXA=BXB，则A=B.答案：设S=AnB-C), T=AnB)一(AnC)，若xES，则xEA 且xEB-C，即xEA，并且xEB 且工(J:C,所以xEAnB)且xe(An
32、C)，得.rET,所以S三T.反之，若.rET，则工E(AnB)且xr/:AnC),即.rEA，工EB，且xr/:C，则得工EB-C,即得xEAn(B-C)，即xES，所以Ts;S.因此T=S.另，可以用恒等式替换的方法证明题库六一、 单项选择题（每小题3分，本题共15分）(9分）(12分）(2分）(3分）(4分）(5分）(6分）(7分）(8分）(5分）(7分）(9分）(10分）(11分）(12 4)-) . 若栠合A=1,2,3,4，则下列表述不正栦的是（） A.2,3EA c.I,2,3,4)竺AB. A!;l,2,3,-1)D.1EA2. 若无向图G的结点度数之和为 20，则G的边数为（
33、） A. 10C. 308.20 D. 53. 无向图G是棵树，结点数为 10，则G的边数为（） A. 5C. 9B. 10D.114设A（工）心是人，B（心：工是学生、则命题有的人是学生“可符号化为（） A勹（V工）（A（工)-+B(工）B. (3心(A(x) / B（工）C. （V工）（A（工） AB（工）D. ., 3工）（A（:r）/ -.B(:r）5.下面的推理正确的是（） A. (l)(V x)F（工）一G（心(2)F(y)-G(y)B. Cl)(3x)F(x）一G（心(2) F(y)-G(y)C. (1)(3心(F(.c）一GC.i:)(2)F(y)-G(x)D. (1)(3心(
34、F（工）-G(:r)(2) F(y)一G(y)答案：I.A2. A 前提引入USO). 前提引人US(1). 前提引入ES(). 前提引入ES(l). 3.C4. B三二、填空题（每小题3分，本题共15分）5. D6. 设集合 A = 1, 2, 3, B = 2, 3, 4, C = 3, 4. 5)，则AU (C - 8)等于7. 设A=2,3,B= I 1,2,C= 3,4，从A到B的函数/=!,，从B到C的函数g=,），贝U Dom(g./)等于 8. 已知图G中共有1个2度结点，2个3度结点，3 个4度结点，则G的边数是 9. 设G是连通平面图，v,e,r分别表示G的结点数，边数和面
35、数，v值为5,e值为4，则r的值为10. 设个体域D= l,2.3,4),A (x)为工大于5”，则谓词公式(V工）A(x)的其值为答案：6. 1,2,3,5)7. 2,3)（或A)8. 10 产三、逻辑公式翻译（每小题6分，本题共12分）11. 将语句“学生的主要任务是学习“翻译成命题公式12. 将语句“今天天晴，昨天下雨翻译成命题公式答案：11. 设P：学生的主要任务是学习则命题公式为：P.12. 设P：今天天晴，Q：昨天下雨则命题公式为：p /IQ.(2分）(6分）(2分）(6分）尸巴四、判断说明题（判断各题正误，井说明理由每小题7分，本题共14分）3.空集的幕集是空集14. 完全图凡不
36、是平面图答案：13. 错误空集的幕集不为空集，为fa.14. 错误完全图凡是平面图，如凡可以如下图示嵌入平面(3分）(7分）(3分）(5分）(7分）尸严五、计算题（每小题12分，本题共36分）15. 设集合A=l,2,3,4上的关系：R=,S=, 试计算(DR S, (2)R一1:(3)r(Rns) 16. 图GV,E，其中V=a,b,c,d,E= (a,b),(a,c),(a,d), (b,c), (b,d),(c,d)，对应边的权值依次为2、3、4、5、6及7，试(1)画出G的图形；(2)写出G的邻接矩阵；(3)求出G权最小的生成树及其权值17. 求P.（0/R)的析取范式与士合取范式答案
37、：15. O)A UB=a,b,c,d);(2)A-B=a;(4分）(8分）(3)A XB= ,) 16.(l)G的图形表示如图一所示：(12分）内/内内图一(3分）(2)邻接矩阵：1010 1101 1010 b111(6分）(3)deg(v,)=3,deg(v2)=2, deg(v,)=3, deg(v,)=2 (4)补图如图二所示：(9分）10 v。二内图二(12分）17. 用Kruskal算法求产生的最小生成树 步骤为；切（v,v,)=l选e,=v,v1w(v,m)选e,=v，叭心(v,v6)=2选e3=v,v,w(v3,m)3 选e,巧叭wtv2,v,)=4远cs=”“w(v.,v,
38、)=5选e,=v5v, 最小生成树如图三所示：(6分）Vd 图三最小生成树的权W(T)=l+1 +2+3+4+5= 16. 说明：用其他方法，结果正确参照给分,113 (9分）(12分）三六、证明题（本题共8分）18. 试证明：7 7 (P-Q)/乡7 RI (Q一R)7 P. 答案：18. 证明：(I).,PVQ p (1分）(2)P p（附加前提）(2分）(3)Q T0)(2)J (4分）(4)P AQ T(2)（3)I (5分）(5)(PVQ) T(4) (6分）(6)-,(P-,Q) T(S)E (7分）(7)P-+., (P-. -.Q) CP规则(8分）说明：因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分另，可以用具值表验证
