2019年秋季离散数学综合考试

1离散数学形成性考核作业4离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1.可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2.在线提交word文档．3.自备答题纸张，将答题过程手工书写，并拍照上传．一、公式翻译题1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．设：P:小王去上课。Q：小李去旅游。则PQ2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．设：P:他去旅游Q：他有时间则PQ3．请将语句“有人不去工作”翻译成谓词公式．设A（x）：x是人B（x）：去工作x(A(x)﹁B(x))4．请将语句“所有人都努力学习．”翻译成谓词公式．设A（x）：x是人B（x）：努力学习x(A(x)B(x))姓名：严先贵学号1944201250206得分：教师签名：2二、计算题1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（1）(AB)；（2）(A∩B)；（3）A×B．解（1）（AB）={{1},{2}}（2）（A∩B）={1,2}（3）A×B={1}，1＞，{{1}，2＞2．设A={1，2，3，4，5}，R={x，y|xA，yA且x+y4}，S={x，y|xA，yA且x+y0}，试求R，S，RS，SR，R-1，S-1，r(S)，s(R)．解：R={〈1，1〉，〈1，2〉，〈1，3〉，〈2，1〉，〈2，2〉，〈3，1〉}，S=φRS=φSR=φR-1={〈1，1〉，〈2，1〉，〈3，1〉，〈1，2〉，〈2，2〉，〈1，3〉}S-1=φr(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的哈斯图；(3)求出集合B的最大元、最小元．解：R={〈1，1〉，〈1，2〉，〈1，3〉，〈2，1〉，〈2，2〉，〈3，1〉}，S=φRS=φSR=φ3R-1={〈1，1〉，〈2，1〉，〈3，1〉，〈1，2〉，〈2，2〉，〈1，3〉}S-1=φr(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〉}44．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}．(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的哈斯图(3)集合B的没有最大元，最小元是2．4．设G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形．解：(1)v1v5v2v3v4156374825(2)邻接矩阵为0110010110110110110000100(3)v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度数为2，v5结点度数为2(4)补图图形为5．图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的邻接矩阵v1v5v2v3v463）G权最小的生成树及其权值6．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．7权为2*5+3*5+5*4+7*3+17*2+31=1317．求PQR的析取范式，合取范式、主析取范式，主合取范式．8．设谓词公式()((,)()(,,))()(,)xPxyzQyxzyRyz．（1）试写出量词的辖域；35251717311368（2）指出该公式的自由变元和约束变元．9．设个体域为D={a1,a2}，求谓词公式(y)(x)P(x,y)消去量词后的等值式；三、证明题1．对任意三个集合A,B和C，试证明：若AB=AC，且A，则B=C．证明：（1）对于任意〈a，b〉∈AB，其中a∈A，b∈B，因为AB=AC，必有〈a，b〉∈AC，其中b∈C，因此BC。（2）同理，对于任意〈a，c〉∈AC，其中a∈A，c∈C，因为AB=AC，必有〈a，c〉∈AB，其中c∈B，因此CB。由（1）、（2）得：B=C．2．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：若R与S是集合A上的自反关系，则任意x∈A,＜x,x＞∈R,＜x,x＞∈S,9从而＜x,x＞∈R∩S,注意x是A的任意元素，所以R∩S也是集合A上的自反关系。3．设连通图G有k个奇数度的结点，证明在图G中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G才能使其成为欧拉图．4．试证明(P(QR))PQ与(PQ)等价．5．试证明：(A∧B)∧(B∨C)∧CA．10