离散数学（本）2016年7月份试题（含答案）.docx
离散数学（本）2016年7月份试题（含答案）离散数学（本）2016年7月份试题 一、单项选择题（每小题3分，本题共15分） 1若集合A1,2,3,4，B1,3,5，则下列表述正确的是 ( ) AAB BB ÌA CB ¹A DB Í A 2设A1,2,3，B=2,4,6，A到B的关系Rx, y| 2x=y，则R= ( ) A. <1,3>,<2,4>,<3,5> B. <2,1 >,<4,3>,<6,5> C. <1,1>,<2,2>,<3,3> D. <1,2>,<2,4>,<3,6> 3无向图G是棵树，边数是10，则G的结点度数之和是（ ） A. 20 B. 9 C. 10 D. 11 4下面的推理正确的是（ ） 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） US（1） 5设个体域为整数集，则公式“x$y(x+y=2)的说明可为 ( ) A. 任一整数x，对随意整数y满意x+y=2 B. 对任一整数x，存在整数y满意x+y=2 C. 存在一整数x，对随意整数y满意x+y=2 D. 存在一整数x，有整数y满意x+y=2 二、填空题（每小题3分，本题共15分） 6设集合A=1, 2, 3，B=2, 3, 4，C=3, 4, 5，则B(AC)等于 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两个图同构的必要条件包括结点数相等、边数相等与 9设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，v值为5，e值为4则r的值为 10设个体域D1, 2, 3, 4，则谓词公式($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>, <2，3>, <3，4>，S=<1，1>, <2，2>, <3，3>， 试计算（1）R·S； （2）R -1； （3）r（RÇS） 16图G=<V, E>，其中V=a, b, c, d，E= (a, b), (a, c), (a, d), (b, c), (b, d), (c, d) ，对应边的权值依次为1、1、5、2、3及4，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值 17求Ø（PQ）R的析取范式与主合取范式 六、证明题（本题共8分） 18设A，B，C均为随意集合，试证明：A Ç( B - C ) = (AÇ B ) -(A ÇC ) 离散数学（本）2016年1月份试题 参考解答 一、单项选择题（每小题3分，本题共15分） 1C 2D 3A 4D 5B 二、填空题（每小题3分，本题共15分） 61,2,3, 4 73, 4 8度数相同的结点数相等 91 10A(1 ) A(2) A(3) A(4) 三、逻辑公式翻译（每小题6分，本题共12分） 11设P：昨天下雨，Q：今日下雨 （2分） 则命题公式为：PQ （6分） 12设P：下雨，Q：我们去参与竞赛 （2分） 则命题公式为：ØPQ （或 Ø QP） （6分） 四、推断说明题（每小题7分，本题共14分） 13正确 （3分） 因为若图G是一个欧拉图，则图中存在欧拉回路 （5分） 按定义知，欧拉回路也是欧拉路 （7分） 14错误 （3分） 反例：如图G的结点数比边数多1，但不是树 （或：按定义有：无向图G是树当且仅当无向图G是连通图且边数比结点数少1） （7分） 说明：举出符合条件的反例均给分 五计算题（每小题12分，本题共36分） 15解：（1）R·S =<1，2>，<2，3>； （4分） （2）R -1=<2，1>, <3，2>, <4，3>； （8分） （3）r（RÇS）=<1，1>, <2，2> , <3，3>, <4，4> （12分） 16解：G的图形表示为： （3分） 邻接矩阵： （6分） 粗线表示的图是最小的生成树，权为5： （9分） （12分） 17解：Ø（P Q）R Û(Ø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 Ç( B - C )，T=(AÇ B ) -(A ÇC )， 若xS，则xA且xB -C，即 xA，并且xB 且 xÏC， （2分） 所以x(AÇ B )且xÏ(A ÇC )，得xT， （3分） 所以SÍT （4分） 反之，若xT，则x(AÇB ) 且 xÏ(A ÇC )， （5分） 即xA，xB ，且x ÏC，则得xB -C， （6分） 即得xA Ç( B - C )，即xS，所以TÍS （7分） 因此T=S （8分） 另，可以用恒等式替换的方法证明
