您好,欢迎访问三七文档
当前位置:首页 > 幼儿/小学教育 > 小学教育 > 2019年秋季离散数学综合考试
----离散数学形成性考核作业4姓名:严先贵号学1944201250206分:得教师签名:离散数学综合练习书面作业要求:学生提交作业有以下三种方式可供选择:1.可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅.2.在线提交word文档.3.自备答题纸张,将答题过程手工书写,并拍照上传.一、公式翻译题1.请将语句“小王去上课,小李也去上课.”翻译成命题公式.小王去上课。设:P::小李去旅游。QPQ则.2.请将语句“他去旅游,仅当他有时间.”翻译成命题公式他去旅游P:设::他有时间Q则PQ.“有人不去工作”翻译成谓词公式3.请将语句xA(x):是人设):去工作B(xB(x))﹁x(A(x).4.请将语句“所有人都努力学习.”翻译成谓词公式A(x):x是人设B(x):努力学习x(A(x)B(x))1---------二、计算题,1,2}1.设,试计算,B={1,2,{1,2}};B))(A∩1)(AB);(2(.B)A×(3解})1)(AB((2)(A∩B)={1,2}(3)A×B={1},1>,{{1},2>2.设A={1,2,3,4,5},R={x,y|xA,yA且x+y4},S={x,y|xA,11--yA且x+y0},试求R,S,RS,SR,R,S,r(S),s(R).解:R={〈1,1〉,〈1,2〉,〈1,3〉,〈2,1〉,〈2,2〉,〈3,1〉},S=φRS=φR=φS-1}12〉,〈,3〉〉,〈3,1〉,〈1,2〉,〈2,R2={〈1,1〉,〈,1-1=φSr(S)={〈1,1〉,〈2,2〉,〈3,3〉,〈4,4〉,〈5,5〉}s(R)={〈1,1〉,〈1,2〉,〈1,3〉,〈2,1〉,〈2,2〉,〈3,1〉}3.设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6}.(1)写出关系R的表示式;(2)画出关系R的哈斯图;B的最大元、最小元.(3)求出集合解:R={〈1,1〉,〈1,2〉,〈1,3〉,〈2,1〉,〈2,2〉,〈3,1〉},S=φRS=φR=φS2----------1={〈1,1〉,〈2,1〉,〈3,1〉,〈1,2〉,〈2,2〉,〈1R,3〉}-1=φSr(S)={〈1,1〉,〈2,2〉,〈3,3〉,〈4,4〉,〈5,5〉}s(R)={〈1,1〉,〈1,2〉,〈1,3〉,〈2,1〉,〈2,2〉,〈3,1〉}3---------4.设上的整除关系,={2,4,6}.是,={1,2,3,4,5,6,7,8}ARAB(1)写出关系R的表示式;(2)画出关系R的哈斯图;(3)求出集合B的最大元、最小元.解:(1)R={〈1,1〉,〈1,2〉,〈1,3〉,〈1,4〉,〈1,5〉,〈1,6〉,〈1,7〉,〈1,8〉,〈2,2〉,〈2,4〉,〈2,6〉,〈2,8〉,〈3,3〉,〈3,6〉,〈4,4〉,〈4,8〉,〈5,5〉,〈6,6〉,〈7,7〉,〈8,8〉}(2)关系R的哈斯图86432571(3)集合B的没有最大元,最小元是2.4.设G=V,E,V={v,v,v,v,v},E={(v,v),(v,v),(v,v),(v,v),4243331435221(v,v),(v,v)},试5345的图形表示;给出G写出其邻接矩阵;(2)(1)画出其补图的图形.求出每个结点的度数;(3)(4)解:(1)v1vv254vv34---------(2)邻接矩阵为0010000110110110110100110(3)2结点度数为结点度数为23,v,结点度数为v1,vv结点度数为结点度数为2,v54312(4)补图图形为v1v2v5vv435.图G=V,E,其中V={a,b,c,d,e},E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)},对应边的权值依次为2、1、2、3、6、1、4及5,试(1)画出G的图形;(2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.解:(1)G的图形如下:(2)写出G的邻接矩阵5---------权最小的生成树及其权值)3G,试画出相应的最优二叉树,计算该最优62,3,5,7,17,31.设有一组权为二叉树的权.6---------6331117715523权为2*5+3*5+5*4+7*3+17*2+31=131QR的析取范式,合取范式、主析取范式,主合取范式.7.求P8.设谓词公式(x)(P(x,y)(z)Q(y,x,z))(y)R(y,z).)试写出量词的辖域;(17---------(2)指出该公式的自由变元和约束变元.9.设个体域为D={a,a},求谓词公式(y)(x)P(x,y)消去量词后的等值式;21三、证明题1.对任意三个集合A,B和C,试证明:若AB=AC,且A,则B=C.证明:(1)对于任意〈a,b〉∈,其中a∈,b∈,因为,=ABABABAC必有〈a,b〉∈AC,其中b∈C,因此BC。(2)同理,对于任意〈a,c〉∈AC,其中a∈A,c∈C,因为AB,其中c∈,因此,必有〈a,c〉∈。=BBACCAB由(1)、(2)得:B=C.2.试证明:若R与S是集合A上的自反关系,则R∩S也是集合A上的自反关系.证明:若R与S是集合A上的自反关系,则任意x∈A,<x,x>∈R,<x,x>∈S,8---------从而<x,x>∈R∩S,注意x是A的任意元素,所以R∩S也是集合A上的自反关系。k3.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图.k才能使其成为欧拉图.条边到图G故最少要加24.试证明(P(QR))PQ与(PQ)等价.5.试证明:(A∧B)∧(B∨C)∧CA.9---------10-----
本文标题:2019年秋季离散数学综合考试
链接地址:https://www.777doc.com/doc-5691797 .html