《離散數(shù)學(xué)及其應(yīng)用》第7章 特殊關(guān)系

離散數(shù)學(xué)第三篇二元關(guān)系第7章特殊關(guān)系7.0內(nèi)容提要集合的概念1集合的表示方法2偏序關(guān)系3良序關(guān)系4等價關(guān)系1擬序關(guān)系2全序關(guān)系47.1本章學(xué)習(xí)要求重點掌握一般掌握了解11幾個特殊關(guān)系的概念2等價和偏序關(guān)系的證明3等價類和商集的計算48個特殊元31擬序、全序和良序關(guān)系的相關(guān)性質(zhì)。21擬序、全序和良序關(guān)系的定義；2擬序與偏序關(guān)的聯(lián)系3擬序、全序、良序的聯(lián)系。判定下列關(guān)系具有哪些性質(zhì)1、在全體中國人所組成的集合上定義的“同姓”關(guān)系；2、對任何非空集合A，A上的全關(guān)系；3、三角形的“相似關(guān)系”、“全等關(guān)系”；4、直線的“平行關(guān)系”；5、“朋友”關(guān)系；解：1，2，3都具有自反性，對稱性和傳遞性；4具有反自反，對稱和傳遞性，不具有自反性；5具有自反和對稱性，不具有傳遞性。等價關(guān)系7.2等價關(guān)系定義7.2.1設(shè)R是定義在非空集合A上的關(guān)系，如果R是自反的、對稱的、傳遞的，則稱R為A上的等價關(guān)系。由定義7.2.1知：（1）關(guān)系R是等價關(guān)系當(dāng)且僅當(dāng)R同時具備自反性、對稱性和傳遞性；（2）關(guān)系R不是等價關(guān)系當(dāng)且僅當(dāng)R不具備自反性或?qū)ΨQ性或傳遞性。例7.2.1

1.冪集上定義的“”關(guān)系；

2.整數(shù)集上定義的“<”關(guān)系；

3.全體中國人所組成的集合上定義的“同性別”關(guān)系。不具有對稱性不具有對稱性，自反性是等價關(guān)系判定下列關(guān)系是否是等價關(guān)系?例7.2.2在時鐘集合A＝{1,…,24}上定義整除關(guān)系：R＝{<x,y>|{x,yA)∧((x-y)被12所整除)｝。

（1）寫出R中的所有元素；

（2）畫出R的關(guān)系圖；

（3）證明R是一個等價關(guān)系。例7.2.2解（2）此等價關(guān)系的關(guān)系圖：（1）R={<1,1>,…,<24,24>,<1,13>,<13,1>,<2,14>,<14,2>,…,<11,23>,<23,11>,<12,24>,<24,12>}}113圖7.2.1……21431512241、對x∈A，有(x-x)被12所整除，所以<x,x>∈R，即R是自反的。2、對x,y∈A,若<x,y>∈R,有(x-y)被12整除，則(y-x)＝-(x-y)被12整除,所以,<y,x>∈R,即R是對稱的。3、對x,y,z∈A,若<x,y>∈R且<y,z>∈R,有(x-y)被12所整除且(y-z)被12所整除,所以(x-z)＝(x-y)＋(y-z)被12所整除,所以,<x,z>∈R,即R是傳遞的.由1,2,3知R是等價關(guān)系?！隼?.2.2解(續(xù))從例7.2.2可以看出關(guān)系R將集合A分成了如下的12個子集：

{1,13},{2,14},{3,15},{4,16},{5,17},{6,18},{7,19},{8,20},{9,21},{10,22},{11,23},{12,24}。這12個A的子集具有如下特點：1、在同一個子集中的元素之間都有關(guān)系R；2、不同子集的元素之間無關(guān)系R。例7.2.3設(shè)n為正整數(shù)，考慮整數(shù)集合Z上的整除關(guān)系如下：R={<x,y>|{x,y∈Z}∧(n|(x-y))}證明R是一個等價關(guān)系。

證明

(1)對xZ，有n|(x-x)，所以<x,x>R，即R是自反的。(2)對x,yZ，若<x,y>R，即n|(x-y)，所以m|(y-x)，所以，<y,x>R，即R是對稱的。(3)對x,y,zZ，若<x,y>R且<y,z>R，有n|(x-y)且n|(y-z)，所以由(x-z)=(x-y)+(y-z)得n|(x-z)，所以，<x,z>R，即R是傳遞的。由(1)、(2)、(3)知，R是Z上的等價關(guān)系。■以n為模的同余關(guān)系(CongruenceRelation)上述R稱為Z上以n為模的同余關(guān)系，記xRy為x＝y(tǒng)(modn)稱為同余式。如用resn(x)表示x除以n的余數(shù)，則x＝y(tǒng)(modn)resn(x)＝resn(y)。此時，R將Z分成了如下n個子集：{…,-3n,-2n,-n,0,n,2n,3n,…}{…,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1,…}{…,-3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2,…}

…{…,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,…}說明同樣地，這n個Z的子集具有如下特點：

1、在同一個子集中的元素之間都有關(guān)系R；

2、不同子集的元素之間沒有關(guān)系R；

3、不同子集的交集是空集；

4、所有這些子集的并集就構(gòu)成集合Z。稱為集合Z的一個劃分7.2.2集合的劃分定義7.2.2給定非空集合A，設(shè)有集合S={S1,S2,S3...Sm}.如果滿足SiA且Si≠Φ，i＝1,2,...,m；Si∩Sj＝Φ，i≠j，i,j＝1,2,...,m；

。則集合S稱作集合A的一個劃分(Partition)，而S1,S2,...Sm叫做這個劃分的塊(Block)或類(Class)。例7.2.4試給出非空集合A上2個不同的劃分解（1）在A中設(shè)定一個非空子集A1，令A(yù)2=A-A1，則根據(jù)集合劃分的定義，{A1,A2}就構(gòu)成了集合A的一個劃分，見圖(a)；（2）在A中設(shè)定兩個不相交非空子集A1和A2，令A(yù)3=A-(A1∪A2)，則根據(jù)集合劃分的定義，{A1,A2,A3}就構(gòu)成了集合A的一個劃分，見圖(b)。AAA1A1A2(a)(b)例7.2.5設(shè)設(shè)A={0,1,2,4,5,8,9}，1、寫出R是A上的以4為模的同余關(guān)系R的所有元素；2、求分別與元素1,2,3,4有關(guān)系R的所有元素所作成的集合。解：1、R={<0,0>,<1,1>,<2,2>,<4,4>,<5,5>,<8,8>,<9,9>,<0,4>,<4,0>,<4,8>,<8,4>,<0,8>,<8,0>,<1,5>,<5,1>,<1,9>,<9,1>,<5,9>,<9,5>}.

顯然，R是A的一個等價關(guān)系。集合{1,5,9}稱為元素1關(guān)于等價關(guān)系R的等價類，記為[1]R，即[1]R={1,5,9};例7.2.5解2、與元素1有關(guān)系R的所有元素所作成的集合{1,5,9};

與元素2有關(guān)系R的所有元素所作成的集合{2};與元素4有關(guān)系R的所有元素所作成的集合{0,4,8}.[2]R={2},[4]R={0,4,8}.7.2.3等價類與商集定義7.2.3

設(shè)R是非空集合A上的等價關(guān)系，對任意x∈A，稱集合

[x]R＝{y|y∈A∧<x,y>∈R}為x關(guān)于R的等價類(equivalenceclass)，或叫作由x生成的一個R等價類，其中x稱為[x]R的生成元(或叫代表元，或典型元)(generator)。由定義7.2.3可以看出：（1）等價類產(chǎn)生的前提是A上的關(guān)系R必須是等價關(guān)系；（2）A中所有與x有關(guān)系R的元素y構(gòu)成了[x]R；（3）A中任意一個元素一定對應(yīng)一個由它生成的等價類；（4）R具有自反性意味著對x∈A，[x]R≠Φ；（5）R具有對稱性意味著對任意x，y∈A，若有y∈[x]R，則一定有x∈[y]R。例7.2.5(續(xù))設(shè)A={0,1,2,4,5,8,10}，R是A上的以4為模的同余關(guān)系。求（1）R的所有等價類；（2）畫出R的關(guān)系圖。解:(1)[1]R＝{1,5,9}＝[5]R＝[9]R；[2]R={2}；[4]R＝{0,4,8}=[0]R＝[8]R。圖7.2.32159159定理7.2.1設(shè)R是非空集合A上的等價關(guān)系，則有下面的結(jié)論成立：1)對xA，[x]R≠Φ；2)對x,y∈A，

a)如果y∈[x]R，則有[x]R=[y]R，

b)如果y[x]R，則有[x]R∩[y]R＝Φ。3)

＝A；定理7.2.1的證明2)

對任意x,y∈A，若y∈[x]R，則<x,y>∈R。

a)

對z∈[x]R，則有：<x,z>∈R，又<x,y>∈R，由R的對稱性有：<y,x>∈R，由R的傳遞性有：

<y,z>∈R。所以z∈[y]R，即：[x]R[y]R。

證明：1）對任意x∈A，因為R是等價關(guān)系，所以R是自反的，因此<x,x>∈R，即x∈[x]R，故[x]R≠Φ。

b)對z∈[y]R，則有：<y,z>∈R，又<x,y>∈R，由R的傳遞性有：<x,z>∈R。所以，z∈[x]R，即：

[y]R[x]R。所以，由a)和b)知：[x]R＝[y]R。3）因為對任意x∈A，[x]R

A，所以

A。定理7.2.1的證明（續(xù)）對任意x∈A，因R是自反的，所以<x,x>∈R，即x∈[x]R。所以x∈，即A

。故=A。(2)

若y[x]R，設(shè)[x]R∩[y]R≠Φ,則存在z∈[x]R∩[y}R。即z∈[x]R，z∈[y]R，則有：<x,z>∈R，<y,z>∈R，由R的對稱性，<z,y>∈R。由R的傳遞性有：<x,y>∈R，即y∈[x]R，矛盾。所以[x]R∩[y]R＝Φ?！錾碳x7.2.4

設(shè)R是非空集合A上的等價關(guān)系，由R確定的一切等價類的集合，稱為集合A上關(guān)于R的商集(QuotientSet)，記為A/R，即

A/R＝{[x]R|(x∈A)}例7.2.6

設(shè)集合A={0,1,2,4,5,8,10}，R為A上以4為模的同余關(guān)系。求A/R。解根據(jù)例7.2.5，商集A/R={[0]R,[1]R,[2]R}={{0,4,8},{1,5，9},{2}}。例7.2.7設(shè)集合A={1,2,3,4,5,8}，R為A上以3為模的同余關(guān)系。求A/R。解根據(jù)例7.2.3知，A上以3為模的同余關(guān)系R是等價關(guān)系。因為[1]R={1,4}=[4]R,[2]R=[5]R=[8]R={2,5,8},[3]R={3}，所以根據(jù)商集的定義，A/R={[1]R,[2]R,[3]R}={{1,4},{2,5,8},{3}}。計算商集A/R的通用過程：（1）任選A中一個元素a，計算[a]R；（2）如果[a]R≠A，任選一個元素b∈A-[a]R，計算[b]R；（3）如果[a]R∪[b]R≠A，任選一個元素c∈A-[a]R-[b]R，計算[c]R；以此類推，直到A中所有元素都包含在計算出的等價類中。7.2.4等價關(guān)系與劃分定理7.2.2

設(shè)R是非空集合A上的等價關(guān)系，則A對R的商集A/R是A的一個劃分，稱之為由R所導(dǎo)出的等價劃分。定理7.2.3給定集合A的一個劃分П={A1,A2,…,An},則由該劃分確定的關(guān)系R=(A1×A1)∪(A2×A2)∪…∪(An×An)是A上的等價關(guān)系。我們稱該關(guān)系R為由劃分П所導(dǎo)出的等價關(guān)系。定理7.2.3的證明證明

1）R是自反的對x∈A，因為П(A)是A的一個劃分，所以存在一個劃分塊Ai∈П(A)，使得x∈Ai，顯然x和x同屬于П(A)的一個劃分塊Ai，故<x,x>∈R，所以R是自反的。

2)R是對稱的

對x,y∈A，若<x,y>∈R，則x和y同屬于П(A)的一個劃分塊Ai，因此y和x同屬于П(A)的一個劃分塊Ai，故<y,x>∈R，所以R是對稱的。定理7.2.3的證明(續(xù))3)R是傳遞的對x,y,z∈A，若<x,y>∈R，<y,z>∈R，則x和y同屬于П(A)的一個劃分塊Ai，y和z同屬于П(A)的一個劃分塊Aj，因此y∈Ai∩Aj，由于不同的劃分塊交為空，所以Ai=Aj，因此x和z同屬于П(A)的一個劃分塊Ai，即<x,z>∈R，所以R是傳遞的。綜上，由1)、2)、3)知，R是A上的等價關(guān)系。

說明：集合A上的等價關(guān)系和A的劃分是一一對應(yīng)的。例7.2.8解只有1個劃分塊的劃分為S1，見圖(a)；具有2個劃分塊的劃分為S2、S3和S4，見圖(b)、(c)和(d)，具有3個劃分塊的劃分為S5，見圖(e)。設(shè)A={1,2,3}，求A上所有的等價關(guān)系及其對應(yīng)的商集。231231231231231

(a)(b)(c)(d)(e)例7.2.8(續(xù)）假設(shè)由Si導(dǎo)出的對應(yīng)等價關(guān)系為Ri，i=1,2,3,4,5，則有R1=S1×S1=A×A，A/R1={{1,2,3}}；R2={1,2}×{1,2}∪{3}×{3}={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>},A/R2={{1,2},{3}}；

R3={1,3}×{1,3}∪{2}×{2}={<1,1>,<1,3>,<2,2>,<3,1>,<3,3>},

A/R3={{1,3},{2}}；例7.2.8(續(xù)）R4={2,3}×{2,3}∪{1}×{1}={<1,1>,<2,2>,<2,3>,<3,2>,<3,3>}，A/R4={{1},{2,3}}；R5={1}×{1}∪{2}×{2}∪{3}×{3}={<1,1>,<2,2>,<3,3>}=IA，A/R5={{1},{2},{3}}。

例7.2.9設(shè)R是A上的自反和傳遞關(guān)系，S也是A上的關(guān)系，且滿足：<x,y>∈S(<x,y>∈R∧<y,x>∈R)(7.2.2)證明S是A上的等價關(guān)系。證明（1）S是自反的：對任意a∈A，因R是自反的，所以<a,a>∈R，由<a,a>∈R并且<a,a>∈R和(7.2.2)得<a,a>∈S，即S是自反的。例7.2.9(續(xù))（2）S是對稱的：對a,b∈A，若<a,b>∈S，則由(7.2.2)得<a,b>∈R并且<b,a>∈R，即有<b,a>∈R并且<a,b>∈R，所以有<b,a>∈S，即S是對稱的。例7.2.9(續(xù))（3）S是傳遞的：對a,b,c∈A，若<a,b>∈S，<b,c>∈S，則由(7.2.2)得<a,b>∈R且<b,a>∈R和<b,c>∈R且<c,b>∈R。因為R是傳遞的，所以有<a,c>∈R和<c,a>∈R。從而，<a,c>∈S，即S是傳遞的。由(1),(2)和(3)知，S是A上的一個等價關(guān)系。例7.2.10設(shè)R是集合A上的一個關(guān)系.對a,b,c∈A，若<a,b>∈R并且<a,c>∈R，則有<b,c>∈R，則R稱為A上的循環(huán)關(guān)系。試證明R是A上的一個等價關(guān)系的充要條件是R是循環(huán)關(guān)系和自反關(guān)系。例7.2.10證明“”若R是等價關(guān)系。1)、顯然R是自反的。2)、對任意a,b,c∈A，若<a,b>∈R,<a,c>∈R，則由R是對稱的，有<b,a>∈R并且<a,c>∈R，由R是傳遞的，所以，<b,c>∈R。即R是循環(huán)的關(guān)系。

由1)，2)知R是自反的和循環(huán)的。“”

若R是自反的和循環(huán)的。1)、顯然R是自反性的；2)、對任意a,b∈A,若<a,b>∈R,則由R是自反的,有<a,a>∈R，因R是循環(huán)的，所以，<a,b>∈R且<a,a>∈R<b,a>∈R，即R是對稱的。例7.2.10證明(續(xù))3)、對任意a,b,c∈A，若<a,b>∈R，<b,c>∈R，則由R對稱的，有<b,a>∈R并且<b,c>∈R；由R是循環(huán)的，所以<b,a>∈R且<b,c>∈R<a,c>∈R，即R是傳遞的。由1)、2)、3)知R是A上的一個等價關(guān)系?！隼?.2.10證明(續(xù))7.2.6等價關(guān)系的應(yīng)用例7.2.11在圖7.2.5中，點i和j之間有路當(dāng)且僅當(dāng)從結(jié)點i通過圖中的邊能夠到達結(jié)點j。規(guī)定對任意結(jié)點i，i和i之間一定有路。定義R如下：<i,j>∈Ri和j之間有路。試說明該關(guān)系R是否可以給定結(jié)點集A={1,2,3,4,5,6,7,8}一個劃分？如果能，請給出具體的劃分。圖7.2.575683124例7.2.11解（1）由于規(guī)定任意結(jié)點i與他自身之間一定有路，因此<i,i>∈R，即R具有自反性；（2）若<i,j>∈R，則兩個結(jié)點i和j之間存在路，當(dāng)然也存在j和i之間的路，所以<j,i>∈R，即R具有對稱性；（3）若<i,j>∈R,<j,k>∈R，則結(jié)點i和j之間有路，j和k之間也有路，從而i到k之間存在經(jīng)過j的路，即有<i,k>∈R，因此得到R具有傳遞性。由(1)、(2)和(3)知，R是等價關(guān)系。例7.2.11解(續(xù))于是所有不同的等價類為：[1]R={1,2,3,4}，[5]R={5,6,7}，[8]R={8}。根據(jù)定理7.2.2知，A/R={[1]R,[5]R,[8]R}={{1,2,3,4},{5,6,7},{8}}就是A的一個劃分。例7.2.12信息檢索系統(tǒng)中的信息有{離散數(shù)學(xué)，高等數(shù)學(xué)，計算機操作系統(tǒng)，計算機網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)，編譯原理，軟件工程，計算機組成原理}。試給該信息檢索系統(tǒng)指定三種不同的劃分。解設(shè)A={離散數(shù)學(xué)，高等數(shù)學(xué)，計算機操作系統(tǒng)，計算機網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)，編譯原理，軟件工程，計算機組成原理}，則例7.2.12解（續(xù)）劃分1：含關(guān)鍵詞離散數(shù)學(xué)，則A={{離散數(shù)學(xué)},{高等數(shù)學(xué),計算機操作系統(tǒng),計算機網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),編譯原理,軟件工程,計算機組成原理}}；劃分2：含關(guān)鍵詞數(shù)學(xué)，則A={{離散數(shù)學(xué),高等數(shù)學(xué)},{計算機操作系統(tǒng),計算機網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),編譯原理,軟件工程,計算機組成原理}}；劃分3：含關(guān)鍵詞計算機，則A={{離散數(shù)學(xué)，數(shù)據(jù)結(jié)構(gòu),編譯原理,軟件工程,高等數(shù)學(xué)},{計算機操作系統(tǒng),計算機網(wǎng)絡(luò),計算機組成原理}}?？偨Y(jié)1、熟記等價關(guān)系的定義；2、利用等價關(guān)系的定義證明一個關(guān)系是等價關(guān)系；3、給定A上的等價關(guān)系R，會求所有的等價類和商集A/R；并求出對應(yīng)的集合的劃分；4、給定集合A上的劃分，會求對應(yīng)的等價類。判定下列關(guān)系具有哪些性質(zhì)1、對任何非空集合A，A上的恒等關(guān)系；2、多邊形的“相似關(guān)系”、“全等關(guān)系”；3、集合A的冪集P(A)上定義的“包含關(guān)系”；4、集合A的冪集P(A)上定義的“真包含關(guān)系”。解：1，2都具有自反性，對稱性和傳遞性，是等價關(guān)系；

3具有自反性，反對稱性和傳遞性；

4具有反自反性，反對稱性，傳遞性。偏序關(guān)系擬序關(guān)系7.3次序關(guān)系拍攝一張室內(nèi)閃光燈照片，需要完成如下任務(wù)：1、打開鏡頭蓋；2、照相機調(diào)焦；3、打開閃光燈；4、按下快門按鈕。

這些任務(wù)中有的必須在其他任務(wù)之前完成。例如，任務(wù)1必須在任務(wù)2之前完成，任務(wù)2，3必須在任務(wù)4之前完成，即任務(wù)之間存在“先后”關(guān)系，即次序關(guān)系。7.3.1擬序關(guān)系定義7.3.1設(shè)R是非空集合A上的關(guān)系，如果R是反自反和傳遞的，則稱R是A上的擬序關(guān)系(Quasi-OrderRelation)，簡稱擬序，記為“＜”，讀作“小于”，并將“<a,b>∈＜”記為“a＜b”。序偶<A,＜>稱為擬序集(Quasi-OrderSet)。由定義7.3.1知：（1）R是擬序關(guān)系R同時具有反自反性和傳遞性；（2）R不是擬序關(guān)系R不具有反自反性或者傳遞性；（3）擬序“＜”的逆關(guān)系“＜-1”也是擬序，用“＞”表示，讀作“大于”。例7.3.1設(shè)R是集合A上的擬序關(guān)系，則R是反對稱的。證明假設(shè)R不是反對稱的關(guān)系，則必存在x,y∈A，且x≠y，滿足<x,y>∈R并且<y,x>∈R。因為R是A上的擬序關(guān)系，所以R具有傳遞性，從而有<x,x>∈R。這與R是反自反的矛盾，從而假設(shè)錯誤，即R一定是反對稱的。例7.3.2判斷下列關(guān)系是否為擬序關(guān)系（1）集合A的冪集P(A)上定義的“”；（2）實數(shù)集R上定義的“小于”關(guān)系(＜)；解（1）集合A的冪集P(A)上定義的“”具有反自反性和傳遞性，所以<P(A),>是擬序集。（2）實數(shù)集合R上定義的“小于”關(guān)系(＜)具有反自反性和傳遞性，所以<R,＜>是擬序集。7.3.2偏序關(guān)系定義7.3.2

設(shè)R是非空集合A上的關(guān)系，如果R是自反的、反對稱的和傳遞的，則稱R是A上的偏序關(guān)系(PartialOrderRelation)，簡稱偏序，記為“≤”，讀作“小于等于”，并將“<a,b>∈≤”記為a≤b。序偶<A,≤>稱為偏序集(PartialOrderSet)。由定義7.3.2知（1）R是偏序關(guān)系R同時具有自反性、反對稱性和傳遞性；（2）R不是偏序關(guān)系R不具備自反性或反對稱性或傳遞性；（3）偏序“≤”的逆關(guān)系“≤-1”也是一個偏序，我們用“≥”表示，讀作“大于等于”；（4）(“≤”-IA)為A上的擬序關(guān)系，(“＜”∪IA)為A上的偏序關(guān)系。試判斷下列關(guān)系是否為偏序關(guān)系集合A的冪集P(A)上的包含關(guān)系“”；實數(shù)集合R上的小于等于關(guān)系“≤”；自然數(shù)集合N上的模m同余關(guān)系；自然數(shù)集合N上的整除關(guān)系“|”；ALGOL或PL/I等都是塊結(jié)構(gòu)語言，設(shè)B={b1,b2,…,bn}是這種語言的一個程序中的塊的集合。對所有i和j，定義關(guān)系“≤”如下：bi≤bj當(dāng)且僅當(dāng)bi被bj所包含。例7.3.3例7.3.3解根據(jù)偏序關(guān)系的定義知，

(1)，(2)，(4)，(5)所對應(yīng)的關(guān)系同時具有自反性，反對稱性和傳遞性，所以都是偏序集；(3)所對應(yīng)的關(guān)系不具有反對稱性，所以它不是偏序關(guān)系；例7.3.4設(shè)X是所有4位二進制串的集合，在X上定義關(guān)系R：如果s1的某個長度為2的子串等于s2的某個長度為2的子串，則<s1,s2>∈R，例如因為0111和1010中都含有子串01，所以<0111，1010

>∈R。試判斷R是否是一個偏序關(guān)系。例7.3.4解對任意的s,t∈X，如果<s,t>∈R，則s的某個長度為2的子串等于t的某個長度為2的子串，也可以說t的某個長度為2的子串等于s的某個長度為2的子串，即有<t,s>∈R，從而R是對稱的。根據(jù)對稱性，存在0111，1010∈X，有<0111，1010

>∈R且<0111，1010

>∈R，但是0111≠1010，從而R不是反對稱的，從而R不是偏序關(guān)系。例7.3.5考慮任務(wù)集T，它包含了拍攝一張室內(nèi)閃光照片必須按順序完成的任務(wù)：1、打開鏡頭蓋；2、照相機調(diào)焦；3、打開閃光燈；4、按下快門按鈕。在T上定義關(guān)系R如下：<i,j>∈R如果i=j或者任務(wù)i必須在任務(wù)j之前完成。試判斷R是T上的偏序關(guān)系并畫出它的關(guān)系圖。例7.3.5解根據(jù)R的定義，有R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}。根據(jù)自反、反對稱和傳遞的定義知，關(guān)系R具有自反性，對稱性和傳遞性。從而R是偏序關(guān)系，其關(guān)系圖如右圖所示。12342哈斯圖（1）用小圓圈或點表示A中的元素，省掉關(guān)系圖中所有的環(huán)；（因自反性)（2）對任意x,y∈A，若x＜y，則將x畫在y的下方，可省掉關(guān)系圖中所有邊的箭頭；（因反對稱性）（3）對任意x,y∈A(x≠y)，若x≤y，且x與y之間不存在z∈A，使得x≤z,z≤y，則x與y之間用一條線相連，否則無線相連。（因傳遞性）例7.3.6畫出例7.3.5中關(guān)系R的哈斯圖。解例7.3.5中關(guān)系R的哈斯圖如下圖所示。12例7.3.7設(shè)A={2,3,6,12,24,36}，“≤”是A上的整除關(guān)系R，畫出其一般的關(guān)系圖和哈斯圖。解由題意可得R={<2,2>,<2,6>,<2,12>,<2,24>,<2,36>,<3,3>,<3,6>,<3,12>,<3,24>,<3,36>,<6,6>,<6,12>,<6,24>,<6,36>,<12,12>,<12,24>,<12,36>,<24,24>,<36,36>}，從而得出該偏序集<A,≤>的一般關(guān)系圖和哈斯圖如下：例7.3.7（續(xù)）關(guān)系圖哈斯圖2361236242361236243特殊元素定義7.3.3設(shè)<A,≤>是偏序集，B是A的任何一個子集，若存在元素b∈B，使得對x∈B，（1）都有x≤b,則稱b為B的最大元素,簡稱最大元（2）都有b≤x,則稱b為B的最小元素，簡稱最小元（3）滿足b≤xx=b，則稱b為B的極大元素,簡稱極大元；（4）滿足x≤bx=b，則稱b為B的極小元素,簡稱極小元。定義7.3.3可以符號化為：注意（1）B的最大元、最小元、極大元和極小元如果存在，一定在B中；（2）b是B的最大元B中所有的元素都比b?。?/p>

b是B的最小元B中所有的元素都比b大；b是B的極大元B中沒有比b大的元素；

b是B的極小元B中沒有比b小的元素。例7.3.8在例7.3.7中，設(shè)B1={6,12}，B2={2,3}，B3={24,36}，B4={2,3,6,12}是集合A的子集，試求出B1,B2,B3和B4的最大元，最小元，極大元和極小元。解

A的子集合B1,B2,B3和B4的最大元，最小元，極大元和極小元見下表。集合最大元最小元極大元極小元B1126126B2無無2,32,3B3無無24,3624,36B412無122,3定義7.3.4設(shè)<A,≤>是偏序集，B是A的任何一個子集。若存在元素a∈A，使得（1）對任意x∈B，都有x≤a，則稱a為B的上界；（2）對任意x∈B，都有a≤x，則稱a為B的下界；（3）若元素a′∈A是B的上界，元素a∈A是B的任何一個上界，若均有a′≤a，則稱a′為B的最小上界或上確界。記a′=SupB；（4）若元素a′∈A是B的下界，元素a∈A是B的任何一個下界，若均有a≤a′，則稱a′為B的最大下界或下確界。記a′=InfB。由定義7.3.4知

（1）子集合B的上、下界和上、下確界可在集合A中尋找；（2）一個子集合B的上、下界不一定存在，如果存在，可以不唯一的；（3）一個子集合B的上、下確界不一定存在，如果存在，一定唯一；（4）一個子集合B有上(下)確界，一定有上(下)界，反之不然。例7.3.9在例7.3.7中，設(shè)B1={6,12}，B2={2,3}是集合A的子集，試求出B1，B2的上界、下界、上確界和下確界。解集合B1、B2的各種特殊元素見下表。集合上界下界上確界下確界B112,24,362,3,6126B26,12,24,36無6無例7.3.10A={x1,x2,x3,x4}，A上定義偏序集<A,≤>的哈斯圖如圖7.3.4所示。求B={x1,x2}和C={x3,x4}上界、下界、上確界和下確界。解B、C的各種特殊元見下表。x1圖7.3.4x3x2x4集合上界下界上確界下確界B無x3,x4無無Cx1,x2無無無例7.3.11設(shè)集合A={a,b,c,d,e,f,g,h}，對應(yīng)的哈斯圖見圖7.3.5。令B1={a,b}，B2={c,d,e}。求出B1，B2的最大元、最小元、極大元、極小元、上界、下界、上確界、下確界。解B1和B2的各種特殊元素見下表。eabcdfgh圖7.3.5集合最大元最小元極大元極小元上界下界上確界下確界B1無無a,ba,bc,d,e,f,g,h無c無B2無cd,echc,a,bhc結(jié)論：(設(shè)<A,≤>是一偏序集，B是A的子集)（1）若b是B的最大元，則b一定是B的極大元，上界和上確界，反之，則不然；（2）若b是B的最小元，則b一定是B的極小元，下界和下確界，反之，則不然。定理7.3.1設(shè)<A,≤>是一偏序集，B是A的子集。則：（1）若b是B的最大元b是B的極大元、上界、上確界；（2）若b是B的最小元b是B的極小元、下界、下確界；（3）若a是B的上確界，且a∈Ba是B的最大元；（4）若a是B的下確界，且a∈Ba是B的最小元。定理7.3.2設(shè)<A,≤>是一偏序集，B是A的子集。則：（1）若B存在最大元，則B的最大元是惟一的；（2）若B存在最小元，則B的最小元是惟一的；（3）b是B的最大元b是B的惟一極大元；（4）b是B的最小元b是B的惟一極小元；（5）若B存在上確界，則B的上確界是惟一的；（6）若B存在下確界，則B的下確界是惟一的。例7.3.12設(shè)集合X={x1,x2,x3,x4,x5}上的偏序關(guān)系如下圖所示，求X的最大元、最小元、極大元、極小元。求子集X1={x2,x3,x4}，X2={x3,x4,x5}，X3={x1,x3,x5}的上界、下界、最小上界、最大下界、最大元、最小元、極大元和極小元。x1x2x3x5x4

例7.3.12解X1，X2和X3的各種特殊元見下表。集合最大元最小元極大元極小元上界下界上確界下確界X1無x4x2,x3x4x1x4x1x4X2x3無x3x4,x5x1,x3無x3無X3x1x5x1x5x1x5x1x57.3.3全序關(guān)系定義7.3.5設(shè)<A,≤>是一個偏序關(guān)系，若對任意x,y∈A，總有x≤y或y≤x，二者必居其一，則稱關(guān)系“≤”為全序關(guān)系(TotalOrderRelation)，簡稱全序，或者線序關(guān)系，簡稱線序。稱<A,≤>為全序集(TotalOrderSet)，或者線序集，或者鏈(Chain)。從定義7.3.5可以看出：全序關(guān)系是偏序關(guān)系，反之則不然。例7.3.13試判斷下列關(guān)系是否為全序關(guān)系，如果是，請畫出其哈斯圖。（1）設(shè)集合A={a,b,c}，其上的關(guān)系“≤”={<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<a,c>}（2）實數(shù)集R上定義的小于等于關(guān)系“≤”；（3）實數(shù)集R上定義的小于關(guān)系“<”；（4）集合A的冪集P(A)上定義的包含關(guān)系“”。例7.3.13解（1）<A,≤>是全序集，其哈斯圖見圖(a)；（2）<R,≤>是全序集，其哈斯圖是數(shù)軸，見圖(b),其中x,y,z∈R；（3）不是全序關(guān)系；（4）當(dāng)|A|<2時，P(A)上定義的“”是全序關(guān)系，<P(A),>是全序集，其哈斯圖見圖(c)；當(dāng)|A|≥2，則<P(A),>不是全序集。例7.3.13解（續(xù)）ΦΦabcxya{a}(a)(b)(c)7.3.4良序關(guān)系定義7.3.6

設(shè)<A,≤>是一偏序集，若A的任何一個非空子集都有最小元素，則稱“≤”為良序關(guān)系，簡稱良序，此時<A,≤>稱為良序集。從定義7.3.6可以看出：（1）R是良序關(guān)系R是偏序關(guān)系和A的任何非空子集都有最小元；（2）良序關(guān)系一定是偏序關(guān)系，反之則不然；（3）良序關(guān)系一定是全序關(guān)系，反之則不然。例7.3.14試判斷例7.3.13的(1)和(2)是否為良序關(guān)系。解（1）<A,≤>是良序集；（2）<R,≤>是不良序集。注：1、“≤”是良序關(guān)系“≤”是全序關(guān)系“≤”是偏序關(guān)系；2、有限全序集一定是良序集。7.3.6次序關(guān)系的應(yīng)用例7.3.15計算機科學(xué)中常用的字典排序如下：設(shè)∑是一有限的字母表?！粕系淖帜附M成的字母串叫∑上的字；∑*是包含空字“ε”的所有字組成的集合，建立∑*上的字典次序關(guān)系L：設(shè)x=x1x2…xn,y=y1y2…ym，其中x