资源描述：
《2019年秋季离散数学综合考试.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、离散数学形成性考核作业4姓名：严先贵学号1944201250206得分：教师签名：离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1.可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2.在线提交word文档．3.自备答题纸张，将答题过程手工书写，并拍照上传．一、公式翻译题1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．设：P:小王去上课。Q：小李去旅游。则PQ2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．设：P:他去旅游Q：他有时间则PQ3．请
2、将语句“有人不去工作”翻译成谓词公式．设A（x）：x是人B（x）：去工作x(A(x)﹁B(x))4．请将语句“所有人都努力学习．”翻译成谓词公式．设A（x）：x是人B（x）：努力学习x(A(x)B(x))1二、计算题1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（1）(AB)；（2）(A∩B)；（3）A×B．解（1）（AB）={{1},{2}}（2）（A∩B）={1,2}（3）A×B={<1}，1＞，{{1}，2＞2．设A={1，2，3，4，5}，R={
3、xA，yA且x+y4}，S={
4、x
5、A，-1-1，r(S)，s(R)．yA且x+y<0}，试求R，S，RS，SR，R，S解：R={〈1，1〉，〈1，2〉，〈1，3〉，〈2，1〉，〈2，2〉，〈3，1〉}，S=φRS=φSR=φ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
6、的表示式；(2)画出关系R的哈斯图；(3)求出集合B的最大元、最小元．解：R={〈1，1〉，〈1，2〉，〈1，3〉，〈2，1〉，〈2，2〉，〈3，1〉}，S=φRS=φSR=φ2R-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〉}34．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，={2,4,6}．B(1)写出关系R的表示式；
7、(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的哈斯图84632571(3)集合B的没有最大元，最小元是2．4．设G=，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(
8、v4,v5)}，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形．解：(1)v1v2v54v3v4(2)邻接矩阵为0010000110110110110100110(3)v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度数为2，v5结点度数为2(4)补图图形为v1v2v5v3v45．图G=，其中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
9、、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解：（1）G的图形如下：（2）写出G的邻接矩阵53）G权最小的生成树及其权值6．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．66331117175523权为2*5+3*5+5*4+7*3+17*2+31=1317．求PQR的析取范式，合取范式、主析取范式，主合取范式．8．设谓词公式(x)(P(x,y)(z)Q(y,x,z))(y)R(y,z)．（1）试写出量词的辖域；7（2）指出该公式的自由变元和约束变
10、元．9．设个体域为D={a1,a2}，求谓词公式(y)(x)P(x,y)消去量词后的等值式；三、证明题1．对任意三个集合A,B和C，试证明：若AB=AC，且A，则B=C．证明：（1）对于任意〈a，b〉∈，其中a∈A，b∈
