离散数学2014年7月份试题.doc

试卷代号：1009-3 座位号 中央广播电视大学 学年度第 学期“开放本科”期末考试离散数学（本） 试题2012年7月题号一二三四五六总分得分一、单项选择题（每小题3分，本题共15分）1若集合Aa, b, c, d，则下列表述正确的是( C ) AaA BaACa, b, cA Da, b, c, d A2设A2，B=3,4,5，A到B的关系Rx, y| xA, yB且x = y+1，则R=( A )A B,C D, 3无向图G是个棵树，边数为12，则G的结点数是（ D ） A12 B24 C11 D134下面的推理正确的是（ A ）A(1) （$x）（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) （x）A（x）B（x） 前提引入(2) A（y）B（y） US（1） D(1) （x）(A（x）B（x） 前提引入 (2) A（y）B（x） ES（1）5设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ B ）A($x)(A(x)B(x) B(x)(A(x) B(x) C($x)(A(x)B(x) D(x)(A(x)B(x)二、填空题（每小题3分，本题共15分）6设集合A=1, 2, 3，B=3, 4, 5，C=2, 3, 4, 5，则B（AC）等于1, 3, 4, 5 7设A=1，2，B=a，b，C=3，4，从A到B的函数f=, ，从B到C的函数g=, ，则Dom(g f)等于 1，2，或A 8两个图同构的必要条件是 结点数相等；边数相等；度数相同的结点数相等 9设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 v-e+r=2 10设个体域D1,2,3，则谓词公式(x)A(x)消去量词后的等值式为 A(1)A(2)A(3) 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“3大于2或1加1等于2”翻译成命题公式 设P：3大于2，Q：1加1等于2） 则命题公式为：PQ12将语句“如果明天下雪，我们就去旅游”翻译成命题公式设P：明天下雪，Q：我们就去旅游 则命题公式为：PQ 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13若图G中存在汉密尔路，则图G是一个汉密尔顿图 不正确 反例：如图二中存在汉密尔路，但图G不是一个汉密尔顿图 图二14无向图G是树当且仅当无向图G是连通图不正确反例：如图三为连通图，但不是树 图三五、计算题（每小题12分，本题共36分）15设A=1，2，3，4，5，R=|xA，yA且x-y=3，S=|xA，yA且x+y=3，试求R，S，RS，R-1，r(S) ，s(R)R=, S=, RS=, R-1=, r(S)= , s(R)= ,16设有如图一所示的有向图G =， 图一（1）求G的邻接矩阵A；（2）已知A3=，求G中v1到v4的长度为3的路径条数； （3）求G中v1的长度为3 的回路条数（1）G的邻接矩阵为：A=， （2）由A3中a14可知，G中v1到v4的长度为3 的路径有2条； （3）由A3中a11可知，G中v1的长度为3 的回路有3条； 说明：如果没有求出矩阵乘积，而通过列举找出正确的路与回路数，也给相应分数17求（PQ）R的析取范式与主合取范式（PQ）R （PQ）R (PQ)R 析取范式 (PR)(QR) (PR )(QQ) (QR) (PR )(QQ) (QR)(PP) (PR Q) (PR Q) (QRP) (QRP ) (PQR)(PQR)(PQR) 主合取范式 六、证明题（本题共8分）18设A，B，C均为任意集合，试证明：A - ( BC ) = (A- B ) - C 设S= A - ( BC )，T= (A- B ) - C，若xS，则xA且xBC，即 xA，并且xB 且 xC， 由xA且xB，得xA - B，又由xC得 x(A- B )