離散數(shù)學(xué)-2-4-1(等價關(guān)系)2014-10-13

2.4特殊關(guān)系關(guān)系可能具有的性質(zhì)：自反反自反對稱反對稱傳遞特殊關(guān)系：具有上述某些性質(zhì)的關(guān)系等價關(guān)系：自反、對稱、傳遞偏序關(guān)系：自反、反對稱、傳遞第一頁第二頁，共21頁。2.4.1等價關(guān)系定義2.21

設(shè)R為非空集合A上的關(guān)系（即A

并且R

A

A）。

如果R是自反的、對稱的和傳遞的，

則稱R為A上的等價關(guān)系。

設(shè)R是一個等價關(guān)系。

如果<x,y>∈R,

則稱x與y等價.

第二頁第三頁，共21頁。例2.50判斷下列關(guān)系是否為等價關(guān)系

R1:選修離散數(shù)學(xué)課程同學(xué)中的“同班”關(guān)系 R2:冪集上的“

”關(guān)系 R3:直線間的“平行”關(guān)系 R4:整數(shù)集上的“

”關(guān)系 R5:人群中的“朋友”關(guān)系自反對稱傳遞等價關(guān)系R1R2R3R4R5√×√√√√√√√√√√√√××

×××第三頁第四頁，共21頁。例2.52給定一個正整數(shù)n，考慮整數(shù)集合Z上的整除關(guān)系R={<x,y>|x

Z，y

Z，(x

y)被n整除}。證明R是Z上的等價關(guān)系。證明:

（1）……因此，R是自反的。（2）……因此，R是對稱的。（3）……因此，R是傳遞的。綜上，關(guān)系R為Z上的等價關(guān)系。證畢。

x

y(modn)：x-y可以被n整除，“x和y模n同余”。同余關(guān)系第四頁第五頁，共21頁。例2.53設(shè)集合A={a,b,c,d,e}上的關(guān)系R1={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<d,d>,<d,e>,<e,d>,<e,e>}和R2={<a,b>,<b,a>,<b,b>,<c,c>,<d,d>,<d,e>}，判斷R1和R2是否為等價關(guān)系？用關(guān)系矩陣和關(guān)系圖表示其中的等價關(guān)系。解:

R1具有自反性、對稱性和傳遞性，是等價關(guān)系。

R2不是等價關(guān)系。

第五頁第六頁，共21頁。例2.53(續(xù))設(shè)集合A={a,b,c,d,e}上的關(guān)系R1={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<d,d>,<d,e>,<e,d>,<e,e>}和R2={<a,b>,<b,a>,<b,b>,<c,c>,<d,d>,<d,e>}，判斷R1和R2是否為等價關(guān)系？用關(guān)系矩陣和關(guān)系圖表示其中的等價關(guān)系。解:相互等價的元素將關(guān)系矩陣分成了不同的塊；相互等價的元素組成了關(guān)系圖中相互連通的部分。aebdcR1第六頁第七頁，共21頁。等價類定義2.22設(shè)R是非空集合A上的等價關(guān)系，對于任意x

A，稱集合

[x]R={y|y

A且<x,y>

R}為x關(guān)于R的等價類，或稱為由x生成的一個R的等價類；并稱其中的x為[x]R的生成元或代表元。即，[x]R表示由所有與x關(guān)于R等價的元素組成的集合。

第七頁第八頁，共21頁。例2.54設(shè)R是集合A={1,2,3,4,5,6,7,8}上的模3同余關(guān)系，用關(guān)系圖表示該關(guān)系？并求R的所有等價類。

解:

集合A={1,2,3,4,5,6,7,8}上的模3同余關(guān)系為R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<2,8>,<3,3>,<3,6>,<4,1>,<4,4>,<4,7>,<5,2>,<5,5>,<5,8>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>,<8,2>,<8,5>,<8,8>}可以得到關(guān)系R的關(guān)系圖如圖所示。關(guān)于R的等價類如下[1]R=[4]R=[7]R={1,4,7}[2]R=[5]R=[8]R={2,5,8}[3]R=[6]R={3,6}147258R36第八頁第九頁，共21頁。等價類的性質(zhì)定理2.19

設(shè)R為非空集合A上的等價關(guān)系，則：

(1)對于任意x∈A，[x]R

是A的非空子集.

(2)對于任意x,y∈A，如果<x,y>

R,則[x]R=[y]R.

(3)對于任意x,y∈A，如果<x,y>

R,則[x]R

[y]R=

.

(4)

∪x

A[x]R

=A.第九頁第十頁，共21頁。商集定義2.23設(shè)R是非空集合A上的等價關(guān)系；將由R的所有等價類構(gòu)成的集合稱為A關(guān)于R的商集,記A/R。A/R={[x]R

|x

A}

例2.25:令R是集合A={1,2,3,4,5,6,7,8}上的模3同余關(guān)系；A關(guān)于R的商集為：

A/R={[1]R,[2]R,[3]R}={{1,4,7},{2,5,8},{3,6}}A關(guān)于恒等關(guān)系的商集為：

A/IA

={{1},{2},{3},{4},{5},{6},{7},{8}}A關(guān)于全域關(guān)系的商集為：

A/EA

={{1,2,3,4,5,6,7,8}}第十頁第十一頁，共21頁。商集的計(jì)算例2.56

對于集合A={a,b,c,d,e}上的關(guān)系R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<d,d>,<d,e>,<e,d>,<e,e>}，求A/R。解：根據(jù)等價類的定義有[a]R=[b]R

={a,b},

[c]R

={c},[d]R=[e]R

={d,e}從而有A/R={{a,b},{c},{d,e}}第十一頁第十二頁，共21頁。劃分定義2.24

對于非空集合A，如果某個集合S={S1,S2,…,Sm}滿足①Si

A且

Si≠

（i=1,2,…,m），②Si

Sj=

（i≠j；i=1,2,…,m；j=1,2,…,m），③S1

S2

…

Sm=A，則將S稱為A的一個劃分，將S1,S2,…,Sm稱為這個劃分塊。第十二頁第十三頁，共21頁。例2.57設(shè)集合A＝{1,2,3,4}，判斷下列集合是否是A的劃分

①{{1},{2,3},{4}}②{{1,2,3,4}}③{{1},{2,3},{1,4}}④{

,{1,2},{3,4}}⑤{{1},{2,3}}⑥{{1,2,3,4},

}第十三頁第十四頁，共21頁。例2.58考察例2.55中集合A={1,2,3,4,5,6,7,8}。商集A/R={{1,4,7},{2,5,8},{3,6}}是否為A的劃分？第十四頁第十五頁，共21頁。等價類與劃分(等價類->劃分)定理2.20設(shè)R是非空集合A上的等價關(guān)系，則商集A/R是A的一個劃分，將其稱為由等價關(guān)系R導(dǎo)出的等價劃分，其中每個等價類都是一個劃分塊。例2.59對于例2.56中集合A={a,b,c,d,e}以及商集A/R={{a,b},{c},{d,e}}。

顯然，A/R是集合A的一個劃分。

第十五頁第十六頁，共21頁。等價類與劃分(劃分->等價類)定理2.21設(shè)S={S1,S2,…,Sm}是非空集合A的一個劃分，則由該劃分確定的關(guān)系

R=(S1

S1)

(S2

S2)

…

(Sm

Sm)是A上的等價關(guān)系。將上述等價關(guān)系稱為由劃分S所導(dǎo)出的等價關(guān)系。

第十六頁第十七頁，共21頁。例2.60對于集合A＝{1,2,3,4}的劃分{{1},{2,3},{4}}，試構(gòu)造A上的等價關(guān)系。解:根據(jù)定理2.21，構(gòu)造如下關(guān)系R=({l}

{l})

({2,3}

{2,3})

({4}

{4})={<1,1>}

{<2,2>,<2,3>,<3,2>,<3,3>}

{<4,4>}={<1,1>,<2,2>,<2,3>,<3,2>,<3,3>,<4,4>}顯然，關(guān)系R是自反的、對稱的和傳遞的，即，R是A上的等價關(guān)系。

第十七頁第十八頁，共21頁。練習(xí)設(shè)A={1,2,3,4,5}.1)

求A的劃分

={{1,2},{3},{4,5}}對應(yīng)的等價關(guān)系。

2)已知關(guān)系R={<1,3>,<1,1>,<3,1>,<3,3>,<2,2>,<5,2>,<5,5>,<2,5>,<4,2>,<4,4>,<4,5>,<5,4>,<2,4>}，求R對應(yīng)的劃分。解:R

={<1,1>,<2,2>,<1,2>,<2,1>,<3,3>,<4,4>,<5,5>,<4,