離散數(shù)學(xué)第四章等價(jià)關(guān)系和偏序關(guān)系

1第1頁，課件共25頁，創(chuàng)作于2023年2月等價(jià)關(guān)系的定義與實(shí)例定義設(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.

實(shí)例設(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ù)相等.2第2頁，課件共25頁，創(chuàng)作于2023年2月等價(jià)關(guān)系的驗(yàn)證驗(yàn)證模3相等關(guā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)自反性、對(duì)稱性、傳遞性得到驗(yàn)證3第3頁，課件共25頁，創(chuàng)作于2023年2月A上模3等價(jià)關(guān)系的關(guān)系圖設(shè)A={1,2,…,8},

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

4第4頁，課件共25頁，創(chuàng)作于2023年2月等價(jià)類定義設(shè)R為非空集合A上的等價(jià)關(guān)系,

x∈A，令

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

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

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

[3]=[6]={3,6}5第5頁，課件共25頁，創(chuàng)作于2023年2月等價(jià)類的性質(zhì)

定理1

設(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)∪{[x]|x∈A}=A，即所有等價(jià)類的并集就是A.

6第6頁，課件共25頁，創(chuàng)作于2023年2月實(shí)例A={1,2,…,8}上模3等價(jià)關(guān)系的等價(jià)類：

[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第7頁，課件共25頁，創(chuàng)作于2023年2月商集定義

設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集,記做A/R,A/R={[x]R

|x∈A}實(shí)例A={1,2,…,8},A關(guān)于模3等價(jià)關(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}}8第8頁，課件共25頁，創(chuàng)作于2023年2月集合的劃分定義設(shè)A為非空集合,若A的子集族π(π

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

(1)

π(2)

x

y(x,y∈π∧x≠y→x∩y=

)

(3)∪π=A

則稱π是A的一個(gè)劃分,稱π中的元素為A的劃分塊.9第9頁，課件共25頁，創(chuàng)作于2023年2月例題例1設(shè)A＝{a,b,c,d},

給定π1,π2,π3,π4,π5,π6如下：

π1={{a,b,c},esim00q}，π2={{a,b},{c},o0cuw2c}

π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第10頁，課件共25頁，創(chuàng)作于2023年2月等價(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)系確定的商集就是π.例2給出A＝{1,2,3}上所有的等價(jià)關(guān)系求解思路：先做出A的所有劃分,然后根據(jù)劃分寫出對(duì)應(yīng)的等價(jià)關(guān)系.11第11頁，課件共25頁，創(chuàng)作于2023年2月等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)π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>}∪IAπ4對(duì)應(yīng)于全域關(guān)系EA，π5對(duì)應(yīng)于恒等關(guān)系IA12第12頁，課件共25頁，創(chuàng)作于2023年2月實(shí)例例3設(shè)A={1,2,3,4}，在A

A上定義二元關(guān)系R：

<<x,y>,<u,v>>

R

x+y=u+v，求R導(dǎo)出的劃分.

解A

A={<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第13頁，課件共25頁，創(chuàng)作于2023年2月實(shí)例（續(xù)）根據(jù)<x,y>的x+y=2,3,4,5,6,7,8將A

A劃分成7個(gè)等價(jià)類：

(A

A)/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第14頁，課件共25頁，創(chuàng)作于2023年2月偏序關(guān)系定義非空集合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)系.15第15頁，課件共25頁，創(chuàng)作于2023年2月相關(guān)概念x與y可比：設(shè)R為非空集合A上的偏序關(guān)系,

x,y

A,x與y可比

x?y∨y?x.

結(jié)論：任取兩個(gè)元素x和y,可能有下述情況：

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

全序關(guān)系：

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

x,y

A,x與y都是可比的，則稱R為全序（或線序）實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系16第16頁，課件共25頁，創(chuàng)作于2023年2月覆蓋：設(shè)R為非空集合A上的偏序關(guān)系,x,y∈A,如果x?y且不存在z

A使得x?z?y,則稱y覆蓋x.實(shí)例：{1,2,4,6}集合上的整除關(guān)系,2覆蓋1,4和6覆蓋2.4不覆蓋1.

相關(guān)概念（續(xù)）17第17頁，課件共25頁，創(chuàng)作于2023年2月偏序集與哈斯圖定義集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.

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

>.哈斯圖：利用偏序自反、反對(duì)稱、傳遞性簡化的關(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)之間連邊18第18頁，課件共25頁，創(chuàng)作于2023年2月哈斯圖實(shí)例例4<{1,2,3,4,5,6,7,8,9},R整除><P({a,b,c}),R

>19第19頁，課件共25頁，創(chuàng)作于2023年2月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

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

20第20頁，課件共25頁，創(chuàng)作于2023年2月偏序集的特定元素定義設(shè)<A,?>為偏序集,B

A,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第21頁，課件共25頁，創(chuàng)作于2023年2月特殊元素的性質(zhì)

對(duì)于有窮集，極小元和極大元必存在，可能存在多個(gè).

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

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

孤立結(jié)點(diǎn)既是極小元，也是極大元.22第22頁，課件共25頁，創(chuàng)作于2023年2月定義設(shè)<A,?>為偏序集,B

A,y

A.(1)若

x(x∈B→x?y