4.4等價(jià)關(guān)系與偏序關(guān)系4.4.1等價(jià)關(guān)系4.4.2等價(jià)類和商集4.4.3集合的劃分4.4.4偏序關(guān)系4.4.5偏序集與哈斯圖1課件等價(jià)關(guān)系的定義與實(shí)例定義4.18

設(shè)R為非空集合上的關(guān)系.如果R是自反的、對(duì)稱的和傳遞的,則稱R為A上的等價(jià)關(guān)系.設(shè)R是一個(gè)等價(jià)關(guān)系,若<x,y>∈R,稱x等價(jià)于y,記做x～y.

例1

設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.不難驗(yàn)證R為A上的等價(jià)關(guān)系,因?yàn)?/p>

x∈A,有x≡x(mod3)

x,y∈A,若x≡y(mod3),則有y≡x(mod3)

x,y,z∈A,若x≡y(mod3),y≡z(mod3),則有

x≡z(mod3)2課件模3等價(jià)關(guān)系的關(guān)系圖設(shè)A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}R的關(guān)系圖如下：3課件等價(jià)類的性質(zhì)

定理4.8

設(shè)R是非空集合A上的等價(jià)關(guān)系,則

(1)x∈A,[x]是A的非空子集.

(2)x,y∈A,如果xRy,則[x]=[y].

(3)x,y∈A,如果xy,則[x]與[y]不交.

(4)，即所有等價(jià)類的并集就是A.

5課件性質(zhì)的證明由等價(jià)類定義可知,x∈A有[x]A.由自反性有xRx，因此x∈[x],即[x]非空.

任取z,則有

z∈[x]<x,z>∈R<z,x>∈R<z,x>∈R∧<x,y>∈R<z,y>∈R<y,z>∈R從而證明了z∈[y].綜上所述必有[x][y].同理可證[y][x].這就得到了[x]=[y].(3)假設(shè)[x]∩[y]≠,則存在z∈[x]∩[y],從而有z∈[x]∧z∈[y],即<x,z>∈R∧<y,z>∈R成立.根據(jù)R的對(duì)稱性和傳遞性必有<x,y>∈R,與xy矛盾6課件性質(zhì)的證明（續(xù)）(4)先證.任取y,y∈

x(x∈A∧y∈[x])

y∈[x]∧[x]A

y∈A從而有.再證A.任取y,y∈A

y∈[y]∧y∈A

y∈從而有A成立.綜上所述得7課件集合的劃分定義4.21

設(shè)A為非空集合,若A的子集族

(

P(A))滿足下面條件：

(1)

(2)xy(x,y∈∧x≠y→x∩y=)

(3)∪

=A

則稱是A的一個(gè)劃分,稱

中的元素為A的劃分塊.

例3

設(shè)A＝{a,b,c,d},給定

1,

2,

3,

4,

5,

6如下：

1={{a,b,c},ocosyws}，

2={{a,b},{c},0ecweow}

3={{a},{a,b,c,d}}，

4={{a,b},{c}}

5={,{a,b},{c,d}}，

6={{a,{a}},{b,c,d}}

則

1和

2是A的劃分,其他都不是A的劃分.9課件等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)商集A/R就是A的一個(gè)劃分不同的商集對(duì)應(yīng)于不同的劃分任給A的一個(gè)劃分

,如下定義A上的關(guān)系R：

R={<x,y>|x,y∈A∧x與y在的同一劃分塊中}

則R為A上的等價(jià)關(guān)系,且該等價(jià)關(guān)系確定的商集就是.例4給出A＝{1,2,3}上所有的等價(jià)關(guān)系求解思路：先做出A的所有劃分,然后根據(jù)劃分寫出對(duì)應(yīng)的等價(jià)關(guān)系.10課件例4

1,

2和

3分別對(duì)應(yīng)于等價(jià)關(guān)系R1,R2和R3.

其中

R1={<2,3>,<3,2>}∪IA

R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAA上的等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)：

4對(duì)應(yīng)于全域關(guān)系EA

5對(duì)應(yīng)于恒等關(guān)系IA11課件偏序關(guān)系定義4.22

非空集合A上的自反、反對(duì)稱和傳遞的關(guān)系，稱為A上的偏序關(guān)系，記作?.設(shè)?為偏序關(guān)系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.

實(shí)例集合A上的恒等關(guān)系IA是A上的偏序關(guān)系.

小于或等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.13課件相關(guān)概念定義4.23x與y可比

設(shè)R為非空集合A上的偏序關(guān)系,

x,yA,x與y可比x?y∨y?x.

結(jié)論：x,yA，下述幾種情況發(fā)生其一且僅發(fā)生其一.

x?y,

y?x,x＝y(tǒng),x與y不是可比的

定義4.25

全序

R為非空集合A上的偏序,x,yA,x與y都可比，則稱R為全序.定義4.26覆蓋

x,y∈A,如果x?y且不存在zA使得x?z?y,則稱y覆蓋x.實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系{1,2,4,6}集合上的整除關(guān)系,2覆蓋1,4和6覆蓋2.但4不覆蓋1.14課件偏序集與哈斯圖定義4.27集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.

實(shí)例：整數(shù)集和數(shù)的小于等于關(guān)系構(gòu)成偏序集<Z,≤>

冪集P(A)和包含關(guān)系構(gòu)成偏序集<P(A),R>.哈斯圖：利用偏序自反、反對(duì)稱、傳遞性簡(jiǎn)化的關(guān)系圖特點(diǎn)：每個(gè)結(jié)點(diǎn)沒有環(huán)兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊15課件

例7

已知偏序集<A,R>的哈斯圖如下圖所示,試求出集合A和關(guān)系R的表達(dá)式.

哈斯圖實(shí)例（續(xù)）A={a,b,c,d,e,f,g,h}

R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

17課件偏序集的特定元素定義4.28

設(shè)<A,?>為偏序集,BA,y∈B.

(1)若x(x∈B→y?x)成立,則稱y為B的最小元.

(2)若x(x∈B→x?y)成立,則稱y為B的最大元.

(3)若x(x∈B∧x?y→x=y)成立,則稱y為B的極小元.

(4)若x(x∈B∧y?x→x=y)成立,則稱y為B的極大元.

性質(zhì)：對(duì)于有窮集，極小元和極大元必存在，可能存在多個(gè).最小元和最大元不一定存在，如果存在一定惟一.最小元一定是極小元；最大元一定是極大元.孤立結(jié)點(diǎn)既是極小元，也是極大元.

18課件定義4.29

設(shè)<A,?>為偏序集,BA,yA.

（1）若x(x∈B→x?y)成立,則稱y為B的上界.

（2）若x(x∈B→y?x)成立,則稱y為B的下界.

（3）令C＝{y|y為B的上界},則稱C的最小元為B的最小上界或上確界.

（4）令D＝{y|y為B的下界},則稱D的最大元為B的最大下界或下確界.性質(zhì)：下界、上界、下確界、上確界不一定存在下界、上界存在不一定惟一下確界、上確界如果存在，則惟一集合的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì).

偏序集的特定元素(續(xù))19課件偏序集的特殊子集定義4.30

設(shè)<A,?>為偏序集,BA.(1)如果x,yB，x與y都是可比的，則稱B是A中的一條鏈，B中的元素個(gè)數(shù)稱為鏈的長(zhǎng)度；(2)如果x,yB，xy，x與y都是不可比的，則稱B是A中的一條反鏈，B中的元素個(gè)數(shù)稱為反鏈的長(zhǎng)度.實(shí)例：在偏序集<{1,2,…,9},|>中，{1,2,4,8}是長(zhǎng)為4的鏈，{1,4}是長(zhǎng)為2的鏈，{2,3}是長(zhǎng)為2的反鏈.對(duì)于單元集{2}，它的長(zhǎng)度是1，既是鏈也是反鏈.21課件分解為反鏈算法4.2偏序集反鏈分解算法輸入：偏序集A輸出：A中的反鏈B1,B2,…1．i12．BiA的所有極大元的集合（顯然Bi是一條反鏈）3．令A(yù)ABi4．ifA