两集合的容斥原理

把 $A\cup B$ 分成三个两两不相交的部分:$A\setminus B$(只属于 $A$)、$B\setminus A$(只属于 $B$)、以及 $A\cap B$(两者都属于)。由于这些部分互不相交且覆盖了 $A\cup B$,所以 $|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|$。

再注意到 $A$ 本身分成不相交的 $A\setminus B$ 与 $A\cap B$,于是 $|A|=|A\setminus B|+|A\cap B|$,即 $|A\setminus B|=|A|-|A\cap B|$。同理 $|B\setminus A|=|B|-|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|$。