离散数学总结ppt市公开课一等奖百校联赛特等奖课件.pptx

离 散 数 学总结第1页离散数学q离散数学离散数学(Discrete Mathematics)q离散数学是以离散数学是以研究离散量结构和相互间关系研究离散量结构和相互间关系为主要目标，为主要目标，其其研究对象普通地是有限个或可数个元素研究对象普通地是有限个或可数个元素，所以它充分，所以它充分描描述了计算机科学离散性特点述了计算机科学离散性特点。集合论集合论数理逻辑数理逻辑图论图论代数结构代数结构第2页离散数学应用举例q关系型数据库设计关系型数据库设计(关系代数关系代数)q表示式解析表示式解析(树树)q优化编译器结构优化编译器结构(闭包闭包)q编译技术、程序设计语言编译技术、程序设计语言(代数结构代数结构)qLisp和和Prolog、人工智能、自动推理、机器证实、人工智能、自动推理、机器证实(数理逻辑数理逻辑)q网络路由算法网络路由算法(图论图论)q游戏中人工智能算法游戏中人工智能算法(图论、树、博弈论图论、树、博弈论)q教授系统教授系统(集合论、数理逻辑集合论、数理逻辑知识和推理规则计算机表示知识和推理规则计算机表示)q软件工程软件工程团体开发团体开发时间和分工优化时间和分工优化(图论图论网络、划分网络、划分)q(各种各种)算法结构、正确性证实和效率评定算法结构、正确性证实和效率评定(离散数学各分支离散数学各分支)第3页离散数学学习要领q概念概念（正确）（正确）必须掌握好离散数学中大量概念必须掌握好离散数学中大量概念q判断判断（准确）（准确）依据概念对事物属性进行判断依据概念对事物属性进行判断q推理推理（可靠）（可靠）依据多个判断推出一个新判断依据多个判断推出一个新判断第4页数理逻辑命题逻辑q命题、真值、简单命题与复合命题、命题符号化。命题、真值、简单命题与复合命题、命题符号化。q联结词：联结词：，。q命题公式、求公式赋值。命题公式、求公式赋值。q真值表、真值表、公式成真赋值和成假赋值。公式成真赋值和成假赋值。q公式类型：重言式、矛盾式、可满足式。公式类型：重言式、矛盾式、可满足式。q等值式与等值演算。等值式与等值演算。q基本等值式，其中含：双重否定律、幂等律、交换律、结合基本等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德律、分配律、德摩根律、吸收律、零律、同一律、排中律、摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。值式、归谬论。q与范式相关概念：简单合取式、简单析取式、析取范式、合与范式相关概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。取范式、极小项、极大项、主析取范式、主合取范式。第5页求给定公式范式步骤求给定公式范式步骤(1)消去联结词消去联结词、(若存在若存在)。ABABAB(AB)(AB)(2)否定号消去否定号消去(利用双重否定律利用双重否定律)或内移或内移(利用德摩根律利用德摩根律)。AA(AB)AB(AB)AB(3)利用分配律：利用利用分配律：利用对对分配律求析取范式，分配律求析取范式，对对分配律求合取范式。分配律求合取范式。A(BC)(AB)(AC)A(BC)(AB)(AC)第6页求公式A主析取范式方法与步骤方法一、等值演算法方法一、等值演算法(1)化归为析取范式。化归为析取范式。(2)除去析取范式中全部永假析取项。除去析取范式中全部永假析取项。(3)将析取式中重复出现合取项和相同变元合并。将析取式中重复出现合取项和相同变元合并。(4)对合取项补入没有出现命题变元，即添加如对合取项补入没有出现命题变元，即添加如(pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)写出写出A真值表。真值表。(2)找出找出A成真赋值。成真赋值。(3)求出每个成真赋值对应极小项（用名称表示），按角标从求出每个成真赋值对应极小项（用名称表示），按角标从小到大次序析取。小到大次序析取。第7页求公式A主合取范式方法与步骤方法一、等值演算法方法一、等值演算法(1)化归为合取范式。化归为合取范式。(2)除去合取范式中全部永真合取项。除去合取范式中全部永真合取项。(3)将合取式中重复出现析取项和相同变元合并。将合取式中重复出现析取项和相同变元合并。(4)对析取项补入没有出现命题变元，即添加如对析取项补入没有出现命题变元，即添加如(pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)写出写出A真值表。真值表。(2)找出找出A成假赋值。成假赋值。(3)求出每个成假赋值对应极大项（用名称表示），按角标从求出每个成假赋值对应极大项（用名称表示），按角标从小到大次序析取。小到大次序析取。第8页数理逻辑命题逻辑q推理形式结构推理形式结构推理前提推理前提推理结论推理结论推理正确推理正确q判断推理是否正确方法判断推理是否正确方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法q对于正确推理，在自然推理系统对于正确推理，在自然推理系统P中结构证实中结构证实自然推理系统自然推理系统P定义定义自然推理系统自然推理系统P推理规则推理规则附加前提证实法附加前提证实法归谬法归谬法第9页数理逻辑 一阶逻辑q个体词（个体域、全总个体域），谓词个体词（个体域、全总个体域），谓词(特征谓词特征谓词)，量词，量词（全称量词、存在量词）（全称量词、存在量词）q命题符号化：命题符号化：v当给定个体域时，在给定个体域内将命题符号化。当给定个体域时，在给定个体域内将命题符号化。v当没给定个体域时，应在全总个体域内符号化。当没给定个体域时，应在全总个体域内符号化。v在符号化时，当引入特征谓词时，注意全称量词与蕴含在符号化时，当引入特征谓词时，注意全称量词与蕴含联结词搭配，存在量词与合取联结词搭配。联结词搭配，存在量词与合取联结词搭配。q逻辑有效式、矛盾式、可满足式逻辑有效式、矛盾式、可满足式q闭式性质：在任何解释下均为命题。闭式性质：在任何解释下均为命题。q对给定解释，会判别公式真值或不能确定真值。对给定解释，会判别公式真值或不能确定真值。第10页数理逻辑一阶逻辑q深刻了解主要等值式，并能熟练地使用它们。深刻了解主要等值式，并能熟练地使用它们。q熟练地使用置换规则、换名规则和代替规则。熟练地使用置换规则、换名规则和代替规则。q准确地求出给定公式前束范式（形式能够不唯一）。准确地求出给定公式前束范式（形式能够不唯一）。q正正确确地地使使用用UI、UG、EI、EG规规则则，尤尤其其地地要要注注意意它它们们之之间间关系。关系。v一一定定对对前前束束范范式式才才能能使使用用UI、UG、EI、EG规规则则，对对不不是是前束范式公式要使用它们，一定先求出公式前束范式。前束范式公式要使用它们，一定先求出公式前束范式。v记住记住UI、UG、EI、EG规则各自使用条件。规则各自使用条件。v在在同同一一推推理理证证实实中中，假假如如既既要要使使用用UI规规则则，又又要要使使用用EI规规则则，一一定定要要先先使使用用EI规规则则，后后使使用用UI规规则则，而而且且UI规规则则使使用个体常项一定是用个体常项一定是EI规则中使用过。规则中使用过。q对于给定推理，正确地结构出它证实。对于给定推理，正确地结构出它证实。第11页集合论集合代数q掌握集合子集、相等、空集、全集、幂集等概念及其符号掌握集合子集、相等、空集、全集、幂集等概念及其符号化表示。化表示。vB A x(xBxA)vB A x(x B x A)vq掌握集合交、并、（相对和绝对）补、对称差、广义交、掌握集合交、并、（相对和绝对）补、对称差、广义交、广义并定义及其性质。广义并定义及其性质。vABx|xAxBvABx|xAx Bvq掌握基本集合恒等式（等幂律、交换律、结合律、分配律、掌握基本集合恒等式（等幂律、交换律、结合律、分配律、德德摩根律、收律、零律、同一律、排中律、矛盾律、余摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）。补律、双重否定律、补交转换律）。q利用逻辑演算或利用已知集合恒等式或包含式证实新等式利用逻辑演算或利用已知集合恒等式或包含式证实新等式或包含式或包含式。第12页集合恒等式证实方法q逻辑演算法逻辑演算法利用利用逻辑等值式逻辑等值式和和推理规则推理规则q集合演算法集合演算法利用利用集合恒等式集合恒等式和和已知结论已知结论第13页逻辑演算法格式题目：题目：AB证实：证实：x，xAxB所以所以AB或证或证A BA B题目：题目：A B证实：证实：x，xAxB所以所以A B第14页集合演算法格式题目：题目：AB证实：证实：AB所以所以AB题目：题目：A B证实：证实：A B所以所以A B第15页集合论二元关系q有序对、笛卡尔积、笛卡尔积性质有序对、笛卡尔积、笛卡尔积性质q二元关系，二元关系，A到到B二元关系，二元关系，A上二元关系，关系定义域和值上二元关系，关系定义域和值域，关系逆，关系合成，关系定义域、值域、逆等主要性质域，关系逆，关系合成，关系定义域、值域、逆等主要性质q集合集合A上二元关系主要性质（自反性，反自反性，对称性，上二元关系主要性质（自反性，反自反性，对称性，反对称性，传递性）定义及判别法，对一些关系证实它们有反对称性，传递性）定义及判别法，对一些关系证实它们有或没有中性质。或没有中性质。qA上二元关系上二元关系n次幂定义及主要性质次幂定义及主要性质q等价关系、等价类、商集、划分等概念，以及等价关系与划等价关系、等价类、商集、划分等概念，以及等价关系与划分之间对应分之间对应q偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念小元、上界、下界、上确界、下确界等概念第16页关系性质特点自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义xARxA RRRRRx=yRRq集合表集合表示式示式IA RRIARR-1RR-1 IAR R R关系矩阵关系矩阵主对角线主对角线元素全是元素全是1主对角线主对角线元素全是元素全是0矩阵是对称矩矩阵是对称矩阵阵若若rij1，且，且ij，则，则rji0q对对M2中中1所在位所在位置，置，M中对应中对应位置都位置都是是1关系图关系图每个顶点每个顶点都有环都有环每个顶点每个顶点都没有环都没有环q假如两个假如两个顶点之间顶点之间有边，一有边，一定是一对定是一对方向相反方向相反边边(无单无单边边)q假如两点假如两点之间有边，之间有边，一定是一一定是一条有向边条有向边(无双向无双向边边)q假如顶假如顶点点xi到到xj有边，有边，xj到到xk有边，有边，则从则从xi到到xk也也有边有边第17页关系性质证实通常证实方法是利用定义证实。通常证实方法是利用定义证实。R在在A上自反上自反任取任取x，有，有xARR在在A上对称上对称任取任取，有，有RRR在在A上反对称上反对称任取任取，有，有RRxyR在在A上传递上传递任取任取,，有，有RRR第18页集合论函数q掌掌握握函函数数、A到到B函函数数、集集合合在在函函数数下下像像、集集合合在在函函数数下下完完全全原原像像概概念念及及表表示示法法；当当A与与B都都是是有有穷穷集集时时，会会求求A到到B函数个数。函数个数。q掌握掌握A到到B函数是单射、满射、和双射定义及证实方法。函数是单射、满射、和双射定义及证实方法。q掌掌握握常常函函数数、恒恒等等函函数数、单单调调函函数数、特特征征函函数数、自自然然映映射射等概念。等概念。q掌握复合函数主要性质和求复合函数方法。掌握复合函数主要性质和求复合函数方法。q掌握反函数概念及主要性质。掌握反函数概念及主要性质。第19页单射和满射证实方法q证实函数证实函数f:AB是满射是满射，基本方法是：，基本方法是：任取任取yB，找到找到xA(x 与与y 相关，可能是一个关于相关，可能是一个关于y 表表示式示式)或者证实或者证实存在存在xA，使得，使得f(x)y。q证实函数证实函数f:AB是单射是单射，基本方法是：，基本方法是：假设假设A中中存在存在x1和和x2，使得，使得f(x1)f(x2)，利用已知条，利用已知条件或者相关定理最终件或者相关定理最终证实证实x1x2。第20页集合论基数q掌握基数基本概念掌握基数基本概念q掌握可数集合和不可数集合概念，以及相关结论掌握可数集合和不可数集合概念，以及相关结论第21页代数结构-代数系统q组成代数系统基本成份组成代数系统基本成份非空集合非空集合 集合上若干个封闭二元和一元运算集合上若干个封闭二元和一元运算 代数常数代数常数q二元运算性质和特异元素二元运算性质和特异元素q同类型与同种代数系统同类型与同种代数系统q子代数定义与实例子代数定义与实例第22页代数结构知识体系半群与群半群与群环与域环与域格与布尔代数格与布尔代数分类分类代数代数推广推广成份：载体及运算成份：载体及运算公理：运算性质公理：运算性质代数系统组成代数系统组成代数系统代数系统同态与同构同态与同构代数系统间关系代数系统间关系映射映射子代数子代数积代数积代数商代数商代数等价关系等价关系笛卡儿积笛卡儿积子集子集新代数系统新代数系统同种同种同类型同类型产生产生第23页群与半群广群广群二元运算封闭性二元运算封闭性结合律结合律半群半群单位元单位元独异点独异点每个元素可逆每个元素可逆群群交换律交换律交换半群交换半群交换律交换律交换独异点交换独异点交换律交换律Abel群群有限个元素有限个元素有限群有限群生成元生成元循环群循环群实例实例n元置换群元置换群实例实例Klein群群第24页代数结构-环q代代数数系系统统组组成成环环条条件件：组组成成Abel群群；组组成半群；成半群；对于对于+满足分配律。满足分配律。q环环中中运运算算性性质质：a0=0a=0；a(-b)=(-a)b=-(ab)；乘乘法法对对加加法法广广义分配律。义分配律。q环环R非非空空子子集集S组组成成R子子环环条条件件：任任取取a,b 属属于于S,有有a-b 属属于于S；ab属于属于S。q环同态映射定义、判别法及其实例。环同态映射定义、判别法及其实例。第25页代数结构-格与布尔代数q偏偏序序集集组组成成格格条条件件：任任意意二二元元子子集集都都有有最最大大下下界界和和最最小小上上界界。q格实例：正整数因子格，幂集格，子群格。格实例：正整数因子格，幂集格，子群格。q格格性性质质：对对偶偶原原理理，格格中中算算律律（交交换换、结结合合、幂幂等等、吸吸收收），保序性，分配不等式。保序性，分配不等式。q格作为代数系统定义。格作为代数系统定义。q格格L非空子集非空子集S组成组成L子格条件：子格条件：S对对L两个运算封闭。两个运算封闭。q函数函数 组成格同态条件：组成格同态条件：(ab)(a)(b)(ab)(a)(b)q格同态保序性。格同态保序性。第26页代数结构-格与布尔代数q假假如如格格中中一一个个运运算算对对另另一一个个运运算算是是可可分分配配，称称这这个个格格是是分分配格。配格。q分配格两种判别法：分配格两种判别法：不存在与钻石格或五角格同构子格；不存在与钻石格或五角格同构子格；对于任意元素对于任意元素a,b,c,有有abac 且且abac bc。q有界格定义及其实例。有界格定义及其实例。q格中元素补元及其性质（分配格中补元唯一性）。格中元素补元及其性质（分配格中补元唯一性）。q有补格定义。有补格定义。第27页代数结构-格与布尔代数q布尔代数两个等价定义：布尔代数两个等价定义：v有补分配格有补分配格；v有有两两个个二二元元运运算算并并满满足足交交换换律律、分分配配律律、同同一一律律和和补补元元律律代数系统。代数系统。q布尔代数特殊性质：布尔代数特殊性质：双重否定律双重否定律和和德摩根律德摩根律。q子布尔代数定义及其判别。子布尔代数定义及其判别。q布尔代数同态判定：布尔代数同态判定：vf(ab)f(a)f(b)(或或f(ab)f(a)f(b),vf(a)-f(a)q对对于于任任意意自自然然数数n，只只有有一一个个2n 元元有有限限布布尔尔代代数数，就就是是幂幂集代数。集代数。第28页图论处理实际问题(1)很多离散问题能够用图模型求解。很多离散问题能够用图模型求解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间关系。在一个图模型中，边经常代表两个顶点之间关系。第29页图论基本概念q了解与图定义相关很多概念，以及它们之间相互关系。了解与图定义相关很多概念，以及它们之间相互关系。q深刻了解握手定理及其推论内容，并能熟练地应用它们。深刻了解握手定理及其推论内容，并能熟练地应用它们。q深刻了解图同构、简单图、完全图、正则图、子图、补图、深刻了解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们性质和相互关系，并能熟练地应用二部图等概念及其它们性质和相互关系，并能熟练地应用这些性质和关系。这些性质和关系。q深刻了解通路与回路定义、相互关系及其分类，掌握通路深刻了解通路与回路定义、相互关系及其分类，掌握通路与回路各种不一样表示方法。与回路各种不一样表示方法。q了解无向图点连通度、边连通度等概念及其之间关系，并了解无向图点连通度、边连通度等概念及其之间关系，并能熟练地求出给定较为简单图点连通度与边连通度。能熟练地求出给定较为简单图点连通度与边连通度。q了解有向图连通性概念及其分类，掌握判断有向连通图类了解有向图连通性概念及其分类，掌握判断有向连通图类型方法。型方法。第30页欧拉图和哈密顿图q深刻了解欧拉图与半欧拉图定义及判别定理。深刻了解欧拉图与半欧拉图定义及判别定理。q会用会用Fleury算法求出欧拉图中欧拉回路。算法求出欧拉图中欧拉回路。q深刻了解哈密顿图及半哈密顿图定义。深刻了解哈密顿图及半哈密顿图定义。q会用破坏哈密顿图应满足一些必要条件方法判断一些图不会用破坏哈密顿图应满足一些必要条件方法判断一些图不是哈密顿图。是哈密顿图。q会用满足哈密顿图充分条件方法判断一些图是哈密顿图。会用满足哈密顿图充分条件方法判断一些图是哈密顿图。q严格地分清哈密顿图必要条件和充分条件，千万不能将必严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，一样地，也不能将充分条件当成必要要条件当充分条件，一样地，也不能将充分条件当成必要条件。条件。第31页图论树q树树v连通无回路无向图连通无回路无向图v任意两个顶点之间存在唯一路径。任意两个顶点之间存在唯一路径。vmn 1。v任何边均为桥。任何边均为桥。v在任何两个不一样顶点之间加一条新边，在所得图中得在任何两个不一样顶点之间加一条新边，在所得图中得到唯一一个含新边圈。到唯一一个含新边圈。vn 阶非平凡无向树中最少有两片树叶。阶非平凡无向树中最少有两片树叶。q生成树：生成树：G 子图而且是树子图而且是树v树枝（树枝（n-1）、弦（）、弦（m-n+1）、余树（）、余树（m-n+1条边条边）v无向图无向图G 含有生成树当且仅当含有生成树当且仅当G 连通。连通。第32页平面图和着色q平面图及平面嵌入、平面图面与次数。平面图及平面嵌入、平面图面与次数。q极大平面图及性质、极小非平面图。极大平面图及性质、极小非平面图。q欧拉公式及其推广欧拉公式及其推广q平面图边数平面图边数m与顶点数与顶点数n关系、简单平面图关系、简单平面图G中，中，(G)5。q库拉图斯基两个定理。库拉图斯基两个定理。q平面图对偶图。平面图对偶图。q顶点着色与点色数、一些定理。顶点着色与点色数、一些定理。q地图及其面着色、面色数、平面图五色定理。地图及其面着色、面色数、平面图五色定理。q边着色及边色数、关于边着色一些定理。边着色及边色数、关于边着色一些定理。第33页