国家开放大学电大本科《离散数学》期末试题及答案四套（试卷号：1009）.pdf

1、国家开放大学电大本科离散数学2030-2031期末试题及答案（试卷号：1009)一、 单项选择题（每小题3分， 本题共15分）1. 若集合A=1,2,3,4,B= (1,3,5)，则下列表述正确的是（） A. A=BB. BCAC. B-:;cAD. BA2. 设A=(l心3),8=2,4,6),A到B的关系R= （位，y|红y)，则R=(). A. ,)B. (,C. (,D. ,3. 无向图G 是棵树，边数是 10，则G 的结点度数之和是（） A. 20B. 9C. 10D. 114. 下面的推理正确的是（） A. (1)(/x)F（工）一(G（工）(2)F(y)一Gy)B. (1)(3工

2、）F(x)-G(x)(2)F(y)一G(y)C. (1)(3:x）（F(:x）一G(x)前提引入USO). 前提引人USO). 前提引人(2)F(y)一G（工）ES(l).D. (l) (t/工）（F（心一G（心）前提引入(2)F(y)一G(y)US(l). 5. 设个体域为整数集，则公式Vx3y(工+y=2)的解释可为（） A.任一整数工，对任意整数y满足工y2B.对任一整数工，存在整数y满足工y=2C. 存在一整数工，对任意整数y满足工y2D. 存在一整数工，有整数y满足工y=2答案：1.c2. D3. A4. D5. B三二、填空题（每小题3分，本题共15分）6. 设栠合A=a,b,c)

3、,B= b,c),C=c,d)，则 An(BUC)等千7. 设A=l,2,B=2,3,C= 3,4)，从A到B的函数f=,），从B到C 的函数g=,，则Ran(g。f)等千8设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为 6，则在G-S中的连通分支数不超过9.设C是打8 个结点的连通图结点的度数之和为21，则可从G中删去条边后使之变成树，10.设个体域D=(l.2.3.4)，则诩词公式(V:r）A （工）悄去几词后的等伉式为答案：6. b,c)7. (3,4)（或C)8.69. 510. A (1) /A (2) /A (3) / A (4)得 分1评卷人三、逻辑公式翻译（每小题6

4、分，本题共12分）11.将语句“昨天下市，今天仍然下雨“翻译成命题公式12.将语句“我们下午2点或者去礼堂石电影或者去教室丑书“翻译戍命眨公寸答案：I I.设P：昨天下甫，Q：今天下雨(2分）则命题公式为：PAQ.(6分）12.设P：我们下午2点去礼堂行电影，Q：我们下午2点去教室刀书(2分）则命题公式为：7 (P.Q).(6分）注：或行(, pQ)V(P, Q) 得 分1评卷人四、判断说明题（判断各题正误，并说明理由每小题7分，本题共14分）13.不存在集合A与B，使得AEB与AB同时成立14.如图二所示的图G存在一条欧拉回路内答案：13.错误例：设A=a,B=a,a则有AEB且AB.说明毋

5、出符合条件的反例均给分，5 d I n I C 图二(3分）(5分）(7分）14. 正确因为图G为连通的，且其中每个顶点的度数均为偶数如果具体指出一条欧拉回路也同样给分三五、计算题（每小题12分，本题共36分）15. 设A=l,2,3),R=工，yI工EA,yEA且工y=4,S=工，yI工EA,yEA且(3分）(7分）工外，试求R,s,R-1,r(S).16. 设图G=,V=v1,Vt,v,v,),E= (v,v,),(v,v心(v,v,)，试(1)画出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形17.求,(PVQ)VR的析取范式与主合取范式答案：）

6、 15. O)R=l,.,P一(7 G PV7 Q)） 答案：(1)F一Qp (1分）(Z)P P（附加前提）(2分）(3)Q T(l)(2)! (4分）(4)PAQ T(2) (3) I (5分）(5)-,（-,PV-,Q) T(4)E (6分）(6)-i(P-iQ) T(S)E (7分）(7)P-+-,（P-.,Q) CP规则(8分）说明：因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分另，可以用艾值表验证国家开放大学电大本科离散数学2028-2029期末试题及答案（试卷号：1009)一、 单项选择题（每小题3分， 本

7、题共15分）1.若集合A=l,2,3,4，则下列表述不正确的是（） A. lEAC. l,2,3EAB. 1,2,3CAD. 0竺A2. 若R1和凡是A上的对称关系，则R,UR,R巾R2tK-R2,R2-R1中对称关系有（）个A. 1C.3B. 2D. 4 3. 设G为连通无向团，则（）时，G中存在欧拉回路A. G不存在奇数度数的结点B. G存在偶数度数的结点C. G存在一个奇数度数的结点D. G存在两个奇数度数的结点4. 无向图G是棵树 ，边数是10，则G的结点度数之和是（） A. 20 c.10B. 9D. 115.设个体域为整数集，则公式V工3y(.x+y=O)的解释可为（） A.存在一

8、整数工有整数y满足工y=OB对任意整数工存在整数y满足工y=OC. 存在一整数工对任意整数y满足工y=OD.任意整数工对任意整数y满足工y=O答案：1.C2.D3. A4. A二、 填空题（每小题3分， 本题共15分）6. 设A=l,2,B=l,2,3)，则A到B上不同的函数个数为7. 有n个结点的无向完全图的边数为5.B8.若无向图G中存在欧拉路但不存在欧拉回路，则G的奇数度数的结点有个9. 设G是有10个结点的 无 向连通图，结点的度 数 之 和 为30，则从G中删去条边后使之变成树JO. 设个体 域D=l.2,3,1)，则谓词公式(3工）A （.:r）消去犹词后的等值式为答案：6. 97

9、.11(11-1)/2（或CD8. 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) 四、 判断说明题（判断各题正误， 并说明理由每小题7分， 本题共 14分）13. 存在集合A与B，使得AEB与AB同时成立M 完全图K1是平面图答案：13. 正确例：

10、设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叩），（v1.v5),(v,v,),(v3,vs)，试(1)画出G的图形表示；(Z)写出其邻接矩阵；(3)求出每个结点的度数；(

11、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台,PA,Q)VR内析取范式台(-,PVR)/(-,QVR)台(-,PVR)V(Q/-,Q)/ (-,QVR) V3 Ov仁(-,P

12、VR)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(AnC)，得.rET,所以S三T.反之，若.rET，则工E(AnB)且xr/:AnC),即.rEA，工EB，且xr/:C，则得工EB-C,即得

13、xEAn(B-C)，即xES，所以Ts;S.因此T=S.另，可以用恒等式替换的方法证明(9分）(12分）(2分）(3分）(4分）(5分）(6分）(7分）(8分）(5分）(7分）(9分）(10分）(11分）(12 4)-) 国家开放大学电大本科离散数学2024-2025期末试题及答案（试卷号：1009)一、 单项选择题（每小题3分， 本题共15分）1. 设A=O,3,5,7,9,B=2,4,6),A到B的关系R=I.r一y=)则R=（） A. ,8. ,C. ,D. ,2. 若集合A=a,b,c，则下列表述正确的是（） A. a,b竺A8. aEAC. a,bEAD.0EA3. 设个体域为集合1

14、,2,3,4,5)，则公式(V.r）（3y) ( .ry=5)的解释可为（） A. 存在一整数工有整数y满足工y=5B 对任一整数工存在整数y满足工y=Sc.存在一整数工对任意整数y满足工y=SD.任一整数工对任意整数y满足工y54. 设G为连通无向图，则（）时，G中存在欧拉回路A.G存在两个奇数度数的结点B.G存在一个奇数度数的结点C.G不存在奇数度数的结点D.G存在偶数度数的结点5. n阶无向完全图K同的边数及每个结点的度数分别是（） A. n(n-1)与nC.n-1 与n答案：1.D三2. A3.8 B. n(n-1 )/2与n-1D. n(n-l)与n-14. C二、填空题（每小题3分

15、，本题共15分）6. 设集合A=工肛是小于4的正整数），用集合的列举法A=5. B7. 设A= 1,2),B= a,b),C= I,2)，从A到B的函数/= ,），从B到C的函数g= . )，则复合函数g.J=8. 设G=是一个图，结点度数之和为30，则G的边数为9. 设G是具有n个结点m条边k个面的连通平面图，则n+k-2=IO. 设个体域D=2,3,4),A(:r;）为飞小于3”，则谓词公式CVx)A（立的真值为答案：6. ,2,37. ,)8. 159.m10. 假（或F，或0)三三、逻辑公式翻译（每小题6分，本题共12分）11. 将语句“如果今天下雨，那么明天的比赛就要延期“翻译成命题

16、公式12. 将语句“地球是圆的，太阳也是圆的“翻译成命题公式答案：11. 设P：今天下雨，Q：明天的比赛就要延期则命题公式为：P一Q.12. 设P:地球是圆的，Q：太阳是圆的则命题公式为：PAQ.(2分）(6分）(2分）(6分）三四、判断说明题（判断各题正误，井说明理由每小题7分，本题共14分）13. 设A=a心c,d),R=,)，则R是等价关系H. (V.x)(P(.x) / Q(y)-R(.x)中量词V的辖域为(P(工)/Q(y).答案：13. 错误R不是等价关系，因R 中不含，故不满足自反性14 正确辖域为紧接扭词V之后的最小子公式（P（心AQ(y).三五、计算题（每小题12分，本题共3

17、6分）15. 设集合A=a,b,c,B=b,c,d，试计算O)AUB;(Z)A-81 (3)AXB.(3分）(7分）(3分）(7分）16. 设G=,V=v1,v,，巧，v,E= (v1,vi), (v1,v,), (v,v,), (vi,v,),(v1,v)，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形17. 试利用Kruskal算法求出如下所示赋权图中的娘小生成树（妥求与出求隅步骤），开求此最小生成树的权V6 ,V3 8 答案：15. 解：（l)R S=, 1(2)R-I =,;(3)r(R ns= ,)16. 解：（l)G的图形表示为：4

18、万丿(8分）(12分）(3分）(2)邻接矩阵：1110 l101 lOll 0111 -(6分）(3)粗线与结点表示的是最小生成树，(10分）b 5 权值为9(12分）17. 解：P-QAR)臼，PV(QAR) 析取范式台, PVQ)A, PVR) 仁(, P V Q) V (R A, R) A , P V R) 仁, PVQ)V(RA, R)A(, PVR)VCQA, Q) 己, PVQVR)A, PVQV, R)A, PVRVQ)AC, PVRV, Q)仁(7 PVQVR)Ah PVQV7 R)Ah PV7 QVR) 巨尸六、证明题（本题共8分）答案：18.试证明,P-+-QP-(P-+-

19、,Q).18.证明：(l)7 P VQ(2)P (3)Q (4)P/Q (Shh PV7 Q) p P（附加前提）T(1)(2)/ T(2)(3) / T(4)E 主合取范式(2分）(5分）(7分）(9分）(11分）(12分）(1分）(3分）(5分）(6分）(7分）(6)P一7 h PV7 Q) CP规则(8分）说明：（1）因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分(2)可以用其值表验证 采用反证法可参照给分国家开放大学电大本科离散数学2022-2023期末试题及答案（试卷号：1009)一、 单项选择题（每小题3分，

20、 本题共15分）1. 若集合A=1,2,3，则下列表述正确的是(). A. ,2,3EAC. 1,2,3竺AB. ACl,2D. l,2EA2. 设A= (l.2,3), B = (l,2,3,4,A到B的关系R=I.xEA,yEB，工y),则R=() .A. ,B. (,c.,)D. ,3. 无向图G的边数是10，则图G的结点度数之和为（） A. 10c.304. 如图一所示，以下说法正确的是（A. e是割点B. 位，e)是点割集C. b,e)是点割集D. d)是点割集5. 设个体域为整数集，则公式V工3y(x+y=2)的解释可为（） A. 任意整数工，对任意整数y满足工y=2B.对任意整数

21、工，存在整数y满足工y=2c.存在一整数工，对任意整数y满足工y=2D. 存在一整数工，有整数y满足工y2B. 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，则BUA -C)等于7. 设A= (1,2,B = 2,3,C= 3,4)，从A到B的函数f=,，从B到C的函数g=,，则Ran(g寸）等于8. 两个图同构的必要条件包括结点数相等、边数相等与9. 设G是连通平面图，v,e,r分别表示G的结点数， 边数和面数，v 值为5,e 值为4则r的值为10. 设个

22、体域D=l.2,3,4)，则谓词公式(3心A（工）消去量词后的等值式为答案：6. 1,2,3,47. 3,4度数相同的结点数相等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.（或飞-P)(6分）四、 判断说明题（判断各题正误， 并说明理由， 每小题7分 本题共14分

23、）13.若图G是一个欧拉图，则图G 中存在欧拉路14. 无向图G的结点数比边数多1，则G是树答案：13. 正确因为若图G是一个欧拉图，则图中存在欧拉回路按定义知，欧拉回路也是欧拉路14. 错误反例：如图G的结点数比边数多1，但不是树乙五、 计算题（每小题12分， 本题共36分）15. 设集合A=l,Z,3,4)上的关系：R= ,),S=,), 试计算(l)RS1(2)R-; (3)rRns). (3分）(5分）(7分）(3分）16. 图G=，其 中V= a, b, c, d), E = (a, b), (a, c), (a, d), (b, c), (b,d),(c,d)），对应边的权值依次为

24、1、1、5、2、3 及4，请画出G的图形、写出G的邻接矩阵井求出G权朵小的生成树及其权值17. 求勹(PVQ)VR的析取范式与主合取范式答案：15. (l)A UB= (a,b,c,d;(2)A-B=c,d; (4分）(8分）(3)A XB=,(12分）16. (I)G的图形表示如图一所示：VI I;? 图一(2)邻接矩阵：-0 1 1 1 0 l0 lI O ll O l 0(3)deg(v1)=3, deg(v2) =2, deg(v,) =3, deg(v,)=2 (4)补图如图二所示：10v图二17.用Kruskal算法求产生的最小生成树步骤为：心（v,v,)=l，选e,=v,v,w(

25、v.,v,)=3，选e2=v,v,w(v1,v,)=4选e3=v,v, 心(Vs,v,)=9，选e,=v,v, w(v,v,)=18，选es=v.Vsw(v,v,)=22，选e,=v,v,V4 (3分）(6分）(9分）V2 (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，则有rEB,因此A巨B.设xEB，则x，工EBXB,因AXA=BXB，故r,.rEAXA，则有工EA，因此B竺A.故得A=B.(9分）(12分）(l分）(3分）(5分）(6分）(7分）(8分）