集合运算与韦恩图

八组运算律为什么成立

任取 $x\in U$。集合相等只须证明两侧对这个任意元素给出相同的归属判断。

(1) 交集要求两个条件都成立，并集要求至少一个成立；条件的列举顺序不改变真假，故得到两条交换律。

(2) $x\in A\cup(B\cup C)$ 与 $x\in(A\cup B)\cup C$ 都表示三个条件至少一个成立；两个交式都表示三个条件全部成立，故得到结合律。

(3) 对 $A\cup(B\cap C)$，分 $x\in A$ 与 $x\notin A$ 两种情况：若在 $A$ 中，两侧都包含它；若不在 $A$ 中，两侧都要求它同时属于 $B,C$。对另一条 $A\cap(B\cup C)$，若不在 $A$ 中两侧都不包含它；若在 $A$ 中两侧都要求至少属于 $B,C$ 之一。这给出两条分配律的完整证明。

(4) 元素永不属于空集、必属于全集，所以与空集取并不增元素、取交没有元素，与全集取并得到全集、取交保留原集。

(5) 同一个归属判断重复一次，不改变真假，所以交并均幂等。

(6) 因为 $A\cap B\subseteq A$，把它并入 $A$ 不增加元素；因为 $A\subseteq A\cup B$，用后者与 $A$ 取交不会删去 $A$ 中元素。

(7) 任取 $x\in U$，它恰好处于“属于 $A$”和“不属于 $A$”中的一种，因此 $A$ 与补集覆盖 $U$ 且不相交。

(8) 不属于 $A\cup B$ 表示两者都不属于，等价于属于 $A^c\cap B^c$；不属于 $A\cap B$ 表示至少不属于一者，等价于属于 $A^c\cup B^c$。再否定一次“不属于 $A$”，恢复“属于 $A$”，得到 $(A^c)^c=A$。

所有论证都适用于空集、相等集合和包含集合，不依赖韦恩图是否把所有区域画成非空。

用元素法证明集合恒等式

证明 $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ 时，任取元素 $x$，有

两个集合对每个元素作出相同判断，所以相等。这种证明也说明集合运算的分配律来自逻辑中的“且”“或”。同样，$A\subseteq B$ 等价于 $A\cap B=A$，也等价于 $A\cup B=B$；把这些等式改写成包含关系，往往比直接运算容易。

对称差：逐元素的二值运算与消去律

设 $A,B,C\subseteq U$。给每个 $x\in U$ 记一个数 $\mathbf1_A(x)$：属于 $A$ 时为 $1$，不属于时为 $0$。对称差正好记录两者归属不同，因此

这只是对 $0,1$ 的四种组合逐一核对，不需要数论先修。它给出

最后一式说，连续翻转同一批元素两次会还原。因而

例如 $(P\triangle A)\triangle(Q\triangle B)=A\triangle B$，在两侧再与 $A\triangle B$ 作对称差，即得 $P\triangle Q=\varnothing$，等价于 $P=Q$。若 $P,Q$ 均为某个 $n$ 元集的子集，则这样的有序集合对有 $2^n$ 个。

有限集合还有

证明时将 $A\cup B$ 分为 $A\setminus B,A\cap B,B\setminus A$ 三个不交部分；右侧加法将中间部分算两遍，扣除两遍即剩对称差。

对称差距离的最小值与全部取等集合

有限集合的差异可用 $d(A,B)=|A\triangle B|$ 度量。对任意有限集 $X$，

逐元素证明：若一个元素对 $A,B$ 的归属不同，无论 $X$ 选不选，它恰贡献 $1$；若同时属于 $A,B$，$X$ 选它贡献 $0$、不选贡献 $2$；若同时不属于 $A,B$，$X$ 不选贡献 $0$、选贡献 $2$。

所以最小值为 $|A\triangle B|$，全部取等集合恰为

对称差中的每个元素可以自由决定，取等集合共有 $2^{|A\triangle B|}$ 个。例如 $A=\{1,2,3\},B=\{2,3,4\}$，最小值为 $2$，$X$ 必须包含 $2,3$，可任选 $1,4$，有四种。只求得下界而不说明可达配置，会漏掉这个方法的一半。