1.3 集合运算与笛卡尔积

在第 1.2 节中，你学会了如何描述一个集合，以及如何判断一个对象是否属于这个集合。现在，我们要把两个集合组合起来。组合有两种常用方式：

• 集合运算用来组合或比较成员资格条件。

• 笛卡尔积用来把第一个集合中的一个选择与第二个集合中的一个选择配成一对。

学完本节后，你将能从零开始计算并集、交集、差集、补集与笛卡尔积，并且能解释每个结果的含义，而不只是机械地移动符号。

运算之前，先确定全集

全集（universal set）记作 $U$，表示当前问题中允许讨论的所有对象。它不是“世界上所有东西的集合”，而是由问题的范围决定的。

例如，如果我们只研究从 $1$ 到 $6$ 的整数，就可以规定

这个问题中的其他集合都看作 $U$ 的子集。令

本节前半部分会一直使用这个例子。先固定全集，可以避免一个重要的歧义：“不在 $A$ 中”到底要保留哪些对象，只有先知道允许从哪些对象中选择，才能确定。

从单个元素出发理解四种集合运算

想象从 $U$ 中任取一个元素 $x$，然后依次问两个“是或否”的问题：

1. $x$ 是否属于 $A$？

2. $x$ 是否属于 $B$？

成员资格一共只有四种可能区域：

下面的每一种集合运算，都是从这四个区域中选择一个或多个区域。

并集：保留至少出现在一个集合中的元素

$A$ 与 $B$ 的并集记作 $A\cup B$。只要一个元素属于 $A$、属于 $B$，或者同时属于二者，它就属于并集：

竖线 $\mid$ 表示“满足”。整个式子可以读作：“所有满足‘属于 $A$ 或属于 $B$’的 $U$ 中元素 $x$ 所组成的集合。”这里数学中的“或”是兼或，因此同时属于两个集合的元素也要保留。

在当前例子中，先写出 $A$ 的元素，再补上 $B$ 中尚未出现的元素：

集合不记录重复次数，所以重复的元素只写一次。

交集：只保留共同元素

交集记作 $A\cap B$。一个元素必须同时属于两个集合，才能进入交集：

逐个检查可知，只有 $2$ 和 $6$ 同时通过两个成员资格条件，所以

差集：保留一边，并去掉重叠部分

差集 $A\setminus B$ 先从 $A$ 开始，再删除其中所有也属于 $B$ 的元素：

符号 $\notin$ 表示“不属于”。在例子中，从 $A$ 删除 $2$ 和 $6$，剩下

差集有方向。如果交换两个集合，就要从 $B$ 开始：

因此，$A\setminus B$ 与 $B\setminus A$ 通常不同。

补集：保留全集中不属于该集合的元素

$A$ 的补集记作 $A^{\mathsf c}$，它包含固定全集中所有不属于 $A$ 的元素：

从 $U=\{1,2,3,4,5,6\}$ 中删除 $1,2,4,6$，得到

这就是为什么必须先明确全集。即使 $A$ 不变，只要全集改变，$A$ 的补集也可能改变。

检查四个互不重叠的区域

对于同一个 $U$、$A$ 与 $B$，四个互不重叠的区域分别是

“互不重叠”表示没有元素会同时出现在两个区域中；这四个区域合在一起又包含了 $U$ 中的每个元素。因此，它们也可以用来检查答案：$U$ 中每个元素都必须恰好出现一次。

实验把四种成员资格区域变成可投放区域。投放对象前，可以先说出它的两个判断结果，例如“在 $A$ 中，但不在 $B$ 中”，再选择对应区域。这样可以把图形位置与成员资格规则联系起来。

计算并集大小时，避免重复计数

如果直接计算 $|A|+|B|$，那么 $A\cap B$ 中的每个元素会在计算 $A$ 时数一次，在计算 $B$ 时再数一次。减去交集的大小，就能去掉多算的那一次：

在当前例子中，

这与列出的五个元素 $\{1,2,3,4,6\}$ 一致。这种思路称为两个集合的容斥原理（inclusion–exclusion）。后续章节会把同一种计数思想扩展到更多集合。

为什么补集会交换“或”与“且”

下面两个等式称为德摩根律（De Morgan’s laws）：

符号虽然紧凑，但可以直接翻译成日常语言：

• 一个元素不在并集中，只有当它不在 $A$ 中，并且也不在 $B$ 中。

• 一个元素不在交集中，只要它不在 $A$ 中，或者不在 $B$ 中，或者两个集合都不在。

检查第一条定律时，可以跟踪任意一个元素 $x$。若 $x\notin A\cup B$，说明两个集合都没有接纳它。于是 $x\in A^{\mathsf c}$ 且 $x\in B^{\mathsf c}$，所以 $x\in A^{\mathsf c}\cap B^{\mathsf c}$。这个推理也可以反向进行，因此等式两边包含完全相同的元素。

“且”“或”“非”会在第 2 章成为正式的逻辑运算。本节只需要使用它们在成员资格判断中的普通含义。

有序对会记住两个位置

集合运算组合的是成员资格条件。接下来要学习的构造组合的是选择。假设一个应用中有两个用户：

并且有三种操作：

要表示“Ada 执行编辑”，需要同时保存一个用户和一种操作。有序对可以完成这件事：

第一个位置与第二个位置承担不同角色。一般来说，

只有当第一个坐标相同且第二个坐标也相同时，两个有序对才相等：

“第一坐标”和“第二坐标”只是两个位置的名称，这里不要求任何几何知识。

笛卡尔积生成所有可能的配对

笛卡尔积 $A\times B$ 包含所有第一坐标来自 $A$、第二坐标来自 $B$ 的有序对：

可以用下面的固定步骤完整列出它：

1. 选择 $A$ 的第一个元素。

2. 把它依次与 $B$ 的每个元素配对。

3. 移到 $A$ 的下一个元素并重复。

若 $A=\{1,2\}$ 且 $B=\{x,y,z\}$，就得到

也可以把同样的六个有序对排成一个长方形表格：

这里的方括号只是把有序对整理成行和列，不需要使用矩阵运算。

如果 $A$ 有 $2$ 个选择，$B$ 有 $3$ 个选择，那么每个第一坐标都有 $3$ 个可能搭档，所以共有 $2\cdot3=6$ 个有序对。对任意有限集合，都有

在像素地板中，每个格子都代表一个有序对。它所在的行固定一个坐标，所在的列固定另一个坐标。涂满所有格子就是构造完整的笛卡尔积；只涂选中的格子，则会得到一个由部分有序对组成的集合。

这样的选中集合 $R\subseteq A\times B$ 称为从 $A$ 到 $B$ 的二元关系。现在只需把“关系”理解为“被选中的一些有序对”。第 4 章会从头建立完整理论，本节不预先要求其他关系知识。

章节衔接

这一章中，你依次学会了识别离散状态、用集合描述对象、对成员资格进行运算，以及构造有序对。你可能已经注意到，“且”“或”“非”在这些定义中反复出现。第 2 章会从这些熟悉的词出发，一步一步把它们变成精确的逻辑命题。