试卷代号：1009 座位■口 中央广播电视大学2011一2012学年度第一学期“开放本科”期末考试（半开卷） 离散数学（本）试题 2012年1月 题 号 二 三 四 五 六 总分 分 数 得 分 评卷人 一、单项选择题（每小题3分，本题共15分） 1.若集合A的元素个数为10，则其幂集的元素个数为(). A.10 B.100 C.1024 D.1 2.设A={a,b},B={1,2},R1,R2,R3是A到B的二元关系，且R={<a,2>,<a,1>}, R2={<a,1>,<a,2>,<b,1>),R=(<a,1>,<b,2>},则( )是从A到B的函数 A.R1和R2 B.R2 C.R, D.R,和R 3.设A={1,2,3,4,5,6,7,8},R是A上的整除关系，B一{2,4,6}，则集合B的最大元、 最小元、上界、下界依次为(). A.8、2、8、2 B.无、2、无、2 C.6、2、6、2 D.8、1、6、1 4.若完全图G中有n个结点(n≥2)，m条边，则当( )时，图G中存在欧拉回路， A.n为奇数 B.n为偶数 C.m为奇数 D.m为偶数 67
试卷代号 9座位号 中央广播电视大学 11 2学年度第一学期"开放本科"期末考试(半开卷) 离散数学(本)试题 2012 年1 |题号|一|二|三 l四|五|六|总分| |分数 I I I I I I I 题{每小题 3分，本题共 5分) I I I 1.若集合 A的元素个数为 0，则其幕集的元素个数为( A.10 B. 100 C. 1024 D. 1 2. {1 ，2} 且R ={<a,2>,<a,1>} , Rz= {<a ，1> ，<a ，2> ，<b ，1>} 凡={<a ，1> ，<b ，2>} )是从 A.R 和R C. R3 B.Rz D.R 和R 3. R是 A上的整除关系 {2 ，4 ，6} 合B 最小元、上界、下界依次为( ). A.8 、2 ，8 、2 C. U8 、1 、6 、1 4. 图G 个结 三~2) )时，图 G中存在欧拉回路. A.n C.m 为奇数D.m 偶数 67
5.已知图G的邻接矩阵为 (0001 1) 0 0001 0 0011 1 0101 1 1110 则G有(). A.6点，8边 B.6点，6边 C.5点，8边 D.5点，6边 得 分 评卷人 二、填空题（每小题3分，本题共15分） 6.设集合A={a},那么集合A的幂集是 7.若R:和R2是A上的对称关系，则R1UR,R1∩R2,R1一R2,R2一R,中对称关系有 个 8.设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去 条边后 使之变成树. 9.设连通平面图G的结点数为5，边数为6，则面数为 10.设个体域D={a,b},则谓词公式(Vx)(A(x)∧B(x))消去量词后的等值式为 得分 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“今天有联欢活动，明天有文艺晚会.”翻译成命题公式. 12.将语句“如果小王来，则小李去.”翻译成命题公式. 68
5. 图G 邻接矩阵为 00011 o 000 1 00011 1 0 1 0 1 1 1 1 1 0 ). A.6 ，8 C.5 ，8 |得分|评卷人| I I I B.6 ，6 D.5 ，6 二、填空题(每小题 3分，本题共 5分} 6. 集合 合A 事集 7. 是A 对称关 则R URz ,Rl n 对称 个. 8. 图G 有5 点度 总和为10 从G 删去 使之变成树. 9. 连通平 图G 为5 为6 则 面 10. 设个体域D= {a 则 谓 词 Vx) (A (x) (x)) 去 量 词 后 得分|评卷人 三、逻辑公式翻译(每小题6分，本题共 2分) 1. 将语 联欢 天有 艺 晚 题公 12. 小李 68
得分 评卷人 四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由· 13.若偏序集<A,R>的哈斯图如图一所示，则集合A的最大元为a,极小元不存在. a 图一 14.P∧(P+Q)VP为永假式. 分 评卷人 五、计算题（每小题12分，本题共36分）】 15.设集合A=(1,2,3,4},R={<x,y>|x,y∈A;x-yl=1或x-y=0),试 (1)写出R的有序对表示； (2)画出R的关系图； (3)说明R满足自反性，不满足传递性， 16.设图G=<V,E>,V={1,2,,v4,5},E={(1,2),(U1,3),(v2,4),(3,5), (4,5)},试 (1)画出G的图形表示； (2)写出其邻接矩阵； (3)求出每个结点的度数； (4)画出图G的补图的图形 17.求P→Q∧R的合取范式与主析取范式. 得 分 评卷人 六、证明题（本题共8分） 18.设连通无向图G有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3， 试说明G中可能有的顶点数. 69
|得分|评卷人| I I I 四、判断说明题{每小题 7分，本题共 14分) 判断下列各题正误，并说明理由. 13. 偏序集 一所 合A 大元 极小元 存在 /气 14. -, P A (P -，Q)VP 永假 |得分|评卷人| I I I 五、计算题{每小题 2分，本题共 6分} 15. 合A= {l ，2 ，3 yεA =1 或x-y=O} (1)写出 R的有序对表示; (2) 出R (3) 明R 满足 不满足传 16. 't } , E = {(VI' Vz ) , (VI' V3 ) , (吨 (叫， , (叭， ，试 (1)画出 G的图形表示 (2) 邻接 (3) (4) 图G 17. 求P 八R 合取 析取范 |得分|评卷人| I I I 六、证明题{本题共 8分) 18. 通无 图G 有14 ，3 个4 ，4 个3 于3 试说明 G中可能有的顶点数. 69
试卷代号：1009 中央广播电视大学2011一2012学年度第一学期“开放本科”期末考试（半开卷） 离散数学（本）试题答案及评分标准 (供参考) 2012年1月 一、单项选择题（每小题3分，本题共15分】 1.C 2.C 3.B 4.A 5.D 二、填空题（每小题3分，本题共15分）】 6.{,{a} 7.4 8.1 9.3 10.(A(a)AB(6))∧(A(a)B(b) 三、逻辑公式翻译（每小题6分，本题共12分） 11.设P:今天有联欢活动，Q:明天有文艺晚会， (2分) P∧Q. (6分) 12.设P:小王来，Q:小李去 (2分) P→Q (6分) 四、判断说明题（每小题7分，本题共14分）】 13.错误. (3分) 对于集合A的任意元素x,均有<x,a>∈R(或xRa),所以a是集合A中的最大元.(5分) 但按照极小元的定义，在集合A中b,c,d均是极小元. (7分) 14.错误， (3分) PA(P→nQ)VP是由PA(P+Q)与P组成的析取式， 如果P的值为真，则PA(P一Q)VP为真， (5分) 如果P的值为假，则P与P+Q为真，即P∧(P·Q)为真， 70
试卷代号 0 0 中央广播电视大学 2 0 11 2 0 2学年度第一学期"开放本科"期末考试(半开卷) 离散数学(本)试题答案及评分标准 (供参考〉 2012 年1 -、单项选择题{每小题 3分，本题共 5分} I. C 2.C 3. B 4.A 5.0 二、填空题{每小题3分.本题共 5分} 6. {正当 {a}} 7.4 8.1 9.3 10. (A(a) 八B(b» 八(A(a) 八B(b» 三、逻辑公式翻译{每小题 6分，本题共 2分} 1. 天有联欢 12. 小李 P• Q. (2 (6 (2 (6 四、判断说明题{每小题 7分，本题共 14分} 13. (3 对于集合 A的任意元素工，均有 ε R ，所以 a是集合 A中的最大元. (5 但按照极小元的定义，在集合 A中 d均是极小元. (7 14. (3 ""PA (P•""Q) V 由""PA (P "" 与P 如果 为真 ...， "" (5 如果 ...， "" ...， "" 70
也即PA(PQ)VP为真， (7分) 所以一PA(P+Q)VP是永真式 另种说明： 一P∧(P+Q)VP是由一P∧(P+一Q)与P组成的析取式， 只要其中一项为真，则整个公式为真， (5分) 可以看到，不论P的值为真或为假，一P∧(P→一Q)与P总有一个为真， 所以P∧(P→Q)VP是永真式， (7分) 或用等价演算P∧(P+Q)VP台T 五、计算题（每小题12分，本题共36分） 15.(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>, <3,4>,<4,3>} (3分) (2)关系图如图二： 图二 (6分) (3)因为<1,1>，<2,2>，<3,3>，<4,4>均属于R,即A的每个元素构成的有序对均 在R中，故R在A上是自反的. (9分) 因有<2,3>与<3,4>属于R,但<2,4>不属于R,所以R在A上不是传递的.(12分) 16.(1)关系图如图三： 图三 (3分】 (2)邻接矩阵 71
也即 "" "" P为真. (7 所以 "" (P• ""Q) V 是永 另种说明 ""PA(P→""Q)VP 由""PA(P→""Q) 取式 只要其中一项为真，则整个公式为真. (5 可以看到，不论 P的值为真或为假 ""PA (P→""Q) 总有一 所以 ...， "" P是永真式. (7 或用等价演算"" "" 五、计算题{每小题 2分，本题共 6分) 15. (l)R = {<1.1>.<2.2> .<3.3>.<4.4>.<1.2>.<2.1>.<2. 3> .<3 ,2>. <3.4>.<4.3>} (2) 系 图 (3 图二二 (3) 为<1 ，1>.<2.2>.<3.3>.<4.4> 即A 构成 R中，故 R在 A上是自反的. (9 因有 >与 3， >属于 ，但 >不属于 .所以 R在A上不是传递的. (1 2分) 16. (1)关系图如图三 V2 (2) 图三 V4 Vs (3 71