De Morgan定理
(1)
(2)
（2）成立
（1）成立
（*）
证明（*）：
由于n=2，即（2）式，成立
根据数学归纳法，假设（*）成立
即：，则有
证毕。
容斥原理，定义|A|为集合A的元素个数
预备知识：若
则|AUB|=|A|+|B|
若
则|AUB|最多被计算一次
因此：|AUB|=|A|+|B|-|
|
进一步：
等价于：
可采用数学归纳法证明，类比（*）式的证明
又由于：
所以：
原文：http://www.cnblogs.com/JasonCow/p/6412111.html