集合论习题解析.pptVIP

容斥原理解题总结使用容斥原理时，首先搞清论域，划定全集；其次对全集进行分类，列出计算式；最后根据容斥原理的公式进行计算。第61页，共126页，星期日，2025年，2月5日北京师范大学2001证明容斥原理：设A1,A2,……,An都是有限集，则|A1?A2?……?An|=其中：{i1,i2,…in}是遍历{1,2,…,n}的所有k元子集。/*证明思想：数学归纳法*/第62页，共126页，星期日，2025年，2月5日证明：1）归纳基础：当k=2时，集合A1和A2的公共元素个数为|A1?A2|，这些元素中的每一个在|A1|+|A2|里计算了两次，但在|A1?A2|中是作为一个元素计算的。因此有|A1?A2|=|A1|+|A2|-|A1?A2|。所以，当n=2时，命题成立。第63页，共126页，星期日，2025年，2月5日2）归纳步骤：第64页，共126页，星期日，2025年，2月5日当k=n时，|A1?A2?……?An|=|(A1?A2?……?An-1)?An|=|(A1?A2?……?An-1)|+|An|-|(A1?A2?……?An-1)?An|因为|(A1?A2?……?An-1)?An|=|(A1?An)?(A2?An)?……?(An-1?An)|/*n-1个集合的并，根据归纳假设展开*/第65页，共126页，星期日，2025年，2月5日北京师范大学2000设S为任一集合，证明在S与其幂集P(S)之间不存在1-1对应。第66页，共126页，星期日，2025年，2月5日1.2集合运算——证明基本法、公式法第67页，共126页，星期日，2025年，2月5日中国科学院软件所19981对于任意集合A和B，证明:(1)P(A)?P(B)?P(A?B),(2)P(A)?P(B)=P(A?B)；并举例说明P(A)?P(B)?P(A?B)。/*幂集的定义：P(A)={x|x?A}*/第68页，共126页，星期日，2025年，2月5日（1）/*基本法*/对任意的x?P(A)?P(B)，有x?P(A)或x?P(B)。若x?P(A)，则x?A，所以x?A?B，即x?P(A?B)；同理，若x?P(B)，则x?B，所以x?A?B，即x?P(A?B)。综上所述，P(A)?P(B)?P(A?B)。第69页，共126页，星期日，2025年，2月5日（2）/*基本法*/对任意的x?P(A)?P(B)，有x?P(A)且x?P(B)。即x?A并且x?B，则x?A?B。所以x?P(A?B)。故P(A)?P(B)?P(A?B)。对任意的x?P(A?B)，有x?A?B，即x?A并且x?B，所以x?P(A)且x?P(B)。因此P(A?B)?P(A)?P(B)。综上所述，P(A)?P(B)=P(A?B)。第70页，共126页，星期日，2025年，2月5日举例说明P(A)?P(B)?P(A?B)。A={1},B={2},A?B={1,2};P(A)={?,{1}},P(B)={?,{2}},P(A)?P(B)={?,{1},{2}},P(A?B)={?,{1},{2},{1,2}};所以P(A)?P(B)?P(A?B)。第71页，共126页，星期日，2025年，2月5日中国科学院计算所19982证明：若(A-B)?(B-A)=C，则A?(B-C)?(C-B)的充分必要条件是A?B?C=?。证明思想：（1）充分性，即证明：若A?B?C=?，则A?(B-C)?(C-B)；基本法证明；（2）必要性，即证明：若A?(B-C)?(C-B)，则A?B?C=?；反证法证明。第72页，共126页，星期日，2025年，2月5日证明：（1）对于任意的a?A，因为A?B?C=?，所以a?B?C，则a有3种情况：I)a?B，但a?C，则a?C-B，所以a?(B-C)?(C-B)；II)a?B，但a?C，则a?B-C，所以a?(B-C)?(C-B)；III)a?B且a?C，因为a?A，所以a?A-B，所以a?(A-B)?(B-A)，即a?C，导致矛盾，所以a?B且a?C不可能出现。综上所述，对于任意的a?A，a?(A-B)?(B-A)，所以A?(B-C)?(