资源描述
2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）选择一项：A.数理逻辑B.集合论C.图论D.谓词逻辑题目2答案已保存满分10.00标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）选择一项：A.函数B.关系的概念及其运算C.关系的性质与闭包运算D.几个重要关系题目3答案已保存满分10.00标记题目题干本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B ）讲选择一项：A. 18B. 20C. 19D. 17题目4答案已保存满分10.00标记题目题干本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C ）选择一项：A.集合恒等式与等价关系的判定B.图论部分书面作业C.集合论部分书面作业D. 网上学习问答题目5答案已保存满分10.00标记题目题干课程学习平台左侧第1个版块名称是：（C ）选择一项：A.课程导学B.课程公告C.课程信息D.使用帮助题目6答案已保存满分10.00标记题目题干课程学习平台右侧第5个版块名称是：（D ）选择一项：A.典型例题B.视频课堂C.VOD点播D.常见问题题目7答案已保存满分10.00标记题目题干“教学活动资料”版块是课程学习平台右侧的第（A ）个版块选择一项：A. 6B. 7C. 8D. 9题目8答案已保存满分10.00标记题目题干课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）选择一项：A.复习指导B.视频C.课件D.自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100500字完成后在下列文本框中提交解答：学习计划学习离散数学任务目标：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培养自学能力、抽象思维能力和逻辑推理能力，解决实际问题的能力，以提高专业理论水平。其三是初步掌握处理离散结构所必须的描述工具和方法离散数学的主要内容：第一章节：主要介绍集合及其运算第二章节：主要介绍关系与函数第三章节：主要介绍图的基本概念及性质第四章节：主要介绍几种特殊图第五章节：主要介绍树及其应用第六章节：主要介绍命题逻辑第七章节：主要介绍谓词逻辑离散数学的考核方式分为：了解、理解和掌握。 了解是能正确判别有关概念和方法；理解是能正确表达 有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。离散数学形考任务二若集合Aa,a,1,2Aa,a,1,2，则下列表述正确的是(C )选择一项：A.a,aAa,aAB.1，2A1，2AC.aAaAD.AA题目2答案已保存满分10.00标记题目题干设集合A=1, 2, 3，B=3, 4, 5，C=5, 6, 7，则ABC =(A )选择一项：A.1, 2, 3, 4B.1, 2, 3, 5C.2, 3, 4, 5D.4, 5, 6, 7题目3答案已保存满分10.00标记题目题干设集合A= 1,aa，则P(A) = (D )选择一项：A.1, aaB.,1, aaC.1,a,1,a1,a,1,aD.,1,a,1,a,1,a,1,a题目4答案已保存满分10.00标记题目题干集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=|x+y=10且x, yA，则R的性质为（B）选择一项：A.自反的B.对称的C.传递且对称的D.反自反且传递的题目5答案已保存满分10.00标记题目题干如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有（B）个选择一项：A. 0B. 2C. 1D. 3题目6答案已保存满分10.00标记题目题干设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为( D)选择一项：A.8、2、8、2B.8、1、6、1C.6、2、6、2D.无、2、无、2题目7答案已保存满分10.00标记题目题干设集合A=2, 4, 6, 8，B=1, 3, 5, 7，A到B的关系R=| y = x +1，则R= (A )选择一项：A. , , B. , , C., , D., , 题目8答案已保存满分10.00标记题目题干设集合A=1 , 2, 3上的函数分别为：= ，g= ，h= ，则h=（A）选择一项：A.gB.gC.D.gg题目9答案已保存满分10.00标记题目题干设A、B是两个任意集合，侧A-B =(B )选择一项：A. A=BB. A BC. A BD.B=题目10答案已保存满分10.00标记题目题干设集合A=1，2，3，4，5，偏序关系是A上的整除关系，则偏序集上的元素5是集合A的（C ）选择一项：A.最大元B.最小元C.极大元D.极小元离散数学作业3离散数学集合论部分形成性考核书面作业一、填空题 1设集合，则P(A)-P(B )= 3，1,3，2,3，1,2,3 ，A B= , 2设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 3设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系，则R的有序对集合为 ， 4设集合A=1, 2, 3, 4 ，B=6, 8, 12， A到B的二元关系R那么R1 , 5设集合A=a, b, c, d，A上的二元关系R=, , , ，则R具有的性质是没有任何性质6设集合A=a, b, c, d，A上的二元关系R=, , , ，若在R中再增加两个元素,，则新得到的关系就具有对称性7如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2 个8设A=1, 2上的二元关系为R=|xA，yA, x+y =10，则R的自反闭包为 , 9设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含 , 等元素10设集合A=1, 2，B=a, b，那么集合A到B的双射函数是 , 或, 二、判断说明题（判断下列各题，并说明理由）1若集合A = 1，2，3上的二元关系R=，则(1) R是自反的关系； (2) R是对称的关系解：（1）错误。R不具有自反的关系，因为不属于R。（2）错误。R不具有对称的关系，因为不属于R。 2如果R1和R2是A上的自反关系，判断结论：“R-11、R1R2、R1R2是自反的” 是否成立？并说明理由 解：成立 因为R1和R2是A上的自反关系，即IAR1，IAR2。 由逆关系定义和IAR1，得IA R1-1； 由IAR1，IAR2，得IA R1R2，IA R1R2。所以，R1-1、R1R2、R1R2是自反的。ooooabcd图一ooogefho3若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 解：错误集合A的最大元不存在，a是极大元 4设集合A=1, 2, 3, 4，B=2, 4, 6, 8，判断下列关系f是否构成函数f：，并说明理由(1) f=, , , ； (2)f=, , ；(3) f=, , , 解：（1）不构成函数。因为对于3属于A，在B中没有元素与之对应。（2）不构成函数。因为对于4属于A，在B中没有元素与之对应。（3）构成函数。因为A中任意一个元素都有A中唯一的元素相对应。三、计算题1设，求：(1) (AB)C； (2) (AB)- (BA) (3) P(A)P(C)； (4) AB解：(1) (AB)C=11,3,5=1,3,5(2) (AB)- (BA)=1,2,4,5-1=2,4,5 (3) P(A) =,1,4,1,4 P(C)= ,2,4,2,4 P(A)P(C)=1,1,4(4) AB= (AB)- (BA)= 2,4,52设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=，,3设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=空集 R*S=空集 S*R=空集 R-1=,S-1 =空集r(S)=s(R)= 4设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6(1) 写出关系R的表示式； (2 )画出关系R的哈斯图； (3) 求出集合B的最大元、最小元 解：(1)R=(3)集合B没有最大元，最小元是2125641073891112关系R的哈斯图123469578101112关系R的哈斯图123469578101112关系R的哈斯图(2)关系R的唯斯图四、证明题1试证明集合等式：A (BC)=(AB) (AC)证明：设，若xA (BC)，则xA或xBC，即 xA或xB 且 xA或xC即xAB 且 xAC ，即 xT=(AB) (AC)，所以A (BC) (AB) (AC) 反之，若x(AB) (AC)，则xAB 且 xAC， 即xA或xB 且 xA或xC，即xA或xBC，即xA (BC)，所以(AB) (AC) A (BC)因此A (BC)=(AB) (AC)2试证明集合等式A (BC)=(AB) (AC)证明：设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC，即 xA且xB 或 xA且xC， 也即xAB 或 xAC ，即 xT，所以ST 反之，若xT，则xAB 或 xAC， 即xA且xB 或 xA且xC 也即xA且xBC，即xS，所以TS 因此T=S 3对任意三个集合A, B和C，试证明：若AB = AC，且A，则B = C证明： （1） 对于任意AB，其中aA，bB,因为AB= AC，必有AC,其中b C因此BC（2）同理，对于任意AC,其中，aA，cC，因为AB= AC必有AB，其中cB，因此CB有（1）（2）得B=C4试证明：若R与S是集合A上的自反关系，则RS也是集合A上的自反关系证明：若R与S是集合A上的自反关系，则任意xA,x,xR,x,xS,从而x,xRS,注意x是A的任意元素，所以RS也是集合A上的自反关系离散数学形考任务四设无向图G的邻接矩阵为，则G的边数为(B )选择一项：A. 6B. 5C. 4D. 3题目2答案已保存满分10.00标记题目题干如图一所示，以下说法正确的是 (D ) 选择一项：A.(a,ea,e)是割边B.(a,ea,e)是边割集C.(a,e),(b,c)(a,e),(b,c)是边割集D.(d,ed,e)是边割集题目3答案已保存满分10.00标记题目题干如图三所示，以下说法正确的是 (C ) 选择一项：A.(a,da,d)是割边B.(a,da,d)是边割集C.(a,d),(b,d)(a,d),(b,d)是边割集D.(b,db,d)是边割集题目4答案已保存满分10.00标记题目题干无向图G存在欧拉回路，当且仅当（C ）.选择一项：A. G中所有结点的度数全为偶数B. G中至多有两个奇数度结点C. G连通且所有结点的度数全为偶数D. G连通且至多有两个奇数度结点题目5答案已保存满分10.00标记题目题干若G是一个欧拉图，则G一定是(C )选择一项：A. 平面图B. 汉密尔顿图C. 连通图D. 对偶图题目6答案已保存满分10.00标记题目题干无向树T有8个结点，则T的边数为(B )选择一项：A. 6B. 7C. 8D. 9题目7答案已保存满分10.00标记题目题干已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为(A )选择一项：A. 5B. 8C. 3D. 4题目8答案已保存满分10.00标记题目题干设无向图G的邻接矩阵为，则G的边数为(C )选择一项：A. 1B. 6C. 7D. 14题目9答案已保存满分10.00标记题目题干设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( D )选择一项：A. （a）只是弱连通的B. （b）只是弱连通的C. （c）只是弱连通的D. （d）只是弱连通的题目10答案已保存满分10.00标记题目题干以下结论正确的是(D )选择一项：A. 无向完全图都是欧拉图B. 有n个结点n1条边的无向图都是树C. 无向完全图都是平面图D. 树的每条边都是割边离散数学作业5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题1已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 15 2设给定图G(如右由图所示)，则图G的点割集是 3设G是一个图，结点集合为V，边集合为E，则G的结点 度数之和 等于边数的两倍4无向图G存在欧拉回路，当且仅当G连通且 不含奇数度结点 5设G=是具有n个结点的简单图，若在G中每一对结点度数之和大于等于V ，则在G中存在一条汉密尔顿回路 16161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616166若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 7设完全图K有n个结点(n2)，m条边，当n为奇数时，K中存在欧拉回路8结点数v与边数e满足 e= v1 关系的无向连通图就是树9设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树10设正则5叉树的树叶数为17，则分支数为i = 4 二、判断说明题（判断下列各题，并说明理由）1如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。”2如下图所示的图G存在一条欧拉回路答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。3如下图所示的图G不是欧拉图而是汉密尔顿图 G 答：正确。因为有4个结点的度数为奇数，所以不是欧拉图；而对于图中任意点集中的非空子集，都有V1。其中是从图中删除结点及其关联的边。4设G是一个有7个结点16条边的连通图，则G为平面图答：错误。若G是连通平面图，那么若，而16376，所以不满足定理条件，叙述错误。 17171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717 5设G是一个连通平面图，且有6个结点11条边，则G有7个面答：正确。因为连通平面图满足欧拉公式。即：。由此题条件知6-11+7=2成立。三、计算题1设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） （2） （3） 1、2、4、3、2（4） 2图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 1a。 6 4 2 1 3 。 。 e 5 d （2） （3） b。 。c 2 1 a。 1 e。 3 。d 其权值为：7 3已知带权图G如右图所示 (1) 求图G的最小生成树； (2)计算该生成树的权值答：(1) 1 2 7 5 3 (2) 权值为18。4设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权解： 65 17 48 5 12 17 31 2 3 5 7 权值为65。四、证明题1设G是一个n阶无向简单图，n是大于等于3的奇数证明图G与它的补图中的奇数度顶点个数相等证明：设a为G中任意一个奇数度顶点，由定义，a仍为顶点，为区分起见，记为a, 则deg(a)+deg(a)=n-1, 而n为奇数，则a必为奇数度顶点。由a的任意性，容易得知结论成立。2设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图。故最少要加条边才能使其成为欧拉图。形考任务六设P：我将去打球，Q：我有时间命题 “我将去打球，仅当我有时间” 时符号化为(B )选择一项：A.B.C.D.题目2还未回答满分10.00标记题目题干命题公式(PQ) 的析取范式是 (D )选择一项：A. (PQ)RB. (PQ)RC. (PQ)RD. (PQ)R题目3还未回答满分10.00标记题目题干命题公式(PQ) 析取范式是(A )选择一项：A.PQB.C.D.题目4答案已保存满分10.00标记题目题干下列公式成立的为(D )选择一项：A. PQ PQB. PQ PQC. QP PD. P(PQ)Q题目5答案已保存满分10.00标记题目题干下列公式 (C )为重言式选择一项：A. PQPQB. (Q(PQ) (Q(PQ)C. (P(QP)(P(PQ)D. (P(PQ) Q题目6答案已保存满分10.00标记题目题干设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（D ）选择一项：A.(x)(A(x)B(x)(x)(A(x)B(x)B.(x)(A(x)B(x)(x)(A(x)B(x)C.(x)(A(x)B(x)(x)(A(x)B(x)D.(x)(A(x)B(x)(x)(A(x)B(x)题目7还未回答满分10.00标记题目题干表达式(x)(P(x,y) Q(z) y(R(x,y)z Q(z)中 (x) 中辖域是(B )选择一项：A.P(x,y)B.P(x,y) Q(z)C.R(x,y)D.题目8答案已保存满分10.00标记题目题干 A设个体域D=a,b,c，那么谓词 公式去量词后的等值式为A选择一项：A. (A(a)A(b)A(c)(B(a)B(b)B(b)B. (A(a)A(b)A(c)(B(a)B(b)B(b)C. (A(a)A(b)A(c)(B(a)B(b)B(b)D. (A(a)A(b)A(c)(B(a)B(b)B(b)题目9还未回答满分10.00标记题目题干 A下列等价公式成立的为(A )选择一项：A.PP Q QB.C.D.题目10还未回答满分10.00标记题目题干 A设个体域D是整数集合，则命题xy (xy = y)的真值是（A ）选择一项：A. TB. FC.不确定D.以上说法都不是离散数学作业7离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题1命题公式的真值是1或T 2设P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 （PQ）R 3含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 (PQR)(PQR) 4设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课” 可符号化为 x(P(x) Q(x) 5设个体域Da, b,那么谓词公式消去量词后的等值式为 (A(a) A(b) (B(a) B(b) 6设个体域D1, 2, 3，A(x)为“x大于3”，则谓词公式($x)A(x) 的真值为0(F) 7谓词命题公式(x)(A(x)B(x) C(y)中的自由变元为 y 8谓词命题公式(x)(P(x) Q(x) R(x，y)中的约束变元为 x 三、公式翻译题 1请将语句“今天是天晴”翻译成命题公式设P：今天是晴天。则P。 2请将语句“小王去旅游，小李也去旅游”翻译成命题公式 设P：小王去旅游。 Q：小李去旅游。则PQ 3请将语句“他去旅游，仅当他有时间”翻译成命题公式设P：他去旅游。Q：他有时间。则PQ 4请将语句“41次列车下午五点开或六点开”翻译成命题公式设P：41次列车下午五点。Q：41次列车下午六点开。则P或Q 5请将语句 “有人不去工作”翻译成谓词公式设 A（x）：x是人B（x）：去工作x(A(x) B(x) 6请将语句“所有人都努力工作”翻译成谓词公式设 A（x）：x是人B（x）：努力工作x(A(x) B(x)四、判断说明题（判断下列各题，并说明理由） 1命题公式PP的真值是1。答：错误。因为P和P的否不能同时为真。 2命题公式中的约束变元为y。 答：错误。该式中的约束元为x。3谓词公式中x量词的辖域为P(x,y) (z)Q(x,y,z) 。答：错误。谓词公式中x量词的辖域为P(x,y)。若谓词公式变为），x量词的辖域为P(x,y) (z)Q(x,y,z)。 4下面的推理是否正确，请给予说明(1) (x)A(x) B(x) 前提引入(2) A(y) B(y) US (1)答：错误。因为B(x)不受全称量词x的约束，不能使用全称指定规则。（2）应为A(y) B(x)，换名时，约束元与自由变元不能混淆。四计算题1 求PQR的析取范式，合取范式、主析取范式，主合取范式PQRPQR （析取范式）（PQR） （合取范式）真值表：PQRP原式极小项极大项00011PPP00111PQR01011PQR01111PQR10000PQR10101PQR11001PQR11101PQR主析取范式（PPP）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR） 主合取范式（PQR）2求命题公式(PQ)(RQ) 的主析取范式、主合取范式真值表：PQR（PQ）RQ原式极小项极大项000101PPP001111PQR010011PQR011011PQR100000PQR101011PQR110011PQR111011PQR主析取范式（PPP）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR） 主合取范式（PQR）3设谓词公式（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元答：（1）x的辖域为P（x,y）zQ(x,y,z)z的辖域为Q(x,y,z) y的辖域为R(y,z)(2) 约束变元为P（x,y）zQ(x,y,z)中的xQ(x,y,z) 中的 zR(y,z) 中的y自由变元为P（x,y）zQ(x,y,z)中的yR(y,z)中的z 4设个体域为D=a1, a2，求谓词公式y$xP(x,y)消去量词后的等值式；答：谓词公式y$xP(x,y)消去量词后的等值式为=$xP（x, a1）$xP（x, a2）=P (a1, a2） P (a1, a2）(P(a1, a2） P (a1, a2)五、证明题 1试证明 (P(QR)PQ与 (PQ)等价证明：(P(QR)PQ P(QR)PQPQ（PQ）2试证明(AB) (BC) CA证明：(AB) (BC) C (AB) (BC) C(AB) (B C) (C C)(AB) (BC) 0)(AB) (BC)(A (B C) )( B (B C)(A (B C) )0A (B C) (A B C)故由左边不可推出右边A
展开阅读全文