集合论

集合论是现代数学的基础语言。从数的定义到函数的概念，从几何学到拓扑学，几乎所有数学分支都可以建立在集合论的基础上。在计算机科学中，集合论直接应用于数据库的关系模型、编程语言中的集合数据结构、形式化验证等领域。

集合的基本概念

什么是集合？

集合（Set）是由一些确定的、互不相同的对象组成的整体。这些对象称为集合的元素（Element）或成员（Member）。

集合有三个关键特性：

确定性：对于任何一个对象，都能明确判断它是否属于该集合。例如，"小于 10 的正整数"是一个明确的集合，但"很大的数"不是一个集合，因为"很大"没有明确定义。

互异性：集合中的元素互不相同。例如，集合 $\{1, 2, 2, 3\}$ 实际上等于 $\{1, 2, 3\}$ 。

无序性：集合中的元素没有顺序。 $\{1, 2, 3\}$ 和 $\{3, 2, 1\}$ 是同一个集合。

元素与集合的关系

元素 $x$ 属于集合 $A$ ，记作 $x \in A$ ；元素 $x$ 不属于集合 $A$ ，记作 $x \notin A$ 。

# Python 中的集合操作
A = {1, 2, 3, 4, 5}
print(3 in A)   # True，相当于 3 ∈ A
print(6 in A)   # False，相当于 6 ∉ A

常用数集符号

在数学中，一些常用的数集有专门的符号：

符号	名称	含义
$\mathbb{N}$	自然数集	$\{0, 1, 2, 3, \ldots\}$ 或 $\{1, 2, 3, \ldots\}$
$\mathbb{Z}$	整数集	$\{\ldots, -2, -1, 0, 1, 2, \ldots\}$
$\mathbb{Q}$	有理数集	所有可以表示为分数的数
$\mathbb{R}$	实数集	所有实数
$\mathbb{C}$	复数集	所有复数

注意：自然数集是否包含 0，在不同教材中可能有不同约定。本教程采用 $\mathbb{N} = \{0, 1, 2, \ldots\}$ 的定义。

空集

不含任何元素的集合称为空集（Empty Set），记作 $\emptyset$ 或 $\{\}$ 。

空集有一个重要性质：空集是任何集合的子集。这可以通过逻辑推理证明：要证明 $\emptyset \subseteq A$ ，需要证明"对于所有 $x$ ，如果 $x \in \emptyset$ ，则 $x \in A$ "。由于不存在 $x \in \emptyset$ ，这个命题空真（vacuously true）。

集合的表示方法

枚举法

直接列出集合的所有元素，用花括号括起来。

$A = \{1, 2, 3, 4, 5\}$

$B = \{\text{red}, \text{green}, \text{blue}\}$

当元素很多或有无限个元素时，可以使用省略号：

$\mathbb{N} = \{0, 1, 2, 3, \ldots\}$

$C = \{2, 4, 6, \ldots, 100\}$

描述法（谓词法）

通过描述元素的特征性质来定义集合。

$D = \{x \mid x \text{ 是小于 10 的正整数}\}$

$E = \{x \in \mathbb{R} \mid x^2 < 4\}$

竖线左边是变量，右边是元素满足的条件。第二个例子中， $x \in \mathbb{R}$ 指定了论域。

描述法在编程中对应列表推导式或过滤操作：

# 描述法的编程对应
D = [x for x in range(1, 10)]  # {x | x 是小于 10 的正整数}
E = [x for x in range(-10, 11) if x**2 < 4]  # {x ∈ Z | x² < 4}

区间表示法

对于实数集的子集，可以使用区间表示法：

记号	含义
$[a, b]$	$\{x \in \mathbb{R} \mid a \leq x \leq b\}$ （闭区间）
$(a, b)$	$\{x \in \mathbb{R} \mid a < x < b\}$ （开区间）
$[a, b)$	$\{x \in \mathbb{R} \mid a \leq x < b\}$ （半开半闭）
$(a, b]$	$\{x \in \mathbb{R} \mid a < x \leq b\}$ （半开半闭）
$(-\infty, a]$	$\{x \in \mathbb{R} \mid x \leq a\}$
$(a, +\infty)$	$\{x \in \mathbb{R} \mid x > a\}$

集合之间的关系

子集

如果集合 $A$ 的每一个元素都是集合 $B$ 的元素，则称 $A$ 是 $B$ 的子集（Subset），记作 $A \subseteq B$ 。

用逻辑符号表示： $A \subseteq B \Leftrightarrow \forall x (x \in A \to x \in B)$

# 判断子集关系
A = {1, 2}
B = {1, 2, 3, 4}
print(A.issubset(B))  # True，A ⊆ B
print(A <= B)         # True，另一种写法

真子集

如果 $A \subseteq B$ 且 $A \neq B$ ，则称 $A$ 是 $B$ 的真子集（Proper Subset），记作 $A \subset B$ 或 $A \subsetneq B$ 。

$\{1, 2\} \subset \{1, 2, 3\}$

$\{1, 2, 3\} \subseteq \{1, 2, 3\} \quad \text{但不是真子集}$

集合相等

两个集合相等，当且仅当它们互为子集：

$A = B \Leftrightarrow A \subseteq B \land B \subseteq A$

这个定义是证明两个集合相等的基本方法：证明 $A \subseteq B$ 和 $B \subseteq A$ 。

超集

$B$ 是 $A$ 的超集（Superset），记作 $B \supseteq A$ ，等价于 $A \subseteq B$ 。

集合的运算

并集

集合 $A$ 和 $B$ 的并集（Union）包含属于 $A$ 或属于 $B$ 的所有元素：

$A \cup B = \{x \mid x \in A \lor x \in B\}$

A = {1, 2, 3}
B = {3, 4, 5}
print(A | B)  # {1, 2, 3, 4, 5}，并集
print(A.union(B))  # 同上

交集

集合 $A$ 和 $B$ 的交集（Intersection）包含同时属于 $A$ 和 $B$ 的元素：

$A \cap B = \{x \mid x \in A \land x \in B\}$

A = {1, 2, 3}
B = {3, 4, 5}
print(A & B)  # {3}，交集
print(A.intersection(B))  # 同上

如果 $A \cap B = \emptyset$ ，则称 $A$ 和 $B$ 不相交（Disjoint）。

差集

集合 $A$ 减去 $B$ 的差集（Difference）包含属于 $A$ 但不属于 $B$ 的元素：

$A - B = \{x \mid x \in A \land x \notin B\}$

也记作 $A \setminus B$ 。

A = {1, 2, 3}
B = {3, 4, 5}
print(A - B)  # {1, 2}，差集
print(A.difference(B))  # 同上

注意： $A - B$ 和 $B - A$ 通常不相等。

补集

如果存在一个全集 $U$ （包含所有讨论对象的集合），则 $A$ 的补集（Complement）是 $U$ 中不属于 $A$ 的元素：

$\overline{A} = A^c = U - A = \{x \in U \mid x \notin A\}$

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A = {1, 2, 3}
complement = U - A  # {4, 5, 6, 7, 8, 9, 10}

补集的定义依赖于全集。在不同的上下文中，全集可能不同。

对称差

集合 $A$ 和 $B$ 的对称差（Symmetric Difference）包含恰属于其中一个集合的元素：

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

A = {1, 2, 3}
B = {3, 4, 5}
print(A ^ B)  # {1, 2, 4, 5}，对称差
print(A.symmetric_difference(B))  # 同上

对称差在集合运算中的地位类似于异或在逻辑运算中的地位。

集合恒等式

集合运算遵循一系列恒等式，这些恒等式与逻辑等价式有对应关系。

基本恒等式

幂等律：

$A \cup A = A$

$A \cap A = A$

交换律：

$A \cup B = B \cup A$

$A \cap B = B \cap A$

结合律：

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

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

分配律：

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

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

吸收律：

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

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

涉及空集和全集的恒等式

同一律：

$A \cup \emptyset = A$

$A \cap U = A$

支配律：

$A \cup U = U$

$A \cap \emptyset = \emptyset$

补集律：

$A \cup \overline{A} = U$

$A \cap \overline{A} = \emptyset$

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

德摩根律

德摩根律在集合运算中同样重要：

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

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

这两个公式可以推广到多个集合：

$\overline{\bigcup_{i=1}^{n} A_i} = \bigcap_{i=1}^{n} \overline{A_i}$

$\overline{\bigcap_{i=1}^{n} A_i} = \bigcup_{i=1}^{n} \overline{A_i}$

在编程中，德摩根律常用于简化条件：

# "不在 A 中 或 不在 B 中" 等价于 "不在 (A 并 B) 中"
not (x in A and x in B)  # 等价于
not x in A or not x in B  # 等价于
x not in A | B

笛卡尔积

笛卡尔积（Cartesian Product）是构建有序对集合的运算。

有序对

有序对（Ordered Pair） $(a, b)$ 是由两个元素按固定顺序组成的结构。有序对的关键性质是：

$(a, b) = (c, d) \Leftrightarrow a = c \land b = d$

注意： $(a, b) \neq (b, a)$ （除非 $a = b$ ），这与集合不同。

笛卡尔积的定义

集合 $A$ 和 $B$ 的笛卡尔积 $A \times B$ 是所有有序对 $(a, b)$ 的集合，其中 $a \in A$ ， $b \in B$ ：

$A \times B = \{(a, b) \mid a \in A \land b \in B\}$

例如，设 $A = \{1, 2\}$ ， $B = \{x, y\}$ ，则：

$A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$

A = {1, 2}
B = {'x', 'y'}
cartesian = {(a, b) for a in A for b in B}
# {(1, 'x'), (1, 'y'), (2, 'x'), (2, 'y')}

笛卡尔积的性质

大小关系：如果 $A$ 有 $m$ 个元素， $B$ 有 $n$ 个元素，则 $A \times B$ 有 $m \times n$ 个元素。

不满足交换律： $A \times B \neq B \times A$ （除非 $A = B$ 或其中一个是空集）

对并集的分配律：

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

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

对交集的分配律：

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

n 元笛卡尔积

笛卡尔积可以推广到多个集合：

$A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_i \in A_i\}$

特别地， $A^n = \underbrace{A \times A \times \cdots \times A}_{n\text{ 个}}$ 。

例如， $\mathbb{R}^2$ 表示二维平面上的所有点， $\mathbb{R}^3$ 表示三维空间中的所有点。

# 二维平面上的点
R2 = [(x, y) for x in range(3) for y in range(3)]
# [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]

幂集

幂集的定义

集合 $A$ 的幂集（Power Set）是 $A$ 的所有子集组成的集合，记作 $\mathcal{P}(A)$ 或 $2^A$ 。

例如，设 $A = \{1, 2\}$ ，则：

$\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$

from itertools import combinations

def power_set(s):
    result = []
    for r in range(len(s) + 1):
        result.extend([set combo) for combo in combinations(s, r)])
    return result

A = {1, 2}
print(power_set(A))
# [set(), {1}, {2}, {1, 2}]

幂集的大小

如果 $|A| = n$ （ $A$ 有 $n$ 个元素），则 $|\mathcal{P}(A)| = 2^n$ 。

这是因为对于每个元素，都有两种选择：在子集中或不在子集中。 $n$ 个元素的组合数是 $2^n$ 。

这个结论有一个重要推论：任何集合的幂集比原集合更大，即 $|\mathcal{P}(A)| > |A|$ 。这是康托尔定理的内容，揭示了无穷集合的不同"大小"。

幂集的应用

幂集在计算机科学中有重要应用：

布尔代数： $n$ 个布尔变量的可能取值组合对应于 $\{0, 1\}^n$ ，这与幂集的大小相同。

组合优化：子集选择问题（如背包问题）本质上是遍历幂集。

数据库：关系数据库中的关系是笛卡尔积的子集，约束条件限定了允许的子集。

集合的分划

分划的定义

集合 $A$ 的分划（Partition）是将 $A$ 分成若干非空、互不相交的子集，这些子集的并等于 $A$ 。

形式地说，集合族 $\{A_1, A_2, \ldots, A_n\}$ 是 $A$ 的分划，当且仅当：

$A_i \neq \emptyset$ （每个子集非空）
$A_i \cap A_j = \emptyset$ ，当 $i \neq j$ （子集两两不相交）
$\bigcup_{i=1}^{n} A_i = A$ （所有子集的并等于 $A$ ）

例如，整数集 $\mathbb{Z}$ 可以按模 3 分划：

$\mathbb{Z} = \{3k \mid k \in \mathbb{Z}\} \cup \{3k+1 \mid k \in \mathbb{Z}\} \cup \{3k+2 \mid k \in \mathbb{Z}\}$

这三个集合分别是被 3 整除、除以 3 余 1、除以 3 余 2 的整数，它们互不相交且并集为 $\mathbb{Z}$ 。

# 按模 3 分划
def partition_mod3(n):
    return n % 3

numbers = range(10)
partitions = {0: [], 1: [], 2: []}
for n in numbers:
    partitions[partition_mod3(n)].append(n)
# {0: [0, 3, 6, 9], 1: [1, 4, 7], 2: [2, 5, 8]}

分划与等价关系

分划与等价关系有深刻联系：每个等价关系诱导一个分划，每个分划对应一个等价关系。这个联系将在下一章详细讨论。

一个具体例子：在社交网络中，"是否有共同好友"可能是一个等价关系（需要验证传递性）。如果成立，它将用户分划成若干"社交圈"。

容斥原理

容斥原理（Inclusion-Exclusion Principle）是计算多个集合并集大小的重要工具。

两个集合的容斥原理

$|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|$

一般形式

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n|$

应用示例

问题：在 1 到 100 的整数中，有多少个数能被 2 或 3 整除？

设 $A$ 为能被 2 整除的数， $B$ 为能被 3 整除的数。

$|A| = 100/2 = 50$

$|B| = \lfloor 100/3 \rfloor = 33$

$|A \cap B|$ 是能被 6 整除的数， $|A \cap B| = \lfloor 100/6 \rfloor = 16$

$|A \cup B| = 50 + 33 - 16 = 67$

# 验证
count = sum(1 for i in range(1, 101) if i % 2 == 0 or i % 3 == 0)
print(count)  # 67

集合论的悖论

朴素集合论存在一些逻辑悖论，最著名的是罗素悖论（Russell's Paradox）。

罗素悖论

考虑"所有不包含自身的集合组成的集合"：

$R = \{x \mid x \notin x\}$

问： $R \in R$ 是否成立？

如果 $R \in R$ ，根据 $R$ 的定义， $R \notin R$ ，矛盾
如果 $R \notin R$ ，根据 $R$ 的定义， $R \in R$ ，矛盾

这个悖论揭示了朴素集合论的问题：不能任意定义"所有满足某性质的元素组成的集合"，因为可能导致自指问题。

公理化集合论

为解决悖论，数学家发展了公理化集合论（如 ZFC 公理系统），对集合的构造施加限制。在 ZFC 中，通过"分离公理"限制集合构造的方式，避免了罗素悖论。

虽然公理化集合论更加严谨，但在大多数应用场合，朴素集合论已经足够，只需注意避免涉及"所有集合的集合"这类自指定义。

集合论在计算机科学中的应用

集合论不仅是数学的基础，在计算机科学中也有着直接而广泛的应用。理解这些应用，有助于将抽象的数学概念与实际编程联系起来。

关系数据库的数学基础

关系数据库的整个理论体系建立在集合论之上。理解这一点，能帮助你更好地理解 SQL 查询的本质。

关系即集合：在关系数据库中，一张表（关系）本质上是一个有限集合。表的每一行是一个元组，元组是属性的有序组合。

例如，一个学生表可以表示为： $Student = \{(1, '张三', 20), (2, '李四', 21), (3, '王五', 20)\}$

这是笛卡尔积的子集： $Student \subseteq ID \times Name \times Age$

SQL 操作的集合论解释：

SQL 操作	集合论对应
`SELECT ... FROM A, B`	笛卡尔积 $A \times B$
`UNION`	并集 $\cup$
`INTERSECT`	交集 $\cap$
`EXCEPT` / `MINUS`	差集 $-$
`WHERE` 条件	选择运算 $\sigma$ （筛选满足条件的元素）
`SELECT DISTINCT`	去重，体现集合的互异性

-- 并集操作
SELECT name FROM students WHERE age > 20
UNION
SELECT name FROM teachers WHERE age > 20;
-- 等价于：{学生中年龄>20的姓名} ∪ {教师中年龄>20的姓名}

-- 差集操作
SELECT name FROM students
EXCEPT
SELECT name FROM graduates;
-- 等价于：学生集合 - 毕业生集合

连接操作的集合论本质：

内连接本质上是选择笛卡尔积中满足连接条件的子集：

SELECT * FROM A JOIN B ON A.id = B.a_id;
-- 数学表示：{(a, b) ∈ A × B | a.id = b.a_id}

外连接更复杂，涉及并集操作：左外连接 = 内连接 ∪ 左表中未匹配的元组（右属性置空）。

编程语言中的集合类型

现代编程语言都提供了集合数据类型，直接对应数学中的集合概念。

Python 的 set 类型：

# 创建集合
A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

# 集合运算
A | B   # 并集：{1, 2, 3, 4, 5, 6, 7}
A & B   # 交集：{3, 4, 5}
A - B   # 差集：{1, 2}
A ^ B   # 对称差：{1, 2, 6, 7}

# 子集判断
{1, 2} <= A  # True
{1, 6} <= A  # False

# 成员测试（O(1) 时间复杂度，比列表快）
3 in A  # True

集合的去重特性：集合自动去除重复元素，这来源于集合论中元素的互异性。

# 快速去重
numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique = list(set(numbers))  # [1, 2, 3, 4]

性能考量：集合使用哈希表实现，成员测试和插入的平均时间复杂度为 O(1)，而列表是 O(n)。当需要频繁判断元素是否存在时，应优先使用集合。

位图与集合的高效表示

当元素是有限个整数（或可以映射到整数）时，可以用位图高效表示集合。

原理：用二进制位的第 $i$ 位表示元素 $i$ 是否在集合中。1 表示存在，0 表示不存在。

class BitSet:
    """位图集合实现"""
    def __init__(self, max_value):
        self.bits = 0
        self.max_value = max_value
    
    def add(self, x):
        if 0 <= x <= self.max_value:
            self.bits |= (1 << x)
    
    def remove(self, x):
        if 0 <= x <= self.max_value:
            self.bits &= ~(1 << x)
    
    def contains(self, x):
        return bool(self.bits & (1 << x))
    
    def union(self, other):
        result = BitSet(max(self.max_value, other.max_value))
        result.bits = self.bits | other.bits
        return result
    
    def intersection(self, other):
        result = BitSet(max(self.max_value, other.max_value))
        result.bits = self.bits & other.bits
        return result

# 使用示例
bs = BitSet(100)
bs.add(5)
bs.add(10)
print(bs.contains(5))   # True
print(bs.contains(7))   # False

位图的优势：

空间效率高：每个元素只占 1 位
集合运算高效：并集、交集、差集都是位运算，时间复杂度 O(1)
缓存友好：内存连续

位图在数据库索引、布隆过滤器、垃圾回收的标记阶段等场景广泛应用。

集合在算法中的应用

去重与判重：

# 判断数组是否有重复元素
def has_duplicate(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

# 时间复杂度 O(n)，空间复杂度 O(n)

查找交集/并集：

# 找出两个数组中的公共元素
def common_elements(arr1, arr2):
    return list(set(arr1) & set(arr2))

# 找出只在一个数组中出现的元素（对称差）
def unique_elements(arr1, arr2):
    return list(set(arr1) ^ set(arr2))

滑动窗口问题：集合常用于维护滑动窗口中的元素，判断是否有重复。

def length_of_longest_substring(s):
    """无重复字符的最长子串长度"""
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

图论中的集合应用

图的表示本身就依赖集合论。图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 组成。

# 图的集合表示
class Graph:
    def __init__(self):
        self.vertices = set()  # 顶点集
        self.edges = set()     # 边集，存储为 (u, v) 元组
    
    def add_vertex(self, v):
        self.vertices.add(v)
    
    def add_edge(self, u, v):
        self.vertices.add(u)
        self.vertices.add(v)
        self.edges.add((u, v))
    
    def neighbors(self, v):
        """返回顶点 v 的邻居集合"""
        return {u for (x, u) in self.edges if x == v} | {u for (u, x) in self.edges if x == v}

幂集与组合枚举

幂集在组合优化问题中经常出现。例如，背包问题、子集和问题都需要枚举所有子集。

from itertools import combinations

def power_set(elements):
    """生成幂集"""
    result = []
    for r in range(len(elements) + 1):
        for subset in combinations(elements, r):
            result.append(set(subset))
    return result

# 子集和问题：找出和为 target 的子集
def subset_sum(numbers, target):
    """暴力枚举所有子集"""
    for r in range(len(numbers) + 1):
        for subset in combinations(numbers, r):
            if sum(subset) == target:
                return set(subset)
    return None

虽然幂集的大小是 $2^n$ ，增长极快，但对于小规模问题或需要精确解的场景，幂集枚举仍然是可行的方法。

容斥原理在概率计算中的应用

容斥原理在计算事件概率时特别有用。

问题：在 1 到 100 的整数中随机取一个数，求它既不被 2 整除也不被 3 整除的概率。

解：

设 $A$ 为被 2 整除的事件， $P(A) = 50/100 = 1/2$
设 $B$ 为被 3 整除的事件， $P(B) = 33/100$
$P(A \cap B)$ 为被 6 整除的概率， $P(A \cap B) = 16/100$
所求概率 $P(\overline{A} \cap \overline{B}) = P(\overline{A \cup B}) = 1 - P(A \cup B)$
$= 1 - [P(A) + P(B) - P(A \cap B)]$
$= 1 - (0.50 + 0.33 - 0.16) = 0.33$

# 验证
count = sum(1 for i in range(1, 101) if i % 2 != 0 and i % 3 != 0)
print(f"概率 = {count/100}")  # 0.33

小结

本章介绍了集合论的基础知识：

基本概念：集合的定义、元素与集合的关系、常用数集符号
表示方法：枚举法、描述法、区间表示法
集合关系：子集、真子集、集合相等
集合运算：并、交、差、补、对称差
重要概念：笛卡尔积、幂集、分划
计算工具：容斥原理
实际应用：关系数据库、编程语言集合类型、位图、算法优化

集合论是后续学习函数与关系、组合数学、图论的基础。理解集合论在计算机科学中的应用，能够帮助你更好地设计和分析算法，理解数据结构的选择依据，以及编写更高效的代码。下一章将讨论函数与关系，它们建立在集合论的基础上，是连接抽象数学与具体应用的重要桥梁。

练习

证明集合恒等式 $A - (B \cup C) = (A - B) \cap (A - C)$ 。
设 $A = \{1, 2, 3\}$ ，写出 $A$ 的幂集 $\mathcal{P}(A)$ 。
证明德摩根律 $\overline{A \cap B} = \overline{A} \cup \overline{B}$ 。
计算 $A \times B$ ，其中 $A = \{a, b\}$ ， $B = \{1, 2, 3\}$ 。
在 1 到 1000 的整数中，有多少个数既不能被 3 整除，也不能被 5 整除？

集合的基本概念​

什么是集合？​

元素与集合的关系​

常用数集符号​

空集​

集合的表示方法​

枚举法​

描述法（谓词法）​

区间表示法​

集合之间的关系​

子集​

真子集​

集合相等​

超集​

集合的运算​

并集​

交集​

差集​

补集​

对称差​

集合恒等式​

基本恒等式​

涉及空集和全集的恒等式​

德摩根律​

笛卡尔积​

有序对​

笛卡尔积的定义​

笛卡尔积的性质​

n 元笛卡尔积​

幂集​

幂集的定义​

幂集的大小​

幂集的应用​

集合的分划​

分划的定义​

分划与等价关系​

容斥原理​

两个集合的容斥原理​

三个集合的容斥原理​

一般形式​

应用示例​

集合论的悖论​

罗素悖论​

公理化集合论​

集合论在计算机科学中的应用​

关系数据库的数学基础​

编程语言中的集合类型​

位图与集合的高效表示​

集合在算法中的应用​

图论中的集合应用​

幂集与组合枚举​

容斥原理在概率计算中的应用​

小结​

练习​