Question

离散数学题：若|X|=n,则|P(X)|=2^n 乘法原理证明

Answer 1

证明： 设 B = {1, 2, 3, · · · , s − 1}， A = {1, 2, 3, · · · , s}. 可知A 比B 多一个元素S，所以A 的子集中不含有s的个数为|P(B)|. 其它A的子集必然含有s，移除s,我们会得到一个B的子集。所以A 的子集中含有s的个数也为|P(B)|. 因为 每一个A的子集要不就含有要不就不含有s。 显然这样的子集共有2|P(B)|. 我们可以得出结论如果如果A比B多一个元素,|P(A)| = 2|P(B)|. 更有，,|P(空集)|
=1， 显然，如果|X|=n, 则 |P(X)| = 2^n。
证毕。
,

追问

用乘法原理咋证呀？

追答

这就是乘法原理啊。|P(A)| = 2|P(B)| 多一个元素就乘2. 空集是1.n=1 就是2 n=2 就是2*2. n=n 就是 2^n