离散数学总结课件

1、离,散,数,学,总结,1,离散数学,?,离散数学,(,Discrete Mathematics,),?,离散数学是以,研究离散量的结构和相互间的关系,为主要目,标，其,研究对象一般地是有限个或可数个元素,，因此它充,分,描述了计算机科学离散性的特点,。,集合论,数理逻辑,图论,代数结构,2,离散数学的应用举例,?,关系型数据库的设计,(,关系代数,),?,表达式解析,(,树,),?,优化编译器的构造,(,闭包,),?,编译技术、程序设计语言,(,代数结构,),?,Lisp,和,Prolog,、人工智能、自动推理、机器证明,(,数理逻辑,),?,网络路由算法,(,图论,),?,游戏中的人工智能算

2、法,(,图论、树、博弈论,),?,专家系统,(,集合论、数理逻辑,知识和推理规则的计算机表达,),?,软件工程,团队开发,时间和分工的优化,(,图论,网络、划分,),?,(,各种,),算法的构造、正确性的证明和效率的评估,(,离散数学的,各分支,),3,离散数学的学习要领,?,概念,（正确）,必须掌握好离散数学中大量的概念,?,判断,（准确）,根据概念对事物的属性进行判断,?,推理,（可靠）,根据多个判断推出一个新的判断,4,数理逻辑命题逻辑,?,命题、真值、简单命题与复合命题、命题符号化。,?,联结词：,，,，,?,。,?,命题公式、求公式的赋值。,?,真值表、公式的成真赋值和成假赋值。,?

3、,公式的类型：重言式、矛盾式、可满足式。,?,等值式与等值演算。,?,基本的等值式，其中含：双重否定律、幂等律、交换律、结,合律、分配律、德,摩根律、吸收律、零律、同一律、排中,律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否,定等值式、归谬论。,?,与范式有关的概念：简单合取式、简单析取式、析取范式、,合取范式、极小项、极大项、主析取范式、主合取范式。,5,求给定公式范式的步骤,(1),消去联结词,、,?,(,若存在,),。,AB,?,A,B,A,?,B,?,(A,B),(A,B),(2),否定号的消去,(,利用双重否定律,),或内移,(,利用德摩根律,),。,A,?,A,(A,B),?

4、,A,B,(A,B),?,A,B,(3),利用分配律：利用对的分配律求析取范式，,对的分配律求合取范式。,A,(B,C),?,(A,B),(A,C),A,(B,C),?,(A,B),(A,C),6,求公式,A,的主析取范式的方法与步骤,方法一、等值演算法,(1),化归为析取范式。,(2),除去析取范式中所有永假的析取项。,(3),将析取式中重复出现的合取项和相同的变元合并。,(4),对合取项补入没有出现的命题变元，即添加如,(,p,p,),式，,然后应用分配律展开公式。,方法二、真值表法,(1),写出,A,的真值表。,(2),找出,A,的成真赋值。,(3),求出每个成真赋值对应的极小项（用名称

5、表示），按角标,从小到大顺序析取。,7,求公式,A,的主合取范式的方法与步骤,方法一、等值演算法,(1),化归为合取范式。,(2),除去合取范式中所有永真的合取项。,(3),将合取式中重复出现的析取项和相同的变元合并。,(4),对析取项补入没有出现的命题变元，即添加如,(,p,p,),式，,然后应用分配律展开公式。,方法二、真值表法,(1),写出,A,的真值表。,(2),找出,A,的成假赋值。,(3),求出每个成假赋值对应的极大项（用名称表示），按角标,从小到大顺序析取。,8,数理逻辑命题逻辑,?,推理的形式结构,?,推理的前提,?,推理的结论,?,推理正确,?,判断推理是否正确的方法,?,真

6、值表法,?,等值演算法,?,主析取范式法,?,对于正确的推理，在自然推理系统,P,中构造证明,?,自然推理系统,P,的定义,?,自然推理系统,P,的推理规则,?,附加前提证明法,?,归谬法,9,数理逻辑,一阶逻辑,?,个体词（个体域、全总个体域），谓词,(,特性谓词,),，量词,（全称量词、存在量词）,?,命题符号化：,?,当给定个体域时，在给定个体域内将命题符号化。,?,当没给定个体域时，应在全总个体域内符号化。,?,在符号化时，当引入特性谓词时，注意全称量词与蕴含,联结词的搭配，存在量词与合取联结词的搭配。,?,逻辑有效式、矛盾式、可满足式,?,闭式的性质：在任何解释下均为命题。,?,对给

7、定的解释，会判别公式的真值或不能确定真值。,10,数理逻辑一阶逻辑,?,深刻理解重要的等值式，并能熟练地使用它们。,?,熟练地使用置换规则、换名规则和代替规则。,?,准确地求出给定公式的前束范式（形式可以不唯一）。,?,正确地使用,UI,、,UG,、,EI,、,EG,规则，特别地要注意它们之间,的关系。,?,一定对前束范式才能使用,UI,、,UG,、,EI,、,EG,规则，对不是,前束范式的公式要使用它们，一定先求出公式的前束范式。,?,记住,UI,、,UG,、,EI,、,EG,规则的各自使用条件。,?,在同一推理的证明中，如果既要使用,UI,规则，又要使用,EI,规则，,一定要先使用,EI,

8、规则，后使用,UI,规则，而且,UI,规,则使用的个体常项一定是,EI,规则中使用过的。,?,对于给定的推理，正确地构造出它的证明。,11,集合论集合代数,?,掌握集合的子集、相等、空集、全集、幂集等概念及其符,号化表示。,?,B,?,A,?,?,x,(,x,B,x,A,),?,B,?,A,?,?,x,(,x,?,B,?,x,?,A),?,?,掌握集合的交、并、（相对和绝对）补、对称差、广义交、,广义并的定义及其性质。,?,A,B,x,|,x,A,x,B ,?,A,B,x,|,x,A,x,?,B ,?,?,掌握基本的集合恒等式（等幂律、交换律、结合律、分配,律、德,摩根律、收律、零律、同一律、

9、排中律、矛盾律、,余补律、双重否定律、补交转换律）。,?,运用逻辑演算或利用已知的集合恒等式或包含式证明新的,等式或包含式,。,12,集合恒等式的证明方法,?,逻辑演算法,利用,逻辑等值式,和,推理规则,?,集合演算法,利用,集合恒等式,和,已知结论,13,逻辑演算法的格式,题目：,A,B,证明：,?,x,，,x,A,?, ,?,x,B,所以,A,B,或证,A,?,B,A,?,B,题目：,A,?,B,证明：,?,x,，,x,A,?, ,?,x,B,所以,A,?,B,14,集合演算法的格式,题目：,A,B,证明：,A, ,B,所以,A,B,题目：,A,?,B,证明：,A,?, ,?,B,所以,A

10、,?,B,15,集合论二元关系,?,有序对、笛卡尔积、笛卡尔积的性质,?,二元关系，,A,到,B,的二元关系，,A,上的二元关系，关系的定义,域和值域，关系的逆，关系的合成，关系的定义域、值域、,逆等的主要性质,?,集合,A,上的二元关系的主要性质（自反性，反自反性，对称,性，反对称性，传递性）的定义及判别法，对某些关系证明,它们有或没有中的性质。,?,A,上二元关系的,n,次幂的定义及主要性质,?,等价关系、等价类、商集、划分等概念，以及等价关系与划,分之间的对应,?,偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极,小元、上界、下界、上确界、下确界等概念,16,关系性质的特点,自反性,

11、反自反性,对称性,反对称性,传递性,定义,x,A,x,x,R,x,A,x,x,?,R,x,y,R, ,y,x,R,x,y,R,y,x,R,x,=,y,x,y,R,y,z,R,x,z,集合表达式,I,A,?,R,RI,A,?,R,R,-1,RR,-1,?,I,A,R,?,R,?,R,关系矩阵,主对角线,元素全是,1,主对角线,元素全是,0,矩阵是对称矩,阵,若,r,ij,1,，且,i,j,，则,r,ji,0,对,M,2,中,1,所,在位置，,M,中相应的位,置都是,1,关系图,每个顶点,都有环,每个顶点,都没有环,如果两个顶点,之间有边，一,定是一对方向,相反的边,(,无单,边,),如果两点之间

12、,有边，一定是,一条有向边,(,无双向边,),如果顶点,x,i,到,x,j,有边，,x,j,到,x,k,有边，,则从,x,i,到,x,k,也有边,17,关系性质的证明,通常的证明方法是利用定义证明。,R,在,A,上自反,任取,x,，有,x,A,?,?,x,x,R,R,在,A,上对称,任取,x,y,，有,x,y,R,?,?,y,x,R,R,在,A,上反对称,任取,x,y,，有,x,y,R,y,x,R,?,?,x,y,R,在,A,上传递,任取,x,y, ,y,z,，有,x,y,R,y,z,R,?,?,x,z,R,18,集合论函数,?,掌握函数、,A,到,B,的函数、集合在函数下的像、集合在函,数下

13、的完全原像的概念及表示法；当,A,与,B,都是有穷集时，,会求,A,到,B,的函数的个数。,?,掌握,A,到,B,的函数是单射、满射、和双射的定义及证明方,法。,?,掌握常函数、恒等函数、单调函数、特征函数、自然映射,等概念。,?,掌握复合函数的主要性质和求复合函数的方法。,?,掌握反函数的概念及主要性质。,19,单射和满射的证明方法,?,证明函数,f,: AB,是满射,的，基本方法是：,任取,y,B,，,找到,x,A,(,x,与,y,相关，可能是一个关于,y,的,表达式,),或者证明,存在,x,A,，使得,f,(,x,),y,。,?,证明函数,f,: AB,是单射,的，基本方法是：,假设,A

14、,中,存在,x,1,和,x,2,，使得,f,(,x,1,),f,(,x,2,),，利用已知条件,或者相关的定理最终,证明,x,1,x,2,。,20,集合论基数,?,掌握基数的基本概念,?,掌握可数集合和不可数集合的概念，以及相关结论,21,图论解决实际问题,(1),很多离散问题可以用图模型求解。,(2),为了建立一个图模型，需要决定顶点和边分别代表什么。,(3),在一个图模型中，边经常代表两个顶点之间的关系。,22,图论基本概念,?,理解与图的定义有关的诸多概念，以及它们之间的相互关,系。,?,深刻理解握手定理及其推论的内容，并能熟练地应用它们。,?,深刻理解图同构、简单图、完全图、正则图、子

15、图、补图、,二部图等概念及其它们的性质和相互关系，并能熟练地应,用这些性质和关系。,?,深刻理解通路与回路的定义、相互关系及其分类，掌握通,路与回路的各种不同的表示方法。,?,理解无向图的点连通度、边连通度等概念及其之间的关系，,并能熟练地求出给定的较为简单的图的点连通度与边连通,度。,?,理解有向图连通性的概念及其分类，掌握判断有向连通图,类型的方法。,23,欧拉图和哈密顿图,?,深刻理解欧拉图与半欧拉图的定义及判别定理。,?,会用,Fleury,算法求出欧拉图中的欧拉回路。,?,深刻理解哈密顿图及半哈密顿图的定义。,?,会用破坏哈密顿图应满足的某些必要条件的方法判断某些,图不是哈密顿图。,?,会用满足哈密顿图的充分条件的方法判断某些图是哈密顿,图。,?,严格地分清哈密顿图必要条件和充分条件，千万不能将必,要条件当充