离散数学

集合论

将A的所有不同子集构成的集合成为A的幂集，记作P(A)

德摩根率：集合并集的补集=集合补集的交；集合交集的补集=集合补集的并集

如果存在A,B and A和B之间一一对应的关系，那么称A和B等势。

计数问题

从n个人中选出r个人围成圆桌而坐成为环形r排列

$$P_c(n,r)=\frac{P_n^r}{r}=\frac{n!}{r * (n-r)!}$$

命题逻辑

重言式永远为真，矛盾式永远为假，如果不是永假的就是可满足的

p—>Q<==>非p ∩ Q（只有p是真且Q为假的时候才是假的）

∩是合取，∪是析取

有限个文字的析取称为子句，有限个文字的合取称为短句。

• US（全称特指规则）
• ES（存在特指规则）
• UG（全称推广规则）
• EG（存在特指规则）

二元关系

由两个元素x，y按照一定的次序组成的二元组成为有序偶对，简称序偶，记作

笛卡尔积：$A \times B=\{ | x\in A \bigwedge y\in B\}$

自反性：对于 有 $\in R$，说明R在A上是自反的。

反自反性：对于 有 $\notin R$，说明R在A上是反自反的。

反对称性：对于 如果$\in R\in R$ 那么x=y

传递性：设R是非空集合上的A的关系，对于 ，如果有$ \in R \in R \in R$ ，则称关系R是传递的。

关系闭包是增加最少元素使其具备所需要的性质的扩充。

特殊关系

等价关系：设R是定义在非空集合A上的关系，如果R是自反的，对称的，传递的，则称R是A上的等价关系。

拟序关系：设R是非空集合A上的关系，如果R是反自反的、反对称的和传递的，则称R是A上的拟序关系。

偏序关系：设R是非空集合A上的关系，如果R是自反的，反对称的和传递的，则称R是A上的偏序关系。

全序关系：在偏序关系中，如果对于，总有 或者 ，二者一定有一个成立，则称关系是全序关系。