2020电大-离散数学-形考综合练习答案

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．请将语句“所有人都努力学习．”翻译成谓词公式．姓名：学号：得分：教师签名：2答：设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，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,32,12,23,1}S=空集RS=空集SR=空集R-1={1,1,2,13,11,22,21,3}S-1=空集r(S)={1,12,23,34,45,5}s(R)={1,11,21,32,12,23,1}3．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}．(1)写出关系R的表示式；(2)画出关系R的哈斯图；(3)求出集合B的最大元、最小元．3解：(1)R={1,11,21,31,41,51,61,71,82,22,42,62,83,33,64,44,85,56,67,78,8}(2)R的哈斯图为：abdfcehg(3)集合B没有最大元，最小元是24．设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）G的图形为：V1V2V3V4V5（2）邻接矩阵为：（4）补图为：V1V2V3V4V5（3）v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度数为2，v5结点度数为2：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，试4（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解：（1）G的图形：（2）邻接矩阵：（3）最小生成树及权值6．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．解：二叉树如下（方形为给定权）：61301710523117753权：2*5+3*5+5*4+7*3+17*2+31=1317．求PQR的析取范式，合取范式、主析取范式，主合取范式．解：PQR⇔RQR取范式、合取范式、主合取范式都为：RQR主析取范式为：（PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)58．设谓词公式()((,)()(,,))()(,)xPxyzQyxzyRyz．（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元．答：（1）量词x的辖域为：P(x,y)→(∀z)Q(y,x,z)量词z的辖域为：Q(y,x,z)量词y的辖域为：R(y,z)（2）P(x,y)中的x是约束变元，y是自由变元Q(y,x,z)中的x和z是约束变元，y是自由变元R(y,z)中的z是自由变元，y是约束变元9．设个体域为D={a1,a2}，求谓词公式(y)(x)P(x,y)消去量词后的等值式；答：(y)(x)P(x,y)=xP(x,a1)xP(x,a2)=(P(a1,a1)P(a2,a1))(P(a1,a2)P(a2,a2))三、证明题1．对任意三个集合A,B和C，试证明：若AB=AC，且A，则B=C．证明：(1)对于任意a,b∈A×B,其中a∈A,b∈B,因为A×B=A×C,必有a,b∈A×C,其中b∈C因此B⊆C(2)同理,对于任意a,c∈A×C,其中,a∈A,c∈C,因为A×B=A×C，必有a,c∈A×B,其中c∈B,因此C⊆B由(1)(2)，得B=C。62．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：若R与S是集合A上的自反关系,则任意x∈A,x,x∈R,x,x∈S,从而x,x∈R∩S,注意x是A的任意元素,所以R∩S也是集合A上的自反关系.3．设连通图G有k个奇数度的结点，证明在图G中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．故最少要加k/2条边到图G才能使其成为欧拉图．4．试证明(P(QR))PQ与(PQ)等价．证明：(P(QR))PQ⇔(P(QR))PQ⇔(PQR)PQ⇔(PPQ)(QPQ)(RPQ)⇔(PQ)(PQ)(PQR)⇔PQ⇔(PQ)5．试证明：(A∧B)∧(B∨C)∧CA．证明：7(A∧B)∧(B∨C)∧C⇔(A∨B)∧(B∨C)∧C⇔(A∨B)∧(B∧C)∨(C∧C)⇔(A∨B)∧(B∧C)⇔(A∧(B∧C))∨(B∧(B∧C))⇔A∧(B∧C)⇔(A∨B∨C)所以左边不能推出右边的“A”