试卷代号：1009 座位■■ 国家开放大学（中央广播电视大学）2014年春季学期“开放本科”期末考试 离散数学（本）试题（半开卷） 2014年7月 题 号 二 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（每小题3分，本题共15分）》 1.若集合A={a,b,c,d},则下列表述正确的是(). A.{a}∈A B.(a)A C.(a,b,c)CA D.{a,b,c,d}∈A 2.设A={2},B={3,4,5},A到B的关系R={(x,yx∈A,y∈B,x=y+1},则R=(). A.0 B.{,,》 C.{》 D.{,} 3.无向图G是个棵树，边数为12，则G的结点数是( A.12 B.24 C.11 D.13 4.下面的推理正确的是(). A.(1)(3x)(A(x)→B(x)) 前提引入 (2)A(y)→B(y) ES(1). B.(1)(]x)A(x)→B(x) 前提引入 (2)A(y)→B(y) US(1). C.(1)(Vx)A(x)+B(x) 前提引入 (2)A(y)→B(y)） US(1). D.(1)(Hx)(A(x)+B(x)) 前提引入 (2)A(y)B(x) ES(1). 52
试卷代号 0 0 座位号CD 国家开放大学(中央广播电视大学 14年春季学期"开放本科"期末考试 离散数学(本)试题{半开卷) 2014 年7 |题号|一|二|三|四|五|六|总分| 数I I I I I I I I |得分|评卷人| 择题(每小题 3分，本题共 5分) I I I 1.若集合 A = 则下 ). A. {a} R{α} C. {a,b , c} C A D. {a ,b, c ,d }εA 2. ,B = { 3, 4, 5 } A到 B的关系 ξ A y十1}，则 ). A. 0 B. { , ,} C. {} D. { ,} 3. 图G 是个棵树 则G ). A.12 B.24 C. ll D.13 4. 下 面 正确 A. (1) (丑 )( 前提引人 (2)A(y)•B(y) ES(1 ). B. 0) ( 3 x)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)AB(x)) B.(x)(A(x)+B(x)) C.(3x)(A(x)A-B(x)) D.(Vz)(A(z)AB(x)) 得 分 评卷人 二、填空题（每小题3分，本题共15分）】 6.设集合A={1,2,3},B={3,4,5},C={2,3,4,5},则BU(A一C)等 于 7.设A={1,2},B={a,b},C={3,4},从A到B的函数f={,},从B到 C的函数g={,},则Dom(gf)等于 8.两个图同构的必要条件是 9.设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v,e和r满足的关系 式 10.设个体域D={1,2,3},则谓词公式（x)A(x)消去量词后的等值式 为 得分 评卷人 三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“3大于2或1加1等于2”翻译成命题公式. 12.将语句“如果明天下雪，我们就去旅游.”翻译成命题公式. 得分 评卷人 四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由. 13.若图G中存在汉密尔路，则图G是一个汉密尔顿图. 14.无向图G是树当且仅当无向图G是连通图. 53
5. :x ，B(x) :x 是学生 是所有人 是学 ). A. --, ( 3 x)(A(x) 八B(x» B. --, ("Ix ) (A(x)•B(x» c. --, ( 3 x)(A(x) --， B(x» D. ( Vx) (A(x) 1\B(x» |得分|评卷人| I I I 二、填空题{每小题 3分，本题共 5分) 6. {l, 2, 3 }, B = {3 ,4 ,5} ,C= {2 ，3 ，4 ，5} 7. {I ,2} l， >， 2， J) 8. 件是 9. 设G 是连通平面 示G 10. 设 个 域D= {l ，2 ，3} "I A (x) 三、逻辑公式翻译(每小题 6分，本题共 2分} 1. 句"3 于2 或1 加1 于2" 命题 12. 我们 旅游 译成命 |得分|评卷人| I I I 四、判断说明题{每小题 7分，本题共 4分} 判断下列各题正误，并说明理由. 13. 图G 在汉密 图G 个汉 14. 图G 是树 且仅 图G 53
得 分 评卷人 五、计算题（每小题12分，本题共36分） 15.设A={1,2,3,4,5},R=(|x∈A,y∈A且x-y=3,S=({x∈A, y∈A且x+y=3},试求R,S,R·S,R-1,r(S),s(R). 16.设有如图一所示的有向图G=, 14 图一 (1)试求出G的邻接矩阵A. [32427 2131 (2)已知A3= ,求G中U1到v,的长度为3的路径条数； 000 0010 (3)求G中1的长度为3的回路条数. 17.求(PVQ)→R的析取范式与主合取范式. 得 分 评卷人 六、证明题（本题共8分） 18.设A,B,C均为任意集合，试证明：A一(BUC)=(A-B)一C. 54
|得分|评卷人| I I I 五、计算题{每小题 2分，本题共 6分} 15. {l , 2, 3, 4, 5},R = { Ix εA ，y 且x-y=3;i,s = { Ix εA yEA 且x+y=3} R， S， ，R ，s(R). 16. 图一 G U U G= (3) 求G 为3 17. 求(PVQ) →R 合取 |得分|评卷人| I I I 六、证明题{本题共 8分) 18. 集合 一(BUC)= (A- B)-C. 54
试卷代号：1009 国家开放大学（中央广播电视大学）2014年春季学期“开放本科”期末考试 离散数学（本）试题答案及评分标准（半开卷） (供参考) 2014年7月 一、单项选择题（每小题3分，本题共15分】 1.C 2.A 3.D 4.A 5.B 二、填空题（每小题3分，本题共15分）】 6.{1,3,4,5} 7.{1,2}或A 8.结点数相等：边数相等；度数相同的结点数相等 9.v-e+r=2 10.A(1)∧A(2)∧A(3) 三、逻辑公式翻译（每小题6分，本题共12分） 11.设P:3大于2，Q:1加1等于2. (2分) 则命题公式为：PVQ (6分) 12.设P:明天下雪，Q:我们就去旅游 (2分) 则命题公式为：P·Q, (6分) 四、判断说明题（每小题7分，本题共14分】 13.错误， (3分) 反例：如图二中存在汉密尔路，但图G不是一个汉密尔顿图， (7分) 图二 (或：按定义有：若图G中存在汉密尔回路，则图G是一个汉密尔顿图.) 说明：举出符合条件的反例均给分， 55
试卷代号 国家开放大学(中央广播电视大学 4年春季学期"开放本科"期未考试 离散数学(本)试题答案及评分标准(半开卷) (供参考) 2014 年7 一、单项选择题(每小题 3分，本题共 5分} I. e 2.A 3. D 4.A 5. B 二、填空题(每小题 3分，本题共 5分) 6. {l .3. 4. 5} 7.{1.2} 或A 8. 相等 边数相 等 9. v-e+r=2 10. (l 八A(2) 八A(3) 三、逻辑公式翻译(每小题 6分，本题共 2分) 1. 于2.Q:l 加1 于2. 则命题公式为 12. 天下 则命题公式为 四、判断说明题(每小题 7分，本题共 4分} 13. 反例:如图二中存在汉密尔路，但图 G不是一个汉密尔顿图. o 0 图二 (或:按定义有:若图 G中存在汉密尔回路，则图 G是一个汉密尔顿图. ) 说明:举出符合条件的反例均给分. (2 (6 (2 (6 (3 (7分) 55
14.错误， (3分) 反例：如图三为连通图，但不是树。 (7分) 图三 (或：按定义有：无向图G是树当且仅当无向图G是无回路的连通图.) 说明：举出符合条件的反例均给分 五、计算题（每小题12分，本题共36分） 15.R={, (2分) S={,} (4分) R·S={,} (6分) R-1={,} (8分) r(S)={,,,,,} (10分) s(R)={,,,}. (12分) 说明：对于每一个求解项，如果基本求出了解，可以给对应1分 卫110 1010 16.G的邻接矩阵为：A= (4分) 0001 0010 (2)由A3中a4可知，G中v1到，的长度为3的路径有2条； (8分) (3)由A3中a11可知，G中v1的长度为3的回路有3条； (12分) 说明：如果没有求出矩阵乘积，而通过列举找出正确的路与回路数，也给相应分数 17.(PVQ)→R ÷(PVQ)VR (2分) 一（一P∧Q)VR析取范式 (5分) ÷(=PVR)A(QVR) (7分) (PVR)V(QA-Q)∧(-QVR) (9分) 56
14. 反例:如图三为连通图，但不是树. /\ 图三 〈或 定义 且仅 ) 说明:举出符合条件的反例均给分. 五、计算题{每小题 2分，本题共 6分) 15. R= { , } S={ ,} R· S={ ,} R- 1 = {, } r(S) = {, , , , , } s(R) = { , , , }. 说明:对于每一个求解项，如果基本求出了解，可以给对应 1分. 1 1 1 0 1 010 16.G 邻接 000 1 o 0 1 0 (3 (7 (2 (4 (6 (8 (1 (1 (4 (2 (5 (7 (9 (2) a u ，G 为3 有2 (8 (3) ll ，G 为3 有3 (1 2 说明:如果没有求出矩阵乘积，而通过列举找出正确的路与回路数，也给相应分数. 17. (PVQ)• R -， VQ) VR -， -， V 析取范式 -， VR) A (-,Q VR) -， VR) V (Q A -， )八(-， R) 56
=(-PVR)V(Q∧-Q)∧(-QVR)V(PAP) (10分) ≌(-PVRVQ)A(-PVRV-Q)∧(-QVRVP)∧(-QVRV-P) (11分) -(PV-QVR)∧(PVQVR)∧(PV-QVR)主合取范式 (12分) 六、证明题（本题共8分） 18.证明： 设S=A-(BUC),T=(A一B)-C, 若x∈S,则x∈A且x任BUC,即x∈A,并且x任B且xC, (2分) 由x∈A且xB,得x∈A-B,又由xtC得x∈(A-B)一C,即x∈T, (3分) 所以S二T. (4分) 反之，若x∈T,则x∈(A一B)且xC, (5分) 由x∈(A一B),得x∈A且xB,则得xBUC, (6分) 即得x∈A且x任BUC,即x∈S, 所以T三S (7分) 因此T=S (8分) 57
-， V R) V (Q 1\ -， )八(-， R) V (P -，P) -， RV Q) -， V R V -， )八(-， V R V P) 1\ (-,Q V R V -,P ) -,Q V R) -，PVQV R) -，PV -，QVR) 合取 六、证明题(本题共 18. = A <B U C T=(A-B)-C, S，则 A且 B U C A，并且 f/:. ，又由 f/:. 所以 反之，若 ，则 B)且 f/:. 由工 f/:. B， f/:. c， 即得 A且 f/:. c ，即 所以 因此 (1 (1 (1 (2 (3 (4 (5 (6 (7分) (8 57