离散数学复习

2019-07-09

幂集

P(A)

容斥原理

二元关系

1、有序对/序偶：由两个元素x和y按一定顺序排成二元组，记作；同理可得有序n元组

2、笛卡儿积：设A，B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对。所有这样的有序对组成的集合叫做A与B的笛卡儿积

$A \times B = {<x, y> | x \in A, y \in B}$

性质：不满足交换律、结合律

3、二元关系：集合中两个元素之间的某种关系

定义：如果一个集合满足以下条件之一：（1）集合非空，且所有元素都是有序对（2）集合为空

则称该集合为一个二元关系，简称为关系，记作 $R$

$<x, y> \in R，记作xRy$

4、从A到B的关系与A上的关系

设A，B为集合， $A \times B$ 的任何子集所定义的二元关系叫做从A到B的关系，当A=B时叫做A上的二元关系

5、A上的重要关系

全域关系 $E_A$ ；恒等关系 $I_A$ ；小于等于关系 $L_A$ ；整除关系 $D_A$ ；包含关系

6、关系的表示：关系的集合表达式；关系矩阵；关系图

关系图仅适用于表示A上的关系

关系的运算

1、关系的定义域与值域

2、逆与合成

$R^{-1} = {<y, x> | <x, y> \in R} \\ R \circ S = {<x, y> | \exist z (<x, z> \in S \and <z, y> \in R)}$

3、限制和像

4、A上关系的幂运算

设R为A上的关系，n为自然数，则R的n次幂定义为：

$(1)R^0 = {<x, x> | x\in A} = I_A \\ (2)R^{n + 1} = R^n \circ R$

5、幂的性质

$（1）当关系图中有回路时：R^2 = R^4 = ... = R^{2k}; R^3 = R^5 = ... = R^{2k + 1}\\ (2)R^m \circ R^n = R^{m + n}\\ (3)(R^m)^n = R^{mn}$

关系的性质

1、自反性；反自反性

在自反性方面R有三种可能：自反的、反自反的、既非自反又非反自反的

2、对称性

可以即对称又反对称。如$R = \{ | x \in R \}$

3、传递性

关系的闭包运算

1、设 $R \subseteq A \times A$ ，那么包含R而使之具有自反性质的最小关系，称之为R的自反闭包。对称闭包和传递闭包同理。

自反闭包记作 $r(R)$ ；对称闭包 $s(R)$ ；传递闭包 $t(R)$

2、计算方法：

（1）逻辑运算方法：设R是A上的任一关系，则

$r(R) = R \cup I_A\\ s(R) = R \cup R^{-1}\\ t(R) = R \cup R^2 \cup ... \cup R^{n - 1}$

（2）矩阵形式（3）关系图法

等价关系和偏序关系

1、等价关系：集合A上的关系R是自反的，对称的和传递的。

设R是一个等价关系，若$\in R$，则称x等价于y，记作x~y

2、相容关系：R是A上的关系，且A是自反的，对称的

等价关系一定是相容关系；相容关系不一定是等价关系

3、偏序关系：集合A上的关系R是自反的，反对称的和传递的，记作” $\leq$ ”

设R为偏序关系，如果$\in R $，则记作$ x \leq y$，读作“x小于等于y”。注意：这里的“小于等于”不是指数的大小，而是在偏序关系中的顺序性。

例子：（1）任何集合A上的恒等关系（2）集合A的幂集P（A）上的包含关系（3）实数集上的小于等于、大于等于关系（4）正整数集上的整除关系

4、相关概念

偏序集：集合A和偏序关系 $R_\leq$ 构成一个偏序集，记作$$。

可比：对于任意两个元素x和y，若 $x \leq y或 y \leq x$ ，则x与y是可比的

全序关系与全序集：若A中任意两个元素都是可比的，则 $R_\leq$ 为全序关系，$$为全序集

盖住：如果 $x\leq y$ ，且不存在z使得 $x \leq z \leq y$ （不是间接的），则称y能盖住x

5、哈斯图

6、偏序集中的一些特殊元素

极小元；极大元；最小元；最大元；上界；下界；上确界（最小上界）；下确界（最大下界）