两个集合的容斥原理

关键思路是把 $A \cup B$ 拆成三个两两不相交的部分,再各计数一次。

首先,用另一个集合来划分每个集合:$A = (A \setminus B) \cup (A \cap B)$ 与 $B = (B \setminus A) \cup (A \cap B)$。在这两个等式中,右边的两部分互不相交,因为 $(A\setminus B) \cap (A \cap B) = \varnothing$(不在 $B$ 中的元素不可能同时在 $B$ 中),同理 $(B\setminus A) \cap (A \cap B) = \varnothing$。由于有限集合的大小等于其两两不相交划分各部分大小之和,由此得到 $|A| = |A \setminus B| + |A \cap B|$ 与 $|B| = |B \setminus A| + |A \cap B|$。

接下来注意到 $A \cup B$ 本身可以拆成三个两两不相交的部分:$A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)$。事实上 $A\setminus B$、$B\setminus A$、$A\cap B$ 两两不相交(属于 $A\setminus B$ 的元素不属于 $B$,因而也不属于 $A \cap B$ 或 $B \setminus A$;其余情形同理),且它们的并集恰好就是属于 $A$ 或属于 $B$ 的全部元素。按此划分计数即得 $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$。

最后代入:由 $|A| = |A \setminus B| + |A \cap B|$ 得 $|A \setminus B|$ $= |A| - |A\cap B|$,由 $|B| = |B \setminus A| + |A \cap B|$ 得 $|B \setminus A|$ $= |B| - |A\cap B|$。将两者代入 $|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$ 得 $|A \cup B| = (|A| - |A\cap B|) + (|B| - |A\cap B|) + |A\cap B| = |A| + |B| - |A\cap B|$,这正是 $|A \cup B| = |A| + |B| - |A \cap B|$。证明完毕。