很多组合数学的问题正向考虑比较困难,反向考虑就容易很多。这种时候,Morgan 定律就排上了用场,下面是该定律的形象化的证明和一个具体应用的例子。
假定有两个集合 A 和 B,Morgan 定律把它们的交集通过补集和并集操作表示如下:
(1)
这个定律一个形象化的证明如下:
下面是 Morgan 定律具体应用的例子,假定我们有一个 位的数字,每一位上可以是0-9这10个数字,那么既有0又有1的数字一共有多少?
所有总共可能的数字是 (World):
(2)
其中没有0的数字 (定义为集合 ) :
(3)
其中没有1的数字 (定义为集合 ) :
(4)
所有有0的数字(定义为集合A):
(5)
所有有1的数字(定义为集合B):
(6)
那么根据 Morgan 定律,又有0又有1的数字就是:
(7)
我们已经知道 ,
,关键是
如何计算,可以看出,既没有0也没有1的数字是:
(8)
所以我们有:
(9)
最后对于又有0又有1的数字就是:
(10)
对于 的情况,又有0又有1的数字只有两个:
和
,按照上面的公式算一下:
(11)
Feller 老爷爷后面的东西还是很靠谱呀。 🙂