资源描述:
《北大离散数学03教程文件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、北大离散数学03什么是集合(set)集合:不能精确定义。一些对象的整体就构成集合,这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,…表示集合用小写英文字母a,b,c,…表示元素aA:表示a是A的元素,读作“a属于A”aA:表示a不是A的元素,读作“a不属于A”2021/9/82《集合论与图论》第3讲集合的表示列举法描述法特征函数法2021/9/83《集合论与图论》第3讲列举法(roster)列出集合中的全体元素,元素之间用逗号分开,然后用花括号括起来,例如A={a,b,c,d,…,x,y,z}B={0,1,2,3
2、,4,5,6,7,8,9}集合中的元素不规定顺序C={2,1}={1,2}集合中的元素各不相同(多重集除外)C={2,1,1,2}={2,1}2021/9/84《集合论与图论》第3讲多重集(multipleset)多重集:允许元素多次重复出现的集合元素的重复度:元素的出现次数(0).例如:设A={a,a,b,b,c}是多重集元素a,b的重复度是2元素c的重复度是1元素d的重复度是02021/9/85《集合论与图论》第3讲描述法(definingpredicate)用谓词P(x)表示x具有性质P,用{x
3、P(x)}表示具有性质P的集合,例如P1(x)
4、: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/9/86《集合论与图论》第3讲描述法(续)两种表示法可以互相转化,例如E={2,4,6,8,…}={x
9、x>0且x是偶数}={x
10、x=2(k+1),k为非负整数}={2(k+1)
11、k为非负整数}有些书在描述法中用:代替
12、,例如{2(k+1):k为非负整数}2021/9/87《集合论与图论》第3讲特征函数法(characteristic
13、function)集合A的特征函数是A(x):1,若xAA(x)=0,若xA对多重集,A(x)=x在A中的重复度2021/9/88《集合论与图论》第3讲常用的数集合N:自然数(naturalnumbers)集合N={0,1,2,3,…}Z:整数(integers)集合Z={0,1,2,…}={…,-2,-1,0,1,2,…}Q:有理数(rationalnumbers)集合R:实数(realnumbers)集合C:复数(complexnumbers)集合2021/9/89《集合论与图论》第3讲集合之间的关系子集、相等、真子集空集、全集幂集
14、、n元集、有限集集族2021/9/810《集合论与图论》第3讲子集(subset)B包含于A,A包含B:BAx(xBxA)B不是A的子集:BAx(xBxA)x(xBxA)x(xBxA)x(xBxA)x(xBxA)2021/9/811《集合论与图论》第3讲相等(equal)相等:A=BABBAx(xAxB)A=BABBA(=定义)x(xAxB)x(xBxA)(定义)x((xAxB)(xBxA))(量词分配)x(x
15、AxB)(等值式)2021/9/812《集合论与图论》第3讲包含()的性质AA证明:AAx(xAxA)1若AB,且AB,则BA证明:AB(A=B)(ABBA)(定义)(AB)(BA)(德•摩根律)AB(已知)BA(即BA)(析取三段论)#2021/9/813《集合论与图论》第3讲包含()的性质(续)若AB,且BC,则AC证明:ABx(xAxB)x,xAxB(AB)xC(BC)x(xAxC),即AC.#2021/9/814《集合论与图论》
16、第3讲真子集(propersubset)真子集:B真包含A:ABABABAB(ABAB)(定义)(AB)(A=B)(德•摩根律)x(xAxB)(A=B)(定义)2021/9/815《集合论与图论》第3讲真包含()的性质AA证明:AAAAAA100.#若AB,则BA证明:(反证)设BA,则ABABABAB(化简)BABABABA所以ABBAA=B(=定义)但是ABABABAB(化简)矛盾!#2021/9/816《集合论与图论》第3讲
17、真包含()的性质(续)若AB,且BC,则AC证明:ABABABAB(化简),同理BC