东北大学离散数学复习总结
- 格式：docx
- 大小：60.97 KB
- 文档页数：20
方法、知识点总结 （知识重点和考题重点） 前三章重点内容（知识重点）： 1、蕴含（条件）“→”的真值 P→Q的真值为假，当且仅当P为真，Q为 假。 2、重言(永真)蕴涵式证明方法 <1>假设前件为真，推出后件也为真。 <2>假设后件为假，推出前件也为假。 易错 3、等价公式和证明中运用 4、重要公式 重言蕴涵式：P∧Q => P or Q P or Q => p∨Q A->B =>(A∧or∨C)->(B∧or∨C) 其他是在此基础上演变 等价公式：幂等律 P∧P=P P∨P=P 吸收律 P∧(P∨Q)=P P∨(P∧Q)=P 同一律 P∨F=P P∧T=P P∨T=T P∧F=F P <-> Q = (P->Q)∧(Q->P) = (P∧Q)∨(﹁P∧﹁Q) 5、范式的写法（最方便就是真值表法） 6、派遣人员、课表安排类算法： 第一步：列出所有条件，写成符号公式 第二步：用合取∧连接 第三步：求上一步中的析取范式即可 7、逻辑推理的写法 直接推理论证：其中I公式是指 重言蕴涵式那部分 其中E公式是指 等价公式部分 条件论证: 形如 ~ , ~, ~ => R->S R P(附加条件) ... ... S T R->S CP 8、谓词基本内容
注意：任意用—> 连接 存在用 ∧ 连接 量词的否定公式 量词的辖域扩充公式 量词分配公式 其他公式 9、带量词的公式在论域内的展开 10、量词辖域的扩充公式 11、前束范式的写法 给定一个带有量词的谓词公式， 1)消去公式中的联接词→和←→(为了便于量词 辖域的扩充)； 2)如果量词前有“﹁?”，则用量词否定公式﹁?”后移。再用摩根定律或求公式的否定公式，将“﹁?”后移到原子谓词公式之前；
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的A次方
给定有限集合A，如果|A|=n, 则|P(A)|=2的n次方 14、求集合的划分数与等价关系数 ——相同 15、三种重要集合运算 一、差运算- (相对补集) 二、绝对补集~ 三、对称差 前三章重点内容（考题重点）：最常考 内容和方法需要看自己课件，前三章考试内容不多且简单 1、命题符号化（包括第一章简单的命题和第二章谓词的命题） 2、逻辑推理（命题逻辑和谓词逻辑两种推理，每章书最后部分） 3、主析取范式与主合取范式（命题逻辑和谓词逻辑中的两种范式写法） 4、真值的判断 后五章重点内容（知识重点）： 1、笛卡尔积 定义:设A、B是集合，由A的元素为第一元素， B的元素为第二元素组成序偶的集合，称为A和B 的笛卡尔积，记作A×B
如果A、B都是有限集，且|A|=m, |B|=n，则 |AXB |=mn.
2、域的表示： 定义域dom（关系的第一个元素的范围） 值域 Ran（关系的第二个元素的范围） 3、 空关系、完全关系、A上的恒等关系IA的定义 空关系只有点，没有一条边。 4、关系的个数 5、对称、反对称、自反、反自反、传递的判定 6、等价关系、等价类 定义：设R是A上关系,若R是自反的、对称的和 传递的， 则
称R是A中的等价关系
等价关系的个数：划分数； 由等价关系图求等价类： R图中每个独立子图上的结点，构成一个等价类。 不同的等价类个数=独立子图个数 7、相容关系、相容类 特点：自反、对称。 图的简化：⑴不画环； ⑵ 两条对称边用一条无向直线代替 相容类：设r是集合X上的相容关系，C?X,如果对于C中任 意两个元素x,y有∈r ,称C是r的一个相容类
从简化图找最大相容类： 最大相容类的意义是——一个相容类加多一个点就不是相容类了，所以最大相容类可以是多个而不是唯一的“最大”的概念，定义类似极大线性无关组，但元素个数不同
------找最大完全多边形。 最大完全多边形：含有结点最多的多边形中，每个结点 都与其它结点相联结。
通过最大相容类求完全覆盖： 完全覆盖就是指 所有最大相容类构成的集合。 8、关系的分类： 偏序关系定义：R是A上自反、反对称和传递的关系，则称R 是
A上的偏序关系。并称是偏序集。
全序关系定义：是偏序集，任何x,y∈A，如果x与y都
是可 比较的，则称≤是全序关系(线序、链)。
9、偏序集Hasse图的画法 1).用“。”表示A中元素。 2).如果x≤y,且x≠y，则结点y要画在结点x的上方。 3). 如果x≤y,且y盖住x，x与y之间连一直线。 4). 一般先从最下层结点(全是射出的边与之相连(不考虑 环))，逐层向上画，直到最上层结点(全是射入的边与之 相连)。(采用抓两头，带中间的方法 )
10、重要元素定义（极大小元、最大小元、上下界、最大下界与
最小上界）
11、如何求映射是入（单）、满、双射？ 第一步：分别求出定义域和值域 第二步：比较就出来了，就那么简单 但是要证明的话： 两者结合得：双射成立 12、复合函数中的重要性质（常考）： f:X→Y, g:Y→Z是两个函数, 则 ⑴如果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:X→Y是双射的函数，fC:Y?X 也是函数, 称 之为 f 的逆函数。
设f:X→Y是双射的函数，则有 15、第六章基础知识重点 幂等元、幺元e、零元0、逆元的概念 同态同构：f(x)满射、并且满足 *不是双射就一定复合同构的条件： 必须具有 幺元对幺元、零元对零元...... 代数系统（重点） 半群：封闭、可逆 独异点：有幺元 群：可逆 交换群：可交换 群的特征：1.消去律 2.无零元 3.除幺元外无其他幂等元
运算表中：每个元素在每一行、列必须出现仅出现一次！ 16、第七章基础知识重点 格：是偏序集，如果任何a,b∈A,使得{a,b}都有最大
下界和最小上界，则称是格
平凡格：所有全序都是格，称之为平凡格。
分配格：（判定定理）
所有链均为分配格。 设是分配格，对任何a,b,c∈A, 如果有 a∧b=a∧c及 a∨b=a∨c则必有 b=c .
有界格：（判定定理）
有界格定义：如果一个格存在全上界1与全下界0，则 称此格为有界格。
从格的图形看：全上界1，就是图的最上边元素(只一个)。 全下界0，就是图的最下边元素(只一个)。 有补格：（判定定理：根据定义看是不是每个中间元素都有
补元）
补元：设是个有界格，a∈A, 如果存在 b∈A, 使得a∨b=1 a∧b=0 则称a与b互为补元（其中∨是求最小上界，∧求最大下界）
有补格的定义：一个有界格中，如果每个元素都有补元，则称之为有补格 布尔格：如果一个格既是分配格又是有补格，则称之为布
尔格。
*重要定理： 在有界分配格中，如果元素有补元，则补元 是唯一的。 17、格的同构条件（特别）需同时满足： 钻石定律： 一个布尔代数的所有原子（直接覆盖最小元0的元素）构成的布尔代数一定与元代数同构
18、布尔代数表达式和布尔函数 是布尔代数的形式 含有变元 x1,x2,…,xn 的布尔 表达式记作E(x1,x2,…xn),也可以看成是一个函数f:Bn→B, 称之为布尔函数
布尔表达式的范式的写法（很重要，与第一第二章的方法类似） 19、第八章图论的重要知识点（好多好多的定义自己记吧） 图的同构： 两个图同构的必要条件: 1.结点个数相等. 2.边数相等. 3.度数相同的结点数相等. 4.对应的结点的度数相等. 图的连通：强连通、单侧连通和弱连通（一般不考） 如果任何两个结点间相互可达, 则称 G是强连通. 如果任何一对结点间, 至少有一个结点到另 一个结点可达, 则称G是单侧连通. 如果将G看成无向图后 (即把有向边看成无向边)是连通的,则称G是弱连通
强分图、单侧分图和弱分图 在简单有向图中,具有强连通的最大子图,称为强分图. 具 有单侧连通的最大子图,称为单侧分图. 具有弱连通的最 大子图,称为弱分图. 图的矩阵表示和写法（前两个有点重要）：
一、邻接矩阵
