《集合概念和运算》PPT课件.ppt

lisanshuxueouc2011,1,第3讲集合的概念与运算,1.集合的概念2.集合之间的关系3.集合的运算4.文氏图、容斥原理,*表示不要求，表示要求自学,lisanshuxueouc2011,2,集合论(settheory),十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)GeorgFerdinandPhilipCantor18451918德国数学家,集合论创始人.,lisanshuxueouc2011,3,集合结构,离散数学的大部分内容是研究离散结构，表现离散对象。很多重要的离散结构是用集合来构造的，即对象的联合。例如组合，计数，关系，用来表现关系的序偶集合，图，结点和联结结点的边的集合，用来模拟计算机的有限状态机等。,lisanshuxueouc2011,4,集合论的起源与发展,集合论(SetTheory)是现代数学的基础它的起源可追溯到16世纪末，主要是对数集进行卓有成效的研究19世纪70年代德国数学家康托尔(G.Cantor)在无穷序列和分析的有关课题的理论研究中创立了集合论康托尔对具有任意特性的无穷集合进入了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础因此，康托尔被誉为集合论的创始人,lisanshuxueouc2011,5,康托尔的基本理论,康托尔集合论（朴素集合论）中的许多证明均能从三个公理得出这三个公理是:外延公理:如果两个集合中各个元素都是相同的，则它们相等抽象公理:任给一个性质，都有一个满足该性质的客体所组成的集合选择公理:每个集合都有一个选择函数但是,抽象公理产生了悖论，选择性公理让人困惑.,lisanshuxueouc2011,6,集合论的起源与发展(罗素悖论),当人们认为集合论足够严谨时,在本世纪初,出现了许多悖论,如著名的罗素悖论(即理发师悖论),有力冲击了或者说动摇了集合论的发展罗素悖论：由“不属于该集合的所有客体组成集合”会导出矛盾.论证把抽象公理符号化为：(y)(x)(xy(x)其中,(x)是不以y为自由变元的公式.把(x)取为“x不为y的成员”,即(x)=(xy).则罗素悖论符号化为(y)(x)(xy(xy)取xy，可得(y)(y)(yy(yy),lisanshuxueouc2011,7,集合论的起源与发展(公理化体系),许多数学家哲学家为克服这些矛盾而建立了各种公理化集合论体系(“这些原则必须足够狭窄，以保证排除一切矛盾；另一方面又必须充分广阔，使康托尔集合论中一切有价值的内容得以保存下来”)，其中以20世纪初、中期的ZFS(E.Zermelo,A.Fraenkel,T.Skolem)和NBG(VonNeurnann,P.Bernavs,K.Gdel)公理化体系最为流行.到20世纪60年代，P.L.Cohen发明了强制方法而得到了关于连续统与选择公理的独立性成果，而后的研究结果推陈出新，大量涌现,lisanshuxueouc2011,8,集合论的起源与发展（续）,在同一时代，美国数学家L.A.Zadeh提出了Fuzzy集理论,以及20世纪80年代波兰数学家Z.Pawlak发表了Rough集理论，这两种理论区别于以往的集合论，是一种新的模糊集理论，受到了学术界的重视和青睐，取得了喜人成果还有多位著名学者也为集合论的发展作出了重要贡献在此基础上，逐步形成了公理化集合论和抽象集合论，使该学科成为数学中发展最为迅速的一个分支。集合论观点已渗透到古典分析、泛函、概率、函数论以及信息论、排队论等现代数学各个领域。,lisanshuxueouc2011,9,集合(set),集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,表示集合用小写英文字母a,b,c,表示元素aA：表示a是A的元素，读作“a属于A”aA：表示a不是A的元素，读作“a不属于A”,lisanshuxueouc2011,10,集合的表示,列举法描述法特征函数法,lisanshuxueouc2011,11,列举法(roster),列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如A=a,b,c,d,x,y,zB=0,1,2,3,4,5,6,7,8,9集合中的元素不规定顺序C=2,1=1,2集合中的元素各不相同(多重集除外)C=2,1,1,2=2,1,lisanshuxueouc2011,12,多重集(multipleset),多重集:允许元素多次重复出现的集合元素的重复度:元素的出现次数(0).例如:设A=a,a,b,b,c是多重集元素a,b的重复度是2元素c的重复度是1元素d的重复度是0,lisanshuxueouc2011,13,描述法(definingpredicate),用谓词P(x)表示x具有性质P，用x|P(x)表示具有性质P的集合，例如P1(x):x是英文字母A=x|P1(x)=x|x是英文字母=a,b,c,d,x,y,zP2(x):x是十进制数字B=x|P2(x)=x|x是十进制数字=0,1,2,3,4,5,6,7,8,9,lisanshuxueouc2011,14,描述法（续）,两种表示法可以互相转化，例如E=2,4,6,8,=x|x0且x是偶数=x|x=2(k+1)，k为非负整数=2(k+1)|k为非负整数有些书在描述法中用:代替|,例如2(k+1):k为非负整数,lisanshuxueouc2011,15,特征函数法(characteristicfunction),集合A的特征函数是:对多重集,:x在A中的重复度.,lisanshuxueouc2011,16,常用的数集合,N：自然数(naturalnumbers)集合N=0,1,2,3,Z(I)：整数(integers)集合Z=0,1,2,=,-2,-1,0,1,2,Q：有理数(rationalnumbers)集合R：实数(realnumbers)集合C：复数(complexnumbers)集合,lisanshuxueouc2011,17,集合之间的关系,子集、相等、真子集空集、全集幂集、n元集、有限集集族,lisanshuxueouc2011,18,子集(subset),B包含于A,A包含B:BAx(xBxA)B不是A的子集:BAx(xBxA)x(xBxA)x(xBxA)x(xBxA)x(xBxA),lisanshuxueouc2011,19,相等(equal),相等:A=BABBAx(xAxB)A=BABBA(=定义)x(xAxB)x(xBxA)(定义)x(xAxB)(xBxA)(量词分配)x(xAxB)(等值式),lisanshuxueouc2011,20,包含()的性质,AA证明:AAx(xAxA)1若AB,且AB,则BA证明:AB(A=B)(ABBA)(=定义)(AB)(BA)(德摩根律)AB(已知)(BA)(即BA)(析取三段论)#(AB)BA析取三段论),lisanshuxueouc2011,21,包含()的性质(续),若AB,且BC,则AC(传递性)证明:ABx(xAxB)x,xAxB(AB)xC(BC)x(xAxC),即AC.#,lisanshuxueouc2011,22,真子集(propersubset),真子集:B真包含A:ABABABAB(ABAB)(定义)(AB)(A=B)(德摩根律)x(xAxB)(A=B)(定义),lisanshuxueouc2011,23,真包含()的性质,AA证明:AAAAAA100.#若AB,则BA证明:(反证)设BA,则ABABABAB(化简)BABABABA所以ABBAA=B(=定义)但是ABABABAB(化简)矛盾!#,lisanshuxueouc2011,24,真包含()的性质(续),若AB,且BC,则AC证明:ABABABAB(化简律),同理BCBC,所以AC.假设A=C,则BCBA,又AB,故A=B,此与AB矛盾,所以AC.所以,AC.#,lisanshuxueouc2011,25,空集(emptyset),空集:没有任何元素的集合是空集,记作。例如,xR|x2+1=0定理1:对任意集合A,A证明:Ax(xxA)x(0xA)1.#推论:空集是唯一的.证明:设1与2都是空集,则12211=2.#,lisanshuxueouc2011,26,全集,全集:如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E。全集是相对的,视情况而定,因此不唯一.例如,讨论(a,b)区间里的实数性质时,可以选E=(a,b),E=a,b),E=a,b,E=(a,+),E=(-,+)等,lisanshuxueouc2011,27,n元集(n-set),n元集:含有n个元素的集合称为n元集。0元集:。1元集(或单元集),如a,b,。|A|:表示集合A中的元素个数,A是n元集|A|=n有限集(fimiteset):|A|是有限数,|A|0,Aa=0,a),Aa|aR+的指标集是R+.,lisanshuxueouc2011,33,集合之间的运算,并集、交集相对补集、绝对补、对称差广义并集、广义交集,lisanshuxueouc2011,34,文氏图(Venndiagram),文氏图(VennDiagram)以英国数学家JohnVenn命名.,lisanshuxueouc2011,35,并集(union),并集:AB=x|(xA)(xB)xAB(xA)(xB)初级并(广义并):,lisanshuxueouc2011,36,并集(举例),例1:设An=xR|n-1xn,n=1,2,10,则例2:设An=xR|0x1/n,n=1,2,则,lisanshuxueouc2011,37,集合的并的性质,(1)AA=A幂等律(2)A=A同一律(3)AE=E零律(4)AB=BA交换律(5)(AB)C=A(BC)结合律,lisanshuxueouc2011,38,交集(intersection),交集:AB=x|(xA)(xB)xAB(xA)(xB)初级交(广义交):,lisanshuxueouc2011,39,不相交(disjoint),不相交:AB=.互不相交:设A1,A2,是可数多个集合,若对于任意的ij,都有AiAj=,则说它们互不相交.例:设An=xR|n-1xn,n=1,2,10,则A1,A2,是不相交的.,lisanshuxueouc2011,40,交集(举例),例1:设An=xR|n-1xn,n=1,2,10,则例2:设An=xR|0x1/n,n=1,2,则,lisanshuxueouc2011,41,集合的交的性质,(1)AA=A幂等律(2)A=零律(3)AE=A同一律(4)AB=BA交换律(5)(AB)C=A(BC)结合律证明：设x(AB)Cx(AB)xC(xAxB)xCxA(xBxC)xA(BC),所以,(AB)C=A(BC).,lisanshuxueouc2011,42,绝对补(complement),绝对补:A=E-A,E是全集,AEA=x|(xExA)A=xE|xA),lisanshuxueouc2011,43,相对补集(setdifference),相对补集:属于A而不属于B的全体元素,称为B对A的相对补集,记作A-BA-B=x|(xA)(xB),lisanshuxueouc2011,44,绝对补运算的性质,(a)A=A(b)E=(c)=E(d)AA=(e)AA=E,lisanshuxueouc2011,45,对称差(symmetricdifference),对称差:属于A而不属于B,或属于B而不属于A的全体元素,称为A与B的对称差,记作AB。AB=x|(xAxB)(xAxB)AB=(A-B)(B-A)=(AB)-(AB),lisanshuxueouc2011,46,相对补、对称差、补(举例),例:设A=xR|0x2,B=xR|1x3,则A-B=xR|0x1=0,1)B-A=xR|2x3=2,3)AB=xR|(0x1)(2x3)=0,1)2,3),lisanshuxueouc2011,47,对称差的性质,(a)AB=BA(b)A=A,AA=(c)AE=A,AA=E(d)A(BC)=(AB)(AC)(e)(AB)C=A(BC),lisanshuxueouc2011,48,集合运算（应用举例）,F:一年级大学生的集合S：二年级大学生的集合R：计算机系学生的集合M：数学系学生的集合T：选修离散数学的学生的集合L：爱好文学学生的集合P：爱好体育运动学生的集合,lisanshuxueouc2011,49,容斥原理,设S为有穷集，P1,P2,Pn是n种性质,Ai是S中具有性质Pi的元素构成的子集，i=1,2,n.则S中具有性质P1,P2,Pn的元素数为,lisanshuxueouc2011,50,*容斥原理(证明),n=2时的情况:|AB|=|A|+|B|-|AB|归纳证明:以n=3为例:|ABC|=|(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|,lisanshuxueouc2011,51,容斥原理（续）,推论S中不具有性质P1,P2,Pn的元素数为,lisanshuxueouc2011,52,容斥原理(举例),例1:在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?解:设E=xN|1x10000,|E|=10000A=xE|x=k2kZ,|A|=100B=xE|x=k3kZ,|B|=21AB=xE|x=k6kZ,|AB|=4.则|(AB)|=|E|-|AB|=|E|-(|A|+|B|-|AB|)=10000-100-21+4=9883#,lisanshuxueouc2011,53,容