离散数学总结

1、离散数学q 离散数学离散数学(Discrete Mathematics)q 离散数学是以离散数学是以研究离散量的结构和相互间的关系研究离散量的结构和相互间的关系为主要目为主要目标，其标，其研究对象一般地是有限个或可数个元素研究对象一般地是有限个或可数个元素，因此它充，因此它充分分描述了计算机科学离散性的特点描述了计算机科学离散性的特点。集合论集合论数理逻辑数理逻辑图论图论代数结构代数结构离散数学的应用举例q 关系型数据库的设计关系型数据库的设计(关系代数关系代数)q 表达式解析表达式解析(树树)q 优化编译器的构造优化编译器的构造(闭包闭包)q 编译技术、程序设计语言编译技术、程序设计语言(代

2、数结构代数结构)q Lisp和和Prolog、人工智能、自动推理、机器证明、人工智能、自动推理、机器证明(数理逻辑数理逻辑)q 网络路由算法网络路由算法(图论图论)q 游戏中的人工智能算法游戏中的人工智能算法(图论、树、博弈论图论、树、博弈论)q 专家系统专家系统(集合论、数理逻辑集合论、数理逻辑知识和推理规则的计算机表达知识和推理规则的计算机表达)q 软件工程软件工程团队开发团队开发时间和分工的优化时间和分工的优化(图论图论网络、划分网络、划分)q (各种各种)算法的构造、正确性的证明和效率的评估算法的构造、正确性的证明和效率的评估(离散数学的离散数学的各分支各分支)离散数学的学习要领q概念

3、概念（正确）（正确）必须掌握好离散数学中大量的概念必须掌握好离散数学中大量的概念q判断判断（准确）（准确）根据概念对事物的属性进行判断根据概念对事物的属性进行判断q推理推理（可靠）（可靠）根据多个判断推出一个新的判断根据多个判断推出一个新的判断数理逻辑命题逻辑q 命题、真值、简单命题与复合命题、命题符号化。命题、真值、简单命题与复合命题、命题符号化。q 联结词：联结词：，。q 命题公式、求公式的赋值。命题公式、求公式的赋值。 q 真值表、公式的成真赋值和成假赋值。真值表、公式的成真赋值和成假赋值。 q 公式的类型：重言式、矛盾式、可满足式。公式的类型：重言式、矛盾式、可满足式。q 等值式与等值

4、演算。等值式与等值演算。q 基本的等值式，其中含：双重否定律、幂等律、交换律、结基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德合律、分配律、德摩根律、吸收律、零律、同一律、排中摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。定等值式、归谬论。q 与范式有关的概念：简单合取式、简单析取式、析取范式、与范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。合取范式、极小项、极大项、主析取范式、主合取范式。求给定公式范式的步骤

5、求给定公式范式的步骤(1)消去联结词消去联结词、(若存在若存在)。AB ABAB (AB)(AB)(2)否定号的消去否定号的消去(利用双重否定律利用双重否定律)或内移或内移(利用德摩根律利用德摩根律)。A A(AB) AB(AB) AB(3)利用分配律：利用利用分配律：利用对对的分配律求析取范式，的分配律求析取范式， 对对的分配律求合取范式。的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)求公式A的主析取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)化归为析取范式。化归为析取范式。 (2)除去析取范式中所有永假的析取项。除去析取范式中所有永假的析取项。(

6、3)将析取式中重复出现的合取项和相同的变元合并。将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如对合取项补入没有出现的命题变元，即添加如(pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)写出写出 A 的真值表。的真值表。(2)找出找出 A 的成真赋值。的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。求公式A的主合取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)化归为合取范式。化归为合取

7、范式。 (2)除去合取范式中所有永真的合取项。除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如对析取项补入没有出现的命题变元，即添加如(pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)写出写出 A 的真值表。的真值表。(2)找出找出 A 的成假赋值。的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。数理逻辑命题逻辑q

8、推理的形式结构推理的形式结构推理的前提推理的前提推理的结论推理的结论推理正确推理正确q 判断推理是否正确的方法判断推理是否正确的方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法 q 对于正确的推理，在自然推理系统对于正确的推理，在自然推理系统P中构造证明中构造证明 自然推理系统自然推理系统P的定义的定义自然推理系统自然推理系统P的推理规则的推理规则附加前提证明法附加前提证明法归谬法归谬法数理逻辑 一阶逻辑q 个体词（个体域、全总个体域），谓词个体词（个体域、全总个体域），谓词(特性谓词特性谓词)，量词，量词（全称量词、存在量词）（全称量词、存在量词）q 命题符号化：命题符号化：

9、v当给定个体域时，在给定个体域内将命题符号化。当给定个体域时，在给定个体域内将命题符号化。v当没给定个体域时，应在全总个体域内符号化。当没给定个体域时，应在全总个体域内符号化。v在符号化时，当引入特性谓词时，注意全称量词与蕴含在符号化时，当引入特性谓词时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。联结词的搭配，存在量词与合取联结词的搭配。 q 逻辑有效式、矛盾式、可满足式逻辑有效式、矛盾式、可满足式 q 闭式的性质：在任何解释下均为命题。闭式的性质：在任何解释下均为命题。 q 对给定的解释，会判别公式的真值或不能确定真值。对给定的解释，会判别公式的真值或不能确定真值。数理逻辑

10、一阶逻辑q 深刻理解重要的等值式，并能熟练地使用它们。深刻理解重要的等值式，并能熟练地使用它们。 q 熟练地使用置换规则、换名规则和代替规则。熟练地使用置换规则、换名规则和代替规则。 q 准确地求出给定公式的前束范式（形式可以不唯一）。准确地求出给定公式的前束范式（形式可以不唯一）。 q 正确地使用正确地使用UI、UG、EI、EG规则，特别地要注意它们之间规则，特别地要注意它们之间的关系。的关系。 v一定对前束范式才能使用一定对前束范式才能使用UI、UG、EI、EG规则，对不是规则，对不是前束范式的公式要使用它们，一定先求出公式的前束范式。前束范式的公式要使用它们，一定先求出公式的前束范式。v

11、记住记住UI、UG、EI、EG规则的各自使用条件。规则的各自使用条件。v在同一推理的证明中，如果既要使用在同一推理的证明中，如果既要使用UI规则，又要使用规则，又要使用EI规则，规则，一定要先使用一定要先使用EI规则，后使用规则，后使用UI规则，而且规则，而且UI规规则使用的个体常项一定是则使用的个体常项一定是EI规则中使用过的。规则中使用过的。q 对于给定的推理，正确地构造出它的证明。对于给定的推理，正确地构造出它的证明。集合论集合代数q 掌握集合的子集、相等、空集、全集、幂集等概念及其符掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示。号化表示。vB A x (xB xA) vB

12、 A x (x B x A)vq 掌握集合的交、并、（相对和绝对）补、对称差、广义交、掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质。广义并的定义及其性质。 vAB x | xA xB vAB x | xA x B vq 掌握基本的集合恒等式（等幂律、交换律、结合律、分配掌握基本的集合恒等式（等幂律、交换律、结合律、分配律、德律、德摩根律、收律、零律、同一律、排中律、矛盾律、摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）。余补律、双重否定律、补交转换律）。q 运用逻辑演算或利用已知的集合恒等式或包含式证明新的运用逻辑演算或利用已知的集合恒

13、等式或包含式证明新的等式或包含式等式或包含式 。集合恒等式的证明方法q 逻辑演算法逻辑演算法利用利用逻辑等值式逻辑等值式和和推理规则推理规则q 集合演算法集合演算法利用利用集合恒等式集合恒等式和和已知结论已知结论逻辑演算法的格式题目：题目：AB证明：证明： x， xA xB所以所以 AB或证或证 A B A B 题目：题目：A B证明：证明： x， xA xB所以所以 A B集合演算法的格式题目：题目：AB证明：证明： A B所以所以 AB题目：题目：A B证明：证明：A B所以所以 A B集合论二元关系q 有序对、笛卡尔积、笛卡尔积的性质有序对、笛卡尔积、笛卡尔积的性质 q 二元关系，二元关

14、系，A到到B的二元关系，的二元关系，A上的二元关系，关系的定义上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系的定义域、值域、域和值域，关系的逆，关系的合成，关系的定义域、值域、逆等的主要性质逆等的主要性质 q 集合集合A上的二元关系的主要性质（自反性，反自反性，对称上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质。它们有或没有中的性质。q A上二元关系的上二元关系的n次幂的定义及主要性质次幂的定义及主要性质 q 等价关系、等价类、商集、划分等概念，以及等价关系

15、与划等价关系、等价类、商集、划分等概念，以及等价关系与划分之间的对应分之间的对应 q 偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念小元、上界、下界、上确界、下确界等概念关系性质的特点自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性定义定义xA RxA RR RRR x=yRR集合表达式集合表达式IA RRIARR-1RR-1 IAR R R关系矩阵关系矩阵主对角线主对角线元素全是元素全是1主对角线主对角线元素全是元素全是0 矩阵是对称矩矩阵是对称矩阵阵 若若 rij1，且且 i

16、j，则，则rji0 对对M2中中1所所在位置，在位置，M中相应的位中相应的位置都是置都是1 关系图关系图每个顶点每个顶点都有环都有环每个顶点每个顶点都没有环都没有环 如果两个顶点如果两个顶点之间有边，一之间有边，一定是一对方向定是一对方向相反的边相反的边(无单无单边边) 如果两点之间如果两点之间有边，一定是有边，一定是一条有向边一条有向边(无双向边无双向边) 如果顶点如果顶点 xi到到 xj 有边，有边，xj 到到 xk 有边，有边，则从则从 xi到到 xk 也有边也有边 关系性质的证明通常的证明方法是利用定义证明。通常的证明方法是利用定义证明。R 在在 A 上自反上自反任取任取 x，有，有x

17、A RR 在在 A 上对称上对称任取任取 ，有，有R RR 在在 A 上反对称上反对称任取任取 ，有，有R R xyR 在在 A 上传递上传递任取任取 , ，有，有R R R集合论函数q 掌握函数、掌握函数、A到到B的函数、集合在函数下的像、集合在函的函数、集合在函数下的像、集合在函数下的完全原像的概念及表示法；当数下的完全原像的概念及表示法；当A与与B都是有穷集时，都是有穷集时，会求会求A到到B的函数的个数。的函数的个数。 q 掌握掌握A到到B的函数是单射、满射、和双射的定义及证明方的函数是单射、满射、和双射的定义及证明方法。法。 q 掌握常函数、恒等函数、单调函数、特征函数、自然映射掌握常

18、函数、恒等函数、单调函数、特征函数、自然映射等概念。等概念。 q 掌握复合函数的主要性质和求复合函数的方法。掌握复合函数的主要性质和求复合函数的方法。 q 掌握反函数的概念及主要性质。掌握反函数的概念及主要性质。单射和满射的证明方法q 证明函数证明函数 f : AB是满射是满射的，基本方法是：的，基本方法是：任取任取 yB，找到找到 xA ( x 与与 y 相关，可能是一个关于相关，可能是一个关于 y 的的表达式表达式)或者证明或者证明存在存在xA，使得，使得 f (x)y。q 证明函数证明函数 f : AB是单射是单射的，基本方法是：的，基本方法是：假设假设 A 中中存在存在 x1 和和 x

19、2，使得，使得 f (x1)f (x2)，利用已知条件，利用已知条件或者相关的定理最终或者相关的定理最终证明证明 x1x2。集合论基数q 掌握基数的基本概念掌握基数的基本概念q 掌握可数集合和不可数集合的概念，以及相关结论掌握可数集合和不可数集合的概念，以及相关结论图论解决实际问题(1) 很多离散问题可以用图模型求解。很多离散问题可以用图模型求解。(2) 为了建立一个图模型，需要决定顶点和边分别代表什么。为了建立一个图模型，需要决定顶点和边分别代表什么。(3) 在一个图模型中，边经常代表两个顶点之间的关系。在一个图模型中，边经常代表两个顶点之间的关系。图论基本概念q 理解与图的定义有关的诸多概

20、念，以及它们之间的相互关理解与图的定义有关的诸多概念，以及它们之间的相互关系。系。q 深刻理解握手定理及其推论的内容，并能熟练地应用它们。深刻理解握手定理及其推论的内容，并能熟练地应用它们。q 深刻理解图同构、简单图、完全图、正则图、子图、补图、深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。用这些性质和关系。q 深刻理解通路与回路的定义、相互关系及其分类，掌握通深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。路与回路的各种不同的表示方法。q 理解无向图的点连通度、边连通度等概念及其之间的关系，理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通并能熟练地求出给定的较为简单的图的点连通度与边连通度。度。q 理解有向图连通性的概念及其分类，掌握判断有向连通图理解有向图连通性的概念及其分类，掌握判断