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