试卷代号：1009 座位号☐ 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试（半开卷） 离散数学（本）试题 2009年7月 题 号 三 四 五 六 总 分 分数 得 分 评卷人 一、单项选择题（每小题3分，本题共15分）】 1.若集合A={a,b},B={a,b,{a,b}},则(). A.ACB,且A∈B B.A∈B,但A亡B C.ACB,但A任B D.A在B,且A在B 2.集合A={1,2,3,4,5,6,7,8}上的关系R={|x+y=10且x,y∈A},则 R的性质为(). A.自反的 B.对称的 C.传递且对称的 D.反自反且传递的 3.如果R和R2是A上的自反关系，则RUR2,R∩R2,R一R2中自反关系有()个. A.0 B.2 C.1 D.3 4.如图一所示，以下说法正确的是(). A.{(a,e)}是割边 d B.{(a,e)}是边割集 C.{(a,e),(b,c)}是边割集 D.{(d,e)}是边割集 图一 66
试卷代号:1009 座位号口一习 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试(半开卷) 离散数学(本) 试题 2009年 7月 题 号 四 五 、 /、 总 分 分 数 得 分 评卷人 一、单项选择题(每小题 3分，本题共 15分〕 1，若集合 A=天a,b} ,B=戈a,b,互a,b}}，则( ) A. ACB，且 A任B C. ACB，但 A任B B. AC- B，但 A敏B D. A敏B，且 A任B 2.集合 A=}1, 2, 3, 4, 5, 6, 7, 8)上的关系 R=(<二，y% I x十y=10且 x, yGA)，则 尺的性质为( )， A.自反的 C.传递且对称的 B.对称的 D，反自反且传递的 3.如果 R,和凡 是 A上的自反关系，则 R, UR2,Rl门凡 ,R, -R2中自反关系有( )个 A.0 C. 1 4.如图一所示，以下说法正确的是 ( A. { (a, e)}是割边 B. { (a, e)}是边割集 C. {(a, e) ,(b,‘)}是边割集 一D. {(d,。)}是边割集 B. 2 D. 3 图 一
5.设A(x):x是人，B(x):x是学生，则命题“不是所有人都是学生”可符号化为(). A.(Vx)(A(x)∧B(x) B.(3)(A(x)AB(x)) C.(Hx)(A(x)→B(x) D.(3x)(A(x)∧B(x) 得分 评卷人 二、填空题（每小题3分，本题共15分）】 6.若集合A的元素个数为10，则其幂集的元素个数为 7.设A={a,b,c},B={1,2},作f:A→B,则不同的函数个数为 8.若A={1,2},R={|x∈A,y∈A,x+y=10},则R的自反闭包为 9,结点数v与边数e满足 关系的无向连通图就是树： 10.设个体域D={a,b,c},则谓词公式(Hx)A(x)消去量词后的等值式为 得分 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“尽管他接受了这个任务，但他没有完成好.”翻译成命题公式 12.将语句“今天没有下雨.”翻译成命题公式. 得 分 评卷人 四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由. 13.下面的推理是否正确，试予以说明 (1)(Hx)F(x)→G(x) 前提引入 (2)F(y)→G(y) US(1). 67
5.设 A(x) :x是人 ，B(二):x是学生，则命题“不是所有人都是学生”可符号化为( A.('d x) (A(x)八B(x)) C.，(b' x) (A (x)一B(x)) B.，(日x)(A(x)八B(x)) D.，(3 x) (A (x) A ，B(x)) 得 分 评卷人 二、填空题 (每小题 3分，本题共 15分) 6.若集合 A 的元素个数为 10，则其幂集的元素个数为 7.设A={a,b,c},B={1,2}，作 f:A-B，则不同的函数个数为 8.若人二{1,2},R={ I xC-A, yEA, x+y=10}，则R的自反闭包为 9.结点数 v与边数 。满足 关系的无向连通图就是树. 10.设个 体 域 D = { a, b, c }，则 谓 词 公 式 (dx) A (x)消 去 量 词 后 的 等 值 式 为 得 分 评卷人 三、逻辑公式翻译(每小题 6分 ，本题共 12分) 将语句“尽管他接受 了这个任务，但他没有完成好.”翻译成命题公式. 将语句“今天没有下雨.”翻译成命题公式. l es ， 白 ，. J ll l 得 分 评卷人 四、判断说明题 (每小题 7分 ，本题共 14分) 判断下列各题正误 ，并说明理 由. 13.下面的推理是否正确 ，试予以说明. (1)(d x)F(x)一 G(x) (2) F(y)-G(y) 前提引人 LTS(1)
14.若偏序集的哈斯图如图二所示，则集合A的最大元为a,最小元不存在. 图二 得 分 评卷人 五、计算题（每小题12分，本题共36分） 15.求(PVQ)→(RVQ)的合取范式. 16.设A={0,1,2,3,4},R={x∈A,y∈A且x+y|x∈A, y∈A且x+y≤3}，试求R,S,R·S,R1,S-1,r(R) 17.画一棵带权为1,2,2,3,4的最优二叉树，计算它们的权. 得分 评卷人 六、证明题（本题共8分） 18.设G是一个n阶无向简单图，n是大于等于2的奇数.证明G与G中的奇数度顶点个 数相等(G是G的补图). 68
14.若偏序集的哈斯图如图二所示，则集合 A的最大元为a，最小元不存在. 。。q\。 方 图 二 巨耍{五簿一“2分，*-%# 36分’ 15.求(PVQ)一(RVQ)的合取范式. 16.设 A={。，1,2,3,4},R={ IxEA,yEA且x十y }xC-A, yEA且x+y镇3}，试求 R,S,R·S,R一‘，S-', r(R). 17.画一棵带权为 l, 2, 2, 3, 4的最优二叉树，计算它们的权. 六、证明题 (本题共 8分) 阶无向简单图，n是大于等于 2的奇数.证明G与G中的奇数度顶点个 数相等(G是 G的补图)
试卷代号：1009 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试（半开卷） 离散数学（本）试题答案及评分标准 (供参考) 2009年7月 一、单项选择题（每小题3分，本题共15分） 1.A 2.B 3.B 4.D 5.C 二、填空题（每小题3分，本题共15分）】 6.1024(或填：21°) 7.8(或填：23) 8.{,} 9.e=v-1 10.A(a)∧A(b)∧A(c) 三、逻辑公式翻译（每小题6分，本题共12分】 11.设P:他接受了这个任务，Q:他完成好了这个任务， (2分) P∧nQ. (6分) 12.设P:今天下雨， (2分) P (6分) 四、判断说明题（每小题7分，本题共14分） 13.错误 (3分) (2)应为F(y)→G(x),换名时，约束变元与自由变元不能混淆. (7分) 14.错误. (3分) 集合A的最大元不存在，a是极大元. (7分) 五、计算题（每小题12分，本题共36分） 15.(PVQ)→(RVQ) 台(PVQ)V(RVQ) 台(P∧Q)V(RVQ) 台(PVRVQ)A(QVRVQ) 台(PVRVQ)∧R(合取范式) (12分) 注：其他解法参照给分 69
试卷代号:1009 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试(半开卷) 离散数学(本) 试题答案及评分标准 (供参考) 2009年 7月 一、单项选择题(每小题 3分，本题共 15分) 1. A 2. B 3. B 4. D 5. C 二、填空题(每小题 3分，本题共 15分) 6. 1024(或填:210) 7. 8(或填 :23) 8.{ ,} 9. e= v一 1 10. A(a) e A(b) n A(c) 三、逻辑公式翻译 (每小题 6分，本题共 12分 ) 11.设尸:他接受了这个任务，Q:他完成好了这个任务， 尸八，Q. 12.设P:今天下雨， ，尸. 四、判断说明题(每小题 7分，本题共 14分) 13.错误. (2)应为 F(刃-G(x)，换名时，约束变元与自由变元不能混淆. 14.错误. 集合 A 的最大元不存在 ，a是极大元. 五、计算题(每小题 12分，本题共36分) 15.(P V Q)- (R V Q) 幼 ，(PVQ)V(RVQ) t} (，Pn，Q) V (R V Q) 拱 (，PVRVQ) A(，QVRVQ) } ( -PVRVQ)AR(合取范式) 注 :其他解法参照给分. (2分) (6分) (2分) (6分) (3分) (?分 ) (3分 ) (7分) (12分)
16.R=0, (2分) S={,,,,,,, ,,} (4分) R·S=0, (6分) R-1=0, (8分) S-1=S, (10分) r(R)=I. (12分) 17. 12 7 4 03 2 (10分) 1 权为1×3+2×3+2×2+3×2+4×2=27 (12分) 六、证明题（本题共8分】 18.证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数， (3分) 因此，若G中顶点的度数为奇数，则在G中的度数一定也是奇数， (6分) 所以G与G中的奇数度顶点个数相等. (8分) 70
16. R=必 ， S={ ， ， ， ， ， ， ， ， ，} R·5=必 ， R一‘=必， S一’= S， r(R)=IA- 17. 12 (2分) (4分) (6分) (8分) (10分) (12分) (10分) 权为 1X3+2X3十2X2+3X2+4X2=27 六、证明题(本题共 8分) 18.证明:因为n是奇数，所以n阶完全图每个顶点度数为偶数， 因此，若 G中顶点 v的度数为奇数，则在 G中v的度数一定也是奇数 ， 所以 G与G 中的奇数度顶点个数相等. (12分) <3分) (6分) <8分)