離散數(shù)學(xué)任課教師：楊春10一月2023數(shù)學(xué)科學(xué)學(xué)院2023/1/10第7章特殊關(guān)系良序關(guān)系5偏序關(guān)系3等價關(guān)系1擬序關(guān)系2全序關(guān)系4內(nèi)容提要2023/1/107.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解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)系。2023/1/107.2等價關(guān)系定義7.2.1設(shè)R是定義在非空集合A上的關(guān)系，如果R是自反的、對稱的、傳遞的，則稱R為A上的等價關(guān)系。2023/1/10例7.2.1不具有對稱性不具有對稱性，自反性是等價關(guān)系判定下列關(guān)系是否是等價關(guān)系?冪集上定義的“”關(guān)系；整數(shù)集上定義的“＜”關(guān)系；全體中國人所組成的集合上定義的“同性別”關(guān)系。2023/1/10例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)系。2023/1/10以n為模的同余關(guān)系上述R稱為Z上以n為模的同余關(guān)系(CongruenceRelation)，記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,…}2023/1/107.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)。2023/1/107.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)。2023/1/10例7.2.5(續(xù))設(shè)A={0,1,2,4,5,8,9}，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。（2）21590482023/1/10定理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；2023/1/10證明1）對任意x∈A，因為R是等價關(guān)系，所以R是自反的，因此<x,x>∈R，即x∈[x]R，故[x]R≠Φ。2023/1/10證明2)對任意x,y∈A，a)若y∈[x]R，則<x,y>∈R。對任意z∈[x]R，則有：<x,z>∈R，又<x,y>∈R，由R的對稱性有：<y,x>∈R，由R的傳遞性有：<y,z>∈R。所以z∈[y]R，即：[x]R[y]R。對任意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。b)若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＝Φ。2023/1/10因為對任意x∈A，[x]RA，所以A。對任意x∈A，因R是自反的，所以<x,x>∈R，即x∈[x]R。所以x∈，即A。故=A。證明3)2023/1/10商集定義7.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,9}，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}}。2023/1/10計算商集A/R的通用過程任選A中一個元素a，計算[a]R；如果[a]R≠A，任選一個元素b∈A-[a]R，計算[b]R；如果[a]R∪[b]R≠A，任選一個元素c∈A-[a]R-[b]R，計算[c]R；以此類推，直到A中所有元素都包含在計算出的等價類中。2023/1/107.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)系。2023/1/10定理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是對稱的。2023/1/10定理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)的。2023/1/10例7.2.8設(shè)A={1,2,3}，求A上所有的等價關(guān)系及其對應(yīng)的商集。解只有1個劃分塊的劃分為S1，見圖(a)；具有2個劃分塊的劃分為S2、S3和S4，見圖(b)、(c)和(d)，具有3個劃分塊的劃分為S5，見圖(e)。231231231231231(a)(b)(c)(d)(e)2023/1/10例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}}；2023/1/10例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}}。2023/1/10例7.2.9設(shè)R是A上的自反和傳遞關(guān)系，S也是A上的關(guān)系，且滿足：對任意x,y∈A，<x,y>∈S(<x,y>∈R∧<y,x>∈R)證明S是A上的等價關(guān)系。證明（1）S是自反的：對任意a∈A，因R是自反的，所以<a,a>∈R，由<a,a>∈R并且<a,a>∈R和S的定義得<a,a>∈S，即S是自反的。2023/1/10例7.2.9(續(xù))（2）S是對稱的：對任意a,b∈A，若<a,b>∈S，則由S的定義得<a,b>∈R并且<b,a>∈R，即有<b,a>∈R并且<a,b>∈R，所以有<b,a>∈S，即S是對稱的。2023/1/10例7.2.9(續(xù))（3）S是傳遞的：對任意a,b,c∈A，若<a,b>∈S，<b,c>∈S，則由S的定義得<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)系。2023/1/10例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是A上的循環(huán)關(guān)系和自反關(guān)系。2023/1/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是A上的循環(huán)的關(guān)系。由1)，2)知R是自反的和循環(huán)的。2023/1/10若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是對稱的。3)對任意a,b,c∈A，若<a,b>∈R，<b,c>∈