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

试卷代号：1009 座位号 中央广播电视大学 学年度第 学期“开放本科”期末考试离散数学（本） 试题2014年1月题号一二三四五六总分得分一、单项选择题（每小题3分，本题共15分）1若集合Aa,b,c，则下列表述正确的是( B ) AaA BaACA Da,b,cA2设A1,2，B=1,2,3,4,5，A到B的关系Rx, y| xA, yB且x+1=y，则R=( D )A, B,C, D, 3无向图G的边数为12，则图G的结点的度数之和是（ A ） A24 B12 C6 D184设连通平面图G有v个结点，e条边，r个面，则（ B ）Av + e - r=2 Br + v - e =2 Cv + e - r=4 Dv + e r = 45设个体域D是整数集合，则命题x$y (xy = y)的真值是（ C ）A. 不确定 B. F C. T D. 以上说法都不是二、填空题（每小题3分，本题共15分）6设集合A=1, 2, 3，B=3, 4, 5，C=5, 6, 7，则ABC等于1, 2, 3, 4 7设A=1，2，B=a，b，C=3，4，5，从A到B的函数f =, ，从B到C的函数g=, ，则Ran(g f)等于 3，4 8若图G=，其中V= a, b, c, d ，E= (a, b), (a, d) , (b, c) , (b, d)，则该图中的割边为 (b, c) 9设G是欧拉图，则G的奇数度数的结点数为 0 个10设个体域D2, 4, 6，A(x)为“x是偶数”，则谓词公式(x)A(x)的真值为 真 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“我学英语，并且学法语”翻译成命题公式设P：我学英语，Q：我学法语 则命题公式为： PQ12将语句“除非小王来，否则小李不去”翻译成命题公式设P：小王来，Q：小李去则命题公式为：QP或PQ 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13空集 的幂集也是空集 不正确。 空集的幂集为 14($x)(P(x)Q(y)R(z)中的约束变元为y 不正确。 ($x)(P(x)Q(y)R(z)中的约束变元为x五、计算题（每小题12分，本题共36分）15设集合A=1, 2, 3，R=, ,，S=, 试计算（1）RS； （2）R -1； （3）r（R）（1）RS =, ,； （2）R -1=, , ； （3）r（R）=, , , , 16图G=，其中V= a, b, c, d ，E= (a, b), (a, c) , (a, d), (b, c) , (c, d)，对应边的权值依次为6、5、2、3及8，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值（1）G的图形表示如图一所示： ooooabcd图一86532 （3分）（2）邻接矩阵： （6分）（3）图二中的粗线与结点表示的是最小生成树： ooooabcd图二86532权值为10 ooooooooo123334761317试画一棵带权为1, 2, 3, 3, 4的最优二叉树,并计算该最优二叉树的权权为13+23+32+32+42=29 六、证明题（本题共8分）18试证明：PQ P(PQ) 证明：（1）PQ P （1分）（2）P P（附加前提） （3分）（3）Q T（1）（2）I （5分）（4）PQ T（2）（3）I （7分）（5）P(PQ) CP规则 （8分