离散数学(本)2017年1月份试题.doc

离散数学（本）2017年1月份试题一、单项选择题（每小题3分，本题共15分）1若集合A1,2,3,4，则下列表述不正确的是 ( ) A 2, 3 A BA 1, 2 ,3,4C1, 2, 3, 4 A D1A2若无向图G的结点度数之和为20，则G的边数为（ ）A10 B20 C30 D5 3无向图G是棵树，结点数为10，则G的边数为（ ） A 5 B 10 C 9 D 114设A（x）：x是人，B（x）：x是学生，则命题“有的人是学生”可符号化为（ ）A(x)(A(x) B(x) B (x)(A(x)B(x) C(x)(A(x)B(x) D(x)(A(x)B(x)5下面的推理正确的是（ ）A(1) （x）F（x）G（x） 前提引入 (2) F（y）G（y） US（1） B(1) （$x）F（x）G（x） 前提引入(2) F（y）G（y） US（1） C(1) （$x）(F（x）G（x） 前提引入 (2) F（y）G（x） ES（1）D(1) （$x）（F（x）G（x） 前提引入 (2) F（y） G（y） ES（1） 二、填空题（每小题3分，本题共15分）6设A=1，2，B=1，2，3 ，则A到B上不同的函数个数为 7有n个结点的无向完全图的边数为 8若无向图G中存在欧拉路但不存在欧拉回路，则G的奇数度数的结点有 个9设G是有10个结点的无向连通图，结点的度数之和为30，则从G中删去 条边后使之变成树10设个体域D1, 2, 3, 4，则谓词公式($x)A(x)消去量词后的等值式为 三、逻辑公式翻译（每小题6分，本题共12分） 11将语句“昨天下雨”翻译成命题公式 12将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式 四、判断说明题（判断各题正误，并说明理由每小题7分，本题共14分）13存在集合A与B，使得AB与AB同时成立14完全图K4是平面图五计算题（每小题12分，本题共36分）15设偏序集的哈斯图如下，B为A的子集，其中B= b, c ，试（1）写出R的关系表达式；（2）画出关系R的关系图；（3）求出B的最大元、极大元、上界16设图G=，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v4)，(v1, v5)，(v2, v3)，(v3, v5) ，试（1）画出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出图G的补图的图形17求P（QR）的合取范式与主合取范式 六、证明题（本题共8分）18设A，B，C是任意集合，试证明：若AA=BB，则A=B离散数学（本）2017年1月份试题解答(供参考)一、单项选择题（每小题3分，本题共15分）1A 2A 3C 4B 5D二、填空题（每小题3分，本题共15分）697n(n-1)/2 （或C2n）829610A(1) A(2) A(3) A(4)三、逻辑公式翻译（每小题6分，本题共12分） 11设P：昨天下雨 （2分） 则命题公式为：P （6分）12设P：小王今天上午去看电影 Q：小王今天上午去打球 （2分）则命题公式为：（PQ） 或者（PQ）（ PQ ） （6分）四、判断说明题（每小题7分，本题共14分）13正确 （3分）例：设A=a，B=a，a （5分）则有AB且AB （7分）说明：举出符合条件的例均给分14正确 （3分）完全图K4是平面图， （5分）如K4可以如下图示嵌入平面 （7分）五计算题（每小题12分，本题共36分）15（1）R=,（4分） （2）关系图 （8分）（3）集合B无最大元，极大元为b与c、无上界 （12分）16解：（1）关系图 （3分）（2）邻接矩阵 （6分）（3）deg(v1)=3deg(v2)=2deg(v3)=2deg(v4)=1deg(v5)=2 （9分）（4）补图 （12分）17P（QR） P(QR) （2分）(PQ)(PR) 合取范式 （5分）(PQ) (RR) (PR) （7分）(PQ) (RR) (PR) (QQ) （9分）(PQR )(PQR) (PRQ )(PRQ) （11分）(PQR )(PQR)(PQR) 主合取范式 （12分）六、证明题（本题共8分）18证明：设