集合的概念与运算

集合的概念与运算第1页，课件共51页，创作于2023年2月集合论(settheory)十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)GeorgFerdinand

PhilipCantor1845~1918德国数学家,集合论创始人.

第2页，课件共51页，创作于2023年2月什么是集合(set)集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,…表示集合用小写英文字母a,b,c,…表示元素aA：表示a是A的元素，读作“a属于A”

aA：表示a不是A的元素，读作“a不属于A”第3页，课件共51页，创作于2023年2月集合的表示列举法描述法特征函数法第4页，课件共51页，创作于2023年2月列举法(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页，课件共51页，创作于2023年2月多重集(multipleset)多重集:允许元素多次重复出现的集合元素的重复度:元素的出现次数(0).例如:设A={a,a,b,b,c}是多重集元素a,b的重复度是2元素c的重复度是2元素d的重复度是0第6页，课件共51页，创作于2023年2月描述法(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}第7页，课件共51页，创作于2023年2月描述法（续）两种表示法可以互相转化，例如E={2,4,6,8,…}={x|x>0且x是偶数}={x|x=2(k+1)，k为非负整数}={2(k+1)|k为非负整数}有些书在列举法中用:代替|,例如{2(k+1):k为非负整数}第8页，课件共51页，创作于2023年2月特征函数法(characteristicfunction)集合A的特征函数是

A(x):

1，若x

A

A

(x)=

0，若x

A对多重集,

A(x)=x在A中的重复度第9页，课件共51页，创作于2023年2月数的集合N：自然数(naturalnumbers)集合N={0,1,2,3,…}Z：整数(integers)集合Z={0,

1,

2,…}={…,-2,-1,0,1,2,…}Q：有理数(rationalnumbers)集合R：实数(realnumbers)集合C：复数(complexnumbers)集合第10页，课件共51页，创作于2023年2月集合之间的关系子集、相等、真子集空集、全集幂集、n元集、有限集集族第11页，课件共51页，创作于2023年2月子集(subset)

子集:若B中的元素也都是A中的元素,则称B为A的子集,或说B包含于A,或说A包含B,记作BABAx(xBxA)若B不是A的子集,则记作B

AB

Ax(xBxA)

x(xB

xA)

x

(

xB

xA)x(xB

xA)x(xBx

A)第12页，课件共51页，创作于2023年2月子集(举例)设A={a,b,c},B={a,b,c,d},C={a,b},则AB,CA,CBACBabcdefghij…………第13页，课件共51页，创作于2023年2月相等(equal)相等:互相包含的集合是相等的.A=B

ABBAA=Bx(xA

xB)A=B

ABBA(=定义)

x(xAxB)

x(xBxA)(定义)x((xA

xB)(xB

xA))(量词分配)x(xA

xB)(等值式)第14页，课件共51页，创作于2023年2月包含(

)的性质AA证明:AAx(xAxA)1若AB,且AB,则B

A

证明:A

B

(A=B)

(ABBA)(定义)

(AB)

(BA)(德•摩根律)AB(已知)

BA(即B

A)(析取三段论)#第15页，课件共51页，创作于2023年2月包含(

)的性质(续)若AB,且BC,则AC证明:ABx(xAxB)x,xAxB(AB)xC(BC)

x(xAxC),即AC.#第16页，课件共51页，创作于2023年2月真子集(propersubset)

真子集:B真包含A:ABABABAB(ABAB)(定义)

(AB)

(A=B)(德•摩根律)x(xAxB)

(A=B)(

定义)第17页，课件共51页，创作于2023年2月真包含(

)的性质AA证明:AAAAAA100.#若AB,则BA

证明:(反证)设BA,则

ABABABAB(化简)BABABABA所以ABBAA=B(=定义)但是ABABABAB(化简)矛盾!

#第18页，课件共51页，创作于2023年2月真包含(

)的性质(续)若AB,且BC,则AC证明:ABABABAB(化简),同理BCBC,所以AC.假设A=C,则BCBA,又AB,故A=B,此与AB矛盾,所以AC.

所以,AC.

#第19页，课件共51页，创作于2023年2月空集(emptyset)空集:没有任何元素的集合是空集,记作

例如,{xR|x2+1=0}定理1:对任意集合A,

A

证明:Ax(x

xA)x(0xA)1.#推论:空集是唯一的.证明:设1与2都是空集,则

1

2

2

1

1=

2.#第20页，课件共51页，创作于2023年2月全集全集:如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E全集是相对的,视情况而定,因此不唯一.例如,讨论(a,b)区间里的实数性质时,可以选E=(a,b),E=[a,b),E=(a,B],E=[a,b],E=(a,+),E=(-,+)等第21页，课件共51页，创作于2023年2月幂集(powerset)幂集:A的全体子集组成的集合,称为A的幂集,记作P(A)P(A)={x|xA}注意:xP(A)xA例子:A={a,b},P(A)={,{a},{b},{a,b}}.#第22页，课件共51页，创作于2023年2月n元集(n-set)

n元集:含有n个元素的集合称为n元集0元集:

1元集(或单元集),如{a},{b},{},{{}},…|A|:表示集合A中的元素个数,

A是n元集|A|=n有限集(fimiteset):|A|是有限数,|A|<,也叫有穷集第23页，课件共51页，创作于2023年2月幂集(续)定理:|A|=n|P(A)|=2n.证明:每个子集对应一种染色,一共有2n

种不同染色.#A{a1}

a1a2a3………an{a1,a3}……第24页，课件共51页，创作于2023年2月集族(setfamily)集族:由集合构成的集合.幂集都是集族.指标集(indexset):

设A是集族,若A={A

|S},则S称为A的指标集.S中的元素与A中的集合是一一对应的.也记作A={A

|S}={A

}S例1:{A1,A2}的指标集是{1,2}第25页，课件共51页，创作于2023年2月集族(举例)例2:An={xN|x=n},A0={0},A1={1},…{An|nN}={{0},{1},{2},…}{An|nN}的指标集是N例3:设R+={x

R|x>0},Aa=[0,a),{Aa|a

R+}的指标集是R+0a第26页，课件共51页，创作于2023年2月集合之间的运算并集、交集相对补集、对称差、绝对补广义并集、广义交集第27页，课件共51页，创作于2023年2月并集(union)并集:A

B={x|(x

A)(x

B)}x

A

B

(x

A)(x

B)初级并:第28页，课件共51页，创作于2023年2月并集(举例)例1:设An={xR|n-1xn},n=1,2,…,10,则例2:设An={xR|0x1/n},n=1,2,…,则第29页，课件共51页，创作于2023年2月交集(intersection)交集:A

B={x|(x

A)(x

B)}x

A

B

(x

A)(x

B)初级交:第30页，课件共51页，创作于2023年2月交集(举例)例1:设An={xR|n-1xn},n=1,2,…,10,则例2:设An={xR|0x1/n},n=1,2,…,则第31页，课件共51页，创作于2023年2月不相交(disjoint)不相交:A

B=

互不相交:设A1,A2,…是可数多个集合,若对于任意的ij,都有Ai

Bj=

,则说它们互不相交例:设An={xR|n-1<x<n},n=1,2,…,10,则A1,A2,…是不相交的第32页，课件共51页，创作于2023年2月相对补集(setdifference)相对补集:属于A而不属于B的全体元素,称为B对A的相对补集,记作A-BA-B={x|(x

A)(x

B)}A-BAB第33页，课件共51页，创作于2023年2月对称差(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)=(AB)-(AB)ABAB第34页，课件共51页，创作于2023年2月绝对补(complement)绝对补:~A=E-A,E是全集,AE~A={x|(xExA)}~A={xE|xA)}~AA第35页，课件共51页，创作于2023年2月相对补、对称差、补(举例)例:设A={xR|0x<2},A={xR|1x<3},则A-B={xR|0x<1}=[0,1)B-A={xR|2x<3}=[2,3)A

B={xR|(0x<1)(2x<3)}=[0,1)[2,3)[)[))[第36页，课件共51页，创作于2023年2月广义并集(bigunion)广义并:设A是集族,A中所有集合的元素的全体,称为A的广义并,记作∪A.∪A

={x|z(xzzA}当是以S为指标集的集族时∪A

=∪{A

|S}=∪

A

S例:设A={{a,b},{c,d},{d,e,f}},则

∪A={a,b,c,d,e,f}第37页，课件共51页，创作于2023年2月广义交集(bigintersection)广义交:设A是集族,A中所有集合的公共元素的全体,称为A的广义交,记作∩A.∩A

={x|z(zAxz)}当是以S为指标集的集族时∩A

=∩{A

|S}=∩

A

S例:设A={{1,2,3},{1,a,b},{1,6,7}},则

∩A={1}第38页，课件共51页，创作于2023年2月广义交、广义并(举例)设A1={a,b,{c,d}},

A2={{a,b}},

A3={a},

A4={

,{

}},A5=a(a),A6=,则∪A1=a∪b∪{c,d},∩A1=a∩b∩{c,d},∪A2={a,b},∩A2={a,b},∪A3=a,∩A3=a∪A4=

∪{

}={

},∩A4=

∩{

}=,∪A5=∪a,∩A5=∩a∪A6=,∩A6=E第39页，课件共51页，创作于2023年2月文氏图(Venndiagram)文氏图:平面上的n个圆(或椭圆),使得任何可能的相交部分,都是非空的和连通的JohnVenn,1834~1923例:第40页，课件共51页，创作于2023年2月文氏图(应用)文氏图可表示集合运算(结果用阴影表示)ABABA-BAB~AAAAAAABBBBBAB=第41页，课件共51页，创作于2023年2月文氏图(问题)Venn曾经构造出4个椭圆的文氏图,并且断言:没有5个椭圆的文氏图PeterHamburger&RaymondPippert,1996,构造出5个椭圆的文氏图Canyoutryit?第42页，课件共51页，创作于2023年2月文氏图(续)试试n=4:14<16第43页，课件共51页，创作于2023年2月文氏图(续)试试n=517+5<32第44页，课件共51页，创作于2023年2月容斥原理(principleofinclusion/exclusion)容斥原理(或包含排斥原理)第45页，课件共51页，创作于2023年2月容斥原理(证明)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|ABBCA第46页，课件共51页，创作于2023年2月容斥原理(举例)例1:在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?解:设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.#第47页，课件共51页，创作于2023年2月容斥原理(举例、续)例2:在24名科技人员中,会说英,日,德,法语的人数分别为13,5,10,和9,其中同时会说英语,德语,或同时会说英语,法语,或同时会说德语,法语两种语言的人数均为4