資源描述：
《離散數(shù)學(xué)-集合論基礎(chǔ).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。
1、集合論基礎(chǔ)內(nèi)容提要現(xiàn)代數(shù)學(xué)的基礎(chǔ)滲透到計(jì)算機(jī)科學(xué)的各個(gè)方面典型的離散結(jié)構(gòu)模型基本內(nèi)容：集合的概念、性質(zhì)、運(yùn)算、關(guān)系、函數(shù)等。集合論基礎(chǔ)集合的概念注意：集合無法精確定義！說明集合：把具有共同性質(zhì)的一些組成一個(gè)整體，通常用大寫字母表示，A，B，S有限集與無限集集合論基礎(chǔ)元素與集合元素：組成集合的單個(gè)事物，通常用小寫字母表示，a,b,c若一個(gè)元素a在集合A內(nèi)，稱a屬于A，記作a∈A。若一個(gè)元素a不在集合A內(nèi)，稱a不屬于A，記作a?A。集合論基礎(chǔ)集合的表示枚舉法把集合中的所有元素列舉出來例:A={1,2,3,…N}敘述法把集合中元素的共同性質(zhì)刻劃出來例:A
2、={xP(x)},P為一謂詞.集合論基礎(chǔ)外延性原理兩個(gè)集合相等,當(dāng)且僅當(dāng)它們有相同的成員.記作A=B.也就是說,Vx(x∈A?x∈B)集合論基礎(chǔ)子集子集:集合A的每一個(gè)元素都是集合B的元素,則稱A是B的子集.記作A?B.也就是說,Vx(x∈A→x∈B).回憶:兩個(gè)集合相等的充要條件是互為子集!集合論基礎(chǔ)真子集集合A是集合B的子集,且A與B不相等,則稱A是B的真子集.也就是說,(Vx)(x∈A→x∈B)∧(?y)(y∈B∧y?A)集合論基礎(chǔ)空集不包含任何元素的集合稱為空集.記作Φ.也就是說,Φ={xP(x)∧?P(x)}注意:空集是任意集合的子集.比
3、較:Φ和{Φ}集合論基礎(chǔ)全集在一定范圍內(nèi),如果所有集合都是一個(gè)集合的子集,那么此集合可作為全集,記作E.也就是說,E={xP(x)∨?P(x)}.注意:全集的概念是相對的.集合論基礎(chǔ)冪集給定任意一個(gè)集合A,由A的所有子集作為元素所組成的集合記作T(A).顯然:(1)Φ和A是T(A)中的元素;(2)如果A=n,T(A)=2n.集合論基礎(chǔ)基于冪集的二進(jìn)制編碼把集合A中的元素按出現(xiàn)的次序作為二進(jìn)制數(shù)的位,而各元素在A的每個(gè)子集中的出現(xiàn)編為1,不出現(xiàn)則為0.這樣每個(gè)子集唯一地對應(yīng)著一個(gè)二進(jìn)制數(shù)編碼.若A=n,則T(A)={Aii∈J},J={jj是n位二進(jìn)
4、制數(shù),000…0≦j≦111…1}.為什么?集合論基礎(chǔ)集合的運(yùn)算集合的交集合的并集合的補(bǔ)集合的差集合的對稱差集合論基礎(chǔ)集合的交集合A和集合B的所有共同元素所組成的集合.記作A∩B.也就是說,A∩B={x(x∈A∧x∈B)}.集合論基礎(chǔ)集合交運(yùn)算的性質(zhì)冪等律:A∩A=A零一律:A∩Φ=Φ同一律:A∩E=A交換律:A∩B=B∩A結(jié)合律:(A∩B)∩C=A∩(B∩C)集合論基礎(chǔ)集合的并集合A和集合B中所有屬于A或?qū)儆贐的元素組成的集合,記作A∪B.也就是說,A∪B={x(x∈A∨x∈B)}.集合論基礎(chǔ)集合并運(yùn)算的性質(zhì)冪等律:A∪A=A同一律:A∪Φ=A零
5、一律:A∪E=E交換律:A∪B=B∪A結(jié)合律:(A∪B)∪C=A∪(B∪C)集合論基礎(chǔ)集合的補(bǔ)E是全集,A是一個(gè)集合,屬于E而不屬于A的元素所組成的集合.記作~A.也就是說,~A={xx?A}.集合論基礎(chǔ)集合補(bǔ)運(yùn)算的性質(zhì)對合律:~(~A)=ADeMorgan律:~(A∪B)=~A∩~B,~(A∩B)=~A∪~B否定律:~E=Φ,~Φ=EA∪~A=E,A∩~A=Φ集合論基礎(chǔ)集合的差所有屬于集合A而不屬于集合B的元素組成的集合.記作A-B.也就是說,A-B={x(x∈A∧x?B)}.比較(1)A-B和B-A;(2)差運(yùn)算和補(bǔ)運(yùn)算.集合論基礎(chǔ)集合差運(yùn)算的
6、性質(zhì)A-B=A∩~BA-B=A-(A∩B)集合論基礎(chǔ)集合的對稱差或者屬于集合A,或者屬于集合B,但不能同時(shí)屬于A和B.記作A⊕B.也就是說,A⊕B={x(x∈A∧x?B)∨(x∈B∧x?A)},即,A⊕B=(A-B)∪(B-A)集合論基礎(chǔ)集合對稱差運(yùn)算的性質(zhì)交換律:A⊕B=B⊕A同一律:A⊕Φ=A零一律:A⊕A=Φ結(jié)合律:(A⊕B)⊕C=A⊕(B⊕C)A⊕B=(A∩~B)∪(~A∩B)集合論基礎(chǔ)集合運(yùn)算的其它性質(zhì)分配律:A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)A∩(B-C)=(A∩B)-(A∩C)吸收律:A∪(A
7、∩B)=AA∩(A∪B)=A集合論基礎(chǔ)思考集合運(yùn)算有最小運(yùn)算符集合嗎?如果有,是什么?A:{~,∩}或{~,∪}集合論基礎(chǔ)集合的計(jì)數(shù)包含與排斥原理:A和B是有限集,其元素個(gè)數(shù)分別為A和B,則A∪B=A+B-A∩B.特別地,當(dāng)A和B不相交時(shí),有A∪B=A+B.注:可以推廣到n個(gè)集合的情形.集合論基礎(chǔ)序偶具有固定次序表示兩個(gè)個(gè)體之間的關(guān)系記作.顯然,≠.比較:序偶與集合的關(guān)系(序偶也稱為有序集)注意:可以推廣到n元情形.集合論基礎(chǔ)笛卡爾積給定集合A和集合B,定義這樣的序偶,其第一個(gè)元素屬于A,第二個(gè)元素屬于B.上述序偶組成
8、的集合稱為集合A和B的笛卡爾積.記作AXB.也就是說,AXB={(x∈A)∧(y∈B)}集合論基礎(chǔ)笛卡爾積的性質(zhì)
