離散數(shù)學(xué)集合論基礎(chǔ)

離散數(shù)學(xué)集合論基礎(chǔ)第一頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的概念注意：集合無法精確定義！說明集合：把具有共同性質(zhì)的一些組成一個整體，通常用大寫字母表示，A，B，S有限集與無限集第二頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)元素與集合元素：組成集合的單個事物，通常用小寫字母表示，a,b,c若一個元素a在集合A內(nèi)，稱a屬于A，記作a∈A。若一個元素a不在集合A內(nèi)，稱a不屬于A，記作aA。第三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的表示枚舉法把集合中的所有元素列舉出來例:A={1,2,3,…N}敘述法把集合中元素的共同性質(zhì)刻劃出來例:A={x|P(x)},P為一謂詞.第四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)外延性原理兩個集合相等,當(dāng)且僅當(dāng)它們有相同的成員.記作A=B.也就是說,Vx(x∈A?x∈B)第五頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)子集子集:集合A的每一個元素都是集合B的元素,則稱A是B的子集.記作AB.

也就是說,Vx(x∈A→x∈B).回憶:兩個集合相等的充要條件是互為子集!第六頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)真子集集合A是集合B的子集,且A與B不相等,則稱A是B的真子集.也就是說,(Vx)(x∈A→x∈B)∧(y)(y∈B∧y

A)第七頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)空集不包含任何元素的集合稱為空集.記作Φ.也就是說,Φ={x|P(x)∧?P(x)}注意:空集是任意集合的子集.比較:Φ和{Φ}第八頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)全集在一定范圍內(nèi),如果所有集合都是一個集合的子集,那么此集合可作為全集,記作E.

也就是說,E={x|P(x)∨?P(x)}.注意:全集的概念是相對的.第九頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)冪集給定任意一個集合A,由A的所有子集作為元素所組成的集合記作T(A).顯然:(1)Φ和A是T(A)中的元素;(2)如果|A|=n,|T(A)|=2n.第十頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)基于冪集的二進(jìn)制編碼把集合A中的元素按出現(xiàn)的次序作為二進(jìn)制數(shù)的位,而各元素在A的每個子集中的出現(xiàn)編為1,不出現(xiàn)則為0.這樣每個子集唯一地對應(yīng)著一個二進(jìn)制數(shù)編碼.若|A|=n,則T(A)={Ai|i∈J},J={j|j是n位二進(jìn)制數(shù),000…0≦j≦111…1}.

為什么?第十一頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的運(yùn)算集合的交集合的并集合的補(bǔ)集合的差集合的對稱差第十二頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的交集合A和集合B的所有共同元素所組成的集合.記作A∩B.也就是說,A∩B={x|(x∈A∧x∈B)}.第十三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合交運(yùn)算的性質(zhì)冪等律:A∩A=A零一律:A∩Φ=Φ同一律:A∩E=A交換律:A∩B=B∩A結(jié)合律:(A∩B)∩C=A∩(B∩C)第十四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的并集合A和集合B中所有屬于A或?qū)儆贐的元素組成的集合,記作A∪B.也就是說,A∪B={x|(x∈A∨x∈B)}.第十五頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合并運(yùn)算的性質(zhì)冪等律:A∪A=A同一律:A∪Φ=A零一律:A∪E=E交換律:A∪B=B∪A結(jié)合律:(A∪B)∪C=A∪(B∪C)第十六頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的補(bǔ)E是全集,A是一個集合,屬于E而不屬于A的元素所組成的集合.記作~A.也就是說,~A={x|x

A}.第十七頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合補(bǔ)運(yùn)算的性質(zhì)對合律:~(~A)=ADeMorgan律:~(A∪B)=~A∩~B,~(A∩B)=~A∪~B否定律:~E=Φ,~Φ=E

A∪~A=E,A∩~A=Φ第十八頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的差所有屬于集合A而不屬于集合B的元素組成的集合.記作A-B.

也就是說,A-B={x|(x∈A∧x

B)}.比較(1)A-B和B-A; (2)差運(yùn)算和補(bǔ)運(yùn)算.第十九頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合差運(yùn)算的性質(zhì)A-B=A∩~BA-B=A-(A∩B)第二十頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的對稱差或者屬于集合A,或者屬于集合B,但不能同時屬于A和B.記作A⊕B.也就是說,A⊕B={x|(x∈A∧xB)∨

(x∈B∧xA)},即,

A⊕B=(A-B)∪(B-A)第二十一頁，共七十二頁，2022年，8月28日集合論基礎(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)第二十二頁，共七十二頁，2022年，8月28日集合論基礎(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∩B)=AA∩(A∪B)=A

第二十三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)思考集合運(yùn)算有最小運(yùn)算符集合嗎?如果有,是什么?A:{~,∩}或{~,∪}第二十四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的計數(shù)包含與排斥原理:A和B是有限集,其元素個數(shù)分別為|A|和|B|,則

|A∪B|=|A|+|B|-|A∩B|.

特別地,當(dāng)A和B不相交時,有

|A∪B|=|A|+|B|.注:可以推廣到n個集合的情形.第二十五頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)序偶具有固定次序表示兩個個體之間的關(guān)系記作<a,b>.顯然,<a,b>≠<b,a>.比較:序偶與集合的關(guān)系

(序偶也稱為有序集)注意:可以推廣到n元情形.第二十六頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)笛卡爾積給定集合A和集合B,定義這樣的序偶,其第一個元素屬于A,第二個元素屬于B.上述序偶組成的集合稱為集合A和B的笛卡爾積.記作AXB.也就是說,AXB={<x,y>|(x∈A)∧(y∈B)}第二十七頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)笛卡爾積的性質(zhì)AXB≠BXA若A=Φ或B=Φ,則AXB=Φ.(AXB)XC≠AX(BXC)AX(B∪C)=(AXB)∪(AXC)AX(B∩C)=(AXB)∩(AXC)(A∪B)XC=(AXC)∪(BXC)(A∩B)XC=(AXC)∩(BXC)第二十八頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)二元關(guān)系任一序偶的集合確定了一個二元關(guān)系.

記作<x,y>∈R或xRy.特別地,對于集合A和B,如果x∈A,y∈B,則序偶<x,y>所組成的關(guān)系R稱為從集合A到集合B的二元關(guān)系.注意:R是A和B的笛卡爾積的子集.兩個特殊二元關(guān)系:全域關(guān)系和空關(guān)系.第二十九頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)一個集合上的二元關(guān)系如果序偶中的兩個元素屬于同一個集合A,那么稱R為在集合A上的一個二元關(guān)系.例子:恒等關(guān)系I={<x,x>|x∈A}.第三十頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)二元關(guān)系的表示集合方法:二元關(guān)系本身就是集合!關(guān)系圖:把集合的元素作為結(jié)點(diǎn),若xRy,則標(biāo)上從x到y(tǒng)的有向線段矩陣表示:MR=[rij]mxn

其中rij=1,當(dāng)<xi,yj>∈R,xi∈A,yj∈B.

否則rij=0.注意:各表示方法等價.而確定某種表示方法后需遵從相應(yīng)的運(yùn)算法則.第三十一頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)二元關(guān)系的性質(zhì)一般地,只討論一個集合上的二元關(guān)系某些特殊的性質(zhì)需要進(jìn)一步探討自反性(反自反性,非自反性)對稱性(反對稱性,非對稱性)傳遞性第三十二頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)自反性與反自反性自反:R是集合A上的一個二元關(guān)系,如果對所有的x∈A,都有xRx,則稱R是自反的.否則R是非自反的.R自反iff(Vx)(x∈A→<x,x>∈R)反自反:R是集合A上的一個二元關(guān)系,如果對所有的x∈A,都沒有xRx,則稱R是反自反的.R反自反iff(Vx)(x∈A→<x,x>R)注意:自反與反自反可以同時存在第三十三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)對稱性與反對稱性R是集合A上的一個二元關(guān)系,如果對于所有的x,y,每當(dāng)xRy,就有yRx,則稱R是對稱的.否則R是非對稱的.R在A上對稱iff(Vx)(Vy)((x∈A∧y∈A∧<x,y>∈R)→<y,x>∈R)R是集合A上的一個二元關(guān)系,如果對于所有的x,y,每當(dāng)xRy和yRx時必有x=y,則稱R是反對稱的.R在A上反對稱iff(Vx)(Vy)((x∈A∧y∈A∧<x,y>∈R∧<y,x>∈R)→x=y)注意:對稱與反對稱可以同時存在第三十四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)傳遞性R是集合A上的一個二元關(guān)系,如果對于任意的元素x,y,z,每當(dāng)xRy和yRz時,都有xRz,那么R是傳遞的.否則R是非傳遞的.R在A上傳遞iff(Vx)(Vy)(Vz)((x∈A∧y∈A∧z∈A∧<x,y>∈R∧<y,z>∈R)→<x,z>∈R)第三十五頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)復(fù)合關(guān)系設(shè)R是從集合A到集合B的一個二元關(guān)系,S是從集合B到集合C的另一個二元關(guān)系,則記RoS是R和S的復(fù)合關(guān)系.即

RoS={<x,z>|x∈A∧z∈C∧(y)y∈B∧<x,y>∈R∧<y,z>∈S}特別地,若R=S,則復(fù)合關(guān)系記為R(2).推廣到一般情形為RoRoR…RoR=R(n).第三十六頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)復(fù)合關(guān)系的性質(zhì)有序性:RoS≠SoR結(jié)合律:(RoS)oP=Ro(SoP)第三十七頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)復(fù)合關(guān)系的矩陣表示設(shè)R的關(guān)系矩陣MR=[rij]mxn,S的關(guān)系矩陣Ms=[sjk]nxp,

RoS的關(guān)系矩陣MRoS=[xik]mxp,

其中,xik=∨j=1n(rij∧

sjk).注:這里的∨和∧稱為邏輯加和邏輯乘.即0∨0=0,0∨1=1,1∨0=1,1∨1=1.0∧0=0,0∧1=0,1∧0=0,1∧1=1.?怎么與數(shù)理邏輯中的真與假及運(yùn)算相對應(yīng)?第三十八頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)逆關(guān)系R是從集合A到集合B的一個二元關(guān)系,將R中的每一序偶的元素順序互換,得到R的逆關(guān)系R-1.R-1={<y,x>|<x,y>∈R}思考:逆關(guān)系的矩陣是原關(guān)系矩陣的轉(zhuǎn)置.第三十九頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)逆關(guān)系的性質(zhì)(R-1)-1=R(R1∪R2)-1=R1-1∪R2-1(R1∩

R2)-1=R1-1∩

R2-1(R1-R2)-1=R1-1-

R2-1(AXB)-1=BXA(RoS)-1=S-1oR-1(~R)-1=~R-1注:~R=AXB-R第四十頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)關(guān)系的閉包運(yùn)算自反閉包:把原關(guān)系R擴(kuò)充成包含R的最小的自反的關(guān)系,記作r(R).對稱閉包:把原關(guān)系R擴(kuò)充成包含R的最小的對稱的關(guān)系,記作s(R).傳遞閉包:把原關(guān)系R擴(kuò)充成包含R的最小的傳遞的關(guān)系,記作t(R).第四十一頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)思考R本身是自反的,它的自反閉包是什么?R是對稱的呢?R是傳遞的呢?第四十二頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)自反閉包的計算R是集合A上的一個二元關(guān)系,那么R的自反閉包

r(R)=R∪IA

為什么?第四十三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)對稱閉包的計算R是集合A上的一個二元關(guān)系,那么R的對稱閉包

s(R)=R∪R-1

為什么?第四十四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)傳遞閉包的計算R是集合A上的一個二元關(guān)系,那么R的傳遞閉包

t(R)=∪i=1∞Ri,

且存在一個正整數(shù)k≦|A|(=n),使得

t(R)=∪i=1kRi,

通常就當(dāng)成t(R)=∪i=1nRi.為什么?第四十五頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)閉包運(yùn)算之間的性質(zhì)R是集合A上的一個二元關(guān)系,則有rs(R)=sr(R)rt(R)=tr(R)st(R)

ts(R)第四十六頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的覆蓋把一個集合A分成若干個非空子集(稱為分塊)Si,使得A中的每一個元素至少屬于其中一個分塊,且A=∪i=1mSi.令S={S1,S2,…,Sm},稱集合S是集合A的一個覆蓋.第四十七頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)集合的分劃令集合S={S1,S2,…,Sm}是集合A的一個覆蓋,且Si∩

Sj=Φ(i≠j),

則稱集合S是集合A的一個分劃(或稱為劃分).最小分劃:A本身組成的集合;最大分劃:A中每個元素構(gòu)成一個分塊所組成的集合.第四十八頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)交叉分劃與加細(xì)若{A1,A2,…,Ar}和{B1,B2,…,Bs}是同一集合A的兩種分劃,而其中所有Ai∩

Bj≠Φ組成的集合,稱為原來兩種分劃的交叉分劃.可以證明:交叉分劃也是原集合的一種分劃;交叉分劃也是原分劃的加細(xì).

第四十九頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)等價關(guān)系R是集合A上的一個二元關(guān)系,若R是自反的、對稱的和傳遞的，則R為等價關(guān)系?；貞洠呵懊嫠龅亩P(guān)系特點(diǎn)。第五十頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)等價類R是集合A上的一個二元關(guān)系，對于任意A中的元素a，定義集合

[a]R={x|x∈A,aRx}

為元素a形成的關(guān)于等價關(guān)系R的等價類。第五十一頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)等價類的性質(zhì)等價類非空（為什么？）R是集合A上的等價關(guān)系，a,b都是A中的元素，aRbiff[a]R=[b]R.(為什么？）第五十二頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)商集及性質(zhì)R上集合A上一個等價關(guān)系，其所定義的等價類所組成的集合{[a]R|a∈A}稱為A關(guān)于R的商集。記作A/R?？梢宰C明：等價關(guān)系R決定了A的一個分劃，即A/R；A上的一個分劃確定A上的一個等價關(guān)系R，且這個分劃就是A/R。第五十三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)偏序關(guān)系R是集合A上的一個二元關(guān)系，若R是自反的、反對稱的和傳遞的，則稱R是A上的一個偏序關(guān)系。通常記作≤；序偶〈A，≤〉稱為A的偏序集第五十四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)蓋住在偏序集〈A，≤〉中，如果x,y都是A中的元素，且x≤y，而x≠y，A中不存在元素z,滿足x≤z,z≤y，則稱元素y蓋住元素x.記作COVA={<x,y>|x,y∈A,y蓋住x}.即y是滿足偏序關(guān)系的緊跟在x后面的那個元素！顯然，蓋住關(guān)系是唯一的。第五十五頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)Hasse圖根據(jù)蓋住的性質(zhì)畫出Hasse圖作圖規(guī)則：（1）用小圓圈代表集合中的元素；（2）根據(jù)蓋住關(guān)系連接兩個元素，被蓋住的元素在下，蓋的元素在上；（3）把COVA中的序偶全部按（2）中的方法畫出來。第五十六頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)鏈與反鏈〈A，≤〉是偏序集，B是A的一個子集，如果B中的元素都有偏序關(guān)系，則稱B為鏈；〈A，≤〉是偏序集，B是A的一個子集，如果B中的元素都沒有偏序關(guān)系，則稱B為反鏈；注意：單個元素所組成的子集既是鏈又是反鏈。第五十七頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)鏈與反鏈的長度鏈中元素的個數(shù)稱為鏈的長度，其最大值為|A|。注意：在Hasse圖中，鏈中的元素按照蓋住關(guān)系從下往上連成一線。反鏈中元素的個數(shù)稱為反鏈的長度.最長反鏈的長度即鏈的個數(shù)。注意：反鏈中的元素分屬于不同的鏈。為什么？第五十八頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)全序關(guān)系〈A，≤〉是偏序集，如果A本身是鏈，則稱〈A，≤〉為全序集。二元關(guān)系≤為全序關(guān)系或線序關(guān)系。在Hasse圖中全序關(guān)系表示成一條直線?！碅，≤〉中只有一條鏈，其長度為|A|。第五十九頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)極大元〈A，≤〉是偏序集，B是A的子集，對于B中的一個元素b，如果B中沒有任何不同于b的元素x，滿足b≤x，則稱b是B的極大元。元素b是子集B的鏈中最大的去蓋的元素（最頂層元素）。注意：極大元不是唯一的！第六十頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)極小元〈A，≤〉是偏序集，B是A的子集，對于B中的一個元素b，如果B中沒有任何不同于b的元素x，滿足x≤b，則稱b是B的極小元。元素b是子集B的鏈中最小的被蓋住的元素（最底層元素）。注意：極小元不是唯一的！第六十一頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)最大元〈A，≤〉是偏序集，B是A的子集，對于B中的一個元素b，如果B中任何不同于b的元素x，都滿足x≤b，則稱b是B的最大元。元素b是子集B的不同鏈中共同的極大元，所以最大元是唯一的。第六十二頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)最小元〈A，≤〉是偏序集，B是A的子集，對于B中的一個元素b，如果B中任何不同于b的元素x，都滿足b≤x，則稱b是B的最小元。元素b是子集B的不同鏈中共同的極小元，所以最小元是唯一的。第六十三頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)思考當(dāng)〈A，≤〉是全序集時，它的極大元、極小元、最大元、最小元怎樣？第六十四頁，共七十二頁，2022年，8月28日集合論基礎(chǔ)上界與下界〈A，≤〉是偏序集，B是A的子集，存在A中的一個元素a，對于B中的任何元素x，都滿足x≤a，則稱a是B的上界?！碅，≤〉是偏序集，B是A的子集，存在A中的一個元素a，對于B中的任何元素x，都滿足a≤x，則稱a是B的下界。顯然