集合的基本概念(離散數(shù)學(xué)).ppt

1、離 散 數(shù) 學(xué) (I),離散數(shù)學(xué)(I),第一章 集合論基礎(chǔ) 第二章 命題邏輯 第三章 一階邏輯 第四章 圖與網(wǎng)絡(luò) 第五章 數(shù)論基礎(chǔ),第一章 集合論基礎(chǔ),1.1 集合的基本概念 1.2 關(guān) 系 1.3 映 射,康托爾(Cantor),1.1 集合的基本概念,什么是集合(Set)？ “所要討論的一類對(duì)象的整體”； “具有同一性質(zhì)單元的集體” 通常，用大寫的英文字母A, B, C,表示集合；,1、二十六個(gè)英文字母可以看成是一個(gè)集合； 2、所有的自然數(shù)看成是一個(gè)集合； 3、吉林大學(xué)計(jì)算機(jī)學(xué)院2001級(jí)的本科學(xué)生可以看成是一個(gè)集合； 4、這間教室中的所有座位可以看成是一個(gè)集合。,例如:,集合的元素(me

2、mber或element),組成一個(gè)集合的那些對(duì)象或單元稱為這個(gè)集合的元素。 通常，用小寫的英文字母a, b, c,表示集合中的元素,設(shè)A是一個(gè)集合，a是集合A中的元素，記以aA，讀作a屬于A；若a不是集合A中的元素，則記以aA，讀作a不屬于A。 例如：A是正偶數(shù)集合，則2A，8A，36A；而 3A，9A，17A,屬于(belong to),包含有限個(gè)元素的集合，稱為有限集或有窮集(finite set)； 包含無(wú)限個(gè)元素的集合，稱為無(wú)限集或無(wú)窮集(infinite set )。 例：所有英文字母組成的集合是有限集，整數(shù)集合是無(wú)限集。,有限集 、無(wú)限集,約定，存在一個(gè)沒(méi)有任何元素的集合，稱為空

3、集(empty set) ，記為，有時(shí)也用來(lái)表示。 約定，所討論的對(duì)象的全體稱為全集(universal set)，記作E或U，我們所討論的集合都是全集的子集 。全集是相對(duì)的。,空集、全集,設(shè)A是有窮集合， A中元素的個(gè)數(shù)稱為集合A的元素?cái)?shù)，記為A。 例如，設(shè)A是所有英文字母組成的集合，則A=26。特別， | |=0,集合的元素?cái)?shù),列舉法；將集合中的元素一一列舉，或列出足夠多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1,4,9,16,25,36。 描述法 ；通過(guò)描述集合中元素的共同特征來(lái)表示集合，例如： V= x|x是元音字母 ，B= x|x=a2 , a是自然數(shù),集合

4、的表示法,文氏圖(Venn Diagram)用一個(gè)大的矩形表示全集，在矩形內(nèi)畫一些圓或其它的幾何圖形，來(lái)表示集合，有時(shí)也用一些點(diǎn)來(lái)表示集合中的特定元素。 例如：集合V=a,e,i,o,u ，用文氏圖表示如下:,E,V,a,u,確定性； 互異性； 無(wú)序性； 多樣性；,集合的特征,任何一個(gè)對(duì)象，或者是這個(gè)集合的元素，或者不是，二者必居其一； 例如：A=x|x是自然數(shù)，且x100 B=x|x是年輕人 C=x|x是禿子,確定性,集合中任何兩個(gè)元素都是不同的，即集合中不允許出現(xiàn)重復(fù)的元素。 例如： 集合A=a,b,c,c,b,d，實(shí)際上，應(yīng)該是A=a,b,c,d,互異性,集合與其中的元素的順序無(wú)關(guān) 例如

5、： 集合a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a，都是表示同一個(gè)集合。,無(wú)序性,集合中的元素可以是任意的對(duì)象，相互獨(dú)立，不要求一定要具備明顯的共同特征。 例如：A=a,a,a,b,a, 1A=1,a,*,-3,a,b,x|x是汽車,地球,多樣性,設(shè)集合S=A|A是集合，且AA 若SS，則S是集合S的元素，則根據(jù)S的定義，有S S，與假設(shè)矛盾； 若SS，則S是不以自身為元素的集合，則根據(jù)S的定義，有SS，與假設(shè)矛盾；,羅素悖論(Russells paradox),當(dāng)兩個(gè)集合A和B的元素完全一樣，即A，B實(shí)際上是同一個(gè)集合時(shí)，則稱集合A，B相等，記以A=B。 例：設(shè)A=x|x是

6、偶數(shù)，且0x10，B=2,4,6,8，則A=B。,【定義1】集合相等,設(shè)A，B是兩個(gè)集合，若A的元素都是B的元素，則稱A是B的子集，也稱B包含A，或A包含于B，記以A B，或B A 。 若AB，且AB，則稱A是B的真子集(proper subset)，也稱B真包含A，或A真包含于B，記以AB，或B A 。,【定義2】子集(subset),設(shè)A=2,4,6,8 ，B= x|x是正偶數(shù)， C=x|x是整數(shù),則有A B，B C，AC,并且A B，B C，A C 。,例：,對(duì)任意集合A, 有A A。 空集是任意集合的子集，且空集是唯一的。 對(duì)于任意兩個(gè)集合A、B，A=B當(dāng)且僅當(dāng)AB且BA。,重要結(jié)論,

7、是否存在集合A和B, 使得AB 且A B ？若存在，請(qǐng)舉一例。 設(shè)A=a ，B=a,a,b,c，則有:AB 且A B 再例如： 且 ,討論：,設(shè)A 是集合，A的所有子集為元素做成的集合稱為A的冪集，記以(A)或 2A。 (A)=S|S A 例： A=a,b,c ，則(A)=,a,b,c,a,b,a,c,b,c,a,b,c,【定義3】?jī)缂?power set),若A為有窮集，|A|=n，則|2A | = Cn0 + Cn1 + + Cnn =2n 。 x(A)當(dāng)且僅當(dāng)xA。 設(shè)A、B是兩個(gè)集合，AB當(dāng)且僅當(dāng)(A)(B)；,冪集的性質(zhì),設(shè)C是一個(gè)集合。若C的元素都是集合，則稱C為集合族。 若集合族

8、C可表示為C=SddD，則稱D為集合族C的標(biāo)志（索引）集。,【定義4】集合族、標(biāo)志集,顯然，2A是一個(gè)集合族。 設(shè)A1, A2, A3, 是集合的序列，且兩兩之間互不相同，則集合A1, A2, A3, 是一個(gè)集合族，可表示為Ai| iN，其中,N是自然數(shù)集合，是該集合的標(biāo)志集合。,設(shè)A，B是兩個(gè)集合。所有屬于A或者屬于B的元素做成的集合，稱為A和B的并集，記以AB。即AB=x|xA或xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。,【定義5】集合的并集(Union),并集的文氏圖,A,B,AB,設(shè)A，B是兩個(gè)集合。由屬于A又屬于B的元素組成的集合，稱為A

9、和B的交集，記以AB。即AB=x|xA且xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=c，d。,【定義6】集合的交集(Intersection),交集的文氏圖,A,B,AB,設(shè)A1，A2，An是n個(gè)集合，則，A1A2An ，簡(jiǎn)記為 A1A2An ，簡(jiǎn)記為,并集和交集的推廣,容斥原理 (principle of inclusion-exclusion),容斥原理是指我們計(jì)算某類物體的數(shù)目時(shí)，要排斥那些不應(yīng)包含在這個(gè)計(jì)數(shù)中的數(shù)目，但同時(shí)要包容那些被錯(cuò)誤地排斥了的數(shù)目，以此補(bǔ)償。 定理：設(shè)A、B是任意有限集合，有： |AB| = |A| + |B| - | AB|,設(shè)A1，A2，A

10、n是n個(gè)集合，則,容斥原理 (principle of inclusion-exclusion),稱為包含排斥原理，簡(jiǎn)稱容斥原理。,設(shè)A，B是兩個(gè)集合。由屬于集合A而不屬于集合B的所有元素組成的集合，稱為A與B的差集，記以A-B，或AB。即A-B=x|xA且xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是A - B=a，b。,【定義7】集合的差集(Difference),差集的文氏圖,A,B,A-B,E,設(shè)A是一個(gè)集合，全集E與A的差集稱為A的余集或補(bǔ)集，記以A。即A=E-A 例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。 特別，,【定義8】集合的補(bǔ)集(Co

11、mplement),補(bǔ)集的文氏圖,A,A的補(bǔ)集,E,設(shè)A，B是兩個(gè)集合。則A與B的環(huán)和(對(duì)稱差),記以AB, 定義為AB=(A-B)(B-A)。 A與B的對(duì)稱差還有一個(gè)等價(jià)的定義，即AB=(AB)-(AB)。 例：令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=a，b， e，f。,【定義9】集合的對(duì)稱差,對(duì)稱差的文氏圖,A,B,AB,E,設(shè)A，B是兩個(gè)集合，則A與B的環(huán)積定義為 A B = AB,【定義10】集合的環(huán)積,A,B,E,我們將(a1,a2 , ,an)稱為有序n元組，其中，a1是其第一個(gè)元素，a2是其第二個(gè)元素， ，an是其第n個(gè)元素。 兩個(gè)有序n元組(a1,a2 , ,an)

12、和(b1,b2 , ,bn)相等當(dāng)且僅當(dāng)ai=bi , i=1,2,n,【定義11】有序n元組(ordered n-tuple),對(duì)于有序n元組，當(dāng)n=2時(shí)，我們將其稱作有序二元組，也稱作有序?qū)?或序偶。 有序?qū)Φ奶攸c(diǎn)： 若ab,則(a,b)(b,a) 兩個(gè)有序?qū)?a,b)和(c,d)相等當(dāng)且僅當(dāng)a=c，b=d,【定義12】有序?qū)?ordered pairs),設(shè)A，B是兩個(gè)集合，所有有序?qū)?x, y)做成的集合(其中xA，yB)，稱為A，B的直乘積(笛卡兒積)，記以AB。 AB=(x，y)xA且yB。,【定義13】笛卡兒積(Cartesian product),設(shè)A1,A2 , ,An是n個(gè)

13、集合，由所有有序n元組(a1,a2,an)做成的集合(其中aiAi，i=1,2, ,n)，稱為A1,A2,An的直乘積(笛卡兒積)，記以A1A2 An。 A1A2 An=(a1,a2 , ,an) aiAi，i=1,2, ,n 。,【定義14】笛卡兒積的推廣,設(shè)A=1,2，B=a,b,c,則AB=(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)； BA =(a,1), (a,2),(b,1),(b,2),(c,1),(c,2)；,例如：,|AB|=A B； 對(duì)任意集合A，有A=，A=； 直乘積運(yùn)算不滿足交換律，即ABBA； 直乘積運(yùn)算不滿足結(jié)合律，即(AB)CA(BC),直乘積的性質(zhì),5. 直乘積運(yùn)算對(duì)并和交運(yùn)算滿足分配律， 即:A(BC)=(AB)(AC)，(BC)A=(BA)(CA)， A(BC)=(AB)(AC)， (BC)A=(BA)(CA)； 6. 設(shè)A，B，C，D是集合，若AC且BD，則AB CD。,等冪律： AA=A，AA=A。 交換律： AB=BA，AB=BA。 結(jié)合律： (AB)C=A(BC)，(AB)C=A(BC)。 分配律： A(BC)=(