集合和二元關(guān)系復習

1、溫 故 而 知 新 !,67-1,溫故而知新!,2020年7月31日星期五,溫 故 而 知 新 !,67-2,集合的表示法,集合是由它包含的元素完全確定的，為了表示一個集合，通常有：列舉法、隱式法（描述法）、歸納法、文氏圖等表示方法。,溫 故 而 知 新 !,67-3,2.2集合的運算,定義 設(shè)A、B是兩個集合，則 ABx|xAxB 仍是一個集合，稱為集合A與B的并集，稱“”為并運算（Union Operation）。 用文氏圖表示如下：,溫 故 而 知 新 !,67-4,交集,定義 設(shè)A，B是兩個集合，則 ABx|xAxB 仍是一個集合，稱為集合A與B的交集，稱“”為交運算（Intersec

2、tion Operation）。用文氏圖可表示如下：,溫 故 而 知 新 !,67-5,差集,定義 設(shè)A，B是兩個集合，則 A-Bx|xAxB 仍是一個集合，稱為集合A與B的差集，稱“-”為差運算（Subtraction Operation)，-又叫相對補集。用文氏圖可表示如下：,溫 故 而 知 新 !,67-6,定義 設(shè)U是全集，A是U的子集，則 U-Ax|xU并且xA 仍是一個集合，稱它為集合A的補集(也可記為，AC等），“”稱為補運算（Complement Operation）。用文氏圖可表示如下：,補集,溫 故 而 知 新 !,67-7,關(guān)于運算“差”和“補”的幾個性質(zhì),1. ； 2.

3、 （）； 3.（）（）； 4 （）； 5 。,溫 故 而 知 新 !,67-8,對稱差(環(huán)和),定義：設(shè)A，B是兩個集合，則 AB=x|(xA)(xB)(xB)(xA) =(A-B)(B-A) 仍是一個集合，稱它為與的對稱差集，稱“”為對稱差運算。用文氏圖可表示如下：,A,B,U,圖中的陰影部分為AB。,溫 故 而 知 新 !,67-9,1. 等冪律： ； 2交換律： ； ； 3結(jié)合律： （）（）； （）（）； 4恒等律： ； ； 5零 律： ； ； 6分配律： （）（）（）； （）（）（）。 7吸收律： A（AB）A； A（AB）=A； 8否定律：,9DeMorgan律：,10矛盾律： A

4、=；,11排中律： A =U；,溫 故 而 知 新 !,67-10,冪集,定義由集合A的所有子集組成的集合稱為A的冪集，記為(A)或2A。 (A)x|一切xA,這種以集合為元素構(gòu)成的集合，常稱為集合的集合或集族（Family of Set）。 對集族的研究在數(shù)學方面、知識庫和表處理語言以及人工智能等方面都有十分重要的意義。,結(jié)論:顯然，若集合有個元素，則集合共有2n個子集，即：|(A)| 2n。,溫 故 而 知 新 !,67-11,容斥原理,定義所謂容斥，是指我們計算某類物的數(shù)目時，要排斥那些不應(yīng)包含在這個計數(shù)中的數(shù)目，但同時要包容那些被錯誤地排斥了的數(shù)目，以此補償，這種原理稱為容斥原理，又稱

5、為包含排斥原理。,定理設(shè)A和B是任意有限集合，有 |AB|A|B|AB|。,例 某軟件公司的程序員都熟悉C+或VB，其中熟悉C+的共47人，熟悉VB的共35人，C+和VB都熟悉的共23人，問該公司共有多少程序員？,溫 故 而 知 新 !,67-12,推論設(shè)U為全集，A和B是任意有限集合，則 |U|(|A|B|)|AB| 證明： = =|U-(AB)| |U|AB|U|(|A|B|)|AB|。,設(shè)A1,A2,An是任意有限集合，有:,溫 故 而 知 新 !,67-13,2.5 序偶與笛卡爾乘積,定義由兩個元素x,y按照一定的次序組成的二元組稱為有序偶對，簡稱序偶,記作,其中，稱x為的第一元素，y

6、為的第二元素。,例1平面上點的坐標，x,yR；中國地處亞洲，,等都是序偶。這條單地址指令也是序偶。,性質(zhì) （1）（當xy時) （2）當且僅當xu,yv。,溫 故 而 知 新 !,67-14,n重有序組,定義由n個元素a1,a2,a3,an按照一定的次序組成的n元組稱為n重有序組，記作 即：,an。,例2a年b月c日d時e分f秒可用下述六重有序組來描述：。,性質(zhì) 當且僅當aibi（i1,2,3,n）。,溫 故 而 知 新 !,67-15,定義設(shè)A,B是兩個集合，稱集合 AB|(xA)(yB) 為集合A與B的笛卡兒積。特別，記AA為A2。,笛卡兒積,AB|(xA)(yB),CD|(xC)(yD)

7、, ,溫 故 而 知 新 !,67-16,定義設(shè)A1,A2,An為n個非空集合，稱,3.1.1關(guān)系的定義,A1A2An的任意子集R為以A1A2An 為基的n元關(guān)系。,特別：當R時，則稱R為空關(guān)系； 當RA1A2An時，則稱R為全關(guān)系。,由于A1A2An的任何子集都是一個n元關(guān)系，按照子集的定義，A1A2An共有 2|A1A2An| 個不同的子集。因此，以A1A2An為基的不 同關(guān)系共有 2|A1A2An| 個。,溫 故 而 知 新 !,67-17,定義 設(shè)A，B為兩個集合，AB的任何一個子 集R所定義的二元關(guān)系稱為從A到B的二元關(guān)系，簡稱關(guān)系。 如R是從A到A的二元關(guān)系，則稱R為A上的二元關(guān)系

8、。,3.1.2二元關(guān)系,由于任何AB的子集都是一個二元關(guān)系，按照子集的定義，知AB共有2|A|B|個不同的子集。因此，從A到B不同的關(guān)系共有2|A|B|個。,設(shè)有一序偶： R， 常把這一事實記為xRy，讀作“x對y有關(guān)系R”。如 R， 則記為xRy，讀作“x對y沒有關(guān)系R”。,溫 故 而 知 新 !,67-18,3.1.3關(guān)系的表示法,1.集合表示法,由于關(guān)系也是一種特殊的集合，所以集合的幾種基本的表示法也可以用到關(guān)系的表示中。 可用枚舉法和敘述法來表示關(guān)系。,例 設(shè)A2,B3,關(guān)系R 如定義集合N上的“小于等于”關(guān)系： R|(x,yN)(xy)。,溫 故 而 知 新 !,67-19,2.關(guān)系

9、圖法,設(shè)a1,a2,a3,.,an和b1,b2,b3,.,bm分別為圖中的節(jié)點，用“。”表示； 如R,則從ai到bj可用一有向邊aibj相連。為對應(yīng)圖中的有向邊。,設(shè)Aa1,a2,a3,.,an,Bb1,b2,b3,.,bm，R是 從A到B的一個二元關(guān)系，則對應(yīng)于關(guān)系R之關(guān)系圖有如下規(guī)定：,如R,則從ai到ai用一帶箭頭的小圓環(huán)表示ai,溫 故 而 知 新 !,67-20,設(shè)Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm， R是從A到B的一個二元關(guān)系， 稱矩陣MR(rij)nm為關(guān)系 R的關(guān)系矩陣或鄰接矩陣，其中：,3.關(guān)系矩陣,顯然，關(guān)系矩陣是布爾矩陣。 注意 在寫關(guān)系矩陣時，首

10、先應(yīng)對集合A和B中的元素進行排序，不同的排序會得到不同的關(guān)系矩陣。當集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。,溫 故 而 知 新 !,67-21,3.1.4 關(guān)系的性質(zhì)（91-93）,自反性與反自反性,定義設(shè)R是集合A上的二元關(guān)系， 對任意的xA,都滿足R，則稱R是自反的，或稱R具有自反性，即 R在A上是自反的(x)(xA)(R)=1,2) 對任意的xA,都滿足R，則稱R是反自反的，或稱R具有反自反性，即 R在A上是反自反的(x)(xA)( R)=1,溫 故 而 知 新 !,67-22,設(shè)A=a,b,c,d，,例,R=,。,因為A中每個元素x，都有R，所以R

11、是自反的。,R的關(guān)系圖,R的關(guān)系矩陣,溫 故 而 知 新 !,67-23,S=,。,例 (續(xù)1),S的關(guān)系圖,S的關(guān)系矩陣,因為A中每個元素x，都有 S，所以S是反自反的。,溫 故 而 知 新 !,67-24,T=,。,例 (續(xù)2),因為A中有元素b，使 T，所以T不是自反的；因為A中有元素a，使T，所以T不是反自反的。,T的關(guān)系圖,T的關(guān)系矩陣,溫 故 而 知 新 !,67-25,任何不是自反的關(guān)系未必一定是反自反的關(guān)系，反之亦然。即存在既不是自反的也不是反自反的關(guān)系。 表現(xiàn)在關(guān)系圖上：關(guān)系R是自反的，當且僅當其關(guān)系圖中每個結(jié)點都有環(huán)；關(guān)系R是反自反的，當且僅當其關(guān)系圖中每個結(jié)點都無環(huán)。 表

12、現(xiàn)在關(guān)系矩陣上：關(guān)系R是自反的，當且僅當其關(guān)系矩陣的主對角線上全為1；關(guān)系R是反自反的當且僅當其關(guān)系矩陣的主對角線上全為0。,結(jié)論,溫 故 而 知 新 !,67-26,對稱性與反對稱性,設(shè)R是集合A上的二元關(guān)系， 對任意的x,yA，如果R，那么R，則稱關(guān)系R是對稱的，或稱R具有對稱性，即 R在A上是對稱的 (x)(y)(xA) (yA)(R)(R)=1,2) 對任意的x,yA，如果R且R，那么x=y，則稱關(guān)系R是反對稱的，或稱R具有反對稱性，即 R在A上是反對稱的 (x)(y)(xA) (yA)(R)(R)(x=y)=1,溫 故 而 知 新 !,67-27,設(shè)A=a,b,c,d，,例,R1=,

13、R2=,R1的關(guān)系圖,R1的關(guān)系矩陣,是對稱的,是反對稱的,R2的關(guān)系圖,R2的關(guān)系矩陣,溫 故 而 知 新 !,67-28,R3=,例 (續(xù)1),R4=,既不是對稱的，也不是反對稱的,R3的關(guān)系圖,R3的關(guān)系矩陣,既是對稱的，也是反對稱的,R3的關(guān)系圖,R3的關(guān)系矩陣,溫 故 而 知 新 !,67-29,任何不是對稱的關(guān)系未必一定是反對稱的關(guān)系，反之亦然。即存在既不是對稱的也不是反對稱的關(guān)系，也存在既是對稱的也是反對稱的關(guān)系。 表現(xiàn)在關(guān)系圖上：關(guān)系R是對稱的當且僅當其關(guān)系圖中，任何一對結(jié)點之間，要么有方向相反的兩條邊，要么無任何邊；關(guān)系R是反對稱的當且僅當其關(guān)系圖中，任何一對結(jié)點之間，至多有

14、一條邊。 表現(xiàn)在關(guān)系矩陣上：關(guān)系R是對稱的當且僅當其關(guān)系矩陣為對稱矩陣，即rij=rji，i,j=1,2, ,n；關(guān)系R是反對稱的當且僅當其關(guān)系矩陣為反對稱矩陣，即rijrji=0，i,j=1,2,n，ij。,結(jié)論,溫 故 而 知 新 !,67-30,傳遞性,定義 設(shè)R是集合A上的二元關(guān)系，對任 意的x,y,zA，如果R且R，那么 R，則稱關(guān)系R是傳遞的，或稱R具有傳遞 性，即,R在A上是傳遞的 (x)(y)(z)(xA)(yA)(zA) (R)(R)(R)=1,溫 故 而 知 新 !,67-31,設(shè)A=a,b,c,d，,例,R1=,R2=,是傳遞的,R1的關(guān)系圖,R1的關(guān)系矩陣,是傳遞的,R

15、2的關(guān)系圖,R2的關(guān)系矩陣,溫 故 而 知 新 !,67-32,R3=,例 (續(xù)1),R4=,不是傳遞的,R3的關(guān)系圖,R3的關(guān)系矩陣,不是傳遞的,R3的關(guān)系圖,R3的關(guān)系矩陣,溫 故 而 知 新 !,67-33,表現(xiàn)在關(guān)系圖上：關(guān)系R是傳遞的當且僅當其關(guān)系圖中，任何三個結(jié)點x,y,z（可以相同）之間，若從x到y(tǒng)有一條邊存在，從y到z有一條邊存在，則從x到z一定有一條邊存在。 表現(xiàn)在關(guān)系矩陣上：關(guān)系R是傳遞的當且僅當其關(guān)系矩陣中，對任意i,j,k1,2,3,n，若rij=1且rjk=1，必有rik=1。,結(jié)論,溫 故 而 知 新 !,67-34,設(shè)A是任意的集合， A上的全關(guān)系A(chǔ)A是自反的、對

16、稱的、傳遞的關(guān)系； A上的空關(guān)系是反自反的、反對稱的、對稱的、傳遞的關(guān)系； A上的恒等關(guān)系IA是自反的、對稱的、反對稱的、傳遞的關(guān)系。,例,例 朋友關(guān)系是自反的、對稱的、而非傳遞的關(guān)系； 父子關(guān)系是反自反的、反對稱的、而非傳遞的關(guān)系.,溫 故 而 知 新 !,67-35,在整數(shù)集I上定義的 “小于等于”關(guān)系是自反的、反對稱的、傳遞的關(guān)系； “小于”關(guān)系是反自反的、反對稱的、傳遞的關(guān)系； “等于”關(guān)系是自反的、反對稱的、對稱的、傳遞的關(guān)系。,例,例8.21設(shè)A1,2,3,4，R,，是A上的關(guān)系。,冪集上的 “包含”關(guān)系是自反的、反對稱的、傳遞的關(guān)系； “真包含”關(guān)系是反自反的、反對稱的、傳遞的關(guān)

17、系； “相等”關(guān)系是自反的、反對稱的、對稱的、傳遞的關(guān)系。,則R既不是自反的，又非反自反的；即不是對稱的，也非 反對稱的；也不是傳遞的。即不具備關(guān)系的任何性質(zhì)。,溫 故 而 知 新 !,67-36,關(guān)系性質(zhì)的邏輯表示,設(shè)R是集合A上的二元關(guān)系， R是自反的,是永真的,R不是自反的,是永真的,R是反自反的,是永真的,R不是反自反的,是永真的,R是對稱的,是永真的,R不是對稱的,是永真的,溫 故 而 知 新 !,67-37,關(guān)系性質(zhì)的邏輯表示(續(xù)),R是反對稱的,R是傳遞的,是永真的,R不是傳遞的,是永真的,是永真的,R不是反對稱的,是永真的,溫 故 而 知 新 !,67-38,設(shè)R，S都是集合A

18、到B的兩個關(guān)系，則： RS|(xRy)(xSy) RS|(xRy)(xSy) R-S|(xRy)(xSy) |(xy),3.2關(guān)系的運算,關(guān)系的交、并、補、差運算（補充）,根據(jù)定義，由于AB是相對于R的全集，所以AB-R,且RAB,R。,溫 故 而 知 新 !,67-39,定義設(shè)R是一個從集合A到集合B的二元 關(guān)系，則從B到A的關(guān)系R-1|R稱 為R的逆關(guān)系,運算“-1”稱為逆運算。,關(guān)系的逆運算 P101,注意：關(guān)系是一種集合，逆關(guān)系也是一種集合，因此，如果R是一個關(guān)系，則R-1和都是關(guān)系，但R-1和是完全不同的兩種關(guān)系，千萬不要混淆。,溫 故 而 知 新 !,67-40,關(guān)系的合成運算 P

19、96,設(shè)R是一個從集合A到集合B的二元關(guān) 系，S是從集合B到集合C的二元關(guān)系(也可 簡單地描述為R：AB，S：BC)，則R與 S的合成關(guān)系（合成關(guān)系）RS是從A到C的關(guān)系， 并且： RS|(xA)(zC) (y)(yB)(xRy)(ySz) 運算“”稱為合成運算。,注意，在合成關(guān)系中，R的后域B一定是S的前域B，否則R和S是不可合成的。合成的結(jié)果RS的前域就是R的前域A，后域就是S的后域C。如果對任意的xA和zC，不存在yB，使得xRy和ySz同時成立，則RS為空，否則為非空。并且， R=R=。,溫 故 而 知 新 !,67-41, RSR。S ABCAC 1。1。11。12。2。22。23。

20、3。33。34。4。44。4,2).用關(guān)系圖求RS。,例 R,， S,，,3).用關(guān)系矩陣求RS。P99,MRS MR.MS,溫 故 而 知 新 !,67-42,設(shè)I是整數(shù)集合，R，S是I到I的兩個關(guān)系： R|xI； S|xI。 則：RS SR RR SS (RR)R (RS)R,例,|xI |xI |xI |xI |xI |xI,溫 故 而 知 新 !,67-43,設(shè)R是從集合A到集合B的關(guān)系，S1,S2是從集合B到集 合C的關(guān)系，T是從集合C到集合D的關(guān)系，則： R(S1S2)(RS1)(RS2) R(S1S2)(RS1)(RS2) (S1S2)T(S1T)(S2T) (S1S2)T(S1

21、T)(S2T),定理3.2.1 P97,證明4)對任意(S1S2)T，則由合成運算知，,至少存在cC,使得：(S1S2)，T。即： S1,且S2。 因此，由S1,且T，則有：(S1T), 由S2,且T，則有：(S2T)。 所以，(S1T)(S2T)。即， (S1S2)T(S1T)(S2T)。,溫 故 而 知 新 !,67-44,設(shè)R,S,T分別是從集合A到集合B，集合B到 集合C，集合C到集合D的二元關(guān)系，則 1)(RS)TR(ST) 2)(RS)-1S-1R-1 (補充),定理3.2.7,證明1)設(shè)(RS)T，,cC,使得：RS，T。,則由合成運算知,至少存在,R(ST),又對于RS，則至少

22、存一個bB，使得 R，S。 因此,由S,T,有ST，又由 R和ST，知：所以 (RS)TR(ST)。 同理可證：R(ST)(RS)T。 由集合性質(zhì)知：(RS)TR(ST)。,溫 故 而 知 新 !,67-45,2).任取(RS)-1，則RS 由“”的定義知：則至少存一個bB,使得： R，S， 即：R-1,S-1。 由S-1和R-1,有：S-1R-1， 所以，(RS)-1S-1R-1。 反之，任取S-1R-1，由“”的定義知：則至少存一個bB,使得：S-1和R-1， 所以：R，S。 由“”知：RS。即有：(RS)-1。 所以，S-1R-1(RS)-1。 由集合的定義知：(RS)-1S-1R-1。

23、,定理 (續(xù)) 2)(RS)-1S-1R-1,溫 故 而 知 新 !,67-46,定義設(shè)R是集合A上的二元關(guān)系，則可 定義R的n次冪Rn,該Rn也是A上的二元關(guān)系，定義 如下： 1.R0IA|aA； 2.R1； 3.Rn+1RnRRRn。,關(guān)系的冪 P98,顯然，RmRnRm+n,(Rm)nRmn。,溫 故 而 知 新 !,67-47,定義設(shè)R是定義在A上的二元關(guān)系，若存在R的一個擴充ExtR滿足： ExtR是自反的(或?qū)ΨQ的、或傳遞的)。 對任何的擴充Ext*R，若Ext*R是自反的(對稱的、或傳遞的)，則：ExtRExt*R。 此時稱ExtR為R的自反閉包關(guān)系(或?qū)ΨQ閉包關(guān) 系、或傳遞閉包

24、關(guān)系)，分別記為r(R)(s(R)或 t(R)。,關(guān)系的閉包,溫 故 而 知 新 !,67-48,求一個關(guān)系的自反閉包，即將圖中的所有無環(huán)的節(jié)點加上環(huán)；關(guān)系矩陣中對角線上的值rij全變?yōu)椤?”。 求一個關(guān)系的對稱閉包，則在圖中，任何一對節(jié)點之間，若僅存在一條邊，則加一條方向相反的另一條邊；關(guān)系矩陣中則為：若有rij1(ij)，則令rji1(若rji1),即Ms(R)MRMR-1。 求一個關(guān)系的傳遞閉包，則在圖中，對任意節(jié)點a,b,c,若a到b有一條邊，同時b到c也有一條邊，則從a到c必增加一條邊(當a到c無邊時)；在關(guān)系矩陣中，若rij1，rjk1,則令rik1(若rik1)。,利用關(guān)系圖和關(guān)

25、系矩陣求閉包,溫 故 而 知 新 !,67-49,設(shè)R是集合A上的二元關(guān)系，則： r(R)RIA。 s(R)RR-1。 t(R)，若|A|n，則t(R)。,定理,溫 故 而 知 新 !,67-50,設(shè)PP1,P2,P3,P4是四個程序，R,S是定義在P上的 調(diào)用關(guān)系如下： R, S, 求r(R),s(R),t(R)，r(S),s(S),t(S)。,例,解：r(R)RIA , , , ,。 ,。,溫 故 而 知 新 !,67-51,例 (續(xù)1),s(R)RR-1, , , ,。 t(R)RR2R3R4, ,。 r(S)SIA, , , ,。,溫 故 而 知 新 !,67-52,s(S)SS-1,

26、 , ,例 (續(xù)2),t(S)SS2S3S4, , , ,) , ,。,溫 故 而 知 新 !,67-53,定義 1）集合A上的關(guān)系的自反對稱閉包定義為rs(R)r(s(R) 2）集合A上的關(guān)系的自反傳遞閉包定義為rt(R)r(t(R) 3）集合A上的關(guān)系的對稱傳遞閉包定義為st(R)s(t(R) 同上，我們還可定義sr(R),tr(R),ts(R),多重閉包,定理設(shè)R是集合A上的關(guān)系，則： 1)rs(R)sr(R)2)rt(R)tr(R) 3)st(R)ts(R),溫 故 而 知 新 !,67-54,設(shè)A1,2,R,則：,例,傳遞閉包和自反傳遞閉包，常用于形式語言與程序設(shè)計中，在計算機文獻中

27、，常把關(guān)系R的傳遞閉包t(R)記作R+，而自反傳遞閉包rt(R)記作R*。顯然有(R+)+=R+。,st(R)s(t(R)s() , ts(R)t(s(R)t(,) , 即：st(R)ts(R),溫 故 而 知 新 !,67-55,3.4次序關(guān)系,次序關(guān)系的定義 定義 設(shè)R是集合A上的自反的、反對稱的、傳遞的關(guān)系，則稱R是A上的偏序關(guān)系(記為“”)。序偶稱為偏序集。,設(shè)R是集合A上的反自反的、反對稱的、傳遞的關(guān)系，則稱R是A上的擬序關(guān)系(記為“”)。序偶稱為擬序集。,為使敘述簡潔，我們常將ab并且ab記為ab。 容易證明：偏序的逆關(guān)系-1也是一個偏序，我們用“”表示，讀作“大于等于”；擬序的逆

28、關(guān)系-1也是一個擬序，我們用“”表示，讀作“大于”。,溫 故 而 知 新 !,67-56,集合A的冪集(A)上定義的“”和“”分別是偏序關(guān)系和擬序關(guān)系。是偏序集，是擬序集。,例,實數(shù)集合R上定義的“”和“”分別是偏序關(guān)系和擬序關(guān)系。是偏序集，是擬序集。 大于零的自然數(shù)集合N上定義的“整除”關(guān)系“”也是一個偏序關(guān)系,是偏序集。 ALGOL或PL/I等都是塊結(jié)構(gòu)語言，設(shè)： Bb1,b2,b3,bn 是這種語言的一個程序中的塊的集合。對所有i和j，定義關(guān)系“”如下： bibj當且僅當bi被bj所包含。 則“”也是一個偏序關(guān)系,是偏序集。,溫 故 而 知 新 !,67-57,定義 設(shè)是一個偏序集，對任

29、意x,yA，如果xy或yx，則稱x與y是可比的。若x與y是可比的，xy，并且不存在zA，使得xzy，則稱y覆蓋x。,可比與覆蓋,例 1）集合A=a,b,c，偏序集中，a與a,b是可比的，a與b,c不是可比的；a,b覆蓋a，但a,b,c不覆蓋a。 偏序集中，對任意x,yA，x與y都是可比的，但是，x不覆蓋y，y也不覆蓋x。 偏序集中，對任意x,yA，x與y都是可比的，但是，x覆蓋x-1。 Z:所有的整數(shù) 偏序集中，2與3不是可比的；2與6是可比的，并且6覆蓋2；2與8是可比的，但8不覆蓋2；對任意nN+，0與n是可比的，但0不覆蓋n。 N:自然數(shù)的全體,溫 故 而 知 新 !,67-58,偏序集

30、的哈斯圖,用小圓圈或點表示A中的元素，省掉關(guān)系圖中所有的環(huán)。(因自反性) 對任意x,yA，若xy，則將x畫在y的下方，可省掉關(guān)系圖中所有邊的箭頭。(因反對稱性) 對任意x,yA，若y覆蓋x，則x與y之間用一條線相連之，否則無線相連。(因傳遞性) 按1),2),3)所作成的圖稱為哈斯圖(Hasse圖)。,溫 故 而 知 新 !,67-59,例,設(shè)A2,3,6,12,24,36,“”是A上的整除關(guān)系，畫出其一般的關(guān)系圖和哈斯圖。,溫 故 而 知 新 !,67-60,例,設(shè)集合Aa，Ba,b，Ca,b,c，Da,b,c,d。分別畫出集合A、B、C、D之冪集P(A)、P(B)、P(C)、P(D)上定義

31、的“”的哈斯圖。,a,a,b,a,b,a,b,c,a,b,a,c,b,c,a,b,c,a,b,c,d,a,b,a,c,b,c,a,d,b,d,c,d,a,b,c,a,b,d,a,c,d,b,c,d,a,b,c,d,溫 故 而 知 新 !,67-61,偏序集中的特殊元素,定義設(shè)是偏序集，B是A的任何一個子集。,若存在元素bB,使得對任意xB,都有xb,則稱b為B的最大元素，簡稱最大元。 若存在元素bB,使得對任意xB,都有bx,則稱b為B的最小元素，簡稱最小元。 若存在元素bB,使得對任意xB,滿足bxxb,則稱b為B的極大元素，簡稱極大元。 若存在元素bB,使得對任意xB,滿足xbxb,則稱b

32、為B的極小元素，簡稱極小元 。 若存在元素aA,使得對任意xB,都有xa,則稱a為B的上界。 若存在元素aA,使得對任意xB,都有ax,則稱a為B的下界。 若元素aA是B的上界,元素aA是B的任何一個上界,若均有aa,則稱a為B的最小上界或上確界,記aSupB?；騦ub 若元素aA是B的下界,元素aA是B的任何一個下界,若均有aa,則稱a為B的最大下界或下確界,記aInfB?；騡lb,溫 故 而 知 新 !,67-62,設(shè)是一偏序集，B是A的子集。則： 若bB是B的最大元b是B的極大元、上界、最小上界； 若bB是B的最小元b是B的極小元、下界、最大下界； 若aA是B的最小上界，且aBa是B的最大元； 若aA是B的最大下界，且aBa是B的最小元； 若B存在最大元，則B的最大元是惟一的； 若B存在最小元，則B的最小元是惟一的； 若bB是B的極大元，且b是唯一的b是B的最大元； 若bB是B的極小元，且b是唯一的b是B的最小元； 若B存在最小上