離散數學第四章等價關系和偏序關系

1第一頁，共二十五頁，2022年，8月28日等價關系的定義與實例定義設R為非空集合上的關系.如果R是自反的、對稱的和傳遞的,則稱R為A上的等價關系.設R是一個等價關系,若<x,y>∈R,稱x等價于y,記做x～y.

實例設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的余數相等.2第二頁，共二十五頁，2022年，8月28日等價關系的驗證驗證模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)自反性、對稱性、傳遞性得到驗證3第三頁，共二十五頁，2022年，8月28日A上模3等價關系的關系圖設A={1,2,…,8},

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

4第四頁，共二十五頁，2022年，8月28日等價類定義設R為非空集合A上的等價關系,x∈A，令

[x]R={y|y∈A∧xRy}稱[x]R為x關于R的等價類,簡稱為x的等價類,簡記為[x].實例A={1,2,…,8}上模3等價關系的等價類：

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

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

[3]=[6]={3,6}5第五頁，共二十五頁，2022年，8月28日等價類的性質

定理1

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

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

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

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

(4)∪{[x]|x∈A}=A，即所有等價類的并集就是A.

6第六頁，共二十五頁，2022年，8月28日實例A={1,2,…,8}上模3等價關系的等價類：

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

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

[3]=[6]={3,6}

以上3類兩兩不交，

{1,4,7}{2,5,8}{3,6}={1,2,…,8}7第七頁，共二十五頁，2022年，8月28日商集定義

設R為非空集合A上的等價關系,以R的所有等價類作為元素的集合稱為A關于R的商集,記做A/R,A/R={[x]R

|x∈A}實例A={1,2,…,8},A關于模3等價關系R的商集為

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

A關于恒等關系和全域關系的商集為：

A/IA

={{1},{2},…,{8}}

A/EA

={{1,2,…,8}}8第八頁，共二十五頁，2022年，8月28日集合的劃分定義設A為非空集合,若A的子集族π(πP(A))滿足下面條件：

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

(3)∪π=A

則稱π是A的一個劃分,稱π中的元素為A的劃分塊.9第九頁，共二十五頁，2022年，8月28日例題例1設A＝{a,b,c,d},

給定π1,π2,π3,π4,π5,π6如下：π1={{a,b,c},jtzwbi5}，π2={{a,b},{c},bdlu48i}

π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的劃分.

為什么？10第十頁，共二十五頁，2022年，8月28日等價關系與劃分的一一對應商集A/R就是A的一個劃分不同的商集對應于不同的劃分任給A的一個劃分π,如下定義A上的關系R：

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

則R為A上的等價關系,且該等價關系確定的商集就是π.例2給出A＝{1,2,3}上所有的等價關系求解思路：先做出A的所有劃分,然后根據劃分寫出對應的等價關系.11第十一頁，共二十五頁，2022年，8月28日等價關系與劃分之間的對應π1,π2和π3分別對應等價關系R1,R2和R3.

R1={<2,3>,<3,2>}∪IA，R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAπ4對應于全域關系EA，π5對應于恒等關系IA12第十二頁，共二十五頁，2022年，8月28日實例例3設A={1,2,3,4}，在AA上定義二元關系R：

<<x,y>,<u,v>>Rx+y=u+v，求R導出的劃分.

解AA={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}13第十三頁，共二十五頁，2022年，8月28日實例（續(xù)）根據<x,y>的x+y=2,3,4,5,6,7,8將AA劃分成7個等價類：

(AA)/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}

14第十四頁，共二十五頁，2022年，8月28日偏序關系定義非空集合A上的自反、反對稱和傳遞的關系，稱為A上的偏序關系，記作?.設?為偏序關系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.

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

小于或等于關系,整除關系和包含關系也是相應集合上的偏序關系.15第十五頁，共二十五頁，2022年，8月28日相關概念x與y可比：設R為非空集合A上的偏序關系,

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

結論：任取兩個元素x和y,可能有下述情況：

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

全序關系：

R為非空集合A上的偏序,x,yA,x與y都是可比的，則稱R為全序（或線序）實例：數集上的小于或等于關系是全序關系整除關系不是正整數集合上的全序關系16第十六頁，共二十五頁，2022年，8月28日覆蓋：設R為非空集合A上的偏序關系,x,y∈A,如果x?y且不存在zA使得x?z?y,則稱y覆蓋x.實例：{1,2,4,6}集合上的整除關系,2覆蓋1,4和6覆蓋2.4不覆蓋1.

相關概念（續(xù)）17第十七頁，共二十五頁，2022年，8月28日偏序集與哈斯圖定義集合A和A上的偏序關系?一起叫做偏序集,記作<A,?>.

實例：整數集和小于等于關系構成偏序集<Z,≤>，冪集P(A)和包含關系構成偏序集<P(A),R>.哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關系圖特點：每個結點沒有環(huán)，兩個連通的結點之間的序關系通過結點位置的高低表示，位置低的元素的順序在前，具有覆蓋關系的兩個結點之間連邊18第十八頁，共二十五頁，2022年，8月28日哈斯圖實例例4<{1,2,3,4,5,6,7,8,9},R整除><P({a,b,c}),R>19第十九頁，共二十五頁，2022年，8月28日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

哈斯圖實例（續(xù)）例5已知偏序集<A,R>的哈斯圖如右圖所示,試求出集合A和關系R的表達式.

20第二十頁，共二十五頁，2022年，8月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)成立,則稱y為B的極小元.

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

21第二十一頁，共二十五頁，2022年，8月28日特殊元素的性質

對于有窮集，極小元和極大元必存在，可能存在多個.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是極小元；最大元一定是極大元.

孤立結點既是極小元，也是極大元.22第二十二頁，共二十五頁，2022年，8月28日定義設<A,?>為偏序集,BA,yA.(1)若x(x∈B→x?