离散数学总结.ppt

离散数学,总结,离散数学,离散数学(DiscreteMathematics)离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。,离散数学的应用举例,关系型数据库的设计(关系代数)表达式解析(树)优化编译器的构造(闭包)编译技术、程序设计语言(代数结构)Lisp和Prolog、人工智能、自动推理、机器证明(数理逻辑)网络路由算法(图论)游戏中的人工智能算法(图论、树、博弈论)专家系统(集合论、数理逻辑知识和推理规则的计算机表达)软件工程团队开发时间和分工的优化(图论网络、划分)(各种)算法的构造、正确性的证明和效率的评估(离散数学的各分支),离散数学的学习要领,概念（正确）必须掌握好离散数学中大量的概念判断（准确）根据概念对事物的属性进行判断推理（可靠）根据多个判断推出一个新的判断,数理逻辑命题逻辑,命题、真值、简单命题与复合命题、命题符号化。联结词：，。命题公式、求公式的赋值。真值表、公式的成真赋值和成假赋值。公式的类型：重言式、矛盾式、可满足式。等值式与等值演算。基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。与范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。,求给定公式范式的步骤,(1)消去联结词、(若存在)。ABABAB(AB)(AB)(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。AA(AB)AB(AB)AB(3)利用分配律：利用对的分配律求析取范式，对的分配律求合取范式。A(BC)(AB)(AC)A(BC)(AB)(AC),求公式A的主析取范式的方法与步骤,方法一、等值演算法(1)化归为析取范式。(2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。方法二、真值表法(1)写出A的真值表。(2)找出A的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。,求公式A的主合取范式的方法与步骤,方法一、等值演算法(1)化归为合取范式。(2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。方法二、真值表法(1)写出A的真值表。(2)找出A的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。,数理逻辑命题逻辑,推理的形式结构推理的前提推理的结论推理正确判断推理是否正确的方法真值表法等值演算法主析取范式法对于正确的推理，在自然推理系统P中构造证明自然推理系统P的定义自然推理系统P的推理规则附加前提证明法归谬法,数理逻辑一阶逻辑,个体词（个体域、全总个体域），谓词(特性谓词)，量词（全称量词、存在量词）命题符号化：当给定个体域时，在给定个体域内将命题符号化。当没给定个体域时，应在全总个体域内符号化。在符号化时，当引入特性谓词时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。逻辑有效式、矛盾式、可满足式闭式的性质：在任何解释下均为命题。对给定的解释，会判别公式的真值或不能确定真值。,数理逻辑一阶逻辑,深刻理解重要的等值式，并能熟练地使用它们。熟练地使用置换规则、换名规则和代替规则。准确地求出给定公式的前束范式（形式可以不唯一）。正确地使用UI、UG、EI、EG规则，特别地要注意它们之间的关系。一定对前束范式才能使用UI、UG、EI、EG规则，对不是前束范式的公式要使用它们，一定先求出公式的前束范式。记住UI、UG、EI、EG规则的各自使用条件。在同一推理的证明中，如果既要使用UI规则，又要使用EI规则，一定要先使用EI规则，后使用UI规则，而且UI规则使用的个体常项一定是EI规则中使用过的。对于给定的推理，正确地构造出它的证明。,集合论集合代数,掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示。BAx(xBxA)BAx(xBxA)掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质。ABx|xAxBABx|xAxB掌握基本的集合恒等式（等幂律、交换律、结合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）。运用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式。,集合恒等式的证明方法,逻辑演算法利用逻辑等值式和推理规则集合演算法利用集合恒等式和已知结论,逻辑演算法的格式,题目：AB证明：x，xAxB所以AB或证ABAB,题目：AB证明：x，xAxB所以AB,集合演算法的格式,题目：AB证明：AB所以AB,题目：AB证明：AB所以AB,集合论二元关系,有序对、笛卡尔积、笛卡尔积的性质二元关系，A到B的二元关系，A上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系的定义域、值域、逆等的主要性质集合A上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质。A上二元关系的n次幂的定义及主要性质等价关系、等价类、商集、划分等概念，以及等价关系与划分之间的对应偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念,关系性质的特点,关系性质的证明,通常的证明方法是利用定义证明。R在A上自反任取x，有xARR在A上对称任取，有RRR在A上反对称任取，有RRxyR在A上传递任取,，有RRR,集合论函数,掌握函数、A到B的函数、集合在函数下的像、集合在函数下的完全原像的概念及表示法；当A与B都是有穷集时，会求A到B的函数的个数。掌握A到B的函数是单射、满射、和双射的定义及证明方法。掌握常函数、恒等函数、单调函数、特征函数、自然映射等概念。掌握复合函数的主要性质和求复合函数的方法。掌握反函数的概念及主要性质。,单射和满射的证明方法,证明函数f:AB是满射的，基本方法是：任取yB，找到xA(x与y相关，可能是一个关于y的表达式)或者证明存在xA，使得f(x)y。证明函数f:AB是单射的，基本方法是：假设A中存在x1和x2，使得f(x1)f(x2)，利用已知条件或者相关的定理最终证明x1x2。,集合论基数,掌握基数的基本概念掌握可数集合和不可数集合的概念，以及相关结论,图论解决实际问题,(1)很多离散问题可以用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。,图论基本概念,理解与图的定义有关的诸多概念，以及它们之间的相互关系。深刻理解握手定理及其推论的内容，并能熟练地应用它们。深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。,欧拉图和哈密顿图,深刻理解欧拉图与半欧拉图的定义及判别定理。会用Fleury算法求出欧拉图中的欧拉回路。深刻理解哈密顿图及半哈密顿图的定义。会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地