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

方法、知识点总结
〔知识重点和考题重点〕
前三章重点容〔知识重点〕:
蕴含〔条件〕"→〞的真值
P→Q的真值为假,当且仅当P为真,Q为假。
重言(永真)蕴涵式证明方法
<1>假设前件为真,推出后件也为真。
<2>假设后件为假,推出前件也为假。
易错
等价公式和证明中运用
重要公式
重言蕴涵式: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)
式的写法〔最方便就是真值表法〕
派遣人员、课表安排类算法:
第一步:列出所有条件,写成符号公式
第二步:用合取∧连接
第三步:求上一步中的析取式即可
逻辑推理的写法
直接推理论证:其中I公式是指重言蕴涵式那局部
其中E公式是指等价公式局部
条件论证: 形如~ , ~, ~ => R->S
R P(附加条件)
... ...
S T
R->S CP
谓词根本容
注意:任意用—> 连接
存在用∧连接
量词的否认公式
量词的辖域扩大公式
量词分配公式
其他公式
带量词的公式在论域的展开
量词辖域的扩大公式
前束式的写法
给定一个带有量词的谓词公式,
消去公式中的联接词→和←→(为了便于量词辖域的扩大);
如果量词前有"﹁Ø〞,那么用量词否认公式﹁Ø〞后移。再用摩根定律或求公式的否认公式,将"﹁Ø〞后移到原子谓词公式之前;
用约束变元的改名规那么或自由变元的代入规那么对变元换名(为量词辖域扩大作准备);
用量词辖域扩大公式提取量词,使之成为前束式形式。
简要概括: 1、去-> , <-> 2、移﹁
3、换元 4、量词辖域扩大
谓词演算的推理理论
推理规那么:P、T、CP、US、ES、EG、UG 的使用
ES US 去量词
EG UG 添量词
★谨记:ES要在US之前,很重要
添加量词考前须知:
集合的幂集〔用P表示,也常有花P表示〕
A是集合,由A的所有子集构成的集合,称之为A的幂集。记作P(A)或2的A次方
给定有限集合A,如果|A|=n, 那么|P(A)|=2的n次方
求集合的划分数与等价关系数——一样
三种重要集合运算
差运算- (相对补集)
绝对补集~
对称差
前三章重点容〔考题重点〕:最常考
容和方法需要看自己课件,前三章考试容不多且简单
命题符号化〔包括第一章简单的命题和第二章谓词的命题〕
逻辑推理〔命题逻辑和谓词逻辑两种推理,每章书最后局部〕
主析取式与主合取式〔命题逻辑和谓词逻辑中的两种式写法〕
真值的判断
后五章重点容〔知识重点〕:
笛卡尔积
定义:设A、B是集合,由A的元素为第一元素, B的元素为第二元素组成序偶的集合,称为A和B 的笛卡尔积,记作A×B
如果A、B都是有限集,且|A|=m, |B|=n,那么|AXB |=mn.
域的表示:
定义域dom〔关系的第一个元素的围〕
值域 Ran〔关系的第二个元素的围〕
空关系、完全关系、A上的恒等关系IA的定义
空关系只有点,没有一条边。
关系的个数
对称、反对称、自反、反自反、传递的判定
等价关系、等价类
定义:设R是A上关系,假设R是自反的、对称的和传递的,那么称R是A中的等价关系
等价关系的个数:划分数;
由等价关系图求等价类:
R图中每个独立子图上的结点,构成一个等价类。
不同的等价类个数=独立子图个数
相容关系、相容类
特点:自反、对称。
图的简化:⑴不画环;
⑵两条对称边用一条无向直线代替
相容类:设r是集合X上的相容关系,CÍX,如果对于C中任意两个元素x,y有<x,y>∈r ,称C是r的一个相容类
从简化图找最大相容类:
最大相容类的意义是——一个相容类加多一个点就不是相容类了,所以最大相容类可以是多个而不是唯一的"最大〞的概念,定义类似极大线性无关组,但元素个数不同
------找最大完全多边形。最大完全多边形:含有结点最多的多边形中,每个结点都与其它结点相联结。
通过最大相容类求完全覆盖:
完全覆盖就是指所有最大相容类构成的集合。
关系的分类:
偏序关系定义:R是A上自反、反对称和传递的关系,那么称R 是A上的偏序关系。并称<A,R>是偏序集。
全序关系定义:<A,≤>是偏序集,任何x,y∈A,如果x与y都是可比拟的,那么称≤是全序关系(线序、链)。
偏序集Hasse图的画法
.用"。〞表示A中元素