离 散 数 学,总结,离散数学,离散数学(Discrete Mathematics) 离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。,离散数学的应用举例,关系型数据库的设计(关系代数) 表达式解析(树) 优化编译器的构造(闭包) 编译技术、程序设计语言(代数结构) Lisp和Prolog、人工智能、自动推理、机器证明(数理逻辑) 网络路由算法(图论) 游戏中的人工智能算法(图论、树、博弈论) 专家系统(集合论、数理逻辑知识和推理规则的计算机表达) 软件工程团队开发时间和分工的优化(图论网络、划分) (各种)算法的构造、正确性的证明和效率的评估(离散数学的各分支),离散数学的学习要领,概念（正确）必须掌握好离散数学中大量的概念 判断（准确）根据概念对事物的属性进行判断 推理（可靠）根据多个判断推出一个新的判断,求给定公式范式的步骤,(1)消去联结词、(若存在)。AB ABAB (AB)(AB) (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。A A(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规则中使用过的。 对于给定的推理，正确地构造出它的证明。,集合论集合代数,掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示。 B A x (xB xA) B A x (xB xA) 掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质。 AB x | xA xB AB x | xA x B 掌握基本的集合恒等式（等幂律、交换律、结合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）。 运用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式。,集合恒等式的证明方法,逻辑演算法 利用逻辑等值式和推理规则 集合演算法 利用集合恒等式和已知结论,逻辑演算法的格式,题目：AB 证明： x， xA xB 所以 AB 或证 AB AB,题目：AB 证明： x， xA xB 所以 AB,集合演算法的格式,题目：AB 证明： A B 所以 AB,题目：AB 证明：A B 所以 AB,集合论二元关系,有序对、笛卡尔积、笛卡尔积的性质 二元关系，A到B的二元关系，A上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系的定义域、值域、逆等的主要性质 集合A上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质。 A上二元关系的n次幂的定义及主要性质 等价关系、等价类、商集、划分等概念，以及等价关系与划分之间的对应 偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念,关系性质的特点,关系性质的证明,通常的证明方法是利用定义证明。 R 在 A 上自反 任取 x，有 xA R R 在 A 上对称 任取 ，有 R R R 在 A 上反对称 任取 ，有 R R xy R 在 A 上传递 任取 , ，有 R R R,集合论函数,掌握函数、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。,集合论基数,掌握基数的基本概念 掌握可数集合和不可数集合的概念，以及相关结论,代数结构-代数系统,构成代数系统的基本成分 非空集合 集合上若干个封闭的二元和一元运算 代数常数 二元运算性质和特异元素 同类型的与同种的代数系统 子代数的定义与实例,代数结构的知识体系,群与半群,半群,独异点,群,交换半群,交换独异点,Abel群,有限群,循环群,n元置换群,Klein群,代数结构-环,代数系统 构成环的条件： 构成Abel群；构成半群； 对于 + 满足分配律。 环中运算性质：a0=0a=0；a(-b)=(-a)b=-(ab)；乘法对加法的广义分配律。 环 R 的非空子集 S 构成 R 的子环的条件：任取 a,b 属于 S, 有a-b 属于 S；ab属于S。 环同态映射的定义、判别法及其实例。,代数结构-格与布尔代数,偏序集构成格的条件：任意二元子集都有最大下界和最小上界。 格的实例：正整数的因子格，幂集格，子群格。 格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。 格作为代数系统的定义。 格 L 的非空子集 S 构成 L 的子格的条件： S 对 L 的两个运算封闭。 函数 构成格同态的条件： (ab) (a) (b) (ab) (a) (b) 格同态的保序性。,代数结构-格与布尔代数,如果格中一个运算对另一个运算是可分配的，称这个格是分配格。 分配格的两种判别法： 不存在与钻石格或五角格同构的子格； 对于任意元素 a, b, c, 有 abac 且 abac bc。 有界格的定义及其实例。 格中元素的补元及其性质（分配格中补元的唯一性）。 有补格的定义。,代数结构-格与布尔代数,布尔代数的两个等价定义： 有补分配格； 有两个二元运算并满足交换律、分配律、同一律和补元律的代数系统。 布尔代数的特殊性质：双重否定律和德摩根律。 子布尔代数的定义及其判别。 布尔代数同态的判定： f (ab)f (a)f (b) ( 或 f (ab)f (a)f (b), f (a)-f (a) 对于任意自然数 n，只有一个 2n 元的有限布尔代数，就是幂集代数。,图论解决实际问题,(1) 很多离散问题可以用图模型求解。 (2) 为了建立一个图模型，需要决定顶点和边分别代表什么。 (3) 在一个图模型中，边经常代表两个顶点之间的关系。,图论基本概念,理解与图的定义有关的诸多概念，以及它们之间的相互关系。 深刻理解握手定理及其推论的内容，并能熟练地应用它们。 深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些性质和关系。 深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。 理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。 理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。,欧拉图和哈密顿图,深刻理解欧拉图与半欧拉图的定义及判别定理。 会用 Fleury 算法求出欧拉图中的欧拉回路。 深刻理解哈密顿图及半哈密顿图的定义。 会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图。 会用满足哈密顿图的充分条件的方法判断某些图是哈密顿图。 严格地分清哈密顿图必要条件和充分条件，千万不能将必要条件当充分条件，同样地，也不能将充分条件当成必要条件。,图论树,树 连通无回路的无向图 任意两个顶点之间存在唯一的路径。 mn1。 任何边均为桥。 在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 n 阶非平凡的无向树中至少有两片树叶。 生成树： G 的子图并且是树 树枝（n-1）、弦（ m-n+1 ）、余树（ m-n+1 条边 ） 无向图 G 具有生成树当且仅当 G 连通。,平面图和着色,平面图及平面嵌入、平面图的面与次数。 极大平面图及性质、极小非平面图。 欧拉公式及其推广 平面图的边数m与顶点数n的关系、简单平面图G中，(G)5。 库拉图斯基的两个定理。 平面图的对偶图。 顶点的着色与点色数、一些定理。 地图及其面着色、面色数、平面图的五色定理。 边着色及边色数、关于边着色的一些定理。,