離散數(shù)學(xué)等價關(guān)系與偏序關(guān)系演示文稿1/30第1頁，共28頁。2/30（優(yōu)選）離散數(shù)學(xué)等價關(guān)系與偏序關(guān)系第2頁，共28頁。等價關(guān)系實例例2：考慮整數(shù)集Z上的模n同余關(guān)系。例4：設(shè)f:X

Y，Ker(f)={(x,y)x,yX，且f(x)=f(y)}。Ker(f)是X上的等價關(guān)系。例3：實數(shù)集上的“>”、“<”、“≧”、“≦”是不是R上的等價關(guān)系？實數(shù)集上的“>”、“<”、“≧”、“≦”都不是R上的等價關(guān)系。是等價關(guān)系。第3頁，共28頁。例5：設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：

R={(x,y)|x,y

A∧x≡y(mod3)}R的關(guān)系圖如下：等價關(guān)系的關(guān)系圖第4頁，共28頁。

定義2

設(shè)R是X上的一個等價關(guān)系，xX，X的子集Ex={yyX且xRy}稱為x關(guān)于R的等價類，或簡記為x的等價類。x的等價類常記為[x]，即[x]={yyX且xRy}。例5：設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：

R={(x,y)|x,y

A∧x≡y(mod3)}等價類的定義A={1,2,…,8}上模3等價關(guān)系的等價類：

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}第5頁，共28頁。等價類的性質(zhì)(3)

x,y

X,如果(x,y)

R,則[x]∩[y]=

。定理1設(shè)R是非空集合X上的等價關(guān)系,則

(1)

x

X,[x]≠

。(2)

x,y

X,如果(x,y)

R,則[x]=[y]。

(4)，即所有等價類的并集就是X。第6頁，共28頁。

定義3

設(shè)X為非空集合，X的若干個子集形成的集族

稱為X的一個劃分，如果具有性質(zhì)：集合的劃分如果

是X的一個劃分，則當

=k時，被稱為X的一個k-劃分。(2)x,y，若xy，則x∩y=;(1)

；(3)

。

稱

中的元素為X的劃分塊。第7頁，共28頁。例6：設(shè)A＝{a,b,c,d},給定

1,

2,

3,

4,

5,

6如下：

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

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

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的劃分。實例第8頁，共28頁。

定理1

設(shè)R是X上的一個等價關(guān)系，則R的所有等價類的集合是X的一個劃分。等價關(guān)系與集合的劃分

定理2

設(shè)是集合X的一個劃分，令

R={(x,y)|x,y

X∧x與y在

的同一劃分塊中}則R是X上的一個等價關(guān)系，并且就是R的等價類之集。注：由定理1、2可得：X上的等價關(guān)系與X的劃分是一一對應(yīng)的，并且互相確定。第9頁，共28頁。

定義4

設(shè)R是X上的等價關(guān)系，由R所確定的X的劃分也就是R的所有等價類之集稱為X對R的商集，并記X/R。

即：X/R={[x]xX，[x]是x的等價類}。

等價關(guān)系R確定的劃分是R的所有等價類之集

{[x]xX}商集第10頁，共28頁。例7：令A(yù)={1,2,…,8}。A關(guān)于模3等價關(guān)系R的商集為：

A/R={{1,4,7},{2,5,8},{3,6}}

A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：

A/IA={{1},{2},…,{8}}A/EA={{1,2,…,8}}實例第11頁，共28頁。例8：給出A＝{1,2,3}上所有的等價關(guān)系。求解思路：先做出A的所有劃分,然后根據(jù)劃分寫出對應(yīng)的等價關(guān)系。

實例第12頁，共28頁。實例

1,

2和

3分別對應(yīng)于等價關(guān)系R1,R2和R3，其中

R1={(2,3),(3,2)}∪IA

R2={(1,3),(3,1)}∪IA

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

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

5對應(yīng)于恒等關(guān)系IA；問題：設(shè)集合X為有限集，|X|=n，則X上有多少個等價關(guān)系？第13頁，共28頁。定理4設(shè)R為X上的一個二元關(guān)系，則e(R)=(R∪R-1)*。

R的等價閉包(R的自反對稱傳遞閉包)，記為e(R),e(R)是X上包含R的那些等價關(guān)系的交集。

定理5

設(shè)R,S是X上的等價關(guān)系，則R

S是等價關(guān)系的充要條件是R

S=S

R。

推論設(shè)R,S是X上的等價關(guān)系，則R

S是等價關(guān)系的充要條件是R

S

S

R。等價關(guān)系的運算第14頁，共28頁。

定義1

集合X上的二元關(guān)系R稱為偏序關(guān)系，如果R同時滿足以下三個性質(zhì)：當抽象地討論X上的偏序關(guān)系時，常用符號“”表示偏序關(guān)系。如果xy，則讀作“x小于或等于y”。1.R是自反的；2.R是反對稱的；3.R是傳遞的。約定xy且xy時，就記為x<y。在偏序關(guān)系中，并不是X中所有元素都可比較;如果存在x,yX使得xy與yx中有一個成立，則稱x與y可比較;如果x,yX，xy并且yx，則稱x與y不可比較。2偏序關(guān)系第15頁，共28頁。

定義2

設(shè)是X上的一個偏序關(guān)系，則稱二元組(X,)為偏序集。一個集合上可能存在多個偏序集。例1：設(shè)S是一個集合，S的子集間的包含關(guān)系是不是偏序關(guān)系？在這個偏序集中，存在著不可比較元素。例如：S={a,b,c}，則{a}與{b,c}不可比較。偏序集例如實數(shù)集上存在(R,)和(R,≥)兩個偏序集。

S的子集間的包含關(guān)系是2S上的偏序關(guān)系，(2S,)是一個偏序集。第16頁，共28頁。例2：自然數(shù)集合N上的整除關(guān)系“

”是不是偏序關(guān)系?自然數(shù)集合N上的整除關(guān)系“

”是偏序關(guān)系。

(N,)是一個偏序集。設(shè)≤是X上的偏序關(guān)系，則≤的逆≤-1也是X上的偏序關(guān)系，以后用“≥”表示≤的逆關(guān)系，并讀成“大于或等于”。若x≥y且xy，則簡記為x>y。實例第17頁，共28頁。

定義3

集合X上的偏序關(guān)系叫做全序關(guān)系，如果x,yX，xy與yx至少有一個成立。全序關(guān)系也稱為線性序關(guān)系。X與全序關(guān)系≤構(gòu)成的二元組(X,≤)稱為全序集。偏序集與全序集的主要區(qū)別在于全序集中任兩個元素均可比較“大小”，而在偏序集中任意兩個元素不一定都能比較大小。實數(shù)間的常用的“小于或等于”關(guān)系是不是全序關(guān)系?全序關(guān)系與全序集集合的包含關(guān)系與自然數(shù)間的整除關(guān)系是不是全序關(guān)系?是全序關(guān)系，相應(yīng)的偏序集也是全序集。二者都不是全序關(guān)系。第18頁，共28頁。

定義4設(shè)(X,≤)是一個偏序集，稱y蓋住x，如果x<y且對每個zX，若x≤z≤y，則x=z或y=z。如果y蓋住x，則y被稱為x的后繼，而x稱為y的前驅(qū)。蓋住的定義例3：偏序集(N,≤)中，稱3蓋住2，3是2的后繼，2是3的先驅(qū)。

{1,2,4,6}集合上的整除關(guān)系,2覆蓋1,4和6覆蓋2；但4不覆蓋1.第19頁，共28頁。哈斯(Hasse)圖首先偏序關(guān)系≤是自反的，所以偏序關(guān)系的關(guān)系圖中每個頂點都有一個環(huán)，因此可以省略每個頂點的環(huán)。其次由于偏序關(guān)系是傳遞的，那么只要在前驅(qū)與后繼間聯(lián)線即可。最后由于反對稱性，若x<y，x

y，則點y畫在x的上方，這樣就不必用矢線了，按上述方法畫出的圖稱為(X,≤)的哈斯圖。

第20頁，共28頁。特點：

(1)每個結(jié)點沒有環(huán);(2)兩個連通的結(jié)點之間的序關(guān)系通過結(jié)點位置的高低表示，位置低的元素的順序在前;(3)具有覆蓋關(guān)系的兩個結(jié)點之間連邊。

哈斯圖就是利用偏序的自反、反對稱、傳遞性簡化了的關(guān)系圖。哈斯(Hasse)圖的特點第21頁，共28頁。例4：({1,2,3,4,5,6,7,8,9},R整除)(P({a,b,c}),R

)哈斯圖實例第22頁，共28頁。

例5：已知偏序集(A,R)的哈斯圖如下圖所示，試求出集合A和關(guān)系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

哈斯圖實例第23頁，共28頁。例6：設(shè)A={a1,a2,...,an}是一個全序集，則其元素(A,≤)的哈斯圖象一條鏈子一樣。所以，全序關(guān)系也叫做線性序關(guān)系，全序集又稱為線性序集?？梢浴皬男〉酱蟆迸帕袨椋?/p>

ai1<ai2<...<ain全序關(guān)系的哈斯圖第24頁，共28頁。

定義5設(shè)(X,≤)是一個偏序集，BX。如果存在一個元素aX使得對B中每個元素x有x≤a，則稱a為B的一個上界。上界與下界的定義如果存在一個元素bX，使得對B的每一個元素x有b≤x，則稱b為B的一個下界。①上界與下界都不一定存在。例7：令A(yù)={2,3,6,12,24,36}，A在整除關(guān)系“”下構(gòu)成一個偏序集(A,)。{24,36}不存在上界,②上界與下界可能有很多元素6,12,24,36都是子集{2,3}的上界。{2,3}不存在下界,第25頁，共28頁。

定義6設(shè)(X,≤)是一個偏序集，BX。如果存在一個元素aB使得對B中每個元素x有x≤a，則稱a是B中的最大元素。①最大元素一定是上界，最小元素一定是下界;最大與最小元素如果存在一個元素bB，使得對B的每一個元素x有b≤x，則稱b是B中的最小元素。②有上下界不一定有最大與最小元素,③最大元素與最小元素若有一定是唯一的。因為上下界不一定在子集中;第26頁，共28頁。

定義7

設(shè)(X,≤)是一個偏序集，BX。如果B有上界且B的一切上界之集