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-----