離散數學第三章

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

、三角形相似∽和全等關系≌，…..一.等價關系1.定義:設R是A上關系,若R是自反的、對稱的和傳遞的，則稱R是A中的等價關系。若a,bA，且aRb，則稱a與b等價。例子，集合A={1,2,3,4,5,6,7},R是A上的模3同余關系，即R={<x,y>|x-y可被3整除(或x/3與y/3的余數相同)}即<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.等價關系的有向圖1)等價關系的有向圖:從關系圖可看出，R是自反、對稱、傳遞的關系，所以R是等價關系。

等價關系R的有向圖由若干個獨立子圖(R圖的一部分)構成的，每個獨立子圖都是完全關系圖。上述關系R圖就是由三個獨立的完全圖構成的。

下面給出八個關系如圖所示，根據等價關系有向圖的特點，判斷哪些是等價關系，

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

2)完全關系(全域關系A×A)圖，下面分別是當A中只有1、2、3個元素時的完全關系圖。A={1,2,3}下面是A中關系：1。2。。1。2。。331。2。。1。2。。1。2。。1。2。。3333R2R1R5R61。2。。1。2。。33R3R4R7R8思考題：A={1,2,3},可構造多少個A中不同的等價關系？可以根據等價關系有向圖的特點來考慮。如果等價關系R中有

a)三個獨立子圖的情形，則()個等價關系。

b)二個獨立子圖的情形，則()個等價關系。

c)一個獨立子圖的情形，則()個等價關系。一共有()個不同的R中的等價關系。二.等價類

我們經常用等價關系對集合進行劃分，得到的劃分塊稱之為等價類。1.定義：R是A上的等價關系，a∈A,由a確定的集合[a]R={x|x∈A∧<a,x>∈R}稱集合[a]R為由a形成的R等價類。簡稱a等價類。可見x∈[a]R<a,x>∈R上例中，A={1,2,3,4,5,6,7},R是A上的模3同余關系，[1]R={1,4,7}=[4]R=[7]R----余數為1的等價類

[2]R={2,5}=[5]R----余數為2的等價類

[3]R={3,6}=[6]R----余數為0的等價類思考題：此例為什么只有三個等價類？2.由等價關系圖求等價類：R圖中每個獨立子圖上的結點，構成一個等價類。不同的等價類個數=獨立子圖個數。上述三個等價關系各有幾個等價類？說出對應的各個等價類。從上述模3同余關系例子中，可以歸納出等價類的性質：任何兩個等價類要么相等，要么不相交；那么在什么情況下相等？那么在什么情況下不相交？1。2。。3R21。2。。3R1。R3。。1233.等價類性質

R是A上等價關系，任意a,b,c∈A

⑴同一個等價類中的元素，彼此有等價關系R。

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

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

b∈[a]R,又因為bRb,所以b∈[b]R，所以b∈[a]R∩[b]R，產生矛盾。⑶

[a]R=[b]R當且僅當<a,b>∈R。證明:(充分性)若<a,b>∈R，則任何x∈[a]R，有<a,x>∈R，由對稱性得<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，由對稱性得<a,b>∈R.⑷.A中任何元素a,a必屬于且僅屬于一個等價類。證明：A中任何元素a,由于有aRa,所以a∈[a]R

，如果a∈[b]R

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

任意兩個等價類

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

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

。

(因為要么<a,b>∈R，要么<a,b>R。)⑹R的所有等價類構成的集合是A的一個劃分。

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

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

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

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

X={1,2,3},X上關系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上的等價關系R，決定了A的一個劃分，該劃分就是商集A/R.證明：由等價類性質可得：

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

。

(這個定理顯然成立。)證明:(必要性)因為A/R1={[a]R1|a∈A}；A/R2={[a]R2|a∈A}，由于R1=R2，對任意的

a∈A有

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

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

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

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

。一般地A={A1,A2,…,An}是X的一個劃分，則構造一個X中的等價關系R，使得X/R=A。

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

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

1)證R自反：任取a∈X，因為A是X的劃分，必存在AiA使aAi

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

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

3)證R傳遞：任取a,b,c∈X,設aRb，bRc,必存在AiA使得<a,b>∈Ai×Ai,<b,c>∈Ai×Ai,(不可能有另一個劃分塊AkA使得<b,c>∈Ak×Ak,因為如果這樣，就使得,既b∈Ai又bAk

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

所以R傳遞。最后得R是集合X中的等價關系。2222本節重點：等價關系概念、證明。等價類概念、性質。求商集。作業：第134頁⑵、(3)、⑷

相容關系是另一種常見關系，

如朋友關系、同學關系等。這些關系的共性是自反的、對稱的。一.定義:給定集合X上的關系r,若r是自反的、對稱的,則r是A上相容關系。顯然：等價關系一定是相容關系，相容關系不一定是等價關系。例子：X是由一些英文單詞構成的集合。

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

一.偏序關系(partialorderrelation)

1.定義：R是A上自反、反對稱和傳遞的關系，則稱R是A上的偏序關系。并稱<A,R>是偏序集。例如數值的≤、≥關系和集合的都是偏序關系。因為數值≤是熟知的偏序關系，所以用符號“≤”表示任意偏序關系，但要注意!!“≤”不一定是“小于或等于”的含義。例1A={1,2,4,6},≤是A中的整除關系，其關系圖如右圖，顯然≤是自反、反對稱和傳遞的，即它是個偏序關系。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都是可比較的，則稱≤是全序關系(線序、鏈)。例2B={1,2,4,8},≤表示整除關系，則≤是全序關系，如圖：全序關系一定是偏序關系，但是偏序不一定是全序。偏序關系的有向圖，不能直觀地反映出元素之間的次序，所以下面介紹另外一種圖---Hasse圖。通過這個圖，就能夠清晰地反映出元素間的層次。下面介紹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，因為中間有個2,1≤2≤4.2.偏序集Hasse圖的畫法：令<A,≤>是偏序集，1.用“。”表示A中元素。2.如果x≤y,且x≠y，則結點y要畫在結點x的上方。3.如果x≤y,且y蓋住x，x與y之間連一直線。4.一般先從最下層結點(全是射出的邊與之相連(不考慮環))，逐層向上畫，直到最上層結點(全是射入的邊與之相連)。(采用抓兩頭，帶中間的方法

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

2。。1。。642。。1。。84１。２。４。６。１。２。４。８。練習：C={1,2,3,6,12,24,36},≤是C、D上整除關系：<Ｃ,≤>的Hasse圖：以及A={a,b,c}<P(A),>的Hasse圖：下面作練習：教材第146頁(7)四.偏序集中的重要元素設<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圖找最小(大)元：子集中如果只有唯一的極小(大)元，則這個極小(大)元，就是最小(大)元。否則就沒有最小(大)元。下面介紹最小(大)元的唯一定理。６。１。３。12。２。24。36。{6,12,24}{2,3}{1,2,3}A無161無無24無子集B最小元最大元定理1：<A,≤>是偏序集，B是A的非空子集，如果B有最小元(最大元)，則最小元(最大元)是唯一的。證明：假設B有兩個最小元a、b,則因為a是最小元，b∈B，根據最小元定義，有a≤b;類似地，因為b是最小元，a∈B，根據最小元定義，有b≤a。因為≤有反對稱性，所以有a=b。

同理可證最大元的唯一性。小結：<A,≤>是偏序集，B是A的非空子集，則⑴B的極小(大)元總是存在的，就是子集中處在最下(上)層的元素是極小(大)元。⑵B的最小元(最大元)有時可能不存在，只有有唯一的極小(大)元，則這個極小(大)元就是最小(大)元。否則就沒有最小(大)元。三.上界與下界(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的上界，并且對B的所有上界x,都有y≤x,則稱y是B的最小