复习要点及练习题市公开课特等奖市赛课微课一等奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学复习及练习题,第1页,第1章 集合,1,、集合表示及其运算,掌握集合表示法；掌握集合相关概念、相关运算和相关性质。重点掌握利用集合运算相关性质化简集合表示式。,2,、自然数和归纳法,掌握两种（第一、第二）数学归纳法特点；能够熟练利用两种归纳法进行问题求解。,3,、笛卡尔乘积,掌握笛卡尔乘积相关概念。,第2页,第2章 二元关系,1,、,二元关系定义及相关概念,2,、二元关系,3,种表示方式：序偶集合；关系矩阵；关系图,3,、,3,种特殊二元关系：相容关系；等价关系；序关系,重点掌握等价关系,4,、关系4,类运算：求补运算；求逆运算；合成运算；闭包运算,重点掌握关系闭包运算。,5,、关系,5,个性质：自反性；反自反性；对称性；反对称性；传递性,第3页,第3章 函数,1,、部分函数,掌握函数及其相关定义：部分函数，全函数，定义域，值域。,掌握满射、内射和双射概念。,2,、基数,集合基数定义，无穷集合之间等势定义，无穷基数分级，以及集合基数必定小于其幂集基数。重点掌握“抽屉原理”应用。,第4页,集合论,填空题,1,、设,A=1,2,，,B=1,2,3,4,5,则,BA=(),A,B=(),。,2,、设,A=1,2,3,4,，,A,上二元关系,R=,，,S=,，,则,R-1,o,S-1=(),S1,o,R-1=(),domR=(),ranS=().,3.,设,A=a,b,，则,P(A)A=().,4.,设集合,A,=,a,，则,A,幂集,P,(,A,)=().,5.,设,A=x,xN,且,2x12,，,R,为,A,上整除关系。若取,S=2,4,9,，则对半序结构,A,R,来说，,S,上界为,(),下界为,(),上确界为,(),下确界为,().S,极大元为,(),极小元为,();,最大元为,(),最小元为,().,6.,设,A,是由,4,个元素组成集合，则,A,上能够定义,(),个不一样二元关系；,(),个不一样自反关系；,(),个不一样反自反关系；,(),个不一样对称关系；,(),个不一样反对称关系。,7.,设,A=a,b,c,则,A,上能够定义（）个不一样等价关系。,8.,等价关系性质为,(),。,9.,等价关系关系矩阵有哪些特点？（）,第5页,集合论,选择题,1.,空集,幂集,(),基数为（）,A.0 B.1 C.2.D.3,2.,设,R,是非空集合,A,上二元关系，则,R,对称闭包,s(R)=().,A.R,IA B.,R,R-1 C.,R,IA D.,R,R-1,3.,关系,R,传递闭包,t(R),能够由,(),来定义。,A.t(R),是包含,R,二元关系,B.t(R),是包含,R,最小传递关系,C.t(R),是包含,R,一个传递关系,D.,任何包含,R,传递关系,4.,设集合,A=1,2,3,4,5,，则下式为真是,(),A.1,A B.2,3,4,A C.5,A D.,A,5.,设,是一个空集，则以下之一哪一个不成立 （）,A.,B.,C.,+D.,+,第6页,集合论,计算或证实题,1.,求,1,1,幂集：,2.,设,A=a,b,c,d R,AA,且,R=,求：,（,1,）,r(R)(2)s(R)(3)t(R),并画出它们关系图。,3.,设,A,=3,(B),=16,(A,B,),=64,试求,B,AB,A-B,A,B,.,4.,设,A=x,x,为,54,因子,，,R,AA,且对任意,x,yA,xRy iff x,整除,y.,（,1,）画出半序集哈斯图；,（,2,）取,A,子集,B=2,3,9,求出,B,最小元、极大元和上确界。,5.,任给,52,个整数，证实其中必定有两数之差或者两数之和能够被,100,整除。,第7页,第4章 命题逻辑,1,、命题和逻辑词,掌握命题逻辑相关概念，熟悉逻辑联接词真值表。重点掌握命题符号化。,2,、合式公式,掌握合式公式定义方法，掌握永真式、永假式以及公式可满足定义。重点掌握合式公式真值表结构方法。,3,、等价与蕴含,掌握等价、对偶式和蕴含概念。重点掌握等价式、蕴含式证实。掌握一些实际应用问题推理。,4,、范式和判定问题,掌握命题公式极大项、极小项、主合取（析取）范式定义。重点掌握主范式求法。,第8页,第5章 谓词逻辑,1.,变元、谓词和量词,掌握一阶谓词逻辑中新引入语法语义概念。重点是掌握将自然语言表示符号化。,2.,合式公式,掌握一阶谓词逻辑中合式公式归纳定义方法；掌握一阶逻辑公式语义解释方法；能够区分变元约束出现和自由出现。,3.,永真式及其判定,掌握一阶谓词逻辑代入定理、置换定理；掌握一些主要等价式和蕴含式；重点掌握求公式前束范式方法。,第9页,数理逻辑,填空题,1,、给定以下命题：,P:,天在下雪,Q:,我进城,R:,我有时间,使用逻辑联接词将以下复合命题符号化,（,1,）假如天不下雪且我有时间，我就进城；,（,2,）我进城必要条件是我有时间；,（,3,）天不在下雪；,（,4,）我进城当且仅当我有时间且天不下雪；,（,5,）天下雪，那么我不进城。,2,、,合式公式,Q (PQ),与,P,关系是,_,。,(,等价、蕴含,),3,、合式公式,(QQ)(PR)P),是永,_,式。,4,、,n,个命题变元可生成（）个不等价合式公式。,第10页,数理逻辑,填空题（续）,5.,设论域为,1,2,，命题,(,x),(,y)(x+y=4),真值为（）。,6.,若论域为非负整数集，,A(x,y),表示,x+y=y,则,(,x)(,y)A(x,y),真值为（）。,7.,设论域,D,4,5,那么谓词公式,(,x)P(x),(,y)Q(y),消去量词后等值式为（）。,8.,(,x)F(x),(y)G(x,y),前束范式为（）。,9.A,B,为集合，命题,AB=,A=B,真值为（）。,第11页,数理逻辑,选择题,1,、以下命题中，不是真命题是 （）,A.,假如,2*2=5,则雪是白。,B.,不存在最大质数。,C.,若太阳从西边落下，则,9+5,小于,10,。,D.,离散数学是计算机科学系一门必修课。,2,、以下式子中，（）是永真。,A.,Q (PQ)B.P(PQ)C.(PQ)P D.(PQ)Q,3.,下面,”,PQ,”,等价说法中，不正确为,(),A.P,是,Q,充分条件,B.Q,是,P,必要条件,C.Q,仅当,P D.,只有,Q,才,P,4.,以下各式中，（）是析取范式。,A.P Q B.P(QR)C.P(QR)D.P(Q R),第12页,数理逻辑,计算题和推理题,1.,一个命题公式,A(P,Q,R),成真指派为,FFF,FFT,FTF,TFF,TTF,求其主范式。,2.,教材上习题,4.4,第,1,题,b),d),3.,教材上习题,4.3,第,2,题,a),4.,在谓词逻辑中将以下命题符号化：,(1),有些大学生不是运动员；,（,2,）会叫狗未必会咬人,（,3,）对于每个实数都存在比它大有理数。,5.,求公式,前束范式,:,教材上习题,5.4,第,1,题,a),6.,三人预计比赛结果，甲说“,A,第一，,B,第二”。乙说“,C,第二，,D,第四”,.,丙说“,A,第二，,D,第四”。结果三人预计得都不全对，但都对了一个，问,A,B,C.D,名次。,第13页,首先要依据题设条件，把原题表示为一个合取范式，然后将合取范式化为主析取范式，每一个极小项就是一个可能结果。在主析取范式中，删除不符题意极小项，其剩下即为所求可能结果。,解：设,P:A,第一,Q:B,第二,R:C,第二,S:D,第四,W:A,第二,由题意应有,:(P,Q),(R,S),(W,S),T,（,表示异或,）,将左边合式公式化为析取范式：,(,P,Q,R,S,W),(,P,Q,R,S,W),(,P,Q,R,S,W),(,P,Q,R,S,W),因为,Q,、,R,、,W,矛盾,故,P,Q,R,S,WF,P,Q,R,S,W,F.,又因为,P,Q,R,S,W,表示,A,第一,B,不是第二,C,不是第二,D,第四,A,不是第二,.,由此可知,A,B,C,D,都不是第二，矛盾,.,所以 原式,P,Q,R,S,W,T,即,A,不是第一,B,是第二,C,不是第二,D,第四,A,不是第二,由此可得：,C,第一,B,第二,A,第三,D,第四。,第14页,第7章 图论,1,基本概念：,(1),掌握有向图、无向图及其相关要素（节点、边、出度、入度、度）数学定义及记号,;,(2),掌握完全图、连通图、补图、子图、同构图等基本概念；,(3),掌握和应用握手定理；,2,图矩阵表示方法：,熟悉了解图邻接矩阵表示法3,树与有向树：,(1),掌握树几个等价定义；,(2),熟悉了解完全二叉树结构和性质；,(3),掌握哈夫曼树算法；,(4),掌握用“避圈法”结构加权图最小生成树。,4,欧拉图、哈米尔顿图、二部图与平面图：,掌握上述各特殊图定义、性质和判断方法,第15页,图论,填空题,1,、设,G,是,n,个结点简单无向连通图，那么其边最少条数为（）,;,边最多条数为（）。,2,、无向图,G,是由,k(k2),棵树组成森林，最少要添加（）条边才能使,G,成为一棵树。,3,、设用,G,是由,4,棵树组成一个树林，,G,有,15,个结点，则,G,有,(),条边。,4,、一颗完全二叉树高为,4,，则它最少有（）片树叶，至多有,(),片树叶。,5,、设,G,是一棵二叉树，,G,有,10,个点，其中,6,个叶点，则,G,总度数为（），分枝点数为,().,6,、给定一个图,G,邻结矩阵,X,，求,vi,至,vj,长度为,3,路径条数（）。,7,、无向连通图,G,是欧拉图，当且仅当,G,中每一个顶点度数为,().,第16页,图论,选择题,1,、一个无向图有,4,个结点，其中,3,个度数为,2,3,3,则第,4,个结点度数不可能为（）。,A.,0 B.1 C).2 D.4,2,、设无向图中有,8,条边，有两个,3,度顶点和一个,4,度顶点，其余顶点度为,2,，则该图顶点数是,(),。,A,3B,4 C,5 D,63,、在有,5,个结点图中,奇结点个数不可能为（）。,(A)0 (B)1 (C)2 (D)4,4,、二部图,K,2,3,是（）。,A.,欧拉图,B.,哈密顿图,C.,非平面图,D.,平面图,5,、以下命题正确是（）。,A.,欧拉图子图一定是欧拉图,B.,哈密顿图子图一定是哈密顿图,C.,平面图子图一定是平面图,D.,树子树图一定是树,第17页,图论,计算或证实题,三、计算或证实题,1,、给定权,1,4,9,16,25,36,49,64,81,100,试结构一棵最优二叉树，并求其叶加权长度。,2,、用“避圈法,”,对教材,P137,图,7.3.8,求出其一棵最小生成树。,3,、证实：一棵多于一个顶点树最少有两片树叶。,4,、画出二部图,K3,4,问该图是平面图吗？为何？,5,、平时布置作业题（略）。,第18页,教材上习题答案：,可参看：,尤其当你对一些“数学密集型”领域如视频、图像处理等有兴趣时，这些知识将成为你手中利器。,（,5,）培养团体精神，学会与人合作。今天软件工程早已经不是一个人能够单独操作，而必须靠团体合作才能成功。不知道合作人是不能成大器。大家要多去寻找能够与人一起做项目标机会。,（,6,）激励创新意识，培养好奇心，不要死记硬背。没有掌握某种算法技术根本原理，就不会有应变和创新能力。想成为一位好程序员,主要是要养成钻研，好奇，创新，动手，合作优异习惯，不满足于填鸭，不满足于考试交差，不满足于表象。这不是学几门课能够一蹴而就。,（7）有策略地“打工”。在不影响学业前提下，寻找真正有意义暑期工作或兼职。去找一个重视技术企业，在一个好“老板”指导下完成真正会被用户使用程序。不要急于去一个要你做“头”而独挡一面地方，因为向他人学习才是你目标。,第21页,希望大家都能把握机会，养成好学习习惯，把,专业主干课程,学精学透；希望大家都能有一个美好未来！,第22页,