離散數(shù)學(xué)第三章

3-10等價(jià)關(guān)系與等價(jià)類下面我們介紹一類很重要的關(guān)系，也是我們遇到最多的關(guān)系，例如，數(shù)值相等關(guān)系=、命題間的等價(jià)關(guān)系

、三角形相似∽和全等關(guān)系≌，…..一.等價(jià)關(guān)系1.定義:設(shè)R是A上關(guān)系,若R是自反的、對(duì)稱的和傳遞的，則稱R是A中的等價(jià)關(guān)系。若a,bA，且aRb，則稱a與b等價(jià)。例子，集合A={1,2,3,4,5,6,7},R是A上的模3同余關(guān)系，即R={<x,y>|x-y可被3整除(或x/3與y/3的余數(shù)相同)}即<x,y>∈Rx(mod3)=y(mod3)例如4(mod3)=7(mod3)

3(mod3)=6(mod3)R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<3,3>,<3,6>,<4,1>,<4,4>,<4,7>,<5,2>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>}2。5。1。4。7。3。6。2.等價(jià)關(guān)系的有向圖1)等價(jià)關(guān)系的有向圖:從關(guān)系圖可看出，R是自反、對(duì)稱、傳遞的關(guān)系，所以R是等價(jià)關(guān)系。

等價(jià)關(guān)系R的有向圖由若干個(gè)獨(dú)立子圖(R圖的一部分)構(gòu)成的，每個(gè)獨(dú)立子圖都是完全關(guān)系圖。上述關(guān)系R圖就是由三個(gè)獨(dú)立的完全圖構(gòu)成的。

下面給出八個(gè)關(guān)系如圖所示，根據(jù)等價(jià)關(guān)系有向圖的特點(diǎn)，判斷哪些是等價(jià)關(guān)系，

1。2。1。2。3。1。A={1}A={1,2}A={1,2,3}

2)完全關(guān)系(全域關(guān)系A(chǔ)×A)圖，下面分別是當(dāng)A中只有1、2、3個(gè)元素時(shí)的完全關(guān)系圖。A={1,2,3}下面是A中關(guān)系：1。2。。1。2。。331。2。。1。2。。1。2。。1。2。。3333R2R1R5R61。2。。1。2。。33R3R4R7R8思考題：A={1,2,3},可構(gòu)造多少個(gè)A中不同的等價(jià)關(guān)系？可以根據(jù)等價(jià)關(guān)系有向圖的特點(diǎn)來考慮。如果等價(jià)關(guān)系R中有

a)三個(gè)獨(dú)立子圖的情形，則()個(gè)等價(jià)關(guān)系。

b)二個(gè)獨(dú)立子圖的情形，則()個(gè)等價(jià)關(guān)系。

c)一個(gè)獨(dú)立子圖的情形，則()個(gè)等價(jià)關(guān)系。一共有()個(gè)不同的R中的等價(jià)關(guān)系。二.等價(jià)類

我們經(jīng)常用等價(jià)關(guān)系對(duì)集合進(jìn)行劃分，得到的劃分塊稱之為等價(jià)類。1.定義：R是A上的等價(jià)關(guān)系，a∈A,由a確定的集合[a]R={x|x∈A∧<a,x>∈R}稱集合[a]R為由a形成的R等價(jià)類。簡稱a等價(jià)類?？梢妜∈[a]R<a,x>∈R上例中，A={1,2,3,4,5,6,7},R是A上的模3同余關(guān)系，[1]R={1,4,7}=[4]R=[7]R----余數(shù)為1的等價(jià)類

[2]R={2,5}=[5]R----余數(shù)為2的等價(jià)類

[3]R={3,6}=[6]R----余數(shù)為0的等價(jià)類思考題：此例為什么只有三個(gè)等價(jià)類？2.由等價(jià)關(guān)系圖求等價(jià)類：R圖中每個(gè)獨(dú)立子圖上的結(jié)點(diǎn)，構(gòu)成一個(gè)等價(jià)類。不同的等價(jià)類個(gè)數(shù)=獨(dú)立子圖個(gè)數(shù)。上述三個(gè)等價(jià)關(guān)系各有幾個(gè)等價(jià)類？說出對(duì)應(yīng)的各個(gè)等價(jià)類。從上述模3同余關(guān)系例子中，可以歸納出等價(jià)類的性質(zhì)：任何兩個(gè)等價(jià)類要么相等，要么不相交；那么在什么情況下相等？那么在什么情況下不相交？1。2。。3R21。2。。3R1。R3。。1233.等價(jià)類性質(zhì)

R是A上等價(jià)關(guān)系，任意a,b,c∈A

⑴同一個(gè)等價(jià)類中的元素，彼此有等價(jià)關(guān)系R。

即任意x,y∈[a]R，必有<x,y>∈R證明：任取x,y∈[a]R，由等價(jià)類定義得，<a,x>∈R,<a,y>∈R,由R對(duì)稱得，<x,a>∈R，又由R傳遞得<x,y>∈R。⑵

[a]R∩[b]R=Φ，當(dāng)且僅當(dāng)<a,b>R。證明:(充分性)設(shè)<a,b>R，假設(shè)[a]R∩[b]R≠Φ,則存在x∈[a]R∩[b]R，∴x∈[a]R∧x∈[b]R,∴<a,x>∈R,<b,x>∈R,由R對(duì)稱得<x,b>∈R又由R傳遞得<a,b>∈R,產(chǎn)生矛盾。(必要性)若[a]R∩[b]R=Φ,而<a,b>∈R,由等價(jià)類定義得

b∈[a]R,又因?yàn)閎Rb,所以b∈[b]R，所以b∈[a]R∩[b]R，產(chǎn)生矛盾。⑶

[a]R=[b]R當(dāng)且僅當(dāng)<a,b>∈R。證明:(充分性)若<a,b>∈R，則任何x∈[a]R，有<a,x>∈R，由對(duì)稱性得<b,a>∈R，再由傳遞性得<b,x>∈R,∴x∈[b]R，所以[a]R[b]R。類似可證[b]R[a]R?！郲a]R=[b]R。(必要性)如果[a]R=[b]R,由于有aRa,所以a∈[a]R

，a∈[b]R

，所以有<b,a>∈R，由對(duì)稱性得<a,b>∈R.⑷.A中任何元素a,a必屬于且僅屬于一個(gè)等價(jià)類。證明：A中任何元素a,由于有aRa,所以a∈[a]R

，如果a∈[b]R

，所以有<b,a>∈R.由性質(zhì)⑶[a]R=[b]R。⑸

任意兩個(gè)等價(jià)類

[a]R、[b]R，要么[a]R=[b]R

，要么[a]R∩[b]R=Φ

。

(因?yàn)橐?lt;a,b>∈R，要么<a,b>R。)⑹R的所有等價(jià)類構(gòu)成的集合是A的一個(gè)劃分。

(由性質(zhì)⑷⑸即得。)(這個(gè)劃分稱之為商集)三.商集

商”和除法有關(guān)，比如把一塊蛋糕平均分成四份，從兩種不同的角度看這件事：從算術(shù)角度看：1除以4,每份1/4,這就是“商”,于是:1=1/4+1/4+1/4+1/4從集合角度看：用刀分}{生日日快快樂樂生定義：R是A上等價(jià)關(guān)系，由R的所有等價(jià)類構(gòu)成的集合稱之為A關(guān)于R的商集。記作A/R。即

A/R={[a]R|a∈A}例如A={1,2,3,4,5,6,7},R上模3同余關(guān)系，則

A/R={[1]R,[2]R,[3]R}={{1,4,7},{2,5},{3,6}}練習(xí)

X={1,2,3},X上關(guān)系R1、R2

、R3，如上圖所示。X/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}}X/R2={[1]R2,[2]R2}={{1},{2,3}}X/R1={[1]R3}={{1,2,3}}1。2。。3R21。2。。3R1。R3。。123定理1:

集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃分，該劃分就是商集A/R.證明：由等價(jià)類性質(zhì)可得：

1)A/R中任意元素[a]R，有[a]RA.2)設(shè)[a]R,[b]R是A/R的兩個(gè)不同元素，有[a]R[b]R=Φ3)因?yàn)锳中每個(gè)元素都屬于一個(gè)等價(jià)類，所以所有等價(jià)類的并集必等于A。所以商集A/R是A的一個(gè)劃分。定理2：設(shè)R1和R2是非空集合A上的等價(jià)關(guān)系，則R1=R2當(dāng)且僅當(dāng)A/R1=A/R2

。

(這個(gè)定理顯然成立。)證明:(必要性)因?yàn)锳/R1={[a]R1|a∈A}；A/R2={[a]R2|a∈A}，由于R1=R2，對(duì)任意的

a∈A有

[a]R1={x|x∈A,<a,x>∈R1}={x|x∈A,<a,x>∈R2}=[a]R2即A/R1=A/R2。(充分性)對(duì)任意的<a,b>∈R1

a∈[a]R1∧b∈[a]R1a∈[c]R2∧b∈[c]R2(A/R1=A/R2)<a,b>∈R2

即R1=R2四.由劃分確定等價(jià)關(guān)系例如，X={1,2,3,4},A={{1,2},{3},{4}},A是X的一個(gè)劃分，求X上一個(gè)等價(jià)關(guān)系R，使得X/R=A。顯然R的圖如右圖所示：

R={1,2}2∪{3}2∪{4}2

。一般地A={A1,A2,…,An}是X的一個(gè)劃分，則構(gòu)造一個(gè)X中的等價(jià)關(guān)系R，使得X/R=A。

R=A1∪A2∪,…,∪An其中Ai=Ai×Ai，下面證明R是X中的等價(jià)關(guān)系。等價(jià)關(guān)系集合的劃分A/R？2。1。3。4。2222定理3:

集合X的一個(gè)劃分可以確定X上的一個(gè)等價(jià)關(guān)系。證明：假設(shè)A={A1,A2,...,An}是X的一個(gè)劃分，如下構(gòu)造X上的一個(gè)等價(jià)關(guān)系R:R=A1∪A2∪,…,∪An其中Ai=Ai×Ai，(i=1,2…n).

1)證R自反：任取a∈X，因?yàn)锳是X的劃分，必存在AiA使aAi

,于是<a,a>∈Ai×Ai,又Ai×AiR∴有aRa。

2)證R對(duì)稱：任取a,b∈X,設(shè)aRb，必存在AiA使得<a,b>∈Ai×Ai,于是a,bAi,bRa,R是對(duì)稱的。

3)證R傳遞：任取a,b,c∈X,設(shè)aRb，bRc,必存在AiA使得<a,b>∈Ai×Ai,<b,c>∈Ai×Ai,(不可能有另一個(gè)劃分塊AkA使得<b,c>∈Ak×Ak,因?yàn)槿绻@樣，就使得,既b∈Ai又bAk

,與A是劃分矛盾。)于是a,b,cAi,所以<a,c>∈Ai×Ai，又Ai×AiR∴有aRc

所以R傳遞。最后得R是集合X中的等價(jià)關(guān)系。2222本節(jié)重點(diǎn)：等價(jià)關(guān)系概念、證明。等價(jià)類概念、性質(zhì)。求商集。作業(yè)：第134頁⑵、(3)、⑷

相容關(guān)系是另一種常見關(guān)系，

如朋友關(guān)系、同學(xué)關(guān)系等。這些關(guān)系的共性是自反的、對(duì)稱的。一.定義:給定集合X上的關(guān)系r,若r是自反的、對(duì)稱的,則r是A上相容關(guān)系。顯然：等價(jià)關(guān)系一定是相容關(guān)系，相容關(guān)系不一定是等價(jià)關(guān)系。例子：X是由一些英文單詞構(gòu)成的集合。

X={fly,any,able,key,book,pump,fit},X上關(guān)系r:r={<α,β>|α∈X,β∈X且α與β含有相同字母}3-11相容關(guān)系3-12序關(guān)系次序關(guān)系也是常遇到的重要關(guān)系，例如：數(shù)值的≤、＜、≥、＞關(guān)系；集合的、關(guān)系；圖書館的圖書按書名的字母次序排序；詞典中的字(詞)的排序；計(jì)算機(jī)中文件按文件名排序；程序按語句次序執(zhí)行；…….本節(jié)討論幾種次序關(guān)系。

一.偏序關(guān)系(partialorderrelation)

1.定義：R是A上自反、反對(duì)稱和傳遞的關(guān)系，則稱R是A上的偏序關(guān)系。并稱<A,R>是偏序集。例如數(shù)值的≤、≥關(guān)系和集合的都是偏序關(guān)系。因?yàn)閿?shù)值≤是熟知的偏序關(guān)系，所以用符號(hào)“≤”表示任意偏序關(guān)系，但要注意!!“≤”不一定是“小于或等于”的含義。例1A={1,2,4,6},≤是A中的整除關(guān)系，其關(guān)系圖如右圖，顯然≤是自反、反對(duì)稱和傳遞的，即它是個(gè)偏序關(guān)系。2.x與y是可比較的：<A,≤>是偏序集，x,y∈A，如果要么x≤y,要么y≤x,則稱x與y是可比較的。上例中1,2,4或1,2,6間是可比較的。而4與6間是不可比較的2。。1。。64二.全序(線序、鏈)定義：<A,≤>是偏序集，任何x,y∈A，如果x與y都是可比較的，則稱≤是全序關(guān)系(線序、鏈)。例2B={1,2,4,8},≤表示整除關(guān)系，則≤是全序關(guān)系，如圖：全序關(guān)系一定是偏序關(guān)系，但是偏序不一定是全序。偏序關(guān)系的有向圖，不能直觀地反映出元素之間的次序，所以下面介紹另外一種圖---Hasse圖。通過這個(gè)圖，就能夠清晰地反映出元素間的層次。下面介紹Hasse圖。2。。1。。84三.偏序集的哈斯圖(Hasse圖

)<A,≤>是偏序集，x,y∈Ａ1.元素y蓋住元素x：如果x≤y,且x≠y，且不存在z∈A,使得z≠x∧z≠y∧x≤z∧z≤y，則稱元素y蓋住元素x。元素y蓋住x

x≤y∧x≠y∧z(z∈A∧z≠x∧z≠y∧x≤z∧z≤y)即元素y蓋住元素x不存在z∈A,使得z介于x與y之間。上例中4沒有蓋住1，因?yàn)橹虚g有個(gè)2,1≤2≤4.2.偏序集Hasse圖的畫法：令<A,≤>是偏序集，1.用“?！北硎続中元素。2.如果x≤y,且x≠y，則結(jié)點(diǎn)y要畫在結(jié)點(diǎn)x的上方。3.如果x≤y,且y蓋住x，x與y之間連一直線。4.一般先從最下層結(jié)點(diǎn)(全是射出的邊與之相連(不考慮環(huán)))，逐層向上畫，直到最上層結(jié)點(diǎn)(全是射入的邊與之相連)。(采用抓兩頭，帶中間的方法

)例如，前邊兩個(gè)例子：它們的Ｈasse圖分別如下：可見右圖，是全序，它的Ｈasse圖是一條直線，所以全序也叫線序，或鏈。是從它的Hasse圖得名。

2。。1。。642。。1。。84１。２。４。６。１。２。４。８。練習(xí)：C={1,2,3,6,12,24,36},≤是C、D上整除關(guān)系：<Ｃ,≤>的Hasse圖：以及A={a,b,c}<P(A),>的Hasse圖：下面作練習(xí)：教材第146頁(7)四.偏序集中的重要元素設(shè)<A,≤>是偏序集，B是A的非空子集。一.極小元與極大元

y是B的極小元y(y∈B∧x(x∈B∧x≠y∧x≤y))

(在B中沒有比y更小的元素了，y就是極小元)y是B的極大元y(y∈B∧x(x∈B∧x≠y∧y≤x))

(在B中沒有比y更大的元素了，y就是極大元)舉例，給定<A,≤>的Hasse圖如圖所示：從Hasse圖找極小(大)元：子集中處在最下(上)層的元素是極小(大)元。６。１。３。12。２。24。36。{6,12,24}{2,3}{1,2,3}A2,31612,32,32424,36子集B極小元極大元二.最小元與最大元

y是B的最小元y(y∈B∧x(x∈By≤x))

(最小元y是B中元素，該元素比B中所有元素都小)y是B的最大元y(y∈B∧x(x∈Bx≤y))

(最大元y是B中元素，該元素比B中所有元素都大)舉例，給定<A,≤>的Hasse圖如圖所示：從Hasse圖找最小(大)元：子集中如果只有唯一的極小(大)元，則這個(gè)極小(大)元，就是最小(大)元。否則就沒有最小(大)元。下面介紹最小(大)元的唯一定理。６。１。３。12。２。24。36。{6,12,24}{2,3}{1,2,3}A無161無無24無子集B最小元最大元定理1：<A,≤>是偏序集，B是A的非空子集，如果B有最小元(最大元)，則最小元(最大元)是唯一的。證明：假設(shè)B有兩個(gè)最小元a、b,則因?yàn)閍是最小元，b∈B，根據(jù)最小元定義，有a≤b;類似地，因?yàn)閎是最小元，a∈B，根據(jù)最小元定義，有b≤a。因?yàn)椤苡蟹磳?duì)稱性，所以有a=b。

同理可證最大元的唯一性。小結(jié)：<A,≤>是偏序集，B是A的非空子集，則⑴B的極小(大)元總是存在的，就是子集中處在最下(上)層的元素是極小(大)元。⑵B的最小元(最大元)有時(shí)可能不存在，只有有唯一的極小(大)元，則這個(gè)極小(大)元就是最小(大)元。否則就沒有最小(大)元。三.上界與下界(UpperBoundandLowerBound)y是B的上界y(y∈A∧x(x∈Bx≤y))

(上界y是A中元素，該元素比B中所有元素都大)y是B的下界y(y∈A∧x(x∈By≤x))

(下界y是A中元素，該元素比B中所有元素都小)舉例，給定<A,≤>的Hasse圖如圖所示：從Hasse圖找上(下)界：注意是在A中找?。?。１。３。12。２。24。36。上界下界

16,12,24,361246,2,3,11無子集B{2,3}{1,2,3}{6,12,24}A6,12,24,36四.最小上界(上確界)和最大下界(下確界)(LeastUpperBoundandGreatestLowerBound)定義：

y是B的上界，并且對(duì)B的所有上界x,都有y≤x,則稱y是B的最小