集合的概念与表示法

关于集合的概念与表示法第一页，共八十二页，2022年，8月28日3.1集合的概念与表示法3.1.1集合的概念

集合作为数学的一个基本而又简单的原始概念，是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合，用小写字母(如a、b)表示集合中的元素。给定一个集合A和一个元素a，可以判定a是否在集合A中。如果a在A中，我们称a属于A，记为a∈A。否则，称a不属于A，记为aA。例如，某大学计算机系的全体学生、所有自然数等都是集合。第二页，共八十二页，2022年，8月28日由集合的概念可知，集合中的元素具有确定性、互异性、无序性和抽象性的特征。其中：(1)确定性是指：一旦给定了集合A，对于任意元素a，我们就可以准确地判定a是否在A中，这是明确的。(2)互异性是指：集合中的元素之间是彼此不同的。即集合{a，b，b，c}与集合{a，b，c}是一样的。(3)无序性是指：集合中的元素之间没有次序关系。即集合{a，b，c}与集合{c，b，a}是一样的。(4)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A＝{1，2，{1，2}}，其中{1，2}是集合A的元素。第三页，共八十二页，2022年，8月28日集合是多种多样的，我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数，记为|A|。当|A|有限时，称A为有限集合；否则，称A为无限集合。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。第四页，共八十二页，2022年，8月28日3.1.2集合的表示法

表示一个集合通常有两种方法：列举法和谓词表示法。

1.列举法(或枚举法)

列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。例如：A＝{a，b，c}，B＝{0，1，2，3，…}。列举法一般用于有限集合和有规律的无限集合。

2.谓词表示法(或描述法)

谓词表示法是用谓词来概括集合中元素的属性。通常用{x|p(x)}来表示具有性质p的一些对象组成的集合。例如：{x|1≤x≤6∧x为整数}为由1、2、3、4、5、6组成的集合。下面讨论集合之间的关系。第五页，共八十二页，2022年，8月28日3.1.3集合的包含与相等

包含与相等是集合间的两种基本关系，也是集合论中的两个基本概念。两个集合相等是按照下述原理定义的。外延性原理两个集合A和B是相等的，当且仅当它们有相同的元素。记为A＝B。例如，若A＝{2，3}，B＝{小于4的素数}，则A＝B。定义3.1

设A和B为两个集合，若对于任意的a∈A必有a∈B，则称A是B的子集，也称A包含于B或B包含A，记作AB。如果B不包含A，记作AB。B包含A的符号化表示为：ABx(x∈A→x∈B)。例如，若A＝{1，2，3，4}，B＝{1，2}，C＝{2，3}，则BA且CA，但CB。第六页，共八十二页，2022年，8月28日定理3.1集合A和B相等当且仅当这两个集合互为子集。即：A＝BAB∧BA。证明若A＝B，则A和B具有相同的元素，于是x(x∈A→x∈B)、x(x∈B→x∈A)都为真，即AB且BA。反之，若AB且BA，假设A≠B，则A与B元素不完全相同。不妨设有某个元素x∈A但xB，这与AB矛盾，所以A＝B。这个定理非常重要，是证明两个集合相等的基本思路和依据。第七页，共八十二页，2022年，8月28日定理3.2设A、B和C是三个集合，则：(1)AA。(2)AB∧BCAC。证明

(1)由定义显然成立。(2)AB∧BCx(x∈A→x∈B)∧x(x∈B→x∈C)x((x∈A→x∈B)∧(x∈B→x∈C))x(x∈A→x∈C)AC。定义3.2

设A和B是两个集合，若AB且B中至少有一个元素b使得bA，则称A是B的真子集，也称A真包含于B或B真包含A，记作AB。否则，记作AB。B真包含A的符号化表示：第八页，共八十二页，2022年，8月28日ABx(x∈A→x∈B)∧x(x∈B∧xA)。若两个集合A和B没有公共元素，我们说A和B是不相交的。例如，若A＝{a，b，c，d}，B＝{b，c}，则B是A的真子集，但A不是A的真子集。需要指出的是，∈与表示元素和集合的关系，而、与＝表示集合和集合的关系。例如，若A＝{0，1}，B＝{0，1，{0，1}}，则AB且AB。定理3.3设A、B和C是三个集合，则(1)(AA)。(2)AB(BA)。(3)AB∧BCAC。第九页，共八十二页，2022年，8月28日证明仅证(2)和(3)(2)ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))(BA)。(3)AB∧BC(x(x∈A→x∈B)∧x(x∈B∧xA))∧(x(x∈B→x∈C)∧x(x∈C∧xB))x(x∈A→x∈B∧x∈B→x∈C)∧(x(x∈B∧xA)∧x(x∈C∧xB))x(x∈A→x∈C)∧(x(x∈C∧xA)AC。第十页，共八十二页，2022年，8月28日3.1.4空集、集族、幂集和全集定义3.3没有任何元素的集合称为空集，记作。以集合为元素的集合称为集族。例如，{x|x≠x}是空集；{x｜x是某大学的学生社团}是集族。定理3.4

空集是任何集合的子集。证明任给集合A，则Ax(x∈→x∈A)。由于x∈是假的，所以x(x∈→x∈A)为真，于是有A为真。推论空集是惟一的。对于任一集合A，我们称空集和其自身A为A的平凡子集。第十一页，共八十二页，2022年，8月28日特别要注意与{}的区别，是不含任何元素的集合，是任意集合的子集，而{}是含有一个元素的集合。定义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}}}。第十二页，共八十二页，2022年，8月28日定理3.5

若|A|＝n，则|P(A)|＝2n。证明因为A的m个元素的子集的个数为Cnm，所以|P(A)|＝Cn0＋Cn1＋…＋Cnn＝2n。定理3.6设A和B是两个集合，则：(1)B∈P(A)BA。(2)ABP(A)P(B)。(3)P(A)＝P(B)A＝B。(4)P(A)∈P(B)A∈B。(5)P(A)∩P(B)＝P(A∩B)。(6)P(A)∪P(B)P(A∪B)。第十三页，共八十二页，2022年，8月28日定义3.5

所要讨论的集合都是某个集合的子集，称这个集合为全集，记作U或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题时，可把整个坐标平面取作全集。第十四页，共八十二页，2022年，8月28日3.1.5有限幂集元素的编码表示为便于在计算机中表示有限集，可对集合中的元素规定一种次序，在集合和二进制之间建立对应关系。设U＝{a1，a2，…，an}，对U的任意子集A，A与一个n位二进制数b1b2…bn对应，其中bi＝1当且仅当ai∈A。对于一个n位二进制数b1b2…bn，使之对应一个集合A＝{ai|bi＝1}。例如，若A＝{a，b，c}，则A的幂集为P(A)＝{Ai|i∈J}，其中J＝{i|i是二进制数且000≤i≤111}，其中A000＝，A011＝{b，c}等。一般地P(A)＝{Ai|i∈J}，其中J＝{i|i是二进制数且≤i≤}。第十五页，共八十二页，2022年，8月28日3.2集合的运算与性质3.2.1集合的交、并、补

定义3.6

设A和B为两个集合，A和B的交集A∩B、并集A∪B分别定义如下：A∩B＝{x|x∈A∧x∈B}A∪B＝{x|x∈A∨x∈B}

显然，A∩B是由A和B的公共元素组成的集合，A∪B由A和B的所有元素组成的集合。例如，若A＝{1，2，3}，B＝{1，4}，则A∩B＝{1}，A∪B＝{1，2，3，4}。集合的交与并可以推广到n个集合的情况，即A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}第十六页，共八十二页，2022年，8月28日例1设A和B为两个集合，且AB，则A∩CB∩C。证明对任意的x∈A∩C，则有x∈A且x∈C。而AB，由x∈A得x∈B，则x∈B且x∈C，从而x∈B∩C。所以，A∩CB∩C。例2设A和B为两个集合，则ABA∪B＝BA∩B＝A。证明对任意的x∈A∪B，则x∈A或x∈B。又AB，所以x∈B，于是A∪BB。又显然有BA∪B，故A∪B＝B。反之，若A∪B＝B，因AA∪B，所以AB。同理可证ABA∩B＝A。第十七页，共八十二页，2022年，8月28日定义3.7

设A和B为两个集合，所有属于A而不属于B的元素组成的集合称为B对于A的补集，或相对补。记作A－B＝{x|x∈A∧xB}。A－B也称为A和B的差集。例如，若A＝{1，2，3}，B＝{1，4}，则A－B＝{2，3}，B－A＝{4}。定义3.8

设U为全集，集合A关于U的补集U－A称为集合A的绝对补或余集，记为(或～A或Ac)。即＝{x|x∈U且xA}。例3

设A和B为两个集合，则A－B＝A∩。证明因为x∈A－Bx∈A∧xBx∈A∧x∈x∈A∩，所以A－B＝A∩。第十八页，共八十二页，2022年，8月28日定理3.7

对于任意3个集合A、B和C，其交、并、补满足下面10个定律：(1)幂等律A∩A＝A，A∪A＝A(2)结合律(A∪B)∪C＝A∪(B∪C)，(A∩B)∩C＝A∩(B∩C)(3)交换律A∪B＝B∪A，A∩B＝B∩A(4)分配律A∪(B∩C)＝(A∪B)∩(A∪C)，A∩(B∪C)＝(A∩B)∪(A∩C)(5)同一律A∪＝A，A∩U＝A第十九页，共八十二页，2022年，8月28日(6)零律A∪U＝U，A∩＝(7)互补律A∪＝U，A∩＝(8)吸收律A∪(A∩B)＝A，A∩(A∪B)＝A(9)德·摩根律＝∩，＝∪，A－(B∪C)＝(A－B)∩(A－C)，A－(B∩C)＝(A－B)∪(A－C)(10)双重否定律＝A以上等式的证明主要用到命题演算的等价式，即欲证集合A＝B，只需证明x∈Ax∈B。也可利用已有的公式证明。第二十页，共八十二页，2022年，8月28日定理3.8

任意集合A和B，B＝A∪B＝U且A∩B＝。证明如B＝，则A∪B＝A∪＝U，A∩B＝A∩＝。反之，若A∪B＝U且A∩B＝，则B＝B∩U＝B∩(A∪)＝(B∩A)∪(B∩)＝∪(B∩)＝(A∩)∪(B∩)＝(A∪B)∩＝U∩＝。例4

证明A∩(B∪C)＝(A∩B)∪(A∩C)。证明因为x∈A∩(B∪C)x∈A∧x∈(B∪C)x∈A∧(x∈B∨x∈C)(x∈A∧x∈B)∨(x∈A∧x∈C)x∈(A∩B)∨x∈(A∩C)x∈(A∩B)∪(A∩C)，所以A∩(B∪C)＝(A∩B)∪(A∩C)。第二十一页，共八十二页，2022年，8月28日例5

证明＝∩。证明因为x∈xA∪BxA∧xBx∈∧x∈x∈∩，所以＝∩。例6

证明A－(B∪C)＝(A－B)∩(A－C)。证明因为x∈A－(B∪C)x∈A∧x(B∪C)x∈A∧(xB∧xC)(x∈A∧xB)∧(x∈A∧xC)x∈(A－B)∧x∈(A－C)x∈(A－B)∩(A－C)，所以A－(B∪C)＝(A－B)∩(A－C)。第二十二页，共八十二页，2022年，8月28日例7

证明A∩(B－C)＝(A∩B)－(A∩C)。证明

A∩(B－C)＝A∩(B∩)＝(A∩B∩)∪(A∩B∩)＝(A∩B)∩(∪)＝(A∩B)∩＝(A∩B)－(A∩C)。例8

已知A∪B＝A∪C，A∩B＝A∩C，试证B＝C。证明

B＝B∩(A∪B)＝B∩(A∪C)＝(B∩A)∪(B∩C)＝(A∩C)∪(B∩C)＝(A∪B)∩C＝(A∪C)∩C＝C。第二十三页，共八十二页，2022年，8月28日3.2.2集合的对称差定义3.9

集合A和B的对称差定义为AB＝(A－B)∪(B－A)。例如，若A＝{0，{0}}，则P(A)A＝(P(A)－A)∪(A－P(A))＝{，0，{{0}}，{0，{0}}}。定理3.9设A、B和C为三个集合，则：

(1)AB＝BA。

(2)(AB)C＝A(BC)。

(3)A∩(BC)＝(A∩B)(A∩C)。第二十四页，共八十二页，2022年，8月28日(4)A＝A；AU＝；AA＝；A＝U。

(5)AB＝(A∪B)－(A∩B)。

证明仅证(5)AB＝(A－B)∪(B－A)＝(A∩)∪(B∩)＝((A∩)∪B)∩((A∩)∪)＝(A∪B)∩(∪B)∩(A∪)∩(∪)＝(A∪B)∩(∪)＝(A∪B)－(A∩B)。第二十五页，共八十二页，2022年，8月28日3.2.3广义并、广义交运算定义3.10

集合A的所有元素的元素组成的集合称为A的广义并。符号化表示为：∪A＝{x|B(B∈A∧x∈B)}。定义3.11集合A的所有元素的公共元素组成的集合称为A的广义交。符号化表示为：∩A＝{x|B(B∈Ax∈B)}。例如，若A＝{{a，b，c}，{a，d，e}，{a，f}}，则∪A＝{a，b，c，d，e，f}，∩A＝{a}。由定义可知，广义交和广义并是针对集族而言的，对于非集族来说，其广义交和广义并均为空集。第二十六页，共八十二页，2022年，8月28日定理3.10设A和B为两个集合，则：(1)∪{A}＝A。(2)∪(A∪B)＝(∪A)∪(∪B)。证明

(1)因为x∈∪{A}B(B∈{A}∧x∈B)A∈{A}∧x∈Ax∈A，所以∪{A}＝A(2)因为x∈∪(A∪B)C(C∈A∪B∧x∈C)C((C∈A∨C∈B)∧x∈C)C((C∈A∧x∈C)∨(C∈B∧x∈C))C(C∈A∧x∈C)∨C(C∈B∧x∈C)x∈∪A∨x∈∪Bx∈(∪A)∪(∪B)，所以∪(A∪B)＝(∪A)∪(∪B)。第二十七页，共八十二页，2022年，8月28日定理3.11设A和B为两个集合，则：(1)∩{A}＝A。(2)∩{A，B}＝A∩B。证明

(1)因为x∈∩{A}B(B∈{A}x∈B)A∈{A}x∈Ax∈A，所以∩{A}＝A。(2)因为x∈∩{A，B}C(C∈{A，B}x∈C)(A∈{A，B}x∈A)∧(B∈{A，B}x∈B)x∈A∧x∈Bx∈A∩B，所以∩{A，B}＝A∩B。第二十八页，共八十二页，2022年，8月28日3.2.4集合的文氏图集合之间的相互关系和运算还可以用文氏图来描述，它有助于我们理解问题，有时对解题也很有帮助。在不要求有求解步骤的题目中，我们可以使用文氏图求解，但它不能用于题目的证明。在文氏图中，用矩形表示全集U，矩形内部的点均为全集中的元素，用圆或椭圆表示U的子集，其内部的点表示不同集合的元素，并将运算结果得到的集合用阴影部分表示。图3-1表示了集合的5种基本运算，阴影部分表示经过相应运算得到的。第二十九页，共八十二页，2022年，8月28日第三十页，共八十二页，2022年，8月28日3.3集合的划分与覆盖在集合的研究中，除了进行集合之间的比较外，还要对集合的元素进行分类。这一节将讨论集合的划分问题。定义3.12

设S＝{A1，A2，…，An}是集合A的某些非空子集组成的集合，若＝A，则称S为集合A的一个覆盖。定义3.13

设＝{A1，A2，…，An}是集合A的某些非空子集组成的集合，若＝A，且Ai∩Aj＝(i≠j)，则称为A的一个划分，称中的元素为A的划分块。第三十一页，共八十二页，2022年，8月28日由定义知，划分一定是覆盖，但反之则不然。例如，S＝{{a}，{b，c}，{c}}是A＝{a，b，c}的覆盖，但不是A的划分。例1设有整数集Z，res5(x)表示整数x被5除后所得的余数。令Ai＝{x|x∈Z∧res5(x)＝i∧i∈Z5}，则{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，且Ai∩Aj＝(i≠j)。所以，{A0，A1，A2，A3，A4}是Z的一个划分。第三十二页，共八十二页，2022年，8月28日例2

求集合A＝{a，b，c}的所有不同的划分。解其不同的划分共有5个：1＝{{a}，{b}，{c}}，2＝{{a}，{b，c}}，3＝{{a，c}，{b}}，4＝{{a，b}，{c}}，5＝{{a，b，c}}。定理3.12

设{A1，A2，…，Ar}和{B1，B2，…，Bs}是同一集合A的两种划分，则其所有Ai∩Bj≠组成的集合也是原集合的一种划分。定义3.14

设{A1，A2，…，Ar}和{B1，B2，…，Bs}是同一集合A的两种划分，则称其所有Ai∩Bj≠组成的集合为原来两划分的交叉划分。第三十三页，共八十二页，2022年，8月28日定义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中任意元素Ai∩Bj必有Ai∩BjAi和Ai∩BjBj，故T必是原划分的加细。例3

设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或)的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。第三十四页，共八十二页，2022年，8月28日证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。对任意的a∈U，则a∈Ai或a∈，两者必有一个成立，取Ai为包含元素a的Ai或，则a∈Ai，即有a∈si，于是Usi。又显然有siU，所以U＝si。任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。第三十五页，共八十二页，2022年，8月28日3.4排列与组合3.4.1加法与乘法原理在组合计数的计算和研究中，加法原理和乘法原理是两个最常用也是最基本的原理。加法原理若事件的有限集合S＝S1∪S2∪…∪Sn，且S1、S2、…、Sn两两不相交，则|S|＝|S1|＋|S2|＋…＋|Sn|

乘法原理若事件的有限集合S是依次取自有限集合S1、S2、…、Sn中事件的序列的集合，则|S|＝|S1|×|S2|×…×|Sn|第三十六页，共八十二页，2022年，8月28日例1

求由数字1、2、3、4、5组成的小于1000的数(每个数字都允许重复出现)的个数。解在三位数中，每一个数位上的数字都有5种不同的选取法，由乘法原理知，满足条件的三位数的个数是53个。同理可知，满足条件的二位数和一位数的个数分别为52个和5个。再由加法原理知，满足条件的自然数总共有53＋52＋5＝155个。第三十七页，共八十二页，2022年，8月28日3.4.2排列和组合

1.排列定义3.16集合S有n个元素，从中选取r个元素作有序排列，且在排列中不允许任何元素重复出现，则称这种排列为S的r―无重复排列。当r＝n时，称其为全排列。S的所有r―无重复排列的个数记为P(n，r)或Pnr。定理3.14

n个元素的r―无重复排列的个数为：P(n，r)＝n(n－1)(n－2)…(n－r＋1)。当r＝n时，P(n，n)＝n!

证明在从n个不同的元素中按顺序取出r个元素时，第一个元素有n种不同的选法，第2个元素有n－1种不同的选法，…，第r个元素从剩下的n－r＋1个元素中选取，有n－r＋1种不同的选法。根据乘法原理，顺序选取r个元素共有的不同选取方法数为：P(n，r)＝n(n－1)(n－2)…(n－r＋1)。第三十八页，共八十二页，2022年，8月28日例2

从1、2、…、9中选取数字构成3位数，如要求每个数字都不相同，问共有多少种方法？解从1、2、…、9中选取百位数，共9种选法，再从剩下的数字中选取十位数，共8种选法，最后从剩下的数字中选取个位数，共7种选法。因此，从1、2、…、9中选取数字构成3位数共有9×8×7＝504种方法。定义3.17r―无重复排列可以看作是将选出的r个元素排列在一条直线上的排列，这时也称为r―线状排列。如果把这r个元素排列在一个圆周上，则这种排列称为S的r―圆排列。对两个圆排列，若其中一个圆排列可以由另一个圆排列通过旋转而得到，则认为这两个圆排列在本质上是同一个圆排列。于是有下面的结论成立。第三十九页，共八十二页，2022年，8月28日定理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!/(8×3)＝1680天。第四十页，共八十二页，2022年，8月28日2.组合定义3.18集合S有n个元素，从中选取r个元素，若不考虑它们的排列顺序，且在选取中不允许元素重复出现，称这种选取方式为S的r―无重复组合。S的所有r―无重复组合的个数记为C(n，r)或Cnr。定理3.16n个元素的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)＝＝。第四十一页，共八十二页，2022年，8月28日例4

从1、2、…、300之中任取3个数，使得它们的和能被3整除，问有多少种方法？解把1、2、…、300分成A、B和C三组，A＝{3k＋1|k∈Z}，B＝{3k＋2|k∈Z}，C＝{3k|k∈Z}。任取三个数i、j、k，那么选取是无序的且满足i＋j＋k能被3整除。将选法分为两类：都取自同一组，方法数3C(100，3)。分别取自A、B和C，方法数(C(100，1))3。由加法原则，总取数为3C(100，3)＋(C(100，1))3＝1485100。第四十二页，共八十二页，2022年，8月28日3.4.3排列与组合的生成

1.排列的生成排列的生成算法有词典顺序法、逆序法和递归排序法等。在这里仅介绍词典顺序法。设S＝{1，2，…，n}，(a1，a2，…，an)和(b1，b2，…，bn)是S的两个排列，若存在i∈{1，2，…，n}，使得对一切j＝1，2，…，i有aj＝bj而ai＋1＜bi＋1，则称排列(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)的下一个排列。第四十三页，共八十二页，2022年，8月28日定理3.17对S的两个排列，(b1，b2，…，bn)是(a1，a2，…，an)的下一个排列的充要条件是：(1)存在m∈{1，2，…，n}，使得对一切i＝1，2，…，m－1有ai＝bi，am＜bm，am＜am＋1且am＋1＞am＋2＞…＞an；(2)bm＝min{aj|aj＞am，j＝m＋1，m＋2，…，n}；(3)bm＋1＜bm＋2＜…＜bn。由此定理可建立生成所有排列的算法：步1：置(a1，a2，…，an)＝(1，2，…，n)步2：设已有排列(a1，a2，…，an)，置i＝n；步2.1：若ai＞ai－1，则记m＝i－1，令bm＝min{aj|aj＞am，j＝i，i＋1，…，n}，并将(am，am＋1，…，an)\{bm}第四十四页，共八十二页，2022年，8月28日中的元素由小到大排起来，记这个排列为(bm＋1，am＋2，…，an)。置(a1，a2，…，am－1，am，am＋1，…，an)＝(a1，a2，…，am－1，bm，bm＋1，…，bn)然后返回步2。步2.2：若ai＜ai－1，则当i－1＞1时，置i＝i－1，返回步2.1。当i－1＝1时，算法终止。例5S＝{1，2，3，4}，求其全排列。解123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321。第四十五页，共八十二页，2022年，8月28日2.组合的生成定理3.18(a1，a2，…，ar)和(b1，b2，…，br)是S的两个不同的r－子集，则(b1，b2，…，br)是(a1，a2，…，ar)的下一个子集的充要条件是：(1)存在1≤m≤r，使得对一切i＝1，2，…，m－1有ai＝bi，对一切i＞m有am＝n－r＋i；(2)bm＝am＋1；(3)对于m≤j≤r－1，有bj＋1＝bj＋1。由此定理可建立生成所有子集的算法：步1：设S＝{1，2，…，n}，取(a1，a2，…，ar)＝(1，2，…，r)第四十六页，共八十二页，2022年，8月28日步2：设已有S的r子集(a1，a2，…，ar)，置i＝r；步2.1：若ai＜n－r＋i，则令bi＝ai＋1，并且对j＝i，i＋1，…，r－1，置bj＋1＝bj＋1。然后置(a1，a2，…，ar)＝(a1，a2，…，ai－1，bi，bi＋1，…，br)，然后返回步2。步2.2：若ai＝n－r＋i，则当i＞1时，置i＝i－1，返回步2.1。当i＝1时，算法终止。例6

S＝{1，2，3，4，5，6}，求其所有4元素子集。解

123412351236124512461256134513461356145623452346235624563456。第四十七页，共八十二页，2022年，8月28日3.5归纳原理

3.5.1结构归纳原理设集合A是归纳定义的集合，现欲证A中所有元素具有性质P，即证：对于任意x∈A有P(x)为真。可进行如下证明：

(1)(归纳基础)证明归纳定义基础条款中规定的A的基本元素x均使P(x)为真。

(2)(归纳推理)证明归纳定义的归纳条款是“保性质P的”。即在假设归纳条款中已确定元素x1、x2、…、xn使P(xi)(i＝1，2，…，n)真的前提下，证明用归纳条款中的操作g所生成元素g(x1，x2，…，xn)依然具有性质P，即P(g(x1，x2，…，xn))为真。第四十八页，共八十二页，2022年，8月28日由于A仅由(1)和(2)条款所确定的元素组成，因此当上述证明过程完成时，“A中所有元素具有性质P”得证。这种推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法。为区别通常所说的数学归纳法，它又称为“结构归纳法”。数学归纳法是其一种特例。第四十九页，共八十二页，2022年，8月28日3.5.2数学归纳原理将上述原理应用到自然数集上进行归纳推理，就是我们所说的数学归纳法。

1.第一数学归纳法用第一数学归纳法证明所有自然数具有性质P时，只要如下推理：

(1)归纳基础：证P(0)真，即证明数0具有性质P。

(2)归纳过程：对任意k(≥0)，假设P(k)真(归纳假设“k满足性质P”)时，推出P(k＋1)真。

(3)结论：所有自然数具有性质P。第五十页，共八十二页，2022年，8月28日例1

用归纳法证明：对任意的自然数n，有(0＋1＋2＋…＋n)2＝03＋13＋23＋…＋n3。证明当n＝0时，n2＝03。假设n＝k时，(0＋1＋2＋…＋k)2＝03＋13＋23＋…＋k3，那么n＝k＋1时，(0＋1＋2＋…＋k＋k＋1)2＝(0＋1＋2＋…＋k)2＋2(0＋1＋2＋…＋k)(k＋1)＋(k＋1)2

＝03＋13＋23＋…＋k3＋k(k＋1)2＋(k＋1)2＝03＋13＋23＋…＋k3＋(k＋1)3所以，对任意自然数结论成立。第五十一页，共八十二页，2022年，8月28日2.第二数学归纳法用第二数学归纳法证明所有自然数具有性质P时，只要如下推理：(1)归纳基础：证P(0)真，即证明数0具有性质P。(2)归纳过程：对任意k(≥0)，假设P(i)真，k＞i≥0(归纳假设“0，1，…，k－1满足性质P”)时，推出P(k)真。(3)结论：所有自然数具有性质P。例2

有数目相同的两堆棋子(每堆棋子数为n)，甲、乙两人玩取棋子游戏。规定两人轮流取棋子，每次两人取子数相同，不能不取，也不能同时在两堆中取子，取得最后一枚棋子者为胜者。求证：后取者必胜。第五十二页，共八十二页，2022年，8月28日证明不妨设甲为先取者，乙为后取者。当n＝1时，两堆各有一枚棋子，甲必先从一堆中取走一枚棋子，余下最后一枚棋子必被乙取走，乙胜。假设n＜k时乙必胜。下证n＝k时也是乙必胜。设第一轮取子时，甲从一堆中取走r枚棋子，余下k－r＜k枚棋子，那么，乙从另一堆中也取走r枚棋子，亦留下k－r＜k枚棋子。若(1)r＝k，那么乙取走最后一枚棋子，乙胜。(2)1＜r＜k，那么1＜k－r＜k。对留下的两堆棋子，每一堆为k－r枚，由归纳假设，在以后甲乙的搏奕中乙必胜。因此全局也是乙必胜。第五十三页，共八十二页，2022年，8月28日3.6容斥原理和抽屉原理3.6.1容斥原理设集合A是归纳定义的集合，现欲证A中所有元素具有性质P，即证：对于任意x∈A有P(x)为真。可进行如下证明：

(1)(归纳基础)证明归纳定义基础条款中规定的A的基本元素x均使P(x)为真。

(2)(归纳推理)证明归纳定义的归纳条款是“保性质P的”。即在假设归纳条款中已确定元素x1、x2、…、xn使P(xi)(i＝1，2，…，n)真的前提下，证明用归纳条款中的操作g所生成元素g(x1，x2，…，xn)依然具有性质P，即P(g(x1，x2，…，xn))为真。第五十四页，共八十二页，2022年，8月28日集合的运算，可用于有限个元素的计数问题。在有限集的元素计数问题中，容斥原理有着广泛的应用。定理3.19(容斥原理)

对有限集合A和B，有|A∪B|＝|A|＋|B|－|A∩B|。证明因为A∪B＝B∪(A－B)且B∩(A－B)＝，所以|A∪B|＝|B|＋|A－B|。又因为A＝(A－B)∪(A∩B)且(A－B)∩(A∩B)＝，所以|A|＝|A－B|＋|A∩B|。故|A∪B|＝|A|＋|B|－|A∩B|。定理3.20

推广到n个集合A1，A2，…，An的情形，有：|A1∪A2∪…∪An|＝∑i|Ai|－∑i＜j|Ai∩Aj|＋∑i＜j＜k|Ai∩Aj∩Ak|－…＋(－1)n－1|A1∩A2∩…∩An|。第五十五页，共八十二页，2022年，8月28日例1

一个班有50个学生，在第一次考试中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得95分的有多少人？解设A和B分别表示在第一次和第二次考试中得95分的学生的集合。则：|A|＝26，|B|＝21，＝17。于是＝50－＝50－(|A|＋|B|－|A∩B|)，从而|A∩B|＝－50＋|A|＋|B|＝17－50＋26＋21＝14。所以，两次考试都得95分的有14人。例2

从{1，2，3，4，5，6，7，8，9}中取7个不同的数字构成7位数，如不允许5和6相邻，总共有多少种方法？第五十六页，共八十二页，2022年，8月28日解任取7个不同的数字构成7位数的个数为＝9!/2，5和6相邻的个数为6！(2！)＝6×7！，根据容斥原理，总共有9!/2－6×7!＝151200种方法。例3

某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：第五十七页，共八十二页，2022年，8月28日|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，

|B∩C|=5,|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不会打这三种球的共5人。在不要求严格步骤的情况下，以上各题也可通过文氏图的方法来求解。下面以例3加以说明：设A、B、C分别表示会打排球、网球和篮球的学生集合。该问题的文氏图如图3-2所示。由题意可得：第五十八页，共八十二页，2022年，8月28日|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根据上面各等式，依次求得：第五十九页，共八十二页，2022年，8月28日|I1|＝5，|I2|＝4，|I3|＝5，|I4|＝1，|I5|＝2，|I6|＝3，|I7|＝0。所以，＝25－|A∪B∪C|＝25－(|I1|＋|I2|＋|I3|＋|I4|＋|I5|＋|I6|＋|I7|)＝25－(5＋4＋5＋1＋2＋3＋0)＝5。故，不会打这三种球的共5人。第六十页，共八十二页，2022年，8月28日3.6.2抽屉原理(鸽巢原理)

抽屉原理是一个十分基本、非常重要、应用极其广泛的数学原理，是解决数学中的一类存在性问题的基本工具。定理3.21(抽屉原理)(1)把多于n个元素的集合S分成n个子集S1、S2、…、Sn的并集，那么至少存在一个集合Si，它包含S中的两个或两个以上的元素。

(2)把多于mn个元素的集合S分成n个子集S1、S2、…、Sn的并集，那么至少存在一个集合Si，它包含S中的m＋1或m＋1以上的元素。证明仅证(2),反证法。

(2)若结论不成立，则对于任意子集Si，有|Si|≤m，于是|S|≤|S1|＋|S2|＋…＋|Sn|≤mn，矛盾。第六十一页，共八十二页，2022年，8月28日例3

在从1到2n的整数中，任意选取n＋1个数，证明在这n＋1个数中总存在两个数，使得其中一个数是另一个的倍数。证明设S＝{1，2，…，2n}，Si＝{a|a∈S，且存在k∈N使得a＝2k(2i－1)}，i＝1，2，…，n。于是S＝S1∪S2∪…∪Sn，则n＋1个数中必有两个数在S的同一个子集Si中，这两个数中的一个数是另一个的偶数倍。例4

在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形(可能是退化的)面积不超过1/8。证明把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形(可能是退化的)面积不超过小正方形的一半，即1/8。第六十二页，共八十二页，2022年，8月28日3.7递推关系

3.7.1递推关系的概念

有些计数问题往往与求一个数列的通项有关。但在一些复杂的特定条件下要直接求出这个数列的通项公式，有时十分困难。而在同样的条件下，写出该数列相邻项之间的关系，再利用一定的方法和技巧，却往往能很容易的得到所要的结论。

例1

斐波那契数列(Fibonacci)问题假定一对兔子两个月成熟后，每月生一对兔子。按照假定，一对刚出生的兔子在n个月后，共有多少对兔子？解设第n个月的兔子数为Fn，由题意得F0＝1F1＝1Fn＝Fn－1＋Fn－2，n≥2第六十三页，共八十二页，2022年，8月28日例2汉诺塔(Hanoi)问题有三根立柱A、B、C以及n个大小不同的圆盘套在立柱A上，大的圆盘在下面，小的圆盘在上面，构成一个塔形。现在要把这n个圆盘移到立柱B上。可以利用这三根立柱，每次只能移动一个圆盘，但不允许将它放在较小的圆盘上，问最少需移动多少次？解令Hn为完成这样的一次移动至少必须移动圆盘的次数。为了把n个圆盘从立柱A移到立柱B，可先将n－1个圆盘从立柱A移到立柱C，留下最大的圆盘，移动的次数为Hn－1；然后再将最大的圆盘移动到立柱B，移动1次；最后将n－1个圆盘从立柱C移到立柱B，移动次数为Hn－1。第六十四页，共八十二页，2022年，8月28日于是有Hn＝2Hn－1＋1，n≥2，其中H1＝1。以上的例子有一个共同的特点，即从我们在计数问题所得出的数列中，它的一般项可用它自身数列中的前面若干项来表达。这样，从给定的初始值出发，利用所建立的关系式可以依次算出数列中的每一项。我们称这些关系式为递推关系。下面我们介绍递推关系的几种解法。第六十五页，共八十二页，2022年，8月28日1.递推关系的生成函数解法设{a0，a1，…，an，…}为一个无穷数列，我们称f(t)＝a0＋a1t＋…＋antn＋…为该数列的生成函数。例3

数列{1，1，…，1，…}的生成函数为＝1＋t＋…＋tn＋…。将递推关系代入数列的生成函数的系数中去，通过计算可以得到生成函数的显式，然后再将它展开成幂级数就可求得数列的通项。例4

斐波那契数列问题解设F(x)＝为斐波那契数列的生成函数，则有第六十六页，共八十二页，2022年，8月28日F(x)＝F0＋F1x＋＝1＋x＋＝1＋x＋x＋xn＝1＋x＋x(F(x)－1)＋x2F(x)从上面关系式可以解出F(x)＝＝＝＝比较等式两边xn的系数，得到Fn＝。第六十七页，共八十二页，2022年，8月28日2.常系数线性齐次递推关系的解法我们把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(其中H(n)、H(n－1)、…、H(n－k)是n的函数)的递推关系式称为常系数线性齐次递推关系，并称xk＋b1xk－1＋b2xk－2＋…＋bk＝0为其特征方程，它的根称为其特征根。在使用特征根方法求解递推关系时要用到下面三个定理，其证明参见相关文献。定理3.22

设q为非零的实数或复数，则H(n)＝qn是递推关系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解当且仅当q是它的一个特征根。第六十八页，共八十二页，2022年，8月28日定理3.23

设q1、q2、…、qk为非零的实数或复数，则H(n)＝C1q1n＋C2q2n＋…＋Ckqkn(C1、C2、…、Ck是确定的常数)是递推关系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解当且仅当q1、q2、…、qk是它的k个不同的特征根。定理3.24

设q1、q2、…、qk为非零的实数或复数，它们是递推关系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的特征方程的t(t≤k)个不同的特征根，各有e1、e2、…、et重。则递推关系式的一般解是H(n)＝H1(n)＋H2(n)＋…＋Ht(n)，其中Hi(n)＝C1qin＋C2nqin＋…＋qin(i＝1，2，…，t；C1，C2，…，为确定的常数)。例6

斐波那契数列问题第六十九页，共八十二页，2022年，8月28日解递推关系Fn＝Fn－1＋Fn－2的特征方程为x2―x―1＝0，其解为：x1＝，x2＝。于是递推关系的通解为Fn＝C1＋C2。将F0＝1，F1＝1代入得C1＋C2＝1C1＋C2＝1解上述式子得：C1＝，C2＝－。于是Fn＝。第七十页，共八十二页，2022年，8月28日3.常系数线性非齐次递推关系的解法我们把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝f(n)(其中H(n)、H(n－1)、…、H(n－k)是n的函数，f(n)是n的多项式或an)的递推关系式称为常系数线性非齐次递推关系。这类递推关系的求解可通过将非齐次递推关系归约为齐次递推关系的方法来求解。下面我们通过一个例子来说明。例7汉诺塔问题解递推关系Hn＝2Hn－1＋1对应的齐次方程的通解为Hn＝C2n。利用常系数变易法作代换Hn＝an2n可得an＝an－1＋，从而an＝a0＋＋＋…＋＝a0＋1－，Hn＝an2n＝(1＋a0)2n－1。由H1＝1得a0＝1。因此，Hn＝2n－1。第七十一页，共八十二页，2022年，8月28日3.8集合论在命题逻辑中的应用3.8.1命题逻辑中的集合表示首先引入以下几个符号：

(A)：命题公式A的主析取范式中所有小项mi的下标组成的集合。［A］：命题公式A的主合取范式中所有大项Mi的下标组成的集合。令U＝{0，1，2，…，2n－1}，则U为n个命题变元所组成的所有小项(或大项)对应的下标组成的集合。下面，我们先通过一个例子来说明命题公式的主范式可以用集合来表示，然后证明命题公式的主范式和推理都可通过集合运算而得到。第七十二页，共八十二页，2022年，8月28日例1

求命题公式P∧Q与P∨Q的主析取范式。解命题公式P∧Q与P∨Q的真值表如表3-1所示：表3-1于是(P∧Q)＝{3}，(P∨Q)＝{1，2，3}。将上述例子推广到含有n个命题变元的命题公式中，则有以下的重要结论。第七十三页，共八十二页，2022年，8月28日定理3.25设V＝{P1，P2，…，Pn}，A是命题公式，其包含的命题变元均在集合V中，则[A]＝U－(A)