《离散数学形成性考核作业.pdf》由会员分享，可在线阅读，更多相关《离散数学形成性考核作业.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.离散数学形成性考核作业 4 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择：1.可将此次作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅 2.在线提交 word 文档 3.自备答题纸张，将答题过程手工书写，并拍照上传 一、公式翻译题 1请将语句“小王去上课，小李也去上课”翻译成命题公式 设 P：小王去上课。Q:小李去上课。则 PQ 2请将语句“他去旅游，仅当他有时间”翻译成命题公式 设 P：他去旅游。Q:他有时间。则 PQ 3请将语句“有人不去工作”翻译成谓词公式 设 A(x):x 是人 B(x):去工作 x(A(x)B(x
2、)4请将语句“所有人都努力学习”翻译成谓词公式 设 A(x):x 是人 B(x):努力工作 x(A(x)B(x)姓 名：学 号：得 分：教师签名：.二、计算题 1设 A=1,2,1,2，B=1,2,1,2，试计算（1）(AB)；（2）(AB)；（3）AB 解：（1）（AB）=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设 A=1,2,3,4,5,6,7,8，R 是 A 上的整除
3、关系，B=2,4,6(1)写出关系 R 的表示式；(2)画出关系 R 的哈斯图；(3)求出集合 B 的最大元、最小元 解：(1)R=,(2)(3)集合 B 没有最大元，最小元是 2 1 2 3 4 6 5 7 8 关系 R 的哈斯图.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）1v 2v 3v 4v 5v （2）0110010110110110110000100)(DA （3）)d
4、eg(1v1、)deg(2v2、)deg(3v4、)deg(4v3、)deg(5v2 （4）1v 2v 3v 4v 5v .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 权最小的生成树及其权值 b c 解：（1）。2 1 a。6 4 2 1 3 。e 5 d （2）0111110110110011100110110)(DA （3）b c 。2 1 a。1 3 。e d 其权值
5、为：7 .6设有一组权为 2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权 解：65 17 48 5 12 17 31 2 3 5 7 权值为 65。7 求 PQR 的析取范式，合取范式、主析取范式，主合取范式 解：P(QR）=PQR 所以合取范式和析取范式都是PQR 所以主合取范式就是PQR 所以主析取范式就是(PQ R)(PQ R)(PQ R)(PQ R)(PQ R)(PQ R)(PQ R)8设谓词公式()(,)()(,)()(,)x P x yz Q y x zy R y z （1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元 解：(1)量词x 的辖域为
6、 P(x,y)(z)Q(y,x,z)量词z 的辖域为 Q(y,x,z)量词y 的辖域为 R(y,x)(2)P(x,y)中的 x 是约束变元，y 是自由变元 Q(y,x,z)中的 x 和 z 是约束变元，y 是自由变元 R(y,x)中的 x 是自由变元，y 是约束变元 .9设个体域为 D=a1,a2，求谓词公式(y)(x)P(x,y)消去量词后的等值式；解：yxP(x,y)=xP(x,a1)xP(x,a2)=(P(a1,a1)P(a2,a1)(P(a1,a2)P(a1,a2)三、证明题 1对任意三个集合 A,B 和 C，试证明：若 AB=AC，且 A，则 B=C 证明：设 xA，yB，则AB，因
7、为 AB=AC，故 AC，则有 yC，所以 B C 设 xA，zC，则 AC，因为 AB=AC，故AB，则有 zB，所以 CB 故得 A=B 2试证明：若 R 与 S 是集合 A 上的自反关系，则 RS 也是集合 A 上的自反关系 证明：R1和 R2是自反的，x A，R1，R2，则 R1R2，所以 R1R2是自反的 3设连通图 G 有 k 个奇数度的结点，证明在图 G 中至少要添加2k条边才能使其成为欧拉图 证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。又由欧拉图的充要条件是图 G 中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图 G 的所有结点的度数变为偶数，成为欧拉图。故最少要加2k条边才能使其成为欧拉图。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 证明：c 前提引入；cb 前提引入；b 析取三段论；)(BA 前提引入；BA 置换；B 析取三段论。