集合的概念与表示法.ppt

2023/9/16,第3章 集合,3.1 集合的概念与表示法3.2 集合的运算与性质 3.3 集合的划分与覆盖 3.4 排列与组合3.5 归纳原理3.6 容斥原理和抽屉原理3.7 递推关系3.8 集合论在命题逻辑中的应用,2023/9/16,3.1 集合的概念与表示法,3.1.1 集合的概念 集合作为数学的一个基本而又简单的原始概念，是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合，用小写字母(如a、b)表示集合中的元素。给定一个集合A和一个元素a，可以判定a是否在集合A中。如果a在A中，我们称a属于A，记为aA。否则，称a不属于A，记为aA。例如，某大学计算机系的全体学生、所有自然数等都是集合。,2023/9/16,由集合的概念可知，集合中的元素具有确定性、互异性、无序性和抽象性的特征。其中：(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的元素。,2023/9/16,集合是多种多样的，我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数，记为|A|。当|A|有限时，称A为有限集合；否则，称A为无限集合。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。,2023/9/16,3.1.2 集合的表示法 表示一个集合通常有两种方法：列举法和谓词表示法。1.列举法(或枚举法)列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。例如：Aa，b，c，B0，1，2，3，。列举法一般用于有限集合和有规律的无限集合。2.谓词表示法(或描述法)谓词表示法是用谓词来概括集合中元素的属性。通常用x|p(x)来表示具有性质p的一些对象组成的集合。例如：x|1x6x为整数为由1、2、3、4、5、6组成的集合。下面讨论集合之间的关系。,2023/9/16,3.1.3 集合的包含与相等 包含与相等是集合间的两种基本关系，也是集合论中的两个基本概念。两个集合相等是按照下述原理定义的。外延性原理 两个集合A和B是相等的，当且仅当它们有相同的元素。记为AB。例如，若A2，3，B小于4的素数，则AB。定义3.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。,2023/9/16,定理3.1 集合A和B相等当且仅当这两个集合互为子集。即：ABABBA。证明 若AB，则A和B具有相同的元素，于是x(xAxB)、x(xBxA)都为真，即AB且BA。反之，若AB且BA，假设AB，则A与B元素不完全相同。不妨设有某个元素xA但xB，这与AB矛盾，所以AB。这个定理非常重要，是证明两个集合相等的基本思路和依据。,2023/9/16,定理3.2 设A、B和C是三个集合，则：(1)AA。(2)ABBCAC。证明(1)由定义显然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定义3.2 设A和B是两个集合，若AB且B中至少有一个元素b使得bA，则称A是B的真子集，也称A真包含于B或B真包含A，记作AB。否则，记作AB。B真包含A的符号化表示：,2023/9/16,ABx(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 设A、B和C是三个集合，则(1)(AA)。(2)AB(BA)。(3)ABBCAC。,2023/9/16,证明 仅证(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。,2023/9/16,3.1.4 空集、集族、幂集和全集定义3.3 没有任何元素的集合称为空集，记作。以集合为元素的集合称为集族。例如，x|xx是空集；xx是某大学的学生社团是集族。定理3.4 空集是任何集合的子集。证明 任给集合A，则Ax(xxA)。由于x是假的，所以x(xxA)为真，于是有A为真。推论 空集是惟一的。对于任一集合A，我们称空集和其自身A为A的平凡子集。,2023/9/16,特别要注意与的区别，是不含任何元素的集合，是任意集合的子集，而是含有一个元素的集合。定义3.4 一个集合A的所有子集组成的集合称为A的幂集，记作P(A)或2A。例1 求幂集P()、P()、P(，)、P(1，2，3)。解 P()P()，P(，)，P(1，2，3)，1，2，3，1，2，3。,2023/9/16,定理3.5 若|A|n，则|P(A)|2n。证明 因为A的m个元素的子集的个数为Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理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)。,2023/9/16,定义3.5 所要讨论的集合都是某个集合的子集，称这个集合为全集，记作U或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题时，可把整个坐标平面取作全集。,2023/9/16,3.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。,2023/9/16,3.2 集合的运算与性质,3.2.1 集合的交、并、补 定义3.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,2023/9/16,例1 设A和B为两个集合，且AB，则ACBC。证明 对任意的xAC，则有xA且xC。而AB，由xA得xB，则xB且xC，从而xBC。所以，ACBC。例2 设A和B为两个集合，则ABABBABA。证明 对任意的xAB，则xA或xB。又AB，所以xB，于是ABB。又显然有BAB，故ABB。反之，若ABB，因AAB，所以AB。同理可证ABABA。,2023/9/16,2023/9/16,定理3.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,2023/9/16,(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。也可利用已有的公式证明。,2023/9/16,定理3.8 任意集合A和B，B ABU且AB。证明 如B，则ABA U，ABA。反之，若ABU且AB，则BBUB(A)(BA)(B)(B)(A)(B)(AB)U。例4 证明A(BC)(AB)(AC)。证明 因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。,2023/9/16,例5 证明。证明 因为x xABxAxBx x x，所以。例6 证明A(BC)(AB)(AC)。证明 因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。,2023/9/16,2023/9/16,3.2.2 集合的对称差 定义3.9 集合A和B的对称差定义为AB(AB)(BA)。例如，若A0，0，则P(A)A(P(A)A)(AP(A)，0，0，0，0。定理3.9 设A、B和C为三个集合，则：(1)ABBA。(2)(AB)CA(BC)。(3)A(BC)(AB)(AC)。,2023/9/16,(4)AA；AU；AA；AU。(5)AB(AB)(AB)。证明 仅证(5)AB(AB)(BA)(A)(B)(A)B)(A)(AB)(B)(A)()(AB)()(AB)(AB)。,2023/9/16,3.2.3 广义并、广义交运算 定义3.10 集合A的所有元素的元素组成的集合称为A的广义并。符号化表示为：Ax|B(BAxB)。定义3.11 集合A的所有元素的公共元素组成的集合称为A的广义交。符号化表示为：Ax|B(BAxB)。例如，若Aa，b，c，a，d，e，a，f，则Aa，b，c，d，e，f，Aa。由定义可知，广义交和广义并是针对集族而言的，对于非集族来说，其广义交和广义并均为空集。,2023/9/16,定理3.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)。,2023/9/16,定理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。,2023/9/16,3.2.4 集合的文氏图 集合之间的相互关系和运算还可以用文氏图来描述，它有助于我们理解问题，有时对解题也很有帮助。在不要求有求解步骤的题目中，我们可以使用文氏图求解，但它不能用于题目的证明。在文氏图中，用矩形表示全集U，矩形内部的点均为全集中的元素，用圆或椭圆表示U的子集，其内部的点表示不同集合的元素，并将运算结果得到的集合用阴影部分表示。图3-1表示了集合的5种基本运算，阴影部分表示经过相应运算得到的。,2023/9/16,2023/9/16,3.3 集合的划分与覆盖,在集合的研究中，除了进行集合之间的比较外，还要对集合的元素进行分类。这一节将讨论集合的划分问题。定义3.12 设SA1，A2，An是集合A的某些非空子集组成的集合，若 A，则称S为集合A的一个覆盖。定义3.13 设A1，A2，An是集合A的某些非空子集组成的集合，若 A，且AiAj(ij)，则称为A的一个划分，称中的元素为A的划分块。,2023/9/16,由定义知，划分一定是覆盖，但反之则不然。例如，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，。于是，Z，且AiAj(ij)。所以，A0，A1，A2，A3，A4是Z的一个划分。,2023/9/16,例2 求集合Aa，b，c的所有不同的划分。解 其不同的划分共有5个：1a，b，c，2a，b，c，3a，c，b，4a，b，c，5a，b，c。定理3.12 设A1，A2，Ar和B1，B2，Bs是同一集合A的两种划分，则其所有AiBj组成的集合也是原集合的一种划分。定义3.14 设A1，A2，Ar和B1，B2，Bs是同一集合A的两种划分，则称其所有AiBj组成的集合为原来两划分的交叉划分。,2023/9/16,定义3.15 给定A的两个划分A1，A2，Ar和B1，B2，Bs，若对于每个Aj都有Bk使得AjBk，则称A1，A2，Ar为B1，B2，Bs的加细。定理3.13 任何两种划分的交叉划分，都是原来各划分的一种加细。证明 设A1，A2，Ar和B1，B2，Bs的交叉划分为T，对于T中任意元素AiBj必有AiBjAi和AiBjBj，故T必是原划分的加细。例3 设A1、A2和A3是全集U的子集，则形如 Ai(Ai为Ai或)的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。,2023/9/16,证明 小项共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的一个划分。,2023/9/16,3.4 排列与组合,3.4.1 加法与乘法原理 在组合计数的计算和研究中，加法原理和乘法原理是两个最常用也是最基本的原理。加法原理 若事件的有限集合SS1S2Sn，且S1、S2、Sn两两不相交，则|S|S1|S2|Sn|乘法原理 若事件的有限集合S是依次取自有限集合S1、S2、Sn中事件的序列的集合，则|S|S1|S2|Sn|,2023/9/16,例1 求由数字1、2、3、4、5组成的小于1000的数(每个数字都允许重复出现)的个数。解 在三位数中，每一个数位上的数字都有5种不同的选取法，由乘法原理知，满足条件的三位数的个数是53个。同理可知，满足条件的二位数和一位数的个数分别为52个和5个。再由加法原理知，满足条件的自然数总共有53525155个。,2023/9/16,3.4.2 排列和组合 1.排列 定义3.16 集合S有n个元素，从中选取r个元素作有序排列，且在排列中不允许任何元素重复出现，则称这种排列为S的r无重复排列。当rn时，称其为全排列。S的所有r无重复排列的个数记为P(n，r)或Pnr。定理3.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)。,2023/9/16,例2 从1、2、9中选取数字构成3位数，如要求每个数字都不相同，问共有多少种方法？解 从1、2、9中选取百位数，共9种选法，再从剩下的数字中选取十位数，共8种选法，最后从剩下的数字中选取个位数，共7种选法。因此，从1、2、9中选取数字构成3位数共有987504种方法。定义3.17 r无重复排列可以看作是将选出的r个元素排列在一条直线上的排列，这时也称为r线状排列。如果把这r个元素排列在一个圆周上，则这种排列称为S的r圆排列。对两个圆排列，若其中一个圆排列可以由另一个圆排列通过旋转而得到，则认为这两个圆排列在本质上是同一个圆排列。于是有下面的结论成立。,2023/9/16,定理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 有8个人围着圆桌进餐，如果要求每餐坐的顺序不同，那么他们在一起最多能共进几天餐？解 首先8圆排列数为8!/8，又一日三餐，故他们一起能共餐8!/(83)1680天。,2023/9/16,2.组合定义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)。,2023/9/16,例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。,2023/9/16,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，a2，an)和(b1，b2，bn)的排列(c1，c2，cn)，使得(a1，a2，an)(c1，c2，cn)(b1，b2，bn)，则称(b1，b2，bn)为(a1，a2，an)的下一个排列。,2023/9/16,定理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,2023/9/16,中的元素由小到大排起来，记这个排列为(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。,2023/9/16,2.组合的生成定理3.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),2023/9/16,步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 S1，2，3，4，5，6，求其所有4元素子集。解 123412351236124512461256134513461356145623452346235624563456。,2023/9/16,3.5 归纳原理,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)为真。,2023/9/16,由于A仅由(1)和(2)条款所确定的元素组成，因此当上述证明过程完成时，“A中所有元素具有性质P”得证。这种推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法。为区别通常所说的数学归纳法，它又称为“结构归纳法”。数学归纳法是其一种特例。,2023/9/16,3.5.2 数学归纳原理 将上述原理应用到自然数集上进行归纳推理，就是我们所说的数学归纳法。1.第一数学归纳法 用第一数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(0)，假设P(k)真(归纳假设“k满足性质P”)时，推出P(k1)真。(3)结论：所有自然数具有性质P。,2023/9/16,例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所以，对任意自然数结论成立。,2023/9/16,2.第二数学归纳法用第二数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(0)，假设P(i)真，ki0(归纳假设“0，1，k1满足性质P”)时，推出P(k)真。(3)结论：所有自然数具有性质P。例2 有数目相同的两堆棋子(每堆棋子数为n)，甲、乙两人玩取棋子游戏。规定两人轮流取棋子，每次两人取子数相同，不能不取，也不能同时在两堆中取子，取得最后一枚棋子者为胜者。求证：后取者必胜。,2023/9/16,证明 不妨设甲为先取者，乙为后取者。当n1时，两堆各有一枚棋子，甲必先从一堆中取走一枚棋子，余下最后一枚棋子必被乙取走，乙胜。假设nk时乙必胜。下证nk时也是乙必胜。设第一轮取子时，甲从一堆中取走r枚棋子，余下krk枚棋子，那么，乙从另一堆中也取走r枚棋子，亦留下krk枚棋子。若(1)rk，那么乙取走最后一枚棋子，乙胜。(2)1rk，那么1krk。对留下的两堆棋子，每一堆为kr枚，由归纳假设，在以后甲乙的搏奕中乙必胜。因此全局也是乙必胜。,2023/9/16,3.6 容斥原理和抽屉原理,3.6.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)为真。,2023/9/16,集合的运算，可用于有限个元素的计数问题。在有限集的元素计数问题中，容斥原理有着广泛的应用。定理3.19(容斥原理)对有限集合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 推广到n个集合A1，A2，An的情形，有：|A1A2An|i|Ai|ij|AiAj|ijk|AiAjAk|(1)n1|A1A2An|。,2023/9/16,例1 一个班有50个学生，在第一次考试中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得95分的有多少人？解 设A和B分别表示在第一次和第二次考试中得95分的学生的集合。则：|A|26，|B|21，17。于是 50 50(|A|B|AB|)，从而|AB|50|A|B|1750262114。所以，两次考试都得95分的有14人。例2 从1，2，3，4，5，6，7，8，9中取7个不同的数字构成7位数，如不允许5和6相邻，总共有多少种方法？,2023/9/16,解 任取7个不同的数字构成7位数的个数为 9!/2，5和6相邻的个数为6！(2！)67！，根据容斥原理，总共有9!/267!151200种方法。例3 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则：,2023/9/16,|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分别表示会打排球、网球和篮球的学生集合。该问题的文氏图如图3-2所示。由题意可得：,2023/9/16,|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根据上面各等式，依次求得：,2023/9/16,|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人。,2023/9/16,3.6.2 抽屉原理(鸽巢原理)抽屉原理是一个十分基本、非常重要、应用极其广泛的数学原理，是解决数学中的一类存在性问题的基本工具。定理3.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|Sn|mn，矛盾。,2023/9/16,例3 在从1到2n的整数中，任意选取n1个数，证明在这n1个数中总存在两个数，使得其中一个数是另一个的倍数。证明 设S1，2，2n，Sia|aS，且存在kN使得a2k(2i1)，i1，2，n。于是SS1S2Sn，则n1个数中必有两个数在S的同一个子集Si中，这两个数中的一个数是另一个的偶数倍。例4 在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形(可能是退化的)面积不超过1/8。证明 把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形(可能是退化的)面积不超过小正方形的一半，即1/8。,2023/9/16,3.7 递推关系,3.7.1 递推关系的概念 有些计数问题往往与求一个数列的通项有关。但在一些复杂的特定条件下要直接求出这个数列的通项公式，有时十分困难。而在同样的条件下，写出该数列相邻项之间的关系，再利用一定的方法和技巧，却往往能很容易的得到所要的结论。例1 斐波那契数列(Fibonacci)问题 假定一对兔子两个月成熟后，每月生一对兔子。按照假定，一对刚出生的兔子在n个月后，共有多少对兔子？解 设第n个月的兔子数为Fn，由题意得F01 F11 FnFn1Fn2，n2,2023/9/16,例2 汉诺塔(Hanoi)问题 有三根立柱A、B、C以及n个大小不同的圆盘套在立柱A上，大的圆盘在下面，小的圆盘在上面，构成一个塔形。现在要把这n个圆盘移到立柱B上。可以利用这三根立柱，每次只能移动一个圆盘，但不允许将它放在较小的圆盘上，问最少需移动多少次？解 令Hn为完成这样的一次移动至少必须移动圆盘的次数。为了把n个圆盘从立柱A移到立柱B，可先将n1个圆盘从立柱A移到立柱C，留下最大的圆盘，移动的次数为Hn1；然后再将最大的圆盘移动到立柱B，移动1次；最后将n1个圆盘从立柱C移到立柱B，移动次数为Hn1。,2023/9/16,于是有Hn2Hn11，n2，其中H11。以上的例子有一个共同的特点，即从我们在计数问题所得出的数列中，它的一般项可用它自身数列中的前面若干项来表达。这样，从给定的初始值出发，利用所建立的关系式可以依次算出数列中的每一项。我们称这些关系式为递推关系。下面我们介绍递推关系的几种解法。,2023/9/16,1.递推关系的生成函数解法设a0，a1，an，为一个无穷数列，我们称f(t)a0a1tantn为该数列的生成函数。例3 数列1，1，1，的生成函数为 1ttn。将递推关系代入数列的生成函数的系数中去，通过计算可以得到生成函数的显式，然后再将它展开成幂级数就可求得数列的通项。例4 斐波那契数列问题解 设F(x)为斐波那契数列的生成函数，则有,2023/9/16,2023/9/16,2.常系数线性齐次递推关系的解法我们把形如H(n)b1H(n1)b2H(n2)bkH(nk)0(其中H(n)、H(n1)、H(nk)是n的函数)的递推关系式称为常系数线性齐次递推关系，并称xkb1xk1b2xk2bk0为其特征方程，它的根称为其特征根。在使用特征根方法求解递推关系时要用到下面三个定理，其证明参见相关文献。定理3.22 设q为非零的实数或复数，则H(n)qn是递推关系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的解当且仅当q是它的一个特征根。,2023/9/16,定理3.23 设q1、q2、qk为非零的实数或复数，则H(n)C1q1nC2q2nCkqkn(C1、C2、Ck是确定的常数)是递推关系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的解当且仅当q1、q2、qk是它的k个不同的特征根。定理3.24 设q1、q2、qk为非零的实数或复数，它们是递推关系式H(n)b1H(n1)b2H(n2)bkH(nk)0(kn，bk0)的特征方程的t(tk)个不同的特征根，各有e1、e2、et重。则递推关系式的一般解是H(n)H1(n)H2(n)Ht(n)，其中Hi(n)C1qinC2nqinqin(i1，2，t；C1，C2，为确定的常数)。例6 斐波那契数列问题,2023/9/16,2023/9/16,3.常系数线性非齐次递推关系的解法我们把形如H(n)b1H(n1)b2H(n2)bkH(nk)f(n)(其中H(n)、H(n1)、H(nk)是n的函数，f(n)是n的多项式或an)的递推关系式称为常系数线性非齐次递推关系。这类递推关系的求解可通过将非齐次递推关系归约为齐次递推关系的方法来求解。下面我们通过一个例子来说明。例7 汉诺塔问题解 递推关系Hn2Hn11对应的齐次方程的通解为HnC2n。利用常系数变易法作代换Hnan2n可得anan1，从而ana0a01，Hnan2n(1a0)2n1。由H11得a01。因此，Hn2n1。,2023/9/16,3.8 集合论在命题逻辑中的应用,3.8.1 命题逻辑中的集合表示 首先引入以下几个符号：(A)：命题公式A的主析取范式中所有小项mi的下标组成的集合。A：命题公式A的主合取范式中所有大项Mi的下标组成的集合。令U0，1，2，2n1，则U为n个命题变元所组成的所有小项(或大项)对应的下标组成的集合。下面，我们先通过一个例子来说明命题公式的主范式可以用集合来表示，然后证明命题公式的主范式和推理都可通过集合运算而得到。,2023/9/16,例1 求命题公式PQ与PQ的主析取范式。解 命题公式PQ与PQ的真值表如表3-1所示：表3-1于是(PQ)3，(PQ)1，2，3。将上述例子推广到含有n个命题变元的命题公式中，则有以下的重要结论。,2023/9/16,定理3.25 设VP1，P2，Pn，A是命题公式，其包含的命题变元均在集合V中，则AU(A)。定理3.26 设VP1，P2，Pn，U0，1，2，2n1，对于任意PiV，则(Pi)x|xUx的n位二进制表示中第i位元素为1，Pix|xUx的n位二进制表示中第i位元素为0。约定，x的n位二进制表示中从左到右依次为第1位、第2位、第n位。证明 由真值表即得。定理3.27 设VP1，P2，Pn，对于任意P、QV，则：(1)(PQ)(P)(Q)。,2023/9/16,(2)(PQ)(P)(Q)。(3)(P)U(P)。(4)(PQ)(U(P)(Q)。(5)(PQ)(U(P)(U(Q)(P)(Q)。证明(1)、(2)、(3)由定理3.26即得。(4)因为PQPQ，所以(PQ)(PQ)(P)(Q)(U(P)(Q)。(5)因为PQ(PQ)(PQ)，所以(PQ)(PQ)(PQ)(P)(Q)(P)(Q)(U(P)(U(Q)(P)(Q)。,2023/9/16,定理3.28 设VP1，P2，Pn，A和B是命题公式，其包含的命题变元均在集合V中，则：(1)(AB)(A)(B)。(2)(AB)(A)(B)。(3)(A)U(A)。(4)(AB)(U(A)(B)。(5)(AB)(U(A)(U(B)(A)(B)。证明 根据定理3.27即得。,2023/9/16,定理3.29 设VP1，P2，Pn，A、A1、A2、An和B分别是命题公式，其包含的命题变元均在集合V中，则：(1)AB当且仅当(A)(B)。(2)AB当且仅当(A)(B)。(3)A1、A2、AnB当且仅当(A1)(A2)(An)(B)。证明(1)若AB，则A和B的主析范式相同，因此A和B的主析范式中小项的下标组成的集合相同，即(A)(B)。反之，若(A)(B)，不妨设其为j1，j2