知识点总复习

MA238 离散数学

迮炎杰，2021年6月

MA238 离散数学 由两部分组成：

• 数理逻辑与集合论

• 图论与代数结构

Part1 数理逻辑与集合论

2.5 对偶式

将合取和析取反一下，把T和F反一下。

2.6 范式（命题逻辑部分）

主析取范式和主合取范式互相转换：

• 这一部分只可意会，注意极小项和极大项的性质

5.3 范式（谓词逻辑部分）

前束范式：量词都在前面

Skolem标准形：

• 一种是存在量词都在全称量词的右边(这种也叫存在前束范式)

• 另一种是直接消去存在量词

5.5 推理演算

1. 全称量词消去规则

2. 全称量词引入规则

3. 存在量词消去规则

4. 存在量词引入规则

9.3 集合的运算

广义并：就是把一个集合的元素拿出来求并

广义交：类似广义并。

幂集：

$$P(A)=\{x|x\subseteq A\}$$

10.4 关系的性质

存在非空集合，既不是自反的，又不是非自反的。但是不存在非空集合，既是自反的，又不是非自反的。

对称性和反对称性，既可以同时满足，也可以同时不满足。

10.5 关系的闭包

自反，对称，传递

定理10.5.12： 对非空集合A上的关系R，有

1. rs(R)=sr(R)

2. rt(R)=tr(R)

3. st(R)$\subseteq$ts(R)

速记方法：有自反的可以交换，st属于ts

10.6 等价关系和划分

自反、对称、传递的关系。

求等价关系的步骤：

• 先求有多少种划分

• 有一种划分就是一种等价关系

10.8 偏序关系

线性序：也称全序。

全序：任何两个元素都有关系。

良序：对偏序集$<A,\leq>$，如果A的任何非空子集都有最小元，则称$\leq$为良序关系，称该集为良序集。

定理10.8.6: 一个良序集一定是一个全序集。（反之不一定）

定理10.8.7: 一个有限的全序集一定是良序集。

Part2 图论与代数结构

2.3 欧拉道路与回路

欧拉回路的充要条件

G中各结点的度数为偶数。

欧拉道路的充要条件

只有2个度数为奇数的点。

2.3 哈密尔顿道路与回路

H道路充分条件

$$\forall v_i,v_j \in G, d(v_i)+d(v_j)\geq n-1$$

H回路充分条件

$$\forall v_i,v_j \in G, d(v_i)+d(v_j)\geq n$$

$$\forall v_i\in G, d(v_i)\geq \frac n2$$

$$G:\forall v_i, v_j(不相邻), d(v_i)+d(v_j)\geq n$$

$$则G存在H回路的充要条件为G+(v_i,v_j)有H回路。$$

3.6 Huffman树

3.7 最短树

Kruskal算法

过程：

1. 初始化一个空的树

2. 挑一个全局最短的边

3. 如果加上这条边没有回路，就加上吧。顺便在原图中去掉

4. 重复2和3，直到树的边为n-1。

Prim算法

基本思想：利用树的邻边进行扩展而不是全局最小。

8.2 群、群的基本性质

群：

• 结合律

• 单位元

• 幺元

阿贝尔群：

• 满足交换律的群

群G的子群的充要条件：

• 运算封闭

• 有单位元，且等于G的单位元

• 任意元素有逆元，且等于G中的逆元

子群判断定理：

• 对于G的非空子集H，H是G的子群的充要条件是：任意a，b属于H，$ab^{-1}$也属于H。

8.3 循环群 群的同构

循环群：

$$G=<a>=\{ a^k| k \in Z\}$$

a称为G的生成元。

定理8.3.1:

• 若$O=\infty$， 生成元只有$a$或$a^{-1}$

• 若$O=n$，生成元有$\varphi(n) $个（欧拉函数，小于n且与n互素的元素个数）。