4.4等價關系與偏序關系4.4.1等價關系4.4.2等價類和商集4.4.3集合的劃分4.4.4偏序關系4.4.5偏序集與哈斯圖1課件等價關系的定義與實例定義4.18

設R為非空集合上的關系.如果R是自反的、對稱的和傳遞的,則稱R為A上的等價關系.設R是一個等價關系,若<x,y>∈R,稱x等價于y,記做x～y.

例1

設A={1,2,…,8},如下定義A上的關系R：

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

其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數與y除以3的余數相等.不難驗證R為A上的等價關系,因為

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等價關系的關系圖設A={1,2,…,8},

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

定理4.8

設R是非空集合A上的等價關系,則

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

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

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

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

5課件性質的證明由等價類定義可知,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)假設[x]∩[y]≠,則存在z∈[x]∩[y],從而有z∈[x]∧z∈[y],即<x,z>∈R∧<y,z>∈R成立.根據R的對稱性和傳遞性必有<x,y>∈R,與xy矛盾6課件性質的證明（續）(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

設A為非空集合,若A的子集族

(

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

(1)

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

(3)∪

=A

則稱是A的一個劃分,稱

中的元素為A的劃分塊.

例3

設A＝{a,b,c,d},給定

1,

2,

3,

4,

5,

6如下：

1={{a,b,c},6ooswsk}，

2={{a,b},{c},a6im6qc}

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課件等價關系與劃分的一一對應商集A/R就是A的一個劃分不同的商集對應于不同的劃分任給A的一個劃分

,如下定義A上的關系R：

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

則R為A上的等價關系,且該等價關系確定的商集就是.例4給出A＝{1,2,3}上所有的等價關系求解思路：先做出A的所有劃分,然后根據劃分寫出對應的等價關系.10課件例4

1,

2和

3分別對應于等價關系R1,R2和R3.

其中

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

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

R3={<1,2>,<2,1>}∪IAA上的等價關系與劃分之間的對應：

4對應于全域關系EA

5對應于恒等關系IA11課件偏序關系定義4.22

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

實例集合A上的恒等關系IA是A上的偏序關系.

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

設R為非空集合A上的偏序關系,

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

結論：x,yA，下述幾種情況發生其一且僅發生其一.

x?y,

y?x,x＝y,x與y不是可比的

定義4.25

全序

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

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

實例：整數集和數的小于等于關系構成偏序集<Z,≤>

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

例7

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

哈斯圖實例（續）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

設<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的極大元.

性質：對于有窮集，極小元和極大元必存在，可能存在多個.最小元和最大元不一定存在，如果存在一定惟一.最小元一定是極小元；最大元一定是極大元.孤立結點既是極小元，也是極大元.

18課件定義4.29

設<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的最大下界或下確界.性質：下界、上界、下確界、上確界不一定存在下界、上界存在不一定惟一下確界、上確界如果存在，則惟一集合的最小元就是它的下確界，最大元就是它的上確界；反之不對.

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

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