An informal (picture based) proof of De Morgan’s laws

很多组合数学的问题正向考虑比较困难,反向考虑就容易很多。这种时候,Morgan 定律就排上了用场,下面是该定律的形象化的证明和一个具体应用的例子。

假定有两个集合 A 和 B,Morgan 定律把它们的交集通过补集和并集操作表示如下:

(1)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) \end{equation*}

这个定律一个形象化的证明如下:

下面是 Morgan 定律具体应用的例子,假定我们有一个 k 位的数字,每一位上可以是0-9这10个数字,那么既有0又有1的数字一共有多少?

所有总共可能的数字是 (World):

(2)   \begin{equation*} 10^k \end{equation*}

其中没有0的数字 (定义为集合 \sim A) :

(3)   \begin{equation*} 9^k \end{equation*}

其中没有1的数字 (定义为集合 \sim B) :

(4)   \begin{equation*} 9^k \end{equation*}

所有有0的数字(定义为集合A):

(5)   \begin{equation*} 10^k - 9^k \end{equation*}

所有有1的数字(定义为集合B):

(6)   \begin{equation*} 10^k - 9^k \end{equation*}

那么根据 Morgan 定律,又有0又有1的数字就是:

(7)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) \end{equation*}

我们已经知道 (\sim A) = 9^k , (\sim B) = 9^k ,关键是 (\sim A)  \bigcup (\sim B) 如何计算,可以看出,既没有0也没有1的数字是:

(8)   \begin{equation*} (\sim A)  \bigcap (\sim B) = 8^k \end{equation*}

所以我们有:

(9)   \begin{equation*} (\sim A)  \bigcup (\sim B) = (\sim A) + (\sim B) - (\sim A)  \bigcap (\sim B) = 9^k + 9^k - 8^k \end{equation*}

最后对于又有0又有1的数字就是:

(10)   \begin{equation*} A \bigcap B = \sim ((\sim A)  \bigcup (\sim B)) = 10^k - (9^k + 9^k - 8^k) \end{equation*}

对于 k=2 的情况,又有0又有1的数字只有两个:0110,按照上面的公式算一下:

(11)   \begin{equation*} 10^2 - (9^2 + 9^2 - 8^2) = 2 \end{equation*}

Feller 老爷爷后面的东西还是很靠谱呀。 🙂