国家开放大学电大本科《离散数学》期末试题标准题库及答案（试卷号：1009）

国家开放大学电大本科离散数学期末试题标准题库及答案（试卷号：1009）考试说明.本人汇总了历年来该科的试题及答案，形成了一个完整的标准考试题库，对考生的复习和考 试起肴非常重要的作用，会给您节省大量的时间。内容包含：单项选择题、填空题、逻辑公式翻译、判 断说明题、计算题、证明慕做考题时，利用本文档中的查找工具（Ctrl+F）,把考题中的关键字输到查 找工具的查找内容框内.就可迅速查找到该题答案。本文库还有其他网核、机者及教学考一体化试题答 案，敬请查看。离散数学题库一一、祖选择题（每小题3分，本题共15分）1. 若集合A = 1,2,3,4,则下列表述不正确的是（）.A. 16AB. 1,2,3UAC. （1,2,3AD. 0UA2. 若殆和R,是A上的对称关系，则殆11殆，殆0氏2,殆一殆，殆一殆中对称关系有（个.A. 1B. 2C. 3D. 43. 设G为连通无向图，则（）时,G中存在欧拉回路.,A. G不存在奇数度数的结点B.G存在偶数度数的结点C. G存在一个奇数度数的结点D.G存在两个奇数度数的结点4-无向图G是棵树，边数是10,则G的结点度数之和是（）.A. 20B.9C. 10D.115. 设个体域为整数集，则公式Vx3y（x+y = 0）的解释可为（）.A. 存在一整数工有整数y满足x+y = 0B. 对任意整数z存在整数了满足x+y = 0C. 存在一整数工对任意整数丁满足1+了 = 0得分评卷人6.设果合A =D. 任意整数对任意整数满足x+j=0二、填空题(每小题3分，本题共15分)1, 2, 3), B = (2, 3, 4, C = 3, 4, 5,则 A U (C - B )等于7. 设 A = (2,3,B = U,2),C=(3,4,从 A 到 B 的函数/= ,从 B 到 C 的函数g = (Vl,3,V2,4,则 Dom(go/)等于.8. 已知图G中共有1个2度结点,2个3度结点,3个4度结点，则G的边数是.9-设（；是连通平面图，如e,r分别表示G的结点数，边数和面数，值为5,e值为4,姻r 的值为.-10. 设个体域D = 1,2.3,4.A（x）为大于5”，副谓伺公式（Vx）A（工）的真值为得分评卷人三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“学生的主要任务是学习”翻译成命题公式.12. 将语句“今天天暗，昨天下雨.”翻译成命题公式.得分评卷人四、判断说明题(判断各题正误，并说明理由.每小题7分，本题共14 分)13. 空集的幕集是空集.14. 完全图K,不是平面图.得分评卷人五、计算题(每小题12分，本题共36分)15. 设集合A = (1,2,3,4上的关系：R = ,S = V1,1,V2,2,V3,3, 试计算(1)RS；(2)R-。(3)r(RriS).16. 图 G=VV,E,其中 V=a,6,c,d,E=(a,6),S,c),(a,d),(8,c),(6,d),(c,d),对 应边的权值依次为2、3、4、5、6及7,试(1) 画出G的图形；(2) 写出G的邻接矩阵；(3) 求出G权最小的生成树及其权值.17. 求P-(QAR)的析取范式与主合取范式.得分评卷人六、证明题(本题共8分)18. 试证明门-I (P-*Q) An R A (Q-R)=i P.即答瘀松标准一、单项选择题（每小题3分,本题共15分）I. C2. D3. A4. A二、填空题（每小题3分，本题共15分）6. 1,2,3,57. 2,3）（或 A）8. 109. 110. 假（或F,或0）三、遂辑公式翻译（每小题6分，本题共12分）II. 设P：学生的主要任务是学习.则命题公式为:P.12. 设P：今天天靖，Q：昨天下雨.则命题公式为：PAQ.四、判断说明鹿（每小题7分,本题共14分）13. 错误.空集的停集不为空集，为0.14. 错误.完全图K，V2,3;（2）R- = V2,1,V3,2,V4,3;（3）r（RnS） = ,16. 解：（1）G的图形表示为：（4分）（8分）（12 分）（2）邻接矩阵:（3分）如K,可以如下图示嵌入平面.bill101111011110.（6分）（3）粗线与结点表示的母眼小生成树,（10 分）（12 分）权值为917. 解：P-(QAR)DiPV(QAR) 析取范式(2分)(-, PVQ)A(n PVR)(5 分)(-)PVQ)V(RAr R)A(iP VR)(7 分)PVQ)V(R A)A(VR)V(QAi Q)(9 分)4=(-i PVQVR)A(iPVQV)A(VRVQ)A(VRVrQ)分)(n PVQVR) A(i PVQViR)A(iPViQVR) 主合取范式(12 分)六、证明题（本题共8分）18.证明：(1)-1 -1 (P-Q)P（1分）(2)P-*QT(1)E（3分）(QR)P(4分)(4)n RP（5分）1 QT(3)(4)Z（6分）(6)-| PT(2)(5)I(8分)说明：（1）因证明过程中.公式引用的次序可以不同，-般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分.（2）另，可以用真值表验证.高帔学题库二一、单项选择蛆（每小题3分，本题共16分）1. 若集合A = 1,2,3,则下列表述正确的是).A. 1,2,3AB.人U(1,2)C. U,2,3UAD. 1,2A2. 设 A = (1,2,3),B = (1,2,3,4,A 到 B 的关系 K = ( |x A ,y 6 B,则 R* ).A. (,)B. ,C.C. ,3. 无向图G的边数是10,则图G的结点度数之和为()A. 10B. 20C. 30D. 54. 如图一所示，以下说法正确的是()A. e是割点B. a,e)是点割集G b,e是点割集D. d是点割集5-设个体域为整数集,则公式V x3y(.x+y = 2)的解释可为().A. 任意整数工.对任意整数v淌足x+y = 2B. 对任意整数了，存在整数y满足工+y=2C. 存在一整数工，对任意整数y满足+了 = 2D. 存在一整数工,有整数丁满足工+ = 2得分评卷人二、填空题(每小题3分，本霆共15分)6. 设集合 A = a,6,c,B = 5,3,C=c,d,则 ACI(BUC)等于.7. 设 A = 1,2,B = (2,3),C=3,4,从 A 到 B 的函数/= (,从 B到 C 的函数& = V2,3,V3,4,则 Ran(go/)等于.8. 设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6,则在G-S中的连通分支数不超过.9. 设G是有8个结点的连通图，结点的度数之和为24,则可从G中删去条边后使之变成树.10. 设个体域D = 1,2, 3, 4),则谓词公式(V工)AS )消去最词后的等值式为评卷人三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“昨天下雨，今天仍然下雨.”翻译成命题公式.四、判断说明题(判断各题正误，并说明理由.每小题7分，本题共14 分)12. 将语句“我们下午2点或者去礼堂看电影或者去教室看书.”翻译成命题公式. 得分评卷人13. 不存在集合人与B,使得AGB与AUB同时成立.14. 如图二所示的图G存在一条欧拉回路.评卷人五、计算题(每小题12分，本题共36分)15. 设 A = l,2,3),R = |x6A,yGA 且+=4,，= 工，3|工人点人且 工=),试求 R,S,RT r(S).16. 设图 G = VV,E,V=s ,v2,v3i ,E = (.vt ,q),(s(v2 ,v4),试(1) 画出G的图形表示；(2) 写出其邻接矩阵；(3求出每个结点的度数；(4) 画出图G的补图的图形17. 求-I (PVQ)VR的析取范式与主合取范式评卷人六、证明题(本题共8分)18. 试证明：i PVQP-a(i (n PViQ).(仅 一、单项选择题(每小题3分，本题共15分)1.C2. D3. B二、填空题(每小题3分，本霆共15分)6. b,c)7. 3,4）（或 C）8.69.510. A（1）AA（2） AA（3） AA（4）三、逻辑公式翻译（每小题6分，本题共12分）11. 设P：昨天下雨,Q：今天下雨.（2分）则命题公式为:FAQ.（6分12. 设P：我们下午2点去礼堂看电影，Q：我们下午2点去教室看书.（2分）则命题公式为门（P-Q）.（6分）注:或者（1 PAQ）V（PA-i Q）四、判断说明题（每小题7分，本题共14分）13. 错误（3分）例:设 A =（5 分）则有AGB且AUB.（7分）说明:举出符合条件的反例均给分.14. 正确.（3分）因为图G为连通的，且其中每个顶点的度数均为偶数.（7分）如果具体指出一条欧拉回路也同样给分.五、计算题（每小题12分，本题共36分）15. 解：R = V1.3,V2,2,V3,1（3分）S = ,（6分）RT = （V3,1,V2,2，V1,3（9分）r（S）=（,（12分）说明：对于每一个求解项，如果部分正确，可以给对应1分16.解：aV（2）邻接矩阵（3分）0 1o r1 00 1（6分）0 00 010 0(3)deg(vi ) = 2deg(为 2)= 2deg(v3)=0deg(v4) = 2(4)补图（9分）（12 分）17. 解：i (PVQ)VR(-)PAn Q)VK 析取范式(5分)0(1 PVR)A(i QVR)(7 分)(-i PVR)V(QAi Q)A(n QVR)(9分)0(r PVK)V(QA-i Q) An QVR)V(PAi P)(10 分)吕()PVR VQ)A(PVR Vi Q)A(i QVR VP) A(i QVR Vi P) (11 分) 0(PVr QVR)A(i PVQVR)A(r PVi QVR)主合取范式(12 分)六、证明题(本题共8分)18. 证明：(Di PVQP(1 分)(2) PP(附加前提)(3分)(3) QT(l)(2)7(5 分)(4) PAQT(2)(3)/(6 分)(5) -i (-1 PV-iQ)T(4)E(7 分)(6) P!(i PVn Q) CP 规则(8 分)说明：（D因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个 公式得出有效结论得1或2分，最后得出结论得2或1分.（2）可以用真值表验证.采用反证法可参照给分.高帔学题库三一、单项选择题（每小题3分，本题共16分）1.若集合A = 1,2,3,4,姻下列表述不正确的是()A. 2,3人& AC1,2,3,4GU,2,3,4)QAD. 16A2.若无向图G的结点度数之和为20,则G的边数为().A. 10B. 20C. 30D.53.无向图G是棵树，结点数为10,则G的边数为().A. 5B. 10C.9D. 114. 设A(x)：x是人是学生，则命题“有的人是学生”可符号化为()A. Vx)(A(x)-*B(x)B. (3x)(A(x)AB(x)C. (Vx)(A(x)AB(xD. -(3x)(A(x)A5. 下面的推理正确的是().A. (VKCr)fGCr)(2)F()-*G(y)B. (l)(3x)F(x)-G(x)(2)F(y)-G(y)C. (l)(3x)(F(x)-G(x)(2)F()G(x)D. (l)(3x)(F(x)-*G(x(2)F)-*G(力前提引入US.前提引入US.前提引入 ES.前提引入ES(1).二、填空题(每小题3分，本题共15分)6. 设A = 1,2),B = 的哈斯图如下，B为A的子集，其中B = 8,c,试(】)写出R的关系表达式；(2) 画出关系R的关系图；(3) 求出B的最大元、极大元、上界.16. 设图 G = VV,E,V=3),力2，0“。4，fs，E = (0，%)，32Vj) (vj !$)试(1) 画出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出图G的补图的图形.17. 求PTQ R)的合取范式与主合取范式.六、证明题(本题共8分)18. 设人.B是任意集合,演证明：若AXA = BXB!J A = B.答案及松标准(仅一、单项选择题(每小题3分，本题共15分)1. A2. A3. C4. B5. D二、填空题(每小题3分，本题共15分)6.97.n(n-l)/2(或 Cf)8.2（2分）（6分）（2分）（6分）（3分）（5分）（7分）（3分）（5分）10. A VA(2) VA(3) VA三、逻辑公式翻译（每小题6分，本题共12分）11. 设P：昨天下雨.则命题公式为:P.12. 设P：小王今天上午去宥电影Q：小王今天上午去打球则命题公式为：r（P Q）,或者（rp AQ）V（P A rQ）四、判断说明题（每小题7分，本题共14分）13. 正确.例：设 =则有且ACB.说明,举出符合条件的例均给分.14. 正确.完全图K,是平面图.如K,可以如下图示嵌入平面.(7分)五、计算题(每小题12分，