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

1、离散数学形成性考核作业 4姓名：学号：得分：教师签名：离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，完成作业后交给辅导教师批阅2. 在线提交 word 文档3. 自备答题纸张，将答题过程手工书写，并拍照上传一、公式翻译题1请将语句“小王去上课，小李也去上课”翻译成命题公式设 P：小王去上课。 Q ：小李去上课。 则命题公式为： PQ2请将语句“他去旅游，仅当他有时间”翻译成命题公式设 P：他去旅游。 Q ：他有时间 则命题公式为： PQ3请将语句 “有人不去工作”翻译成谓词公式答：设 A(

2、x)：x 是人 B(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)(AB)； (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

3、>,<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+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=空集-1R-1=<1,1>,<2,1><3,1&

4、gt;<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 的最大元、最小元解：(1) R=<1,1><1,2&g

5、t;<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 的哈斯图为：gh(3) 集合 B 没有最大元，最小元是 24设 G=<V，E>，V= v1，v2，v3，v4，v5 ，E= (v1,v3)，(v2,v3)，(v2,v4)，(v

6、3,v4)， (v3,v5)，(v4,v5) ，试(2) 写出其邻接矩阵；(4) 画出其补图的图形(1) 给出 G 的图形表示；(3) 求出每个结点的度数；解：1)G的图形为：2)邻接矩阵为：4)补图为：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，试(1)画出 G

7、的图形；(2)写出 G 的邻接矩阵；(3)求出 G 权最小的生成树及其权值解：2)邻接矩阵：1)G 的图形：3)最小生成树及权值6设有一组权为 2, 3, 5, 7, 17, 31 ，试画出相应的最优二叉树，计算该最优二叉树的权解：二叉树如下(方形为已给定权)：23权： 2*5+3*5+5*4+7*3+17*2+31=1317 求 P Q R 的析取范式，合取范式、主析取范式，主合取范式 解：P Q R ? R QR 取范式、合取范式、主合取范式都为： R Q R 主析取范式为：( P Q R) ( P Q R) ( P Q R)( P Q R) (P Q R) (P Q R) (P Q R)

8、8设谓词公式 ( x)(P(x,y) ( z)Q( y, x, z) ( y)R(y,z) (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,

9、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,其中 aA,b B,因为 A×B= A×C, 必有<a,b> A×C,其中 bC因此 B? C(2) 同理,对于任意<a,c>A×C,其中,aA,cC,因为 A×B= A×C，必有<a,c>A×B,其中

10、cB,因此 C? B由(1)(2) ，得 B=C。2试证明：若 R与S是集合 A上的自反关系，则 RS也是集合 A上的自反关系证明：若 R与 S是集合 A上的自反关系 , 则任意 x A,<x,x> R,<x,x>S,从而<x,x> RS,注意 x是A的任意元素,所以 R S也是集合 A 上的自反关系 .k3设连通图 G有k个奇数度的结点， 证明在图 G中至少要添加 k条边才能2 使其成为欧拉图证明：由定理 3.1.2 ，任何图中度数为奇数的结点必是偶数，可知 k 是偶数又根据定理 4.1.1 的推论，图 G是欧拉图的充分必要条件是图 G不含奇数度 结点因此只要在每对奇数度结点之间各加一条边， 使图 G的所有结点的度数变 为偶数，成为欧拉图故最少要加 k/2 条边到图 G才能使其成为欧拉图4试证明(P(QR)P Q 与(PQ）等价证明：(P(QR)PQ?(P(Q R) PQ?(PQ R)PQ?(PP Q)(QP Q) (R