《东北大学离散数学复习总结(满分版)(共36页)》由会员分享，可在线阅读，更多相关《东北大学离散数学复习总结(满分版)(共36页)（37页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上方法、知识点总结（知识重点和考题重点）前三章重点内容（知识重点）：1、 蕴含（条件）“”的真值 PQ的真值为假，当且仅当P为真，Q为 假。2、 重言(永真)蕴涵式证明方法 假设前件为真，推出后件也为真。 假设后件为假，推出前件也为假。易错 3、 等价公式和证明中运用4、 重要公式重言蕴涵式：PQ = P or QP or Q = pQA-B =(AorC)-(BorC)其他是在此基础上演变等价公式：幂等律 PP=P PP=P 吸收律 P(PQ)=P P(PQ)=P 同一律 PF=P PT=P PT=T PF=FP Q = (P-Q)(Q-P) = (PQ)(PQ)5、
2、 范式的写法（最方便就是真值表法）6、 派遣人员、课表安排类算法：第一步：列出所有条件，写成符号公式第二步：用合取连接第三步：求上一步中的析取范式即可7、 逻辑推理的写法直接推理论证：其中I公式是指 重言蕴涵式那部分其中E公式是指 等价公式部分条件论证: 形如 , , = R-S R P(附加条件).S TR-S CP8、 谓词基本内容注意：任意用 连接 存在用 连接量词的否定公式量词的辖域扩充公式量词分配公式其他公式9、 带量词的公式在论域内的展开10、 量词辖域的扩充公式 11、 前束范式的写法 给定一个带有量词的谓词公式， 1) 消去公式中的联接词和(为了便于量词 辖域的扩充)； 2)
3、如果量词前有“”，则用量词否定公式”后移。再用摩根定律或求公式的否定公式，将“”后移到原子谓词公式之前； 3) 用约束变元的改名规则或自由变元的代入 规则对变元换名(为量词辖域扩充作准备)； 4) 用量词辖域扩充公式提取量词，使之成为 前束范式形式。简要概括： 1、去 - ， 2、移 3、换元 4、量词辖域扩充12、 谓词演算的推理理论 推理规则：P、T、CP、US、ES、EG、UG 的使用ES US 去量词EG UG 添量词 谨记：ES要在US之前,很重要 添加量词注意事项：13、 集合的幂集（用P表示，也常有花P表示） A是集合，由A的所有子集构成的集合，称 之为A的幂集。记作P(A)或2
4、的A次方给定有限集合A，如果|A|=n, 则|P(A)|=2的n次方14、 求集合的划分数与等价关系数 相同15、 三种重要集合运算一、 差运算- (相对补集) 二、 绝对补集 三、 对称差 前三章重点内容（考题重点）：最常考内容和方法需要看自己课件，前三章考试内容不多且简单1、 命题符号化（包括第一章简单的命题和第二章谓词的命题）2、 逻辑推理（命题逻辑和谓词逻辑两种推理，每章书最后部分）3、 主析取范式与主合取范式（命题逻辑和谓词逻辑中的两种范式写法）4、 真值的判断后五章重点内容（知识重点）：1、 笛卡尔积定义:设A、B是集合，由A的元素为第一元素， B的元素为第二元素组成序偶的集合，称
5、为A和B 的笛卡尔积，记作AB如果A、B都是有限集，且|A|=m, |B|=n，则 |AXB |=mn. 2、 域的表示：定义域dom（关系的第一个元素的范围）值域 Ran（关系的第二个元素的范围）3、 空关系、完全关系、A上的恒等关系IA的定义空关系只有点，没有一条边。4、 关系的个数 5、 对称、反对称、自反、反自反、传递的判定6、 等价关系、等价类定义：设R是A上关系,若R是自反的、对称的和 传递的，则称R是A中的等价关系等价关系的个数：划分数；由等价关系图求等价类：R图中每个独立子图上的结点，构成一个等价类。 不同的等价类个数=独立子图个数7、 相容关系、相容类特点：自反、对称。图的简
6、化：不画环； 两条对称边用一条无向直线代替相容类：设r是集合X上的相容关系，CX,如果对于C中任 意两个元素x,y有r ,称C是r的一个相容类从简化图找最大相容类：最大相容类的意义是一个相容类加多一个点就不是相容类了，所以最大相容类可以是多个而不是唯一的“最大”的概念，定义类似极大线性无关组，但元素个数不同-找最大完全多边形。 最大完全多边形：含有结点最多的多边形中，每个结点 都与其它结点相联结。 通过最大相容类求完全覆盖：完全覆盖就是指 所有最大相容类构成的集合。8、 关系的分类：偏序关系定义：R是A上自反、反对称和传递的关系，则称R 是A上的偏序关系。并称是偏序集。 全序关系定义：是偏序集
7、，任何x,yA，如果x与y都是可 比较的，则称是全序关系(线序、链)。 9、 偏序集Hasse图的画法1) .用“。”表示A中元素。2) .如果xy,且xy，则结点y要画在结点x的上方。 3). 如果xy,且y盖住x，x与y之间连一直线。4). 一般先从最下层结点(全是射出的边与之相连(不考虑 环)，逐层向上画，直到最上层结点(全是射入的边与之 相连)。(采用抓两头，带中间的方法 ) 10、 重要元素定义（极大小元、最大小元、上下界、最大下界与最小上界）11、 如何求映射是入（单）、满、双射？第一步：分别求出定义域和值域第二步：比较就出来了，就那么简单但是要证明的话：两者结合得：双射成立12、
8、 复合函数中的重要性质（常考）：f:XY, g:YZ是两个函数, 则 如果f和g是满射的，则 g。f 也是满射的； 如果f和g是入射的，则 g。f 也是入射的； 如果f和g是双射的，则 g。f 也是双射的如果 g。f 是满射的，则g是 满射的； 如果g。f 是入射的，则 f 是入射的； 如果 g。f 是双射的，则f是入射的和g是满射的13、 函数种类个数的求法14、 逆函数（性质）设f:XY是双射的函数，fC:YX 也是函数, 称 之为 f 的逆函数。设f:XY是双射的函数，则有15、 第六章基础知识重点幂等元、幺元e、零元0、逆元的概念同态同构：f(x)满射、并且满足*不是双射就一定复合同构
9、的条件：必须具有 幺元对幺元、零元对零元.代数系统（重点）半群：封闭、可逆 独异点：有幺元群：可逆 交换群：可交换群的特征：1.消去律 2.无零元 3.除幺元外无其他幂等元运算表中：每个元素在每一行、列必须出现仅出现一次！16、 第七章基础知识重点格：是偏序集，如果任何a,bA,使得a,b都有最大下界和最小上界，则称是格平凡格：所有全序都是格，称之为平凡格。 分配格：（判定定理）所有链均为分配格。 设是分配格，对任何a,b,cA, 如果有 ab=ac及 ab=ac则必有 b=c . 有界格：（判定定理）有界格定义：如果一个格存在全上界1与全下界0，则 称此格为有界格。 从格的图形看：全上界1，
10、就是图的最上边元素(只一个)。 全下界0，就是图的最下边元素(只一个)。 有补格：（判定定理：根据定义看是不是每个中间元素都有补元）补元：设是个有界格，aA, 如果存在 bA, 使得ab=1 ab=0 则称a与b互为补元（其中是求最小上界，求最大下界）有补格的定义：一个有界格中，如果每个元素都有补元，则称之为有补格 布尔格：如果一个格既是分配格又是有补格，则称之为布尔格。 *重要定理： 在有界分配格中，如果元素有补元，则补元 是唯一的。17、 格的同构条件（特别）需同时满足：钻石定律：一个布尔代数的所有原子（直接覆盖最小元0的元素）构成的布尔代数一定与元代数同构18、 布尔代数表达式和布尔函数
11、 是布尔代数的形式含有变元 x1,x2,xn 的布尔 表达式记作E(x1,x2,xn),也可以看成是一个函数f:BnB, 称之为布尔函数布尔表达式的范式的写法（很重要，与第一第二章的方法类似）19、 第八章图论的重要知识点（好多好多的定义自己记吧）图的同构：两个图同构的必要条件: 1. 结点个数相等. 2. 边数相等. 3. 度数相同的结点数相等.4. 对应的结点的度数相等.图的连通：强连通、单侧连通和弱连通（一般不考）如果任何两个结点间相互可达, 则称 G是强连通. 如果任何一对结点间, 至少有一个结点到另 一个结点可达, 则称G是单侧连通. 如果将G看成无向图后 (即把有向边看成无向边)是
12、连通的,则称G是弱连通强分图、单侧分图和弱分图在简单有向图中,具有强连通的最大子图,称为强分图.具 有单侧连通的最大子图,称为单侧分图.具有弱连通的最 大子图,称为弱分图.图的矩阵表示和写法（前两个有点重要）：一、 邻接矩阵每一行的1：在无向图中代表一条线有向图中代表出线列中的1代表入线二、 可达性矩阵三、 完全关系矩阵图中结点的度与个数、边的关系：考试需要两则结合20、 欧拉图与H（汉密尔）图（重点）定义：在无孤立结点的图G中,若存在一条回路,它 经过图中每条边一次且仅一次,称此回路为欧拉回路. 称此图为欧拉图 汉密尔顿回路(H回路):通过G中每个结点恰好一次的回 路.具有汉密尔顿回路(H回
13、路)的图. 欧拉回路的判定：（充要条件）无向图G具有欧拉路,当且仅当G是连通的,且有零个或两个奇数度的结点. 汉密尔顿图的判定: （只有充分条件）(充分条件)设G是有n个结点的简单图,若G中每对结点度数之和大于等于n,则G有一条H回路 欧拉回路的算法（重重重！虽然可能不考）（记做 闭迹交集法）H回路的算法（重重重！虽然可能不考）（记做 相邻最小权法）21、 树中的重要方法：树的 结点与边数：边数=结点数-1 e = v-1m叉有序树转化成二叉树的方法：赋权图的最小生成树的求法（记做 相邻最小权不回路法）：定义:一棵生成树中的所有边的权之和称为该生成树的 权. 具有最小权的生成树,称为最小生成树.最优树求法：定义*后五章重点内容（考题重点）：1、 求逆元（例如a逆）第一步：求出幺元e第二步：a逆与a进行所定义的运算，写出等式：如a*a逆=e,求解2、 群的阶性质
