离散数学(第3章)陈瑜课件

陈瑜陈瑜Email：7/14/2024第三章第三章 集合及其运算集合及其运算n集集合合是是数数学学中中最最基基本本的的概概念念之之一一,是是现现代代数数学学的的重重要要基基础础,它它已已深深入入到到各各种种科科学学和和技技术术领领域域中中。对对计计算算机机科科学学与与技技术术的的工工作作者者来来说说,更更是是不不可可缺缺少少的的工工具具。本本书书各各部部分分贯贯穿穿着着集集合合论论的的思思想想。计计算算机机科科学学的的许许多多分分支支都都大大量量用用到到集集合合的的概概念念和和知知识识,如如数数据据结结构构,程程序序语语言言,数数据据库库,人工智能人工智能等。等。n集集合合论论的的主主要要特特点点:研研究究问问题题的的广广泛泛性性,分分析析思思考考问问题题的的抽抽象象性性,处处理理问问题题的的统统一一性性,特特别别便便于于描描述述和和研研究究离离散对象及其关系。散对象及其关系。7/14/20247/14/20242 2计算机学院计算机学院3.1 3.1 集合论的基本概念集合论的基本概念 我我们们对对于于“在在一一定定范范围围内内的的讨讨论论的的对对象象组组成成的的整整体体”给给予予一一个个名名字字，叫叫集集合合（SETSET）,其其中中的的对对象象称称为为这这个个集集合合的的“成成员员”或或 “元元素素”（ELEMENTELEMENT）。通通俗俗地地讲讲，所所谓谓集集合合，就就是是某某些些客客体体的的一一个个确确定定的的表表或或汇汇总总。（任任意意客客体体的的聚集聚集）通常用带（不带）标号的通常用带（不带）标号的大写字母大写字母A A、B B、C C、.、A1A1、B1 B1、C1 C1、.、X X、Y Y、Z Z、.表示集合；表示集合；通常用带（不带）标号的通常用带（不带）标号的小写字母小写字母a a、b b、c c、.、a1a1、b1 b1、c1 c1、.、x x、y y、z z、.表示元素。表示元素。一、集合的概念一、集合的概念7/14/20247/14/20243 3计算机学院计算机学院二、二、集合的表示法：集合的表示法：集集合合是是由由它它所所包包含含的的元元素素完完全全确确定定的的，为为了了表表示示一一个个集集合合，通通常常有有：枚枚举举法法、隐隐式式法法（叙叙述述法法）、归归纳纳法法、递递归归指指定定、巴巴科科斯斯范范式式BNFBNF、文氏图、特征函数文氏图、特征函数等表示方法。等表示方法。n1 1、枚举法：、枚举法：此此方方法法就就是是将将集集合合中中的的元元素素全全部部列列出出来来（或或者者只只列列出出一一部部分分元元素素，而而其其余余部部分分可可以以从从前前后后关关系系中中很很明明显显的的知道）。知道）。7/14/20247/14/20244 4计算机学院计算机学院n2 2、隐隐式式法法（叙叙述述法法）：用用一一集集合合之之元元素素所所具具有有的的共共同同性质性质来刻划这个集合。来刻划这个集合。n一般表示方法：一般表示方法：P P x|P(xx|P(x)1 1）“”前面的前面的x x代表集合代表集合P P中的任意元素中的任意元素2 2）“”后面的后面的P(xP(x)表示表示x x必须具有性质必须具有性质P P n其其突突出出优优点点是是原原则则上上不不要要求求列列出出集集合合中中全全部部元元素素，而而只要给出该集合中元素的特性只要给出该集合中元素的特性n例例1 1：S S1 1x|xx|x是正偶数是正偶数 S S2 2x|x|（x x Z Z）并且（）并且（x0)x0)S S3 3x|xx|x是四川大学的学生是四川大学的学生 S S4 4x|xx|x是是“letter”letter”中的字母中的字母 7/14/20247/14/20245 5计算机学院计算机学院n3 3、归纳法：、归纳法：归纳法是通过归纳定义集合，主要由三部归纳法是通过归纳定义集合，主要由三部分组成。分组成。第一部分：第一部分：基础。基础。它指出某些最基本的元素属于它指出某些最基本的元素属于某集合；某集合；第二部分：第二部分：归纳。归纳。指出由基本元素造出新元素的指出由基本元素造出新元素的方法；方法；第三部分：第三部分：极小性。极小性。指出该集合的界限。指出该集合的界限。n第第一一部部分分和和第第二二部部分分指指出出一一个个集集合合至至少少要要包包括括的的元元素素，第三部分第三部分指出一个集合指出一个集合至多要包含的元素至多要包含的元素。n例例2 2：集合集合M M是按如下方式定义：是按如下方式定义：1 1）每一个英文字母都是）每一个英文字母都是M M中的元素；中的元素；2 2）如果）如果P P、Q Q是是M M中的元素，则中的元素，则PQPQ、QPQP也是也是M M中的元素；中的元素；3 3）有有限限次次使使用用（1 1）、（2 2）后后所所得得到到的的字字符符串串都都是是M M中中的元素。的元素。7/14/20247/14/20246 6计算机学院计算机学院n4 4、递归指定集合、递归指定集合 通过通过计算规则计算规则定义集合中的元素定义集合中的元素n n例例例例3 3 3 3：设设设设 a a a a0 0 0 0 1 1 1 1，a a a a1 1 1 1 1 1 1 1，a a a ai+1 i+1 i+1 i+1 a a a ai i i i +a+a+a+ai-1 i-1 i-1 i-1（i i i i 1 1 1 1）S S S Saaaa0 0 0 0，a a a a1 1 1 1，a a a a2 2 2 2，.a a a ak k k k|k|k|k|k 0 0 0 0 7/14/20247/14/20247 7计算机学院计算机学院n5 5、巴科斯范式、巴科斯范式BNFBNF表示法表示法 BNFBNF（Backus Backus Normal Normal FormForm）常常常常用用来来定定义高级程序设计语言的标识符或表达式集合。义高级程序设计语言的标识符或表达式集合。n例例4 4：在在PASCALPASCAL语言中，标识符集定义如下：语言中，标识符集定义如下：:|7/14/20247/14/20248 8计算机学院计算机学院n6 6、文氏图（、文氏图（VennVenn）文文氏氏图图解解是是一一种种利利用用平平面面上上点点的的集集合合作作成成的的对对集集合合的的图图解解。一一般般用用平平面面上上的的圆圆形形或或方方形形表示一个集合。表示一个集合。AA7/14/20247/14/20249 9计算机学院计算机学院n7 7、特征函数表示法、特征函数表示法n定义定义3.13.1 设设A A是集合是集合,称称 为为A A的的特征函数特征函数。（它表明了集合与其成员的关系）。（它表明了集合与其成员的关系）对对某某个个集集合合和和元元素素来来说说，或或者者属属于于集集合合，或或者者不属于不属于集合，两者必居其一，且仅居其一。集合，两者必居其一，且仅居其一。是集合的元素或属于，记为：是集合的元素或属于，记为：a a A A不是的元素或不属于，记为：不是的元素或不属于，记为：a a A A7/14/20247/14/20241010计算机学院计算机学院罗素悖论罗素悖论n n例例 在一个很僻静的孤岛上，住着一些在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师人家，岛上只有一位理发师，该理发师专专给那些并且只给那些给那些并且只给那些自己不刮脸的人自己不刮脸的人刮脸。刮脸。那么，谁给这位理发师刮脸？那么，谁给这位理发师刮脸？解：解：设设 C Cx|xx|x是不给自己刮脸的人是不给自己刮脸的人 b b是这位理发师是这位理发师如如 b b C C，则则 b b C C；如如 b b C C，则则 b b C C。7/14/20247/14/20241111计算机学院计算机学院罗素悖论罗素悖论n n例例 在一个很僻静的孤岛上，住着一些在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师人家，岛上只有一位理发师，该理发师专专给那些并且只给那些给那些并且只给那些自己不刮脸的人自己不刮脸的人刮脸。刮脸。那么，谁给这位理发师刮脸？那么，谁给这位理发师刮脸？解：解：设设 C Cx|xx|x是不给自己刮脸的人是不给自己刮脸的人 b b是这位理发师是这位理发师如如 b b C C，则则 b b C C；如如 b b C C，则则 b b C C。此例说明：此例说明：“集集合合”是一个无法是一个无法精确定义的数学精确定义的数学概念之一概念之一7/14/20247/14/20241212计算机学院计算机学院n三、集合之间的关系与子集三、集合之间的关系与子集 定定义义3.23.2：设设有有集集合合A A与与B B，若若A A中中的的每每一一个个元元素素都都是是B B中中的元素，则称的元素，则称A A是是B B的的子集子集或或B B包含包含A A，记为：，记为：A A B B或或B B A A 上述包含定义又可形象地叙述为：上述包含定义又可形象地叙述为：B B A A对任意对任意x x，如，如x x B B，则，则x x A A。定定义义3.33.3：设设A A、B B是是任任意意两两个个集集合合，如如果果A A B B且且B B A A，则称则称A A与与B B相等，记为相等，记为A=BA=B。符号化表示为：符号化表示为：A=BA=BA A B B且且B B A A。如果如果A A和和B B不相等，则记作不相等，则记作A A B B。7/14/20247/14/20241313计算机学院计算机学院基基 数数集合集合A A中中元素的数目元素的数目称为集合称为集合A A的的基数基数，记为，记为|A|A|。如如|A|A|是有限的，则称是有限的，则称A A为为有限集合有限集合如如|A|A|是无限的，则称是无限的，则称A A为为无限集合无限集合定定义义3.43.4 没没有有元元素素的的集集合合称称为为空空集集,用用 表表示示。空空集集可可表表示为：示为：=x|xx|x x x 定定义义3.53.5 全全集集用用U U或或E E表表示示,它它表表示示在在某某个个固固定定范范围围内内的的所所有对象的全体有对象的全体。性质性质1 1：全集只能是相对唯一的，而非绝对唯一的全集只能是相对唯一的，而非绝对唯一的性质性质1 1：空集是绝对唯一的。空集是绝对唯一的。7/14/20247/14/20241414计算机学院计算机学院性质性质3 31.1.对任意一个集合对任意一个集合A A，都有：都有：A A2.2.对任意一个集合对任意一个集合A A，都有：都有：A A A A(自反性）自反性）3.3.对对任任意意集集合合A A、B B、C C，如如果果A A B B并并且且B B C C，则则A A C C(传递性）传递性）4.4.对对任任意意集集合合A A、B B，A AB B当当且且仅仅当当A A B B并并且且B B A A(反对称性）反对称性）7/14/20247/14/20241515计算机学院计算机学院外延性原理外延性原理 在在集集合合中中，凡凡是是相相同同的的元元素素，均均认认为为是是同同一一个个元元素素，并并可可将将相相同同的的元元素素合合并并成成一一个个元元素素，即即是是说说，这这里里所所谈谈的的“元元素素”都都是是“确确定定的的”，能能够够明明确确加加以以“区区分分的的”对象。我们认为对象。我们认为集合中的元素都是不同的并且是无序的集合中的元素都是不同的并且是无序的。A AB B 当且仅当当且仅当 A A与与B B具有相同的元素，否则，具有相同的元素，否则，A A B Bn例例1.81.8 集合集合 A Aaa，b b，c c，bb B Baa，b b，cc C Ccc，b b，a a A=B=CA=B=Cn n例例例例1.91.91.91.9 E E E Ex|x|x|x|（x x x x Z Z Z Z）并且（）并且（）并且（）并且（x x x x2 2 2 2-3x+2-3x+2-3x+2-3x+20 0 0 0）F F F F1111，2222 G G G G1111，2 2 2 2，2 2 2 2，1 1 1 1，6/3 6/3 6/3 6/3 E E E EF F F FG G G G7/14/20247/14/20241616计算机学院计算机学院3.2 3.2 集合的运算集合的运算n定义定义3.63.6 设设A A、B B是全集是全集U U的两个子集合，则的两个子集合，则A AB B x x U U|x x A Ax x B B 仍仍是是一一个个集集合合，称称为为集集合合A A与与B B的的并并集集，称称“”为为并运算并运算（Union OperationUnion Operation）。）。用文氏图表示如下：用文氏图表示如下：U UAB7/14/20247/14/20241717计算机学院计算机学院交集交集n定义定义3.73.7 设设A A，B B是全集是全集U U的两个子集合，则的两个子集合，则A AB B x x U U|x x A Ax x B B 仍仍是是一一个个集集合合，称称为为集集合合A A与与B B的的交交集集，称称“”为为交交运运算算（Intersection Intersection OperationOperation）。用文氏图可表示如下：用文氏图可表示如下：U UAB7/14/20247/14/20241818计算机学院计算机学院推广推广=A=A1 1AA2 2AA3 3AAn n=A=A1 1AA2 2AA3 3AAn n当当n n无限增大时，可以记为：无限增大时，可以记为：=A=A1 1AA2 2AA3 3，=A=A1 1AA2 2AA3 3。7/14/20247/14/20241919计算机学院计算机学院差集差集n定义定义3.83.8 设设A A，B B是全集是全集U U的两个子集合，则的两个子集合，则A A-B B x x U|x x A Ax x B B 仍仍是是一一个个集集合合，称称为为集集合合A A与与B B的的差差集集，称称“-”为为差差运运算算（Subtraction Subtraction Operation)Operation)，-又叫又叫相对补集相对补集。用文氏图可表示如下：。用文氏图可表示如下：U UAB7/14/20247/14/20242020计算机学院计算机学院补集补集n定义定义3.93.9 设设U U是全集，是全集，A A是是U U的子集，则的子集，则 U-U-A Ax|xx|x U U并且并且x x A A 仍仍是是一一个个集集合合，称称它它为为集集合合A A的的补补集集(也也可可记记为为 ，A AC C等等），“”称称 为为 补补 运运 算算（Complement Complement OperationOperation）。用用文文氏氏图图可可表表示示如下：如下：UA7/14/20247/14/20242121计算机学院计算机学院对称差对称差n定义定义3.103.10：设：设A A，B B是两个集合，则是两个集合，则 A A B=B=x|(xx|(x A A)并并 且且(x(x B)B)或或(x(x B)B)并并 且且(x(x A)A)=(A-B)(B-A)=(A-B)(B-A)仍仍是是一一个个集集合合，称称它它为为与与的的对对称称差差集集，称称“”为对称差运算为对称差运算。用文氏图可表示如下：用文氏图可表示如下：ABU 图中的粉红部分为图中的粉红部分为A A B B。7/14/20247/14/20242222计算机学院计算机学院关于运算关于运算“差差”和和“补补”的几个性的几个性质：质：n1.1.A A A A B B A A ；n2.2.B B；n3.3.A A=或或=；n4 4 U U；n5 5 ；n6 6=（）（）7/14/20247/14/20242323计算机学院计算机学院定理定理3.13.1：1.1.幂等律：幂等律：；2 2交换律：交换律：；3 3结合律：结合律：（）（）（）；（）（）（）；4 4零一律：零一律：；5 5分配律：分配律：（）（）（）（）；）；（）（）（）（）。）。6 6吸收律：吸收律：AA（ABAB）A A；AA（ABAB）=A=A；7 7否定律：否定律：7/14/20247/14/20242424计算机学院计算机学院 8 8DeMorganDeMorgan律：律：9 9矛盾律：矛盾律：A =A =；A =U A =U；7/14/20247/14/20242525计算机学院计算机学院3.4 3.4 集合的幂集和笛卡尔集集合的幂集和笛卡尔集 n一、幂集一、幂集 定定义义3.113.11 由由集集合合A A的的所所有有子子集集组组成成的的集集合合称为称为A A的的幂集幂集，记为，记为(A)(A)或或2 2A A。2 2A A=(A)(A)x|x|一切一切x x A A 这种这种以集合为元素以集合为元素构成的集合，常称为构成的集合，常称为集集合的集合合的集合或或集族集族（Family of SetFamily of Set）。对集族）。对集族的研究在数学方面、知识库和表处理语言以的研究在数学方面、知识库和表处理语言以及人工智能等方面都有十分重要的意义。及人工智能等方面都有十分重要的意义。7/14/20247/14/20242626计算机学院计算机学院n例例1010：设设,，则，则：1 1）2 2A A ,2 2）对于空集对于空集，有：，有：2 2 2 2 ,3 3）(1,2,3)=,1,2,3,1,2,3(1,2,3)=,1,2,3,1,2,3n定理定理3.23.2：设设A A和和B B是两个集合，是两个集合，1 1）如如B B A A，则则2 2B B 2 2A A 2 2）若集合有个元素，则集合共有若集合有个元素，则集合共有2 2n n个子集，个子集，即：即：|(A)|2n。7/14/20247/14/20242727计算机学院计算机学院n二二.笛卡尔积笛卡尔积(直积直积)Descartes)Descartes 定定义义3.123.12:设设给给定定n1n1个个集集合合A A1 1,A,A2 2,A,An n,称称A A1 1A A2 2A An n=a a ai i A Ai i,1i,1i nn 为为A A1 1,A,A2 2,A,An n的笛卡尔积。的笛卡尔积。对对所所有有的的i,Ai,Ai i=A=A时时,A A1 1A A2 2A An n简简写写成成A An n ,如如A AA=AA=A,A,AA AA=AA=A 如如果果所所有有的的集集合合都都是是有有穷穷集集合合,则则n n个个集集合合的笛卡尔积的基数为的笛卡尔积的基数为:|(A|(A1 1A A2 2A An n)|=|A)|=|A1 1|A|A2 2|A|An n|7/14/20247/14/20242828计算机学院计算机学院 集集合合的的笛笛卡卡尔尔积积不不服服从从交交换换律律,还还可可证证明明不不服从结合律服从结合律,但但对对U,U,可左右分配。可左右分配。n定理定理3.33.3:设设A,B,CA,B,C是任意三个集合是任意三个集合,则则 A A(BUC)=(A(BUC)=(AB)U(AB)U(AC)C)A A(BC)=(A(BC)=(AB)(AB)(AC)C)(BUC)(BUC)A=(BA=(BA)U(CA)U(CA)A)(BC)(BC)A=(BA=(BA)(CA)(CA)A)7/14/20247/14/20242929计算机学院计算机学院n定理定理3.43.4:A,B,C:A,B,C为任意集合为任意集合,C,C ,则则 A A B iff A B iff AC C B BC C A A B iff C B iff CA A C CB Bn定理定理3.53.5:设设A,B,CA,B,C为非空集合为非空集合,则则 A AB B C CD D A A C CB B D D7/14/20247/14/20243030计算机学院计算机学院习题：习题：预习第四章预习第四章7/14/20247/14/20243131计算机学院计算机学院