《集合的概念与表示法精选课件.ppt》由会员分享，可在线阅读，更多相关《集合的概念与表示法精选课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3章章 集合集合 关于集合的概念与表示法09.12.2022第一页，本课件共有82页第第3章章 集合集合 09.12.20223.1 集合的概念与表示法集合的概念与表示法 3.1.1 集合的概念集合的概念 集合作为数学的一个基本而又简单的原始概念，是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合，用小写字母(如a、b)表示集合中的元素。给定一个集合A和一个元素a，可以判定a是否在集合A中。如果a在A中，我们称a属于A，记为aA。否则，称a不属于A，记为aA。例如，某大学计算机系的全体学生、所有自然数等都是集
2、合。第二页，本课件共有82页第第3章章 集合集合 09.12.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的元素。第三页，本课件共有82页第第3章章 集合集合 09.12.2022集
3、合是多种多样的，我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数，记为|A|。当|A|有限时，称A为有限集合；否则，称A为无限集合。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。第四页，本课件共有82页第第3章章 集合集合 09.12.20223.1.2 集合的表示法集合的表示法 表示一个集合通常有两种方法：列举法和谓词表示法。1.列举法(或枚举法)列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。例如：Aa，b
4、，c，B0，1，2，3，。列举法一般用于有限集合和有规律的无限集合。2.谓词表示法(或描述法)谓词表示法是用谓词来概括集合中元素的属性。通常用x|p(x)来表示具有性质p的一些对象组成的集合。例如：x|1x6x为整数为由1、2、3、4、5、6组成的集合。下面讨论集合之间的关系。第五页，本课件共有82页第第3章章 集合集合 09.12.20223.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。第六页，本课件共有82页第第3章章 集合集合 09.12.2022定理定理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。这个定理非常重要，是证明两个集合相等的基本思路和依据。第七页，本课件共有82页第第3章章 集合集合 09.12.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的真子集，也称A真包含于B或B真包含A，记作AB。否则，记作AB。B真包含A的符号化表示：第八页，本课件共有82页第第3章章 集合集合 09.12.2022ABx
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。第九页，本课件共有82页第第3章章 集合集合 09.12.2022证明证明 仅证(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。第十页，本课件共有82页第第3章章 集合集合 09.12.20223.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的平凡子集。第十一页，本课件共有82页第第3章章 集合集合 09.12.2022特别要注意与的区别，是不含任何元素的集合，是任意集合的子集，而是含有一个元素的集合。定义定义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。第十二页，本课件共有82页第第3章章 集合集合 09.12.2022定理定理3.53.5 若|A|n，则|P(A)|2n
10、。证明证明 因为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)。第十三页，本课件共有82页第第3章章 集合集合 09.12.2022定义定义3.53.5 所要讨论的集合都是某个集合的子集，称这个集合为全集，记作U或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题时
11、，可把整个坐标平面取作全集。第十四页，本课件共有82页第第3章章 集合集合 09.12.20223.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、十五页，本课件共有82页第第3章章 集合集合 09.12.20223.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第十六页，本课件共有82页第第3章章 集合集合 09.12.2022例例1 1 设A
13、和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。第十七页，本课件共有82页第第3章章 集合集合 09.12.2022定义定义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 。第十八页，本课件共有82页第第3章章 集合集合 09.12.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，AU
15、A第十九页，本课件共有82页第第3章章 集合集合 09.12.2022(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。也可利用已有的公式证明。第二十页，本课件共有82页第第3章章 集合集合 09.12.2022定理定理3.83.8 任意集合A和B，B ABU且AB。证明证明 如B ，则ABA U，ABA 。反之，若ABU且AB，则BBUB(A )(BA)(B )(B )(A )(B )(A
16、B)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)。第二十一页，本课件共有82页第第3章章 集合集合 09.12.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)。第二十二页，本课件共有82页第第3章章 集合集合 09
17、.12.2022例例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。第二十三页，本课件共有82页第第3章章 集合集合 09.12.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。(
18、2)(AB)CA(BC)。(3)A(BC)(AB)(AC)。第二十四页，本课件共有82页第第3章章 集合集合 09.12.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)。第二十五页，本课件共有82页第第3章章 集合集合 09.12.20223.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。由定义可知，广义交和广义并是针对集族而言的，对于非集族来说，其广义交和广义并均为空集。第二十六页，本课件共有82页第第3章章 集合集合 09.12.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)。第
20、二十七页，本课件共有82页第第3章章 集合集合 09.12.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。第二十八页，本课件共有82页第第3章章 集合集合 09.12.20223.2.4 集合的文氏图集合的文氏图 集合之间的相互关系和运算还可以用文氏图来描述，它有助于我们理解问题，有时对解题也很有帮助。在不要求有求解步骤的题目中，我们可以使用文氏图求解，但它不能用于题目的证明。在文氏图中，用
21、矩形表示全集U，矩形内部的点均为全集中的元素，用圆或椭圆表示U的子集，其内部的点表示不同集合的元素，并将运算结果得到的集合用阴影部分表示。图3-1表示了集合的5种基本运算，阴影部分表示经过相应运算得到的。第二十九页，本课件共有82页第第3章章 集合集合 09.12.2022第三十页，本课件共有82页第第3章章 集合集合 09.12.20223.3 集合的划分与覆盖集合的划分与覆盖 在集合的研究中，除了进行集合之间的比较外，还要对集合的元素进行分类。这一节将讨论集合的划分问题。定义定义3.123.12 设SA1，A2，An是集合A的某些非空子集组成的集合，若 A，则称S为集合A的一个覆盖。定义定
22、义3.133.13 设A1，A2，An是集合A的某些非空子集组成的集合，若 A，且AiAj(ij)，则称为A的一个划分，称中的元素为A的划分块。第三十一页，本课件共有82页第第3章章 集合集合 09.12.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，4，1，6，11，A2，8，3，2，7，12，A3，7，2，3，8，13，A4，6
23、，1，4，9，14，。于是，Z，且AiAj(ij)。所以，A0，A1，A2，A3，A4是Z的一个划分。第三十二页，本课件共有82页第第3章章 集合集合 09.12.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和B1，B2，Bs是同一集合A的两种划分，则称其所有AiBj组成的集合为原来两划分的交叉划分。第三十三页
24、，本课件共有82页第第3章章 集合集合 09.12.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的子集，则形如 Ai(Ai为Ai或 )的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构
25、成全集U的一个划分。第三十四页，本课件共有82页第第3章章 集合集合 09.12.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的一个划分。第三十五页，本课件共有82页第第3章章 集合集合 09.12.20223.4 排列与组合排列与组合3.4.1 3.4.1 加法与乘法原理加法与乘法原理 在组
26、合计数的计算和研究中，加法原理和乘法原理是两个最常用也是最基本的原理。加法原理加法原理 若事件的有限集合SS1S2Sn，且S1、S2、Sn两两不相交，则|S|S1|S2|Sn|乘法原理乘法原理 若事件的有限集合S是依次取自有限集合S1、S2、Sn中事件的序列的集合，则|S|S1|S2|Sn|第三十六页，本课件共有82页第第3章章 集合集合 09.12.2022例例1 1 求由数字1、2、3、4、5组成的小于1000的数(每个数字都允许重复出现)的个数。解解 在三位数中，每一个数位上的数字都有5种不同的选取法，由乘法原理知，满足条件的三位数的个数是53个。同理可知，满足条件的二位数和一位数的个数
27、分别为52个和5个。再由加法原理知，满足条件的自然数总共有53525155个。第三十七页，本课件共有82页第第3章章 集合集合 09.12.20223.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个元
28、素时，第一个元素有n种不同的选法，第2个元素有n1种不同的选法，第r个元素从剩下的nr1个元素中选取，有nr1种不同的选法。根据乘法原理，顺序选取r个元素共有的不同选取方法数为：P(n，r)n(n1)(n2)(nr1)。第三十八页，本课件共有82页第第3章章 集合集合 09.12.2022例例2 2 从1、2、9中选取数字构成3位数，如要求每个数字都不相同，问共有多少种方法？解解 从1、2、9中选取百位数，共9种选法，再从剩下的数字中选取十位数，共8种选法，最后从剩下的数字中选取个位数，共7种选法。因此，从1、2、9中选取数字构成3位数共有987504种方法。定义定义3.17 3.17 r无重
29、复排列可以看作是将选出的r个元素排列在一条直线上的排列，这时也称为r线状排列。如果把这r个元素排列在一个圆周上，则这种排列称为S的r圆排列。对两个圆排列，若其中一个圆排列可以由另一个圆排列通过旋转而得到，则认为这两个圆排列在本质上是同一个圆排列。于是有下面的结论成立。第三十九页，本课件共有82页第第3章章 集合集合 09.12.2022定理定理3.15 3.15 n个元素的r圆排列的个数N(n，r)为证明证明 为了得到n个元素的r无重复排列，可以先从n个元素中选取r个元素作r圆排列，这种圆排列的个数是N(n，r)。然后，将这个r圆排列断开后即可得到线状的r无重复排列。因为从r个不同的位置处断开
30、，由乘法原理可得P(n，r)rN(n，r)，即例例3 3 有8个人围着圆桌进餐，如果要求每餐坐的顺序不同，那么他们在一起最多能共进几天餐？解解 首先8圆排列数为8!/8，又一日三餐，故他们一起能共餐8!/(83)1680天。第四十页，本课件共有82页第第3章章 集合集合 09.12.20222.组合组合定义定义3.18 3.18 集合S有n个元素，从中选取r个元素，若不考虑它们的排列顺序，且在选取中不允许元素重复出现，称这种选取方式为S的r无重复组合。S的所有r无重复组合的个数记为C(n，r)或Cnr。定理3.16 n个元素的r无重复组合的个数为C(n，r)。证明 为了得到n个元素的r无重复排
31、列，可以先从n个元素中选取r个元素作r无重复组合，这种无重复组合的个数是C(n，r)，然后将这r个取出的元素作r无重复排列，这种r无重复排列的个数是P(r，r)r!。由乘法原理可得P(n，r)r!C(n，r)，即C(n，r)。第四十一页，本课件共有82页第第3章章 集合集合 09.12.2022例例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
32、和C，方法数(C(100，1)3。由加法原则，总取数为3C(100，3)(C(100，1)31485100。第四十二页，本课件共有82页第第3章章 集合集合 09.12.20223.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)(
33、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)的下一个排列。第四十三页，本课件共有82页第第3章章 集合集合 09.12.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。由此定理可建立生成所有排列的算
34、法：步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第四十四页，本课件共有82页第第3章章 集合集合 09.12.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，求其全排列。解 123412431324134214231
35、432213421432314234124132431312431423214324134123421412341324213423143124321。第四十五页，本课件共有82页第第3章章 集合集合 09.12.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，
36、取(a1，a2，ar)(1，2，r)第四十六页，本课件共有82页第第3章章 集合集合 09.12.2022步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。第四十七页，
37、本课件共有82页第第3章章 集合集合 09.12.20223.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)为真。第四十八页，本课件共有82页第第3
38、章章 集合集合 09.12.2022由于A仅由(1)和(2)条款所确定的元素组成，因此当上述证明过程完成时，“A中所有元素具有性质P”得证。这种推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法。为区别通常所说的数学归纳法，它又称为“结构归纳法”。数学归纳法是其一种特例。第四十九页，本课件共有82页第第3章章 集合集合 09.12.20223.5.2 3.5.2 数学归纳原理数学归纳原理 将上述原理应用到自然数集上进行归纳推理，就是我们所说的数学归纳法。1.1.第一数学归纳法第一数学归纳法 用第一数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数
39、0具有性质P。(2)归纳过程：对任意k(0)，假设P(k)真(归纳假设“k满足性质P”)时，推出P(k1)真。(3)结论：所有自然数具有性质P。第五十页，本课件共有82页第第3章章 集合集合 09.12.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所以，对任意自然数结论成立。第五十一页，本课件共有82页第第3章章 集合集合 09.12.2
40、0222.2.第二数学归纳法第二数学归纳法用第二数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(0)，假设P(i)真，ki0(归纳假设“0，1，k1满足性质P”)时，推出P(k)真。(3)结论：所有自然数具有性质P。例例2 2 有数目相同的两堆棋子(每堆棋子数为n)，甲、乙两人玩取棋子游戏。规定两人轮流取棋子，每次两人取子数相同，不能不取，也不能同时在两堆中取子，取得最后一枚棋子者为胜者。求证：后取者必胜。第五十二页，本课件共有82页第第3章章 集合集合 09.12.2022证明证明 不妨设甲为先取者，乙为后取者
41、。当n1时，两堆各有一枚棋子，甲必先从一堆中取走一枚棋子，余下最后一枚棋子必被乙取走，乙胜。假设nk时乙必胜。下证nk时也是乙必胜。设第一轮取子时，甲从一堆中取走r枚棋子，余下krk枚棋子，那么，乙从另一堆中也取走r枚棋子，亦留下krk枚棋子。若(1)rk，那么乙取走最后一枚棋子，乙胜。(2)1rk，那么1krk。对留下的两堆棋子，每一堆为kr枚，由归纳假设，在以后甲乙的搏奕中乙必胜。因此全局也是乙必胜。第五十三页，本课件共有82页第第3章章 集合集合 09.12.20223.6 容斥原理和抽屉原理容斥原理和抽屉原理 3.6.1 3.6.1 容斥原理容斥原理 设集合A是归纳定义的集合，现欲证A
42、中所有元素具有性质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)为真。第五十四页，本课件共有82页第第3章章 集合集合 09.12.2022集合的运算，可用于有限个元素的计数问题。在有限集的元素计数问题中，容斥原理有着广泛的应用。定理定理3.19(3.19(容斥原理容斥原
43、理)对有限集合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|。第五十五页，本课件共有82页第第3章章 集合集合 09.12.2022例例1 1 一个班有50个学生，在第一次考试中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得95分的有
44、多少人？解解 设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相邻，总共有多少种方法？第五十六页，本课件共有82页第第3章章 集合集合 09.12.2022解解 任取7个不同的数字构成7位数的个数为 9!/2，5和6相邻的个数为6！(2！)67！，根据容斥原理，总共有9!/267!151200种方法。例例3 3 某班有25名学生，其中14
45、人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则：第五十七页，本课件共有82页第第3章章 集合集合 09.12.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。故，不会打这三种球的共5人。在不要求严格步骤的情况下，以上各题也可通过文氏
46、图的方法来求解。下面以例3加以说明：设A、B、C分别表示会打排球、网球和篮球的学生集合。该问题的文氏图如图3-2所示。由题意可得：第五十八页，本课件共有82页第第3章章 集合集合 09.12.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根据上面各等式，依次求得：第五十九页，本课件共有82页第第3章章 集合集合 09.12.2022|I1|5，|I2|4，|I3|5，|I4|1，|I5|2，|I6|3，|I7|0。所以，25|ABC|25(|I1|I2|I3|I4|I5|I6|I7
47、|)25(5451230)5。故，不会打这三种球的共5人。第六十页，本课件共有82页第第3章章 集合集合 09.12.20223.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
48、)若结论不成立，则对于任意子集Si，有|Si|m，于是|S|S1|S2|Sn|mn，矛盾。第六十一页，本课件共有82页第第3章章 集合集合 09.12.2022例例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。证明证明
49、把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形(可能是退化的)面积不超过小正方形的一半，即1/8。第六十二页，本课件共有82页第第3章章 集合集合 09.12.20223.7 递推关系递推关系 3.7.1 3.7.1 递推关系的概念递推关系的概念 有些计数问题往往与求一个数列的通项有关。但在一些复杂的特定条件下要直接求出这个数列的通项公式，有时十分困难。而在同样的条件下，写出该数列相邻项之间的关系，再利用一定的方法和技巧，却往往能很容易的得到所要的结论。例例1 1 斐波那契数列(Fibonacci)问题 假定一对兔子两个月成熟后，每月生一对兔子。按照
50、假定，一对刚出生的兔子在n个月后，共有多少对兔子？解解 设第n个月的兔子数为Fn，由题意得F01 F11 FnFn1Fn2，n2第六十三页，本课件共有82页第第3章章 集合集合 09.12.2022例例2 2 汉诺塔(Hanoi)问题 有三根立柱A、B、C以及n个大小不同的圆盘套在立柱A上，大的圆盘在下面，小的圆盘在上面，构成一个塔形。现在要把这n个圆盘移到立柱B上。可以利用这三根立柱，每次只能移动一个圆盘，但不允许将它放在较小的圆盘上，问最少需移动多少次？解解 令Hn为完成这样的一次移动至少必须移动圆盘的次数。为了把n个圆盘从立柱A移到立柱B，可先将n1个圆盘从立柱A移到立柱C，留下最大的圆