离散数学总复习
总复习
第一章命题逻辑：
视频地址：
1. 第一章 需要熟练掌握的知识点
命题的定义：确定真假命题的陈述句；
逻辑联结词：┐ ∨ ∧ -> ↔
命题变元：任意的命题；
命题公式：合式公式；
永真式：任何情况都是真；
永假式：任何情况都是假；
可满足式：至少有一种情况使得真值为1；
等价式：两个式子的真值表完全相同，双条件永真；
蕴含式：单条件永真（包含）；
极小项：命题变元或者命题变元的否定（命题变元必出现且只出现一次）之间做合取 ∧（m：0表示否定，1表示本身） ；
极大项：命题变元或者命题变元的否定（命题变元必出现且只出现一次）之间做析取 ∨（M：1表示否定，0表示本身） ；
主析取范式：极小项之间做析取（例如：(P∧Q)∨(┐P∧Q)）
主合取范式：极大项之间做合取（外面合取，里面析取）
2.第一章 等价式和蕴含式的证明方法
① 基本等价式的证明方法
- 真值表法（对比真值表）
- 置换定理（通过等价式推导得出）
② 基本蕴含式的证明方法
- 真值表法（单条件永真）
- 附加前提法（CP规则法）
- 反证法（归谬法）
3.第一章 命题公式
① 求出命题公式的主析取范式和主合取范式
- 真值表法（真值为0的极大项之间做合取，真值为1的极小项之间做析取）
- 等值添项法
② 例题对比两种方法：
4.第一章 命题符号化
① 命题符号化：在自然语言中找出原子命题，确定逻辑联结词
② 用推理规则进行有效论证
② 例题如下：
5.第一章 练习题
① 否定命题
② 命题符号化
③ 逆命题、反命题、逆反命题
④ 恒等式证明等价
⑤ 求主析取范式和主合取范式
⑥ 推论规则：CP规则
⑦ 推论规则：反证法（归谬法）
⑧ 命题符号化
第三章集合：
视频地址：
1. 第三章 需要熟练掌握的知识点
① 集合与集合的关系：包含⊆、不包含￠、真包含⊂、相等=；
② 元素与集合的关系：属于∈、不属于∉；
③ 全集、空集、幂集、笛卡尔积；
④ 集合的五种基本运算：~(非)、∩(交)、∪(并)、-(差)、⊕(对称差A⊕B=A∪B - A∩B)；
第四章二元关系：
视频地址：
1. 第四章 需要熟练掌握的知识点
① 关系是序偶的集合，关系R中任一序偶<x,y>可记作<x,y>∈R 或 xRy
② 特殊的关系：恒等关系：Ix={<x,x>|x∈X}、空关系、全域关系
③ 关系的表示：集合表示、矩阵表示、关系图表示
④ 关系的域：
- domR（定义域）是关系R中所有序偶的x的集合
- ranR（值域）是关系R中所有序偶的y的集合
- fldR（域）是R的定义域和值域的并集，dom(R)∪ran(R)
- R↑A 是R在A上的限制，R中的x元素必须属于A
- R[A] 是A在R下的像，ran(R↑A)
⑤ 逆运算：
- 将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系；
- A×B的逆关系为B×A；
- R◦S的的逆关系为S逆◦R逆；
- R是对称的⇔R=R逆；
- R是反对称的⇔R∩R逆⊆Ix；
⑥ 复合关系：
- 设R为X到Y的关系，S为Y到Z的关系，则R◦S称为R和S的复合关系；
- R◦S={<x,z>|x∈X∧z∈Z∧(∃y)(y∈Y∧<x,y>∈R∧<y,z>∈S)}；
⑦ 幂运算：
- R的0次方 = 恒等关系IA
- R的n次方 = R的n-1次方◦R
- 三种运算方法：集合法、关系矩阵法、关系图法；
⑧ 关系的性质：自反性、反自反性、对称性、反对称性、传递性；
⑨ 关系的闭包运算：
- 自反闭包：r(R)=R∪Ix
- 对称闭包：s(R)=R∪R逆
- 传递闭包：t(R)=R+
⑩ 等价关系与偏序关系：
