离散第讲集合的概念交并补差幂集

计算机专业基础课程授课人：梁妍

离散数学的特点与学习要求特点离散性抽象性逻辑性有难度要求预习复习独立完成作业PowerPointTemplate_Sub1.1集合的概念与表示1.2集合运算1.3集合的归纳定义PowerPointTemplate_Sub

集合论是一门研究数学基础的学科，产生于16世纪末德国数学家康托（GeorgCantor,1845~1918）通过集合的直观定义开创了朴素集合论，被公认为集合理论的创始人1902年英国数学家罗素（Russell,1872~1970）证明朴素集合论导致悖论，随后为弥补这一缺陷出现了各种公理化集合论体系集合不仅可以表示数及其运算，更可以用于非数值信息及离散结构的表示和处理。集合论的原理和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中集合的概念、表示与基本运算Page1to7《离散数学》第1讲-6-ξ第一讲集合的概念、表示与基本运算内容提要基础知识集合、元素的概念怎样表示一个集合（列举、描述…）空集、全集、有限集、无限集外延性公理集合相等、子集、若干定理集合的基本运算并、交、差、补幂集运算-7-ξ第一讲集合的概念、表示与基本运算何为集合？何为元素？集合(sets)：指确定的、互相区别的、作整体识别的一些事物（对象）的全体。简称集。集合中的对象称为集合的元素(members)，或称为元、成员。当某一个对象a是集合A的成员时，就说“a属于A”，记成aA，当a不是集合A的成员时，就说“a不属于A”，记成aA。对于任何对象a和任何集合A，a要么属于A，要么不属于A，二者必居其一。-8-ξ第一讲集合的概念、表示与基本运算集合举例师范大学全体学生师范大学所有班级全体正整数1，2，3，4，…偶质数的全体09计算机1班和他们本学期选修的所有课程所有长得像张三的人中国所有著名导演方程x2-2x+1=0的根方程x2+x+1=0的根-9-ξ第一讲集合的概念、表示与基本运算集合与元素集合中的元素可以是任何具体或抽象的个体，也可以是集合A={1，2，{1，2}}集合与其成员是两个截然不同的概念1≠{1}{{a}}≠{a}通常用大写字母A,B,C表示集合，用小写字母a,b,c表示集合的元素（并非绝对）-10-ξ第一讲集合的概念、表示与基本运算集合的表示方法列举法（枚举法）{a,b,c},{秦始皇，汉武帝}{1,2,3,4,…},{2,4,6,8,…}{1,2,4,7,11,…}描述法A={x|P(x)}（A中的元素均满足性质P，而A以外的元素一个也不满足性质P）

xAP(x){x|x是整数且x>0}、{x|x2-2x+1=0}{x|x出生于大连}、{x|x是0到1区间的实数}-11-ξ第一讲集合的概念、表示与基本运算集合的表示方法归纳法（以后介绍）文氏图（常用于表示集合之间的关系）ABU-12-ξ第一讲集合的概念、表示与基本运算常用集合及其表示{0,1}={x|x=0或x=1}自然数集合（或非负整数的集合）N={0,1,2,3,…}整数集合I={…,-2,-1,0,1,2,…}正整数集合I+

={1,2,3,…}={x|xI且x>0}-13-ξ第一讲集合的概念、表示与基本运算常用集合及其表示偶数集合E={…,-4,-2,0,2,4,…}={x|x是偶数}={x|xI且2|x}前n个自然数的集合Nn={0，1，2，…,n-1}={x|xN且x<n}-14-ξ第一讲集合的概念、表示与基本运算常用集合及其表示P：全体素数的集合Q：全体有理数的集合Q＋：全体正有理数的集合R：全体实数的集合R＋：全体正实数的集合C：全体复数的集合-15-ξ第一讲集合的概念、表示与基本运算空集、有限集和无限集定义1.1：没有任何元素的集合称为空集，记为，={}。由全体对象组成的集合称为全集，记为U。定义1.2：只含有限多个元素的集合称为有限集；不是有限集的集合称为无限集。空集是有限集有限集合A中元素的个数称为A的基数(cardinality)，记为|A|空集的基数是0，即||=0-16-ξ第一辉讲集合黄的概静念、辣表示砖与基留本运本算空集趣、有桶限集政和无担限集兴举例{x刃|串x=撞0或x=喂1}自然桂数集拿合N正整陆数集崇合A针=偿{料1，2，{1，2}老}{}师范尤大学观全体货学生方程x2+爷x色+浙1恐=陕0的根-17-ξ第一养讲集合榨的概筛念、孩表示呜与基炉本运页算外延译性公栗理（ex识te康ns原io症na馋li围ty鞭a兄xi得om）外延镇性公教理：两个错集合蛇相等练当且联仅当闸这两县个集粒合具矛有完全脂相同的成序员。即对炒任意宅的集保合A和B：A志=栏B当且茧仅当牢对任秋意元庭素x，x属于A则一杆定有x属于B；反搞之，x属于B也一微定有x属于A。也就辫是说由，集尊合A中的员所有讨元素昌均是膝集合B中的乞元素斤，反按之，B中的购所有览元素彻均是A中的幻玉元素例1.报4旱{裕0,由1浴}惑=喇{1构,伤0}腾=谋{疗0,伪1泥,六0}还=划{钱x析|筹x(咏x2-2舌x+赛1)唐=0办}外延啄性公避理事范实上跃刻画允了集元合元眨素的无序闻性、相异赵性及集令合表示丹形式桃的不泼唯一晨性-18-ξ第一幅讲集合河的概邮念、印表示诱与基消本运杰算子集宾合(s扛ub说se逝ts茄)定义1.裁3：设A，B为集并合，钳若A中每浪一个设元素袍都同停时是B的元哨素，棒则称A是B的子集。即组对于财任意走元素x，当x属于A时一某定有x属于B。表眉示为AB，读症成A包含烫于B，或B包含A。任意蚀集合A均是我自己码的子夹集，号即：AA若要枣说明A不是B的子升集，味只须痒在A中找观到某粗一个绳元素x，使忌得xB即可定义1.捐4：设A、B为集贡合，忌当AB且AB时，缺称A为B的真子绒集，记淡成AB。读挑做A真包稻含于B，或B真包缎含A-19-ξ第一孟讲集合推的概导念、孕表示猪与基昂本运妄算包含悲关系vs还.隶属罚关系包含——集合汽与集瓣合之疯间的密关系{1滔,2板}玩{1叙,钞2纤,早3,坦4典}{1隐,2毅}{1吊,尝2清,筑3,冤4丘}{a丽}海老{a赵}隶属——元素熟与集姜合之脏间的巷关系1岩欧{1战,喝2蹲,速3,胞4神}5版盗{1饰,喂2健,现3,浆4旧}{a咳}逆梁{{弟a}用}-20-ξ第一齿讲集合县的概藏念、秆表示戴与基庄本运鱼算关于雾子集荡的若锈干定验理定理1.有1：对任版何集测合A，B，A=丹B当且蒜仅当AB且BA。对任欠何集困合A，AA定理1.送3：对于肝任何润集合A，B，C，若AB，BC，则AC。证明咱：设x为A中任榴一元罗素，因为AB，所滚以xB；又因食为BC，所景以xC这就羽是说哨，A中所慰有元奶素均索属于C，所戴以有AC。-21-ξ第一识讲集合跃的概夹念、大表示服与基抖本运客算关于全子集摩的若骨干定精理定理1.变2，1.宪4：对任喉意集镰合A，AU，A定理1.亲5：空集期是唯觉一的证明沟：假设1,唉2都是白空集款，根该据定召理3，应仅该有1质2且2眯1，从泄而由奥定理1知1=向2。-22-ξ第一裹讲集合套的概地念、恋表示菊与基戏本运趴算关于弊子集批的若璃干定乞理定理1.亮6：设A为一退个有预限集亡，且|A县|=梢n，则A的子小集个膨数为2n证明缝：集合A的子核集最局多有n个元虾素，足最少烤有0个元宇素。0个元炉素的吃子集羡共有C(槽n,脾0)个；1个元秋素的穿子集钞共有C(凶n,据1)个；……n个元离素的稼子集摧共有C(同n,喊n)个.因此漂，集军合A共有公子集C(逝n,嚷0)每+呼C(挎n,凶1)促+…C(刘n,悲n)=垮2n个。-23-ξ第一话讲集合风的概汁念、唯表示跌与基宽本运殊算集合召的运访算集合岁运算——以集脏合作裙为运烤算对添象，霸运算疑结果透仍为工集合典的运精算算术甩运算悄：3+吸5=风8衣4述×6末=2找4集合代运算威：{1玻,软2}{2助,世3}古={问2}浩{1垃,议2}{2益,裁3}轰={外1,眼2套,阔3}有哪槽些集合运召算交、颗并、士差、虚补求幂命运算广义正并、络交求笛五卡尔员积运弊算-24-ξ第一轰讲集合缘瑞的概龄念、绪表示疗与基临本运贴算集合嚷的并岸运算un尖io颗n（∪桑）定义1.蹄5：(1续)设A、B为任墨意集尖合，糟则由A、B的所轿有元亚素合嘴在一帐起所伤组成弹的集桐合称游为A与B的并迟集，股记成A∪亲B。即法：A∪速B=畜{x茄|xA或xB}xA∪鱼BxA或xB例1.冰6U=魔{0篇,兔1,什2警,矩…,伍9燃}A=意{2灶,右4}辈,鬼B=绕{4敌,脸5,惑6繁,越7}躲,墙C=据{0筐,康8,足9轧},述D素={蛛1,饿2务,悲3}A∪这B，A∪钳C，C∪衔D，B∪挎D-25-ξ第一咏讲集合肠的概制念、撤表示兴与基计本运己算集合栗的交绍运算in举te遗rs剩ec增ti慨on（∩运）定义1.枪5：(2谱)设A、B为任限意集灶合，朱则由A、B的公侧共元端素所盒组成匙的集雷合称谅为A与B的交邀集，适记成A∩亚B。即丹：A∩难B=描{x孝|xA并且xB}xA∩怖BxA并且xB例1.艺6U=俊{0脸,扔1,副2幻玉,辜…,耗9煮}A=辈{2安,泪4}店,棋B=打{4恶,旬5,诱6晃,组7}宜,注C=奖{0素,守8,软9乱},运D烤={习1,共2洒,读3}A∩B，A∩C，C∩D，B∩D-26-ξ第一角讲集合高的概类念、童表示森与基仅本运侧算集合叠的差驼运算di猪ff艘er秘en勿ce（–）定义1.欺5：(3商)设A、B为任理意集袜合，普则由航在A中而顾不在B中的以元素现所组芒成的挎集合鬼称为A对B的差伸，记厦成A–怒B。即寺：A稼–袭B寺=浪{x但|xA且xB}xA弃–丘BxA并且xB例1.期6U=士{0屈,秤1,绞2赠,鲜…,卵9良}A=鸡{2按,熔4}好,舒B=厕{4消,丛5,气6威,括7}蔬,颜C=怕{0满,被8,橡9边},肝D口={躬1,僵2允,乔3}A－B，A－C，C－D，B－D-27-ξ第一恐讲集合便的概请念、医表示缠与基蓝本运训算集合葡的补杠运算co序mp丑le稍me末nt（–）定义1.末5：(4孟)设U为全土集，A为任宽意集剑合，井则所芬有在劳全集U中但垫不属估于A的元暮素所凭组成岔的集似合称挪为A的补捷集，炕记成A¯。即骗：A¯婆=担{粒x陷|xU且xA}xA¯xA例1.岁6U=灵{0受,煎1,先2快,陡…,瓣9金}A=奶{2然,巧4}闷,赶B=闲{4澡,常5,车6咸,咸7}驼,茅C=候{0作,随8,套9塞},巩D造={添1,边2猫,昆3}A¯，B¯，C¯，D¯-28-ξ第一障讲集合做的概轮念、洗表示亡与基仿本运窑算文氏仇图表构示的分集合率并、孤交、兵差、捆补运两算UAAUAA¯A∩BUABA∪BUABA－BUAB(A融∪B励)¯对∩CUABC-29-ξ第一眠讲集合耻的概销念、谈表示浇与基症本运牺算关于管并、宋交、谦差、扭补运鸦算的罚一些伪直观绪结论A∪磁A渴=丘A，A∪=勉A，A∪睡U吉=存UA∩睬A悼=和A，A∩=，A∩抚U梨=材AA功–宾A艘=，A荣–=乎A，A滑–错U啊=，–烘A酒=A¯兴=茄U云–此A，¯=斧U，U¯换=，A¯姥¯士=AA∩妻A¯逮=，A∪删A¯鄙=量UAA∪朝B，BA∪拘B，A∩店BA，A∩幼BBA鱼–未BA若AB，则A∪弯B紧=海B，A∩凭B毒=差A，A消–软B赌=若A∩揉B习=，则A甜–南B熔=港A-30-ξ第一丸讲集合锤的概尾念、适表示球与基击本运楚算关于慕交换爷律和其结合甩律交换泉律2+朝3叠=代3+寻2，a×站b=b×僵aA∪掩B尺=管B∪遭A，A∩渣B忍=常B∩案A一般傲而言近，A沟–卷B≠B踩–裙A结合窄律2+细(3光+5歉)蛮=搏(2回+3乒)+锐5，a×兆(b驶×c)参=剂(a×酬b)城×cA∪都(B才∪C档)澡=鸽(A灿∪B颜)霜∪CA∩活(B碗∩C委)贱=续(A扔∩B助)膏∩C一般升而言游，A论–定(B桌–皇C座)≠(A愁–腔B涛)哲–佣C-31-ξ第一躬讲集合笑的概帆念、出表示匀与基含本运诉算关于羞分配洋律和仔吸收象率分配密律a×攻(b+积c)乡丰=a×帮b+a×喂cA∪武(B办∩C失)医=变(A盯∪B师)池∩疲(A南∪C夫)A∩痛(B扁∪C没)蓄=斗(A赠∩B絮)揭∪杯(A排∩C宿)A∩朗(B－C)躬=(A纳∩B助)－(A速∩C土)一般邮而言杨，A∪芳(B－C)≠(A奏∪B饺)－(A削∪C汽)吸收榆律A∩小(A筒∪B工)黑=再AA∪拖(A肃∩B畅)蒸=屿A-32-ξ第一落讲集合配的概遥念、代表示买与基蜘本运劲算关于评并、厕交、陡差、橡补运圈算的扭几个亩定理定理1.肉6：A哄–旨(B匹∪C渡)军=子(A焰–舍B口)∩晋(A俩–伯C蛙)A存–展(B呼∩C膏)夺=俭(A聚–宫B踏)∪窑(A橡–判C谁)定理1.沿8：(A慌∪B画)¯弄=禁A析¯∩犬B¯(A忽∩B乓)¯退=阶A芬¯∪牵B¯A叫–钩B肆=淹A∩荣B¯证明A化–连(B垦∩C蝴)浩=葬(A们–殃B决)∪竞(A忍–谁C检)对任走意x，xA益–珠(B板∩C仰)xA且xB∩冬CxA且(xB或者xC)(xA且xB)或者(xA且xC)xA–舰B或者xA–嚼Cx(A采–洗B保)∪米(A舍–借C厚)-33-ξ第一四讲集合型的概订念、清表示泥与基篮本运甩算关于虑并、爆交、逼差、茶补运述算的蜓几个涂定理定理1.拣10：AB，A青–躲B掠=，A∪谅B刊=B，A∩夸B贵=恩A四命腐题等折价定理1.菊11：对任迫意集和合A、B，若虽它们酷满足1)A∪妄B文=响U2)抱A崇∩B括=那么B简=粒A¯证明轰：B饿=副B∪催=筑B∪(婚A∩项A¯仁)=值(B∪A煎)野∩想(B该∪A驻¯)=册U端∩葬(B言∪A困¯)=方(A∪A过¯)晶∩布(汤B∪底A¯寺)=择(A盯∩B采)司∪膀A伶¯=∪委A¯=华A¯第二白种证罚法：梦相互阻包含-34-ξ第一狼讲集合禾的概挨念、壳表示其与基筝本运报算集合牢幂运田算定义1.锡6：我们辛把集捆合A的所利有子耀集组熊成的扒集合黄称为A的幂牌集（po兰we逆r掌se旁t），刮记成ρ(凑A)，即ρ(浇A)朗=仪{x画|xA}例：A=牵{2惧,忠4}工,误B=聪{{粪4,巾5臭},折6傲,堡7