离散数学离散第1章集合论

1、广东工业大学计算机学院广东工业大学计算机学院离散数学离散数学离离 散散 数数 学学蔡瑞初蔡瑞初20222022年年3 3月月11 11日星期五日星期五22022-3-112022-3-11关于我关于我蔡瑞初蔡瑞初研究方向：搜索引擎、数据挖掘、生物信息学研究方向：搜索引擎、数据挖掘、生物信息学实验室：实验室：321321实验室实验室EmailEmail：32022-3-112022-3-11关于你们关于你们态度决定一切！态度决定一切！精进、持戒、忍辱、布施、禅定、智慧42022-3-112022-3-11关于离散数学关于离散数学一切计算机学科的基础！一切计算机学科的基础！哲学哲学数学数学语言学语

2、言学。离散离散算法算法网络网络。We are We are here!here!52022-3-112022-3-11关于成绩关于成绩 出勤（出勤（10-15%10-15%）考试考试 + + 态度态度70%-80% 70%-80% 作业（作业（10-15%10-15%） 62022-3-112022-3-11第一篇第一篇 预备知识预备知识第一章第一章 集合论集合论72022-3-112022-3-111.0 1.0 内容提要内容提要集合的概念集合的概念1集合的表示方法集合的表示方法2集合间的关系集合间的关系3集合的运算集合的运算4无限集合无限集合5集合的概念集合的概念1集合的表示方法集合的表示

3、方法2特殊集合特殊集合582022-3-112022-3-111.1 1.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 集合的概念集合的概念及集合间关系及集合间关系2 2 集合的表示集合的表示3 3 集合运算及集合运算及定律定律4 4 幂集幂集P(A)P(A) 31 1 集合的递归集合的递归指定法表示指定法表示2 2 了解无限集了解无限集的基本概念的基本概念21 1 集合的归纳集合的归纳法表示法表示2 2 集合的对称集合的对称差运算差运算 92022-3-112022-3-111.2 1.2 集合集合一、集合的概念一、集合的概念集合集合（SETSET）由指定范围

4、内的某些特定对象由指定范围内的某些特定对象聚集在一起构成。聚集在一起构成。指定范围内的每一个对象称为这个指定范围内的每一个对象称为这个集合的元素集合的元素(element)(element)中国中国所有真皮沙发所有真皮沙发的聚集的聚集指定指定范围范围特定对特定对象象102022-3-112022-3-11二、集合的记法二、集合的记法通常用带通常用带( (不带不带) )标号的大写字母标号的大写字母A A、B B、C C、.、A A1 1、 B B1 1 、C C1 1 、.、X X、Y Y、Z Z、.表示表示集合集合； 通常用带（不带）标号的小写字母通常用带（不带）标号的小写字母a a、b b、

5、c c、.、a a1 1、 b b1 1 、c c1 1 、.、x x、y y、z z、.表示表示元素元素。112022-3-112022-3-11固定的符号固定的符号0, 1, 2, 自然数集合自然数集合N, -2, -1, 0, 1, 2, 整数集合整数集合 Zp/q,p,q是整数，且是整数，且q0 有理数集合有理数集合 Q 实数集合实数集合 R复数集合复数集合 C122022-3-112022-3-111.2.1 1.2.1 集合的表示方法集合的表示方法 集合是由它包含的元素完全确定的，为了表示集合是由它包含的元素完全确定的，为了表示一个集合，通常有：一个集合，通常有： 枚举法枚举法 隐

6、式法（叙述法）隐式法（叙述法） 归纳法归纳法 递归指定递归指定文氏图文氏图132022-3-112022-3-111 1、枚举法（显示法）、枚举法（显示法）-列出集合中全部元素或部分元素的方法叫列出集合中全部元素或部分元素的方法叫枚举法枚举法例例1.2.11.2.1适用场景：适用场景：u一个集合仅含有限个元素一个集合仅含有限个元素u一个集合的元素之间有明显关系一个集合的元素之间有明显关系 142022-3-112022-3-11枚举法的优缺点枚举法的优缺点是一种是一种显式表示法显式表示法优点优点：具有：具有透明性透明性缺点缺点：在表示具有某种特性的集合或集合中元：在表示具有某种特性的集合或集合

7、中元素过多时受到了一定的素过多时受到了一定的局限局限，而且，从计算机，而且，从计算机的角度看，显式法是一种的角度看，显式法是一种“静态静态”表示法，如表示法，如果一下子将这么多的果一下子将这么多的“数据数据”输入到计算机中输入到计算机中去，那将占据大量的去，那将占据大量的“内存内存”。152022-3-112022-3-112 2、隐式法（叙述法）、隐式法（叙述法）通过刻画集合中通过刻画集合中元素所具备的某种特性元素所具备的某种特性来表示集来表示集合的方法称为叙述法（隐式法）合的方法称为叙述法（隐式法）一般表示方法：一般表示方法：P Px|x|P(x)P(x) 适用场景：适用场景：一个集合含有

8、很多或无穷多个元素；一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画的共同特征一个集合的元素之间有容易刻画的共同特征其其突出优点突出优点是原则上不要求列出集合中全部元素，是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性。而只要给出该集合中元素的特性。代表元代表元X X所具有的所具有的性质性质p p162022-3-112022-3-11例例1.2.21.2.2（1 1）A = x|xA = x|x是是“discrete mathematicsdiscrete mathematics”中中的所有字母的所有字母 ；（2 2）Z = x|xZ = x|x是一个整数是一个整数

9、 ； （3 3）S = x|xS = x|x是整数，并且是整数，并且x x2 21 = 01 = 0； （4 4）Q Q+ + = x|x = x|x是一个正有理数是一个正有理数 。172022-3-112022-3-113 3、归纳法、归纳法归纳法是通过归纳定义集合，主要由三部分组成：归纳法是通过归纳定义集合，主要由三部分组成：第一部分：第一部分：基础。基础。指出某些最基本的元素属于某集指出某些最基本的元素属于某集合；合；第二部分：第二部分：归纳。归纳。指出由基本元素造出新元素的方指出由基本元素造出新元素的方法；法；第三部分：第三部分：极小性。极小性。指出该集合的界限。指出该集合的界限。注意

10、：第一部分注意：第一部分和和第二部分第二部分指出一个集合指出一个集合至少包括至少包括的元素的元素，第三部分第三部分指出一个集合指出一个集合至多要包含的元素至多要包含的元素182022-3-112022-3-11例例1.2.31.2.3集合集合A A按如下方式定义：按如下方式定义：（1 1）0 0和和1 1都是都是A A中的元素；中的元素；（2 2）如果）如果a, ba, b是是A A中的元素，则中的元素，则ab, baab, ba也是也是A A中的中的元素；元素；（3 3）有限次使用）有限次使用(1)(1)、(2)(2)后所得到的字符串都是后所得到的字符串都是A A中的元素。中的元素。试指出其

11、定义方式。并举出集合试指出其定义方式。并举出集合A A中的中的3 3个元素个元素192022-3-112022-3-114 4、递归指定集合、递归指定集合通过通过计算规则计算规则定义集合中的元素定义集合中的元素例例1.2.41.2.4 设设 a a0 0 1 1， a ai+1 i+1 2a2ai i （i i 0 0） 定义定义S Saa0 0 ，a a1 1 ，a a2 2 ，. aak k | k| k 0 0 ，试写出集合试写出集合S S中的所有元素。中的所有元素。 202022-3-112022-3-115 5、文氏图解法、文氏图解法 文氏图解法文氏图解法是一种利用平面上点的集合作成

12、的是一种利用平面上点的集合作成的对集合的图解。一般用平面上的对集合的图解。一般用平面上的圆形或方形圆形或方形表示表示一个集合。一个集合。 AA212022-3-112022-3-111.2.2 1.2.2 集合与元素的关系集合与元素的关系元素与集合之间的元素与集合之间的“属于关系属于关系”是是“明确明确”的。的。 对某个集合对某个集合A A和元素和元素a a来说，来说，a a属于集合属于集合A A，记为记为a a A A或者或者a a不属于集合不属于集合A A，记为记为a a A A 两者必居其一且仅居其一两者必居其一且仅居其一。例如，对元素例如，对元素2 2和和N N，就有，就有2 2属于属

13、于N N，即，即2 2 N N，对元素对元素-2-2和和N N，就有，就有-2-2不属于不属于N N，即，即- -2 2 N N。222022-3-112022-3-11罗素悖论罗素悖论例例 在一个很僻静的孤岛上，住着一些人家，岛上在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？设设C Cx|xx|x是不给自己刮脸的人是不给自己刮脸的人 b b是这位理发师是这位理发师如如 b b C C，则，则 b b C C；如如 b b

14、 C C，则，则 b b C C。232022-3-112022-3-111.2.3 1.2.3 集合与集合的关系集合与集合的关系1 1、互异性互异性集合中的元素都是不同的，凡是相同的集合中的元素都是不同的，凡是相同的 元素，均视为同一个元素；元素，均视为同一个元素；1,1,2=1,21,1,2=1,22 2、确定性确定性能够明确加以能够明确加以“区分的区分的”对象；对象；3 3、无序性无序性集合中的元素是没有顺序的。集合中的元素是没有顺序的。 2,1=1,22,1=1,2一、集合的三大特征一、集合的三大特征242022-3-112022-3-11例例1.2.51.2.5设设E = x|(x

15、- 1)(x - 2)(x - 3) = 0, xRE = x|(x - 1)(x - 2)(x - 3) = 0, xR F = x|(x Z F = x|(x Z+ +) )且且(x(x2 212)12)。试指出集合试指出集合E E和和F F中的元素。中的元素。解解 集合集合E = 1, 2, 3E = 1, 2, 3，F = 1, 2, 3F = 1, 2, 3。显然，集合显然，集合E, FE, F中的中的元素完全相同元素完全相同，我们称，我们称这样的这样的两个集合相等两个集合相等 A AB B当且仅当当且仅当A A与与B B具有相同的元素，否则，具有相同的元素，否则，A A B B。2

16、52022-3-112022-3-11例例1.2.61.2.6设设A = BASIC, PASCAL, ADAA = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL B = ADA, BASIC, PASCAL，请判断请判断A A和和B B的关系。的关系。解解 根据集合元素的根据集合元素的无序性和外延性原理无序性和外延性原理可得，可得， A = B A = B。 因为集合因为集合A = BA = B，所以，所以B B中的每个元素都是中的每个元素都是A A中的元中的元素，我们称素，我们称集合集合A A包含包含集合集合B B。262022-3-112022-3

17、-11上述包含定义的数学语言描述为：上述包含定义的数学语言描述为： B B A A对任意对任意x x，如，如x x B B，则，则x x A A。三、包含和真包含关系三、包含和真包含关系定义定义1.2.11.2.1 设设A,BA,B是任意两个集合，如果是任意两个集合，如果 B B的每个元素都是的每个元素都是A A的元素，的元素，则称则称B B是是A A的子集合，简称的子集合，简称子集子集(Subset)(Subset)，这时也称这时也称A A包含包含B B，或，或B B被被A A包含包含，记作，记作A A B B 或或B B A A，称称“ ”或或“ ”为为包含关系包含关系(Inclusion

18、 Relation)(Inclusion Relation)。如果如果B B不被不被A A所包含，则记作所包含，则记作B B A A 。272022-3-112022-3-11例例1.2.71.2.7设设A = BASIC, PASCAL, ADAA = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL B = ADA, BASIC, PASCAL，请判断请判断A A和和B B之间的包含关系。之间的包含关系。解解 根据集合间根据集合间包含关系的定义包含关系的定义知，知，A A B B 且且A A B B 。 又从例又从例1.2.61.2.6知，集合知，集合A

19、 = BA = B，于是我们有：，于是我们有：定理定理1.2.21.2.2 设设A A、B B是任意两个集合，则是任意两个集合，则 A A B B，B B A A A=B A=B 282022-3-112022-3-11真包含关系真包含关系定义定义1.2.21.2.2 设设A,BA,B是任意两个集合，如果是任意两个集合，如果 B B A A并且并且ABAB则称则称B B是是A A的的真子集真子集(Proper Subset)(Proper Subset)，记作，记作B B A A，称称“ ”为为真包含关系真包含关系(Properly Inclusion (Properly Inclusion

20、Relation)Relation)。如果如果B B不是不是A A的真子集，则记作的真子集，则记作B AB A。上述真子集的数学语言描述为：上述真子集的数学语言描述为：B B A A对任意对任意x x，如，如x x B B，则，则x x A,A,并且，并且， y y A A，但是但是y y B B292022-3-112022-3-11判断下列集合之间是否具有真包含关系。判断下列集合之间是否具有真包含关系。（1 1）a, ba, b和和a, b, c, da, b, c, d；（2 2）a, b, c, da, b, c, d和和a, b, c, da, b, c, d。解解 根据根据真子集的

21、定义真子集的定义，有，有（1 1） a, b a, b a, b, c, da, b, c, d；（2 2）因为）因为a, b, c, da, b, c, da, b, c, da, b, c, d，所以所以a, b, c, da, b, c, d不是不是a, b, c, da, b, c, d 的真子集。的真子集。例例1.2.81.2.8302022-3-112022-3-11例例1.2.91.2.9设设A = aA = a是一个集合，是一个集合，B = a, aB = a, a，试问，试问AABB和和AA B B同时成立吗？同时成立吗？ A = aA = a，aaBB AABB成立；成立；

22、 A = aA = a，aaBB AA B B成立。成立。解解 AABB和和A A B B同时成立。同时成立。分析分析312022-3-112022-3-11 1.2.4 1.2.4 几个特殊集合几个特殊集合定义定义1.2.31.2.3 不含任何元素的集合叫做空集不含任何元素的集合叫做空集(Empty Set)(Empty Set)，记作，记作。空集可以符号化为空集可以符号化为 = x|xx = x|xx空集是客观存在的。空集是客观存在的。 1 1、空集、空集 设设A = x|(xR)A = x|(xR)且且(x(x2 20)0)，试列举集合试列举集合A A中的所有元素。中的所有元素。解解 A

23、 = A = 。定理定理1.2.3 1.2.3 （1 1）空集是一切集合的子集；）空集是一切集合的子集；（2 2）空集是绝对唯一的。）空集是绝对唯一的。322022-3-112022-3-11定理定理1.2.3 1.2.3 （2 2）的证明）的证明 对对“唯一性唯一性”的证明通常采用的证明通常采用反证法反证法。即假设即假设“不唯一不唯一”，得出矛盾，从而说明结论正，得出矛盾，从而说明结论正确确假设假设1 1和和2 2是两个空集，且是两个空集，且1 12 2，再证明再证明1 12 2，出现矛盾，从而说明结论成立。，出现矛盾，从而说明结论成立。那么怎么证明那么怎么证明1 12 2？分析分析根据定理

24、根据定理1.2.3 1.2.3 （1 1）空集是一切集合的子集）空集是一切集合的子集 1 1 2 2， 2 2 1 1，根据定理根据定理1.2.21.2.2， 1 12 2 1 1 2 2，2 2 1 1与与1 12 2矛盾矛盾332022-3-112022-3-11定义定义1.2.41.2.4 在一个在一个相对固定的范围相对固定的范围内，内，包含包含此范围内所有元素的集合此范围内所有元素的集合，称为，称为全集或论集全集或论集(Universal Set)(Universal Set)，用，用U U或或E E表示。表示。 用文氏图描述如下用文氏图描述如下: :U2 2、全集、全集342022-

25、3-112022-3-11例例1.2.121.2.12（1 1）在立体几何中，全集是由空间的全体点组成；）在立体几何中，全集是由空间的全体点组成；（2 2）在我国的人口普查中，全集是由我国所有人组成。）在我国的人口普查中，全集是由我国所有人组成。定理定理1.2.51.2.5 全集是相对唯一的全集是相对唯一的. .352022-3-112022-3-11集合集合A A中元素的数目称为集合中元素的数目称为集合A A的的基基数（数（base base number)number)，记为记为|A|A|。如如|A|A|是有限的，则称集合是有限的，则称集合A A为为有限集，有限集，如如|A|A|是无限的，

26、则称集合是无限的，则称集合A A为为无限集。无限集。例例1.2.13求下列集合的基数。求下列集合的基数。（1）A=；（2）B=；（3）C=a,b,c；（；（4）D=a,b,c。解解|A|=0，|B|=1，|C|=3，|D|=2。有限集和无限集有限集和无限集362022-3-112022-3-11m m元子集元子集定义定义1.2.61.2.6 如果一个集合如果一个集合A A含有含有n n个元素，则称集合个元素，则称集合A A为为n n元集元集，称，称A A的含有的含有m m个个(0mn)(0mn)元素的子集为元素的子集为A A的的m m元子集元子集。任给一个任给一个n n元集，怎样求出它的全部元

27、集，怎样求出它的全部m m元子集？元子集？例例1.2.141.2.14 设设A=1,2A=1,2，求出，求出A A的全部的全部m m元子集。元子集。 n=|A| = 2n=|A| = 2，mnmn m=0,1,2m=0,1,2。 当当 m=0 m=0 时，得到时，得到0 0元子集：元子集：； 当当 m=1 m=1 时，得到时，得到1 1元子集：元子集：1, 21, 2； 当当 m=2 m=2 时，得到时，得到2 2元子集：元子集：1, 21, 2。解解 A A的全部的全部m m元子集是元子集是、11、22和和1, 21, 2。分析分析372022-3-112022-3-11子集总数子集总数一般

28、来说，对于一般来说，对于n n元集元集A A，它的，它的m m（0 0 m m n n）元子集有）元子集有 个，个，所以不同的子集总数有：所以不同的子集总数有：(1+1)(1+1)n n2 2n n所以，所以，n n元集共有元集共有2 2n n个子集。个子集。nn1n0nC.CC mnC382022-3-112022-3-11幂集幂集定义定义1.2.71.2.7 设设A A为任意集合，把为任意集合，把A A的的所有不同子集所有不同子集构构成的集合叫做成的集合叫做A A的的幂集幂集( (power set)power set)，记为，记为P P(A)(A)或或2 2A A 。其符号化表示为其符号

29、化表示为 P(A)P(A)x|x|一切一切x x AA该集合又称为该集合又称为集族集族(family of set)(family of set)。 对集族的研究在数学方面、知识库和表处理语言对集族的研究在数学方面、知识库和表处理语言以及人工智能等方面都有十分重要的意义。以及人工智能等方面都有十分重要的意义。 392022-3-112022-3-11例例1.2.15 1.2.15 计算下列幂集计算下列幂集（1 1）P()P()；（；（2 2）P()P()；（；（3 3）P(a,b,c)P(a,b,c)。解解（1 1）P() = P() = ；（2 2）P() = , P() = , ；（3 3

30、）P(a,b,c)=,a,b,c,a,b,cP(a,b,c)=,a,b,c,a,b,c。 显然，若集合有个元素，则集合共有显然，若集合有个元素，则集合共有2 2|A|A|个个子集，即：子集，即：| |P P(A)|(A)| 2 2|A|A|。402022-3-112022-3-111.2.5 1.2.5 集合的运算集合的运算定义定义1.2.81.2.8 设设A A、B B是两个集合，是两个集合，(1)(1)并集并集 A A B=x|xB=x|x A A或或x x BB(2)(2)交集交集 A A B=x|xB=x|x A A且且x x BB(3)(3)差集差集 A A- -B=x|xB=x|x

31、 A A且且x x BB(4)(4)补集补集 = =U-U-A=x|xA=x|x U U且且x x A(A(,A,AC C) )(5)(5)对称差集对称差集 A A B=x|(xB=x|(x A)A)且且(x(x B)B)或或(x(x B)B)且且(x(x A)A)AUA B并集并集UA B差集差集A BU对称差集对称差集UA B交集交集补补集集UA412022-3-112022-3-11推广推广A A1 1AA2 2AA3 3AAn n1niiAin,.,2, 1iin1iAA iZii1iAA iZii1iAA =x|(x=x|(x A A1 1) )或或(x(x A A2 2) )或或或

32、或(x(x A An n)A A1 1AA2 2AA3 3AAn nx|(xx|(x A A1 1) )且且(x(x A A2 2) )且且且且(x(x A An n)当当n n无限增大时，可以记为：无限增大时，可以记为：A A1 1AA2 2AA3 3 A A1 1AA2 2AA3 3422022-3-112022-3-11定理定理1.2.51.2.51.1.等幂律等幂律: := =；= =； 2.2.交换律交换律: := =; ;= =3.3.结合律结合律: :( ()=()=()； ( ()=()=()；4.4.恒等律恒等律: :=； = =； 5.5.零律零律: := =； =；6.6

33、.分配律分配律: :( ()=()=()()() )( ()=()=()()() )7.7.吸收律吸收律: :A(AB)=A;A(AB)=A;A(AB)=AA(AB)=A； 432022-3-112022-3-11定理定理1.2.5(1.2.5(续）续）8.8.A - A = A - A = ； 9.9.A - B = A - (AB)A - B = A - (AB)；10.10.(A - B) - C = A - (BC)(A - B) - C = A - (BC)；11.11.A(B-A) = ABA(B-A) = AB；12.12.A - B =A A - B =A ；13.13.否定律

34、：否定律： ；14.DeMorgan14.DeMorgan律：律： ；15.15.矛盾律：矛盾律： AA；16.16.排中律：排中律：A A U U。BAA BABABABA,AA442022-3-112022-3-11证明：证明：DeMorganDeMorgan律：律：BABABABA BABABABA)2() 1 (分析分析定理定理1.2.21.2.2 设设A A、B B是任意两个集合，则是任意两个集合，则 A A B B，B B A A A=B A=B 452022-3-112022-3-11证明（证明（a a）：）：由、知，由、知，BAxBABABAxBxAx且BAxBxAx且BAxB

35、xAx且BxAx且BAxBAxBABABABA462022-3-112022-3-11证明（证明（b b）：）：（b b）在在 中，用中，用 和和 分别取代分别取代A A和和B B，则有则有 BABABABABABABABABAAB472022-3-112022-3-111.3 1.3 无限集无限集 质质 变变无限集合无法用确切的个数来描述，无限集合无法用确切的个数来描述，因此，无因此，无限集合有许多有限集合所没有的一些特征，而限集合有许多有限集合所没有的一些特征，而有限集合的一些特征也不能任意推广到无限集有限集合的一些特征也不能任意推广到无限集合中去，即使有的能推广，也要做某些意义上合中去，

36、即使有的能推广，也要做某些意义上的修改。的修改。有限集有限集无限集无限集量量 变变482022-3-112022-3-111.3.1 1.3.1 可数集合和不可数集合可数集合和不可数集合 二十世纪初，集合成为数学的基本概念之后，由二十世纪初，集合成为数学的基本概念之后，由冯冯 诺依曼诺依曼（Von NeumannVon Neumann，J.J.）用集合的方式来）用集合的方式来定义自然数取得了成功，提出了用序列定义自然数取得了成功，提出了用序列，,，,，来定义自然来定义自然数。数。 492022-3-112022-3-111.3.1 1.3.1 可数集合与不可数集合可数集合与不可数集合问题问题1

37、,2,3,1,2,3, 与与112 2,2,22 2,3,32 2, , 哪个集合的元素更多？哪个集合的元素更多？引入：引入：自然数集合自然数集合 二十世纪初，集合成为数学的基本概念之后，由二十世纪初，集合成为数学的基本概念之后，由冯冯 诺依曼（诺依曼（Von NeumannVon Neumann，J.J.）用集合的方式来定义）用集合的方式来定义自然数取得了成功，提出了用序列自然数取得了成功，提出了用序列，,，,，来来定义自然数。定义自然数。 502022-3-112022-3-11自然数集合自然数集合N N的定义的定义 N N，若若n n N N，则，则n n: :n n nn N N。也即

38、：也即：0:0: ， 1:1: 00， 2:2: , 0,10,1 . . n: n:0,1,2,3,.n-10,1,2,3,.n-1 . .故故 N N0,1,2,3,.,n,.0,1,2,3,.,n,.512022-3-112022-3-11等势的概念等势的概念 定义定义1.3.11.3.1 设设A A，B B是两个集合，若在是两个集合，若在A A，B B之间之间存在存在1-11-1对应对应的关系：的关系：ABAB则称则称A A与与B B是是等势的等势的(equipotential)(equipotential)，记为：，记为：A A B B。也称集合也称集合A A与与B B等势等势(eq

39、uipotent)(equipotent)。 注意：注意：若若A AB B，则，则 A A B B。 若若A A B B，则，则 A AB B （）（）522022-3-112022-3-11可数集合可数集合( (可列集）可列集） 定义定义1.3.21.3.2 凡是与凡是与自然数集合自然数集合等势的集合，统等势的集合，统称为称为可数集合可数集合( (可列集可列集)(Countable Set )(Countable Set )。记为：记为：0 0 ( (读作读作阿列夫零阿列夫零) ) 。例例1.3.11.3.1 下列集合都是可数集合：下列集合都是可数集合： 1)O1)O+ +x|xx|x N

40、N，x x是奇数是奇数; 2)P 2)Px|xx|x N N，x x是素数是素数; 3) 3)有理数集合有理数集合Q.Q.532022-3-112022-3-11解：解：1 1）在在O O+ +与与N N之间建立之间建立1-11-1对应的关系对应的关系 f f：NONO+ + 如下：如下：N N . . . . . . O O+ + . 2n+1 . 2n+1 .所以，所以，O O+ +是可数集合。是可数集合。542022-3-112022-3-112 2）在在P P与与N N之间建立之间建立1-11-1对应的关系对应的关系f f：NPNP如下：如下：N N . . .P P 11 .11 .

41、 所以，所以，P P是可数集合。是可数集合。552022-3-112022-3-115 5）-3/1-3/118 18 -2/1-2/15 5 -1/1-1/14 4 0/10/100 1/11/11 1 2/1 2/11010 -3/1 -3/11111 -3/2-3/217 17 -2/2 -1/2-2/2 -1/23 3 0/2 1/20/2 1/222 2/2 2/2 3/23/21212 -3/3 -2/3 -3/3 -2/36 6 -1/3-1/37 7 0/3 1/30/3 1/388 2/3 2/399 3/3 3/3 -3/4 -3/41616 -2/4-2/4 -1/4-1

42、/415 15 0/40/4 1/41/414 14 2/4 3/42/4 3/41313所以，有理数集合必是可数集合。所以，有理数集合必是可数集合。 562022-3-112022-3-11定理定理1.3.11.3.1两个有限集合等势两个有限集合等势当且仅当它们有相同的元当且仅当它们有相同的元素个数；素个数；有限集合不和其任何真子集等势；有限集合不和其任何真子集等势；可数集合可以和其可数的真子集等势。可数集合可以和其可数的真子集等势。572022-3-112022-3-11不可数集合不可数集合定义定义1.3.31.3.3开区间开区间(0,1)(0,1)称为称为不可数集合不可数集合，其，其基数

43、设为基数设为( (读读作阿列夫作阿列夫) )；凡是与开区间凡是与开区间(0,1)(0,1)等势的集合都是不可数集合。等势的集合都是不可数集合。例例1.3.21.3.2 (1)(1)闭区间闭区间0,1 0,1 是不可数集合；是不可数集合； (2)(2)实数集合实数集合R R是不可数集合。是不可数集合。582022-3-112022-3-11例例1.3.2 1.3.2 解解（1 1）在闭区间在闭区间0, 10, 1和开区间和开区间(0, 1)(0, 1)之间建立之间建立如下对应关系：如下对应关系： 则上述对应是则上述对应是一一对应一一对应的关系。的关系。 所以所以00，11与与（0 0，1 1）一

44、定是等势的，即）一定是等势的，即00，11是不可数集合是不可数集合。nn201 / 4,11 / 2,R :11n1, 2,3,22nnn(0,1) .其 他592022-3-112022-3-11例例1.3.2 1.3.2 解（续）解（续）（2 2）在实数集和开区间在实数集和开区间(0,1)(0,1)之间建立如下对之间建立如下对应关系：应关系：显然此对应关系是显然此对应关系是一一对应一一对应关系，即（关系，即（0 0，1 1）与）与R R之间是等势的，所以之间是等势的，所以R R是一个不可数集合是一个不可数集合。2n1ntan2602022-3-112022-3-111.4 1.4 集合的应

45、用集合的应用例例1.4.11.4.1 用用H H代表硬币正面，代表硬币正面，T T代表硬币反面。试写代表硬币反面。试写出当扔出三个硬币时可能出现的结果所组成的集合。出当扔出三个硬币时可能出现的结果所组成的集合。解解: : 8 8种可能：种可能：HHHHHH，HHTHHT，HTHHTH，HTTHTT，THHTHH，THTTHT，TTHTTH，TTTTTT。但这三个硬币没有顺序之分，即。但这三个硬币没有顺序之分，即HHTHHT和和HTHHTH是同一个元素，所以是同一个元素，所以 A = HHHA = HHH，HHTHHT，HTTHTT，TTTTTT。612022-3-112022-3-11例例1.4.21.4.2一个正三角形被均分为三个小三角形，如图一个正三角