离散数学：第1讲 集合的概念与运算.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第,1,节,集合的概念与运算,1.,集合的概念,2.,集合之间的关系,3.,集合的运算,4.,文氏图,2,集合论,(set theory),十九世纪数学最伟大成就之一,集合论体系,朴素,(naive),集合论,公理,(axiomatic),集合论,创始人康托,(Cantor),Georg Ferdinand,Philip Cantor 1845 1918,俄罗斯,德国数学家,集合论创始人,.,3,什么是集合,(set),集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素,(element),或成员,(member),用大写英文字母,A,B,C,表示集合,用小写英文字母,a,b,c,表示元素,a,A,：,表示,a,是,A,的元素，读作,“,a,属于,A,”,a,A,：,表示,a,不,是,A,的元素，读作,“,a,不,属于,A,”,4,集合的表示,列举法,描述法,特征函数法,5,列举法,(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,6,描述法,(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,7,描述法（续）,两种表示法可以互相转化，例如,E=2,4,6,8,=x|x0,且,x,是偶数,=x|x=2(k+1),，,k,为非负整数,=2(k+1)|k,为非负整数,有些书在列举法中用,:,代替,|,例如,2(k+1):k,为非负整数,8,特征函数法,(,characteristic function,),集合,A,的特征函数是,A,(x):,1,，若,x,A,A,(x)=,0,，,若,x,A,9,数的集合,N,：自然数,(natural numbers),集合,N=,0,1,2,3,Z,或,I,：整数,(integers),集合,Z=0,1,2,=,-2,-1,0,1,2,Q,：有理数,(rational numbers),集合,R,：实数,(real numbers),集合,C,：复数,(complex numbers),集合,10,集合之间的关系,相等、子集、真子集,空集、全集,幂集、,n,元集、有限集,11,相等,(equal),相等,:,（外延性原理）有相同的元素。记作,A=B,A=B,x(xAxB),不相等：记作,AB,1,，,2,，,4=1,，,4,，,2,1,，,2,，,2,，,3=1,，,2,，,3,但,1,，,2,，,3,与,1,，,2,，,3,呢？,12,子集,(subset),子集,:,若,B,中的元素也都是,A,中的元素,则称,B,为,A,的子集,或说,B,包含于,A,或说,A,包含,B,记作,B,A,B,A x(xBxA),若,B,不是,A,的子集,则记作,B,A,B,A x(xBxA),x(xBxA)x(xBxA),x(xBxA)x(xBxA),13,子集,(,举例,),设,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,14,相等,(equal),相等,:,（外延性原理）有相同的元素,定理：互相包含的集合是相等的（互为子集）,.,A=B,A,B BA,A,BBA,x(xAxB)x(xBxA)(,定义,),x(xAxB)(xBxA)(,量词分配,),x(xAxB)(,等值式,),A=B,15,包含,(,),的性质,AA,证明,:AAx(xAxA)1,若,AB,且,AB,则,B,A,证明,:A,B,(,A=B),(,A,BBA)(,定义,),(,A,B)(BA)(,德,摩根律,),AB(,已知,),BA(,即,B,A)#,16,包含,(,),的性质,(,续,),若,AB,且,BC,则,AC,证明,:A,B x(xAxB),x,xA,xB (AB),xC (BC),x(xAxC),即,AC.#,17,真子集,(proper subset),真子集,:B,真包含,A:,A,B,A,B AB,A,B (,A,B AB)(,定义,),(,A,B)(A=B)(,德,摩根律,),x(xAxB)(A=B)(,定义,),A,B?,18,真包含,(,),的性质,证明,:A,B,A,B AB,A,B (,化简,),同理,B,C BC,所以,A,C.,假设,A=C,则,BCBA,又,A,B,故,A=B,此与,A,B,矛盾,所以,AC.,所以,AC.,#,若,AB,且,BC,则,AC,19,空集,(empty set),空集,:,没有任何元素的集合是空集,记作,例如,xR|x,2,+1=0,定理,1:,对任意集合,A,A,证明,:Ax(xxA),x(0 xA)1.#,推论,:,空集是唯一的,.,证明,:,设,1,与,2,都是空集,则,1,2,2,1,1,=,2.,#,20,全集,全集,:,如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作,E,全集是相对的,视情况而定,因此不唯一,.,例如,讨论,(a,b),区间里的实数性质时,可以选,E=(a,b),21,幂集,(power set),幂集,:A,的全体子集组成的集合,称为,A,的幂集,记作,P,(A),P,(A)=x|x,A,注意,:x,P,(A)xA,例,:A=a,b,P,(A)=,a,b,a,b.#,22,n,元集,(n-set),n,元集,:,含有,n,个元素的集合称为,n,元集,0,元集,:,1,元集,(,或单元集,),如,a,b,|A|:,表示集合,A,中的元素个数,A,是,n,元集,|A|=n,有限集,(finite set):|A|,是有限数,|A|,也叫有穷集,23,幂集计数问题,定理,:|A|=n,|,P,(A)|=2,n,A,a,1,a,1,a,2,a,3,a,n,a,1,a,3,证明,:,每个子集对应一种染色,一共有,2,n,种不同,染色,.#,24,集合之间的运算,交集、并集,相对补集、绝对补、对称差,25,文氏图,(Venn diagram),文氏图,:,平面上的,n,个圆,(,或椭圆,),使得任何可能的相交部分,都是非空的和连通的,John Venn,18341923,例,:,26,文氏图,(,应用,),文氏图可表示集合运算,(,结果用阴影表示,),A,B,A,B,A-,B,A,B,A,A,A,A,A,A,A,B,B,B,B,B,A,B=,27,交集,(intersection),交集,:,由集合,A,和,B,的所有共同元素组成的集合,S,，称为集合,A,和,B,交集，记作,A,B,A,B=x|(x,A),(,x,B),x,A,B,(x,A),(,x,B),A,B,A,B,28,交集,(,举例,),例,1:,设,A=x,R|n-1xn,n=1,2,10,则,29,交集性质,若,A,B,，则,A,C,B,C,A,B,A,，,A,B,B,30,不相交,(disjoint),不相交,:A,B=,互不相交,:,设,A,1,A,2,A,n,是,n,个集合,若对于任意的,i,j,都有,A,i,B,j,=,则说它们互不相交,例,:,设,A,n,=x,R|n-1xn,n=1,2,10,则,A,1,A,2,是,互,不相交的,A,B,A,B=,31,n,个集合的交集,32,交集,(,举例,),例,2:,设,A,n,=x,R|0 x1/n,n=1,2,则,33,并集,(union),并集,:,所有属于集合,A,或属于集合,B,的元素组成的集合,S,，称为集合,A,和,B,交集，记作,A,B,A,B=x|(x,A),(,x,B),x,A,B,(x,A),(,x,B),A,B,A,B,34,并集,(,举例,),例,1:,设,A,n,=x,R|n-1xn,n=1,2,10,则,35,并集性质,若,A,B,，则,A,C,B,C,A,A,B,，,B,A,B,36,n,个集合的并集,并集满足结合律,37,并集,(,举例,),例,2:,设,A,n,=x,R|0 x1/n,n=1,2,则,38,分配律,A,(B C),=(A,B),（,A,C,）,A,(B,C),=(A,B),（,A,C,）,39,相对补集,(set difference),相对补集,:,属于,A,而不属于,B,的全体元素,称为,B,对,A,的相对补集,记作,A-B,A-B=x|(x,A),(,x,B),A-,B,A,B,40,相对补,(,举例,),例,:,设,A=,0,，,2,A=,1,，,2,，,3,则,A-B=,0,B-A=1,，,3,41,绝对补,(complement),绝对补,:A=,E-A,E,是全集,AE,A=x|(x,E,x,A,),A=x,E|,x,A,),A,A,42,对称差,(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,43,对称差,(,举例,),例,:,设,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),),),),44,作业,P96 4,6,8,9,12,14,