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

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

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

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

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

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

6、偶數(shù)，且0x10，B=2,4,6,8，則A=B。,【定義1】集合相等,設A，B是兩個集合，若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),設A=2,4,6,8 ，B= x|x是正偶數(shù)， C=x|x是整數(shù),則有A B，B C，AC,并且A B，B C，A C 。,例：,對任意集合A, 有A A。 空集是任意集合的子集，且空集是唯一的。 對于任意兩個集合A、B，A=B當且僅當AB且BA。,重要結(jié)論,

7、是否存在集合A和B, 使得AB 且A B ？若存在，請舉一例。 設A=a ，B=a,a,b,c，則有:AB 且A B 再例如： 且 ,討論：,設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】冪集(power set),若A為有窮集，|A|=n，則|2A | = Cn0 + Cn1 + + Cnn =2n 。 x(A)當且僅當xA。 設A、B是兩個集合，AB當且僅當(A)(B)；,冪集的性質(zhì),設C是一個集合。若C的元素都是集合，則稱C為集合族。 若集合族

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

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

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

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

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

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】笛卡兒積的推廣,設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； 對任意集合A，有A=，A=； 直乘積運算不滿足交換律，即ABBA； 直乘積運算不滿足結(jié)合律，即(AB)CA(BC),直乘積的性質(zhì),5. 直乘積運算對并和交運算滿足分配律， 即:A(BC)=(AB)(AC)，(BC)A=(BA)(CA)， A(BC)=(AB)(AC)， (BC)A=(BA)(CA)； 6. 設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)=(