《离散数学形成性考核作业4.docx》由会员分享，可在线阅读，更多相关《离散数学形成性考核作业4.docx（16页珍藏版）》请在三一文库上搜索。
1、.姓 名：学 号：得 分： 教师签名： 离散数学形成性考核作业4离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅2. 在线提交word文档3. 自备答题纸张，将答题过程手工书写，并拍照上传一、公式翻译题 1请将语句“小王去上课，小李也去上课”翻译成命题公式 设P:小王去上课。 Q:小李去上课。则命题公式PQ 2请将语句“他去旅游，仅当他有时间”翻译成命题公式设P:他去旅游。Q:他有时间。则命题公式PQ 3请将语句 “有人不去工作”翻译成谓词公式设A(x):x是人 B(x)
2、:去工作 则谓词公式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) AB=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
3、>,<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=空集RS=空集SR=空集 R-1=<1,1>,<2,1><3,1><
4、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><1,3&
5、gt;<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的哈斯图为(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
6、) ，试(1) 给出G的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形解：（1）oooov1ov5v2v3v4(2) 邻接矩阵为(3) v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度数为2，v5结点度数为2(4) 补图图形为oooov1ov5v2v3v45图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的图形； （2
7、）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值解：（1）G的图形如下：（2）写出G的邻接矩阵（3）G权最小的生成树及其权值6设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权35251071731173465权为 2*5+3*5+5*4+7*3+17*2+31=1317 求P®QÚR的析取范式，合取范式、主析取范式，主合取范式答：P®QÚRØ PÚQÚR析取范式、合取范式、主合取范式都为Ø PÚQÚR主析取范式为（Ø PØ
8、QØ R）Ú（Ø PØ Q R）Ú（Ø PQØ R）Ú（Ø P Q R）Ú（PØ QR）Ú（PQØ R）Ú（ PQ R）8设谓词公式（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元（1） 量词 x的辖域为 量词 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，求谓词公
9、式("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(a1, a2)三、证明题 1对任意三个集合A, B和C，试证明：若A´B = A´C，且A¹，则B = C答：(1)对于任意<a,b>A×B,其中aA,bB,因为A×B= A×C,必有<a,b>A×C,其中b C因此BC(2)同理,对于任意<a,c
10、>A×C,其中,aA,cC,因为A×B= A×C必有<a,c>A×B,其中cB,因此CB有(1)(2)得B=C2试证明：若R与S是集合A上的自反关系，则RS也是集合A上的自反关系答：若R与S是集合A上的自反关系,则任意xA,<x,x>R,<x,x>S,从而<x,x>RS,注意x是A的任意元素,所以RS也是集合A上的自反关系.3设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数又根据定理4.1.1的推论，图G是
11、欧拉图的充分必要条件是图G不含奇数度结点因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图故最少要加条边到图G才能使其成为欧拉图 4试证明 (P®(QÚØR)ÙØPÙQ与Ø (PÚØQ)等价证明：(P®(QÚØR)ÙØPÙQ(ØPÚ (QÚØR) ÙØPÙQ (ØPÚ QÚØR) ÙØP
12、ÙQ (ØPÙØPÙ Q) Ú( QÙØPÙQ) Ú(ØRÙØPÙQ) (ØPÙQ) Ú(ØPÙQ) Ú(ØPÙQÙØR) ØPÙQ (吸收律) Ø (PÚØQ) （摩根律）5试证明：Ø(AØB)(ØBC)ØC ÞØA证明：Ø(AØB)(ØBC)ØC ÞØA(ØAB)(ØBC)ØC (ØAB)（(ØBØC)（CØC)） (ØAB)（(ØBØC)0） (ØAB)(ØBØC) （ØA（ØBØC) ）（B（ØBØC） (ØAØBØC) 0 ØAØBØC Ø （ABC）故由左边不可推出右边 A；.