离散数学第三章课件ppt

1、3.1 集合的概念与表示法集合的概念与表示法3.2 集合的运算与性质集合的运算与性质 3.4 排列与组合排列与组合3.3 集合的划分与覆盖集合的划分与覆盖 3.5 归纳原理归纳原理3.6 容斥原理和抽屉原理容斥原理和抽屉原理3.8 集合论在命题逻辑中的应用集合论在命题逻辑中的应用 3.7 递推关系递推关系3.1集合的概念与表示法集合的概念与表示法 3.1.1 集合的概念集合的概念3.1.2 集合的表示法集合的表示法 3.1.3 集合的包含与相等集合的包含与相等 3.1.4 空集、集族、幂集和全集空集、集族、幂集和全集3.1.5 有限幂集元素的编码表示有限幂集元素的编码表示3.1.1 集合的概念

2、集合的概念 通常用大写字母通常用大写字母(如如A、B等等)表示集合，用小写字表示集合，用小写字母母(如如a、b)表示集合中的元素。给定一个集合表示集合中的元素。给定一个集合A和一和一个元素个元素a，可以判定，可以判定a是否在集合是否在集合A中。如果中。如果a在在A中，中，我们称我们称a属于属于A，记为，记为aA。否则，称。否则，称a不属于不属于A，记，记为为a A。 一般我们把一些确定的互不相同的对象的一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。全体称为集合，集合中的对象称为集合的元素。 例如，某大学计算机系的全体学生、所有自然例如，某大学计算机系的全体学生、

3、所有自然数等都是集合。数等都是集合。 说明：一个集合是作为整体识别的、确定的、互相区别的一些事物的全体。严格地讲，这只是一种描述，不能算是集合的定义。类似于几何中的点、线、面等概念，在朴素集合论中，集合也是一种不加定义而直接引入的最基本的原始概念（一给出定义就要引入悖论（Paradox）。而集合论中的其他概念，则都是从它出发给予了严格的定义。 集合元素的特征：集合元素的特征：确定性、互异性、无序确定性、互异性、无序性和抽象性。性和抽象性。 确定性：一旦给定了集合确定性：一旦给定了集合A，对于任意元素，对于任意元素a，可准确地判定可准确地判定a是否在是否在A中，这是明确的。中，这是明确的。 互异

4、性：集合中的元素之间是彼此不同的。即集互异性：集合中的元素之间是彼此不同的。即集合合a，b，b，c与集合与集合a，b，c是一样的。是一样的。 无序性：集合中的元素之间没有次序关系。即集无序性：集合中的元素之间没有次序关系。即集合合a，b，c与集合与集合c，b，a是一样的。是一样的。 抽象性：集合中的元素是抽象的，甚至可以是集抽象性：集合中的元素是抽象的，甚至可以是集合。如合。如A1，2，1，2，其中，其中1，2是集合是集合A的元的元素。素。 集合中元素的个数称为集合的基数，记为集合中元素的个数称为集合的基数，记为|A|。当当|A|有限时，称有限时，称A为有限集合为有限集合（Finite set

5、）， ；否则，；否则，称称A为无限集合为无限集合（Infinite set） 。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。3.1.2 集合的表示法集合的表示法1.列举法 列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。 例如：Aa，b，c，B0，1，2，。 列举法一般用于有限集合和有规律的无限集合。2.谓词表示法 谓词表示法是用谓词来概括集合中元素的属性。通常用x|p(x)来表示具有性质p的一些对象组成的集合。 例如：x|1x6x

6、为整数为由1、2、3、4、5、6组成的集合。3.1.3 集合的包含与相等集合的包含与相等 外延性原理：两个集合外延性原理：两个集合A和和B是相等的，是相等的，当且仅当它们有相同的元素。记为当且仅当它们有相同的元素。记为AB。 例如，若A2，3，B小于4的素数，则AB。 定义定义3.1 设设A和和B为两个集合，若对于任意为两个集合，若对于任意的的aA必有必有aB，则称，则称A是是B的的子集，子集，也称也称A包含于包含于B或或B包含包含A，记作记作A B。如果如果B不包含不包含A，记作，记作A B。B包含包含A的符号化表示为：的符号化表示为：A Bx(xAxB)。 定理定理3.1 集合集合A和和B

7、相等当且仅当这两个集相等当且仅当这两个集合互为子集。即：合互为子集。即：ABA BB A。 例如，若A1，2，3，4，B1，2，C2，3，则BA且CA，但C B。证证明明 若AB，则A和B具有相同的元素，于是x(xAxB)、x(xBxA)都为真，即AB且BA。 反之，若AB且BA，假设AB，则A与B元素不完全相同。不妨设有某个元素xA但xB，这与AB矛盾，所以AB。定理定理3.2 设设A、B和和C是三个集合，则：是三个集合，则：(1)A A。(2)A BB CA C。证证明明(1)由定义显然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定义定义3

8、.2 设设A和和B是两个集合，若是两个集合，若A B且且B中中至少有一个元素至少有一个元素b使得使得b A，则称，则称A是是B的的真子集，真子集，也称也称A真包含于真包含于B或或B真包含真包含A，记作，记作A B。否则，否则，记作记作A B。B真包含真包含A的符号化表示：的符号化表示：A Bx(xAxB) x(xBx A)。若两个集合若两个集合A和和B没有公共元素，我们说没有公共元素，我们说A和和B是是不相交的。不相交的。例如，若Aa，b，c，d，Bb，c，则B是A的真子集，但A不是A的真子集。注：与表示元素和集合的关系，而、与表示集合和集合的关系。例如，若A0，1，B0，1，0，1，则AB且

9、AB。定理定理3.3 设设A、B和和C是三个集合，则是三个集合，则(1) (A A)。 (2)A B(B A)。(3)A BB CA C。证证明明仅证(2)和(3)(2)AB x(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(xAxBxBxC)x(xAxC)(x(xCxA)AC。(x(xBxC)x(xCxB)(x(xBxA)x(xCxB)定义定义3.3 没有任何元素的集合称为没有任何元素的集合称为空集，记空集，记作作

10、。以集合为元素的集合称为以集合为元素的集合称为集族集族。3.1.4 空集、集族、幂集和全集空集、集族、幂集和全集例如，x|xx是空集；xx是某大学的学生社团是集族。定理定理3.4 空集是任何集合的子集。空集是任何集合的子集。任给集合A，则Ax(xxA)。由于x是假的，所以x(xxA)为真，于是有A为真。证证明明特别要注意与的区别，是不含任何元素的集合，是任意集合的子集，而是含有一个元素的集合。 定义定义3.4 一个集合一个集合A的所有子集组成的集合的所有子集组成的集合称为称为A的幂集的幂集（Power Set） ，记作记作P(A)或或2A。推论推论 空集是惟一的。空集是惟一的。 对于任一集合A

11、，我们称空集和其自身A为A的平凡子集。例例1 1 求幂集P()、P()、P(，)、P(1，2，3)。解解P()P()，P(，)，P(1，2，3)，1，2，3， 1，2，3。定理定理3.5 若若|A|n，则，则|P(A)|2n。证明证明 因为A的m个元素的子集的个数为Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理定理3.6 设设A和和B是两个集合，则：是两个集合，则：(1)BP(A)B A。(2)A BP(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)。定义定义3.5 所要讨论的集合都是某个集合的

12、所要讨论的集合都是某个集合的子集，称这个集合为子集，称这个集合为全集全集（Universal set），记作记作U或或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题时，可把整个坐标平面取作全集。 Assignments（作业） 第74页: 1（偶数小题），2（偶数小题），3（偶数小题）3.2 集合的运算与性质集合的运算与性质3.2.1 集合的交、并、补集合的交、并、补 3.2.2 集合的对称差集合的对称差 3.2.3 广义并、广义交运算广义并、广义交运算3.2.4 集合的文氏图集合的文氏图3.2.1集合的

13、交、并、补集合的交、并、补 定义定义3.6 设设A和和B为两个集合，为两个集合，A和和B的的交集交集AB （Intersection） 、并集、并集AB （Union）分别定义如下：分别定义如下： ABx|xAxB ABx|xAxB 例如，若A1，2，3，B1，4，则AB1，AB1，2，3，4。集合的交与并可以推广到n个集合的情况，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn例例1 设A和B为两个集合，且AB，则ACBC。 对任意的xAC，则有xA且xC。而AB，由xA得xB，则xB且xC，从而xBC。所以，ACBC。例例2 设A和B为两个集合，则ABABBABA。

14、反之，若ABB，因AAB，所以AB。 证证明明证证明明 对任意的xAB，则xA或xB。又AB，所以xB，于是ABB。又显然有BAB，故ABB。同理可证ABABA。 定义定义3.7 设设A和和B为两个集合，所有属于为两个集合，所有属于A而不而不属于属于B的元素组成的集合称为的元素组成的集合称为B对于对于A的的补集补集( C o m p l e m e n t )， 或 相 对 补 。或 相 对 补 。 记 作记 作 A B x|xAx B。AB也称为也称为A和和B的差集的差集(Difference)。 例如，若A1，2，3，B1，4，则AB2，3，BA4。 定义定义3.8 设设U为全集，集合为全

15、集，集合A关于关于U的补集的补集UA称为集合称为集合A的的绝对补绝对补或或余集，余集，记为记为Ac。即即:Ac x|xU且且x A。例例3 设A和B为两个集合，则ABABc 。因为xAB证证明明xAxBxAxBc所以ABABc。xABc定理定理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(

16、6)零律零律 AUU，A(7)互补律互补律 AAc U，AAc以上等式的证明主要用到命题演算的等价式，即欲证集合AB，只需证明xAxB。(8)吸收律吸收律 A(AB)A，A(AB)A(9)德德摩根律摩根律 (A B)c Ac Bc (AB)cAcBc A(BC)(AB)(AC) A(BC)(AB)(AC)(10)双重否定律双重否定律 (Ac)c A 定理定理3.8 任意集合任意集合A和和B，BAc ABU且且AB。证证明明如BAc， 则ABAAcU，ABAAc。反之，若ABU且AB，则BBUB(AAc)(BA)(BAc)(BAc) (AAc)(BAc)(AB)AcUAcAc例例4 证明A(BC

17、)(AB)(AC)。证证明明因为xA(BC) xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)所以A(BC)(AB)(AC)。例例5 证明(AB)cAcBc。因为x(AB)c证证明明xAcBcxABxAxBxAcxBc所以(AB)cAcBc。3.2.2 集合的对称差集合的对称差 定义定义3.9 集合集合A和和B的的对称差对称差(Symmetric Difference)定义为定义为A B(AB)(BA)。 例如，若A0，0，则P(A)A(P(A)A)(AP(A)，0，0，0，0。定理定理3.9 设设A、B和和C为三个集合，则：为三个集合，则： (1)

18、A BB A。 (2)(A B) CA (B C)。 (3)A(B C)(AB) (AC)。 (4)AA；A UAc； A A；A AcU。 (5)A B(AB)(AB)。 证证明明仅证(5)： A B(AB)(AB) AB(AB)(BA)(ABc)(BAc)(ABc)B)(ABc)Ac)(AB)(AB)。(AB)(AcBc)3.2.4 集合的文氏图集合的文氏图 在文氏图中，用矩形表示全集U，矩形内部的点均为全集中的元素，用圆或椭圆表示U的子集，其内部的点表示不同集合的元素，并将运算结果得到的集合用阴影部分表示。图3-1表示了集合的5种基本运算，阴影部分表示经过相应运算得到的。 集合之间的相互

19、关系和运算还可以用文氏图来描述，它有助于我们理解问题，有时对解题也很有帮助。在不要求有求解步骤的题目中，我们可以使用文氏图求解，但它不能用于题目的证明。 Assignments（作业） 3.3集合的划分与覆盖集合的划分与覆盖 定义定义3.13 设设 A1，A2，An是集合是集合A的某些非空子集组成的集合，若的某些非空子集组成的集合，若A1AnA，且且AiAj(ij)，则称，则称 为为A的一个的一个划分划分（Partition），），称称 中的元素为中的元素为A的的划分块划分块(Block)。定义定义3.12 设设SA1，A2，An是集合是集合A的的某些非空子集组成的集合，若某些非空子集组成的集

20、合，若 A1A2AnA，则称则称S为集合为集合A的一个的一个覆盖（覆盖（Overlay）。）。由定义知，划分一定是覆盖，但反之则不然。例如，Sa，b，c，c是Aa，b，c的覆盖，但不是A的划分。例例1 1 求集合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是同一集

21、合是同一集合A的两种划分，则称其的两种划分，则称其所有所有AiBj组成的集合为原来两划分的组成的集合为原来两划分的交叉交叉划分。划分。定义定义3.15 给定给定A的两个划分的两个划分A1，A2，Ar和和B1，B2，Bs，若对于每个，若对于每个Aj都有都有Bk使得使得Aj Bk，则称，则称A1，A2，Ar为为B1，B2，Bs的的加细。加细。定理定理3.13 任何两种划分的交叉划分，都是任何两种划分的交叉划分，都是原来各划分的一种加细。原来各划分的一种加细。证明 设A1，A2，Ar和B1，B2，Bs的交叉划分为T，对于T中任意元素AiBj必有AiBjAi和AiBjBj，故T必是原划分的加细。 As

22、signments（作业） 第75页: 14（偶数小题）3.6容斥原理和抽屉原理容斥原理和抽屉原理 3.6.1 容斥原理容斥原理3.6.2 抽屉原理抽屉原理3.6.1容斥原理容斥原理 定理定理3.19(容斥原理容斥原理) 对有限集合对有限集合A和和B，有，有|AB|A|B|AB|。因为因为ABB(AB)且且B(AB)证明又又A(AB)(AB)且且(AB)(AB)所以所以|AB|B|AB|。所以所以|A|AB|AB|。故故|AB|A|B|AB| 。 定理定理3.20 推广到推广到n个集合个集合A1，A2，An的情形，有：的情形，有： |A1A2An| i|Ai|ij|AiAj| ijk|AiAj

23、Ak| (1)n1|A1A2An|。 例例1 一个班有50个学生，在第一次考试中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得95分的有多少人？设A和B分别表示在第一次和第二次考试中得95分的学生的集合。解解则：|A|26，|B|21，|(AB)c|17。于是 |(AB)c| =50- |AB|=50-(|A|+|B|-|AB|)所以，两次考试都得95分的有14人。从而|AB|=17-50+|A|+|B|=17-50+26+21=14。 例例2 从1，2，3，4，5，6，7，8，9中取7个不同的数字构成7位数，如不允许5和6相邻，总

24、共有多少种方法？任取7个不同的数字构成7位数的个数为P79=9!/2，5和6相邻的个数为 6 x 2 x P57 67！，根据容斥原理，总共有9!/267!151200种方法。解解 例例3 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：|A|12，|B|6，|C|14，|AC|6， |BC|=5|ABC|2，|(AC)B|6。所以|(AB)|3。 因为|(AC)B|=|(AB)(BC)|=|(AB)|(BC

25、)|ABC|(AB)|526 于是|ABC|=12+6+14-6-5-3+2=20，|(ABC)c|=25-20=5。故，不会打这三种球的共5人。3.6.2 抽屉原理抽屉原理(鸽巢原理鸽巢原理) 抽屉原理是一个十分基本、非常重要、应用极其广泛的数学原理，是解决数学中的一类存在性问题的基本工具。 (2)把多于把多于mn个元素的集合个元素的集合S分成分成n个子集个子集S1、S2、Sn的并集，那么至少存在一个的并集，那么至少存在一个集合集合Si，它包含，它包含S中的中的m1或或m1以上的元以上的元素。素。 定理定理3.21(抽屉原理抽屉原理) (1)把多于把多于n个元素的集合个元素的集合S分成分成n个子集个子集S1、S2、Sn的并集，那