1、2021-11-291集合論集合論(set theory) 十九世紀(jì)數(shù)學(xué)(shxu)最偉大成就之一 集合論體系 樸素(naive)集合論 公理(axiomatic)集合論 創(chuàng)始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918德國(guó)數(shù)學(xué)家, 集合論創(chuàng)始人. 第1頁(yè)/共47頁(yè)第一頁(yè)，共48頁(yè)。2021-11-292 什么什么(shn me)是集合是集合(set) 集合：不能精確定義。一些對(duì)象的整體(zhngt)就構(gòu)成集合，這些對(duì)象稱(chēng)為元素(element)或成員(member) 用大寫(xiě)英文字母A,B,C,表示集合 用小寫(xiě)英文字母a,b,c,表示元素

2、 aA：表示a是A的元素，讀作“a屬于A” aA：表示a不是A的元素，讀作“a不屬于A”第2頁(yè)/共47頁(yè)第二頁(yè)，共48頁(yè)。2021-11-293集合集合(jh)的表示的表示 列舉(lij)法 描述法 特征函數(shù)法第3頁(yè)/共47頁(yè)第三頁(yè)，共48頁(yè)。2021-11-294列舉列舉(lij)法法(roster) 列出集合中的全體元素，元素之間用逗號(hào)(duho)分開(kāi)，然后用花括號(hào)括起來(lái)，例如 A=a,b,c,d,x,y,z B=0,1,2,3,4,5,6,7,8,9 集合中的元素不規(guī)定順序 C=2,1=1,2 集合中的元素各不相同(多重集除外) C=2,1,1,2=2,1第4頁(yè)/共47頁(yè)第四頁(yè)，共48頁(yè)

3、。2021-11-295多重集多重集(multiple set) 多重集: 允許元素多次重復(fù)出現(xiàn)(chxin)的集合 元素的重復(fù)度: 元素的出現(xiàn)(chxin)次數(shù)(0). 例如: 設(shè)A=a,a,b,b,c是多重集 元素a,b的重復(fù)度是2 元素c的重復(fù)度是1 元素d的重復(fù)度是0第5頁(yè)/共47頁(yè)第五頁(yè)，共48頁(yè)。2021-11-296描述描述(mio sh)法法(defining predicate) 用謂詞P(x)表示x具有性質(zhì)P ，用x|P(x)表示具有性質(zhì) P 的集合，例如(lr) P1 (x): x是英文字母 A=x|P1 (x)=x| x是英文字母 =a,b,c,d,x,y,z P2 (

4、x): x是十進(jìn)制數(shù)字 B=x|P2(x)= x|x是十進(jìn)制數(shù)字 =0,1,2,3,4,5,6,7,8,9第6頁(yè)/共47頁(yè)第六頁(yè)，共48頁(yè)。2021-11-297描述描述(mio sh)法（續(xù)）法（續(xù)） 兩種表示法可以互相轉(zhuǎn)化，例如 E=2,4,6,8, =x|x0且x是偶數(shù) =x|x=2(k+1)，k為非負(fù)整數(shù) =2(k+1) | k為非負(fù)整數(shù) 有些(yuxi)書(shū)在描述法中用:代替|, 例如 2(k+1): k為非負(fù)整數(shù)第7頁(yè)/共47頁(yè)第七頁(yè)，共48頁(yè)。2021-11-298特征函數(shù)法特征函數(shù)法(characteristic function) 集合( jh)A的特征函數(shù)是A (x): 1，

5、若xA A (x) = 0，若xA 對(duì)多重集, A (x)=x在A中的重復(fù)度第8頁(yè)/共47頁(yè)第八頁(yè)，共48頁(yè)。2021-11-299常用常用(chn yn)的數(shù)集合的數(shù)集合 N：自然數(shù)(natural numbers)集合 N=0,1,2,3, Z：整數(shù)(integers)集合 Z=0,1,2,=,-2,-1,0,1,2, Q：有理數(shù)(rational numbers)集合 R：實(shí)數(shù)(shsh)(real numbers)集合 C：復(fù)數(shù)(complex numbers)集合第9頁(yè)/共47頁(yè)第九頁(yè)，共48頁(yè)。2021-11-2910集合集合(jh)之間的關(guān)系之間的關(guān)系 子集、相等、真子集 空集(

6、kn j)、全集 冪集、n元集、有限集 集族第10頁(yè)/共47頁(yè)第十頁(yè)，共48頁(yè)。2021-11-2911子集子集(z j)(subset) B包含于A, A包含B: BA x(xBxA) B不是(b shi)A的子集: BA x(xBxA)x(xBxA)x(xBxA) x(xBxA)x(xBxA)第11頁(yè)/共47頁(yè)第十一頁(yè)，共48頁(yè)。2021-11-2912相等相等(xingdng)(equal) 相等(xingdng): A=B AB BA x(xAxB) A=B ABBA (=定義)x(xAxB)x(xBxA) (定義)x(xAxB)(xBxA)(量詞分配)x(xAxB) (等值式)第12

7、頁(yè)/共47頁(yè)第十二頁(yè)，共48頁(yè)。2021-11-2913包含包含(bohn)()的性質(zhì)的性質(zhì) AA 證明(zhngmng): AAx(xAxA) 1 若AB,且AB,則 BA 證明(zhngmng): AB (A=B) (ABBA) (定義) (AB) (BA) (德摩根律) AB (已知) BA (即BA) (析取三段論) #第13頁(yè)/共47頁(yè)第十三頁(yè)，共48頁(yè)。2021-11-2914包含包含(bohn)()的性質(zhì)的性質(zhì)(續(xù)續(xù)) 若AB,且BC, 則AC 證明(zhngmng): AB x(xAxB) x, xA xB (AB) xC (BC) x(xAxC), 即AC. #第14頁(yè)/共4

8、7頁(yè)第十四頁(yè)，共48頁(yè)。2021-11-2915真子集真子集(z j)(proper subset) 真子集: B真包含(bohn)A: AB AB AB AB (AB AB) (定義) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定義)第15頁(yè)/共47頁(yè)第十五頁(yè)，共48頁(yè)。2021-11-2916真包含真包含(bohn)()的性質(zhì)的性質(zhì) AA 證明: A A AA AA 10 0. # 若AB,則 BA 證明: (反證(fnzhng) 設(shè)BA, 則 AB AB AB AB (化簡(jiǎn)) BA BA BA BA 所以 AB BA A=B (=定義) 但是 AB AB AB A

9、B (化簡(jiǎn)) 矛盾! #第16頁(yè)/共47頁(yè)第十六頁(yè)，共48頁(yè)。2021-11-2917真包含真包含(bohn)()的性質(zhì)的性質(zhì)(續(xù)續(xù)) 若AB,且BC, 則AC 證明(zhngmng): AB AB AB AB (化簡(jiǎn)), 同理 BC BC, 所以AC. 假設(shè)A=C, 則BCBA, 又AB, 故A=B, 此與AB矛盾, 所以AC. 所以, AC. #第17頁(yè)/共47頁(yè)第十七頁(yè)，共48頁(yè)。2021-11-2918空集空集(kn j)(empty set) 空集:沒(méi)有任何(rnh)元素的集合是空集,記作 例如, xR|x2 +1=0 定理1: 對(duì)任意集合A, A 證明: Ax(xxA) x(0 x

10、A)1. # 推論: 空集是唯一的. 證明: 設(shè)1與2都是空集, 則 12 21 1=2 . #第18頁(yè)/共47頁(yè)第十八頁(yè)，共48頁(yè)。2021-11-2919全集全集(qunj) 全集(qunj): 如果限定所討論的集合都是某個(gè)集合的子集,則稱(chēng)這個(gè)集合是全集(qunj),記作E 全集(qunj)是相對(duì)的, 視情況而定, 因此不唯一.例如, 討論(a,b)區(qū)間里的實(shí)數(shù)性質(zhì)時(shí), 可以選E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+),E=(-,+)等第19頁(yè)/共47頁(yè)第十九頁(yè)，共48頁(yè)。2021-11-2920冪集冪集(power set) 冪集: A的全體(qunt

11、)子集組成的集合,稱(chēng)為A的冪集,記作P(A) P(A)=x|xA 注意: xP(A) xA 例子: A=a,b, P(A)=,a,b,a,b. #第20頁(yè)/共47頁(yè)第二十頁(yè)，共48頁(yè)。2021-11-2921n元集元集(n-set) n元集: 含有n個(gè)元素的集合稱(chēng)為(chn wi)n元集 0元集: 1元集(或單元集),如a, b, , , |A|: 表示集合A中的元素個(gè)數(shù), A是n元集 |A|=n 有限集 (fimite set): |A|是有限數(shù), |A|0, Aa=0,a), Aa|aR+ 的指標(biāo)(zhbio)集是R+0a第24頁(yè)/共47頁(yè)第二十四頁(yè)，共48頁(yè)。2021-11-2925集合

12、集合(jh)之間的運(yùn)算之間的運(yùn)算 并集、交集( jioj) 相對(duì)補(bǔ)集、對(duì)稱(chēng)差、絕對(duì)補(bǔ) 廣義并集、廣義交集( jioj)第25頁(yè)/共47頁(yè)第二十五頁(yè)，共48頁(yè)。2021-11-2926并集并集(union) 并集: AB = x | (xA) (xB) xAB (xA) (xB) 初級(jí)(chj)并: )1 (|21inAxniixAAAniniAAAA211211AAAii第26頁(yè)/共47頁(yè)第二十六頁(yè)，共48頁(yè)。2021-11-2927并集并集(舉例舉例(j l) 例1: 設(shè)An=xR|n-1xn,n=1,2,10,則 例2: 設(shè)An=xR|0 x1/n,n=1,2,則10, 0100|101x

13、RxAii 1 , 010|1xRxAii第27頁(yè)/共47頁(yè)第二十七頁(yè)，共48頁(yè)。2021-11-2928交集交集(jioj)(intersection) 交集(jioj): AB = x | (xA) (xB) xAB (xA) (xB) 初級(jí)交: )1 (|21inAxniixAAAniniAAAA211211AAAii第28頁(yè)/共47頁(yè)第二十八頁(yè)，共48頁(yè)。2021-11-2929交集交集(jioj)(舉例舉例) 例1: 設(shè)An=xR|n-1xn,n=1,2,10,則 例2: 設(shè)An=xR|0 x1/n,n=1,2,則iiA10101iiA第29頁(yè)/共47頁(yè)第二十九頁(yè)，共48頁(yè)。2021

14、-11-2930不相交不相交(xingjio)(disjoint) 不相交: AB= 互不相交: 設(shè)A1,A2,是可數(shù)多個(gè)(du )集合, 若對(duì)于任意的ij, 都有AiAj=, 則說(shuō)它們互不相交 例: 設(shè) An=xR|n-1xn, n=1,2,10, 則 A1,A2,是不相交的第30頁(yè)/共47頁(yè)第三十頁(yè)，共48頁(yè)。2021-11-2931相對(duì)補(bǔ)集相對(duì)補(bǔ)集(set difference) 相對(duì)補(bǔ)集: 屬于(shy)A而不屬于(shy)B的全體元素,稱(chēng)為B對(duì)A的相對(duì)補(bǔ)集, 記作A-B A-B = x | (xA) (xB) A-BAB第31頁(yè)/共47頁(yè)第三十一頁(yè)，共48頁(yè)。2021-11-2932

15、對(duì)稱(chēng)對(duì)稱(chēng)(duchn)差差(symmetric difference) 對(duì)稱(chēng)(duchn)差: 屬于A而不屬于B, 或?qū)儆贐而不屬于A的全體元素, 稱(chēng)為A與B的對(duì)稱(chēng)(duchn)差, 記作AB AB=x|(xAxB)(xAxB) AB=(A-B)(B-A)=(AB)-(AB)ABAB第32頁(yè)/共47頁(yè)第三十二頁(yè)，共48頁(yè)。2021-11-2933絕對(duì)絕對(duì)(judu)補(bǔ)補(bǔ)(complement) 絕對(duì)( judu)補(bǔ): A=E-A, E是全集, AE A=x|(xExA) A=xE|xA)AA第33頁(yè)/共47頁(yè)第三十三頁(yè)，共48頁(yè)。2021-11-2934相對(duì)補(bǔ)、對(duì)稱(chēng)相對(duì)補(bǔ)、對(duì)稱(chēng)(duchn)差

16、、補(bǔ)差、補(bǔ)(舉例舉例) 例: 設(shè)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)第34頁(yè)/共47頁(yè)第三十四頁(yè)，共48頁(yè)。2021-11-2935廣義廣義(gungy)并集并集(big union) 廣義(gungy)并: 設(shè)A是集族, A中所有集合的元素的全體, 稱(chēng)為A的廣義(gungy)并, 記作A. A = x | z(xzzA 當(dāng)A是以S為指標(biāo)集的集族時(shí) A = A|S= A S 例: 設(shè) A=a,b,c,d,d,e,f, 則 A= a,b,c,d,e,f第35頁(yè)/共47頁(yè)

17、第三十五頁(yè)，共48頁(yè)。2021-11-2936廣義廣義(gungy)交集交集(big intersection) 廣義交: 設(shè)A是集族, A中所有集合的公共元素的全體, 稱(chēng)為(chn wi)A的廣義交, 記作A. A = x | z(zAxz) 當(dāng)A是以S為指標(biāo)集的集族時(shí) A = A|S= A S 例: 設(shè) A=1,2,3,1,a,b,1,6,7, 則 A= 1第36頁(yè)/共47頁(yè)第三十六頁(yè)，共48頁(yè)。2021-11-2937廣義廣義(gungy)交、廣義交、廣義(gungy)并并(舉例舉例) 設(shè) A1=a,b,c,d, A2=a,b, A3=a, A4=, A5=a(a), A6=, 則A1=

18、 abc,d, A1= a b c,d,A2=a,b, A2=a,b, A3=a, A3=aA4=, A4= =,A5= a, A5= aA6=, A6=E第37頁(yè)/共47頁(yè)第三十七頁(yè)，共48頁(yè)。2021-11-2938文氏圖文氏圖(Venn diagram) 文氏圖: 平面上的n個(gè)圓(或橢圓),使得任何可能(knng)的相交部分, 都是非空的和連通的 John Venn, 18341923 例: 第38頁(yè)/共47頁(yè)第三十八頁(yè)，共48頁(yè)。2021-11-2939文氏圖文氏圖(應(yīng)用應(yīng)用(yngyng) 文氏圖可表示(biosh)集合運(yùn)算(結(jié)果用陰影表示(biosh)ABABA-BABAAAAAA

19、ABBBBBAB=第39頁(yè)/共47頁(yè)第三十九頁(yè)，共48頁(yè)。2021-11-2940容斥原理容斥原理(yunl)(principle of inclusion/exclusion) 容斥原理(或包含(bohn)排斥原理)jijiniiiniAAAA|11kjinnkjiAAAAAA|) 1(|211第40頁(yè)/共47頁(yè)第四十頁(yè)，共48頁(yè)。2021-11-2941容斥原理容斥原理(yunl)(證明證明) n=2時(shí)的情況(qngkung): |AB|=|A|+|B|-|AB| 歸納證明: 以n=3為例: |AB C| = |(AB)C|= |AB|+|C|-|(AB)C| = |A|+|B|-|AB|

20、+|C|-|(AC)(BC)| = |A|+|B|-|AB|+|C| -(|AC|+|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|ABBCA第41頁(yè)/共47頁(yè)第四十一頁(yè)，共48頁(yè)。2021-11-2942容斥原理容斥原理(yunl)(舉例舉例) 例1: 在1到10000之間既不是某個(gè)整數(shù)的平方,也不是某個(gè)整數(shù)的立方(lfng)的數(shù)有多少? 解: 設(shè) E=xN|1x10000, |E|=10000 A=xE|x=k2kZ, |A|=100 B=xE|x=k3kZ, |B|=21 則 |(AB)|=|E|-|AB| =|E|-(|A|+|B

21、|-|AB|) =10000-100-21+4=9883 注意 AB= xE|x=k6kZ, |AB|=4. #第42頁(yè)/共47頁(yè)第四十二頁(yè)，共48頁(yè)。2021-11-2943容斥原理容斥原理(yunl)(舉例、續(xù)舉例、續(xù)) 例2: 在24名科技人員中,會(huì)說(shuō)英,日,德,法語(yǔ)的人數(shù)分別為13, 5, 10, 和9, 其中同時(shí)會(huì)說(shuō)英語(yǔ)(yn y),德語(yǔ), 或同時(shí)會(huì)說(shuō)英語(yǔ)(yn y),法語(yǔ), 或同時(shí)會(huì)說(shuō)德語(yǔ),法語(yǔ)兩種語(yǔ)言的人數(shù)均為4.會(huì)說(shuō)日語(yǔ)的人既不會(huì)說(shuō)法語(yǔ)也不會(huì)說(shuō)德語(yǔ). 試求只會(huì)說(shuō)一種語(yǔ)言的人數(shù)各為多少?又同時(shí)會(huì)說(shuō)英,德,法語(yǔ)的人數(shù)有多少? 解: 設(shè)E=x|x是24名科技人員之一, |E|=24 A=xE|x會(huì)說(shuō)英語(yǔ)(yn y), B=xE|x會(huì)說(shuō)日語(yǔ), C=xE|x會(huì)說(shuō)德語(yǔ) D=xE|x會(huì)說(shuō)法語(yǔ),第43頁(yè)/共47頁(yè)第四十三頁(yè)，共48頁(yè)。2021-11-2944容斥原理容斥原理(yunl)(舉例、續(xù)舉例、續(xù)) 解(續(xù)): 設(shè)所求人數(shù)(rn sh)分別為x1,x2,x3,x4,x(