算法导论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)\)