东北大学离散数学复习总结(满分版).doc

《东北大学离散数学复习总结(满分版).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.方法、知识点总结（知识重点和考题重点）前三章重点容（知识重点）：1、蕴含（条件）“→”的真值P→Q的真值为假，当且仅当P为真，Q为假。2、重言(永真)蕴涵式证明方法<1>假设前件为真，推出后件也为真。<2>假设后件为假，推出前件也为假。易错3、等价公式和证明中运用..1、重要公式重言蕴涵式：P∧Q=>PorQPorQ=>p∨QA->B=>(A∧or∨C)->(B∧or∨C)其他是在此基础上演变等价公式：幂等律P∧P=PP∨P=P吸收律P∧(P∨Q)=PP∨(P∧Q)=P同一律P∨F=PP∧T=PP∨T=TP∧F=FP<->Q=(P->Q)∧(Q->P)=(P∧Q)∨(﹁P∧﹁Q)2

2、、式的写法（最方便就是真值表法）3、派遣人员、课表安排类算法：第一步：列出所有条件，写成符号公式第二步：用合取∧连接第三步：求上一步中的析取式即可4、逻辑推理的写法直接推理论证：其中I公式是指重言蕴涵式那部分其中E公式是指等价公式部分条件论证:形如~,~,~=>R->S..RP(附加条件)......STR->SCP1、谓词基本容注意：任意用—>连接存在用∧连接量词的否定公式量词的辖域扩充公式..量词分配公式其他公式1、带量词的公式在论域的展开2、量词辖域的扩充公式3、前束式的写法给定一个带有量词的谓词公式，1)消去公式中的联接词→和←→(为了便于量词辖域的扩充)；2)如果量词前有“

3、﹁Ø”，则用量词否定公式﹁Ø”后移。再用摩根定律或求公式的否定公式，将“﹁Ø”后移到原子谓词公式之前；3)用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)；4)用量词辖域扩充公式提取量词，使之成为前束式形式。简要概括：1、去->，<->2、移﹁3、换元4、量词辖域扩充..1、谓词演算的推理理论推理规则：P、T、CP、US、ES、EG、UG的使用ESUS去量词EGUG添量词★谨记：ES要在US之前,很重要添加量词注意事项：2、集合的幂集（用P表示，也常有花P表示）A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2的A次方给定有限集合A，如果

4、

5、A

6、=n,则

7、P(A)

8、=2的n次方..1、求集合的划分数与等价关系数——相同2、三种重要集合运算一、差运算-(相对补集)..一、绝对补集~二、对称差前三章重点容（考题重点）：最常考容和方法需要看自己课件，前三章考试容不多且简单1、命题符号化（包括第一章简单的命题和第二章谓词的命题）2、逻辑推理（命题逻辑和谓词逻辑两种推理，每章书最后部分）3、主析取式与主合取式（命题逻辑和谓词逻辑中的两种式写法）4、真值的判断..后五章重点容（知识重点）：1、笛卡尔积定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作A×B如果A、B都是有限集，且

9、

10、A

11、=m,

12、B

13、=n，则

14、AXB

15、=mn.2、域的表示：定义域dom（关系的第一个元素的围）值域Ran（关系的第二个元素的围）3、空关系、完全关系、A上的恒等关系IA的定义空关系只有点，没有一条边。4、关系的个数..1、对称、反对称、自反、反自反、传递的判定2、等价关系、等价类定义：设R是A上关系,若R是自反的、对称的和传递的，则称R是A中的等价关系等价关系的个数：划分数；由等价关系图求等价类：R图中每个独立子图上的结点，构成一个等价类。不同的等价类个数=独立子图个数3、相容关系、相容类..特点：自反、对称。图的简化：⑴不画环；⑵两条对称边用一条无向直线代替相容类：设r是集合X上的

16、相容关系，CÍX,如果对于C中任意两个元素x,y有∈r,称C是r的一个相容类从简化图找最大相容类：最大相容类的意义是——一个相容类加多一个点就不是相容类了，所以最大相容类可以是多个而不是唯一的“最大”的概念，定义类似极大线性无关组，但元素个数不同------找最大完全多边形。最大完全多边形：含有结点最多的多边形中，每个结点都与其它结点相联结。通过最大相容类求完全覆盖：完全覆盖就是指所有最大相容类构成的集合。1、关系的分类：偏序关系定义：R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称是偏序集。全序关系定义：是偏序集，任何x,y∈A，如果x与

17、y都是可比较的，则称≤是全序关系(线序、链)。..1、偏序集Hasse图的画法1).用“。”表示A中元素。2).如果x≤y,且x≠y，则结点y要画在结点x的上方。3).如果x≤y,且y盖住x，x与y之间连一直线。4).一般先从最下层结点(全是射出的边与之相连(不考虑环))，逐层向上画，直到最上层结点(全是射入的边与之相连)。(采用抓两头，带中间的方法)2、重要元素定义（极大小元、最大小元、上下界、最大下界与最小上界）3、如何求映射是入（单）、满、双射？第一