发布日期: 2025-04-28

更新日期: 2025-04-29

文章字数: 4k

离散数学 Chap.2 集合, 函数, 数列, 级数

本系列离散数学博文基于Youtube易志偉老师的免费课程整理而来, 目的在于系统的梳理计算机专业课的基础知识, 并为将来的面试做好充分的准备.
除本系列外, 计算机考研相关还包括数据结构 / 操作系统 / 计算机组成原理 / 计算机网络的相关内容.

2.1 集合

2.1.1 定义

集合 , 这是个我们从初中倒腾到现在的玩意.

概念: 集合(Set)
一个 无序且内容不重复 的物体集.
集合内的元素属于集合. 集合包含其内的每一个元素.

通常被记作:

$$ a \in S / a \notin S $$

那这东西为什么在这门大学的课程里还要拉出来call back一下? ~~(没错, 我们上一章的东西又来了)~~
我们先再给出一些基本的概念.

概念: 集合的相等
两个集合 $ A, B $ , 当且仅当 $ \forall x (x \in A \leftrightarrow x \in B) $ 时, 我们称二者相等.
两个集合内的元素完全相同.

然后, 我们还有个定义来描述集合内元素的数目:

概念: 集合的基(Cardinality)
一个集合的基 , 即 集合内元素的数量 . 通常用 $ |A| $ 来表示.

之后有个数, 就有数量大小之分对吧, 还有可能这集合里面有 无限多 的元素.
根据元素个数 有限 / 无限 , 我们称之为 有限集(Finite Set) / 无限集(Infinite Set) .

注意: 集合套集合?
先看个集合: $ A = \lbrace \lbrace a, b, c \rbrace, \lbrace x \rbrace, x, y \rbrace $ , 那显然, $ \lbrace a, b, c \rbrace \in A $ 这种表述是完全成立的.
之所以举这个例子, 是为了告知读者, 集合中又包含一个集合是完全有可能的事情.

随后我们还要定义一个子集的概念.

概念: 子集(Subset)
两个集合 $ A, B $ , 当且仅当 $ \forall x (x \in B \to x \in A) $ , 则称 $ B $ 是 $ A $ 的子集.
应该还挺好理解的, 子集里面的元素一定也是集合里的元素嘛.
会记作 $ B \subseteq A $

但是这个概念其实有点太宽泛了, 因为我们会发现, 一个集合自己也是自己的子集, 这有点不太符合常识, 因此我们整了个叫 真子集 的玩意.

概念: 真子集(Proper Subset)
两个集合 $ A, B $ , 当且仅当 $ \forall x (x \in B \to x \in A) \land \exists x (x \notin B \land x \in A) $ , 则称 $ B $ 是 $ A $ 的真子集.
比之前那个定义严格, B不能包含A的所有元素.
会记作 $ B \subsetneq A $

2.2 集合中的运算符号

2.2.1 交集 / 并集

读者别发怵哈, 说是集合中的运算符, 但是其实很多符号跟第一章的逻辑是异曲同工的. 第一章看明白了, 其实第二章不会太难哈.

首先是俩我们很熟悉的玩意:

概念: 交集(Intersection)
两个集合 $ A, B $ , 构建集合 $ C $ , $ \forall x ((x \in A \land x \in B) \to x \in C) $ , 则我们称 $ C $ 是 $ A, B $ 的交集.
记作 $ C = A \cap B $

概念: 并集(Union)
两个集合 $ A, B $ , 构建集合 $ C $ , $ \forall x ((x \in A \lor x \in B) \to x \in C) $ , 则我们称 $ C $ 是 $ A, B $ 的并集.
记作 $ C = A \cup B $

这里有个挺重要的公式, 需要理解记忆一下:

$$ |A \cup B| = |A| + |B| - |A \cap B| $$

俩太没意思了, 我们进一步推演一下?

$$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $$

n个呢?

$$
\begin{align*}
|A_1 \cup A_2 \cup … \cup A_n | = & |A_1| + |A_2| + … + |A_n| & 这里是每个单个集合的数量 \\
& - |A_1 \cap A_2| - |A_1 \cap A_3| - … & 这里是两个的组合 \\
& + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + … & 这里是三个的组合 \\
& … \\
& + (-1)^{n+1} |A_1 \cap A_2 \cap … \cap A_n| & 这里是所有的加起来 \\
\end{align*}
$$

上面这种写法是比较冗余的, 主要目的在于让读者能够理解这个玩意在写什么. 有一种更简单的写法:

$$ \cup_{i = 1}^{n} A_i = \sum_{i = 1}^{n} |A_i| - \sum_{1 \leq i \neq j \leq n} |A_i \cap A_j| + \sum_{1 \leq i \neq j \neq k \leq n} |A_i \cap A_j \cap A_k| - … + (-1)^{n+1} | \cap_{i=1}^{n} A_i | $$

除了单纯的定义之外, 还有个专有名词需要明确一下, 叫互斥 .

概念: 互斥(Disjoint)
两个集合 $ A, B $ , 当 $ A \cap B = \emptyset $ 时, 称之为 $ A $ 与 $ B $ 互斥.

这个东西能进一步衍生出来一种关系, 叫分割 .

概念: 分割(Partition)
全集 $ U $ , 如果有这么一组集合 $ A_1, A_2, … , A_n $ , 它们满足 $ U = \cup_{i=1}^n $ 并且两两互斥, 则称 $ A_1, A_2, … , A_n $ 为 $ U $ 的一组分割 .
相当于你将一个整体拿刀切开来, 那不可能将一个元素同时分给两个部分对不.
这个概念在后续还挺有用的, 还希望读者能留个印象.

2.2.2 幂集

概念: 幂集(The Power Set)
一个集合 $ A $ , 由 $ A $ 的所有子集组成的集合被称为 $ A $ 的幂集.
通常记为 $ P(A) $ 或 $ 2^A $ .

例子: 幂集
$ A = \lbrace 1, 2, 3 \rbrace $
$ 2^A = \lbrace \emptyset, \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 1, 2, 3 \rbrace \rbrace $

读者想问了, 为啥写成这德行 $ 2^A $ ?
数一数上面的例子里面 A 的幂集有几个元素? 是不是正好是 $ 2^{|A|} $ ?

那问题又来了, 为啥是这个数?
易老师给了一种非常简单的理解法:

写幂集的过程就是 对集合内的元素进行挑选 的过程.
每一个 幂集的元素 都是一种挑法. 那总共几种挑法?
每个元素都有挑 / 不挑两种选择, 因此幂集中总共 $ 2^{|A|} $ 个元素.

2.2.3 笛卡尔积

概念: 笛卡尔积(Cartesian Products)
两个集合 $ A, B $ , 其二者的笛卡尔积记为 $ A \times B = \lbrace(a, b) | a \in A \land b \in B \rbrace $ .
是由两个集合中所有元素组成的有序对的集合.

笛卡尔积的元素个数也挺简单的:

$$ |A \times B| = |A| \times |B| $$

两边分别各取一遍就行.

2.2.4 差集

概念: 差集
两个集合 $ A, B $ , 二者的差集定义为 $ A-B = \lbrace x | x \in A \land x \notin B \rbrace $
很类似, 用A中的元素其中属于B的元素.

2.2.5 补集

概念: 补集
全集 $ U $ 和集合 $ A $ , 定义 $ A $ 的补集 $ \overline{A} = \lbrace x | x \in U \land x \notin A \rbrace $
就是不在A内的全部元素. 按照刚刚的差集来写的话也能写成 $ U-A $ .

2.3 常用相等集合

对的, 还是逃不开这玩意. 我们又得回来看看集合之间的运算有没有些规律.
读者不用太害怕哈, 这里很多公式跟逻辑那里几乎是一样的.

有个前提得说一下哈, 这里我们用 $ U $ 统一代指全集.

2.3.1 恒等律(Identity Laws)

$$ A \cap U = A $$

$$ A \cup \emptyset = A $$

2.3.2 支配律(Domination Laws)

$$ A \cup U = U $$

$$ A \cap \emptyset = \emptyset $$

2.3.3 幂等律(Idempotent Laws)

$$ A \cap A = A $$

$$ A \cup A = A $$

2.3.4 双重否定(Double Negation)

$$ \overline {\overline A} = A $$

2.3.5 结合律(Associative Laws)

俩式子:

$$ (A \cap B) \cap C = A \cap (B \cap C) $$

$$ (A \cup B) \cup C = A \cup (B \cup C) $$

2.3.6 交换律(Commutative Laws)

俩式子:

$$ A \cap B = B \cap A $$

$$ A \cup B = B \cup A $$

2.3.7 分配律(Distributive Laws)

$$ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) $$

$$ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) $$

2.3.8 德摩根律(De Morgan Laws)

德摩根律有两个式子:

$$ \overline{A \cup B} = \overline A \cap \overline B $$

$$ \overline{A \cap B} = \overline A \cup \overline B $$

2.3.9 吸收率(Absorption Laws)

$$ A \cap (A \cup B) = A $$

$$ A \cup (A \cap B) = A $$

2.3.10 永真律 / 矛盾律(Nogation Laws)

$$ A \cap \overline A = \emptyset $$

$$ A \cup \overline A = U $$

读者请详细对比 2.3 部分和第一章中的 1.2.1 部分.
可以发现其实就是把 $ \land $ 换成了 $ \cap $ , 把 $ \lor $ 换成了 $ \cup $ , 把命题换成了集合.
进一步说, 其实 $ \cap $ 类似于运算中的乘法, $ \cup $ 类似于运算中的加法, $ \emptyset $ 相当于0, $ U $ 相当于运算中的1.

现在问题来了, 式子, 我们有了, 证明, 怎么干?
既然说了这地方跟逻辑非常像, 我们自然需要给出一个像逻辑那边一样简单的证明方法.
是啥, 笔者个人比较喜欢将其称作 元素关系表 , 英文名叫 Membership Table .
这种表格中会假设一个元素, 并用T / F表示元素是否在某个集合内.

我们以证明集合的德摩根率为例.

$$ \overline{A \cup B} = \overline A \cap \overline B $$

$$
\begin{array}{|c|c|c|c|c|c|c|}
\hline
A & B & A \cup B & \overline{A \cup B} & \overline{A} & \overline{B} & \overline{A} \cap \overline{B} \\
\hline
T & T & T & F & F & F & F \\
T & F & T & F & F & T & F \\
F & T & T & F & T & F & F \\
F & F & F & T & T & T & T \\
\hline
\end{array}
$$

同样的, 观察上表, 会发现 $ \overline{A \cup B} $ 和 $ \overline A \cap \overline B $ 的表项是完全一样的. 那么就能证明上式成立.

显然, 这个方法与逻辑中 真值表 相同, 只能用来处理小的问题. 至于大问题怎么解决? 咱给这些公式就是为了解决更大的问题的.

2.4 函数

概念: 函数(Function)
函数, 是针对两个集合而言的.
假设有两个集合 $ A, B $ , 如果对于 $ A $ 中 每一个元素 , $ B $ 中都有一个元素与之相对应, 称之为有一个从 $ A $ 到 $ B $ 的函数.

读者请明确, 函数有两个重要的点:

A中的每个元素都能在B中找到一个元素与之对应.
A中的一个元素对应在B中的元素是唯一的.

接下来, 写一下函数有关的一些专有名词:

对于一个从 $ A $ 到 $ B $ 的函数. 我们通常记作: $ f: A \to B $ .
$ A $ 被称作该函数的 定义域(domain) , $ B $ 被称作该函数的 对应域 / 值域(codomain) .
相对应的, 我们设 $ a \in A, b \in B $ , 如果 $ b $ 是 $ a $ 的对应值, 则记作: $ f(a) = b $ .
这种情况下, $ b $ 是 $ a $ 的值 (也叫像 / image ).
$ a $ 是 $ b $ 的原像 ( preimage ).

注意: 像与原像的关系
按照定义, 我们需要明确, 一个像可以有多个原像, 但一个原像只能对应一个像.

接下来给一个比较常见的函数, 叫 高斯函数

$$ f(x) = \lfloor x \rfloor $$

$$ f(x) = \lceil x \rceil $$

这二者分别表示整数 向下 / 向上 取整. 有 $ \lfloor x \rfloor \leq x \leq \lceil x \rceil $ .

例子: 高斯函数相关的证明
证明: $ \lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x + \frac{1}{2} \rfloor $
提示: 用第一章提到过的枚举法.
将x设置为整数部分 $ n $ + 小数部分 $ r $ , 针对小数部分进行讨论即可.

好的, 还有几种比较特殊的函数, 我们这里介绍一下:

概念: 单射函数(Injection / One to one)
对于一个函数, 如果有 $ (f(a) = f(b)) \to (a = b) $ , 则称之为单射函数.
相当于每个函数的 像对应的原像也是唯一的 .

概念: 满射函数(Surjection / Onto)
对于一个函数, 如果满足 $ \forall b \in B ( \exists a \in A, f(a) = b) $ ,则称之为满射函数.
相当于对应域中的 每个像都能找到至少一个原像.

概念: 双射函数(Bijection / One to one & Onto)
对于一个函数, 如果它又是单射, 又是满射, 则它是双射函数
相当于是 严格一对一的函数 .

随后, 是反函数相关的内容:

概念: 反函数(Inverse Function)
对于一个 双射函数 $ f:A \to B $ , 可以定义它的反函数 $ f^{-1}: B \to A $ , 当 $ f(a) = b $ ,则有 $ f^{-1}(b) = a $ .
反函数存在的前提是这个函数一定得是一个 双射函数 . 读者可以拿高中阶段的一些函数理解一下, 必须是严格一对一的函数才存在反函数.

2.5 数列 / 求和

这里又把一个我们之前看过的玩意拉出来了, 咋回事呢?
因为数列这东西其实可以看成一种比较特殊的函数.

概念: 数列(Sequences) / 级数(Summation)
数列可以看作一种特殊的函数, 它的定义域一定是 整数的子集 .
级数, 则代表着一个数列某些函数值的总加和. 通常, 如果从第 j 项加至第 k 项, 使用 $ \sum_{i=j}^k a_i $ 进行表示.

随后还是把两个最常见的数列写一下:

概念: 等差数列(Arithmetic Progression)
数列项与项之间的差值始终相同. 通常管数列的第一个值 $ a_0 $ 叫首项 , 管数列项与项的差值 $ d $ 叫公差 .

等差数列的级数:

$$
\begin{align*}
S_n & = \sum_{i = 0}^n (a + id) \\
& = (a + (a + nd)) * (n+1) * (\frac{1}{2}) \\
\end{align*}
$$

概念: 等比数列(Geometric Progression)
数列项与项之间的倍数差距始终相同. 通常管数列的第一个值 $ a_0 $ 叫首项 , 管数列项与项的倍数差 $ r $ 叫公比 .

等比数列的级数:

$$
\begin{align*}
S_n & = \sum_{i = 0}^n ar^i \\
& = \frac{a(r^{n+1}-1)}{r-1} \\
\end{align*}
$$

这之后是在微积分里面提过的几个概念, 我们假设c是常数, $ f_n, g_n $ 是两个数列的通项公式:

常数可提:

$$ \sum_{n} cf_n = c \sum_{n} f_n $$

加减可拆:

$$ \sum_{n} (f_n + g_n) = \sum_{n} f_n + \sum_{n} g_n $$

下标可换:

$$ \sum_{n = i}^j f_n = \sum_{n = i+k}^{j+k} f_{n-k} $$

计算可分:

$$ \sum_{n = i}^k f_n = \sum_{n = i}^j f_n + \sum_{n = j+1}^k f_n \space (if \space i \leq j < k) $$

算序可变:

$$ \sum_{n=0}^{2k} f_n = \sum_{n=0}^k f_{2n} + f_{2n+1} $$

最后一些常用的级数公式:

$$
\begin{align*}
\sum_{k=1}^n k^2 & = \frac{n(n+1)(2n+1)}{6} & \\
\sum_{k=1}^n k^3 & = \frac{n^2 (n+1)^2}{4} & \\
\sum_{k=0}^{\infty} x^k & = \frac{1}{x-1} & |x|<1 \\
\sum_{k=1}^{\infty} kx^{k-1} & = \frac{1}{(x-1)^2} & |x|<1 \\
\end{align*}
$$