离散数学 1 第二轮复习 重点易错点总结#

Chapter 1：命题逻辑#

1. 命题的真假性一定确定。

2. 逻辑联结词的优先级

   $\neg$、$\wedge$、$\vee$、$\rightarrow$、$\leftrightarrow$

3. $\rightarrow$ 为 F 的情况有且仅有 $1 \rightarrow 0$

4. 合式公式的定义：

   1. 真值 T 和 F 是合式公式。

   2. 原子命题公式是一个合式公式。

   3. 如果 $A$ 是合式公式，那么 $\neg A$ 是合式公式。

   4. 如果 $A$ 和 $B$ 均是合式公式，那么 $(A \wedge B)$，$(A \vee B)$，$(A \rightarrow B)$ 和 $(A \leftrightarrow B)$ 都是合式公式。

   5. 当且仅当有限次地应用 i. ~ iv. 条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式公式。

   • 重点在于，最外层除了 $\neg$，一定是 $()$。（别的学校似乎不一定这样的要求）。 即，$\neg (P \wedge Q)$ 是合式公式，而 $P \wedge Q$ 不是合式公式。

5. 公式类型：永真式、永假式与可满足式。

6. 替换规则：主要用于公式等价化简。

7. 代入规则：应用于重言式，每个变元都可以“拓展”为一个公式。注意需要代换某个命题变元出现的每一处代以同一个公式。

8. 注意充分和必要的逻辑表达式翻译。

9. 对偶式：仅仅改变 $\wedge$、$\vee$、T、F。

   对偶原理：

   1. 德·摩根律

      $\neg$ 塞进变元，公式变对偶。

   2. 原公式等价，对偶公式也等价。

   3. $P \rightarrow Q \implies \neg Q \rightarrow \neg P$

      原公式蕴含，则对偶公式逆蕴含。

10. 主析取范式/主合取范式的求法：

    1. 观察是否永真永假。

    2. 用配凑项和分配律拆。

    • 也可以上真值表

11. 永真式无主合取范式，

    永假式无主析取范式。

12. 命题逻辑的自然演绎推理：

    规则：P、T、CP、F

    CP：书写时为：P 规则（附加前提）

    F：书写时为：P 规则（假设前提）

    F：假设目标结论为 F，与其他前提推出永假式

    T：E 为使用永真式推导，I 为使用蕴含式推导。

Chapter 2：谓词逻辑#

1. 本质上，

   $(\forall x) A(x) \iff A(a_1) \wedge A(a_2) \wedge \ldots A(a_n)$ $(\exists x) A(x) \iff A(a_1) \vee A(a_2) \vee \ldots A(a_n)$

2. 合式谓词公式

   1. 原子谓词公式是合式公式；

   2. 若 $A$ 是合式公式，则 $\neg A$ 也是合式公式；

   3. 如果 $A$ 和 $B$ 均是合式公式，那么 $A \wedge B$，$A \vee B$，$A \rightarrow B$ 和 $A \leftrightarrow B$ 都是合式公式。

   4. 如果 $A$ 是合式公式，$x$ 是任意变元，且 $A$ 中无 $(\forall x)$ 或 $(\exists x)$ 出现，则 $(\forall x) A(x)$ 和 $(\exists x) A(x)$ 都是合式的公式；

   5. 当且仅当有限次使用规则 i. ~ iv. 由逻辑联结词、圆括号构成的有意义的字符串

   • 注意到此处最外层可以无括号。（神秘的教材）

3. 量词分配律仅有

   $(\forall x)(A(x) \wedge B(x)) \iff (\forall x) A(x) \wedge (\forall x) B(x)$

   $(\exists x)(A(x) \vee B(x)) \iff (\exists x) A(x) \vee (\exists x) B(x)$

   其他的，存在

   $(\forall x) A(x) \vee (\forall x) B(x) \implies (\forall x)(A(x) \vee B(x))$

   $(\exists x)(A(x) \wedge B(x)) \implies (\exists x)A(x) \wedge (\exists x) B(x)$

4. 量词交换式：

   同种量词可任意交换，否则，

   $(\forall x)(\forall y) \implies (\exists y)(\forall x) \implies (\forall x)(\exists y) \implies (\exists x)(\exists y)$

5. 量词逻辑的自然演绎推理注意：

   • US 应在 ES 之后指定。

   • 脱去多重量词应该由外而内，恢复多重量词应该由内而外。

6. 斯柯林范式（大概不考）（其实我觉得 ppt 和书上写的都很错）

   前束范式中所有存在量词位于全称量词之前。

Chapter 3：集合论#

1. 容斥原理：

   $\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|$

Chapter 4：二元关系#

1. 多重序元：$n$ 重序元是一个序偶，它的第一元素是 $(n - 1)$ 重序元。

2. 笛卡尔积一般不满足交换律，因为序元顺序，不满足结合律。

3. 笛卡尔积对 $\cup$、$\cap$ 存在左/右的分配律。

4. $R | S$：设 $R$ 为集合 $A$ 上的二元关系且 $S \subseteq A$，则称 $S$ 上的二元关系 $R \cap (S \times S)$ 为 $R$ 在 $S$ 上的压缩，记为 $R | S$，并称 $R$ 为 $R | S$ 在 $A$ 上的开拓。

   则有：

   • 若 $R$ 是自反的，则 $R | S$ 也是自反的；

   • 若 $R$ 是反自反的，则 $R | S$ 也是反自反的；

   • 若 $R$ 是对称的，则 $R | S$ 也是对称的；

   • 若 $R$ 是反对称的，则 $R | S$ 也是反对称的；

   • 若 $R$ 是可传递的，则 $R | S$ 也是可传递的；

   即：不可传递性不会继承。

5. $domR$: R 的定义域

   $ranR$: R 的值域

   $fldR = domR \cup ranR$: R 的域

6. 关系的合成对 $\cup$ 有分配律， 而对于 $\cap$，显然先 $\cap$ 会损失一部分序偶。

7. 关系的合成满足结合律

8. 关系的合成与求逆运算较简单。

9. 集合的划分是覆盖的特殊情况，

   秩为划分的大小，秩最大的划分成为最大划分。

   划分可以进行加细（真加细）。

10. 可以用子集进行划分（Venn 图），生成的类称为极小项/完全交集。

11. 设 $R$ 是集合 $A$ 上的等价关系，则 $A$ 中等价于元素 $a$ 的所有元素组成的集合称 $a$ 生成的等价类，用 $[a]_r$ 表示。由 $A$ 的各元素所生成的等价类必定覆盖 $A$，决定了集合 $A$ 的一种划分。

12. $R$ 的各元素生成的等价类集合按 $R$ 去划分集合 $X$ 的商集，记作 $X/R$。

13. 全域关系：$X \times X$

    恒等关系：${<x, x> | x \in X}$

    以上两种均称为 $X$ 的平凡划分。

14. 相容关系：自反、对称。

    相容关系定义集合的覆盖，

    等价关系定义集合的划分。

15. 偏序：自反、反对称、可传递。

16. 教材中的拟序关系：反自反、可传递（反对称可以推出）。 实际上是严格偏序。

17. 全序：任意两个元素可比较的偏序。此时 Hasse 图为链。

18. • 最小（大）成员：于集合内，唯一。不一定存在。

    • 极小（大）成员：于集合内，不唯一。一定存在。

    • 下（上）界：位置无所谓，不唯一。不一定存在。

    • 最小上界（最大上界）：唯一。不一定存在。

19. 良序：存在最小成员。

    自然数集在通常序下是良序集，

    整数集在通常序下不是良序集。

Chapter 9：图的基本概念及其矩阵表示#

1. 对图的定义：$G = <V, E, \psi>$（神经病啊讨论有标签图）

3. 竞赛图：给完全图每条边指派方向。

   优先图：程序语句与前面语句的相关性表示而成有向图。

4. 零图：$E = \emptyset, \psi = \emptyset$

   平凡图：一阶零图

   圈图（$C_n(n \geq 3)$）：多边形图

   轮图：给圈图加个点，与原本每个点连边得到。

   $d$ 度正则图：所有点的度数均为 $d$ 的无向图。

5. 两个图同构必须满足的必要条件是：

   1. 顶点个数相同

   2. 边数相同

   3. 度数相同的顶点个数相同

   4. $K$ 度顶点的导出子图同构

6. 设 $G = <V, E, \psi>$、$G^{'} = <V^{'}, E^{'}, \psi^{'}>$ 为图。

   1. 若 $V^{'} \subseteq V, E^{'} \subseteq E, \psi^{'} \subseteq \psi$，则 $G^{'}$ 为 $G$ 的子图，$G$ 为 $G^{'}$ 的母图，记作 $G^{'} \subseteq G$。

   2. 若 $V^{'} \subseteq V, E^{'} \subsetneq E, \psi^{'} \subsetneq \psi$，则 $G^{'}$ 为 $G$ 的子图，$G$ 为 $G^{'}$ 的母图，记作 $G^{'} \subsetneq G$。

   3. 若 $V^{'} = V, E^{'} \subseteq E, \psi^{'} \subseteq \psi$，则 $G^{'}$ 为 $G$ 的生成子图。

7. • 设 $G = <V, E, \psi>$，$V^{'} \subseteq V \wedge V^{'} \neq \emptyset$，以 $V^{'}$ 为结点集合，以起点和终点均在 $V^{'}$ 中的边的全体为边集合的 $G$ 的子图，称为由 $V^{'}$ 导出的 $G$ 的子图，记为 $G[V^{'}]$。

   • 设 $G = <V, E, \psi>$，$E^{'} \subseteq E \wedge E^{'} \neq \emptyset$，以 $E^{'}$ 为边集，以与 $e \in E^{'}$ 关联的结点的全体为点集合的 $G$ 的子图，称为由 $E^{'}$ 导出的 $G$ 的子图。

8. 对于图 $G = <V, E, \psi>$ 和 $G^{'} = <V^{'}, E^{'}, \psi^{'}>$

   1. 如果对于任意 $e \in E \cap E^{'}$ 具有 $\psi(e) = \psi^{'}(e)$， 则称 $G$ 和 $G^{'}$ 是可运算的。

   2. 如果 $V \cap V^{'} = E \cap E^{'} = \emptyset$，则称 $G$ 和 $G^{'}$ 是不相交的。

   3. 如果 $E \cap E^{'} = \emptyset$，则称 $G$ 和 $G^{'}$ 是边不相交的。

   • sb 非要用有标签图，导致这里定义很困难。。。

9. 边不重 $\rightarrow$ 简单路径

   点不重 $\rightarrow$ 基本路径

   基本回路 $\iff$ 圈

10. 如果有向图 $G$ 有子图 $G^{'}$ 满足：对于的任意结点 $v$，$d_{G^{'}}^{+} > 0$（或 $d_{G^{'}}^{-} > 0$），则 $G$ 有有向回路

11. 设 $G$ 为无向图，$R$ 是 $G$ 中结点之间的连通关系，由 $R$ 可将 $V(G)$ 划分成若干等价类，由它们导出的导出子图称 $G$ 的连通分支，其个数记为 $\omega(G)$。

12. 设 $G$ 是有向图。

    1. 如果 $G$ 中任意两个结点都互相可达，则称 $G$ 是强连通的。

    2. 如果对于 $G$ 的任意两结点，必有一个结点可达另一个结点，则称 $G$ 是单向连通的。

    3. 如果 $G$ 的基础图是连通的，则称 $G$ 是弱连通的。

13. 无向图 $G$ 的极大连通子图称为 $G$ 的分支。（同 11. ）

    设 $G$ 是有向图：

    1. $G$ 的极大强连通子图称为 $G$ 的强分支。

    2. $G$ 的极大单向连通子图称为 $G$ 的单向分支。

    3. $G$ 的极大弱连通子图称为 $G$ 的弱分支。

Chapter 12：特殊图#

1. 欧拉图/欧拉路/欧拉回路：很简单

2. Hamilton 图：

   1. 必要条件（性质）：设 $G = <V, E>$ 是哈密顿图，则对于 $V$ 的任意非空真子集 $S$，均有 $\omega(G-S) \leq \lvert S \rvert$。
   • 可用于判断一个图是否不是 Hamilton 图。
   2. 充分条件：设 $G$ 是 $n(n \geq 3)$ 的无向简单图，若对于 $G$ 中任意不相邻的顶点 $v_i, v_j$，均有 $d(v_i)+ d(v_j) \geq n - 1$，则 $G$ 中存在哈密顿通路。若对于 $G$ 中任意不相邻的顶点 $v_i, v_j$，均有 $d(v_i)+ d(v_j) \geq n$，则 $G$ 中存在哈密顿回路，从而 $G$ 为哈密顿图。
   • 可用于判断一个图是否是 Hamilton 图。

3. 二分图：

   匹配无所谓个数，存在极大和最大匹配，最大一定是极大，都可以有多个。

   若匹配数等于 $V_1$，则为从 $\lvert V_1 \rvert$ 到 $\lvert V_2 \rvert$ 的完美匹配。

   设 $V_1$ 和 $V_2$ 是二部图 $G$ 的互补结点子集，$t$ 是正整数。对于 $V_1$ 中的每个结点，在 $V_2$ 中至少有 $t$ 个结点与其邻接。对于 $V_2$ 中的每个结点，在 $V_1$ 中至多有 $t$ 个结点与其邻接。则存在 $V_1$ 到 $V_2$ 的完美匹配。

4. 平面图

   设 $G$ 是一个无向图。图 $G$ 中不存在任何与 $K_5$、$K_{3, 3}$ 同构的子图，当且仅当图 $G$ 是个平面图。

   包含有多边形的图 $G$ 的所有面的边界的多边形，称 $G$ 的极大基本循环。

   欧拉公式：设 $G = <V, E, \psi>$ 是个具有 $k$ 个面（包括无限面在内）的 $(n, m)$ 多边形的图。则 $n - m + k = 2$

   对偶图：边变点、点变边。记作 $G^{*}$。$G = G^{*}$ 则为自对偶图。

   图着色：转换为对偶图，根据四色定理一定能着色出来。