离散数学集合.ppt

《离散数学集合.ppt》由会员分享，可在线阅读，更多相关《离散数学集合.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学集合现在学习的是第1页，共47页2023/4/61集合论(set theory)十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918德国数学家,集合论创始人.现在学习的是第2页，共47页2023/4/62 什么是集合(set)集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,表示集合用小写英文字母a,b,c,表示元素aA：表示a是A的元素，读作“a属于A”aA：表示a

2、不是A的元素，读作“a不属于A”现在学习的是第3页，共47页2023/4/63集合的表示列举法描述法特征函数法现在学习的是第4页，共47页2023/4/64列举法(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现在学习的是第5页，共47页2023/4/65多重集(multiple set)多重集:允许元素多次重复出现的集合元素的重复度:元素的出现次数(0).例如:设A=a,a,b,b,c是

3、多重集 元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是0现在学习的是第6页，共47页2023/4/66描述法(defining predicate)用谓词P(x)表示x具有性质P，用x|P(x)表示具有性质 P 的集合，例如P1(x):x是英文字母A=x|P1(x)=x|x是英文字母=a,b,c,d,x,y,z P2(x):x是十进制数字B=x|P2(x)=x|x是十进制数字=0,1,2,3,4,5,6,7,8,9现在学习的是第7页，共47页2023/4/67描述法（续）两种表示法可以互相转化，例如E=2,4,6,8,=x|x0且x是偶数=x|x=2(k+1)，k为非负整数=2(

4、k+1)|k为非负整数 有些书在描述法中用:代替|,例如2(k+1):k为非负整数现在学习的是第8页，共47页2023/4/68特征函数法(characteristic function)集合A的特征函数是A(x):1，若xA A(x)=0，若xA 对多重集,A(x)=x在A中的重复度现在学习的是第9页，共47页2023/4/69常用的数集合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：复数(comple

5、x numbers)集合现在学习的是第10页，共47页2023/4/610集合之间的关系子集、相等、真子集 空集、全集幂集、n元集、有限集集族现在学习的是第11页，共47页2023/4/611子集(subset)B包含于A,A包含B:BA x(xBxA)B不是A的子集:BA x(xBxA)x(xBxA)x(xBxA)x(xBxA)x(xBxA)现在学习的是第12页，共47页2023/4/612相等(equal)相等:A=B AB BA x(xAxB)A=B ABBA (=定义)x(xAxB)x(xBxA)(定义)x(xAxB)(xBxA)(量词分配)x(xAxB)(等值式)现在学习的是第13页

6、，共47页2023/4/613包含()的性质AA 证明:AAx(xAxA)1若AB,且AB,则 BA 证明:AB (A=B)(ABBA)(定义)(AB)(BA)(德摩根律)AB(已知)BA(即BA)(析取三段论)#现在学习的是第14页，共47页2023/4/614包含()的性质(续)若AB,且BC,则AC证明:AB x(xAxB)x,xA xB (AB)xC (BC)x(xAxC),即AC.#现在学习的是第15页，共47页2023/4/615真子集(proper subset)真子集:B真包含A:AB AB AB AB (AB AB)(定义)(AB)(A=B)(德摩根律)x(xAxB)(A=B

7、)(定义)现在学习的是第16页，共47页2023/4/616真包含()的性质AA 证明:A A AA AA 10 0.#若AB,则 BA 证明:(反证)设BA,则 AB AB AB AB (化简)BA BA BA BA 所以 AB BA A=B(=定义)但是 AB AB AB AB(化简)矛盾!#现在学习的是第17页，共47页2023/4/617真包含()的性质(续)若AB,且BC,则AC证明:AB AB AB AB (化简),同理 BC BC,所以AC.假设A=C,则BCBA,又AB,故A=B,此与AB矛盾,所以AC.所以,AC.#现在学习的是第18页，共47页2023/4/618空集(em

8、pty set)空集:没有任何元素的集合是空集,记作例如,xR|x2+1=0定理1:对任意集合A,A 证明:Ax(xxA)x(0 xA)1.#推论:空集是唯一的.证明:设1与2都是空集,则 12 21 1=2.#现在学习的是第19页，共47页2023/4/619全集全集:如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E全集是相对的,视情况而定,因此不唯一.例如,讨论(a,b)区间里的实数性质时,可以选E=(a,b),E=a,b),E=(a,b,E=a,b,E=(a,+),E=(-,+)等现在学习的是第20页，共47页2023/4/620幂集(power set)幂集:A的全体

9、子集组成的集合,称为A的幂集,记作P(A)P(A)=x|xA注意:xP(A)xA例子:A=a,b,P(A)=,a,b,a,b.#现在学习的是第21页，共47页2023/4/621n元集(n-set)n元集:含有n个元素的集合称为n元集0元集:1元集(或单元集),如a,b,|A|:表示集合A中的元素个数,A是n元集|A|=n有限集(fimite set):|A|是有限数,|A|0,Aa=0,a),Aa|aR+的指标集是R+0a现在学习的是第25页，共47页2023/4/625集合之间的运算并集、交集相对补集、对称差、绝对补广义并集、广义交集现在学习的是第26页，共47页2023/4/626并集(

10、union)并集:AB=x|(xA)(xB)xAB (xA)(xB)初级并:现在学习的是第27页，共47页2023/4/627并集(举例)例1:设An=xR|n-1xn,n=1,2,10,则例2:设An=xR|0 x1/n,n=1,2,则现在学习的是第28页，共47页2023/4/628交集(intersection)交集:AB=x|(xA)(xB)xAB (xA)(xB)初级交:现在学习的是第29页，共47页2023/4/629交集(举例)例1:设An=xR|n-1xn,n=1,2,10,则例2:设An=xR|0 x1/n,n=1,2,则现在学习的是第30页，共47页2023/4/630不相

11、交(disjoint)不相交:AB=互不相交:设A1,A2,是可数多个集合,若对于任意的ij,都有AiAj=,则说它们互不相交例:设 An=xR|n-1xn,n=1,2,10,则 A1,A2,是不相交的现在学习的是第31页，共47页2023/4/631相对补集(set difference)相对补集:属于A而不属于B的全体元素,称为B对A的相对补集,记作A-BA-B=x|(xA)(xB)A-BAB现在学习的是第32页，共47页2023/4/632对称差(symmetric difference)对称差:属于A而不属于B,或属于B而不属于A的全体元素,称为A与B的对称差,记作ABAB=x|(xA

12、xB)(xAxB)AB=(A-B)(B-A)=(AB)-(AB)A BAB现在学习的是第33页，共47页2023/4/633绝对补(complement)绝对补:A=E-A,E是全集,AEA=x|(xExA)A=xE|xA)AA现在学习的是第34页，共47页2023/4/634相对补、对称差、补(举例)例:设A=xR|0 x2,B=xR|1x3,则 A-B=xR|0 x1=0,1)B-A=xR|2x3=2,3)AB=xR|(0 x1)(2x3)=0,1)2,3)现在学习的是第35页，共47页2023/4/635广义并集(big union)广义并:设A是集族,A中所有集合的元素的全体,称为A的

13、广义并,记作A.A=x|z(xzzA 当A是以S为指标集的集族时A=A|S=A S例:设 A=a,b,c,d,d,e,f,则 A=a,b,c,d,e,f现在学习的是第36页，共47页2023/4/636广义交集(big intersection)广义交:设A是集族,A中所有集合的公共元素的全体,称为A的广义交,记作 A.A=x|z(zAxz)当A是以S为指标集的集族时 A=A|S=A S例:设 A=1,2,3,1,a,b,1,6,7,则 A=1现在学习的是第37页，共47页2023/4/637广义交、广义并(举例)设 A1=a,b,c,d,A2=a,b,A3=a,A4=,A5=a(a),A6=

14、,则A1=abc,d,A1=a b c,d,A2=a,b,A2=a,b,A3=a,A3=aA4=,A4=,A5=a,A5=aA6=,A6=E现在学习的是第38页，共47页2023/4/638文氏图(Venn diagram)文氏图:平面上的n个圆(或椭圆),使得任何可能的相交部分,都是非空的和连通的John Venn,18341923例:现在学习的是第39页，共47页2023/4/639文氏图(应用)文氏图可表示集合运算(结果用阴影表示)A BA BA-BA BAAAAAAABBBBBA B=现在学习的是第40页，共47页2023/4/640容斥原理(principle of inclusio

15、n/exclusion)容斥原理(或包含排斥原理)现在学习的是第41页，共47页2023/4/641容斥原理(证明)n=2时的情况:|AB|=|A|+|B|-|AB|归纳证明:以n=3为例:|AB C|=|(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|ABBCA现在学习的是第42页，共47页2023/4/642容斥原理(举例)例1:在1到10000之间既不是某个整数的平方,也不是某个整数的立方的

16、数有多少?解:设 E=xN|1x10000,|E|=10000 A=xE|x=k2kZ,|A|=100 B=xE|x=k3kZ,|B|=21 则|(AB)|=|E|-|AB|=|E|-(|A|+|B|-|AB|)=10000-100-21+4=9883 注意 AB=xE|x=k6kZ,|AB|=4.#现在学习的是第43页，共47页2023/4/643容斥原理(举例、续)例2:在24名科技人员中,会说英,日,德,法语的人数分别为13,5,10,和9,其中同时会说英语,德语,或同时会说英语,法语,或同时会说德语,法语两种语言的人数均为4.会说日语的人既不会说法语也不会说德语.试求只会说一种语言的人

17、数各为多少?又同时会说英,德,法语的人数有多少?解:设E=x|x是24名科技人员之一,|E|=24 A=xE|x会说英语,B=xE|x会说日语,C=xE|x会说德语 D=xE|x会说法语,现在学习的是第44页，共47页2023/4/644容斥原理(举例、续)解(续):设所求人数分别为x1,x2,x3,x4,x(如图),A=xE|x会说英语,|A|=13 B=xE|x会说日语,|B|=5 C=xE|x会说德语,|C|=10 D=xE|x会说法语,|D|=9 首先,x2=|B|-|AB|=5-2=3,其次,对A,C,D用容斥原理,注意|E|=24:24-3=21=13+10+9-4-4-4+x=20+x,得x=1,最后,x1=|A|-|AB|-3-3-1=13-2-7=4,同理 x3=10-3-3-1=3,x4=9-3-3-1=2.#DCBAXX1X2X3X44-X4-X4-X2现在学习的是第45页，共47页2023/4/645总结集合概念:,E,集合运算:,-,P()文氏图容斥原理现在学习的是第46页，共47页2023/4/646习题(#1)p25,习题一,3,7,10,16 现在学习的是第47页，共47页2023/4/647