离散数学（三）——集合与计数

一、集合的基本计算

定义 1.（集合族）

假设有两个集合

𝐴, 𝐵

，以及一个集合族

𝒜︀

。所谓集合族，是指一个以集合为元素的集合。

1.集合交

两个集合的交记为 $𝐴 \cap 𝐵$ ，其中的元素满足：

𝐴 \cap 𝐵 = {𝑥 | 𝑥 \in 𝐴 \land 𝑥 \in 𝐵}

也即元素需要同时属于这两个集合。

一个集合族具有广义交，记为 $⋂ 𝒜︀$ ，定义如下：

定义 2.（广义交）

⋂ 𝒜︀ = {𝑥 | \forall 𝑆 (𝑆 \in 𝒜︀ \to 𝑥 \in 𝑆)}

在常见的情况下，集合族表示为 $𝒜︀ = {𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}}$ ，此时可以写为：

⋂ 𝒜︀ = ⋂_{𝑖 = 1}^{𝑛} 𝐴_{𝑖} = 𝐴_{1} \cap 𝐴_{2} \cap \dots \cap 𝐴_{𝑛}

集合交显然具有交换律、结合律、幂等律：

𝐴 \cap 𝐵 = 𝐵 \cap 𝐴

(𝐴 \cap 𝐵) \cap 𝐶 = 𝐴 \cap (𝐵 \cap 𝐶)

𝐴 \cap 𝐴 = 𝐴

同时，集合之交与子集的关系有：

𝐴 \cap 𝐵 \subseteq 𝐴, 𝐴 \cap 𝐵 \subseteq 𝐵

𝐶 \subseteq 𝐴 \cap 𝐵 当且仅当 𝐶 \subseteq 𝐴 \land 𝐶 \subseteq 𝐵

2.集合并

两个集合的并记为 $𝐴 \cap 𝐵$ ，其中的元素满足：

𝐴 \cup 𝐵 = {𝑥 | 𝑥 \in 𝐴 \lor 𝑥 \in 𝐵}

也即元素只需属于这两个集合中的某一个即可。

一个集合族具有广义并，记为 $⋃ 𝒜︀$ ，定义如下：

定义 3.（广义并）

⋃ 𝒜︀ = {𝑥 | \exists 𝑆 (𝑆 \in 𝒜︀ \land 𝑥 \in 𝑆)}

在常见的情况下，集合族表示为 $𝒜︀ = {𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}}$ ，此时可以写为：

⋃ 𝒜︀ = ⋃_{𝑖 = 1}^{𝑛} 𝐴_{𝑖} = 𝐴_{1} \cup 𝐴_{2} \cup \dots \cup 𝐴_{𝑛}

集合交显然具有交换律、结合律、幂等律：

𝐴 \cup 𝐵 = 𝐵 \cup 𝐴

(𝐴 \cup 𝐵) \cup 𝐶 = 𝐴 \cup (𝐵 \cup 𝐶)

𝐴 \cup 𝐴 = 𝐴

同时，集合之交与子集的关系有：

𝐴 \subseteq 𝐴 \cup 𝐵, 𝐵 \subseteq 𝐴 \cup 𝐵

𝐴 \cap 𝐵 \subseteq 𝐶 当且仅当 𝐴 \subseteq 𝐶 \land 𝐵 \subseteq 𝐶

3.集合差与补

两个集合的差记为 $𝐴 - 𝐵$ ，其中的元素满足：

𝐴 - 𝐵 = {𝑥 | 𝑥 \in 𝐴 \land 𝑥 \notin 𝐵}

集合差显然是不满足交换律、结合律、幂等律的。在集合差的基础上，可以引出集合补的定义。全集 $𝑈$ 与集合 $𝐴$ 的差称为集合 $𝐴$ 的绝对补，一般简称为补，记为：

集合差满足下述等式：

(𝐴 - 𝐵) - 𝐶 = (𝐴 - 𝐶) - 𝐵 = (𝐴 - 𝐶) - (𝐵 - 𝐶)

4.集合对称差

集合的对称差是将两个集合的并剔除掉其集合交之后的集合，记为 $𝐴 \oplus 𝐵$ ：

\begin{aligned} 𝐴 \oplus 𝐵 & = (𝐴 \cup 𝐵) - (𝐴 \cap 𝐵) \\ = (𝐴 - 𝐵) \cup (𝐵 - 𝐴) \\ = {𝑥 | (𝑥 \in 𝐴 \land 𝑥 \notin 𝐵) \lor (𝑥 \notin 𝐴 \land 𝑥 \in 𝐵)} \end{aligned}

集合的对称差显然满足交换律、结合律，即：

𝐴 \oplus 𝐵 = 𝐵 \oplus 𝐴

(𝐴 \oplus 𝐵) \oplus 𝐶 = 𝐴 \oplus (𝐵 \oplus 𝐶)

5.幂集

一个集合 $𝐴$ 的幂集是一个集合族，记为 $℘ (𝐴)$ 或 $2^{𝐴}$ 。集合 $𝐴$ 的幂集中的元素是集合 $𝐴$ 的所有子集，即：

定义 4.（幂集）

℘ (𝐴) = {𝑆 | 𝑆 \subseteq 𝐴}

这意味着对于任何集合来说，空集及其本身都是其幂集的元素(注意是元素不是子集)，空集 $⌀$ 这个元素需要显式地写出来。比如集合 $𝐴 = {1, 2, 3}$ ，其幂集是：

℘ (𝐴) = {⌀, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

空集是一个特殊的集合，关于它有一些注意事项：

℘ (⌀) = {⌀}, ℘ (℘ (⌀)) = {⌀, {⌀}}

⌀ \subseteq ℘ (⌀), ⌀ \in ℘ (⌀)

{⌀} \subseteq ℘ (⌀), {⌀} \notin ℘ (⌀)

{⌀} \subseteq ℘ (℘ (⌀)), {⌀} \in ℘ (℘ (⌀))

{{⌀}} \subseteq ℘ (℘ (⌀)), {{⌀}} \notin ℘ (℘ (⌀))

可以看到在空集的幂集中，“属于”比“子集”要严格得多。

幂集运算会保持子集关系，这是说若 $𝐴 \subseteq 𝐵$ ，那么 $℘ (𝐴) \subseteq ℘ (𝐵)$ 。

另外，对集合 $𝐴$ 的幂集使用广义并，可以使其恢复为集合 $𝐴$ 。这是因为集合本身必是幂集的元素，而幂集中的其他元素都是这个集合的子集：

⋃ ℘ (𝐴) = 𝐴

注 1.（为什么幂集可以记作

2^{𝐴}

？）

用 $| 𝐴 |$ 表示集合中的元素个数。生成 $𝐴$ 的幂集时，可以用二进制串标记每个元素是否出现：不出现记为 $0$ ，出现记为 $1$ 。

例如 $𝐴 = {1, 2, 3}$ 时，二进制串 $001$ 对应子集 ${3}$ ， $000$ 对应空集。遍历全部长度为 $| 𝐴 |$ 的二进制串，恰好生成 $𝐴$ 的所有子集。因此：

| ℘ (𝐴) | = | 2^{𝐴} | = 2^{| 𝐴 |}

6.划分

将一个集合 $𝐴$ 划分为几个互不相交的部分，每个部分自成一个集合，那么这些集合就可以形成一个集合族，称为 $𝐴$ 的划分，记为 $ℱ︀$ 。划分中的每一个集合称为一个划分块。显然地有：

划分中的元素——是一个集合——不是空集，即任意 $𝑆 \in ℱ︀$ 都有 $𝑆 \neq ⌀$ ；划分中的任意两个元素都不相交，即交集为空集： $𝑆_{1} \cap 𝑆_{2} = ⌀$ ；划分的各个部分可以合成为原集合，也就是划分的广义并为原集合本身： $⋃ ℱ︀ = 𝐴$ 。

二、集合等式与子集关系

1.集合等式

集合运算与逻辑运算间极其相似。集合与可以看做逻辑与，集合并可以看做逻辑或，集合补可以看做逻辑非，全集可以看做真，空集可以看做假。在此基础上，我们可以给出关于集合的基本等式：

表 1 集合等式

序号	名称	集合等式
1	同一律	$\begin{matrix} 𝐴 \cap 𝑈 = 𝐴 \\ 𝐴 \cup ⌀ = 𝐴 \end{matrix}$
2	零律	$\begin{matrix} 𝐴 \cup 𝑈 = 𝑈 \\ 𝐴 \cap ⌀ = ⌀ \end{matrix}$
3	矛盾律
4	排中律
5	双重否定律
6	幂等律	$\begin{matrix} 𝐴 \cap 𝐴 = 𝐴 \\ 𝐴 \cup 𝐴 = 𝐴 \end{matrix}$
7	交换律	$\begin{matrix} 𝐴 \cap 𝐵 = 𝐵 \cap 𝐴 \\ 𝐴 \cup 𝐵 = 𝐵 \cup 𝐴 \end{matrix}$
8	结合律	$\begin{matrix} (𝐴 \cap 𝐵) \cap 𝐶 = 𝐴 \cap (𝐵 \cap 𝐶) \\ (𝐴 \cup 𝐵) \cup 𝐶 = 𝐴 \cup (𝐵 \cup 𝐶) \end{matrix}$
9	分配律	$\begin{matrix} 𝐴 \cap (𝐵 \cup 𝐶) = (𝐴 \cap 𝐵) \cup (𝐴 \cap 𝐶) \\ 𝐴 \cup (𝐵 \cap 𝐶) = (𝐴 \cup 𝐵) \cap (𝐴 \cup 𝐶) \end{matrix}$
10	吸收律	$\begin{matrix} 𝐴 \cap (𝐴 \cup 𝐵) = 𝐴 \\ 𝐴 \cup (𝐴 \cap 𝐵) = 𝐴 \end{matrix}$
11	德摩根律
12	集合差等式
13	相对德摩根律	$\begin{matrix} 𝐴 - (𝐵 \cap 𝐶) = (𝐴 - 𝐵) \cup (𝐴 - 𝐶) \\ 𝐴 - (𝐵 \cup 𝐶) = (𝐴 - 𝐵) \cap (𝐴 - 𝐶) \end{matrix}$

其中，相对德摩根律有一点分配律的样子，但需要注意相对德摩根律会使交和并互换。

2.子集关系

子集关系其实已经在之前陈述过，这里再统一说明一次：

(1)集合交：

两个集合的交集必是两个集合的子集：

𝐴 \cap 𝐵 \subseteq 𝐴, 𝐴 \cap 𝐵 \subseteq 𝐵

两个集合的交集的子集必是两个集合的子集：

𝐶 \subseteq 𝐴 \cap 𝐵 当且仅当 𝐶 \subseteq 𝐴 \land 𝐶 \subseteq 𝐵

交运算保持子集关系：

𝐴 \subseteq 𝐵 \to 𝐴 \subseteq (𝐴 \cap 𝐵)

因此可用下式判断子集关系：

𝐴 \subseteq 𝐵 当且仅当 𝐴 \cap 𝐵 = 𝐴

(2)集合并：

两个集合必是两个集合的并集的子集：

𝐴 \subseteq 𝐴 \cup 𝐵, 𝐵 \subseteq 𝐴 \cup 𝐵

两个集合的并集是另一集合的子集，则两个集合必是另一集合的子集：

𝐴 \cap 𝐵 \subseteq 𝐶 当且仅当 𝐴 \subseteq 𝐶 \land 𝐵 \subseteq 𝐶

并运算保持子集关系：

𝐴 \subseteq 𝐵 \to 𝐴 \subseteq (𝐴 \cup 𝐵)

因此可用下式判断子集关系：

𝐴 \subseteq 𝐵 当且仅当 𝐴 \cup 𝐵 = 𝐵

(3)集合差：

两集合之差必是前一个集合的子集：

𝐴 - 𝐵 \subseteq 𝐴

因此可用下式判断子集关系：

𝐴 \subseteq 𝐵 当且仅当 𝐴 - 𝐵 = ⌀

这实际等价于：

(4)幂集：

幂集运算保持子集关系：

𝐴 \subseteq 𝐵 \to ℘ (𝐴) \subseteq ℘ (𝐵)

两个集合的幂集之并，是两个集合之并的幂集的子集(反之则不一定)：

℘ (𝐴) \cup ℘ (𝐵) \subseteq ℘ (𝐴 \cup 𝐵)

两个集合之交的幂集，是两个集合的幂集之交：

℘ (𝐴 \cap 𝐵) = ℘ (𝐴) \cap ℘ (𝐵)

三、计数

现在我们讨论集合中元素个数的问题，也就是组合数学中的计数问题。

1.加法原理

对于集合 $𝐴$ ，有的时候给出它的一个划分 $ℱ︀ = {𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}}$ 会更简单，那么 $𝐴$ 中的元素个数就是划分中的所有集合中元素个数之和，即：

| 𝐴 | = | 𝐴_{1} | + | 𝐴_{2} | + \dots + | 𝐴_{𝑛} |

2.乘法原理

假设有集合 $𝐴_{1}, 𝐴_{2}, \dots, 𝐴_{𝑛}$ ，那么由这些集合的笛卡尔积形成的集合 $𝐴 = 𝐴_{1} \times 𝐴_{2} \times \dots \times 𝐴_{𝑛}$ 中的元素是一个 $𝑛$ 元组 $⟨ 𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑛} ⟩$ ，那么能生成的 $𝑛$ 元组个数，也就是 $𝐴$ 中元素的个数是：

| 𝐴 | = | 𝐴_{1} | \times | 𝐴_{2} | \times \dots \times | 𝐴_{𝑛} |

3.减法原理

在任意有穷集的情况下，两个集合 $𝐴, 𝐵$ 之间有：

| 𝐴 - 𝐵 | = | 𝐴 | - | 𝐴 \cap 𝐵 |

在 $𝐵 \subseteq 𝐴$ 的特殊情况下上式就是减法原理：

这也可以表述为：已知 $𝐴 \subseteq 𝑈$ ，那么为了得到 $𝐴$ 的元素个数，显然可以通过从全集中剔除掉不属于 $𝐴$ 的元素来计数。

4.除法原理

假设有两个集合 $𝐴, 𝐵$ ，对任意 $𝐴$ 中元素总有 $𝑘$ 个 $𝐵$ 中元素与之对应，那么显然有：

| 𝐴 | = \frac{| 𝐵 |}{𝑚}

在特殊情况下，也就是一一对应的情况，那么就有：

| 𝐴 | = | 𝐵 |

5.容斥原理

最简单的情况下，两个集合 $𝐴, 𝐵$ 的容斥原理是：

| 𝐴 \cup 𝐵 | = | 𝐴 | + | 𝐵 | - | 𝐴 \cap 𝐵 |

三个集合时：

| 𝐴 \cup 𝐵 \cup 𝐶 | = | 𝐴 | + | 𝐵 | + | 𝐶 | - | 𝐴 \cap 𝐵 | - | 𝐴 \cap 𝐶 | - | 𝐵 \cap 𝐶 | + | 𝐴 \cap 𝐵 \cap 𝐶 |

当然也可以进一步扩展为 $𝑛$ 个集合的情况：

\begin{aligned} | ⋃_{𝑖 = 1}^{𝑛} 𝐴_{𝑖} | & = | 𝐴_{1} \cup 𝐴_{2} \cup \dots \cup 𝐴_{𝑛} | \\ = \sum_{𝑖 = 1}^{𝑛} | 𝐴_{𝑖} | - \sum_{1 \leq 𝑖 < 𝑗 \leq 𝑛} | 𝐴_{𝑖} \cap 𝐴_{𝑗} | + \\ \sum_{1 \leq 𝑖 < 𝑗 < 𝑘 \leq 𝑛} | 𝐴_{𝑖} \cap 𝐴_{𝑗} \cap 𝐴_{𝑘} | - \dots + {(- 1)}^{𝑛 - 1} | 𝐴_{1} \cap 𝐴_{2} \cap \dots \cap 𝐴_{𝑛} | \end{aligned}

6.鸽笼原理

我们直接介绍广义鸽笼原理。若要将 $𝑁$ 个物品放入 $𝑘$ 个盒子，那么至少有一个盒子至少有 $⌈ \frac{𝑁}{𝑘} ⌉$ 个物品。将这个数称为最小容量。因此：

最小容量 = ⌈ \frac{物品数}{盒子数} ⌉

物体数最小值 = (最小容量 - 1) \times 盒子数 + 1

盒子数最大值 = ⌊ \frac{物体数 - 1}{最小容量 - 1} ⌋