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

离散数学（本）2017年10月份试题一、单项选择题（每小题3分，本题共15分）1若集合A=1，2，B=1，1，2，则下列表述正确的是( ) AAB BAB CAB DBA2设A1, 3, 5，B=2, 4, 6，A到B的关系Rx, y| x+1=y，则R= ( )A B , , C , , D , , 3无向树G结点数是10，则G的边数是（ ） A 10 B 5 C 20 D 94命题“4是偶数或-3是负数”的否定是（ ）。A. 4不是偶数或-3不是负数 B. 4不是偶数且-3不是负数 C. 4不是偶数或-3是负数 D. 4是偶数且-3不是负数5设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)二、填空题（每小题3分，本题共15分）6设集合A=1, 2，B=2, 3，C=3, 4, 5，则A（BC）等于 7设A=1，2，B=2，3，C=3，4，从A到B的函数f=, ，从B到C的函数g=, ，则Ran(g f)等于 8若图G=，其中V= a, b, c, d ，E= (a, b), (a, d) , (b, c) , (b, d)，则该图中的割点为 9设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 10设个体域D1, 2, 3，A(x)为“x等于1”，则谓词公式($x)A(x)的真值为 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“小明去学校了，而且小亮也去学校了”翻译成命题公式 12将语句“如果天晴，我们就去比赛”翻译成命题公式 四、判断说明题（判断各题正误，并说明理由每小题7分，本题共14分）13若图G是一个欧拉图，则图G中存在欧拉路14若无向图G的结点数比边数多1，则G是树五计算题（每小题12分，本题共36分）15设集合A=1, 2, 3, 4，R=, ，S=, ，试计算（1）RS； （2）R -1； （3）s（R）16图G=，其中V= a, b, c, d, e ，E= (a, b), (a, c), (a, d), (b, c), (b, d), (c, d), (c, e), (d, e)，对应边的权值依次为2、3、4、5、6、7，3及2，试画出G的图形，写出G的邻接矩阵，并求出G权最小的生成树及其权值17求（PQ）R的析取范式与主合取范式 六、证明题（本题共8分）18试证明集合等式A (BC)=(AB) (AC)离散数学（本）2017年10月份试题参考解答一、单项选择题（每小题3分，本题共15分）1B 2C 3D 4B 5A二、填空题（每小题3分，本题共15分）6173，48b9v-e+r=210真（或T，或1）三、逻辑公式翻译（每小题6分，本题共12分） 11设P：小明去学校了，Q：小亮去学校了 （2分） 则命题公式为：PQ （6分）12设P：天晴，Q：我们去比赛 （2分）则命题公式为：PQ （6分）四、判断说明题（每小题7分，本题共14分）13正确 （3分）理由：按定义知道，若图G是一个欧拉图，则G中存在欧拉回路， （5分）又因为，欧拉回路也是欧拉路， 所以，满足题中条件的图G存在欧拉路 （7分）14错误 （3分）反例：如图G的结点数比边数多1，但不是树 （7分）说明：按定义有：无向图G是树当且仅当无向图G是连通图且结点数比边数多1或举出符合条件的反例均给分五计算题（每小题12分，本题共36分）15 （1）RS =； （4分）（2）R -1=, ； （8分）（3）s（R）=, , , （12分）16（1）G的图形表示为： （3分）（2）邻接矩阵： （6分）（3）粗线与结点表示的是最小生成树， （10分）权值为10 （12分）17（PQ）R （PQ）R （2分） (PQ)R 析取范式 （5分）(PR)(QR) （7分） (PR )(QQ) (QR) （9分） (PR )(QQ) (QR)(PP) （10分） (PR Q) (PR Q) (QRP) (QRP ) （11分） (PQR)(PQR)(PQR) 主合取范式 （12分）六、证明题（本题共8分）18证明：设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC， (1分)即 xA且xB 或 xA且xC， (2分)也即xAB 或 xAC ， （3分）即 xT，所以ST