《31.21.3集合概念和运算98》由会员分享，可在线阅读，更多相关《31.21.3集合概念和运算98（55页珍藏版）》请在金锄头文库上搜索。
1、第第3讲讲 集合的概念与运算集合的概念与运算n 1. 集合的概念集合的概念n 2. 集合之间的关系集合之间的关系n 3. 集合的运算集合的运算n 4. 文氏图、容斥原理文氏图、容斥原理*表示不要求，表示不要求，表示要求自学表示要求自学集合论集合论(set theory)n十九世纪数学最伟大成就之一十九世纪数学最伟大成就之一n集合论体系集合论体系n朴素朴素(naive)集合论集合论n公理公理(axiomatic)集合论集合论n创始人创始人康托康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918 德国数学家德国数学家, 集合论创始人集合论创始人.集合结
2、构集合结构n离散数学的大部分内容是研究离散结构，表现离散离散数学的大部分内容是研究离散结构，表现离散对象。对象。n很多重要的离散结构是用集合来构造的，即对象的很多重要的离散结构是用集合来构造的，即对象的联合。例如组合，计数，关系，用来表现关系的序联合。例如组合，计数，关系，用来表现关系的序偶集合，图，结点和联结结点的边的集合，用来模偶集合，图，结点和联结结点的边的集合，用来模拟计算机的有限状态机等。拟计算机的有限状态机等。集合论的起源与发展集合论的起源与发展n集合论集合论(Set Theory)是现代数学的基础它的起源可追是现代数学的基础它的起源可追溯到溯到16世纪末，主要是对世纪末，主要是对
3、数集数集进行卓有成效的研究进行卓有成效的研究n19世纪世纪 70年代德国数学家年代德国数学家康托尔康托尔(G . Cantor) 在无穷序在无穷序列和分析的有关课题的理论研究中创立了集合论康列和分析的有关课题的理论研究中创立了集合论康托尔对具有任意特性的无穷集合进入了深入的探讨，托尔对具有任意特性的无穷集合进入了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础因此，康托尔被誉为集合论定了集合论的深厚基础因此，康托尔被誉为集合论的创始人的创始人康托尔的基本理论康托尔的基本理论康托尔集合论（康托尔集合论（朴素集合论朴素集合
4、论）中的许多证明均能从）中的许多证明均能从三个公理得出这三个公理是三个公理得出这三个公理是:外延公理外延公理: 如果两个集合中各个元素都是相同的，如果两个集合中各个元素都是相同的， 则它们相等则它们相等抽象公理抽象公理: 任给一个性质，都有一个满足该性质的任给一个性质，都有一个满足该性质的客体所组成的集合客体所组成的集合选择公理选择公理: 每个集合都有一个选择函数每个集合都有一个选择函数 但是但是,抽象公理产生了悖论，选择性公理让人困惑抽象公理产生了悖论，选择性公理让人困惑.集合论的起源与发展集合论的起源与发展(罗素悖论罗素悖论)n当人们认为集合论足够严谨时当人们认为集合论足够严谨时,在本世纪
5、初在本世纪初,出现了出现了许多悖论许多悖论,如著名的如著名的罗素悖论罗素悖论(即理发师悖论即理发师悖论), 有力有力冲击了或者说动摇了集合论的发展冲击了或者说动摇了集合论的发展n罗素悖论：罗素悖论：由由“不属于该集合的所有客体组成集合不属于该集合的所有客体组成集合”会导出矛盾会导出矛盾. n论证论证 把抽象公理符号化为：把抽象公理符号化为：( y)( x)(xy (x) 其中其中, (x)是不以是不以y为自由变元的公式为自由变元的公式. 把把 (x)取为取为“x不为不为y的成员的成员”, 即即 (x) = (xy). 则则罗素悖论符号化为罗素悖论符号化为 ( y)( x)(xy(xy) 取取x
6、y，可得，可得( y)( y)(yy(yy)集合论的起源与发展集合论的起源与发展(公理化体系公理化体系)n许多数学家哲学家为克服这些矛盾而建立了各种许多数学家哲学家为克服这些矛盾而建立了各种公理公理化集合论体系化集合论体系 (“这些原则必须足够狭窄，以保证排这些原则必须足够狭窄，以保证排除一切矛盾；另一方面又必须充分广阔，使康托尔集除一切矛盾；另一方面又必须充分广阔，使康托尔集合论中一切有价值的内容得以保存下来合论中一切有价值的内容得以保存下来”)，其中以，其中以20世纪初、中期的世纪初、中期的ZFS(E . Zermelo, A . Fraenkel, T . Skolem)和和NBG(Vo
7、n Neurnann, P . Bernavs, K . Gdel)公理化体系公理化体系最为流行最为流行. n到到 20世纪世纪 60年代，年代，P . L . Cohen发明了强制方法而得发明了强制方法而得到了关于到了关于连续统连续统与与选择公理选择公理的独立性成果，而后的研的独立性成果，而后的研究结果推陈出新，大量涌现究结果推陈出新，大量涌现集合论的起源与发展（续）集合论的起源与发展（续）n在同一时代，美国数学家在同一时代，美国数学家 L . A.Zadeh提出了提出了Fuzzy集集理论理论, 以及以及 20世纪世纪80年代波兰数学家年代波兰数学家Z . Pawlak发表发表了了Rough
8、集理论集理论，这两种理论区别于以往的集合论，这两种理论区别于以往的集合论， 是一种新的是一种新的模糊集理论模糊集理论，受到了学术界的重视和青睐，受到了学术界的重视和青睐，取得了喜人成果还有多位著名学者也为集合论的发取得了喜人成果还有多位著名学者也为集合论的发展作出了重要贡献展作出了重要贡献n在此基础上，逐步形成了在此基础上，逐步形成了公理化集合论公理化集合论和和抽象集合论抽象集合论，使该学科成为数学中发展最为迅速的一个分支。使该学科成为数学中发展最为迅速的一个分支。n集合论观点已渗透到古典分析、泛函、概率、函数论集合论观点已渗透到古典分析、泛函、概率、函数论以及信息论、排队论等现代数学各个领域
9、。以及信息论、排队论等现代数学各个领域。集合集合(set)n集合：不能精确定义。集合：不能精确定义。一些对象的整体就构成一些对象的整体就构成集合集合， 这些对象称为这些对象称为元素元素(element)或或成员成员(member)n用大写英文字母用大写英文字母A,B,C,表示集合表示集合n用小写英文字母用小写英文字母a,b,c,表示元素表示元素naA：表示：表示a是是A的元素，读作的元素，读作“a属于属于A”a A：表示：表示a不是不是A的元素，读作的元素，读作“a不属于不属于A”集合的表示集合的表示n列举法列举法n描述法描述法n特征函数法特征函数法列举法列举法(roster)n列出集合中的全
10、体元素，元素之间用逗号分开，列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如然后用花括号括起来，例如A=a,b,c,d,x,y,zB=0,1,2,3,4,5,6,7,8,9n集合中的元素不规定顺序集合中的元素不规定顺序C=2,1=1,2n集合中的元素各不相同集合中的元素各不相同(多重集除外多重集除外)C=2,1,1,2=2,1多重集多重集(multiple set)n多重集多重集: 允许元素多次重复出现的集合允许元素多次重复出现的集合n元素的元素的重复度重复度: 元素的出现次数元素的出现次数(0).n例如例如: 设设A=a,a,b,b,c是多重集是多重集元素元素a,b的重复度
11、是的重复度是2元素元素c的重复度是的重复度是1元素元素d的重复度是的重复度是0描述法描述法(defining predicate)n用用谓词谓词P(x)表示表示x具有性质具有性质P ，用，用x|P(x)表示具表示具有性质有性质P 的集合，例如的集合，例如nP1 (x): x是英文字母是英文字母A=x| P1 (x)=x| x是英文字母是英文字母 =a,b,c,d,x,y,znP2 (x): x是十进制数字是十进制数字B=x| P2(x)= x|x是十进制数字是十进制数字 =0,1,2,3,4,5,6,7,8,9描述法（续）描述法（续）n两种表示法可以互相转化，例如两种表示法可以互相转化，例如E
12、=2,4,6,8, =x|x0且且x是偶数是偶数 =x|x=2(k+1)，k为非负整数为非负整数 =2(k+1) | k为非负整数为非负整数n有些书在描述法中用有些书在描述法中用:代替代替|, 例如例如2(k+1): k为非负整数为非负整数特征函数法特征函数法(characteristic function) n集合集合A的特征函数是的特征函数是 :n对多重集对多重集, : x在在A中的重复度中的重复度.常用的数集合常用的数集合nN：自然数：自然数(natural numbers)集合集合N=0,1,2,3,nZ(I)：整数：整数(integers)集合集合Z=0,1,2,=,-2,-1,0,
13、1,2,nQ：有理数：有理数(rational numbers)集合集合nR：实数：实数(real numbers)集合集合nC：复数：复数(complex numbers)集合集合集合之间的关系集合之间的关系n子集、相等、真子集子集、相等、真子集n空集、全集空集、全集n幂集、幂集、n元集、有限集元集、有限集n集族集族子集子集(subset)nB包含于包含于A, A包含包含B:BA x(xBxA)nB不是不是A的子集的子集:B A x(xBx A)nx(xBxA)x(xBxA)x(xBxA)x(xBx A)相等相等(equal)n相等相等: A=B AB BA x(xAxB)nA=B ABBA
14、 (=定义定义)x(xAxB)x(xBxA) (定义定义)x(xAxB)(xBxA) (量词分配量词分配)x(xAxB) (等值式等值式)包含包含()的性质的性质nAA证明证明: AAx(xAxA) 1n若若AB,且且AB,则则B A证明证明: AB (A=B) (ABBA) (=定义定义)(AB) (BA) (德德摩根律摩根律) AB (已知已知) (BA) (即即B A) (析取三段论析取三段论) # ( (AB )B A 析取三段论析取三段论)包含包含()的性质的性质(续续)n若若AB, 且且BC, 则则AC (传递性传递性)证明证明: AB x(xAxB)x, xA xB (AB) x
15、C (BC) x(xAxC), 即即AC. #真子集真子集(proper subset)n真子集真子集: B真包含真包含A:AB AB ABnA B (AB AB) (定义定义) (AB) (A=B) (德德摩根律摩根律) x(xAx B) (A=B) ( 定义定义)真包含真包含()的性质的性质nA A证明证明: AA AA AA 10 0. #n若若AB,则则B A证明证明: (反证反证) 设设BA, 则则AB AB AB AB (化简化简)BA BA BA BA所以所以AB BA A=B (=定义定义)但是但是AB AB AB AB (化简化简) 矛盾矛盾!#真包含真包含()的性质的性质(
16、续续)n若若AB, 且且BC, 则则AC证明证明: AB AB AB AB (化简律化简律), 同理同理 BC BC, 所以所以AC.假设假设A=C, 则则 BC BA, 又又AB, 故故A=B, 此与此与AB矛盾矛盾, 所以所以AC.所以所以, AC. #空集空集(empty set)n空集空集:没有任何元素的集合是空集没有任何元素的集合是空集,记作记作。 例如例如, xR|x2 +1=0n定理定理1: 对任意集合对任意集合A, A证明证明: Ax(xxA) x(0xA)1. #n推论推论: 空集是唯一的空集是唯一的.证明证明: 设设1与与2都是空集都是空集, 则则12 21 1=2 . #
17、全集全集n全集全集: 如果限定所讨论的集合都是某个集合的子集如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集则称这个集合是全集,记作记作E。n全集是全集是相对的相对的, 视情况而定视情况而定, 因此因此不唯一不唯一.例如例如, 讨论讨论(a,b)区间里的实数性质时区间里的实数性质时, 可以选可以选E=(a,b), E=a,b), E=a,b,E=(a,+),E=(-,+)等等n元集元集(n-set)nn元集元集: 含有含有n个元素的集合称为个元素的集合称为n元集。元集。n0元集元集: 。n1元集元集(或单元集或单元集),如如a, b, , ,。n |A|: 表示集合表示集合A中的元素
18、个数中的元素个数,A是是n元集元集 |A|=nn有限集有限集(fimite set): |A|是有限数是有限数, |A|0, Aa=0,a),Aa|aR+的指标集是的指标集是R+.0a集合之间的运算集合之间的运算n并集、交集并集、交集n相对补集、绝对补、对称差相对补集、绝对补、对称差n广义并集、广义交集广义并集、广义交集文氏图文氏图 (Venn diagram)文氏图文氏图(Venn Diagram)(Venn Diagram)以英国数学家以英国数学家 John Venn John Venn命名命名. .并集并集(union)n并集并集: AB = x | (xA) (xB) xAB (xA)
19、 (xB)n初级并初级并(广义并广义并):并集并集(举例举例)n例例1: 设设An=xR|n-1xn,n=1,2,10,则则n例例2: 设设An =xR|0x1/n,n=1,2,则则集合的并的性质集合的并的性质(1) AA=A 幂等律等律(2) A = A 同一律同一律(3) AE = E 零律零律 (4) AB = BA 交交换律律(5) (AB)C = A(BC) 结合律合律交集交集(intersection)n交集交集: AB = x | (xA) (xB) xAB (xA) (xB)n初级交初级交(广义交广义交):不相交不相交(disjoint)n不相交不相交: AB=.n互不相交互不
20、相交: 设设A1,A2,是可数多个集合是可数多个集合, 若对于若对于 任意的任意的ij, 都有都有AiAj=, 则说它们互不相交则说它们互不相交.n例例: 设设An=xR|n-1xn, n=1,2,10, 则则A1,A2,是不相交的是不相交的.交集交集(举例举例)n例例1: 设设An=xR|n-1xn,n=1,2,10,则则n例例2: 设设An =xR|0x1/n,n=1,2,则则集合的交的性质集合的交的性质(1) AA=A 幂等律等律(2) A = 零律零律(3) AE = A 同一律同一律(4) AB=BA 交交换律律(5) (AB)C = A(BC) 结合律合律证明：明：设 x (AB)
21、C x (AB) xC (xA xB) xC xA (xB xC) x A(BC), 所以所以, (AB)C = A(BC).绝对补绝对补(complement)n绝对补绝对补: A=E-A, E是全集是全集, AEA= x | (xEx A)A= xE | x A)相对补集相对补集(set difference)n相对补集相对补集: 属于属于A而不属于而不属于B的全体元素的全体元素, 称为称为B对对A的相对补集的相对补集, 记作记作A-BA-B = x | (xA) (x B) 绝对补运算的性质绝对补运算的性质(a) A=A(b) E=(c) =E(d) A A=(e) A A=E对称差对称
22、差(symmetric difference)n对称差对称差: 属于属于A而不属于而不属于B, 或属于或属于B而不属于而不属于A的全的全体元素体元素, 称为称为A与与B的对称差的对称差,记作记作A B。 A B=x|(xAx B)(x AxB) A B=(A-B)(B-A)=(AB)-(AB)相对补、对称差、补相对补、对称差、补(举例举例)n例例: 设设A=xR|0x2, B=xR|1x3,则则A-B= xR|0x1=0,1)B-A= xR|2x3=2,3)A B=xR|(0x1)(2x3)=0,1)2,3)对称差的性质对称差的性质(a) A B=B A(b) A =A, A A = (c)
23、A E = A, A A=E(d) A(B C)=(AB) (AC)(e) (A B) C=A (B C)集合运算（应用举例）集合运算（应用举例） F:一年级大学生的集合一年级大学生的集合 S：二年级大学生的集合：二年级大学生的集合 R：计算机系学生的集合：计算机系学生的集合 M：数学系学生的集合：数学系学生的集合 T：选修离散数学的学生的集合：选修离散数学的学生的集合 L：爱好文学学生的集合：爱好文学学生的集合 P：爱好体育运动学生的集合：爱好体育运动学生的集合只有一、二年级的学生才爱好体育运动只有一、二年级的学生才爱好体育运动T (MR)SRS TM LPP FSS (MR) P除去数学和
24、计算机系二年级学生外都不除去数学和计算机系二年级学生外都不选修离散数学选修离散数学所有计算机系二年级学生都选修离散数学所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动数学系学生或爱好文学或爱好体育运动(MF)T=容斥原理容斥原理设设 S 为有穷集，为有穷集，P1, P2, , Pn 是是 n 种性质种性质, Ai 是是 S 中具中具有性质有性质 Pi 的元素构成的子集，的元素构成的子集，i=1, 2, , n. 则则 S 中具中具有性质有性质 P1, P2, , Pn的元素数为的元素数为*容斥原理容斥
25、原理(证明证明)n n=2时的情况时的情况:|AB|=|A|+|B|-|AB|n归纳证明归纳证明: 以以n=3为例为例: |AB C| = |(AB)C|= |AB|+|C|-|(AB)C| = |A|+|B|-|AB|+|C|-|(AC)(BC)| = |A|+|B|-|AB|+|C| -(|AC|+|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|ABABC容斥原理（续）容斥原理（续）推论推论 S 中不具有性质中不具有性质 P1, P2, , Pn的元素数为的元素数为容斥原理容斥原理(举例举例)n例例1: 在在1到到10000之间既不是
26、某个整数的平方之间既不是某个整数的平方, 也不是也不是某个整数的立方的数有多少某个整数的立方的数有多少?n解解: 设设E=xN|1x10000, |E|=10000A=xE|x=k2kZ, |A|=100B=xE|x=k3kZ, |B|=21 AB= xE|x=k6kZ, |AB|=4.则则|(AB)|=|E|-|AB|=|E|-(|A|+|B|-|AB|)=10000-100-21+4=9883#容斥原理容斥原理(举例，续举例，续)例例2 求求1到到1000之间（包含之间（包含1和和1000在内）既不能被在内）既不能被 5 和和6 整除，也不能被整除，也不能被 8 整除的数有多少个？整除的数
27、有多少个？解：解：S = x | x Z, 1 x 1000 , |S|=1000 如下定义如下定义 S 的的 3 个子集个子集 A, B, C： A= x | x S, 5|x ,|A|= 1000/5 =200, B= x | x S, 6|x , |B|= 1000/6 =133 C= x | x S, 8|x , |C|= 1000/8 =125 |AB|= 1000/30 =33, |AC| = 1000/40 =25, |BC|= 1000/24 =41, |ABC| = 1000/120 =8 |ABC|=1000 (200+133+125)+(33+25+41) 8=600容斥
28、原理容斥原理(举例，续举例，续)例例3 有有24名科技人员，每人至少会名科技人员，每人至少会1门外语，英语门外语，英语13人人, 日语日语5人人, 德语德语10人人, 法语法语9人人, 英日英日2人人, 英德英德4人；人； 英法英法4人人, 法德法德4人，会日语的不会法语、德语，人，会日语的不会法语、德语，求：只会求：只会 1 种语言的人数，会种语言的人数，会 3 种语言的人数种语言的人数.解：解：设会三种语言的有设会三种语言的有x, 只会英语的有只会英语的有y1，只会德语有只会德语有y2，只会法语的有只会法语的有y3 ，绘出文氏图，绘出文氏图 。x+2(4-x)+y1+2=13x+2(4-x)+y2=10x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19解得解得 x=1, y1=4, y2=3, y3=2.日日语语英语英语法语法语德语德语总结总结n集合概念集合概念: , , E, , ,n集合运算集合运算: , , -, , , P(A)n文氏图文氏图n容斥原理容斥原理n作业作业:p20, 习题一习题一, 3, 10, 16，32n复习复习:(1) , , -, , , P(A)的谓词逻辑表达式的谓词逻辑表达式 (2) 运算运算, , -, , , P(A)的性质的性质
