面向计算机的科学的离散数学 （期中） 对应计算机系离散数学（1）

tips:本文逻辑和顺序可能混乱，因为作者是根据题目进行知识点的复习

1.在集合A上等价关系个数的计算

等价关系与划分一一对应，非空集合A上的等价关系个数等于A的划分个数，即等价关系个数等于划分个数。 转换为数学模型：即将n个小球放入m个相同的盒子中，并且不能出现空盒，不同的放球方式代表着不同的划分方式 再转换为第二类斯特林数：$S(n,m)$，代表以上方法

第二类斯特林数计算方法

1. 递推公式： 注意到等价于背包问题

4元集等价关系计算

1. 方法：利用第二类斯特林数计算
2. 过程：N = S(4,1) + S(4,2) + S(4,3) + S(4,4) = 1=7+6+1 = 15

6元集等价关系计算

1. 方法：利用第二类斯特林数计算
2. 过程：
   

Tips：列出从1-10的BEll数，为 1 , 2 , 5 , 15 , 52 , 203 , 877 , 4140 , 21147 , 115975

2.证明两个集合等势

方法：想办法构造一个双射从而使两个集合之间能够一一对应 常用方法：对于证明类似于[1 , 0]等势于 ，可以使用正切函数或余切函数进行构造

3.概念辨析

1. A不相容：对于任一解释，A中至少有一子句为假（或者称之为永假或不可满足或矛盾）
2. A相容：存在一种解释，使得A中所有子句为真（或称之为可满足）
3. Skolem范式：与A在不相容意义下保持等价
4. 良序集的条件：1.必须为全续集 2.任何非空子集必须有最小元素

4.证明无限集和实数集等势

方法：构造函数形如

$$f(x) = x , x \in R/(Q \cup Q) + \sqrt{2}$$

$$f(x) = g(x) , x \in (Q\cup Q) + \sqrt{2}$$

其中g(x)为 的映射。由于前者为可数集并可数集等于可数集，可数集与可数集之间一定存在一一映射，g(x)存在。 定义域为R，值域为 证明了该函数为从$ R $到$ R / Q $的一一映射，即等势得证

转自知乎：https://zhuanlan.zhihu.com/p/385762588

5.一些基础（虽然可能不值得写）

1. 2. 3. 4.空关系是一种等价关系，具有传递性，自反性，对称性 5. 6.一个偏序关系的极大元需要属于这个集合，且极大元的定义是没有比它更大的元素 7.上确界的定义是每个元素都小于等于上确界，且不存在小于上确界的元素成为关系的上界

6.根据无穷公理构造的自然数

$$1 = \{0\}$$

$$2 = \{0, 1\}$$

以此类推 我们可以得到

$$\cap 1(2, 3 , 4...) = 0$$

$$\cup n = n - 1$$

7.考虑在一个集合中各种关系的数量

1. $反对称关系：对于集合A有n个元素，由于对于任意的 < a, b > , < b , a > 或没有这一项有3种可能 ， 且对于 < a , a> 都存在有或没有的问题 ， 因此答案为 2^n 3^x , 其中x为点之间连线的个数$
2. $反自反且反对称关系：显然，为去除 <a , a> 的情况，即答案为3^x$
3. 以此类推

8.考虑各种闭包对于关系的破坏

显然自反性(r)，对称性(s)不会因为关系的扩张而受到影响，而对称性不一定，因此，我们需要考虑对这种情况谨慎处理

9.求取主析取范式和主合取范式的一些方法

求取主析取范式基本策略：向式子后面补充 ,变成一个一坨巨大的东西之后慢慢利用分配率等方式进行化简 求取主合取范式：利用主析取范式和主合取范式之间的关系可以很快求解，大概为找到剩余的项，然后分别用 减掉即可