离散数学（本）2020年10月份试题（含答案）.docx
离散数学（本）2020年10月份试题（含答案）离散数学（本）2017年10月份试题 一、单项选择题（每小题3分，本题共15分） 1若集合A=1，2，B=1，1，2，则下列表述正确的是( ) AAÌB BAÎB CAÏB DBÌA 2设A1, 3, 5，B=2, 4, 6，A到B的关系Rx, y| x+1=y，则R= ( ) A Æ B <2, 1 >, <4, 3>, <6, 5> C <1, 2>, <3, 4>, <5, 6> D <1, 1>, <2, 2>, <3, 3> 3无向树G结点数是10，则G的边数是（ ） A 10 B 5 C 20 D 9 4命题“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=<1, 2>, <2, 3>，从B到C的函数g=<2，3>, <3 ，4>，则Ran(g° f)等于 8若图G=<V, E>，其中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=<1，2>, <3，4>，S=<1，1>, <2，2>，试计算 （1）R·S； （2）R -1； （3）s（R） 16图G=<V, E>，其中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Ç (BÈC)=(AÇB) È (AÇC) 离散数学（本）2017年10月份试题 参考解答 一、单项选择题（每小题3分，本题共15分） 1B 2C 3D 4B 5A 二、填空题（每小题3分，本题共15分） 61 73，4 8b 9v-e+r=2 10真（或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）R·S =<1，2>； （4分） （2）R -1=<2，1>, <4，3> ； （8分） （3）s（R）=<1，2>, <3，4>, <2，1>, <4，3> （12分） 16（1）G的图形表示为： （3分） （2）邻接矩阵： （6分） （3）粗线与结点表示的是最小生成树， （10分） 权值为10 （12分） 17（PQ）R ÛØ（PQ）R （2分） Û(ØPØQ)R 析取范式 （5分） Û(ØPR)(ØQR) （7分） Û(ØPR )(QØQ) (ØQR) （9分） Û(ØPR )(QØQ) (ØQR)(PØP) （10分） Û(ØPR Q) (ØPR ØQ) (ØQRP) (ØQRØP ) （11分） Û (PØQR)(ØPQR)(ØPØQR) 主合取范式 （12分） 六、证明题（本题共8分） 18证明： 设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC， (1分) 即 xA且xB 或 xA且xC， (2分) 也即xAB 或 xAC ， （3分） 即 xT，所以SÍT （4分） 反之，若xT，则xAB 或 xAC， （5分） 即xA且xB 或 xA且xC （6分） 也即xA且xBC，即xS，所以TÍS （7分） 因此T=S （8分） 另，可以用恒等式替换的方法证明
