试卷代号：1009 座位号■ 中央广播电视大学2012一2013学年度第一学期“开放本科”期末考试（半开卷） 离散数学（本）试题 2013年1月 题 号 二 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（每小题3分，本题共15分） 1.若集合A={a,b},B={a,{a,b},则( A.AB B.A≤B C.ACB D.A∈B 2.集合A={x|x为小于10的自然数}，集合A上的关系R={|x十y=10且x, y∈A},则R的性质为(). A.自反的 B.对称的 C.传递且对称的 D.反自反且传递的 3.设有向图(a)、(b)、(c)与(d)如图一所示，则下列结论成立的是( (a) (b) (c) (d) 图一 A.(a)仅为弱连通的 B.(b)仅为弱连通的 C.(c)仅为弱连通的 D.(d)仅为弱连通的 63
试卷代号 座位号IT] 中央广播电视大学 3学年度第一学期"开放本科"期末考试(半开卷) 离散数学(本)试题 2013 年1 |题号|一|二|三|四|五|六|总分| |分数 I I I I I I I |得分|评卷人| 题{每小题 3分，本题共 5分} I I I 1.若集合 ，的 {a ，b} }，则( ). ~AEB RACB CACB nAεB 2. 于10 ，集合 A上的关系 0且 yε ). A. 的B. C. 递且对 的D. 且传递 3. 成立 ). ... (a) A. (a) 连通 C. (c)仅为弱连通的 (b) ... (c) 图- B. (b) 为弱 D. (d) (d) " 63
4.设图G的邻接矩阵为 [0110 07 1 0011 10000 0 1001 1010 则G的边数为(). A.5 B.6 C.7 D.8 5.下列公式( )为永真式 A.P∧-Q+PVQ B.(P-(Q→P))+(P→(P→Q) C.(Q-(PVQ))+(-QA(PVQ)) D.(-PV(PAQ))+Q 得分 评卷人 二、填空题（每小题3分，本题共15分） 6.设集合A={1,2,3},那么集合A的幂集是 7.设A={a,b},B={1,2},作f:A→B,则不同的函数个数为 8.若A={1,2},R={x∈A,y∈A,x+y<4},则R的自反闭包为 9.无向连通图在结点数v与边数e满足 关系时是树. 10.(x)(A(x)→B(x)VC(x,y)中的自由变元为 得分 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“他们去旅游，仅当明天天晴.”翻译成命题公式. 12.将语句“今天没有下雪.”翻译成命题公式. 64
4. 图G 邻接 阵为 100 10011 1 0 0 0 0 o 1 001 01010 G的边数为( ). A5 &6 C7 n8 5. )为永真式. A -, p /I. -,Q-P VQ C( ++ -, Q/I.(PVQ» B. (P• ( -, Q• P» ++ ( -, P•(P • Q» D. (-, PV (P /I.Q»++Q |得分|评卷人 I I I 二、填空题{每小题 3分，本题共 5分} 6. 合A= {I ，2 ，3} 合A 事 集 7. 的 函 8. A = {I，幻 9. 连通 边数 10. ( Vx) (A(x)•B(x» VC(x 关系时是树. |得分|评卷人| I I I 三、逻辑公式翻译{每小题 6分，本题共 2分} 1. 们去旅游 天天 译成 题公 12. 下雪 题公 64
得分 评卷人 四、判断说明题（每小题7分，本题共14分）】 判断下列各题正误，并说明理由· 13.汉密尔顿图一定是欧拉图. 14.下面的推理是否正确，试予以说明. (1)(3x)(F(x)+G(y)) 前提引人 (2)F(y)→G(y) ES(1). 得 分 评卷人 五、计算题（每小题12分，本题共36分） 15.设A={0,1,2,3,4,5,6},R={|x∈A,y∈A且x+y|x∈A, y∈A且x十y≤3}，试求R,S,R·S,R1S1,r(R). 16.画一棵带权为1,2,2,3,6的最优二叉树，计算它们的权. 17.求(PVQ)→(RVQ)的析取范式，合取范式. 得分 评卷人 六、证明题（本题共8分） 18.试证明集合等式A∩(BUC)=(A∩B)U(A∩C). 65
|得分|评卷人| I I I 四、判断说明题{每小题 7分，本题共 14分} 判断下列各题正误，并说明理由. 13. 密尔 定是 14. 下面 推理 (1)( 3 x)(F(x) →G(y (2)F(y)•G(y) ES(1 ) . |得分|评卷人| I I I 五、计算题{每小题 2分，本题共 6分} 15. xε yεA x， A， yεA S ,R - 1. S-1 ,r (R ). 16. 为1 ，2 ，2 ，3 ，6 最优 它们 17. 析取 |得分|评卷人| I I I 六、证明题{本题共 8分} 18. 合等式 (BUC)= (AnB) U(AnC). 65
试卷代号：1009 中央广播电视大学2012一2013学年度第一学期“开放本科”期末考试（半开卷） 离散数学（本）试题答案及评分标准 (供参考) 2013年1月 一、单项选择题（每小题3分，本题共15分）】 1.D 2.B 3.C 4.A 5.B 二、填空题（每小题3分，本题共15分） 6.{☑，{1}，{2}，{3}，{1,2}，{1,3}，{2,3}，{1,2,3}} 7.4 8.{,,,} 9.e=v-1 10.C(x,y)中的x与y 三、逻辑公式翻译（每小题6分，本题共12分） 11.设P:他们去旅游，Q:明天天晴， (2分) P→Q, (6分) 12.设P:今天下雪， (2分) P. (6分) 四、判断说明题（每小题7分，本题共14分）】 13.错误. (3分) (1)存在汉密尔顿图不是欧拉图， (5分) 反例见图二， 图二 (7分) 14.错误. (3分) (2)应为F(a)→G(y),换名时，约束变元与自由变元不能混淆. (7分) 66
试卷代号 中央广播电视大学 3学年度第一学期"开放本科"期末考试(半开卷) 离散数学(本〉试题答案及评分标准 (供参考) 2013 年1 一、单项选择题{每小题 3分，本题共 5分} l. D 2.B 3.C 4.A 5. B 二、填空题{每小题 3分.本题共 5分} 6. {正当， }， }， 3 }， 1， }， 1，剖， 2， }， 1， 2， 3 } } 7.4 8. { ,, ,} 9. e-v-1 10. C(x 三、逻辑公式翻译{每小题 6分，本题共 2分} 11. 设P: 去族游 天天 P• Q. 12. "'P. \ 四、判断说明题{每小题 7分，本题共 14分} 13. (1)存在汉密尔顿图不是欧拉图. 反例见图二. 回二 14. (2) →G( 66 (2 (6 (2 (6 (3 (5 (7 (3 (7
五、计算题（每小题12分，本题共36分）】 15.R={} (2分) S={,,,,,,,, ,} (4分) R·S={,,,} (6分) R-1={} (8分) S-1=S (10分) r(R)=IA (12分) 16.最优二叉树如图四： 14 8 06 图四 (10分) 权为：1×3+2×3+2×3+3×3+6×1=30 (12分) 注：其他正确的最优二叉树参照给分 17.(PVQ)-→(RVQ) (PVQ)V(RVQ) (4分) 台(PAQ)V(RVQ) 曰(PVRVQ)A(QVRVQ) 台(PVRVQ)析取、合取范式 (12分) 注：其他正确答案参照给分 六、证明题（本题共8分）】 18.证明： 设S=A∩(BUC,T=(A∩B)U(A∩C,若x∈S,则x∈A且x∈BUC,即x∈A且x∈B或 x∈A且x∈C, 也即x∈A∩B或x∈A∩C,即x∈T,所以SCT. (4分) 反之，若x∈T,则x∈A∩B或x∈A∩C, 即x∈A且x∈B或x∈A且x∈C 也即x∈A且x∈BUC,即x∈S,所以T三S. 因此T=S (8分) 67
五、计算题{每小题 2分，本题共 6分} 15.R={} (2 s={, , , , , , , , ,} R· S={,, ,} R•={} S-l=S r(R)=IA 16. 最优 图 四 14 (4 (6 (8 (1 (1 (4 (1 (1 (1 2 回四 权为 其他 17. (PVQ)• (R V Q) 件..， (PVQ) V(RVQ) 件( .., P /\ ..,Q) V(R VQ) 件( ..,P VRV Q) /).( ..,Q VR V Q) 伸(..， 析取 照 给 六、证明题{本题共 8分} 18. (B B) U C zεA 且zεC 也即 ε A n B n C 即zε 反之，若 ε T ，则 εB εA εC 也即 εBUC 即zεS TI;;;，S. 因此 (4 (8 67