集合的概念与运算.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第3讲 集合的概念与运算,1.集合的概念,2.集合之间的关系,3.集合的运算,4.,文氏图、容斥原理,集合论(,set theory),十九世纪数学最伟大成就之一,集合论体系,朴素,(,naive),集合论,公理(,axiomatic),集合论,创始人,康托,(,Cantor),Georg,Ferdinand,Philip Cantor 1845 1918,德国数学家,集合论创始人.,什么是集合(,set),集合,：,不能精确定义。一些对象的整体就构成,集合,，这些对象称为,元素,(,element),或,成员,(,member),用大写英文字母,A,B,C,表示集合,用小写英文字母,a,b,c,表示元素,a,A,：,表示,a,是,A,的元素，读作“,a,属于,A,”,a,A,：,表示,a,不,是,A,的元素，读作“,a,不,属于,A,”,集合的表示,列举法,描述法,特征函数法,列举法(,roster),列出集合中的,全体元素,，元素之间用,逗号,分开，然后用,花括号,括起来，例如,A=a,b,c,d,x,y,z,B=0,1,2,3,4,5,6,7,8,9,集合中的元素不规定顺序,C,=2,1=1,2,集合中的元素各不相同(,多重集,除外),C,=2,1,1,2=2,1,多重集(,multiple set),多重集,:允许元素多次重复出现的集合,元素的,重复度,:元素的出现次数(,0,).,例如:设,A=a,a,b,b,c,是多重集,元素,a,b,的重复度是,2,元素,c,的重复度是,2,元素,d,的重复度是,0,描述法(,defining predicate),用,谓词,P(x),表示,x,具有性质,P,，用,x,|,P(x),表示具有性质,P,的集合，例如,P,1,(x):,x,是英文字母,A=x|P,1,(x)=x|x,是英文字母,a,b,c,d,x,y,z,P,2,(x):,x,是十进制数字,B=x|P,2,(x)=x|x,是十进制数字,=0,1,2,3,4,5,6,7,8,9,描述法（续）,两种表示法可以互相转化，例如,E=2,4,6,8,=x|x0,且,x,是偶数,=x|x=2(k+1)，k,为非负整数,=2(k+1),|,k,为非负整数,有些书在列举法中用,:,代替,|,例如,2(k+1),:,k,为非负整数,特征函数法(,characteristic function,),集合,A,的,特征函数,是,A,(x):,1,，,若,x,A,A,(x)=,0,，,若,x,A,对多重集,A,(x)=x,在,A,中的重复度,数的集合,N：,自然数(,natural numbers),集合,N=,0,1,2,3,Z：,整数(,integers),集合,Z=0,1,2,=,-2,-1,0,1,2,Q：,有理数(,rational numbers),集合,R：,实数(,real numbers),集合,C：,复数(,complex numbers),集合,集合之间的关系,子集、相等,、,真子集,空集,、,全集,幂集,、n,元集,、,有限集,集族,子集(,subset),子集,:若,B,中的元素也都是,A,中的元素,则称,B,为,A,的子集,或说,B,包含于,A,或说,A,包含,B,记作,B,A,B,A x(xBxA),若,B,不是,A,的子集,则记作,B,A,B,A x(xBxA),x(xB,xA),x,(,xB,xA),x,(,xB,xA)x(xBx,A),子集(举例),设,A=a,b,c,B=a,b,c,d,C=a,b,则,A,B,CA,CB,A,C,B,a,b,c,d,e,f,g,h,i,j,相等(,equal),相等:互相包含的集合是相等的.,A=B,A,B BA,A=B,x(xA,xB),A=B,A,BBA (=,定义),x(xAxB),x(xBxA)(,定义),x(xA,xB)(xB,xA)(,量词分配),x(xA,xB)(,等值式),包含(,)的性质,AA,证明:,AAx(xAxA)1,若AB,且,AB,则,B,A,证明:,A,B,(,A=B),(,A,BBA)(,定义),(,A,B),(,BA)(,德,摩根律),AB(,已知),BA(,即,B,A,)(析取三段论),#,包含(,)的性质(续),若,AB,且,BC,则,AC,证明:,A,B x(xAxB),x,xA,xB (AB),xC (BC),x(xAxC),即,AC.#,真子集(,proper subset),真子集,:,B,真包含,A:,A,B,A,B AB,A,B,(,A,B AB)(,定义),(,A,B),(A=B)(,德,摩根律),x(xAxB),(A=B)(,定义),真包含(,)的性质,AA,证明:,A A,AA AA 10 0.#,若,AB,则,BA,证明:(反证)设,B,A,则,A,B,A,B AB,A,B (,化简),B,A BA BA BA,所以,A,B BA A=B(=,定义),但是,A,B,A,B AB AB(,化简),矛盾!,#,真包含(,)的性质(续),若,AB,且,BC,则,AC,证明:,A,B,A,B AB,A,B (,化简),同理,B,C BC,所以,A,C.,假设,A=C,则,BCBA,又,A,B,故,A=B,此与,A,B,矛盾,所以,AC.,所以,AC.,#,空集(,empty set),空集,:没有任何元素的集合是空集,记作,例如,xR|x,2,+1=0,定理1:对任意集合,A,A,证明:,Ax(,x,xA),x(,0,xA)1.#,推论:空集是唯一的.,证明:设,1,与,2,都是空集,则,1,2,2,1,1,=,2.,#,全集,全集,:如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作,E,全集是,相对的,视情况而定,因此,不唯一,.例如,讨论(,a,b),区间里的实数性质时,可以选,E=(a,b),E=a,b),E=(a,B,E=a,b,E=(a,+,),E=(-,+),等,幂集(,power set),幂集,:,A,的全体子集组成的集合,称为,A,的幂集,记作,P(A),P(A)=x|x,A,注意:,x,P(A)xA,例子:,A=a,b,P(A)=,a,b,a,b.,#,n,元集(,n-set),n,元集,:含有,n,个元素,的集合称为,n,元集,0元集:,1元集(或,单元集),如,a,b,|A|,:,表示集合,A,中的,元素个数,A,是,n,元集,|A|=n,有限集,(,fimite,set):|A|,是有限数,|,A|0,A,a,=0,a),A,a,|,a,R,+,的指标集是,R,+,0,a,集合之间的运算,并集、交集,相对补集、对称差、绝对补,广义并集、广义交集,并集(,union),并集,:,A,B=x|(x,A),(,x,B),x,A,B,(x,A),(,x,B),初级并,:,并集(举例),例1:设,A,n,=x,Rn-1xn,n=1,2,10,则,例2:设,A,n,=x,R|0 x1/n,n=1,2,则,交集(,intersection),交集,:,A,B=x|(x,A),(,x,B),x,A,B,(x,A),(,x,B),初级交,:,交集(举例),例1:设,A,n,=x,R|n-1xn,n=1,2,10,则,例2:设,A,n,=x,R|0 x1/n,n=1,2,则,不相交(,disjoint),不相交,:,A,B=,互不相交,:设,A,1,A,2,是可数多个集合,若对于任意的,i,j,都有,A,i,B,j,=,则说它们互不相交,例:,设,A,n,=x,R|n-1xn,n=1,2,10,则,A,1,A2,是不相交的,相对补集(,set difference),相对补集,:属于,A,而不属于,B,的全体元素,称为,B,对,A,的相对补集,记作,A-B,A-B=x|(x,A),(,x,B),A-,B,A,B,对称差(,symmetric difference),对称差,:属于,A,而不属于,B,或属于,B,而不属于,A,的全体元素,称为,A,与,B,的对称差,记作,A,B,A,B=x|(x,A,x,B),(x,A,x,B),A,B=(A-B),(B-A)=(AB)-(AB),A,B,A,B,绝对补(,complement),绝对补,:,A,=,E-A,E,是全集,AE,A=x|(x,E,x,A,),A=x,E|,x,A,),A,A,相对补、对称差、补(举例),例:设,A=x,R|0 x2,A=x,R|1x3,则,A-B=x,R|0 x1,=0,1),B-A=x,R|2x3,=2,3),A,B=x,R|(0 x1),(,2x3,),=0,1),2,3),),),),广义并集(,big union),广义并,:设,A,是集族,A,中所有集合的元素的全体,称为,A,的广义并,记作,A,.,A,=,x|,z(xzz,A,当是以,S,为指标集的集族时,A,=,A,|,S=,A,S,例:设,A,=,a,b,c,d,d,e,f,则,A=,a,b,c,d,e,f,广义交集(,big intersection),广义交,:设,A,是集族,A,中所有集合的公共元素的全体,称为,A,的广义交,记作,A,.,A,=,x|,z(z,A,xz),当是以,S,为指标集的集族时,A,=,A,|,S=,A,S,例:设,A,=1,2,3,1,a,b,1,6,7,则,A=,1,广义交、广义并(举例),设,A,1,=,a,b,c,d,A,2,=,a,b,A,3,=,a,A,4,=,A,5,=,a(a,),A,6,=,则,A,1,=,a,b,c,d,A,1,=,a,b,c,d,A,2,=,a,b,A,2,=,a,b,A,3,=,a,A,3,=,a,A,4,=,=,A,4,=,=,A,5,=,a,A,5,=,aA,6,=,A,6,=,E,文氏图(,Venn diagram),文氏图,:平面上的,n,个圆(或椭圆),使得任何可能的,相交部分,都是,非空,的和,连通,的,John Venn,18341923,例:,文氏图(应用),文氏图可表示集合运算(结果用阴影表示),A,B,A,B,A-,B,A,B,A,A,A,A,A,A,A,B,B,B,B,B,A,B=,文氏图(问题),Venn,曾经构造出4个椭圆的文氏图,并且断言:没有5个椭圆的文氏图,Peter Hamburger&Raymond,Pippert,1996,构造出5个椭圆的文氏图,Can you try it?,文氏图(续),试试,n=4:,14 16,文氏图(续),试试,n=5,17 +,5 32,容斥原理(,principle of inclusion/exclusion,),容斥原理,(或,包含排斥原理,),容斥原理(证明),n=2,时的情况:,|,A,B|=|A|+|B|-|AB|,归纳证明:以,n=3,为例:,|,A,B C|=,|,(,A,B)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|,A,B,B,C,A容斥原理(举例),例1:在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?,解:设,E=x,N|1x10000,|E|=10000,A,=x,E|x=k,2,kZ,|A|=,100,B,=x,E|x=k,3,kZ,|B|=,21,则|(,A,B,)|=|E|-|A,B|,=,|E|-(,|A|+|B|-|AB|),=10000-100-21+4=9883,注意,AB,=,x,E|x=k,6,kZ,|AB|=,4,.#,容斥原理(举例、续),例2:在24名科技人员中,会说,英,日,德,法语,的人数分别为,13,5,10,和,9,其中同时会说英语,德语,或同时会说英语,法语,或同时会说德语,法语两种语言的人数均为,4,.会说日语的人既不会说法语也不会说德语.试求只会说一种语言的人数各为多少?又同时会说英,德,法语的人数有多少?,解:设,E=x,|x,是24名科技人员之一,|,E|=24,A,=x,E|x,会说,英语,B,=x,E|x,会说,日语,C,=x,E|x,会说,德语,D,=x,E|x,会说,法语,容斥原理(举例、续),解(续):设所求人数分别为,x,1,x,2,x,3,x,4,x(,如图),A,=x,E|x,会说,英语,|A|=13,B,=x,E|x,会说,日语,|B|=5,C,=x,E|x,会说,德语,|C|=10,D,=x,E|x,会说,法语,|D|=9,首先,x,2,=|B|-|A,B|=,5-2=,3,其次,对,A,C,D,用容斥原理,注意,|E|=24:,24-3=,21,=13+10+9-4-4-4+x=,20+x,得,x,=,1,最后,x,1,=|A|-|A,B|,-3-3-1=13-2-7=,4,同理,x,3,=10-3-3-1=,3,x,4,=9-3-3-1=,2,.#,D,C,B,A,X,X,1,X,2,X,3,X,4,4-X,4-X,4-X,2,总结,集合概念:,E,集合运算:,-,P(),文氏图,容斥原理,习题(#1),p25,习题一,3,7,10,16,