基础运算 ·

\cup \; \cap \; - \; \triangle \; {}^{c}

并、交、差、对称差与补

有了成员关系，就能从两个集合造出第三个。五种基本运算的定义都是一句「取哪些元素」，都用成员关系的逻辑联结词写成，在文氏图上恰好各对应一块分区。

1 · 五种运算的定义

operations ·

\cup \; \cap \; - \; \triangle \; {}^{c}

定义 1.1（五种运算）设 $A$ 、 $B$ 是全集 $U$ 的子集。

A \cup B = \{x \mid x \in A \text{ 或 } x \in B\} \qquad A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}

A - B = \{x \mid x \in A \text{ 且 } x \notin B\} \qquad A \triangle B = (A - B) \cup (B - A) \qquad A^c = U - A

依次称作并、交、差、对称差与补。

定义右端的「或、且、非」正是逻辑联结词，所以集合运算与命题联结词是同一套结构的两种写法（见命题与联结词）。补运算是五者中唯一依赖全集的一个：脱离 $U$ 谈 $A^c$ 没有意义，同一个 $A$ 换一个全集，补集就换一批元素。

由定义直接得到两条常用改写： $A - B = A \cap B^c$ ，差是「交上补」，于是差不是独立的第五种运算； $A \triangle B = (A \cup B) - (A \cap B)$ ，对称差是「并去掉交」，即「恰属其一」。

图 1-1 · 五种运算各自点亮文氏图的哪块分区，以及结果的外延与基数。可切换运算并改动两集合的成员对照。

2 · 对偶与 De Morgan 律

duality ·

(A \cup B)^c = A^c \cap B^c

定理 2.1（De Morgan 律） $(A \cup B)^c = A^c \cap B^c$ ，且 $(A \cap B)^c = A^c \cup B^c$ 。

证明证第一式，用相等即互相包含（见定义 1.1）。对任意 $x$ ， $x \in (A \cup B)^c$ 当且仅当 $x \notin A \cup B$ ，即「 $x \in A$ 或 $x \in B$ 」为假。一个析取为假当且仅当两个支都为假，即 $x \notin A$ 且 $x \notin B$ ，也就是 $x \in A^c \cap B^c$ 。两个方向的推理都是同一串等价，故等式成立。第二式把 $A$ 、 $B$ 换成 $A^c$ 、 $B^c$ 再两边取补即得。∎

补运算把并与交对调，这条对称性叫对偶：任何只含 $\cup$ 、 $\cap$ 、 $\subseteq$ 的恒等式，把 $\cup$ 与 $\cap$ 互换、 $\subseteq$ 反向，仍是恒等式。它使运算律成对出现，记一半即可。

3 · 哪些运算律成立

laws · 结合 · 分配

并与交各自满足交换律、结合律、幂等律，并且互相分配。差与对称差的行为则不能由此类推，这是本页最容易出错的地方。取 $U = \{1, \dots, 6\}$ ，用位掩码穷举全部 $64^3 = 262144$ 个三元组 $(A, B, C)$ 逐条验证，结果分成两类。

成立的两条：对称差满足结合律 $(A \triangle B) \triangle C = A \triangle (B \triangle C)$ ，反例数 $0$ ；交对对称差分配 $A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C)$ ，反例数同样是 $0$ 。

失败的两条则失败得相当彻底。差不满足结合律： $262144$ 个三元组里 $215488$ 个（ $82.19\%$ ）两端不等，最小的反例是 $A = \{1\}$ 、 $B = \emptyset$ 、 $C = \{1\}$ ——左端 $(\{1\} - \emptyset) - \{1\} = \emptyset$ ，右端 $\{1\} - (\emptyset - \{1\}) = \{1\}$ 。并对对称差不分配： $258048$ 个三元组（ $98.4375\%$ ）失败，反例可以取到更平凡的 $A = \{1\}$ 、 $B = C = \emptyset$ ——左端得 $\{1\}$ ，右端 $\{1\} \triangle \{1\} = \emptyset$ 。

注 · 这两条失败的方向是穷举前没料到的。 $\cap$ 与 $\cup$ 在 De Morgan 与分配律里处处对称，凭这份对称性会猜「 $\cap$ 对 $\triangle$ 分配，则 $\cup$ 对 $\triangle$ 也分配」，而实测是 $98.4375\%$ 的三元组都推翻它——比差的结合律失败得更普遍。原因在于 $\triangle$ 是模 $2$ 加法而 $\cap$ 是模 $2$ 乘法，二者构成一个布尔环，分配律是环公理； $\cup$ 在这个环里不是乘法，自然不受环公理保护。对偶原理的适用范围也就到此为止：它只覆盖 $\cup$ 、 $\cap$ 、 $\subseteq$ ，把 $\triangle$ 或 $-$ 掺进来即失效。

4 · 参考文献

Algebra of sets. Wikipedia. 并、交、补的运算律清单与对偶原理。https://en.wikipedia.org/wiki/Algebra_of_sets
De Morgan's laws. Wikipedia. 集合形式与命题形式的对应。https://en.wikipedia.org/wiki/De_Morgan%27s_laws
Symmetric difference. Wikipedia. 对称差的结合律，以及幂集在 $\triangle$ 下成为交换群。https://en.wikipedia.org/wiki/Symmetric_difference
Boolean ring. Wikipedia. 以 $\triangle$ 为加法、 $\cap$ 为乘法的环结构。https://en.wikipedia.org/wiki/Boolean_ring