算法导论B.1 Exercises 答案

B.1-1

B.1-2

考虑使用数学归纳法进行证明。

已知两个集合下的德摩根律\(\overline{B\cap C}=\overline{B}\cup\overline{C},\overline{B\cup C}=\overline{B}\cap \overline{C}\)是成立的。

那么假设\(\overline{A_1\cap A_2\cap\dots\cap A_n}=\overline{A_1}\cup\overline{A_2}\cup\dots\cup\overline{A_n}\)成立，考虑如下等式：

\(\begin{aligned} \overline{A_1\cap A_2\cap\dots\cap A_n\cap A_{n+1}}&=\overline{(A_1\cap A_2\cap\dots\cap A_n)\cap A_{n+1}}\\ &=\overline{A_1\cap A_2\cap\dots\cap A_n}\cup \overline{A_{n+1}}\\ &=\overline{A_1}\cup\overline{A_2}\cup\dots\cup\overline{A_n}\cup \overline{A_{n+1}} \end{aligned}\)

因此对于\(n+1\)的情况成立。

假设\(\overline{A_1\cup A_2\cup\dots\cup A_n}=\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_n}\)成立，考虑如下等式：

\(\begin{aligned} \overline{A_1\cup A_2\cup\dots\cup A_n\cup A_{n+1}}&=\overline{(A_1\cup A_2\cup\dots\cup A_n)\cup A_{n+1}}\\ &=\overline{A_1\cup A_2\cup\dots\cup A_n}\cap \overline{A_{n+1}}\\ &=\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_n}\cap \overline{A_{n+1}} \end{aligned}\)

因此对于\(n+1\)的情况同样也成立。

\(\star\) B.1-3

此处使用一个临时符号\(\mathbb{N}_n^+\)表示正整数集合\(\{1,2,3,\dots,n\}\)。

考虑使用数学归纳法证明这个定理。

当\(n=2\)时，容斥原理\(|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|\)成立。

当\(n>1\)时，假设\(n-1\)的情况成立，也就是有：

\(\displaystyle{\left |\bigcup_{i=1}^{n-1} A_i\right|=\sum_{S \subseteq \mathbb{N}_{n-1}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap_{i\in S}A_i\right|}\)

现在考虑证明\(n\)的情况，那么有

\(\begin{aligned} \left |\bigcup_{i=1}^{n} A_i\right|&=\left |\left(\bigcup_{i=1}^{n-1} A_i\right) \cup A_n\right|\\ &=\left |\bigcup_{i=1}^{n-1} A_i\right|+|A_n|-\left |\left(\bigcup_{i=1}^{n-1} A_i\right) \cap A_n\right|\\ &=\left |\bigcup_{i=1}^{n-1} A_i\right|+|A_n|-\left |\bigcup_{i=1}^{n-1} (A_i \cap A_n)\right|&\qquad(A)\\ &=\sum_{S \subseteq \mathbb{N}_{n-1}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap_{i\in S}A_i\right|+|A_n|-\sum_{S \subseteq \mathbb{N}_{n-1}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap_{i\in S\cup\{n\}}A_i\right|&\\ &=\sum_{S \subseteq \mathbb{N}_{n-1}^+,S\neq \varnothing}\left( (-1)^{|S|+1}\cdot \left|\bigcap_{i\in S}A_i\right|+ (-1)^{|S|+1+1}\cdot \left|\bigcap_{i\in S\cup\{n\}}A_i\right|\right) +|A_n|\\ &=\sum_{S \subseteq \mathbb{N}_{n}^+,S\neq \varnothing,S\neq \{n\}}\left( (-1)^{|S|+1}\cdot \left|\bigcap_{i\in S}A_i\right|\right) +|A_n|&\qquad(B)\\ &=\sum_{S \subseteq \mathbb{N}_{n}^+,S\neq \varnothing} (-1)^{|S|+1}\cdot \left|\bigcap_{i\in S}A_i\right| \end{aligned}\)

因此\(n\)的情况也成立。

其中，步骤\((A)\)使用了分配律，步骤\((B)\)则是将\(\mathbb{N}_{n-1}^{+}\)的所有非空子集，都添加上一个元素\(n\)后，和原来的\(\mathbb{N}_{n-1}^{+}\)的所有非空子集，共同组成\(\mathbb{N}_{n}^{+}\)的所有非空子集（除了集合\(\{n\}\)）。

B.1-4

假设奇数集合是\(O\)，那么定义一个从集合\(\mathbb{Z}\)到\(O\)的映射\(f(k)\)：

\(f(k)=2k+1\)

在集合\(\mathbb{Z}\)中的每个元素恰好能映射到\(O\)中的每个元素。由于集合\(\mathbb{Z}\)是可数的，因此集合\(O\)也是可数的。

B.1-5

对于一个集合\(S\)中的任何元素\(x\)，它在\(S\)的每一个子集中，都存在\(2\)个选择：出现在这个子集，或者是不出现在这个子集。

对于集合\(S\)中的\(|S|\)个元素，它们都有着平等的选择。只要存在一个元素的选择不一样，那么最终产生的子集也不一样。因此，\(S\)的幂集的大小为\(2^{|S|}\)。

B.1-6

当\(n=1\)时，元组\(b_1=(a_1)\)。

当\(n>1\)时，元组\(b_{n-1}=(a_1,a_2,\dots,a_{n-1})\)已经定义，在\(b_{n-1}\)后面再多添加一个元素\(a_n\)即可形成\(b_n\)，即

\(b_n=(b_{n-1},a_n)=((a_1,a_2,\dots,a_{n-1}),a_n)=(a_1,a_2,\dots,a_{n-1},a_n)\)