2024年离散数学形成性考核作业离散数学综合练习书面作业VIP专享VIP免费

离散数学形成性考核作业4离散数学综合练习书面作业规定：学生提交作业有如下三种方式可供选择：1.可将本次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完毕作业后交给辅导教师批阅．2.在线提交word文档．3.自备答题纸张，将答题过程手工书写，并拍照上传．一、公式翻译题1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．设Ｐ：小王去上课Ｑ:小李去上课则：命题公式Ｐ∧Ｑ2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．设Ｐ：他去旅游Ｑ：他有时间则命题公式为Ｐ→Ｑ3．请将语句“有人不去工作”翻译成谓词公式．设Ａ（x）:x是人Ｂ（x）：去工作则谓词公式为x（A(x)∧－B（x）)4．请将语句“所有人都努力学习．”翻译成谓词公式．设A（x）:x是人B（x）:努力学习姓名：学号：得分：教师签名：则谓词公式为x（A（x）∧B（x））二、计算题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>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1,2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>}2．设A={1，2，3，4，5}，R={|xA，yA且x+y4}，S={|xA，yA且x+y<0}，试求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的最大元、最小元．4．设G=，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）（2）（3）deg(v1)=1,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2(4)5．图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、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解：（1）（2）（3）其中权值是：76．设有一组权为2,3,5,7,17,31，试画出对应的最优二叉树，计算该最优二叉树的权．解：权值：657．求PQR的析取范式，合取范式、主析取范式，主合取范式．解：8．设谓词公式．（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元．9．设个体域为D={a1,a2}，求谓词公式(y)(x)P(x,y)消去量词后的等值式；三、证明题1．对任意三个集合A,B和C，试证明：若AB=AC，且A，则B=C．证明：设xA,yB,∈∈则∈AB由于AB＝AC，故∈AC,则有yC∈因此BC设xA,zC∈∈，则∈AC由于AB＝AC，故∈AB,则有zB∈因此CB故得A＝B2．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：R和S是自反的，xA,R,S∈∈∈则R∈S因此RS是自反的3．设连通图G有k个奇数度的结点，证明在图G中至少要添加k2条边才能使其成为欧拉图．4．试证明(P(QR))PQ与(PQ)等价．5．试证明：(A∧B)(∧B∨C)∧CA．