集合概念和表示法PPT课件.ppt-淘文阁

资源描述

《集合概念和表示法PPT课件.ppt》由会员分享，可在线阅读，更多相关《集合概念和表示法PPT课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第3章章集合集合关于集合的概念与表示法20.09.2022第一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.1 集合的概念与表示法集合的概念与表示法 3.1.1 集合的概念集合的概念集合作为数学的一个基本而又简单的原始概念，是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合，用小写字母(如a、b)表示集合中的元素。给定一个集合A和一个元素a，可以判定a是否在集合A中。如果a在A中，我们称a属于A，记为aA。否则，称a不属于A，记为aA。例如，某大学计算机系的全体学

2、生、所有自然数等都是集合。第二张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022由集合的概念可知，集合中的元素具有确定性、互异性、无序性和抽象性的特征。其中：(1)确定性是指：一旦给定了集合A，对于任意元素a，我们就可以准确地判定a是否在A中，这是明确的。(2)互异性是指：集合中的元素之间是彼此不同的。即集合a，b，b，c与集合a，b，c是一样的。(3)无序性是指：集合中的元素之间没有次序关系。即集合a，b，c与集合c，b，a是一样的。(4)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A1，2，1，2，其中1，2是集合A的元素。第三张，PPT共八十二页

3、，创作于2022年6月第第3章章集合集合 20.09.2022集合是多种多样的，我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数，记为|A|。当|A|有限时，称A为有限集合；否则，称A为无限集合。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。第四张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.1.2 集合的表示法集合的表示法表示一个集合通常有两种方法：列举法和谓词表示法。1.列举

4、法(或枚举法)列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。例如：Aa，b，c，B0，1，2，3，。列举法一般用于有限集合和有规律的无限集合。2.谓词表示法(或描述法)谓词表示法是用谓词来概括集合中元素的属性。通常用x|p(x)来表示具有性质p的一些对象组成的集合。例如：x|1x6x为整数为由1、2、3、4、5、6组成的集合。下面讨论集合之间的关系。第五张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.1.3 集合的包含与相等集合的包含与相等包含与相等是集合间的两种基本关系，也是集合论中的两个基本概念。两个集合相等是按照下述原理定义的。外延

5、性原理外延性原理两个集合A和B是相等的，当且仅当它们有相同的元素。记为AB。例如，若A2，3，B小于4的素数，则AB。定义定义3.13.1 设A和B为两个集合，若对于任意的aA必有aB，则称A是B的子集，也称A包含于B或B包含A，记作AB。如果B不包含A，记作AB。B包含A的符号化表示为：ABx(xAxB)。例如，若A1，2，3，4，B1，2，C2，3，则BA且CA，但CB。第六张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.1 3.1 集合A和B相等当且仅当这两个集合互为子集。即：ABABBA。证明证明若AB，则A和B具有相同的元素，于是x

6、(xAxB)、x(xBxA)都为真，即AB且BA。反之，若AB且BA，假设AB，则A与B元素不完全相同。不妨设有某个元素xA但xB，这与AB矛盾，所以AB。这个定理非常重要，是证明两个集合相等的基本思路和依据。第七张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.2 3.2 设A、B和C是三个集合，则：(1)AA。(2)ABBCAC。证明证明 (1)由定义显然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定义定义3.23.2 设A和B是两个集合，若AB且B中至少有一个元素b使得bA，则称A是B的真子集

7、，也称A真包含于B或B真包含A，记作AB。否则，记作AB。B真包含A的符号化表示：第八张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022ABx(xAxB)x(xBxA)。若两个集合A和B没有公共元素，我们说A和B是不相交的。例如，若Aa，b，c，d，Bb，c，则B是A的真子集，但A不是A的真子集。需要指出的是，与表示元素和集合的关系，而、与表示集合和集合的关系。例如，若A0，1，B0，1，0，1，则AB且AB。定理定理3.3 3.3 设A、B和C是三个集合，则(1)(AA)。(2)AB(BA)。(3)ABBCAC。第九张，PPT共八十二页，创作于2022年6月

8、第第3章章集合集合 20.09.2022证明证明仅证(2)和(3)(2)ABx(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xAxB)(x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(BA)。(3)ABBC(x(xAxB)x(xBxA)(x(xBxC)x(xCxB)x(xAxBxBxC)(x(xBxA)x(xCxB)x(xAxC)(x(xCxA)AC。第十张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.1.4 3.1.4 空集、集族、幂集和全集空集、集族、幂集和全集定义定义3.3 3.

9、3 没有任何元素的集合称为空集，记作。以集合为元素的集合称为集族。例如，x|xx是空集；xx是某大学的学生社团是集族。定理定理3.43.4 空集是任何集合的子集。证明证明任给集合A，则Ax(xxA)。由于x是假的，所以x(xxA)为真，于是有A为真。推论推论空集是惟一的。对于任一集合A，我们称空集和其自身A为A的平凡子集。第十一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022特别要注意与的区别，是不含任何元素的集合，是任意集合的子集，而是含有一个元素的集合。定义定义3.43.4 一个集合A的所有子集组成的集合称为A的幂集，记作P(A)或2A。例例1 1

10、求幂集P()、P()、P(，)、P(1，2，3)。解解 P()P()，P(，)，P(1，2，3)，1，2，3，1，2，3。第十二张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.53.5 若|A|n，则|P(A)|2n。证明证明因为A的m个元素的子集的个数为Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理定理3.6 3.6 设A和B是两个集合，则：(1)BP(A)BA。(2)ABP(A)P(B)。(3)P(A)P(B)AB。(4)P(A)P(B)AB。(5)P(A)P(B)P(AB)。(6)P(A)P(B)P(AB)。第十三张，PPT共八十二

11、页，创作于2022年6月第第3章章集合集合 20.09.2022定义定义3.53.5 所要讨论的集合都是某个集合的子集，称这个集合为全集，记作U或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题时，可把整个坐标平面取作全集。第十四张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.1.5 有限幂集元素的编码表示有限幂集元素的编码表示为便于在计算机中表示有限集，可对集合中的元素规定一种次序，在集合和二进制之间建立对应关系。设Ua1，a2，an，对U的任意子集A，A与一个

13、显然，AB是由A和B的公共元素组成的集合，AB由A和B的所有元素组成的集合。例如，若A1，2，3，B1，4，则AB1，AB1，2，3，4。集合的交与并可以推广到n个集合的情况，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn第十六张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例1 1 设A和B为两个集合，且AB，则ACBC。证明证明对任意的xAC，则有xA且xC。而AB，由xA得xB，则xB且xC，从而xBC。所以，ACBC。例例2 2 设A和B为两个集合，则ABABBABA。证明证明对任意的xAB，则xA或xB。又AB，所以x

14、B，于是ABB。又显然有BAB，故ABB。反之，若ABB，因AAB，所以AB。同理可证ABABA。第十七张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定义定义3.73.7 设A和B为两个集合，所有属于A而不属于B的元素组成的集合称为B对于A的补集，或相对补。记作ABx|xAxB。AB也称为A和B的差集。例如，若A1，2，3，B1，4，则AB2，3，BA4。定义定义3.83.8 设U为全集，集合A关于U的补集UA称为集合A的绝对补或余集，记为(或A或Ac)。即 x|xU且xA。例例3 3 设A和B为两个集合，则ABA 。证明证明因为xABxAxBxAx x

15、A，所以ABA 。第十八张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.73.7 对于任意3个集合A、B和C，其交、并、补满足下面10个定律：(1)幂等律 AAA，AAA(2)结合律(AB)CA(BC)，(AB)CA(BC)(3)交换律 ABBA，ABBA(4)分配律 A(BC)(AB)(AC)，A(BC)(AB)(AC)(5)同一律 AA，AUA第十九张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022(6)零律 AUU，A(7)互补律 A U，A (8)吸收律 A(AB)A，A(AB)A(9)德摩根律，A(B

16、C)(AB)(AC)，A(BC)(AB)(AC)(10)双重否定律 A以上等式的证明主要用到命题演算的等价式，即欲证集合AB，只需证明xAxB。也可利用已有的公式证明。第二十张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.83.8 任意集合A和B，B ABU且AB。证明证明如B ，则ABA U，ABA 。反之，若ABU且AB，则BBUB(A )(BA)(B )(B )(A )(B )(AB)U 。例例4 4 证明A(BC)(AB)(AC)。证明证明因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(A

17、B)(AC)，所以A(BC)(AB)(AC)。第二十一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例5 5 证明。证明证明因为x xABxAxBx x x ，所以。例例6 6 证明A(BC)(AB)(AC)。证明证明因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。第二十二张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例7 7 证明A(BC)(AB)(AC)。证明证明 A(BC)A(B )(AB)(AB )(AB)

18、()(AB)(AB)(AC)。例例8 8 已知ABAC，ABAC，试证BC。证明证明 BB(AB)B(AC)(BA)(BC)(AC)(BC)(AB)C(AC)CC。第二十三张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.2.2 集合的对称差集合的对称差定义定义3.93.9 集合A和B的对称差定义为AB(AB)(BA)。例如，若A0，0，则P(A)A(P(A)A)(AP(A)，0，0，0，0。定理定理3.9 3.9 设A、B和C为三个集合，则：(1)ABBA。(2)(AB)CA(BC)。(3)A(BC)(AB)(AC)。第二十四张，PPT共八十二页，创作

19、于2022年6月第第3章章集合集合 20.09.2022 (4)AA；AU；AA；AU。(5)AB(AB)(AB)。证明证明仅证(5)AB(AB)(BA)(A)(B)(A)B)(A)(AB)(B)(A)()(AB)()(AB)(AB)。第二十五张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.2.3 广义并、广义交运算广义并、广义交运算定义定义3.103.10 集合A的所有元素的元素组成的集合称为A的广义并。符号化表示为：Ax|B(BAxB)。定义定义3.11 3.11 集合A的所有元素的公共元素组成的集合称为A的广义交。符号化表示为：Ax|B(BA

20、xB)。例如，若Aa，b，c，a，d，e，a，f，则Aa，b，c，d，e，f，Aa。由定义可知，广义交和广义并是针对集族而言的，对于非集族来说，其广义交和广义并均为空集。第二十六张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.103.10设A和B为两个集合，则：(1)AA。(2)(AB)(A)(B)。证明证明 (1)因为xAB(BAxB)AAxAxA，所以AA(2)因为x(AB)C(CABxC)C(CACB)xC)C(CAxC)(CBxC)C(CAxC)C(CBxC)xAxBx(A)(B)，所以(AB)(A)(B)。第二十七张，PPT共八十二页，

21、创作于2022年6月第第3章章集合集合 20.09.2022定理定理3.11 3.11 设A和B为两个集合，则：(1)AA。(2)A，BAB。证明证明 (1)因为xAB(BAxB)AAxAxA，所以AA。(2)因为xA，BC(CA，BxC)(AA，BxA)(BA，BxB)xAxBxAB，所以A，BAB。第二十八张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.2.4 集合的文氏图集合的文氏图集合之间的相互关系和运算还可以用文氏图来描述，它有助于我们理解问题，有时对解题也很有帮助。在不要求有求解步骤的题目中，我们可以使用文氏图求解，但它不能用于题目的证明

22、。在文氏图中，用矩形表示全集U，矩形内部的点均为全集中的元素，用圆或椭圆表示U的子集，其内部的点表示不同集合的元素，并将运算结果得到的集合用阴影部分表示。图3-1表示了集合的5种基本运算，阴影部分表示经过相应运算得到的。第二十九张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022第三十张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.3 集合的划分与覆盖集合的划分与覆盖在集合的研究中，除了进行集合之间的比较外，还要对集合的元素进行分类。这一节将讨论集合的划分问题。定义定义3.123.12 设SA1，A2，An是集合A的某些

23、非空子集组成的集合，若 A，则称S为集合A的一个覆盖。定义定义3.133.13 设A1，A2，An是集合A的某些非空子集组成的集合，若 A，且AiAj(ij)，则称为A的一个划分，称中的元素为A的划分块。第三十一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022由定义知，划分一定是覆盖，但反之则不然。例如，Sa，b，c，c是Aa，b，c的覆盖，但不是A的划分。例1 设有整数集Z，res5(x)表示整数x被5除后所得的余数。令Aix|xZres5(x)iiZ5，则A0，A1，A2，A3，A4作成Z的一个划分。解由题设得：A0，10，5，0，5，10，A1，9，

24、4，1，6，11，A2，8，3，2，7，12，A3，7，2，3，8，13，A4，6，1，4，9，14，。于是，Z，且AiAj(ij)。所以，A0，A1，A2，A3，A4是Z的一个划分。第三十二张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例2 2 求集合Aa，b，c的所有不同的划分。解解其不同的划分共有5个：1a，b，c，2a，b，c，3a，c，b，4a，b，c，5a，b，c。定理定理3.123.12 设A1，A2，Ar和B1，B2，Bs是同一集合A的两种划分，则其所有AiBj组成的集合也是原集合的一种划分。定义定义3.143.14 设A1，A2，Ar

25、和B1，B2，Bs是同一集合A的两种划分，则称其所有AiBj组成的集合为原来两划分的交叉划分。第三十三张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定义定义3.153.15 给定A的两个划分A1，A2，Ar和B1，B2，Bs，若对于每个Aj都有Bk使得AjBk，则称A1，A2，Ar为B1，B2，Bs的加细。定理定理3.13 3.13 任何两种划分的交叉划分，都是原来各划分的一种加细。证明设A1，A2，Ar和B1，B2，Bs的交叉划分为T，对于T中任意元素AiBj必有AiBjAi和AiBjBj，故T必是原划分的加细。例例3 3 设A1、A2和A3是全集U的

26、子集，则形如 Ai(Ai为Ai或 )的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。第三十四张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022证明证明小项共8个，设有r个非空小项s1、s2、sr(r8)。对任意的aU，则aAi或a ，两者必有一个成立，取Ai为包含元素a的Ai或，则a Ai，即有a si，于是U si。又显然有 siU，所以U si。任取两个非空小项sp和sq，若spsq，则必存在某个Ai和分别出现在sp和sq中，于是spsq。综上可知，s1，s2，sr是U的一个划分。第三十五

27、张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.4 排列与组合排列与组合3.4.1 3.4.1 加法与乘法原理加法与乘法原理在组合计数的计算和研究中，加法原理和乘法原理是两个最常用也是最基本的原理。加法原理加法原理若事件的有限集合SS1S2Sn，且S1、S2、Sn两两不相交，则|S|S1|S2|Sn|乘法原理乘法原理若事件的有限集合S是依次取自有限集合S1、S2、Sn中事件的序列的集合，则|S|S1|S2|Sn|第三十六张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例1 1 求由数字1、2、3、4、5组成的小

28、于1000的数(每个数字都允许重复出现)的个数。解解在三位数中，每一个数位上的数字都有5种不同的选取法，由乘法原理知，满足条件的三位数的个数是53个。同理可知，满足条件的二位数和一位数的个数分别为52个和5个。再由加法原理知，满足条件的自然数总共有53525155个。第三十七张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.4.2 3.4.2 排列和组合排列和组合 1.1.排列排列定义定义3.16 3.16 集合S有n个元素，从中选取r个元素作有序排列，且在排列中不允许任何元素重复出现，则称这种排列为S的r无重复排列。当rn时，称其为全排列。S的所有r

29、无重复排列的个数记为P(n，r)或Pnr。定理定理3.143.14 n个元素的r无重复排列的个数为：P(n，r)n(n1)(n2)(nr1)。当rn时，P(n，n)n!证明证明在从n个不同的元素中按顺序取出r个元素时，第一个元素有n种不同的选法，第2个元素有n1种不同的选法，第r个元素从剩下的nr1个元素中选取，有nr1种不同的选法。根据乘法原理，顺序选取r个元素共有的不同选取方法数为：P(n，r)n(n1)(n2)(nr1)。第三十八张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例2 2 从1、2、9中选取数字构成3位数，如要求每个数字都不相同，问共

30、有多少种方法？解解从1、2、9中选取百位数，共9种选法，再从剩下的数字中选取十位数，共8种选法，最后从剩下的数字中选取个位数，共7种选法。因此，从1、2、9中选取数字构成3位数共有987504种方法。定义定义3.17 3.17 r无重复排列可以看作是将选出的r个元素排列在一条直线上的排列，这时也称为r线状排列。如果把这r个元素排列在一个圆周上，则这种排列称为S的r圆排列。对两个圆排列，若其中一个圆排列可以由另一个圆排列通过旋转而得到，则认为这两个圆排列在本质上是同一个圆排列。于是有下面的结论成立。第三十九张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022定理

31、定理3.15 3.15 n个元素的r圆排列的个数N(n，r)为证明证明为了得到n个元素的r无重复排列，可以先从n个元素中选取r个元素作r圆排列，这种圆排列的个数是N(n，r)。然后，将这个r圆排列断开后即可得到线状的r无重复排列。因为从r个不同的位置处断开，由乘法原理可得P(n，r)rN(n，r)，即例例3 3 有8个人围着圆桌进餐，如果要求每餐坐的顺序不同，那么他们在一起最多能共进几天餐？解解首先8圆排列数为8!/8，又一日三餐，故他们一起能共餐8!/(83)1680天。第四十张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20222.组合组合定义定义3.18

32、 3.18 集合S有n个元素，从中选取r个元素，若不考虑它们的排列顺序，且在选取中不允许元素重复出现，称这种选取方式为S的r无重复组合。S的所有r无重复组合的个数记为C(n，r)或Cnr。定理3.16 n个元素的r无重复组合的个数为C(n，r)。证明为了得到n个元素的r无重复排列，可以先从n个元素中选取r个元素作r无重复组合，这种无重复组合的个数是C(n，r)，然后将这r个取出的元素作r无重复排列，这种r无重复排列的个数是P(r，r)r!。由乘法原理可得P(n，r)r!C(n，r)，即C(n，r)。第四十一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例

33、例4 4 从1、2、300之中任取3个数，使得它们的和能被3整除，问有多少种方法？解解把1、2、300分成A、B和C三组，A3k1|kZ，B3k2|kZ，C3k|kZ。任取三个数i、j、k，那么选取是无序的且满足ijk能被3整除。将选法分为两类：都取自同一组，方法数3C(100，3)。分别取自A、B和C，方法数(C(100，1)3。由加法原则，总取数为3C(100，3)(C(100，1)31485100。第四十二张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.4.3 3.4.3 排列与组合的生成排列与组合的生成 1.排列的生成排列的生成算法有词典顺序

34、法、逆序法和递归排序法等。在这里仅介绍词典顺序法。设S1，2，n，(a1，a2，an)和(b1，b2，bn)是S的两个排列，若存在i1，2，n，使得对一切j1，2，i有ajbj而ai1bi1，则称排列(a1，a2，an)字典序小于(b1，b2，bn)，并记为(a1，a2，an)(b1，b2，bn)。若(a1，a2，an)(b1，b2，bn)，且不存在异于(a1，a2，an)和(b1，b2，bn)的排列(c1，c2，cn)，使得(a1，a2，an)(c1，c2，cn)(b1，b2，bn)，则称(b1，b2，bn)为(a1，a2，an)的下一个排列。第四十三张，PPT共八十二页，创作于2022年6

35、月第第3章章集合集合 20.09.2022定理3.17 对S的两个排列，(b1，b2，bn)是(a1，a2，an)的下一个排列的充要条件是：(1)存在m1，2，n，使得对一切i1，2，m1有aibi，ambm，amam1且am1am2an；(2)bmminaj|ajam，jm1，m2，n；(3)bm1bm2bn。由此定理可建立生成所有排列的算法：步1：置(a1，a2，an)(1，2，n)步2：设已有排列(a1，a2，an)，置in；步2.1：若aiai1，则记mi1，令bmminaj|ajam，ji，i1，n，并将(am，am1，an)bm第四十四张，PPT共八十二页，创作于2022年6月第

36、第3章章集合集合 20.09.2022中的元素由小到大排起来，记这个排列为(bm1，am2，an)。置(a1，a2，am1，am，am1，an)(a1，a2，am1，bm，bm1，bn)然后返回步2。步2.2：若aiai1，则当i11时，置ii1，返回步2.1。当i11时，算法终止。例5 S1，2，3，4，求其全排列。解 123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321。第四十五张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.0

37、9.20222.2.组合的生成组合的生成定理定理3.183.18 (a1，a2，ar)和(b1，b2，br)是S的两个不同的r子集，则(b1，b2，br)是(a1，a2，ar)的下一个子集的充要条件是：(1)存在1mr，使得对一切i1，2，m1有aibi，对一切im有amnri；(2)bmam1；(3)对于mjr1，有bj1bj1。由此定理可建立生成所有子集的算法：步1：设S1，2，n，取(a1，a2，ar)(1，2，r)第四十六张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022步2：设已有S的r子集(a1，a2，ar)，置ir；步2.1：若ainri，则令b

38、iai1，并且对ji，i1，r1，置bj1bj1。然后置(a1，a2，ar)(a1，a2，ai1，bi，bi1，br)，然后返回步2。步2.2：若ainri，则当i1时，置ii1，返回步2.1。当i1时，算法终止。例例6 6 S1，2，3，4，5，6，求其所有4元素子集。解解 123412351236124512461256134513461356145623452346235624563456。第四十七张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.5 归纳原理归纳原理 3.5.1 3.5.1 结构归纳原理结构归纳原理设集合A是归纳定义的集合，现欲证

39、A中所有元素具有性质P，即证：对于任意xA有P(x)为真。可进行如下证明：(1)(归纳基础)证明归纳定义基础条款中规定的A的基本元素x均使P(x)为真。(2)(归纳推理)证明归纳定义的归纳条款是“保性质P的”。即在假设归纳条款中已确定元素x1、x2、xn使P(xi)(i1，2，n)真的前提下，证明用归纳条款中的操作g所生成元素g(x1，x2，xn)依然具有性质P，即P(g(x1，x2，xn)为真。第四十八张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022由于A仅由(1)和(2)条款所确定的元素组成，因此当上述证明过程完成时，“A中所有元素具有性质P”得证。这种

40、推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法。为区别通常所说的数学归纳法，它又称为“结构归纳法”。数学归纳法是其一种特例。第四十九张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.5.2 3.5.2 数学归纳原理数学归纳原理将上述原理应用到自然数集上进行归纳推理，就是我们所说的数学归纳法。1.1.第一数学归纳法第一数学归纳法用第一数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(0)，假设P(k)真(归纳假设“k满足性质P”)时，推出P(k1)真。(3)结论：

41、所有自然数具有性质P。第五十张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例1 1 用归纳法证明：对任意的自然数n，有(012n)2031323n3。证明证明当n0时，n203。假设nk时，(012k)2031323k3，那么nk1时，(012kk1)2(012k)22(012k)(k1)(k1)2 031323k3k(k1)2(k1)2031323k3(k1)3所以，对任意自然数结论成立。第五十一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20222.2.第二数学归纳法第二数学归纳法用第二数学归纳法证明所有自然数具有性

42、质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(0)，假设P(i)真，ki0(归纳假设“0，1，k1满足性质P”)时，推出P(k)真。(3)结论：所有自然数具有性质P。例例2 2 有数目相同的两堆棋子(每堆棋子数为n)，甲、乙两人玩取棋子游戏。规定两人轮流取棋子，每次两人取子数相同，不能不取，也不能同时在两堆中取子，取得最后一枚棋子者为胜者。求证：后取者必胜。第五十二张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022证明证明不妨设甲为先取者，乙为后取者。当n1时，两堆各有一枚棋子，甲必先从一堆中取走一枚棋子

43、，余下最后一枚棋子必被乙取走，乙胜。假设nk时乙必胜。下证nk时也是乙必胜。设第一轮取子时，甲从一堆中取走r枚棋子，余下krk枚棋子，那么，乙从另一堆中也取走r枚棋子，亦留下krk枚棋子。若(1)rk，那么乙取走最后一枚棋子，乙胜。(2)1rk，那么1krk。对留下的两堆棋子，每一堆为kr枚，由归纳假设，在以后甲乙的搏奕中乙必胜。因此全局也是乙必胜。第五十三张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.6 容斥原理和抽屉原理容斥原理和抽屉原理 3.6.1 3.6.1 容斥原理容斥原理设集合A是归纳定义的集合，现欲证A中所有元素具有性质P，即证：对于任

44、意xA有P(x)为真。可进行如下证明：(1)(归纳基础)证明归纳定义基础条款中规定的A的基本元素x均使P(x)为真。(2)(归纳推理)证明归纳定义的归纳条款是“保性质P的”。即在假设归纳条款中已确定元素x1、x2、xn使P(xi)(i1，2，n)真的前提下，证明用归纳条款中的操作g所生成元素g(x1，x2，xn)依然具有性质P，即P(g(x1，x2，xn)为真。第五十四张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022集合的运算，可用于有限个元素的计数问题。在有限集的元素计数问题中，容斥原理有着广泛的应用。定理定理3.19(3.19(容斥原理容斥原理)对有限集

45、合A和B，有|AB|A|B|AB|。证明因为ABB(AB)且B(AB)，所以|AB|B|AB|。又因为A(AB)(AB)且(AB)(AB)，所以|A|AB|AB|。故|AB|A|B|AB|。定理定理3.20 3.20 推广到n个集合A1，A2，An的情形，有：|A1A2An|i|Ai|ij|AiAj|ijk|AiAjAk|(1)n1|A1A2An|。第五十五张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例1 1 一个班有50个学生，在第一次考试中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得

46、95分的有多少人？解解设A和B分别表示在第一次和第二次考试中得95分的学生的集合。则：|A|26，|B|21，17。于是 50 50(|A|B|AB|)，从而|AB|50|A|B|1750262114。所以，两次考试都得95分的有14人。例例2 2 从1，2，3，4，5，6，7，8，9中取7个不同的数字构成7位数，如不允许5和6相邻，总共有多少种方法？第五十六张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022解解任取7个不同的数字构成7位数的个数为 9!/2，5和6相邻的个数为6！(2！)67！，根据容斥原理，总共有9!/267!151200种方法。例例3

47、 3 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：第五十七张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022|A|12，|B|6，|C|14，|AC|6，|BC|=5,|ABC|2，|(AC)B|6。因为|(AC)B|(AB)(BC)|(AB)|(BC)|ABC|(AB)|526，所以|(AB)|3。于是|ABC|12614653220，25205。故，不会打这三种球的

48、共5人。在不要求严格步骤的情况下，以上各题也可通过文氏图的方法来求解。下面以例3加以说明：设A、B、C分别表示会打排球、网球和篮球的学生集合。该问题的文氏图如图3-2所示。由题意可得：第五十八张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022|I2|I3|I4|I5|12|I4|I5|I6|I7|6|I1|I2|I5|I6|14|I2|I5|6|I5|I6|5|I5|2|I4|I5|I6|6根据上面各等式，依次求得：第五十九张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022|I1|5，|I2|4，|I3|5，|I4|1，|I5

49、|2，|I6|3，|I7|0。所以，25|ABC|25(|I1|I2|I3|I4|I5|I6|I7|)25(5451230)5。故，不会打这三种球的共5人。第六十张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.20223.6.2 3.6.2 抽屉原理抽屉原理(鸽巢原理鸽巢原理)抽屉原理是一个十分基本、非常重要、应用极其广泛的数学原理，是解决数学中的一类存在性问题的基本工具。定理定理3.213.21(抽屉原理)(1)把多于n个元素的集合S分成n个子集S1、S2、Sn的并集，那么至少存在一个集合Si，它包含S中的两个或两个以上的元素。(2)把多于mn个元素的集合S分成n

50、个子集S1、S2、Sn的并集，那么至少存在一个集合Si，它包含S中的m1或m1以上的元素。证明仅证(2),反证法。(2)若结论不成立，则对于任意子集Si，有|Si|m，于是|S|S1|S2|Sn|mn，矛盾。第六十一张，PPT共八十二页，创作于2022年6月第第3章章集合集合 20.09.2022例例3 3 在从1到2n的整数中，任意选取n1个数，证明在这n1个数中总存在两个数，使得其中一个数是另一个的倍数。证明证明设S1，2，2n，Sia|aS，且存在kN使得a2k(2i1)，i1，2，n。于是SS1S2Sn，则n1个数中必有两个数在S的同一个子集Si中，这两个数中的一个数是另一个的偶

展开阅读全文