预备知识

集合 (Sets)

基本定义与性质

集合 (Set)：一个无序的元素集合 (An unordered collection of elements) 。

空集 (Empty set)：记作 Ø 。

子集 (Subset)：表示一个集合是否被另一个集合所包含。其严格定义为：S⊆T⇔(∀x∈S⇒x∈T)。任何集合都是其自身的子集 。

集合相等 (Equal Sets)：两个集合相等当且仅当它们包含完全相同的元素。这等价于两个集合互为子集：S=T⇔(S⊆T)∧(T⊆S)。例如，集合 {1,2,3} 和 {3,2,1} 是相等的，因为元素的顺序无关紧要 。 ### 集合运算 (Set Operations)

并集 (Union)：A∪B={x:x∈A or x∈B} 。

交集 (Intersection) ：A∩B={x:x∈A and x∈B} 。如果两个集合的交集为空，则称它们不相交 (disjoint) 。

补集 (Complement)：，其中 U 是全集 (Universal Set)。

差集 (Difference)：A-B={x:x∈A and x∉B} 。例如 B-A 。

对称差 (Symmetric Difference) : A∆B={x:x∈A or x∈B but not both} , 表示两个集合中只属于其中一个集合但不同时属于两个集合的元素所组成的集合, 是异或运算 (XOR) 的结果。

集合恒等式

这些恒等式是集合运算的基本定律 ：

幂等律 (Idempotent Law) ：A∩A=A, A∪A=A 。

交换律 (Commutative Law) ：A∪B=B∪A, A∩B=B∩A 。

结合律 (Associative Law) ：A∪(B∪C)=(A∪B)∪C, A∩(B∩C)=(A∩B)∩C 。

分配律 (Distributive Law) ：A∪(B∩C)=(A∪B)∩(A∪C) , A∩(B∪C)=(A∩B)∪(A∩C) 。

吸收律 (Absorption Law) ：A∪(A∩B)=A, A∩(A∪B)=A 。

德摩根定律 (De Morgan’s Law) ：A−(B∪C)=(A−B)∩(A−C), A−(B∩C)=(A−B)∪(A−C) 。

幂集 (Power Set)

定义：一个集合 A 的幂集是 A 的所有子集的集合 (Set of all subsets of A)，记作 2^A。

符号表示：2^A = {T|T⊆A}。

示例：如果集合 S 是 {x, y, z} ，那么它的幂集是

\${{\emptyset,\{x\},\{y\},\{z\},\{x,y\},\{x,z\},\{y,z\},\{x,y,z\}}}\$

划分 (Partition)

定义：一个非空集合 A 的划分 (partition) 是 2^A 的一个子集 Π ，它需要满足以下三个条件：

Π 本身不为空集 (Π ≠ ∅)。

Π 中任意两个不同的成员（它们本身是集合）的交集为空集。

Π 中所有成员的并集等于 A (⋃Π = A)。

示例：集合 {1,2,3} 有五种划分 ：

• ({1}, {2}, {3})
• ({1,2}, {3})
• ({1,3}, {2})
• ({2,3}, {1})
• ({1,2,3})

关系与函数 (Relations and Functions)

关系 (Relations)

基本概念

有序对 (Ordered Pair)：一个包含两个元素的对 (a,b)，其中元素的顺序是重要的 。两个有序对相等当且仅当它们的对应元素分别相等：(a,b)=(c,d)⇔(a=c)∧(b=d) 。

笛卡尔积 (Cartesian Product)：两个集合 A 和 B 的笛卡尔积 A×B 是所有可能有序对的集合，定义为 A×B={(a,b)∣a∈A∧b∈B}。

二元关系 (Binary Relation)：一个从集合 A 到集合 B 的二元关系 R 是笛卡尔积 A×B 的一个子集 (R⊆A×B)。

关系的运算 (Operations of Relations)

逆 (Inverse)：如果 R 是一个从 A 到 B 的关系 (R⊆A×B)，那么它的逆关系 R⁻¹ 是一个从 B 到 A 的关系 (R⁻¹⊆B×A) 。

复合 (Composition)：给定从 A 到 B 的关系 R 和从 B 到 C 的关系 S，它们的复合关系 R∘S 是一个从 A 到 C 的关系。其定义为：R∘S={(a,c)∣∃b∈B,(a,b)∈R ∧ (b,c)∈S}。

定义域与值域 (Domain and Range):

定义域 (Domain)：一个关系的定义域是该关系中所有输入值的集合 。 值域 (Range)：一个关系的值域是该关系中所有输出值的集合。

函数 (Functions)

定义 (Definition): 函数是一种特殊的二元关系 。一个从 A 到 B 的函数 f:A→B 必须满足两个条件：它是一个关系，即f⊆A×B; 对于集合 A 中的每一个元素 a，在集合 B 中都存在唯一一个元素 b，使得 (a,b)∈f。通常，我们将 (a,b)∈f 记作 f(a)=b 。

函数类型 (Types of Functions)

• 单射 (One-to-one / Injective)：如果定义域中任意两个不同的元素，它们在值域中的像也不同，即 ∀a,b∈A∧a≠b⇒f(a)≠f(b) 。
• 满射 (Onto / Surjective)：如果值域中的每一个元素都至少是定义域中一个元素的像，即 ∀b∈B, ∃a∈A such that f(a)=b 。
• 双射 (Bijective / One-to-one correspondence)：一个函数如果既是单射又是满射，则称其为双射。

特殊类型的二元关系 (Special Types of Binary Relations)

关系的表示方法

有向图 (Directed Graph): 可以将集合 A 上的任意关系 R 表示为一个有向图。图中的节点 (node) 代表集合 A 中的每个元素。如果存在有序对 (a, b) ∈ R，则从节点 a 到节点 b 画一条箭头 (arrow)，也称为图的边。

矩阵 (Matrix): 二元关系也可以用逻辑矩阵来表示。矩阵的行和列分别对应关系中两个集合的元素。矩阵中的元素 m_i, j 定义如下： - 如果 (x_i, y_j) ∈ R，则 m_i, j = 1。 - 如果 (x_i, y_j) ∉ R，则 m_i, j = 0。

关系的基本性质

对于一个定义在集合 A 上的关系 R (即，R⊆A×A)，它可能具有以下性质：

自反性 (Reflexive)：对于 A 中的任意元素 a，都有 (a,a)∈R。 对称性 (Symmetric)：如果 (a,b)∈R，那么一定有 (b,a)∈R。 反对称性 (Antisymmetric)：如果 (a,b)∈R 且 (b,a)∈R，那么一定有 a=b。 传递性 (Transitive)：如果 (a,b)∈R 且 (b,c)∈R，那么一定有 (a,c)**∈R。

同时还需要掌握关系的性质对应到矩阵和有向图的表示.

等价关系 (Equivalence Relation)

定义：一个关系如果同时满足自反性、对称性和传递性，则称其为等价关系。

等价类 (Equivalence Classes)：对于元素 a，其等价类 [a] 被定义为集合中所有与 a 等价的元素的集合(可以和a构成等价关系的元素的集合)，即 [a]={b∣(a,b)∈R}。在图表示中，一个等价类对应一个完全连接的”簇”。

例如，可以有 a ~ b ⟺ a ≡ b (mod 3)，根据这个关系，整数可以被划分为三个等价类： [0] = {…, -6, -3, 0, 3, 6, …}（模 3 余 0） [1] = {…, -5, -2, 1, 4, 7, …}（模 3 余 1） [2] = {…, -4, -1, 2, 5, 8, …}（模 3 余 2）

用图表示就是完全连接簇, 每个等价类就形成一个完全图（每两个节点之间都有边）

与划分的关系 (Partition)：一个重要的定理指出，任何集合 A 上的等价关系，其所有等价类的集合构成了对集合 A 的一个划分。

序关系 (Order Relations)

偏序 (Partial Order): 一个关系 ≤ 如果同时满足自反性、反对称性和传递性，则称其为偏序关系。

相关概念： - 最小元素 (Least element)：如果对集合中所有元素 b，都有 a≤b。 - 极小元素 (Minimal element)：如果不存在异于 a 的元素 b 使得 b≤a(可以存在不可比的元素) - 最大元素 (Greatest element)：如果对集合中所有元素 b，都有 b≤a。 - 极大元素 (Maximal element)：如果不存在异于 a 的元素 b 使得 a≤b。

全序 (Total Order): 如果一个偏序关系满足对于集合中任意两个元素 a 和 b，都有 a≤b 或 b≤a 成立（即任意两个元素都可比较），那么这个关系被称为全序或线性序 (linear ordering)。

有限集与无限集 (Finite and Infinite Sets)

集合的等势与基数

等势 (Equinumerous)：如果两个集合 A 和 B 之间存在一个双射函数 (bijective function)，则称它们是等势的 (equinumerous)，记作 A∼B 。等势关系是一种等价关系，满足自反性、对称性和传递性 。

基数 (Cardinality)：基数是衡量集合中元素“数量”的一个概念。如果两个集合等势，那么它们的基数相同 。集合 A 的基数通常表示为 ∣A∣ 。广义基数理论允许我们区分不同类型的无穷大。

有限集与无限集: 有限集 (Finite Set)指拥有有限数量成员的集合; 无限集 (Infinite Set)指不是有限集的集合。无限集又可以进一步分为可数无限和不可数无限。

可数无限集 (Countably Infinite Sets)

定义：如果一个集合与自然数集 N 等势，则称该集合是可数无限的 (countably infinite)。其基数记为 ℵ₀。

希尔伯特旅馆悖论 (Hilbert’s paradox)：这是一个著名的思想实验，用来说明可数无限集的反直觉性质。即使旅馆客满（有无限个房间且都住着人），它仍然可以容纳： - 有限个新客人 - 无限个新客人 - 无限辆巴士，每辆巴士载有无限个新客人

性质与示例： - 定理：可数无限个可数无限集的并集仍然是可数无限的。

三种方法证明了集合 N×N 是可数无限的： - 对角线法图示 - 构造一个双射函数 - 构造两个方向的单射函数来证明基数相等

不可数集与康托定理 (Uncountable Sets and Cantor’s Theorem)

不可数集 (Uncountable Set)：如果一个无限集的基数大于自然数集 N 的基数，则称其为不可数集。

定理：实数集 R 是不可数的，即 |R| > |N|。

有趣的是，开区间 (0,1) 与整个实数集 R 是等势的，可以通过反正切函数构造一个双射来证明。

连续统假设 (Continuum hypothesis)：该假设由康托提出，它断言不存在一个基数严格介于整数基数 (ℵ₀) 和实数基数 (ℵ₁) 之间。

康托定理 (Cantor’s Theorem)：这是一个基础性的定理，它指出对于任何集合 A，其基数严格小于其幂集 P(A) 的基数，即 card(A) < card(P(A))。

• 这意味着不存在”最大的无穷大”。
• 该定理的证明使用了对角线法，通过构造一个特殊的集合 B = {x∈A | x∉f(x)} 来证明任何从 A 到其幂集 P(A) 的函数 f 都不可能是满射的。
• 一个直接的推论是：自然数集的幂集 2ᴺ 是不可数的。

三种基本证明技巧 (Three Fundamental Proof Techniques)

数学归纳法 (The Principle of Mathematical Induction)

这是一种用于证明关于自然数的命题的标准方法。

原理：令 A 为一个自然数集合，如果满足以下两个条件： 1. 0∈A 2. 对于任意自然数 n，如果 {0,1,2,…,n}⊆A，那么 n+1∈A

则 A 包含所有自然数。

证明步骤通常包含三个部分：

1. 基础步骤 (Base Case)：证明命题 P(1)（或P(0)）成立
2. 归纳假设 (Inductive Hypothesis)：假设命题 P(k) 对于某个 k 成立
3. 归纳步骤 (Inductive Step)：证明 P(k+1) 也成立

鸽巢原理 (The Pigeonhole Principle)

该原理描述了一个简单但在证明中非常有用的数量关系。

定义有两种形式：

1. 函数形式：如果 A 和 B 是有限集且 |A|>|B|，那么不存在从 A 到 B 的单射函数
2. 物品形式：如果有 m 个物体要放入 n 个箱子，且 m>n，那么至少有一个箱子包含至少两个物体

示例：讲义中用该原理证明了”对于球体上的任意五个点，必定存在一个闭合的半球包含其中至少四个点”。

证明：讲义本身提供了一个使用数学归纳法来证明鸽巢原理的过程。

对角线法 (The Diagonalization Principle)

这是一种由康托首创的强大证明技巧，常用于证明无限集的不可数性。

核心思想： 1. 给定一个集合 A 上的二元关系 R，我们可以为每个元素 a∈A 定义一个”行集合” Ra={b|b∈A∧(a,b)∈R} 2. 通过考察对角线上的元素，我们可以构造一个新的”对角集合” D={a|a∈A∧(a,a)∉R} 3. 对角线法的关键在于，构造出的集合 D 与任何一个行集合 Ra 都不同

重要应用：

1. 证明康托定理：
   • 假设存在一个从集合 A 到其幂集 P(A) 的双射函数 f
   • 构造对角集合 B={x∈A|x∉f(x)}
   • 这个集合 B 属于 P(A)，但不可能等于任何一个 f(x)
   • 由此产生矛盾，证明了函数 f 不可能是满射
2. 证明实数集 R 的不可数性：
   • 假设实数集是可数的，将其所有成员列成无限序列 r₀,r₁,r₂,…
   • 通过对角线法构造新实数 d，使其小数点后第 n 位与 rn 的第 n 位不同
   • 构造出的数 d 必然不在序列中，从而产生矛盾
3. 证明 2ᴺ 的不可数性：
   • 假设 2ᴺ 是可数的，将其成员表示为列表 R₀,R₁,R₂,…
   • 构造对角集合 D={n∈N|n∉Rn}
   • 集合 D 是 N 的子集，但与列表中的任何 Rn 都不同，产生矛盾

闭包 (Closure)

闭包的基本思想

闭包的核心思想是：将一个集合进行扩展，使其在某种运算下具有”封闭”的性质，并且这种扩展是最小的。

示例：

自然数集 N 在减法运算下是不封闭的，因为两个自然数相减的结果不一定是自然数（例如，1-2=-1∉N）。

整数集 Z 在减法运算下是封闭的。Z 是包含了 N 且在减法运算下封闭的最小集合。

因此，我们称 Z 是 N 在减法运算下的闭包（closure）。

关系的闭包 (Closures of Relations)

这个概念同样可以应用于二元关系，即寻找一个最小的扩展关系，使其满足某些性质（如自反性、对称性、传递性）。

自反传递闭包 (Reflexive Transitive Closure)

表示符号：关系 R 的自反传递闭包通常记作 R*。

定义：R* 是一个包含所有有序对 (a,b) 的集合，其中在 R 的有向图表示中，存在一条从 a 到 b 的路径（path）。路径的长度可以为0（即 a 到 a 自身）。

性质： - R* 包含了原始关系 R（R⊆R） - R 本身是自反的和传递的 - R* 是包含了 R 并且满足自反性和传递性的最小关系

传递闭包 (Transitive Closure)

表示符号：关系 R 的传递闭包通常记作 R+。

定义：R+ 是包含了 R 并且是传递的最小关系。它与 R* 的区别在于，R+ 不要求必须是自反的（即路径长度必须大于0）。

形式化条件：一个关系是 R 的传递闭包 R+，必须满足： 1. R⊆R+ 2. R+ 是传递的 3. 对于任何其他包含了 R 并且是传递的关系 R’，都有 R+⊆R’

字母表与语言 (Alphabet and Language)

本节是连接前面纯数学概念与后续计算理论核心内容的桥梁 。它形式化地定义了计算机科学中用于信息编码的基本单位：符号、字符串和语言 。 ## 字母表与字符串 (Alphabet and Strings)

字母表 (Alphabet)

定义：字母表（记作 Σ）是一个任意的有限集合。

符号 (Symbol)：字母表中的元素被称为符号。

示例： - 二进制字母表：Σ = {0,1} - 英文字母表：Σ = {a,b,c}

字符串 (Strings) 及其运算

定义：字符串 (String) 是由字母表中的符号组成的有限序列。字符串也常被称为词 (Word)。

这里需要知道, 由一个非空字母表所能构成的字符串集合是无限的, 但是我们只把有限长度的字母组合叫做字符串, 也就是说, 一个无限长的 aaaa… 序列根据这个标准定义，不被认为是一个“字符串”

空字符串 (Empty string)：不含任何符号的特殊字符串，记作 e。

Σ* ：表示在字母表 Σ 上所有可能字符串的集合，包括空字符串 e。(也被称为字母表 Σ 的 克林闭包（Kleene Closure）) - 因此Σ*永远不为空集(至少包含e)

字符串运算：

• 连接 (Concatenation)：将两个字符串 x 和 y 首尾相连形成新字符串 xy。空字符串是连接运算的单位元，即对于任意字符串 w，we = ew = w。
• 幂 (Exponentiation)：字符串 w 的 i 次幂 w^i 表示 w 自身连接 i 次。w^0 = e。
• 逆序 (Reversal)：字符串 w 的逆序 w^R 是将 w 中的符号顺序颠倒。例如，如果 w = ua(a ∈ Σ), 则 w^R = au^R(递归定义)。

语言 (Language)

定义：一个语言 L 是在某个字母表 Σ 上所有字符串的集合 Σ^* 的一个任意子集（L ⊆ Σ^*）。或者换句话说, 语言 L 是由符合特定规则的所有字符串组成的集合。

示例： - 空语言 ⌀ - 只包含空字符串的语言 {e} - 字母表本身 Σ 以及 Σ^* 都是合法的语言

语言可以是： - 有限语言：通过明确列出所有字符串来定义 - 无限语言：通过描述字符串应满足的性质来定义，例如 L = {aⁿbⁿ ∣ n ≥ 1}

关于数量的重要定理

1. 对于任意非空有限字母表 Σ，其上所有字符串的集合 Σ^* 是可数无限的。
2. 任何一个语言 L（作为 Σ^* 的子集）都是可数的。
3. 在 Σ 上所有可能语言的总数是不可数无限的，其基数与实数集相同。

语言的运算

标准集合运算： - 并集：L₁ ∪ L₂ = {w ∣ w ∈ L₁ ∨ w ∈ L₂}, 代表或的关系 - 交集：L₁ ∩ L₂ = {w ∣ w ∈ L₁ ∧ w ∈ L₂}, 代表且的关系 - 差集：L₁ − L₂ = {w ∣ w ∈ L₁ ∧ w ∉ L₂} - 补集：

语言特有运算：

1. 连接（Concatenation）： L₁L₂ = {w₁w₂ ∣ w₁ ∈ L₁ ∧ w₂ ∈ L₂}

2. 幂（Exponentiation）：

3. 克林星号/闭包（Kleene Star）： 表示由 L 中字符串进行任意次数（包括零次）连接所能形成的所有字符串的集合。L^* 是 L 在连接运算下的闭包。

4. 正闭包（Positive Closure）： 与 L^* 的唯一区别是不包含零次连接，即不包含空字符串 e（除非 e 本身在 L 中）。