北大离散数学03.ppt

《北大离散数学03.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲集合的概念与运算北京大学1.集合的概念2.集合之间的关系3.集合的运算4.文氏图、容斥原理2021/7/281《集合论与图论》第3讲集合论(settheory)十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)GeorgFerdinandPhilipCantor1845~1918德国数学家,集合论创始人.2021/7/282《集合论与图论》第3讲什么是集合(set)集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,…表示集合用

2、小写英文字母a,b,c,…表示元素aA：表示a是A的元素，读作“a属于A”aA：表示a不是A的元素，读作“a不属于A”2021/7/283《集合论与图论》第3讲集合的表示列举法描述法特征函数法2021/7/284《集合论与图论》第3讲列举法(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}2021/7/285《集合论与图论》第3讲多重集(mult

3、ipleset)多重集:允许元素多次重复出现的集合元素的重复度:元素的出现次数(0).例如:设A={a,a,b,b,c}是多重集元素a,b的重复度是2元素c的重复度是1元素d的重复度是02021/7/286《集合论与图论》第3讲描述法(definingpredicate)用谓词P(x)表示x具有性质P，用{x

4、P(x)}表示具有性质P的集合，例如P1(x):x是英文字母A={x

5、P1(x)}={x

6、x是英文字母}={a,b,c,d,…,x,y,z}P2(x):x是十进制数字B={x

7、P2(x)}={x

8、x是十进制数字}={0,1,2,3,4,5,6,7,8,9}2021/7/

9、287《集合论与图论》第3讲描述法（续）两种表示法可以互相转化，例如E={2,4,6,8,…}={x

10、x>0且x是偶数}={x

11、x=2(k+1)，k为非负整数}={2(k+1)

12、k为非负整数}有些书在描述法中用:代替

13、,例如{2(k+1):k为非负整数}2021/7/288《集合论与图论》第3讲特征函数法(characteristicfunction)集合A的特征函数是A(x):1，若xAA(x)=0，若xA对多重集,A(x)=x在A中的重复度2021/7/289《集合论与图论》第3讲常用的数集合N：自然数(naturalnumbers)集合N={0,1,2,3,…}

14、Z：整数(integers)集合Z={0,1,2,…}={…,-2,-1,0,1,2,…}Q：有理数(rationalnumbers)集合R：实数(realnumbers)集合C：复数(complexnumbers)集合2021/7/2810《集合论与图论》第3讲集合之间的关系子集、相等、真子集空集、全集幂集、n元集、有限集集族2021/7/2811《集合论与图论》第3讲子集(subset)B包含于A,A包含B:BAx(xBxA)B不是A的子集:BAx(xBxA)x(xBxA)x(xBxA)x(xBxA)x(x

15、BxA)2021/7/2812《集合论与图论》第3讲相等(equal)相等:A=BABBA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)(等值式)2021/7/2813《集合论与图论》第3讲包含()的性质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)(

16、析取三段论)#2021/7/2814《集合论与图论》第3讲包含()的性质(续)若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.#2021/7/2815《集合论与图论》第3讲真子集(propersubset)真子集:B真包含A:ABABABAB(ABAB)(定义)(AB)(A=B)(德•摩根律)x(xAxB)(A=B)(定义)2021/7/2816