《离散数学总结》由会员分享，可在线阅读，更多相关《离散数学总结（33页珍藏版）》请在金锄头文库上搜索。
1、离离 散散 数数 学学总结总结离散数学q 离散数学(Discrete Mathematics)q 离散数学是以研究离散量的结构和相互间的关系为主要目 标，其研究对象一般地是有限个或可数个元素，因此它充 分描述了计算机科学离散性的特点。集合论数理逻辑图论代数结构离散数学的应用举例q 关系型数据库的设计(关系代数) q 表达式解析(树) q 优化编译器的构造(闭包) q 编译技术、程序设计语言(代数结构) q Lisp和Prolog、人工智能、自动推理、机器证明(数理逻辑) q 网络路由算法(图论) q 游戏中的人工智能算法(图论、树、博弈论)q 专家系统(集合论、数理逻辑知识和推理规则的计算机表
2、达 ) q 软件工程团队开发时间和分工的优化(图论网络、划分 ) q (各种)算法的构造、正确性的证明和效率的评估(离散数学的 各分支)离散数学的学习要领q概念（正确） 必须掌握好离散数学中大量的概念q判断（准确） 根据概念对事物的属性进行判断q推理（可靠） 根据多个判断推出一个新的判断数理逻辑命题逻辑q 命题、真值、简单命题与复合命题、命题符号化。 q 联结词：，。q 命题公式、求公式的赋值。 q 真值表、公式的成真赋值和成假赋值。 q 公式的类型：重言式、矛盾式、可满足式。 q 等值式与等值演算。 q 基本的等值式，其中含：双重否定律、幂等律、交换律、结 合律、分配律、德摩根律、吸收律、零
3、律、同一律、排中 律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否 定等值式、归谬论。 q 与范式有关的概念：简单合取式、简单析取式、析取范式、 合取范式、极小项、极大项、主析取范式、主合取范式。求给定公式范式的步骤(1)消去联结词、(若存在)。 AB AB AB (AB)(AB) (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 A A (AB) AB (AB) AB (3)利用分配律：利用对的分配律求析取范式，对的分配律求合取范式。 A(BC) (AB)(AC) A(BC) (AB)(AC)求公式A的主析取范式的方法与步骤方法一、等值演算法 (1)化归为析取范式。 (2)除
4、去析取范式中所有永假的析取项。 (3)将析取式中重复出现的合取项和相同的变元合并。 (4)对合取项补入没有出现的命题变元，即添加如(pp)式， 然后应用分配律展开公式。 方法二、真值表法 (1)写出 A 的真值表。 (2)找出 A 的成真赋值。 (3)求出每个成真赋值对应的极小项（用名称表示），按角标 从小到大顺序析取。求公式A的主合取范式的方法与步骤方法一、等值演算法 (1)化归为合取范式。 (2)除去合取范式中所有永真的合取项。 (3)将合取式中重复出现的析取项和相同的变元合并。 (4)对析取项补入没有出现的命题变元，即添加如(pp)式， 然后应用分配律展开公式。 方法二、真值表法 (1)
5、写出 A 的真值表。 (2)找出 A 的成假赋值。 (3)求出每个成假赋值对应的极大项（用名称表示），按角标 从小到大顺序析取。数理逻辑命题逻辑q 推理的形式结构 推理的前提 推理的结论 推理正确q 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 q 对于正确的推理，在自然推理系统P中构造证明 自然推理系统P的定义 自然推理系统P的推理规则 附加前提证明法 归谬法数理逻辑 一阶逻辑q 个体词（个体域、全总个体域），谓词(特性谓词)，量词（ 全称量词、存在量词）q 命题符号化：v当给定个体域时，在给定个体域内将命题符号化。v当没给定个体域时，应在全总个体域内符号化。v在符号化时，当引
6、入特性谓词时，注意全称量词与蕴含 联结词的搭配，存在量词与合取联结词的搭配。 q 逻辑有效式、矛盾式、可满足式 q 闭式的性质：在任何解释下均为命题。 q 对给定的解释，会判别公式的真值或不能确定真值。数理逻辑一阶逻辑q 深刻理解重要的等值式，并能熟练地使用它们。 q 熟练地使用置换规则、换名规则和代替规则。 q 准确地求出给定公式的前束范式（形式可以不唯一）。 q 正确地使用UI、UG、EI、EG规则，特别地要注意它们之间 的关系。 v一定对前束范式才能使用UI、UG、EI、EG规则，对不是 前束范式的公式要使用它们，一定先求出公式的前束范式 。 v记住UI、UG、EI、EG规则的各自使用条
7、件。 v在同一推理的证明中，如果既要使用UI规则，又要使用EI 规则，一定要先使用EI规则，后使用UI规则，而且UI规则 使用的个体常项一定是EI规则中使用过的。 q 对于给定的推理，正确地构造出它的证明。集合论集合代数q 掌握集合的子集、相等、空集、全集、幂集等概念及其符 号化表示。 vB A x (xB xA) vB A x (xB xA) v q 掌握集合的交、并、（相对和绝对）补、对称差、广义交 、广义并的定义及其性质。 vAB x | xA xB vAB x | xA x B v q 掌握基本的集合恒等式（等幂律、交换律、结合律、分配 律、德摩根律、收律、零律、同一律、排中律、矛盾律
8、、 余补律、双重否定律、补交转换律）。 q 运用逻辑演算或利用已知的集合恒等式或包含式证明新的 等式或包含式 。集合恒等式的证明方法q 逻辑演算法 利用逻辑等值式和推理规则q 集合演算法 利用集合恒等式和已知结论逻辑演算法的格式题目：AB 证明： x，xA xB 所以 AB 或证 AB AB 题目：AB证明： x，xA xB所以 AB集合演算法的格式题目：AB 证明： A B 所以 AB题目：AB证明：A B所以 AB集合论二元关系q 有序对、笛卡尔积、笛卡尔积的性质 q 二元关系，A到B的二元关系，A上的二元关系，关系的定义 域和值域，关系的逆，关系的合成，关系的定义域、值域、 逆等的主要性
9、质 q 集合A上的二元关系的主要性质（自反性，反自反性，对称 性，反对称性，传递性）的定义及判别法，对某些关系证明 它们有或没有中的性质。 q A上二元关系的n次幂的定义及主要性质 q 等价关系、等价类、商集、划分等概念，以及等价关系与划 分之间的对应 q 偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极 小元、上界、下界、上确界、下确界等概念关系性质的特点自反性反自反性对称性反对称性传递性定义xA RxA RR RR R x=yR R 集合表达式IA RRIARR-1RR-1 IARRR关系矩阵主对角线 元素全是1主对角线 元素全是0 矩阵是对称矩 阵 若 rij1，且 ij，则rji0
10、 对M2中1所 在位置，M 中相应的位 置都是1 关系图每个顶点 都有环每个顶点 都没有环 如果两个顶点 之间有边，一 定是一对方向 相反的边(无 单边) 如果两点之间 有边，一定是 一条有向边( 无双向边) 如果顶点 xi 到 xj 有边， xj 到 xk 有边 ，则从 xi到 xk 也有边 关系性质的证明通常的证明方法是利用定义证明。 R 在 A 上自反 任取 x，有 xA R R 在 A 上对称 任取 ，有 R R R 在 A 上反对称 任取 ，有 R R xy R 在 A 上传递 任取 , ，有 R R R集合论函数q 掌握函数、A到B的函数、集合在函数下的像、集合在函数 下的完全原像
11、的概念及表示法；当A与B都是有穷集时，会 求A到B的函数的个数。 q 掌握A到B的函数是单射、满射、和双射的定义及证明方法 。 q 掌握常函数、恒等函数、单调函数、特征函数、自然映射 等概念。 q 掌握复合函数的主要性质和求复合函数的方法。 q 掌握反函数的概念及主要性质。单射和满射的证明方法q 证明函数 f : AB是满射的，基本方法是：任取 yB，找到 xA ( x 与 y 相关，可能是一个关于 y 的 表达式)或者证明存在xA，使得 f (x)y。q 证明函数 f : AB是单射的，基本方法是：假设 A 中存在 x1 和 x2，使得 f (x1)f (x2)，利用已知条件 或者相关的定理
12、最终证明 x1x2。集合论基数q 掌握基数的基本概念 q 掌握可数集合和不可数集合的概念，以及相关结论代数结构-代数系统q 构成代数系统的基本成分 非空集合集合上若干个封闭的二元和一元运算代数常数 q 二元运算性质和特异元素 q 同类型的与同种的代数系统 q 子代数的定义与实例代数结构的知识体系半群与群环与域格与布尔代数分类代数 推广成分：载体及运算 公理：运算性质代数系统的构成代数系统的 同态与同构代数系统间的关系映射子代数积代数商代数等价关系笛卡儿积子集新代数系统同种的同类型的产生群与半群广群二元运算的封闭性结合律半群单位元独异点每个元素可逆群交换律 交换半群交换律 交换独异点交换律 Ab
13、el群有限个元素 有限群生成元 循环群实例 n元置换群实例 Klein群代数结构-环q 代数系统 构成环的条件： 构成Abel群； 构成半群； 对于 + 满足分配律。 q 环中运算性质：a0=0a=0；a(-b)=(-a)b=-(ab)；乘法对加法的 广义分配律。 q 环 R 的非空子集 S 构成 R 的子环的条件：任取 a,b 属于 S, 有a-b 属于 S；ab属于S。 q 环同态映射的定义、判别法及其实例。代数结构-格与布尔代数q 偏序集构成格的条件：任意二元子集都有最大下界和最小上 界。 q 格的实例：正整数的因子格，幂集格，子群格。q 格的性质：对偶原理，格中算律（交换、结合、幂等、
14、吸收 ），保序性，分配不等式。 q 格作为代数系统的定义。 q 格 L 的非空子集 S 构成 L 的子格的条件：S 对 L 的两个运算封闭。 q 函数 构成格同态的条件： (ab) (a) (b) (ab) (a) (b)q 格同态的保序性。代数结构-格与布尔代数q 如果格中一个运算对另一个运算是可分配的，称这个格是 分配格。 q 分配格的两种判别法： 不存在与钻石格或五角格同构的子格；对于任意元素 a, b, c, 有 abac 且 abac bc。 q 有界格的定义及其实例。 q 格中元素的补元及其性质（分配格中补元的唯一性）。 q 有补格的定义。代数结构-格与布尔代数q 布尔代数的两个等
15、价定义： v有补分配格； v有两个二元运算并满足交换律、分配律、同一律和补元 律的代数系统。 q 布尔代数的特殊性质：双重否定律和德摩根律。 q 子布尔代数的定义及其判别。 q 布尔代数同态的判定： vf (ab)f (a)f (b) ( 或 f (ab)f (a)f (b), vf (a)-f (a) q 对于任意自然数 n，只有一个 2n 元的有限布尔代数，就是 幂集代数。图论解决实际问题(1) 很多离散问题可以用图模型求解。 (2) 为了建立一个图模型，需要决定顶点和边分别代表什么。 (3) 在一个图模型中，边经常代表两个顶点之间的关系。图论基本概念q 理解与图的定义有关的诸多概念，以及它们之间的相互关 系。 q 深刻理解握手定理及其推论的内容，并能熟练地应用它们 。 q 深刻理解图同构、简单图、完全图、正则图、子图、补图 、二部图等概念及其它们的性质和相互关系，并能熟练地 应用这些性质和关系。 q 深刻理解通路与回路的定义、相互关系及其分类，掌握通 路与回路的各种不同
