集合的交并补代数

集合的交、并、补代数把“同时满足”“至少满足其一”“在全集中不满足”变成可计算的运算。先固定全集 $U$；对 $A,B\subseteq U$，交集 $A\cap B$ 收集同时属于两者的元素，并集 $A\cup B$ 收集至少属于其一的元素，补集 $A^c=U\setminus A$ 收集不属于 $A$ 的元素。

一张名单的三种读法

取 $U=\{1,2,3,4,5\}$，$A=\{1,2,4\}$，$B=\{2,3,4\}$。逐个检查可得 $A\cap B=\{2,4\}$、$A\cup B=\{1,2,3,4\}$、$A^c=\{3,5\}$。集合差 $A\setminus B=\{1\}=A\cap B^c$；它不同于对称差 $A\mathrm{△}B=(A\setminus B)\cup (B\setminus A)=\{1,3\}$。

运算律来自成员资格

交、并满足交换律和结合律，例如 $A\cup (B\cup C)=(A\cup B)\cup C$。分配律 $$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$ 可按元素证明：任取 $x$，左边要求“$x\in A$ 且（$x\in B$ 或 $x\in C$）”；右边要求“（$x\in A$ 且 $x\in B$）或（$x\in A$ 且 $x\in C$）”，两句在每种成员资格下相同。另一条分配律交换交与并即可得到。吸收律 $A\cup (A\cap B)=A$ 告诉我们：先选 $A$ 再把 $A$ 中的一小部分并回来，不增加任何元素。

德摩根律给出 $(A\cup B{)}^c=A^c\cap B^c$ 和 $(A\cap B{)}^c=A^c\cup B^c$。在数据筛选中，“非（年龄符合或地区符合）”要同时排除两种条件，直接把“或”留在外面会筛错。有限集合还满足 $|A\cup B|=|A|+|B|-|A\cap B|$：两张名单各数一次时，交集的人数被数了两次，所以减一次；这连到容斥原理。对无限集合谈“人数”时，不应未经说明就把有限计数式照搬为普通整数加减。

参考资料与相关词条

• MIT 18.100A：集合、运算与证明。
• 相关：集合、德摩根律、容斥原理。