离散数学

本章，我们将学习所有离散结构的基础，集合。集合被用来组织对象。这些对象通常有相同的属性。我们先给出一些感性的定义。

定义：一个集合是一个无序容器，叫做元素或对象的集合。一个集合被说成包含它的元素。我们写法 a ∈ A a \in A a∈A 指的是元素 a a a 在集合 A A A 中。我们用记号 a ∉ A a \notin A a∈/​A 称作元素 a a a 不在集合 A A A 中。

我们通常约定大写字母表示集合，小写字母表示元素。

表示集合有很多方法，经常使用的是 列举法 ，即将集合中的元素用花括号列出来，例如 A = { a , b , c , d } A=\{ a,b,c,d \} A={a,b,c,d} 即集合 A A A 中含有四个元素，分别是 a , b , c , d a,b,c,d a,b,c,d 。

有时候元素的数量可能很多，但是元素有一定的模式，此时我们就能用 … \ldots … 来表示省略，例如 A = { 1 , 2 , … , 99 , 100 } A = \{1,2,\ldots,99,100\} A={1,2,…,99,100} 来表示 1 1 1 到 100 100 100 的整数。

另外一种描述集合的方法称为 集合构造器 记号。我们描述集合元素的特征而不是列举元素。例如 O = { x ∈ Z + ∣ x ≤ 10 } O = \{x \in Z^+|x \leq 10\} O={x∈Z+∣x≤10} 表示集合 O O O 中包含小于等于 10 10 10 的正整数。

下面的这些集合是数学中经常使用的集合。通常用黑体或者空心花体表示。

回想一下我们区间记号的写法：

[ a , b ] = { x ∣ a ≤ x ≤ b } [ a , b ) = { x ∣ a ≤ x < b } ( a , b ] = { x ∣ a < x ≤ b } ( a , b ) = { x ∣ a < x < b } \begin{aligned} \left [a,b \right ] & = \{x|a \leq x \leq b\} \\ [a,b) & = \{x|a \leq x \lt b\} \\ (a,b] & = \{x|a \lt x \leq b\} \\ (a,b) & = \{x|a \lt x \lt b\} \end{aligned} [a,b][a,b)(a,b](a,b)​={x∣a≤x≤b}={x∣a≤xx∣a∅} 的区别，我们发现，前者指的是空集，没有任何元素，后者是一个单集，有一个元素为空集。这就类比于计算机中的文件目录结构。

一些集合能够形象化的表示为韦恩图。在韦恩图中 全集 是指包含一切元素的集合（取决于你的研究对象），记作 U U U ，在韦恩图中用一个矩形表示。在矩形中，其他的几何元素例如圆表示一个集合，用点来表示一个具体的元素，用重叠关系来表示集合关系。

定义：集合 A A A 是集合 B B B 的子集如果集合 A A A 中所有的元素也在 B B B 中。我们使用记号 A ⊆ B A \subseteq B A⊆B 表示。

我们发现 A ⊆ B A \subseteq B A⊆B 等价于：

∀ x ( x ∈ A → x ∈ B ) \forall x (x \in A \to x \in B) ∀x(x∈A→x∈B)

韦恩图表示为 B B B 包含 A A A 。

定理：对于任何集合 S S S ， ∅ ⊆ S \emptyset \subseteq S ∅⊆S 并且 S ⊆ S S \subseteq S S⊆S 。

这说明一个非空集合必有两个子集，一个是空子集，一个是他本身，这两个集合称为平凡子集。

当我们想强调 A A A 是 B B B 的一个子集但是 A ≠ B A \neq B A​=B ，此时我们用记号 A ⊂ B A \subset B A⊂B 说明 A A A 是 B B B 的一个 真子集 。等价于下面的命题：

∀ x ( x ∈ A → x ∈ B ) ∧ ∃ x ( x ∈ B ∧ x ∉ A ) \forall x (x \in A \to x \in B) \wedge \exists x (x \in B \wedge x \notin A) ∀x(x∈A→x∈B)∧∃x(x∈B∧x∈/​A)

如果我们想证明 A = B A = B A=B 我们可以证明 A ⊆ B A \subseteq B A⊆B 并且 B ⊆ A B \subseteq A B⊆A 。

定义：如果集合 S S S 有 n n n 个不同的元素，这里 n n n 是一个非负整数。我们说集合 S S S 是有限集合并且 n n n 是集合的势。集合的势被记作 ∣ S ∣ |S| ∣S∣ 。

另外，集合分为有限集合和无限集合。

定义：如果一个集合不是有限集合，那么他是无限集合。

许多集合问题都和它的子集有关，我们定义幂集这个概念。

定义：给定一个集合 S S S ， S S S 的幂集是他所有子集的集合，记作 P ( x ) \mathcal{P}(x) P(x) 。

如果一个集合 S S S 有 n n n 个元素，那么他的子集有 2 n 2^n 2n 个，它幂集的势为 2 n 2^n 2n 。

集合有的时候并不是我们想要的结构，因为他是无序的。有时候我们需要一个有序的结构，称为 n n n 元组 。

定义：有序 n n n 元组 ( a 1 , a 2 , … , a n ) (a_1,a_2,\ldots,a_n) (a1​,a2​,…,an​) 是一个有序集合， a 1 a_1 a1​ 作为第一个元素，以此类推。

我们说两个 n n n 元组相等，当且仅当对应位置上的元素均相同。

特别的， 2 2 2 元组被称为 有序对 。

定义：让 A A A 和 B B B 是集合，两个集合的笛卡尔积 A × B A \times B A×B 是一个所有元素都是有序对的集合：

A × B = { ( a , b ) ∣ a ∈ A ∧ b ∈ B } A \times B = \{(a,b)|a \in A \wedge b \in B\} A×B={(a,b)∣a∈A∧b∈B}

我们将定义推广至 n n n 个集合的笛卡尔积。

定义：多个集合的笛卡尔积 A 1 × A 2 × … × A n A_1 \times A_2 \times \ldots \times A_n A1​×A2​×…×An​ 是一个所有元素都是有序对的集合：

A 1 × A 2 × … × A n = { ( a 1 , a 2 , … , a n ) ∣ a 1 ∈ A 1 ∧ a 2 ∈ A 2 ∧ … ∧ a n ∈ A n } A_1 \times A_2 \times \ldots \times A_n = \{(a_1,a_2,\ldots,a_n)|a_1 \in A_1 \wedge a_2 \in A_2 \wedge \ldots \wedge a_n \in A_n\} A1​×A2​×…×An​={(a1​,a2​,…,an​)∣a1​∈A1​∧a2​∈A2​∧…∧an​∈An​}

我们使用记号 A 2 A^2 A2 表示运算 A × A A \times A A×A ，同理 A n A^n An 即 n n n 次 A A A 的笛卡尔积。

一个 A × B A \times B A×B 的子集 R R R 被称为是从 A A A 到 B B B 的关系 。

有了集合，我们就可以引入集合限定域，例如 ∀ x ∈ S ( P ( x ) ) \forall x \in S (P(x)) ∀x∈S(P(x)) 就是 ∀ x ( x ∈ S → P ( x ) ) \forall x (x \in S \to P(x)) ∀x(x∈S→P(x)) 的简写。

对于特称量词也同理。

我们将集合和量词的关系连接起来。定义谓词 P ( x ) P(x) P(x) 的 真值集合 { x ∈ D ∣ P ( x ) } \{x \in D | P(x)\} {x∈D∣P(x)} 指的是所有在全域 D D D 上使得 P ( x ) P(x) P(x) 为真的所有元素构成的集合。

对于两或多个集合，可以根据他们拥有元素的特征进行集合的运算。

定义：集合 A A A 和 B B B 的并集，记作 A ∪ B A \cup B A∪B ，是那些在 A A A 在 B B B 或者在两者中的所有元素构成的集合。

集合的并集等价于：

A ∪ B = { x ∣ x ∈ A ∨ x ∈ B } A \cup B = \{x | x \in A \vee x \in B\} A∪B={x∣x∈A∨x∈B}

用韦恩图表示为两者所有的面积。

定义：集合 A A A 和 B B B 的交集，记作 A ∩ B A \cap B A∩B ，是那些既在 A A A 又在 B B B 中的所有元素构成的集合。

集合的并集等价于：

A ∩ B = { x ∣ x ∈ A ∧ x ∈ B } A \cap B = \{x | x \in A \wedge x \in B\} A∩B={x∣x∈A∧x∈B}

用韦恩图表示为两者重叠部分的面积。

定义：两个集合是不交的，当且仅当两个集合的交集为空集。

我们有时对两个集合并集的集合的势的大小感兴趣，注意 ∣ A ∣ + ∣ B ∣ |A| + |B| ∣A∣+∣B∣ 将重叠部分的面积计算了两次，所有我们还有减去一次重叠面积，也就是：

∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |A \cup B| = |A| + |B| - |A \cap B| ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

上面的计算方法被称为 容斥原理 。

定义：两个集合的差集 A − B A - B A−B 是那些在 A A A 中 但不在 B B B 中所有元素构成的集合。也叫 A A A 的补相对于 B B B。

A − B = { x ∣ x i n A ∧ x ∉ B } A - B = \{x | x in A \wedge x \notin B\} A−B={x∣xinA∧x∈/​B}

用韦恩图表示为用 A A A 的面积减去 B B B 的面积。

一旦全集 U U U 确定，那么我们即可以定义集合 S S S 的补集。

定义：集合 A A A 的补集，记作 A ˉ \bar{A} Aˉ 是 U − A U - A U−A 。

也就是说：

A ˉ = { x ∈ U ∣ x ∉ A } \bar{A} = \{x \in U | x \notin A\} Aˉ={x∈U∣x∈/​A}

关于补集有个重要的恒等式：

A − B = A ∩ B ˉ A - B = A \cap \bar{B} A−B=A∩Bˉ

下面表展示了大部分的集合恒等式。

一些恒等式除了使用命题证明外，还可以使用 关系表 证明，关系表是类似于真值表的一个表，用 0 0 0 表示元素不在集合中，用 1 1 1 表示在集合中。

定义：一些集合的并集定义为元素至少在一个集合中。

也就是说：

A 1 ∪ A 2 ∪ … ∪ A n = ⋃ i = 1 n A i A_1 \cup A_2 \cup \ldots \cup A_n = \bigcup_{i=1}^n A_i A1​∪A2​∪…∪An​=i=1⋃n​Ai​

定义：一些集合的交集定义为元素在所有集合中。

也就是说：

A 1 ∩ A 2 ∩ … ∩ A n = ⋂ i = 1 n A i A_1 \cap A_2 \cap \ldots \cap A_n = \bigcap_{i=1}^n A_i A1​∩A2​∩…∩An​=i=1⋂n​Ai​

有很多方式可以在计算机中表示集合。假设全集是有限的，我们可以用一串二进制数来表示一个集合，例如第一位表示元素 a 1 a_1 a1​ 在不在集合中。

此时集合的交并补，正好对应二进制运算的 AND 和 OR 和 NOT 。

定义：让 A A A 和 B B B 是两个非空子集。一个函数 f f f 是给一个确定的 B B B 中元素给每一个 A A A 中的元素。我们写作 f ( a ) = b f(a) = b f(a)=b 这说明我们将 b b b 对应给 a a a 元素。这样的函数写作 f : A → B f: A \to B f:A→B 。

注意，函数有时也叫 映射 或者是 变换 。

描述函数的方式有很多种，一般数学上描述函数给出函数的公式，例如 f ( x ) = x + 1 f(x) = x+1 f(x)=x+1 ，函数也可看做是从 A A A 到 B B B 的关系的一种子集。如果存在 f ( a ) = b f(a) = b f(a)=b 那么一定存在 ( a , b ) (a,b) (a,b) 。

定义：如果函数 f : A → B f:A \to B f:A→B 那么我们称 A A A 是函数的域， B B B 是函数的陪域。如果 f ( a ) = b f(a) = b f(a)=b 我们称 b b b 是 a a a 的像，而 b b b 是原像。函数 f f f 的像或是值域指的是所有 A A A 中元素的像的集合。同时，我们也说是 f f f 是 A A A 到 B B B 的映射。

注意，两个函数相等当且仅当两个函数的域，陪域以及映射关系相同。当我们改变任意一个要素，我们得到是两个不同的函数。

一个函数称为 实值的 如果它的陪域是实数的集合，如果是 整值的 如果它的陪域是整数的集合，两个实值或是整值函数可以相加或者相乘。

定义：让 f 1 f_1 f1​ 和 f 2 f_2 f2​ 是两个 A → R A \to R A→R 的函数。此时 f 1 + f 2 f_1 + f_2 f1​+f2​ 和 f 1 f 2 f_1f_2 f1​f2​ 仍是 A → R A \to R A→R 的函数，分别为 ( f 1 + f 2 ) ( x ) = f 1 ( x ) + f 2 ( x ) (f_1 + f_2)(x) = f_1(x) + f_2(x) (f1​+f2​)(x)=f1​(x)+f2​(x) 和 ( f 1 f 2 ) ( x ) = f 1 ( x ) f 2 ( x ) (f_1f_2)(x) = f_1(x) f_2(x) (f1​f2​)(x)=f1​(x)f2​(x) 。

如果函数 f : A → B f: A \to B f:A→B 那么 A A A 子集的像也就能定义。

定义：如果 f f f 是从 A A A 到 B B B 的函数，让 S S S 是集合 A A A 的子集。子集 S S S 在 f f f 下的像是一个 B B B 的子集，包含每一 S S S 中元素的像，记作 f ( S ) f(S) f(S) ，所以：

f ( S ) = { t ∣ ∃ s ∈ S ( t = f ( s ) ) } f(S) = \{t | \exists s \in S (t = f(s))\} f(S)={t∣∃s∈S(t=f(s))} 。

有时简记为 { f ( s ) ∣ s ∈ S } \{f(s) | s \in S\} {f(s)∣s∈S} 。

注意，写法 f ( S ) f(S) f(S) 是具有歧义的，可能是集合的像，也可能是集合的映射，出现歧义时要具体说明。

有时我们不会给两个不同域元素分配同样的值，这叫做 一对一函数 。

定义：如果函数是一对一函数或者是单射函数，当且仅当对于所有的 f ( a ) = f ( b ) f(a) = f(b) f(a)=f(b) 都有 a = b a = b a=b 。

我们给出单射函数的一些条件。

定义：一个域和陪域都是实数集合的函数 f f f 是单调递增的，当且仅当对于所有 x < y x \lt y x0,1,2,3,…} 或者是 { 1 , 2 , 3 , … } \{1,2,3,\ldots\} {1,2,3,…} ）的函数，我们记作 a n a_n an​ 是 n n n 的像。我们将一系列的 a n a_n an​ 叫做是序列。

我们用 { a n } \{a_n\} {an​} 这个序列来记作一个序列。

有限序列有时也称为是 串 ，串的长度是有限序列的长度，空串记为 λ \lambda λ 。

定义：用 a n a_n an​ 的前项（ { a 1 , a 2 , … , a n − 1 } \{a_1,a_2,\ldots,a_{n-1}\} {a1​,a2​,…,an−1​} ）描述 a n a_n an​ 的方式称为递归描述。一个序列称为解，如果这个序列满足这个递归描述。

初始条件 指的是能开始递归的极小前几项，也就是说，确定了初始条件，那么就唯一的确定了其一个解。

如果我们找到了一个具有初始条件的迭代公式，我们称这个公式是其递归描述的一个 封闭公式 。

进一步展开将在具体数学系列笔记中说明，此处不在赘述。

如果想查询一个序列，可以访问 OEIS (On-Line Encyclopedia of Integer Sequences) 数据库。

接下来，我们讨论序列的和式，我们引入 和式记号 ，假设我们有序列：

a m , a m + 1 , … , a n a_m,a_{m+1},\ldots,a_n am​,am+1​,…,an​

将这些序列元素相加，我们记为：

∑ j = m n a j = a m + a m + 1 + … + a n \sum_{j=m}^n a_j = a_m + a_{m+1} + \ldots + a_n j=m∑n​aj​=am​+am+1​+…+an​

这里， j j j 称为 和式索引 通常使用字母 i , j , k i,j,k i,j,k 来表示。 m m m 称为和式的 下限 n n n 称为和式的 上限 。

定理：如果 a a a 和 r r r 都是实数且 r r r 不等于 0 0 0 ，那么：

∑ j = 0 n a r j = a r n + 1 − a r − 1 \sum_{j=0}^n ar^j = \frac{ar^{n+1} - a}{r - 1} ∑j=0n​arj=r−1arn+1−a​ 如果 r ≠ 1 r \neq 1 r​=1

∑ j = 0 n a r j = ( n + 1 ) a \sum_{j=0}^n ar^j = (n+1)a ∑j=0n​arj=(n+1)a 如果 r = 1 r = 1 r=1

和式也是可以嵌套的，例如：

∑ i = 1 4 ∑ j = 1 3 i j \sum_{i=1}^4 \sum_{j = 1}^3 ij i=1∑4​j=1∑3​ij

处理嵌套和式我们从内部到外部处理，遇见外部变量当做为常量。

对于集合和式：

∑ s ∈ S f ( s ) \sum_{s \in S} f(s) s∈S∑​f(s)

的意思是对所有 f ( s ) f(s) f(s) 求和，其中 s s s 是集合 S S S 中的所有元素。

无限和式也称为 级数 ，处理级数可能需要一些微积分的知识。

进一步展开将在具体数学系列笔记中说明，此处不在赘述。

下面给出常用的和式表：

易知，在枚举的 r i r_i ri​ 中没有一个是和 r r r 相同的，也就是说实数是无法枚举出来的，所以实数集不是可数集。

现在我们讨论一下关于可数集的一些定理。

定理：如果 A A A 和 B B B 是可数集，那么 A ∪ B A \cup B A∪B 也同样是可数集。

我们可以通过 a 1 , b 1 , a 2 , b 2 , … a_1,b_1,a_2,b_2,\ldots a1​,b1​,a2​,b2​,… 进行交替枚举，因此可数集的并集也是可数集。

定理：（Cantor-Bernstein-Schroeder Theorem）是集合论基本定理。如果 ∣ A ∣ ≤ ∣ B ∣ |A| \leq |B| ∣A∣≤∣B∣ 并且 ∣ B ∣ ≤ ∣ A ∣ |B| \leq |A| ∣B∣≤∣A∣ 那么 ∣ A ∣ = ∣ B ∣ |A| = |B| ∣A∣=∣B∣ 。换句话说，如果同时存在从 A A A 到 B B B 和从 B B B 到 A A A 的单射函数，那么必定存在两个集合直接的双射函数。

尽管这个定理阐述的十分简单，但是证明起来却十分困难，读者可查阅相关资料。

现在我们讨论一下在计算机中的应用，那即是存在不可计算函数，指在任何计算机中都不能被计算的函数。

定义：我们说一个函数是 可计算的 ，当且仅当存在计算机和编程语言能够找到他的值，否则是 不可计算的 。

很显然，一定存在不可计算的函数，举例来说，一个计算 [ 0 , 1 ] [0,1] [0,1]内所有实数的和是一个不可计算函数。

我们用一个更高级的理论结束本章。能够证明， Z + \mathbb{Z}^+ Z+ 的幂集和 R \mathbb{R} R 等势，也就是说 ∣ P ( Z + ) ∣ = ∣ R ∣ = c |\mathcal{P}(\mathbb{Z}^+)| = |\mathbb{R}| = \mathfrak{c} ∣P(Z+)∣=∣R∣=c 其中 c \mathfrak{c} c 是实数集的势。

另外一个著名的结论，说明集合的势小于他幂集的势，因此 ∣ Z + ∣ < ∣ P ( Z + ) ∣ |\mathbb{Z}^+| \lt |\mathcal{P}(\mathbb{Z}^+)| ∣Z+∣10​b1​=1∨b2​=1otherwise​

定义：两个矩阵的并记作 A ∨ B \textbf{A} \vee \textbf{B} A∨B 元素为对应元素进行 ∨ \vee ∨ 运算，两个矩阵的交写作 A ∧ B \textbf{A} \wedge \textbf{B} A∧B 元素为对应元素进行 ∧ \wedge ∧ 运算。

现在我们定义两个矩阵的 布尔积 。

定义：让 A \textbf{A} A 是一个 m × k m \times k m×k 矩阵，让 $ B \textbf{B} B 是一个 k × n k \times n k×n 矩阵，两个矩阵布尔积的结果 C = A ⊙ B \textbf{C} = \textbf{A} \odot \textbf{B} C=A⊙B 是一个 m × n m \times n m×n 矩阵，记作 c i j = ( a i 1 ∧ b 1 j ) ∨ ( a i 2 ∧ b 2 j ) ∨ … ∨ ( a i k ∧ b k j ) c_{ij} = (a_{i1} \wedge b_{1j}) \vee (a_{i2} \wedge b_{2j}) \vee \ldots \vee (a_{ik} \wedge b_{kj}) cij​=(ai1​∧b1j​)∨(ai2​∧b2j​)∨…∨(aik​∧bkj​) 。

零一矩阵的布尔积就是矩阵相乘的离散模拟。用交代替称号，用并代替加号。

同样，我们定义幂运算。

定义： A [ n ] \textbf{A}^{[n]} A[n] 表示矩阵和自身做布尔积 n n n 次。特别的 A 0 = I n \textbf{A}^0 = \textbf{I}_n A0=In​ 。