1、姓名：学号：得分：教师签名：离散数学形成性考核作业 4离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅2. 在线提交 word 文档3. 自备答题纸张，将答题过程手工书写，并拍照上传一、公式翻译题1. 请将语句“小王去上课，小李也去上课”翻译成命题公式答：设P：小王去上课。Q：小李去上课。则命题公式为：PQ2. 请将语句“他去旅游，仅当他有时间”翻译成命题公式答：设P：他去旅游。Q：他有时间。则命题公式为：PQ3. 请将语句 “有人不去工作”翻译成谓词公式答：设A(x
2、)：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）(AB)；（3）AB解：(1)A -B =1,2(2)AB =1,2 (3)AB=,2设 A=1，2，3，4，5，R=|xA，yA 且 x+y4，S=|xA，yA 且 x+y0，试求 R，S，RS，SR，R-1，S-1，r(S)，s(R)解：R=,S=空集RS=空集 SR=空集R-1=,S-1=空集 r(S)= s(R)=3
3、设 A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除关系，B=2, 4, 6(1) 写出关系 R 的表示式；(2) 画出关系 R 的哈斯图；(3) 求出集合 B 的最大元、最小元解：(1)R=(2) R 的哈斯图为：abcgdhef(3) 集合B 没有最大元，最小元是 24设 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）G 的图形为：V1（2）邻接矩阵为：
4、（4）补图为：V1V2V5V2V5V3V4V3V4（3）v1 结点度数为 1，v2 结点度数为 2，v3 结点度数为 3，v4 结点度数为 2，v5 结点度数为 2：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，试3（1）画出 G 的图形；（2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值解：（1）G 的图形：（2）邻接矩阵：（3）最小生成树及权值6. 设有一组权为 2, 3, 5,
5、7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权解：二叉树如下（方形为给定权）：61303117171075523权：2*5+3*5+5*4+7*3+17*2+31=1317. 求 PQR 的析取范式，合取范式、主析取范式，主合取范式解：PQRRQR取范式、合取范式、主合取范式都为：RQR主析取范式为：（PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)48设谓词公式($x)(P(x, y) (z)Q( y, x, z) (y)R( y, z) （1） 试写出量词的辖域；（2） 指出该公式的自由变元和约束变元答：（1）量词x 的辖域为：P(x,y)( z)Q(
6、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，试证明：若AB = AC，且A ，则B = C证明：(1) 对于任意AB,其中
7、aA,bB,因为AB= AC, 必有AC,其中bC 因此 B C(2) 同理,对于任意AC,其中,aA,cC,因为 AB=AC，必有AB,其中cB,因此C B 由(1)(2)，得 B=C。72. 试证明：若 R 与 S 是集合 A 上的自反关系，则 RS 也是集合 A 上的自反关系证明：若R 与S 是集合A 上的自反关系,则任意xA,R,S,从而RS,注意x 是 A 的任意元素,所以RS 也是集合A 上的自反关系.3k设连通图 G 有 k 个奇数度的结点，证明在图 G 中至少要添加条边才能2使其成为欧拉图证明：由定理 3.1.2，任何图中度数为奇数的结点必是偶数，可知 k 是偶数又根据定理 4.1.1 的推论，图 G 是欧拉图的充分必要条件是图 G 不含奇数度结点因此只要在每对奇数度结点之间各加一条边，使图 G 的所有结点的度数变为偶数，成为欧拉图故最少要加 k/2 条边到图 G 才能使其成为欧拉图4试证明 (P(QR)PQ 与 (PQ)等价证明：(P(QR)PQ(P(QR)PQ(PQR)PQ(PPQ)(QPQ)(RPQ)(PQ)(PQ)(PQR)PQ (PQ)5试证明：(AB)(BC)C A证明：(AB)(BC)C(AB)(BC)C(AB)(BC)(CC)(AB)(BC)(A(BC)(B(BC)A(BC)(ABC)所以左边不能推出右边的“A”
