试卷代号：1002 座位号■ 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试（半开卷） 计算机数学基础(1)试题 2009年7月 题号 二 三 四 总分 分 数 得分 评卷人 一、单项选择题（每小题4分，共20分） 1.F(x):x是分数，Q(x):x是有理数.则命题“凡是有理数均可表成分数”在谓词逻辑中 符号化为( ). A.3x(Q(x)→F(x) B.Vx(Q(x)-F(x)) C.Vx(Q(x)+F(z)) D.Hx(Q(x)∧F(x) 2.下列不是重言蕴含式的为() A.A∧B→A B.AVB→A C.A,B台AAB D.B→A→B 3.设A,B,C为三个集合，那么以下推理正确的是(). A.A三B,B二C,则A∈C B.A∈B,B∈C,则A∈C C.A二B,B三C,则A三C D.A∈B,B≤C,则A二C 4.设G是有n个结点的无向完全图，则G的边数(). A.合(a-1） B.(x-1) C.n(n-1) D.n(n+1) 5.下列数组中，不能构成图的度数列的数组是(). A.(1,1,1,2,3) B.(1,3,3,3) C.(2,2,2,2,2) D.(1,2,3,4,5) 7
试卷代号:1002 座位号「三二} 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试(半开卷) 计算机数学基础(1) 试题 2009年 7月 题 号 四 总 分 分 数 得 分 评卷人 一、单项选择题(每小题4分，共 20分) 1. F(X) :x是分数 ，Q(x):x是有理数.则命题“凡是有理数均可表成分数”在谓词逻 辑中 符号化为 ( ). A. 3 x(Q(x)- F(x)) B. V x(Q(x)- F(x)) C. b' x(Q(x)- F(x)) D. fl x(Q(x)八F(x)) 2.下列不是重言蕴含式的为( ). A. A八BMA B. AVBM A C. A,B}A八B D. BMA- B 3.设 A,B,C为三个集合 ，那么以下推理正确的是( ). A. ACB,BCC，则 AEC B. AEB,BEC，则 AEC C. ACB,BCC，则 ACC D. AEB,BcC，则 ACC 4.设 G是有 n个结点 的无 向完全图，则 G的边数( ). 1 ，;一刀(n一 1) Z 。 1， 匕。 - ln一 1) Z C. n (n一 1) D. n(n+l) 5.下列数组中，不能构成 图的度数列的数组是 ( A.(1，1，1，2，3) C. (2,2，2，2，2) (1，3，3，3) (1,2，3，4，5) B. D
得分 评卷人 二、填空题（每小题4分，共20分】 6.命题公式P→(QVP)VP的真值是 7.设集合A={1,2,3,4},B={a,b,c},则|AXB|= 8.若集合A三☑当且仅当 9.设图G如图1所示，那么图G的点割集是 图1 10.设平面图G=有r个面：R。(无限面)，R,R2,…,R,-1,则有2|E|= 得分 评卷人 三、化简计算题（每小题10分，共50分） 11.化简命题公式(P+P)→Q)→(P→P)→R) 12.指出谓词公式HxHy(R(x,y)VL(y,z)→3xH(x,y)中的指导变元，量词的辖域 和该公式的自由变元和约束变元. 13.化简集合表达式((AUB)∩B)-(CUB)U((AUB)∩~B)UA). 14.设集合A={a,b,c},已知A上的二元关系R的关系图如图2所示，试写出R的集合 表达式，并指出R具有的性质。 图2
得 分 评卷人 二、填空题(每小题 4分 ，共 20分) 命题公式 尸、 (QV尸)V尸的真值是 设集合 A= {1,2,3,41, B= (a,b,cl，则 JAXBI= 8.若集合AC必当且仅当 9.设图 G如图 1所示，那么图 G的点割集是 图 1 10.设平 面 图 G= 有 r个 面 :Ro(无 限面)9R, 9RZ,...tRr_1，则有 21EI= 得 分 评卷人 三、化简计算题 (每小题 10分。共 50分) 11.化简命题公式 ((P- - P)-Q)- ((，P-->P)-R). 12.指出谓词公式V xV y(R(x,y) V L(y,z))一 3 xH(x, y)中的指导变元，量词的辖域 和该公式的 自由变元和约束变元. 13.化简集合表达式(((AUB) nB)一(CU B))U(((AUB)n一B) U A). 14.设集合A = {a,b,cl，已知A上的二元关系R的关系图如图 2所示，试写出R的集合 表达式 ，并指出 R具有的性质. 图 2
15.在图3的四个图中，(1)哪些是强连通图？(2)哪些是单侧连通图？(3)哪些是弱连通 图？ ④ 图3 得 分 评卷人 四、证明题（本题共10分） 16,证明在非平凡树T中，至少有两片树叶
15.在图 3的四个图中 图? a一 h d一 一4气少 (1)哪些是强连通图?(2)哪些是单侧连通 图?(3)哪些是弱连通 ① 困 一 c “ d “因- 分一 ② ③ 妙 四 · 图 3 得 分 评卷人 四、证明题(本题共 10分) 16.证明在非平凡树 丁中，至少有两片树 叶
试卷代号：1002 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试（半开卷） 计算机数学基础(1)试题答案及评分标准 (供参考) 2009年7月 一、单项选择题（每小题4，共20分） 1.B 2.B 3.C 4.A 5.D 二、填空题（每小题4分，共20分）】 6.1 7.12 8.A=0 9.{b,c},{e 10.deg(R.) 三、化简计算题（每小题10分，共50分） 11.(P-→P)→Q)→((P→P)→R) 台((？PVP)→Q)→(PVP)R) 台(PVQ)→(PVR) 台(P∧Q)V(PVR) (P∧Q)VP)VR 台PVR 12.x,y是该公式的指导变元 2分) ( 量词Hx的辖域是y(R(x,y)VL(y,x); 量词Vy的辖域是R(x,y)VL(y,2); 量词3x的辖域是H(x,y). 10
试卷代号:1002 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试(半开卷) 计算机数学基础(1) 试题答案及评分标准 (供参考) 2009年 7月 一、单项选择题(每小题4，共 20分} l. B 2. B 3. C 4. A 5. D 二、填空题(每小题 4分，共 20分) 6. 1 7. 12 8.A=必 9.{b,。}，{e} 10.习 deg(R,) 三、化简计算题(每小题 10分，共 50分) 11.((P--, -，尸)~ Q)一 ((，P- P)-R) }'((，PV ”P)->Q)一 ((P V P)-}R) }#(P V Q)- (，PVR) 拱(，尸八，Q)V(， PVR) ,} ((二Pe 二Q) V ，P) VR 拱 ，尸VR 12. x, y是该公式的指导变元. 量词V二的辖域是V y(R(x,刃 V L(y,z)); 量词Vy的辖域是R(x,y) V L(y,z); 量词己二的辖域是 H(二，y). 10 (10分) (2分) (8分)
公式中的自由变元是之及H(x,y)中的y:约束变元是R(x,y)VL(y,2)中的x,y. (10分)） 13.((AUB)∩B)-(CUB))U((AUB)∩~B)UA) =(B∩~C∩~B)U(A∩~B)UA) (7分) =⑦UA=A (10分) 14.R的表达式为 R={,,,,,} (6分) R具有自反性，反对称性， (10分) 15.(1)①，④是强连通图； (4分) (2)①，②，④（或只答②）是单侧连通图； (7分) (3)①，②，③，④（或只答③）是弱连通图 (10分) 四、证明题（本题共10分）】 16.设非平凡树T有n个结点n≥2，由树的定义可知，T中任何顶点的度数均大于或等 于1.设T有片树叶，则T中有k个1度顶点，其余n一k个分支点的度数均大于等于2. (4分) 由握手定理，得 k十2(n-k)≤2(n-1). (8分) 解得k≥2. 所以T至少有两片树叶： 0分 11
公式中的自由变元是 z及 H (x, y)中的 y;约束变元是 R(二，y) V L(y,z)中的x, y. (10分) 13.M A UB)nB)一(CUB)) U(((AUB)n--B)UA) =(Bn一cn-B) U ((An-B) U A) (7分) “OUA=A (10分) 14. R的表达式为 R={，，，，，} (6分) R具有自反性，反对称性. (10分) 15. (1)(D,④是强连通图; (4分) (2)①,②,.(或只答②)是单侧连通图; (7分) (3)01,02 ,03 ,.(或只答③)是弱连通图. (1'0分) 四、证 明题(本题共 10分) 16.设非平凡树T有n个结点n>, 2，由树的定义可知，T中任何顶点的度数均大于或等 于 1.设 T有k片树叶，则 T中有k个 1度顶点，其余 n-k个分支点的度数均大于等于 2. (4分) 由握手定理，得 k+2(n-k)毛2(n-1). (8分) 解得 k)2. 所以 T至少有两片树叶. (]0分)