资源描述
试卷代号:1009 座位号C口 中央广播电视大学2013一2014学年度第一学期开放本科期未考试(半开卷) 离散数学(本)试题 2014年1月 !题号|一|二|三|四|五|六|总分| |分数II I I I I I I l得分|评卷人| I II一、单项选择题每小题3分，本题共15分 1.若集合A=a，b，c，则下列表述正确的是(). A.aAB. aCA C.0AD.a，b，cA 2.设A=1 , 2 ,B = 1，2，3，4，时，A到B的关系R=(x，YlxA，yB，x+1=y，则 R=( ). A. , B. , c. , D. , 3.元向图G的边数为12，贝tl图G的结点的度数之和是(). A.24 C.6 B. 12 D.18 4.设连通平面图G有U个结点，e条边，r个面，则(). A.v十e-r=2 C. v+e-r=4 B.r+v-e=2 D. v+e-r=-4 5.设个体域D是整数集合，则命题Vx3y(x o y=y)的真值是(). A.不确定B.F CTn以上说法都不是 65 得分|评卷人 二、填空题每小题3分，本题共15分 6.设集合A=l，2，3，B=3，4，时，c=5 , 6,7，则AUB一C等于 7.设A=I，2，B=怡，b，C=3，4，时，从A到B的函数f吉，从B 到C的函数g=，则Ran(gOf)等于 8.若图G=，其中V=a ,b,c,d ,E =(a，的，(a，d)，(b，c)，(b，d)，则该图中的 割边为 9.设G是欧拉图，则G的奇数度数的结点数为一一一一一个. 10.设个体域D=2，4，6，A(x)为x是偶数，则谓词公式(Vx)A(x)的真值 为 |得分|评卷人| I I I 三、逻辑公式翻译每小题6分，本题共12分 11.将语句我学英语，并且学法语翻译成命题公式. 12.将语句除非小王来，否则小李不去翻译成命题公式. |得分|评卷人| I I I 四、判断说明题每小题7分，本题共14分 判断下列各题正误，并说明理由. 13.空集白的事集也是空集. 14.(丑x)(P(x)Q(y)AR(z中的约束变元为y. |得分|评卷人| I I I 五、计算题每小题12分，本题共36分 15.设集合A=l,2, 3,R = , , ,5= ,试 计算z (l)R 5; (2)R- 1 ; (3)r(R). 66 16.图G=，其中V=怡，b，c，d, E= (a ,b) , (a ,c) , (a , d ) , (b , c) ,(c，d)，对应 边的权值依次为6、5、2、3及8，试E (1)画出G的图形s (2)写出G的邻接矩阵z (3)求出G权最小的生成树及其权值. 17.试画一棵带权为1，2，3，3，4的最优二叉树，并计算该最优二叉树的权. |得分|评卷人| I I I 六、证明题本题共8分 18.试证明:PQP(PAQ). 67 试卷代号:1009 中央广播电视大学2013一2014学年度第一学期开放本科期末考试半开卷) 离散数学(本)试题答案及评分标准 (供参考 2014年1月 一、单项选择题每小题3分，本题共15分) l. B 2.D 3.A 4.B 5. C 二、填空题每小题3分，本题共15分 6. 1 ,2 ,3 ,4 7. 3 ,4 8. (h ,c) 9.0 10.真(或T，或1) 三、逻辑公式翻译每小题6分，本题共12分 11.设P:我学英语，也我学法语. 则命题公式为:PI Q. 12.设P:小王来，Q:小李去. 则命题公式为:QP. 或-，P-，Q 四、判断说明题每小题7分，本题共14分 13.错误. 空集的事集为臼. 14.错误. (丑x)(P(x)Q(y)八R(x中的约束变元为x. 五、计算题每小题12分，本题共36分 15. (1)R S=,; 68 (2分 (6分) (2分) (6分 3分 (7分 (3分 (7分 (4分 (2)R- 1 = , , I (3)r(R) = , , , , (8分) (12分 16.(l)G的图形表示如团一所示z d8c吨，由.、-句 3 田、 a J E G6b (3分 图一 (2)邻接矩阵z b 1 1 1 101 0 1 101 1 0 1 0 (6分 (3)图二中的粗线与结点表示的是最小生成树z d8c -、-二 2-3 图 .、气 d E aUAU (10分) 权值为10 17.最优二叉树如图三所示z (12分 13 (10分 2图三 (二叉树树叶权值顺序不同，参照给分 权为1X3十2X3+3X2+3X2+4X2=29(12分) 69 六、证明题本题共8分 18.证明z (l)P Q (2)P (3)Q (4)PAQ (5)P (P A Q) 另证E 设P(P八Q)为F， 则P为T，PAQ为F. 所以P为T，Q为F， 从而P-Q也为F. 所以PQ=争P(P八Q). P P(附加前提 T (l)(2)l T(2)(3)l CP规则 (l分 (3分 (5分 (7分 (8分 (l分 (3分 (5分 (7分 (8分 说明:1.因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公 式得出有效结论得1或2分，最后得出结论得2或1分. 2.可以用真值表验证. 70 试卷代号:1009座位号CD 国家开放大学(中央广播电视大学)2014年春季学期开放本科期末考试 离散数学(本)试题半开卷) 2014年7月 |题号|一|二|三|四|五|六|总分| l分数II I I I I I I |得分|评卷人| 择题(每小题3分，本题共15分) I I I 1.若集合A=怡，b，c，d，则下列表述正确的是(). A.aAR任A C. a,b , c C A D. a ,b, c ,dA 2.设A=2,B = 3,4,5 ，A到B的关系R=怡，y!xA，yB，x=y十1，则R=(). A. 0 B. , C. D. , 3.无向图G是个棵树，边数为12，则G的结点数是(). A.12 B.24 C. ll D.13 4.下面的推理正确的是( A. (1)(丑x)(A(x)B(x前提引人 (2)A(y) B(y) ES(1 ). B. 0) ( 3x)A(x)职工)前提引人 (2)A(y) B(y) US(1 ) . c. (1) (Vx)A(x) B(x) 前提引人 (2)A(y) B(y) US (l ) . D. (1 )(V x )(A ( x ) B ( x 前提引人 (2)A(y) B(x) ES(). 52 5.设A(x):x是人，B(x):x是学生，则命题不是所有人都是学生可符号化为(). A. -, ( 3x)(A(x)八B(x B. -, (Ix ) (A(x) B(x c. -, ( 3x)(A(x)八-，B(x D. ( V x) (A(x) 1B(x |得分|评卷人| I I I 二、填空题每小题3分，本题共15分) 6.设集合A=l, 2, 3 , B = 3,4,5,C=2，3，4，5，则BU(A-C)等 于 7.设A=I ,2，B=怡，剖，C=3，4，从A到B的函数j=，从B到 C的函数g=，则Dom(gOJ)等于 8.两个图同构的必要条件是 9.设G是连通平面图，v，e，r分别表示G的结点数，边数和面数，则v，e和r满足的关系 式 10.设个体域D=l，2，3，则谓词公式(Ix)A(x)消去量词后的等值式 为 三、逻辑公式翻译(每小题6分，本题共12分 11.将语句3大于2或1加1等于2翻译成命题公式. 12.将语句如果明天下雪，我们就去旅游翻译成命题公式. |得分|评卷人| I I I 四、判断说明题每小题7分，本题共14分 判断下列各题正误，并说明理由. 13.若图G中存在汉密尔路，则图G是一个汉密尔顿图. 14.无向图G是树当且仅当元向图G是连通图. 53 |得分|评卷人| I I I 五、计算题每小题12分，本题共36分 15.设A=l, 2,3,4, 5,R = IxA，yA且x-y=3;i, s = IxA， yEA且x+y=3，试求R，S，RS，R寸，r(剖，s(R). 16.设有如图一所示的有向图G=， 图一 数条径路的 句U 为度长的 U 到 U 中G求 A幻 i l l - u 懈 43 0 1 接2100附 3 2 0 O G= 出 A 求知试已咱 i 句 L (3)求G中VI的长度为3的回路条数. 17.求(PVQ)R的析取范式与主合取范式. |得分|评卷人| I I I 六、证明题本题共8分) 18.设A，B，C均为任意集合，试证明:A一(BUC)=(A-B)-C. 54 试卷代号:1009 国家开放大学(中央广播电视大学)2014年春季学期开放本科期未考试 离散数学(本)试题答案及评分标准(半开卷) (供参考) 2014年7月 一、单项选择题(每小题3分，本题共15分 I. e 2.A 3. D 4.A 5. B 二、填空题(每小题3分，本题共15分) 6. l .3. 4. 5 7.1.2或A 8.结点数相等;边数相等;度数相同的结点数相等 9. v-e+r=2 10.A(l)八A(2)八A(3) 三、逻辑公式翻译(每小题6分，本题共12分) 11.设P:3大于2.Q:l加1等于2. 则命题公式为:PVQ. 12.设p.明天下雪.Q:我们就去旅游. 则命题公式为:PQ. 四、判断说明题(每小题7分，本题共14分 13.错误. 反例:如图二中存在汉密尔路，但图G不是一个汉密尔顿图. o 0 图二 (或:按定义有:若图G中存在汉密尔回路，则图G是一个汉密尔顿图.) 说明:举出符合条件的反例均给分. (2分) (6分) (2分 (6分) (3分) (7分) 55 14.错误. 反例:如图三为连通图，但不是树. / 图三 或z按定义有:无向图G是树当且仅当元向图G是元回路的连通图.) 说明:举出符合条件的反例均给分. 五、计算题每小题12分，本题共36分) 15. R= , S=, R S=, R- 1 = , r(S) = , , , , s(R) = , , , . 说明:对于每一个求解项，如果基本求出了解，可以给对应1分. 1 1 1 0 1 010 16.G的邻接矩阵为:A= 000 1 o 0 1 0 (3分) (7分 (2分) (4分 (6分) (8分) (10分) (12分) (4分) (2分) (5分) (7分) (9分) (2)由A 3 中au可知，G中VI到叭的长度为3的路径有2条;(8分) (3)由A 3 中all可知，G中VI的长度为3的回路有3条;(12分) 说明:如果没有求出矩阵乘积，而通过列举找出正确的路与回路数，也给相应分数. 17. (PVQ) R 。-，(PVQ) VR 。(-，P八-，Q)VR析取范式 (-，PVR) A (-,Q VR) 。(-，PVR) V (Q A-，Q)八(-，QVR) 56 。(-，PV R) V (Q 1-，Q)八(-，QVR) V(P八-，P) 。(-，PVRVQ)八(-，PV R V-，Q)八(-，QV R V P) 1 (-,Q V R V -,P ) 。(PV-,Q VR)八(-，PVQVR)八(-，PV-，QVR)主合取范式 六、证明题(本题共8分 18.证明: 设S=A一BUC)，T=(A-B)-C, 若zS，则zA且z任BUC，即zA，并且z任B且xf/:.C， 由zA且Z任B，得zA-B，又由xf/:.C得xE(A-B)-C，即zT， 所以SCT. 反之，若xET，则xE(A-B)且xf/:.C， 由工(A-B)，得zA且xf/:.B，则得xf/:.BUc， 即得zA且xf/:.BUc，即zS， 所以TCS. 因此T=S. (10分) (11分) (12分) (2分) (3分) (4分) (5分) (6分) (7分) (8分) 57 试卷代号:1009座位号E口 80 国家开放大学(中央广播电视大学)2014年秋季学期开放本科期末考试 离散数学(本)试题(半开卷) 2015年1月 E 四五 一、单项选择题每小题3分，本题共15分 1.若集合A=b，c，d，则下列表述正确的是(). A. b，c，dA B.ACc ,d C. b ,c.dCA D.怡，cCA 1 1 0 0 10010 2已知元向图G的邻接矩阵为110 0 1 11，则G有() o 1 101 00110 A.6点，10边B.5点，12边 C.6点，5边D.5点，6边 3.无向图G是个棵树，结点数为10，ltlG的边数是(). A.9 B. 10 C.11 D.12 4.设A(x):x是人，B(x):x是工人，则命题有人是工人可符号化为(). A. ( t/ x) (A(x) B(x) B. ., (1x)(A(x) B(x) c. ( 3 x)(A(x)八B(x)D. ., ( 3 x)(A(x)八.，B(x) 5.下面的推理正确的是( A. (1)(1 x) F(x) G(x) 前提引人B. (1)(1x)(F(x) G(x) (2)F(y) G(y) US (l). (2)F(y) G(y) C. (1)( 3x)F(x) G(x) 前提引人D. (1)( 3x)(F(x) G(x) (2)F(y) G(y) US( 1). (2)F(y) G(x) 前提引人 US( 1). 前提引人 ES(1). |得分|评卷人| | 二、填空题每小题3分，本题共15分 6.设A=怡，b，c,B= 1 ，2，3，作!:AB，则不同的函数个数为一一-一一- 7.任一元向图中，度数为奇数的结点的个数为一一一- 8.设G是汉密尔顿图，5是其结点集的一个子集，若S的元素个数为6，则在G-5中的连 通分支数不超过-一一一 9.设G是有8个结点的连通图，结点的度数之和为28，则可从G中删去条边后 使之变成树. 10.设个体域D=1，2，则谓词公式Cltx)P(x)V (3x)Q(x)消去量词后的等值式 为 |得分l评卷人| | 三、逻辑公式翻译(每小题6分，本题共12分) 11.将语句小张和小李都可以完成这项工作翻译成命题公式. 12.将语句是偶数当且仅当能被2整除翻译成命题公式. 四、判断说明题(每小题7分，本题共14分) 判断下列各题正误，并说明理由. 13.存在集合A与B.使得AB与ACB同时成立. 14.完全图Ks是平面图. 81 五、计算题每小题12分，本题共36分) 15.设A= 2 , 3 , 6 , 12 , 24 , 36 , B为A的子集，其中B=6，12，R是A上的整除关 系，试: (1)写出R的关系表达式; (2)说明R为偏序关系; (3)画出关系R的哈斯图; (4)求出B的最大元素、极大元素、上确界. 16.设图G=，V=Vj巧，V3，叫，V5 , E = ( Vj川2) , (Vj , V3 ) , (V, Vs ) , (屿，V3), (V2，V4)，(V2，V5)(町，V4), ( V3 , Vs ) , (V4 ,V5 ) ，试; (1)画出G的图形表示; (2)写出其邻接矩阵; (3)求出每个结点的度数; . (4)画出图G的补图的图形. 17.求P(Q八R)的合取范式与主合取范式. 六、证明题本题共8分 18.对任意集合A，B和C，若有C手，则有:ACB的充分必要条件是CXACCXB. 82 试卷代号:1009 国家开放大学(中央广播电视大学)2014年秋季学期开放本科期末考试 离散数学(本)试题答案及评分标准(半开卷) (供参考) 一、单项选择题(每小题3分，本题共15分) l. D 2.D 3. A 二、填空题每小题3分，本题共15分 6.27 7.偶数 8.6 9. 7 10. (P(1)八P(2)V (Q(1) VQ(2) 三、逻辑公式翻译每小题6分，本题共12分 4.C 11.设P:小张可以完成这项工作，Q:小李可以完成这项工作. 则命题公式为:P八Q. 12.设P:a是偶数，Q:能被2整除. 则命题公式为:p.-.Q. 四、判断说明题每小题7分，本题共14分) 5. B 2015年1月 (2分 (6分) (2分) (6分 13.正确(3分) 例:设A=叫，B=忡，a(5分 则有AB且ACB.(7分) 说明:举出符合条件的例均给分. 14.错误(3分) 完全图Ks是有5个结点10条边，因3X5-610，即e3v-6对凡不成立(5分) 故凡不是平面图(7分) 五、计算题(每小题12分，本题共36分) 15. (1)因为在集合A=2 , 3 , 6, 12，24，36中，集合A上的整除关系R为: R= , , , , , , , , 83 , , , , , , , , , , . (3分 (2)R中的每个有序对的第一个元素都可以整除第二个元素，即R为整除关系.每个数可 以整除自身，则关系R是自反的; 由R的元素可看出，若z手y，当存在R，就有f!:R，则说明关系R是反 对称的; 由R的元素可看出，若存在ER，R，就有仨R，则说明关系R 是传递的. 84 所以A上的整除关系R为偏序关系. (说明:只要指出了R的自反性、反对称、传递性，即可给分) (3)关系R的哈斯图如图一所示: 24 36 3 2 图一 (4)集合B的最大元素12、极大元素12、上确界为12 16. (1)关系图如图二所示: (2)邻接矩阵 o 1 101 10111 1 101 1 o 1 101 11110 V2 Vl 图二 Vs (6分) (9分) (12分) (3分) (6分) (3)deg(Vl)=3 deg( vz) =4 deg(V3) =4 deg(叫)=3 deg( Vs) =4 (4)补图如图三所示: 17. P(Q八R) 。.，PV(QR) V20 V30 。(.，PVQ)八(.，PVR) 合取范式 。(.，PVQ)V (R八.，R)八(.，PVR) Vl 图二 (.，p V Q) V (R .，R)八(-.PV R) V (Q .,Q) o Vs V4 (.，P V QV R)八(.，PV QV.，R)八(.，PVRVQ)八(.，PV R V .,Q) 。(.，PVQVR)八(.，PV Q V .,R) (., p V .,Q V R) 六、证明题(本题共8分 18.证明z 已知C笋，即存在cC， 设ACB，则对任意CXA，有cC，aA， 可得cC，aEB， 即有CXB， 所以CXACCXB. 再设CXACCXB， 主合取范式 则对任意aA，由ECXA可得CXB， 即有cC，aB， 所以ACB， 得证. (9分 (12分) (2分) (5分) (7分) (9分) (11分) (12分) (1分) (2分) (3分) (4分) (5分) (6分) (7分) (8分) 85
展开阅读全文