De Morgan定理

  (1)

  (2)

（2）成立

（1）成立

（*）

证明（*）：

由于n=2，即（2）式，成立

根据数学归纳法，假设（*）成立

　　即：，则有

　　证毕。

容斥原理，定义|A|为集合A的元素个数

预备知识：若则|AUB|=|A|+|B|

　　　　   若则|AUB|最多被计算一次

　　　　　因此：|AUB|=|A|+|B|-||

进一步：

等价于：

可采用数学归纳法证明，类比（*）式的证明

又由于：

所以：

排列组合-容斥原理