集合概念与运算

本章说明本章的主要内容–集合的基本概念—集合、相等、(真)包含、子集、空集、全集、幂集–集合运算—交、并、(相对和绝对)补、对称差、广义交、广义并–文氏图—有穷集计数问题–集合恒等式本章与后续各章的关系–是集合论后面各章的基础–是典型的布尔代数系统集合的概念与运算1.集合的概念2.集合之间的关系3.集合的运算4.文氏图、容斥原理集合论(settheory)十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)GeorgFerdinandPhilipCantor1845~1918德国数学家,集合论创始人.什么是集合(set)集合：不能精确定义。一些对象的整体就构成集合,这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,…表示集合用小写英文字母a,b,c,…表示元素aA：表示a是A的元素，读作“a属于A”aA：表示a不是A的元素，读作“a不属于A”例如：方程x2－1＝0的实数解集合：26个英文字母的集合；坐标平面上所有点的集合；……集合的表示列举法描述法特征函数法列举法(roster)列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如A={a,b,c,d,…,x,y,z}B={0,1,2,3,4,5,6,7,8,9}集合中的元素不规定顺序C={2,1,3}={1,2,3}集合中的元素各不相同,如果同一个元素在集合中多次出现应该认为是一个元素。C={2,1,1,2,1,3}={1,2,3}描述法(definingpredicate)用谓词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}描述法（续）两种表示法可以互相转化，例如E={2,4,6,8,…}={x|x0且x是偶数}={x|x=2(k+1)，k为非负整数}={2(k+1)|k为非负整数}有些书在列举法中用:代替|,例如{2(k+1):k为非负整数}特征函数法(characteristicfunction)集合A的特征函数是A(x):1，若xAA(x)=0，若xA数的集合N：自然数(naturalnumbers)集合N={0,1,2,3,…}Z：整数(integers)集合Z={0,1,2,…}={…,-2,-1,0,1,2,…}Q：有理数(rationalnumbers)集合R：实数(realnumbers)集合C：复数(complexnumbers)集合元素和集合之间的关系元素和集合之间的关系是隶属关系,即属于或不属于,属于记作∈，不属于记作。例如:A＝{a,{b,c},d,{{d}}},a∈A，{b,c}∈A,d∈A,{{d}}∈A,bA,{d}A。b和{d}是A的元素的元素。可以用一种树形图表示集合与元素的隶属关系。说明隶属关系可以看作是处在不同层次上的集合之间的关系。规定：对任何集合A都有AA。Aa{b,c}d{{d}}bc{d}d集合之间的关系子集、相等、真子集空集、全集幂集、n元集、有限集集族子集(subset)子集:若B中的元素也都是A中的元素,则称B为A的子集,或说B包含于A,或说A包含B,记作BABAx(xBxA)若B不是A的子集,则记作BABAx(xBxA)x(xBxA)x(xBxA)x(xBxA)x(xBxA)子集(举例)设A={a,b,c},B={a,b,c,d},C={a,b},则AB,CA,CBACBabcdefghij…………隶属和包含的说明隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如A＝{a，{a}}和{a}既有{a}∈A，又有{a}A。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合。相等(equal)相等:互相包含的集合是相等的.A=BABBAA=Bx(xAxB)A=BABBA(=定义)x(xAxB)x(xBxA)(定义)x((xAxB)(xBxA))(量词分配)x(xAxB)(等值式)包含()的性质AA证明:AAx(xAxA)1若AB,且AB,则BA证明:AB(A=B)(ABBA)(定义)(AB)(BA)(德•摩根律)AB(已知)(BA)(即BA)(析取三段论)#包含()的性质(续)若AB,且BC,则AC证明:ABx(xAxB)x,xAxB(AB)xC(BC)x(xAxC),即AC.#真子集(propersubset)真子集:B真包含A:ABABABAB(ABAB)(定义)(AB)(A=B)(德•摩根律)x(xAxB)(A=B)(定义)真包含()的性质AA证明:AAAAAA100.#若AB,则BA证明:(反证)设BA,则ABABABAB(化简)BABABABA所以ABBAA=B(=定义)但是ABABABAB(化简)矛盾!#真包含()的性质(续)若AB,且BC,则AC证明:ABABABAB(化简),同理BCBC,所以AC.假设A=C,则BCBA,又AB,故A=B,此与AB矛盾,所以AC.所以,AC.#空集(emptyset)空集:没有任何元素的集合是空集,记作例如,{xR|x2+1=0}定理1:对任意集合A,A证明:Ax(xxA)x(0xA)1.#推论:空集是唯一的.证明:设1与2都是空集,则12211=2.#全集说明全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如，在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。全集:在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。幂集(powerset)幂集:A的全体子集组成的集合,称为A的幂集,记作P(A)(或2A)P(A))P(A)={x|xA}注意:xP(A)xA例子:A={a,b},P(A)={,{a},{b},{a,b}}.#n元集(n-set)n元集:含有n个元素的集合称为n元集0元集:1元集(或单元集),如{a},{b},{},{{}},…|A|:表示集合A中的元素个数,A是n元集|A|=n有限集(fimiteset):|A|是有限数,|A|,也叫有穷集n元集例1A＝{1,2,3}，将A的子集分类：0元子集（空集）1元子集（单元集）{1}，{2}，{3}2元子集{1,2}，{1,3}，{2,3}3元子集{1,2,3}幂集(续)定理:|A|=n|P(A)|=2n.证明:每个子集对应一种染色,一共有2n种不同染色.#A{a1}a1a2a3………an{a1,a3}……集族(setfamily)集族:由集合构成的集合.幂集都是集族.指标集(indexset):设A是集族,若A={A|S},则S称为A的指标集.S中的元素与A中的集合是一一对应的.也记作A={A|S}={A}S例2:{A1,A2}的指标集是{1,2}集族(举例)例3:An={xN|x=n},A0={0},A1={1},…{An|nN}={{0},{1},{2},…}{An|nN}的指标集是N例4:设R+={xR|x0},Aa=[0,a),{Aa|aR+}的指标集是R+0a§6.2集合之间的运算并集、交集相对补集、对称差、绝对补广义并集、广义交集并集(union)并集:AB={x|(xA)(xB)}xAB(xA)(xB)初级并:)}1(|{21inAxniixAAAniniAAAA211211AAAii并集(举例)例1:设An={xR|n-1xn},n=1,2,…,10,则例2:设An={xR|0x1/n},n=1,2,…,则]10,0[}100|{101xRxAii]1,0[}10|{1xRxAii并集的性质定理设集合AC,BD,则(A∪B)(C∪D)证明对任意的x，若xA∪BxA∨xBxC∨xD(由于AC,BD)xC∪D由集合的包含关系的定义可得(A∪B)(C∪D)交集(intersection)交集:AB={x|(xA)(xB)}xAB(xA)(xB)初级交:)}1(|{21inAxniixAAAniniAAAA211211AAAii交集(举例)例1:设An={xR|n-1xn},n=1,2,…,10,则例2:设An={xR|0x1/n},n=1,2,…,则iiA101}0{1iiA交集的性质定理设集合AB,则(A∩C)(B∩C)证明对任意的x，若xA∩CxA∧xCxB∧xC(由于AB)xB∩C由集合的包含的定义可知(A∩C)(B∩C)不相交(disjoint)不相交:AB=互不相交:设A1,A2,…是可数多个集合,若对于任意的ij,都有AiAj=,则说它们互不相交例:设An={xR|n-1xn},n=1,2,…,10,则A1,A2,…是不相交的相对补集(setdifference)相对补集:属于A而不属于B的全体元素,称为B对A的相对补集,记作A-BA-B={x|(xA)(xB)}A-BAB对称差(symmetricdifference)对称差:属于A而不属于B,或属于B而不属于A的全体元素,称为A与B的对称差,记作ABAB={x|(xAxB)(xAxB)}AB=(A-B)(B-A)=(AB)-(AB)ABAB绝对补(complement)绝对补:~A=E-A,E是全集,AE~A={x|(xExA)}~A={xE|xA)}~AA相对补、对称差、补(举例)例:设A={xR|0x2},A={xR|1x3},则A-B={xR|0x1}=[0,1)B-A={xR|2x3}=[2,3)AB={xR|(0x1)(2x3)}=[0,1)[2,3)[)[))[广义并集(bigunion)广义并:设A是集族,A中所有集合的元素的全体,称为A的广义并,记作∪A.∪A={x|z(xzzA}当是以S为指标集的集族时∪A=∪{A|S}=∪AS例:设A={{a,b},{c,d},{d,e,f}},则∪A={a,b,c,d,e,f}广义交集(bigintersection)广义交:设A是集族,A中所有集合的公共元素的全体,称为A的广义交,记作∩A.∩A={x|z(zAxz)}当是以S为指标集的集族时∩A=∩{A|S}=∩AS例:设A={{1,2,3},{1,a,b},{1,6,7}},则∩A={1}广义交、广义并(举例)设A1={a,b,{c,d}},A2={{a