作业帮 > 数学 > 作业

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

来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/07/18 19:31:07
离散数学题:若|X|=n,则|P(X)|=2^n 乘法原理证明
离散数学题:若|X|=n,则|P(X)|=2^n 乘法原理证明
证明:设 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