(黄)第1章集合(2016-3-12)讲解.ppt

离散数学,第1章集合,1集合的基本概念2集合的基本运算,2,集合的基本概念,本节要求掌握的知识点：1、集合的概念2、集合的几种表示方法3、子集（真子集），集合相等（证明？）4、全集和补集（余集）5、幂集，集合的基，有限集合的幂集的基？,3,现代集合论的创立者：康托（GeorgCantor）德国数学家贡献：超限数，康托对角线法的发现,由于他的理论超越直观，所以曾受到当时一些大数学家的反对，克莱因（Klein,ChristianFelix)、庞加莱(HenriPoincare)、韦尔(HermannWeyl)等著名数学家对康托的集合论持激烈的反对态度,把康托的集合论贬为“病理情形”、HermannWeyl称Cantor的的等级为“雾上之雾”（fogonfog),把康托本人称作“疯子”。,GeorgCantor,1845-1918,甚至他的老师克罗内克（L.Kronecker）攻击康托是神经质，走进了超越数的地狱.对于这些非难和指责，康托仍充满信心，他说:我的理论犹如磐石一般坚固，任何反对它的人将搬起石头砸自己的脚.他还指出:数学的本质在于它的自由性，不必受传统观念束缚。这种争辩持续了十年之久。康托由于经常处于精神压抑之中，致使他1884年患了精神分裂症，最后死于精神病院。,伟大德国数学家希尔伯特（DavidHilbert）1926年曾说道：“没有人能把我们从康托为我们创造的乐园中驱赶走”,1897年举行的第一次国际数学家会议，Cantor的成就得到承认。,DavidHilbert1862-1943,并称Cantor的超限算数为“数学思想最惊人的产物，在纯粹理性的范畴中人类的最美观的表现之一”,（NooneshallexpelusfromtheparadisewhichCantorcreatedforus.),(themostastonishingproductofmathematicalthought,oneofthemostbeautifulrealizatiomsofhumanactivityinthedomainofthepurelyintelligible.),伯特兰罗素（BertrandRussell）把康托的工作描述为probablythegreatestofwhichtheagecanboast.（可能是这个时代所能夸耀的最伟大的工作）,BertrandRussell1872-1970,BertrandRussell英国数学家、数理逻辑学家，哲学家，无神论或者不可知论者，也是上世纪西方最著名、影响最大的学者与和平主义社会活动家之一。1950年获Nobel文学奖以表彰其“多样且重要的作品，持续不断的追求人道主义理想和思想自由”。,数学原理,西方哲学史,幸福之路,物的分析等,朴素集合论中存在悖论,一、罗素悖论（Russellsparadox）(导致第三次数学危机）,一个乡村理发师自称他只给不给自己理发的人理发。,理发师给自己理发,理发师不给自己理发,理发师不给自己理发,理发师给自己理发,罗素悖论的通俗形式（乡村理发师悖论）,现在的问题是这个理发师给不给自己理发？,理发师陷入了两难：进退维谷,二、由一切集合构成的集合的悖论,是集合会导致罗素悖论,解决此悖论方法：,不再是集合，而把它称为真类（properclass）。,若,庄子与惠子游于濠梁之上。庄子曰：“鲦鱼出游从容，是鱼乐也。”惠子曰：“子非鱼，安知鱼之乐？”庄子曰：“子非我，安知我不知鱼之乐？”惠子曰：“我非子，固不知子矣，子固非鱼也，子不知鱼之乐，全矣。”庄子曰：“请循其本。子曰汝安知鱼乐云者，既已知吾知之而问我，我知之濠上也。”,濠梁之辩,庄子秋水,囚徒困境,庄周梦蝶（庄子齐物论）,昔者庄周梦为蝴蝶，栩栩然蝴蝶也，自喻适志与，不知周也。俄然觉，则蘧蘧然周也。不知周之梦为蝴蝶与，蝴蝶之梦为周与？周与蝴蝶，则必有分矣。此之谓物化。,过去庄周梦见自己变成蝴蝶，很生动逼真的一只蝴蝶，感到多么愉快和惬意啊！不知道自己原本是庄周。突然间醒过来，惊惶不定之间方知原来是我庄周。不知是庄周梦中变成蝴蝶呢，还是蝴蝶梦中变成庄周呢？庄周与蝴蝶那必定是有区别的。这就可叫作物、我的交合与变化。,译文,BashGame:同余理论NimGame:异或理论WythoffGame:黄金分割,BashGame:同余理论,一堆n个物品,两人轮流取,每次取1至m个,最后取完者胜.(mn),接着如果后取者再拿走k(1km)个，那么先取者再拿走(m+1-k)个，结果剩下(m+1)(r-1)个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。,1.如果n=m+1，后取者取胜。,2.如果n=(m+1)r+s,(r为任意自然数,0sm),(1)当s=0时，后取者胜；,(2)当1sm时,那么先取者要拿走s个物品,NimGame:异或理论,m堆物品，每堆若干件物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜.,所有物品数目二进制按位的异或为0,先手必输.所有物品数目二进制按位的异或不为0,后手必输.,当m=3时，也称为三堆物博弈,设现有三堆棋子，三堆的数量分别为a,b,c,甲乙两人轮流从这三堆中取棋子，游戏规则如下：甲先取棋子，每人每一次只能选定任意一堆，从这一堆取棋子的数量不限，但至少要从这一堆中选取一个，谁最先取完这三堆棋子谁胜。对于下列三种情形：,问甲、乙二人谁有胜的策略。若甲有胜的策略，甲第一回合应如何取；若乙有胜的策略，在甲第一回合从第一堆个中取走2个后，乙第一回合应如何正确地应对？请用二进制数的异或理论加以说明。,（1）(a,b,c)=(13,22,27),（2）(a,b,c)=(23,10,13),（3）(a,b,c)=(21,29,15),（1）(a,b,c)=(13,22,27),a=13,b=22,c=27,1101,10110=11011,11011,00000,解,乙有胜的策略。,1101,10110,在甲第一回合从一堆个中取走2个后，,1011,10110,11011,00110,10000,11011,00000,1011,-,=110,乙第一回合应从第二堆中取走(110)2=6个,（2）(a,b,c)=(23,10,13),a=23,b=10,c=13,10111,1010,1101,10000,解,甲有胜的策略。,00111,1010,1101,00000,-,=10000,甲第一回合应从第一堆中取走(10000)2=16个,（3）(a,b,c)=(21,29,15),a=21,b=29,c=15,10101,11101,1111,00111,解,甲有胜的策略。,10010,1111,00000,-,=101,甲第一回合应从第一堆中取走(101)2=5个,11101,（3）(a,b,c)=(21,29,15),a=21,b=29,c=15,10101,11101,1111,00111,解,10101,11010,1111,00000,-,=101,或甲第一回合应从第二堆中取走(101)2=5个,（3）(a,b,c)=(21,29,15),a=21,b=29,c=15,10101,11101,1111,00111,解,10101,11101,1000,00000,-,=111,或甲第一回合应从第三堆中取走(111)2=7个,公理集合论（ZFC公理体系）：引入集论公理以避免悖论,（ZF：Zermelo及Fraenkel，C：AxiomofChioce),法国数学家亨利庞加莱对集合论的公理化曾说过：为了防止狼，筑起了栅栏，至于栅栏里面有没有狼还是未知的。,狼-悖论,栅栏-集合论公理化,JulesHenriPoincar1854-1912,亨利庞加莱,(JulesHenriPoincar),法国数学家、天体力学家、数学物理学家、科学哲学家。庞加莱的研究涉及数论、代数学、几何学、拓扑学、天体力学、数学物理、多复变函数论、科学哲学等许多领域。他被公认是19世纪后四分之一和二十世纪初的领袖数学家，是对于数学和它的应用具有全面知识的最后一个人。庞加莱在数学方面的杰出工作对20世纪和当今的数学造成极其深远的影响，他在天体力学方面的研究是牛顿之后的一座里程碑，他因为对电子理论的研究被公认为相对论的理论先驱。,前几个冯诺伊曼序数（VonNeumannordinals）0=1=0=2=0,1=,3=0,1,2=,4=0,1,2,3=,第一个超限序数=0,1,2,第n+1有限序数n=0,1,2,3,n-1,第二个超限序数+1=,第二个超限序数+2=(+1)+1,约翰冯诺伊曼(JohnvonNeumann)匈牙利裔美籍数学家。1903年12月28日生于匈牙利布达佩斯的一个犹太人家庭。20世纪最重要的数学家之一，在现代计算机、博弈论、核武器和生化武器等诸多领域内有杰出建树的最伟大的科学全才之一，被后人称为“计算机之父”和“博弈论之父”。,JohnvonNeumann1903-1957,Hilbertshotel,Imagineahotelwithafinitenumberofrooms.Say,500rooms.Andalltheroomsaretaken.Anewguestarrivesandasksforaroom,andtheownersays,Sorry,alltheroomsaretaken.,Butnowlet,simagineahotelwithaninfinitenumberofrooms,andsupposeoncemorethatalltheroomsaretaken.Anewguestasksforaroom,andtheownersays,Butofcourse!Comeonin.Theownerthenshiftsthepersoninroom#1toroom#2,thepersoninroom#2toroom#3,andsoonintoinfinity.Hethenplacesthenewguestinroom#1.,Howdidthishappen?Alltheroomswerefull,andyettheguestcheckedintoroom#1.Whatismore,weaddedanewguest,didn,tloseanyguests,andyettherearethesamenumberofguests!Theirnumberis,specifically,infinite.,Itgetsstranger.Thenextday,aninfinityofnewguestsarrive,askingforrooms.Butofcourse!saystheowner,whoshiftsthepersoninroom#1intoroom#2,thepersoninroom#2toroom#4,thepersoninroom#3toroom#6,andsoon.Hemoveseachpersontotheroomthatisnumbereddoublehisoriginalroomnumber.Becausedoublesofintegersarealwayseven,everypersoninthehotelisinaneven-numberedroom.Theinfinitenumberofnewguestsnowcheckintotheodd-numberedrooms.Andyet,beforetheycame,alltheroomswereoccupied!AndyetthenumberofguestsinHilbert,sHotelisthesameasbefore:theirnumberisinfinite.,Andthiscanberepeatedaninfinitenumberoftimes.Eachtime,thehotelisfullwhennewguestsarrive,andyettheguestscheckin,andaftertheycheckinthenumberofguestsinthehotelremainsthesameasbefore.,Andwe,renotdoneyet.Supposetheguestinroom#1checksout.Arethereanyfewerguestsinthehotel?Accordingtosettheory,no.Therearestillaninfinitenumberofguestsinthehotel.Supposeaninfinitenumberofguestscheckoutsay,allthoseinodd-numberedrooms.Afterthis,therearestillaninfinitenumberofguestsinthehotel.Buttheownerdoesn,tlikeahalf-emptyhotelthatlooksbad!Soheshiftseachguesttotheroomthathasanumberhalfthatofhiscurrentroom,andthehotelisnowcompletelyfullwithoutaddinganyguests.,Buttheownercan,talwayskeephishotelfullwiththesemaneuvers.Let,ssaythattheinfinitenumberofguestsinanyroomnumberedhigherthan#3checksout.NowHilbert,sHotelhasanveryfinitenumberofguests:three!Andyet,thesamenumberofguestscheckedoutthistimeashadcheckedoutwheneveryoneinanodd-numberedroomcheckedout.Bothtimes,thenumberofdepartingguestswasinfinite.Andyetinthefirstcase,thehotelstillhadaninfinitenumberofguests,andinthesecondcaseit,sguestcountwasreducedtothree.,Agraphicalmatchstickrepresentationoftheordinal.Eachstickcorrespondstoanordinaloftheformm+nwheremandnarenaturalnumbers.,Representationoftheordinalnumbersupto.Eachturnofthespiralrepresentsonepowerof,1、集合的概念,把一些确定的，彼此不同的对象作为一个整体考虑，这个整体称为集合。集合里所含的个体称为集合的元素。注大写英文字母表示集合,小写英文字母（或加数字）表示集合的元素,37,2、集合的表示方法,（）列举法：将集合中的所有的元素罗列出来。例如：，（）描述法：把集合内元素的性质、特点概括描述出来。如上例：是偶数且10思考：两种表示方法的适应场合？元素与集合的关系：.，表示是集合的元素，读作属于.，表示不是的元素，读作不属于,38,集合的元素都属于集合，称为的子集，记为包含在中,不属于的元素也不会属于。,39,3、子集,定理,集合相等与包含相同的元,记为=。,集合中没有元素，称此集合为空集,记为。,3.同一集合里不能有相同的元素，元素之间没有先后次序。,2.，是有二个元素的集合,注：.是空集，不是空集，此集合有一个元素,40,若是的子集，且中至少有一个元素不属于，称是的真子集，记为,3.任何集合是自身的子集，但不是真子集。平凡子集：的平凡子集只有二个和。,41,意为,注1.,2.,即空集是任何集合的子集,P非空时,是P的真子集,4、全集和补集,例若全集U=1，2，3，x，y，A=1，x,研究对象的全体称为全集，记为U。,若U为全集，AU，在U中去掉A的元素，那么U中剩下的元素构成的集合，或者说由属于U不属于A的元素构成的集合，称为A的补集。,记为,则A的补集(或余集)为,5、幂集,无限集：元素个数是无限个的集合,43,集合内元素的个数称为此集合的基数(cardinalnumber)。记集合的基数记为|A|.如：A=1，2，3，X，则|A|=4,有限集：元素个数是有限个的集合。,在集合论中，有限集的基数即为集合内元素的个数，但无限集是通过序数来定义的。,3.若A=a1,a2,an,|=，,44,集合的所有子集作为元素组成的集合,称为的幂集，记为P(A).,注1.只有一个子集，P()=故|P()|=20=,2.设=，有二个子集和，P(A)=,故|P(A)|=21=,故|P(A)|=2n,则A的不同子集个数为：,B0=B000=B1=B001=a3B2=B010=a2B3=B011=a2,a3B4=B100=a1B5=B101=a1,a3B6=B110=a1,a2B7=B111=a1,a2,a3,45,有限集合的幂集：可用二进制序列串作为下标，来表示一个有限集合的所有子集和幂集。,例S3=a1,a2,a3则P(S3)=Bi|i,其中=i|i是二进制数且000i111,故,集合的基本运算,本节要求掌握的知识点：集合的4种基本运算：并、交，差、对称差。说明：集合之间的运算，其运算结果仍然还是集合！（表示：列举法、描述法）,46,1、并和交,3.|AB|A|+|B|.由于A与B的公共元素在中只出现一次，故当A与B无公共元素且是有限集合时等式成立。,47,把所有P与Q的元素并在一起组成新的集合，称为P与Q的并集，记为PQ。,注：1.AB=BA,AAB，BAB,2.AC且BC，则(AB)C,(5)当且仅当PQ时PQP,48,所有既在P中又在Q中的元素组成一个新的集合，称为P与Q的交集，记为PQ。即PQ=x|xPxQ,注：（1）PQQP（交换律）,（2）PQP，PQQ,（3）(CA)(CB),CAB,（4）|PQ|P|,|PQ|Q|当P=Q时等号成立。,设U是全集，Q是U的子集，则差集U-Q为Q关于U的补集。,2、差和对称差,所有在中而不在中的元素组成一个新的集合，称为减的差集，记为P-Q.P-Q=x|(xP)(xQ),注(1)P-Q只是在P中减去了P与Q有公共元素即P-Q=P-(PQ）,（2）若PQ=,则P-Q=P,（3）若QP,则|P-Q|=|P|-|Q|,例如上面的A、B，则AB=BA=a，b，c，d，y,例若全集U=a，b，c，d，x，y，A=a，b，x,B=c，d，x，y则A=c，d，y，B=a，bA-B=a，b,B-A=c，d，y,50,把P与Q的所有元素扣除P与Q的公共元素组成的集合，称为与的对称差，记为PQ.,注(1）PQ=(Q)-(PQ)（2）PQQP,文氏图(Venndiagrams）以英国数学家、逻辑学家JohnVenn来命名。作用：用一个封闭的区域来形象地表示一个集合。直观形象地描绘集合间的关系和运算,JohnVenn,(18341923）,52,集合及其运算的文氏图,由文氏图可知：PQ=(P-Q)(Q-P)=(PQ)-(PQ）,53,Q，故有P-Q，即PP-Q.,54,结论(6)P-Q=P,的证明：,PQ=,1.必要性,设P-Q=P成立,若PQ，令xPQ,则xP=P-Q=P-(PQ),则xPQ，矛盾。,故PQ=,2.充分性,设=成立,（1）若P-Q，则P，故P-QP；,（2）若P，由于=，故,由(1)和(2)知P-Q=P,结论（7）PQ=,55,的证明：,P=Q,PQ=(PQ)-(PQ)=,PQPQ,(PPQ)(QPQ),(PQ)(QP),P=Q,集合运算的性质设为全集，为的子集1.交换律：PQ=QPPQ=QPPQ=QP,2.结合律：P(QR)=(PQ)RP(QR)=(PQ),3.分配律：P(QR)=(PQ)(PR）P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)P(Q-R)=(PQ)-(PR)(PQ)-R=(P-R)(Q-R)(PQ)-R=(P-R)(Q-R),56,德摩根定律（deMorgan),对合律：,57,零一律：，,互补律：,幂等律：，,吸收律：（）（）,P-(QR)=(P-Q)(P-R)P-(QR)=(P-Q)(