集合的概念与表示法课件.ppt

《集合的概念与表示法课件.ppt》由会员分享，可在线阅读，更多相关《集合的概念与表示法课件.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 集合集合 关于集合的概念与表示法11.04.2023第1页，此课件共82页哦第第3章章 集合集合 11.04.20233.1 集合的概念与表示法集合的概念与表示法 3.1.1 集合的概念集合的概念 集合作为数学的一个基本而又简单的原始概念，是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合，用小写字母(如a、b)表示集合中的元素。给定一个集合A和一个元素a，可以判定a是否在集合A中。如果a在A中，我们称a属于A，记为aA。否则，称a不属于A，记为aA。例如，某大学计算机系的全体学生、所有自然数等都是集

2、合。第2页，此课件共82页哦第第3章章 集合集合 11.04.2023由集合的概念可知，集合中的元素具有确定性、互异性、无序性和抽象性的特征。其中：(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的元素。第3页，此课件共82页哦第第3章章 集合集合 11.04.2023集

3、合是多种多样的，我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数，记为|A|。当|A|有限时，称A为有限集合；否则，称A为无限集合。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。第4页，此课件共82页哦第第3章章 集合集合 11.04.20233.1.2 集合的表示法集合的表示法 表示一个集合通常有两种方法：列举法和谓词表示法。1.列举法(或枚举法)列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。例如：Aa，b

4、，c，B0，1，2，3，。列举法一般用于有限集合和有规律的无限集合。2.谓词表示法(或描述法)谓词表示法是用谓词来概括集合中元素的属性。通常用x|p(x)来表示具有性质p的一些对象组成的集合。例如：x|1x6x为整数为由1、2、3、4、5、6组成的集合。下面讨论集合之间的关系。第5页，此课件共82页哦第第3章章 集合集合 11.04.20233.1.3 集合的包含与相等集合的包含与相等 包含与相等是集合间的两种基本关系，也是集合论中的两个基本概念。两个集合相等是按照下述原理定义的。外延性原理外延性原理 两个集合A和B是相等的，当且仅当它们有相同的元素。记为AB。例如，若A2，3，B小于4的素数

5、，则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。第6页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理3.1 3.1 集合A和B相等当且仅当这两个集合互为子集。即：ABABBA。证明证明 若AB，则A和B具有相同的元素，于是x(xAxB)、x(xBxA)都为真，即AB且BA。反之，若AB且BA，假设AB，则A与B元素不完全相同。不妨设有某个元素xA但xB，

6、这与AB矛盾，所以AB。这个定理非常重要，是证明两个集合相等的基本思路和依据。第7页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理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的真子集，也称A真包含于B或B真包含A，记作AB。否则，记作AB。B真包含A的符号化表示：第8页，此课件共82页哦第第3章章 集合集合 11.04.2023ABx

7、(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。第9页，此课件共82页哦第第3章章 集合集合 11.04.2023证明证明 仅证(2)和(3)(2)ABx(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xAxB)(x(

8、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。第10页，此课件共82页哦第第3章章 集合集合 11.04.20233.1.4 3.1.4 空集、集族、幂集和全集空集、集族、幂集和全集定义定义3.3 3.3 没有任何元素的集合称为空集，记作。以集合为元素的集合称为集族。例如，x|xx是空集；xx是某大学的学生社团是集族。定理定理3.43.4 空集是任何集合的子集。证明证明 任给集合A，则Ax(xxA)。由于x是假的，所

9、以x(xxA)为真，于是有A为真。推论推论 空集是惟一的。对于任一集合A，我们称空集和其自身A为A的平凡子集。第11页，此课件共82页哦第第3章章 集合集合 11.04.2023特别要注意与的区别，是不含任何元素的集合，是任意集合的子集，而是含有一个元素的集合。定义定义3.43.4 一个集合A的所有子集组成的集合称为A的幂集，记作P(A)或2A。例例1 1 求幂集P()、P()、P(，)、P(1，2，3)。解解 P()P()，P(，)，P(1，2，3)，1，2，3，1，2，3。第12页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理3.53.5 若|A|n，则|P(A)|2

10、n。证明证明 因为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)。第13页，此课件共82页哦第第3章章 集合集合 11.04.2023定义定义3.53.5 所要讨论的集合都是某个集合的子集，称这个集合为全集，记作U或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题

11、时，可把整个坐标平面取作全集。第14页，此课件共82页哦第第3章章 集合集合 11.04.20233.1.5 有限幂集元素的编码表示有限幂集元素的编码表示 为便于在计算机中表示有限集，可对集合中的元素规定一种次序，在集合和二进制之间建立对应关系。设Ua1，a2，an，对U的任意子集A，A与一个n位二进制数b1b2bn对应，其中bi1当且仅当aiA。对于一个n位二进制数b1b2bn，使之对应一个集合Aai|bi1。例如，若Aa，b，c，则A的幂集为P(A)Ai|iJ，其中Ji|i是二进制数且000i111，其中A000，A011b，c等。一般地P(A)Ai|iJ，其中Ji|i是二进制数且 i 。

12、第15页，此课件共82页哦第第3章章 集合集合 11.04.20233.2 集合的运算与性质集合的运算与性质 3.2.1 集合的交、并、补集合的交、并、补 定义定义3.63.6 设A和B为两个集合，A和B的交集AB、并集AB分别定义如下：ABx|xAxBABx|xAxB 显然，AB是由A和B的公共元素组成的集合，AB由A和B的所有元素组成的集合。例如，若A1，2，3，B1，4，则AB1，AB1，2，3，4。集合的交与并可以推广到n个集合的情况，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn第16页，此课件共82页哦第第3章章 集合集合 11.04.2023例例1 1 设

13、A和B为两个集合，且AB，则ACBC。证明证明 对任意的xAC，则有xA且xC。而AB，由xA得xB，则xB且xC，从而xBC。所以，ACBC。例例2 2 设A和B为两个集合，则ABABBABA。证明证明 对任意的xAB，则xA或xB。又AB，所以xB，于是ABB。又显然有BAB，故ABB。反之，若ABB，因AAB，所以AB。同理可证ABABA。第17页，此课件共82页哦第第3章章 集合集合 11.04.2023定义定义3.73.7 设A和B为两个集合，所有属于A而不属于B的元素组成的集合称为B对于A的补集，或相对补。记作ABx|xAxB。AB也称为A和B的差集。例如，若A1，2，3，B1，4

14、，则AB2，3，BA4。定义定义3.83.8 设U为全集，集合A关于U的补集UA称为集合A的绝对补或余集，记为(或A或Ac)。即 x|xU且xA。例例3 3 设A和B为两个集合，则ABA 。证明证明 因为xABxAxBxAx xA，所以ABA 。第18页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理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，A

15、UA第19页，此课件共82页哦第第3章章 集合集合 11.04.2023(6)零律 AUU，A(7)互补律 A U，A (8)吸收律 A(AB)A，A(AB)A(9)德摩根律 ，A(BC)(AB)(AC)，A(BC)(AB)(AC)(10)双重否定律 A以上等式的证明主要用到命题演算的等价式，即欲证集合AB，只需证明xAxB。也可利用已有的公式证明。第20页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理3.83.8 任意集合A和B，B ABU且AB。证明证明 如B ，则ABA U，ABA 。反之，若ABU且AB，则BBUB(A )(BA)(B )(B )(A )(B )(

16、AB)U 。例例4 4 证明A(BC)(AB)(AC)。证明证明 因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。第21页，此课件共82页哦第第3章章 集合集合 11.04.2023例例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)。第22页，此课件共82页哦第第3章章 集合集合 11.

17、04.2023例例7 7 证明A(BC)(AB)(AC)。证明证明 A(BC)A(B )(AB)(AB )(AB)()(AB)(AB)(AC)。例例8 8 已知ABAC，ABAC，试证BC。证明证明 BB(AB)B(AC)(BA)(BC)(AC)(BC)(AB)C(AC)CC。第23页，此课件共82页哦第第3章章 集合集合 11.04.20233.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)

18、(AB)CA(BC)。(3)A(BC)(AB)(AC)。第24页，此课件共82页哦第第3章章 集合集合 11.04.2023 (4)AA；AU；AA；AU。(5)AB(AB)(AB)。证明证明 仅证(5)AB(AB)(BA)(A)(B)(A)B)(A)(AB)(B)(A)()(AB)()(AB)(AB)。第25页，此课件共82页哦第第3章章 集合集合 11.04.20233.2.3 广义并、广义交运算广义并、广义交运算 定义定义3.103.10 集合A的所有元素的元素组成的集合称为A的广义并。符号化表示为：Ax|B(BAxB)。定义定义3.11 3.11 集合A的所有元素的公共元素组成的集合称

19、为A的广义交。符号化表示为：Ax|B(BAxB)。例如，若Aa，b，c，a，d，e，a，f，则Aa，b，c，d，e，f，Aa。由定义可知，广义交和广义并是针对集族而言的，对于非集族来说，其广义交和广义并均为空集。第26页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理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)。第27页，此

20、课件共82页哦第第3章章 集合集合 11.04.2023定理定理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。第28页，此课件共82页哦第第3章章 集合集合 11.04.20233.2.4 集合的文氏图集合的文氏图 集合之间的相互关系和运算还可以用文氏图来描述，它有助于我们理解问题，有时对解题也很有帮助。在不要求有求解步骤的题目中，我们可以使用文氏图求解，但它不能用于题目的证明。在文氏图中，用矩形表示全集U

21、，矩形内部的点均为全集中的元素，用圆或椭圆表示U的子集，其内部的点表示不同集合的元素，并将运算结果得到的集合用阴影部分表示。图3-1表示了集合的5种基本运算，阴影部分表示经过相应运算得到的。第29页，此课件共82页哦第第3章章 集合集合 11.04.2023第30页，此课件共82页哦第第3章章 集合集合 11.04.20233.3 集合的划分与覆盖集合的划分与覆盖 在集合的研究中，除了进行集合之间的比较外，还要对集合的元素进行分类。这一节将讨论集合的划分问题。定义定义3.123.12 设SA1，A2，An是集合A的某些非空子集组成的集合，若 A，则称S为集合A的一个覆盖。定义定义3.133.1

22、3 设A1，A2，An是集合A的某些非空子集组成的集合，若 A，且AiAj(ij)，则称为A的一个划分，称中的元素为A的划分块。第31页，此课件共82页哦第第3章章 集合集合 11.04.2023由定义知，划分一定是覆盖，但反之则不然。例如，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，4，1，6，11，A2，8，3，2，7，12，A3，7，2，3，8，13，A4，6，1，4，9，14

23、，。于是，Z，且AiAj(ij)。所以，A0，A1，A2，A3，A4是Z的一个划分。第32页，此课件共82页哦第第3章章 集合集合 11.04.2023例例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和B1，B2，Bs是同一集合A的两种划分，则称其所有AiBj组成的集合为原来两划分的交叉划分。第33页，此课件共82页哦第第

24、3章章 集合集合 11.04.2023定义定义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的子集，则形如 Ai(Ai为Ai或 )的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。第

25、34页，此课件共82页哦第第3章章 集合集合 11.04.2023证明证明 小项共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的一个划分。第35页，此课件共82页哦第第3章章 集合集合 11.04.20233.4 排列与组合排列与组合3.4.1 3.4.1 加法与乘法原理加法与乘法原理 在组合计数的计算和研究中，加法

26、原理和乘法原理是两个最常用也是最基本的原理。加法原理加法原理 若事件的有限集合SS1S2Sn，且S1、S2、Sn两两不相交，则|S|S1|S2|Sn|乘法原理乘法原理 若事件的有限集合S是依次取自有限集合S1、S2、Sn中事件的序列的集合，则|S|S1|S2|Sn|第36页，此课件共82页哦第第3章章 集合集合 11.04.2023例例1 1 求由数字1、2、3、4、5组成的小于1000的数(每个数字都允许重复出现)的个数。解解 在三位数中，每一个数位上的数字都有5种不同的选取法，由乘法原理知，满足条件的三位数的个数是53个。同理可知，满足条件的二位数和一位数的个数分别为52个和5个。再由加法

27、原理知，满足条件的自然数总共有53525155个。第37页，此课件共82页哦第第3章章 集合集合 11.04.20233.4.2 3.4.2 排列和组合排列和组合 1.1.排列排列 定义定义3.16 3.16 集合S有n个元素，从中选取r个元素作有序排列，且在排列中不允许任何元素重复出现，则称这种排列为S的r无重复排列。当rn时，称其为全排列。S的所有r无重复排列的个数记为P(n，r)或Pnr。定理定理3.143.14 n个元素的r无重复排列的个数为：P(n，r)n(n1)(n2)(nr1)。当rn时，P(n，n)n!证明证明 在从n个不同的元素中按顺序取出r个元素时，第一个元素有n种不同的选

28、法，第2个元素有n1种不同的选法，第r个元素从剩下的nr1个元素中选取，有nr1种不同的选法。根据乘法原理，顺序选取r个元素共有的不同选取方法数为：P(n，r)n(n1)(n2)(nr1)。第38页，此课件共82页哦第第3章章 集合集合 11.04.2023例例2 2 从1、2、9中选取数字构成3位数，如要求每个数字都不相同，问共有多少种方法？解解 从1、2、9中选取百位数，共9种选法，再从剩下的数字中选取十位数，共8种选法，最后从剩下的数字中选取个位数，共7种选法。因此，从1、2、9中选取数字构成3位数共有987504种方法。定义定义3.17 3.17 r无重复排列可以看作是将选出的r个元素

29、排列在一条直线上的排列，这时也称为r线状排列。如果把这r个元素排列在一个圆周上，则这种排列称为S的r圆排列。对两个圆排列，若其中一个圆排列可以由另一个圆排列通过旋转而得到，则认为这两个圆排列在本质上是同一个圆排列。于是有下面的结论成立。第39页，此课件共82页哦第第3章章 集合集合 11.04.2023定理定理3.15 3.15 n个元素的r圆排列的个数N(n，r)为证明证明 为了得到n个元素的r无重复排列，可以先从n个元素中选取r个元素作r圆排列，这种圆排列的个数是N(n，r)。然后，将这个r圆排列断开后即可得到线状的r无重复排列。因为从r个不同的位置处断开，由乘法原理可得P(n，r)rN(

30、n，r)，即例例3 3 有8个人围着圆桌进餐，如果要求每餐坐的顺序不同，那么他们在一起最多能共进几天餐？解解 首先8圆排列数为8!/8，又一日三餐，故他们一起能共餐8!/(83)1680天。第40页，此课件共82页哦第第3章章 集合集合 11.04.20232.组合组合定义定义3.18 3.18 集合S有n个元素，从中选取r个元素，若不考虑它们的排列顺序，且在选取中不允许元素重复出现，称这种选取方式为S的r无重复组合。S的所有r无重复组合的个数记为C(n，r)或Cnr。定理3.16 n个元素的r无重复组合的个数为C(n，r)。证明 为了得到n个元素的r无重复排列，可以先从n个元素中选取r个元素

31、作r无重复组合，这种无重复组合的个数是C(n，r)，然后将这r个取出的元素作r无重复排列，这种r无重复排列的个数是P(r，r)r!。由乘法原理可得P(n，r)r!C(n，r)，即C(n，r)。第41页，此课件共82页哦第第3章章 集合集合 11.04.2023例例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。由

32、加法原则，总取数为3C(100，3)(C(100，1)31485100。第42页，此课件共82页哦第第3章章 集合集合 11.04.20233.4.3 3.4.3 排列与组合的生成排列与组合的生成 1.排列的生成 排列的生成算法有词典顺序法、逆序法和递归排序法等。在这里仅介绍词典顺序法。设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

33、，a2，an)和(b1，b2，bn)的排列(c1，c2，cn)，使得(a1，a2，an)(c1，c2，cn)(b1，b2，bn)，则称(b1，b2，bn)为(a1，a2，an)的下一个排列。第43页，此课件共82页哦第第3章章 集合集合 11.04.2023定理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

34、，n)步2：设已有排列(a1，a2，an)，置in；步2.1：若aiai1，则记mi1，令bmminaj|ajam，ji，i1，n，并将(am，am1，an)bm第44页，此课件共82页哦第第3章章 集合集合 11.04.2023中的元素由小到大排起来，记这个排列为(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，求其全排列。解 123412431324134214231432213421432314234124

35、132431312431423214324134123421412341324213423143124321。第45页，此课件共82页哦第第3章章 集合集合 11.04.20232.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)第46页

36、，此课件共82页哦第第3章章 集合集合 11.04.2023步2：设已有S的r子集(a1，a2，ar)，置ir；步2.1：若ainri，则令biai1，并且对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。第47页，此课件共82页哦第第3章章 集合集合 11.04

37、.20233.5 归纳原理归纳原理 3.5.1 3.5.1 结构归纳原理结构归纳原理 设集合A是归纳定义的集合，现欲证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)为真。第48页，此课件共82页哦第第3章章 集合集合 11.04.2023由于A仅由(1

38、)和(2)条款所确定的元素组成，因此当上述证明过程完成时，“A中所有元素具有性质P”得证。这种推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法。为区别通常所说的数学归纳法，它又称为“结构归纳法”。数学归纳法是其一种特例。第49页，此课件共82页哦第第3章章 集合集合 11.04.20233.5.2 3.5.2 数学归纳原理数学归纳原理 将上述原理应用到自然数集上进行归纳推理，就是我们所说的数学归纳法。1.1.第一数学归纳法第一数学归纳法 用第一数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(0)，假设P

39、(k)真(归纳假设“k满足性质P”)时，推出P(k1)真。(3)结论：所有自然数具有性质P。第50页，此课件共82页哦第第3章章 集合集合 11.04.2023例例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所以，对任意自然数结论成立。第51页，此课件共82页哦第第3章章 集合集合 11.04.20232.2.第二数学归纳法第二数学归纳法用第二数学归

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

41、，余下最后一枚棋子必被乙取走，乙胜。假设nk时乙必胜。下证nk时也是乙必胜。设第一轮取子时，甲从一堆中取走r枚棋子，余下krk枚棋子，那么，乙从另一堆中也取走r枚棋子，亦留下krk枚棋子。若(1)rk，那么乙取走最后一枚棋子，乙胜。(2)1rk，那么1krk。对留下的两堆棋子，每一堆为kr枚，由归纳假设，在以后甲乙的搏奕中乙必胜。因此全局也是乙必胜。第53页，此课件共82页哦第第3章章 集合集合 11.04.20233.6 容斥原理和抽屉原理容斥原理和抽屉原理 3.6.1 3.6.1 容斥原理容斥原理 设集合A是归纳定义的集合，现欲证A中所有元素具有性质P，即证：对于任意xA有P(x)为真。可

42、进行如下证明：(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)为真。第54页，此课件共82页哦第第3章章 集合集合 11.04.2023集合的运算，可用于有限个元素的计数问题。在有限集的元素计数问题中，容斥原理有着广泛的应用。定理定理3.19(3.19(容斥原理容斥原理)对有限集合A和B，有|AB|A|B|AB|。证明 因为A

43、BB(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|。第55页，此课件共82页哦第第3章章 集合集合 11.04.2023例例1 1 一个班有50个学生，在第一次考试中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得95分的有多少人？解解 设A和B分别表示在第一次和第二次考试中得95分的

44、学生的集合。则：|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相邻，总共有多少种方法？第56页，此课件共82页哦第第3章章 集合集合 11.04.2023解解 任取7个不同的数字构成7位数的个数为 9!/2，5和6相邻的个数为6！(2！)67！，根据容斥原理，总共有9!/267!151200种方法。例例3 3 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网

45、球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则：第57页，此课件共82页哦第第3章章 集合集合 11.04.2023|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。故，不会打这三种球的共5人。在不要求严格步骤的情况下，以上各题也可通过文氏图的方法来求解。下面以例3加以说明：设A、B、C分别表示会打排球、

46、网球和篮球的学生集合。该问题的文氏图如图3-2所示。由题意可得：第58页，此课件共82页哦第第3章章 集合集合 11.04.2023|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根据上面各等式，依次求得：第59页，此课件共82页哦第第3章章 集合集合 11.04.2023|I1|5，|I2|4，|I3|5，|I4|1，|I5|2，|I6|3，|I7|0。所以，25|ABC|25(|I1|I2|I3|I4|I5|I6|I7|)25(5451230)5。故，不会打这三种球的共5人。第60页，此

47、课件共82页哦第第3章章 集合集合 11.04.20233.6.2 3.6.2 抽屉原理抽屉原理(鸽巢原理鸽巢原理)抽屉原理是一个十分基本、非常重要、应用极其广泛的数学原理，是解决数学中的一类存在性问题的基本工具。定理定理3.213.21(抽屉原理)(1)把多于n个元素的集合S分成n个子集S1、S2、Sn的并集，那么至少存在一个集合Si，它包含S中的两个或两个以上的元素。(2)把多于mn个元素的集合S分成n个子集S1、S2、Sn的并集，那么至少存在一个集合Si，它包含S中的m1或m1以上的元素。证明 仅证(2),反证法。(2)若结论不成立，则对于任意子集Si，有|Si|m，于是|S|S1|S2

48、|Sn|mn，矛盾。第61页，此课件共82页哦第第3章章 集合集合 11.04.2023例例3 3 在从1到2n的整数中，任意选取n1个数，证明在这n1个数中总存在两个数，使得其中一个数是另一个的倍数。证明证明 设S1，2，2n，Sia|aS，且存在kN使得a2k(2i1)，i1，2，n。于是SS1S2Sn，则n1个数中必有两个数在S的同一个子集Si中，这两个数中的一个数是另一个的偶数倍。例例4 4 在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形(可能是退化的)面积不超过1/8。证明证明 把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点

49、，它们组成的三角形(可能是退化的)面积不超过小正方形的一半，即1/8。第62页，此课件共82页哦第第3章章 集合集合 11.04.20233.7 递推关系递推关系 3.7.1 3.7.1 递推关系的概念递推关系的概念 有些计数问题往往与求一个数列的通项有关。但在一些复杂的特定条件下要直接求出这个数列的通项公式，有时十分困难。而在同样的条件下，写出该数列相邻项之间的关系，再利用一定的方法和技巧，却往往能很容易的得到所要的结论。例例1 1 斐波那契数列(Fibonacci)问题 假定一对兔子两个月成熟后，每月生一对兔子。按照假定，一对刚出生的兔子在n个月后，共有多少对兔子？解解 设第n个月的兔子数

50、为Fn，由题意得F01 F11 FnFn1Fn2，n2第63页，此课件共82页哦第第3章章 集合集合 11.04.2023例例2 2 汉诺塔(Hanoi)问题 有三根立柱A、B、C以及n个大小不同的圆盘套在立柱A上，大的圆盘在下面，小的圆盘在上面，构成一个塔形。现在要把这n个圆盘移到立柱B上。可以利用这三根立柱，每次只能移动一个圆盘，但不允许将它放在较小的圆盘上，问最少需移动多少次？解解 令Hn为完成这样的一次移动至少必须移动圆盘的次数。为了把n个圆盘从立柱A移到立柱B，可先将n1个圆盘从立柱A移到立柱C，留下最大的圆盘，移动的次数为Hn1；然后再将最大的圆盘移动到立柱B，移动1次；最后将n1