第四章二元關系

1、1/574.1 4.1 二元關系及其表示法二元關系及其表示法4.1.1 4.1.1 序偶與笛卡爾積序偶與笛卡爾積定義定義4.14.1：由兩個元素由兩個元素x x和和y y按一定的次序組成的二按一定的次序組成的二元組稱為有序對或序偶元組稱為有序對或序偶(Ordered)(Ordered)，記作，記作，其中其中x x是它的第一元素，是它的第一元素，y y是它的第二元素。是它的第二元素。性質性質4.14.1：(1)(1)： = = 當且僅當當且僅當x=yx=y；(2)(2)： = =當且僅當當且僅當x=u, y=v;x=u, y=v;例如：平面上的坐標例如：平面上的坐標，x, y Rx, y R；

2、等都是序偶。等都是序偶。2/57定義定義4.24.2：設設A A，B B是兩個集合，稱集合是兩個集合，稱集合 為集合為集合A A與與B B的的笛卡爾積笛卡爾積(Descartes Product)(Descartes Product)。例：設例：設A=1,2A=1,2；B=a, bB=a, b則則A A B=B=，；B B A=A=，b, 1，。性質性質4.24.2：(1). | A (1). | A B |=|A|B |=|A|B|(A, B|B|(A, B為有限為有限集合集合) )； (2). (2). ； (3). (3). 不適合交換律，即不適合交換律，即A AB BB BA(A(除非

3、除非A A，B= B= 或或A=B)A=B)； (4). (4). 不適合結合律，不適合結合律，(A(AB)B)C AC A(B(BC)(C)(除除非非 ) )； (5). (5). 對對和和運算滿足分配律，運算滿足分配律，|,ByAxyxBA AA， CBA 3/57證明：證明：(6). (6). ，且當，且當 或或 時，逆命題成立。時，逆命題成立。 A);(CA)(BAC)(BC),(AB)(AC)(BA),(CA)(BAC)(BC),(AB)(AC)(BAA)()(,)(,)(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyxDCBADBCA

4、 BA BA4/57定義定義4.34.3：一個有序一個有序n(n2)n(n2)元組是一個有序對，元組是一個有序對，它的第一個元素為有序的它的第一個元素為有序的n-1n-1元組元組 ，第二個元素為，第二個元素為 ，記為，記為 即：即： ； 當且僅當當且僅當n n維空間中的點維空間中的點M M的坐標的坐標 為有序的為有序的n n元組元組 。定義定義4.44.4：設設 為為n n個集合個集合(n 2)(n 2)，稱集，稱集合合 為為n n維卡氏積或維卡氏積或n n階笛卡爾積，記作階笛卡爾積，記作 ， 當當 時簡記為時簡記為 。121,naaanannaaaa,121nnnaaaaaaa,21121n

5、nbbbaaa,2121nibaii, 2 , 1,),(21nxxxnxxx,21nAAA,21|,221121nnnAxAxAxxxxnAAA21nAAA21nA5/574.1.2 4.1.2 二元關系二元關系定義定義4.54.5：若集合若集合F F中的全體元素為有序的中的全體元素為有序的n(n2)n(n2)元組，則稱元組，則稱F F為為n n元關系，特別地，當元關系，特別地，當n=2n=2時，稱時，稱F F為二元關系，簡稱關系。為二元關系，簡稱關系。對于二元關系對于二元關系F F，若，若 ，常記作，常記作 ，反之，反之 ；規(guī)定；規(guī)定 為為n n元空關系，也是二元空關系，簡元空關系，也是二

6、元空關系，簡稱空關系。稱空關系。定義定義4.64.6：設設A A，B B為兩集合，為兩集合，A AB B的集合子集的集合子集R R稱稱為為A A到到B B的二元關系，特別地，當?shù)亩P系，特別地，當A=BA=B時，稱時，稱R R為為A A上上的二元關系。的二元關系。例：例：A=a, bA=a, b，B=cB=c，則，則A AB B的子集有的子集有 ，, , ，F(xiàn)yx ,xFyyFx 6/57A A到到B B上的全部二元關系；而上的全部二元關系；而 ，為為B B上的二上的二元關系。元關系。一般來說，若一般來說，若|A|=m|A|=m，|B|=n|B|=n，A A到到B B上的二元關系共上的二元關

7、系共有有 個，個，A A上的共有上的共有 個二元關系；個二元關系；特殊的二元關系：特殊的二元關系： (1). (1). 空關系；空關系； (2). (2). 全域關系：全域關系： ； (3). (3). 恒等關系：恒等關系： 。 mn222mAAAyAxyxEA|,|,AxxxIA7/57定義定義4.74.7：設設R R為二元關系，則為二元關系，則 (1). (1). 為為R R的定義域；的定義域； (2). (2). 為為R R的值域；的值域； (3). (3). 為為R R的域。的域。一般地，若一般地，若R R是是A A到到B B上的二元關系，則有上的二元關系，則有 。 例例4-14-1：

8、設設A=1,2,3,4,5,6A=1,2,3,4,5,6，B=a, b, c, dB=a, b, c, d，則則R=R=，6, c，那么，那么domRdomR=2,3,4,6=2,3,4,6，ranRranR=a, b, c=a, b, c。)(|xRyyxdomR)(|xRyxyranRranRdomRfldRBranRAdomR,8/574.1.2 4.1.2 關系的表示關系的表示1. 1. 集合表示法集合表示法 由于關系也是一種特殊的集合，所以可以用集合由于關系也是一種特殊的集合，所以可以用集合的兩種基本的表示方法的兩種基本的表示方法( (枚舉法，描述法枚舉法，描述法) )來表示來表示關

9、系；如：設關系；如：設A=2A=2，B=3B=3，則，則A A到到B B上的有關系上的有關系R=R=；集合；集合N N上的上的“小于等于小于等于”關系：關系：R=|(x, y) N(x y) R=|(x, y) N(x y) 。2. 2. 關系圖法關系圖法定義定義4.84.8：設集合設集合A= A= 到到B= B= 上的二元關系上的二元關系R R，以集合，以集合A A，B B中的元素為頂點，在中的元素為頂點，在圖中用圖中用“”表示頂點，若表示頂點，若 則可自頂點則可自頂點 向向頂點頂點 引有向邊引有向邊 ，其箭頭指向，其箭頭指向 ，用這種，用這種方法畫出的圖稱為關系圖方法畫出的圖稱為關系圖(G

10、raph of Relation)(Graph of Relation)。nxxx,21nyyy,21jiRyxixjy),(jiyxjy9/57例例4-24-2：求集合求集合A=1,2,3,4A=1,2,3,4的恒等關系，空關系，的恒等關系，空關系，全關系和小于關系的關系圖。全關系和小于關系的關系圖。3. 3. 關系矩陣關系矩陣定義定義4.94.9：設設 ，那么，那么R R的關系矩陣的關系矩陣 為一為一m mn n矩陣，它的第矩陣，它的第i i，j j分量分量 只取只取0 0或或1 1，且，且,2121nmbbbBaaaABARRMijrjijiijbRaRbar當且僅當當且僅當0110/5

11、71.1.關系的交，并，補，差運算關系的交，并，補，差運算定義定義4.104.10：設設R R和和S S為為A A到到B B的二元關系，其并，交的二元關系，其并，交，補，差運算定義如下：，補，差運算定義如下：例例4-34-3：設設A=1,2,3,4A=1,2,3,4，若，若R=|(x-y)/2R=|(x-y)/2是是整數(shù)，整數(shù)，x, y Ax, y A，S=|(x-y)/3S=|(x-y)/3是正整數(shù)，是正整數(shù)，x, y Ax, y A，求，求RSRS，RSRS，S-RS-R，RR，R SR S。解：解：R=R=，|,|,|,|,xRyyxRxSyxRyyxSRxSyxRyyxSRxSyxRy

12、yxSR11/57S=S=， RS= RS=，；RS= RS= ； S-R= S= S-R= S=；R= AR= AA-R=A-R=，；R S=(RS)-(RS)= RS.R S=(RS)-(RS)= RS.關系的補運算是對全關系而言的；關系的補運算是對全關系而言的；關系的并，交，差，補的矩陣可用如下方法求?。宏P系的并，交，差，補的矩陣可用如下方法求?。?SSSRSRSRSRSRSRSRMMMMMMMMMMMM,12/572.2.關系的逆運算關系的逆運算由于關系是序偶的集合，除了集合的一般運算外，由于關系是序偶的集合，除了集合的一般運算外，還有一些特有的運算。還有一些特有的運算。定義定義4.1

13、14.11：設設R R是是A A到到B B的關系，的關系，R R的逆關系或逆是的逆關系或逆是B B到到A A的關系，記為的關系，記為 ，定義為：，定義為：顯然對任意顯然對任意 ，有，有 ； 為為R R的關系矩陣，則的關系矩陣，則 . .例：例： ；A=a, b, c, dA=a, b, c, d，B=1,2,3B=1,2,3，R=R=， =，2, b，。1R|,1xRyxyRByAx ,xyRxRy1RMRRMM1 11,AAII1R13/57定理定理4.14.1：設設R R和和S S都是都是A A到到B B上的二元關系，那么上的二元關系，那么.)( ,).6(;,).5(;).(4(;)(

14、,)( ,).(3(;).(2(;).(1 (1111111111111111111ABBAdomRranRranRdomRSRSRSRSRSRSRSRSRRRRR 14/573.3.關系的復合運算關系的復合運算定義定義4.124.12：設設R R，S S為二元關系，則為二元關系，則R R與與S S的復合關的復合關系系 定義為：定義為： ，其中，其中“ ”“ ”為復合運算，為復合運算， 也記為也記為 。例：設例：設R R表示父子關系，則表示父子關系，則 表示祖孫關系。表示祖孫關系。例例4-44-4：設集合設集合A=0,1,2,3,4A=0,1,2,3,4，R R，S S均為均為A A上的二上的

15、二元關系，且元關系，且R=|R=|x+yx+y=4=4=，S= =|y-S= =|y-x=1=x=1=，；求；求一般地，一般地，SR)(|,tSyxRttyxSRRR2R2RR)(SRR,S)(R,SSRRRSSRRSSR15/57定理定理4.24.2：設設F F，G G，H H為任意二元關系，則為任意二元關系，則定理定理4.34.3：設設R R為為A A上的關系，則上的關系，則定理定理4.44.4：設設F F，G G，H H為任意二元關系，則為任意二元關系，則111).(2(),().(1 (FGGFHGFHGF RRRIIRAA).2( ,).1 (.).(4(,)().3(,).(2(,

16、)().1 (FHFGFHGHFGFHGFFHFGFHGHFGFHGF16/574.4.關系的冪運算關系的冪運算定義定義4.134.13：設設R R是集合是集合A A上的二元關系，則上的二元關系，則R R的的n n次次冪冪 定義為：定義為：例例4-54-5：設設A=0,1,2,3,4A=0,1,2,3,4，R=R=，。則則 =，； = =，； = =，=nRRRRAxxxIRnnA10).2(,|,).1 (2R3R4R2R17/57定理定理4.54.5：設設R R為為A A上的二元關系，上的二元關系，m m，n n為自然數(shù)，為自然數(shù)，則則證證(4)(4)：若：若n=0n=0時，則有時，則有

17、假設假設n=kn=k時，有時，有 ，則，則n=k+1n=k+1時，有時，有 命題成立。命題成立。定理定理4.64.6：設集合設集合A A的基數(shù)為的基數(shù)為n n，R R是是A A上的二元關系上的二元關系，那么存在自然數(shù)，那么存在自然數(shù)i i，j j使得使得證明：我們知道，當證明：我們知道，當|A|=n|A|=n時，時，A A上的二元關系共計上的二元關系共計 個，令個，令k= k= ，因此在，因此在 這這k+1k+1個關個關11).1 (mnmnnnRRRRRRR.)().(4( ,).(3( ,).2(11nnmnnmnmnmRRRRRRR AAnAIIRIR1101)()( ,)(11)()(

18、kkRR111111111)()()()()()(kkkkkRRRRRRRR)20(2njijiRR22n22n1210,kRRRR18/57系中，至少有兩個是相同的系中，至少有兩個是相同的( (鴿巢原理鴿巢原理) )，即有，即有定理定理4.74.7：設設A A是有限集合，且是有限集合，且|A|=n|A|=n，R R是是A A上的二上的二元關系，則元關系，則證明：顯然證明：顯然 ，下面證：，下面證： 。而而 ，為此，只要證明對任意的，為此，只要證明對任意的knkn，有，有 即可。對任意的即可。對任意的 ，則由，則由“”“”的定義知：存在的定義知：存在 ，使得：，使得：.),20(,2jinRR

19、jiji使iniiiRR11 iiiniRR11iniiiRR11 iniiniiiRRR111inikRR1 kRba ,Aaaak121,),(,012110baaaRaaRaaRaakkk令19/57由于由于|A|=n|A|=n，所以由鴿巢原理；，所以由鴿巢原理；k+1k+1個元素個元素 中至少有兩個元素相同，不妨設為中至少有兩個元素相同，不妨設為 ，則，則可可在在 中刪去中刪去 后仍有后仍有由關系的復合運算得：由關系的復合運算得： ，其中，其中 ，此時：若，此時：若 ，則，則 ；若；若 ，則重復上述做法，最終總能找到，則重復上述做法，最終總能找到 ，使使得得 ，即有，即有 ，由此，由此

20、有有 ，由，由k k的任意性的任意性 ， kaa,0)(jiaajiRaaRaaRaakk,12110RaaRaaRaajjiiii,1211RaaRaaRaaRaaRaakkjjii,1112110,0kkRaaba)(ijkknk iniRba1,nk nk kkRaaba ,0iniRba1,inikRR1 iniiiRR11 iniiiRR11 20/575 5：集合在關系下的像：集合在關系下的像定義定義4.144.14：設設R R為二元關系，為二元關系，A A是集合是集合(1)(1)：R R在在A A上的限制上的限制 定義為：定義為： (2)(2)：A A在在R R下的像下的像RAR

21、A定義為定義為RA=ran( )RA=ran( )。例：例：R=R=，則：，則： R Ra=a=，；R Ra= ;a= ; R Ra, a=Ra, a=R； Ra=b,aRa=b,a；Ra,a=b,a,a,aRa,a=b,a,a,a；|,AxxRyyxARARAR,1aaaR;11aaRaR 21/57定理定理4.84.8：設設F F為關系，為關系，A A，B B為集合，則為集合，則例例4-64-6：設設 ，A=0,1,2A=0,1,2，B=0,-1,-2B=0,-1,-2。(1)(1)求求RABRAB和和RARBRARB；(2)(2)求求RA-RBRA-RB和和RA-BRA-B。解解(1)(

22、1)： RAB=R0=0 RAB=R0=0； RARB RARB =0,1,20,1,2 =0,1,2=0,1,20,1,2 =0,1,2； (2) (2)： RA-RB =0,1,2- 0,1,2= RA-RB =0,1,2- 0,1,2= ； RA-B=R1,2=1,2 RA-B=R1,2=1,2,)().4( ,)().3(,)().2( ,)().1 (BFAFBAFBFAFBAFBFAFBAFBFAFBAF|,|,xyZyxyxR 22/57我們在研究關系的性質時，可以假定關系是某一非我們在研究關系的性質時，可以假定關系是某一非空集合上的二元關系，這一假設不失一般性。因空集合上的二元

23、關系，這一假設不失一般性。因此任一此任一A A到到B B上的關系上的關系R R，即，即 ，而，而 ，所以關系，所以關系R R總可以看成是總可以看成是A AB B 上的關系，它與原關系上的關系，它與原關系R R具有完全相同的序具有完全相同的序偶，對它的討論代替對偶，對它的討論代替對R R的討論無損于問題的本質的討論無損于問題的本質1.1.關系的性質關系的性質定義定義4.154.15：設設R R是是A A上的二元關系，即上的二元關系，即 ，則，則(1)(1)若若 ，則稱，則稱R R是自反的是自反的(Reflexive)(Reflexive)；(2)(2)若若 ，則稱，則稱R R是反自反的是反自反的

24、( (IrreflexiveIrreflexive) )；BAR)()(BABABAAAR),(RxxAxx),(RxxAxx23/57(3)(3)若若 ，則稱，則稱R R是對稱的是對稱的(Symmetric)(Symmetric)(4)(4)若若 ，則稱，則稱R R是是反對稱的反對稱的( (AntisymmetricAntisymmetric) )(5)(5)若若 ，則稱，則稱R R是傳遞的是傳遞的(Transitive)(Transitive)例例4-74-7：設設A=a, b, c, dA=a, b, c, d(1):R=(1):R=，c, c，是自反的；是自反的；S=S=，是反自反的；

25、是反自反的；T=,c, T=,c,既不是自反的也不是反自反的；既不是自反的也不是反自反的；),(yRxxRyAyxyx),(yxyRxxRyAyxyx),(xRzyRzxRyAzyxzyx24/57在關系圖上：關系在關系圖上：關系R R是自反的，當且僅當其關系圖是自反的，當且僅當其關系圖中的每個節(jié)點都有環(huán)，關系中的每個節(jié)點都有環(huán)，關系R R是反自反的，當且僅是反自反的，當且僅當其關系圖中的每個節(jié)點上都無環(huán)；當其關系圖中的每個節(jié)點上都無環(huán)；在關系矩陣上：關系在關系矩陣上：關系R R是自反的，當且僅當其關系是自反的，當且僅當其關系矩陣的主對角線上全為矩陣的主對角線上全為1 1，關系，關系R R是反

26、自反的，當是反自反的，當且僅當其關系矩陣的主對角線上全為且僅當其關系矩陣的主對角線上全為0 0。例例4-84-8：設設A=a, b, cA=a, b, c稱的。既是對稱的，也是反對反對稱的；既不是對稱的，也不是是反對稱的；是對稱的；,)4(,) 3(,)2(,) 1 (4321ccaaRaccabaaaRcaaaRaccaaaR25/57關系圖上：關系關系圖上：關系R R是對稱的當且僅當其關系圖中，是對稱的當且僅當其關系圖中，任何一對節(jié)點之間，要么有方向相反的兩條邊，任何一對節(jié)點之間，要么有方向相反的兩條邊，要么無任何邊；關系要么無任何邊；關系R R是反對稱的當且僅當其關系是反對稱的當且僅當其

27、關系圖中，任何一對節(jié)點之間，至多有一條邊；圖中，任何一對節(jié)點之間，至多有一條邊；關系矩陣上：關系關系矩陣上：關系R R是對稱的當且僅當其關系矩陣是對稱的當且僅當其關系矩陣是對稱矩陣；關系是對稱矩陣；關系R R是反對稱的當且僅當其關系矩是反對稱的當且僅當其關系矩陣為反對稱矩陣。陣為反對稱矩陣。例例4-94-9：設設A=a, b, c, dA=a, b, c, d不是傳遞的。不是傳遞的；是傳遞的；是傳遞的；,)4(,)3(,)2(,) 1 (4321dccacbbaRcbbaaaRbaRcacbbaaaR26/57關系圖上：關系關系圖上：關系R R是傳遞的當且僅當其關系圖中，是傳遞的當且僅當其關系

28、圖中，任何三個節(jié)點任何三個節(jié)點x, y, z(x, y, z(可相同可相同) )之間，若從之間，若從x x到到y(tǒng) y，y y到到z z均有一條邊，則從均有一條邊，則從x x到到z z一定有一條邊存在；一定有一條邊存在；關系矩陣上：關系關系矩陣上：關系R R是傳遞當且僅當其關系矩陣中是傳遞當且僅當其關系矩陣中，對任意，對任意2.2.利用集合運算來判斷關系的性質利用集合運算來判斷關系的性質定理定理4.94.9：設設R R是集合是集合A A上的二元關系，則上的二元關系，則。則必有若1, 1, 1, 1 ,ikjkijrrrnkji.)5(;)4(;)3(;)2(;) 1 (11RRRRIRRRRRR

29、IRRRIRAAA 傳遞的是反對稱的是對稱的是反自反的是自反的27/573.3.關系性質的保守性關系性質的保守性定理定理4.104.10：設設R R，S S是是A A上的二元關系，則上的二元關系，則例例4-104-10：設設R=R=， S=S=，是定義在是定義在A=a, b, A=a, b, cc上的兩個二元關系。上的兩個二元關系。傳遞。傳遞反對稱；反對稱對稱；對稱反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR,)5(,)4(,) 3(,)2(,) 1 (1111128/57顯然顯然R R，S S是反自反的，反對稱的，傳遞的，則是反自反的

30、，反對稱的，傳遞的，則 也是反自反的，反對稱的，傳遞也是反自反的，反對稱的，傳遞的；的； 也具備上述的一切性質；也具備上述的一切性質；(3)RS=, ,c, (3)RS=, ,b,僅是對稱的和反自反的；僅是對稱的和反自反的； 則是傳遞的則是傳遞的和對稱的。和對稱的。111,).1 (SRSR SR)2(,)4(abbabbaaSR29/57關系的限制與擴充：對于任何一個具備某種性質關系的限制與擴充：對于任何一個具備某種性質( (如如自反、對稱、傳遞自反、對稱、傳遞) )的關系來說，在理論研究與應的關系來說，在理論研究與應用上都十分重要，但遺憾的是，許多我們要研究用上都十分重要，但遺憾的是，許多

31、我們要研究的關系并不具有我們所希望的良好性質。因此，的關系并不具有我們所希望的良好性質。因此，我們往往要在給定的關系中刪去一些或添加一些我們往往要在給定的關系中刪去一些或添加一些元素，以改變原有關系的性質，即所謂的關系的元素，以改變原有關系的性質，即所謂的關系的限制與擴充。限制與擴充。關系的閉包則是關系的擴充。關系的閉包則是關系的擴充。定義定義4.164.16：設設R R是定義在是定義在A A上的二元關系，若存在上的二元關系，若存在滿足滿足：(1) (1) 是自反的是自反的( (對稱的或傳遞的對稱的或傳遞的) )；(2).(2). ；(3)(3)對對R R的任何擴充的任何擴充 是自反的是自反的

32、( (對稱的對稱的或傳遞的或傳遞的) )，則，則 。一般將。一般將R R的自反、對稱、的自反、對稱、傳遞閉包記作傳遞閉包記作r(R)r(R)，s(R)s(R)，t(R)t(R)。RRRRR RR 30/57例：定義在例：定義在N N上的上的“ ”關系的自反閉包關系的自反閉包r(R)r(R)為為“”“”，對稱閉包，對稱閉包s(R)s(R)為為“”“”，傳遞閉包，傳遞閉包t(R)t(R)為為“ ”；定義在定義在N N上的上的“= =”關系的自反閉包關系的自反閉包r(R)r(R)為為“= =”，對稱，對稱閉包閉包s(R)s(R)為為“= =”，傳遞閉包，傳遞閉包t(R)t(R)為為“= =”。例例4

33、-114-11：設集合設集合A=a, b, cA=a, b, c，R=R=，是定義在是定義在A A上的二元關系，求上的二元關系，求r(R)r(R)，s(R)s(R)，t(R)t(R)并畫出并畫出R R，r(R)r(R)，s(R)s(R)，t(R)t(R)的關系圖，關系矩的關系圖，關系矩陣。陣。解：解： r(R)=,; r(R)=,;s(R)=,;s(R)=,;t(R)=,;t(R)=,;31/57利用關系圖，關系矩陣求閉包的方法：利用關系圖，關系矩陣求閉包的方法：(1).(1).求一個關系的自反閉包，即將圖中所有的無環(huán)求一個關系的自反閉包，即將圖中所有的無環(huán)節(jié)點加上環(huán)，矩陣中的對角線上的值全定

34、義為節(jié)點加上環(huán)，矩陣中的對角線上的值全定義為1 1；(2).(2).求一個關系的對稱閉包，則在圖中，任何一對求一個關系的對稱閉包，則在圖中，任何一對節(jié)點之間，若僅存在一條邊，則加一條反方向的節(jié)點之間，若僅存在一條邊，則加一條反方向的邊；矩陣中則為：若邊；矩陣中則為：若 ，則令，則令 ，即，即 ；(3).(3).求一個關系的傳遞閉包，則在圖中，對任意節(jié)求一個關系的傳遞閉包，則在圖中，對任意節(jié)點點a a，b b，c c，若，若a a到到b b有一條邊，同時有一條邊，同時b b到到c c也有一條也有一條邊，則從邊，則從a a到到c c必增加一條邊必增加一條邊( (當當a a到到c c無邊時無邊時)

35、)，在，在矩陣中，若矩陣中，若 。)( 1jirij) 1( 1jijirr若1)(RRRsMMM）（若則令111, 1ikikjkijrrrr32/57定理定理4.114.11：設設R R是是A A上的二元關系，則上的二元關系，則定理定理4.124.12：設設R R是集合是集合A A上的關系，則上的關系，則定理定理4.144.14：設設R R是集合是集合A A上的關系，則上的關系，則iniiiARRtnARRtRRRsIRRRRr1110)(|,)(: )3(,)(: )2( ,)(: ) 1 (則若.)(: )3(,)(: )2(,)(: ) 1 (RRtRRRsRRRrR是傳遞的是對稱的

36、是自反的.)(: ) 3(,)(),(: )2(,)(),(: ) 1 (傳遞傳遞對稱對稱自反自反RrRRtRrRRtRsR33/57定義定義4.174.17：(1)(1)集合集合A A上的關系上的關系R R的自反對稱閉包定的自反對稱閉包定義為義為rsrs(R)=r(s(R); (2)(R)=r(s(R); (2)集合集合A A上的關系上的關系R R的自反的自反傳遞閉包定義為傳遞閉包定義為rtrt(R)=r(t(R); (3)(R)=r(t(R); (3)集合集合A A上的關上的關系系R R的對稱傳遞閉包定義為的對稱傳遞閉包定義為stst(R)=s(t(R);(R)=s(t(R);類似的類似的

37、，可有，可有srsr(R)(R)，trtr(R)(R)，tsts(R)(R)。定理定理4.154.15：設設R R是集合是集合A A上的關系，則上的關系，則)()().3(),()().2(),()().1 (RtsRstRtrRrtRsrRrs34/574.5.14.5.1：集合和劃分：集合和劃分定義定義4.184.18：設設A A是一個非空集合，是一個非空集合， 是是A A的任意的任意n n個非空子集，如果個非空子集，如果 滿足：滿足： 則稱集合則稱集合 為集合為集合A A的一個劃分的一個劃分(Partition)(Partition)，而，而 叫做這個劃分的塊或叫做這個劃分的塊或類。類。

38、例如：例如：(1) (1) 構成集合構成集合U U的一個劃分；的一個劃分；(2) (2) 構成了構成了U U上的一個劃上的一個劃分。分。nAAA,21nAAA,21AAnjijiAAiniji 1).2( ;, 1,).1 (,)(21nAAAAnAAA,21,AA,21212121AAAAAAAA35/574.5.24.5.2：等價關系：等價關系定義定義4.194.19：設設R R為非空集合為非空集合A A上的關系，如果上的關系，如果R R是自是自反的，對稱的，傳遞的，則稱反的，對稱的，傳遞的，則稱R R為為A A上的等價關系上的等價關系(Equivalent Relation)(Equiv

39、alent Relation)。若。若 ，稱，稱x x等價等價于于y,y,記作記作xyxy。例：例：(1)(1)一群人，同姓，同年齡，同性別都是等價關一群人，同姓，同年齡，同性別都是等價關系，朋友，同學關系不是等價關系：不傳遞；系，朋友，同學關系不是等價關系：不傳遞；(2)(2) 都是都是A A上的等價關系；上的等價關系；(3)(3)三角形三角形“相似相似”，“全等全等”都是等價關系；都是等價關系；(4)(4)冪集上定義的冪集上定義的 關系，整數(shù)集上定義的關系，整數(shù)集上定義的不是不是等價關系，不對稱。等價關系，不對稱。Ryx ,AAIA,36/57例例4-124-12：設設m m為正整數(shù)，整數(shù)

40、集合上的關系為正整數(shù)，整數(shù)集合上的關系 證明關系證明關系R R是等價關系。是等價關系。 證：證：(1)(1)對任意對任意 ，有，有 R R自反；自反； (2)(2)對任意對任意 ，若，若 , ,則則 ，即，即R R對稱；對稱；(3)(3)對任意對任意 ，若，若 ，即，即 ，而，而 ，R R傳遞傳遞R R是是Z Z上的等價關系。上的等價關系。 )(mod,|,myxZyxyxRZxRxxmxx,)(modZyx,)(mod,myxRyx即Rxymxy,modZzyx,RzyRyx,zymyxmmzymyx|,|),(mod),(modRzxzxmzyyxzx,|),()(37/57考察關系考察關

41、系R R和集合和集合Z Z；R R將將Z Z分成了如下分成了如下m m個子集：個子集：這這m m個子集特點是：同一個子集中的元素之間都有關個子集特點是：同一個子集中的元素之間都有關系系R R，不同子集的元素之間無關系，不同子集的元素之間無關系R R，每兩個子集，每兩個子集無公共元素，而所有子集的并正好為無公共元素，而所有子集的并正好為Z Z，構成了，構成了Z Z的一個劃分。的一個劃分。14 , 13 , 12 , 1, 1, 1, 12, 23 , 22 , 2, 2 , 2, 22, 23, 13 , 12 , 1, 1 , 1, 12, 13,3 ,2 , 0 ,2,3,mmmmmmmmm

42、mmmmmmmmmmmmmmm38/574.5.34.5.3：等價類與商集：等價類與商集定義定義4.204.20：設設R R是非空集合是非空集合A A上的等價關系，對任上的等價關系，對任意意 ，稱集合，稱集合 為為x x關于關于R R的等的等價類價類(Equivalence Class)(Equivalence Class)，其中，其中x x稱為稱為 的生成的生成元，由于元，由于 中的任何兩個元素中的任何兩個元素a a，b b均相互等價，均相互等價，一般記作一般記作abab。例例4-134-13：設設A=1,2,3,4,5,8A=1,2,3,4,5,8，考慮，考慮R R是是A A上的以上的以3

43、 3為模的同余關系，求其等價類。為模的同余關系，求其等價類。解：從例解：從例4-124-12知，知，R R是一個等價關系，則是一個等價關系，則Ax|xRyAyyxRRxRxRR44 , 1 1 33 ,858 , 5 , 22RRRR39/57定理定理4.114.11：設設R R為非空集合為非空集合A A上的等價關系，則上的等價關系，則證：證：(1) (1) ，R R是等價關系，則是等價關系，則R R自反，因此自反，因此即即(2)(2).).4(;,).3(;,).2(; ,).1 (AxyxyRxAyxyxxRyAyxxAxRAxRRRRR 則則AxRxx , RRxxxRxzRzxxzz,

44、RRRRyxyzxzRzyRyzRyxRxz,40/57同理：同理：(3)(3)若若 ，則存在，則存在 ，即：，即：定義定義4.214.21：設設R R是集合是集合A A上的等價關系，由上的等價關系，由R R確定的確定的一切等價類的集合，稱為集合一切等價類的集合，稱為集合A A上關于上關于R R的商集的商集(Quotient Set)(Quotient Set)，記為，記為A/RA/R，即，即RRRRyxxy RRyxRRyzxz矛盾與yRxRyxRzyRzx,AxxAxxAxxxxxxRxxAxxAxAxAxxRAxRAxRAxRAxRRAxR, ,)4(即|/AxxRAR41/57定理定理

45、4.124.12：設設R R是非空集合是非空集合A A上的等價關系，則上的等價關系，則A A上上的關于的關于R R的商集的商集A/RA/R是是A A的一個劃分，稱之為由的一個劃分，稱之為由R R導導出的等價劃分。出的等價劃分。證：由定理證：由定理4.114.11知，命題成立。知，命題成立。定理定理4.134.13：設設(A)(A)是非空集合是非空集合A A的一個劃分，則的一個劃分，則A A上的關系上的關系 是是A A上的等價關系，稱之為由上的等價關系，稱之為由(A)(A)所導出的等價所導出的等價關系。關系。證明：證明：(1) (1) 為為A A的一個劃分，的一個劃分， 使得使得 ，即，即x x

46、和和x x同屬于同屬于(A)(A)的一個劃分塊，的一個劃分塊， R R是自反的；是自反的；)(,|,的一個劃分塊同屬于AyxAyxyxR)(,AAx)(AAiiAx42/57(2) (2) ，則，則x x和和y y同屬于同屬于(A)(A)的一的一個劃分塊，即個劃分塊，即y y和和x x同屬于一個劃分塊，同屬于一個劃分塊， ，R R是對稱的；是對稱的；(3) (3) ，則，則x x，y y同屬同屬于于(A)(A)的一個劃分塊的一個劃分塊 ，y y，z z同屬于同屬于(A)(A)的一的一個劃分塊個劃分塊 ， ，而由于不同劃分塊的交，而由于不同劃分塊的交集為空，集為空， ，即，即x x和和z z屬于

47、同一劃分塊，屬于同一劃分塊， R R是傳遞的；是傳遞的；R R為等價關系。為等價關系。若設若設 ，則，則RyxAyx,若Rxy,RzyRyxAzyx,若iAjAjiAAyjiAA ,)(21mAAAA212211)()()(imimmAAAAAAAR43/57有定理有定理4.12,4.134.12,4.13知，集合知，集合A A上的等價關系與集合上的等價關系與集合A A的劃分是一一對應的，因此可以說：劃分與等價的劃分是一一對應的，因此可以說：劃分與等價關系這兩個不同的概念本質上是相同的，即是同關系這兩個不同的概念本質上是相同的，即是同一個概念的兩種不同的表達方式。一個概念的兩種不同的表達方式。

48、例例4-144-14：設設A=1,2,3A=1,2,3，求，求A A上的所有等價關系。上的所有等價關系。解：先求解：先求A A的劃分：只有一個劃分塊的劃分為的劃分：只有一個劃分塊的劃分為1,2,31,2,3；具有；具有2 2個劃分塊的劃分為個劃分塊的劃分為 11，2,32,3， 22，1,31,3， 33，1,21,2，具有，具有3 3個劃分塊的劃分為個劃分塊的劃分為 11，22，33；相應的等價關系為：相應的等價關系為： 12345AIRAAR2 , 3,3 , 2,21AAAIRIRIR543,1 , 2,2 , 1,1 , 3,3 , 144/57例例4-154-15：設設R R是集合是

49、集合A A上的一個關系，對任意上的一個關系，對任意a a，b b，c Ac A，若，若 那么稱那么稱R R為為A A上的循環(huán)關系。試證明上的循環(huán)關系。試證明R R是是A A上的一個上的一個等價關系的充要條件是等價關系的充要條件是R R是循環(huán)關系和自反關系。是循環(huán)關系和自反關系。證明：必要性：若證明：必要性：若R R是等價關系；是等價關系；(1)R(1)R等價等價=R=R自反自反(2) (2) ，R R等價等價R R對稱對稱 ，即，即R R是循環(huán)關是循環(huán)關系；系；充分性：若充分性：若R R自反且循環(huán)自反且循環(huán)：(1)(1)自反性顯然；自反性顯然；(2) (2) ，R R是自反，得是自反，得 ，因

50、，因R R是循環(huán)的是循環(huán)的 ，即，即R R是對稱的；是對稱的；RcbRcaRba,，則有且RcaRbaAcba,若RcbRcaRab,R,傳遞，而Aba ,Raa ,RabRba,則若45/57(3) (3) ，則由，則由R R對稱對稱得得 ，由，由R R循環(huán)，循環(huán)， ， R R是傳遞的；是傳遞的；RR等價。等價。RcbRbaAcba,，若Rab ,Rab ,Rcb ,Rca ,46/57在一些研究中，需要把研究的對象排出次序，因此在一些研究中，需要把研究的對象排出次序，因此，集合的元素之間還有一種重要關系，稱為，集合的元素之間還有一種重要關系，稱為“先先后次序后次序”關系，即偏序關系。關系，

51、即偏序關系。定義定義4.214.21：(1)(1)設設R R為非空集合為非空集合A A上的關系，如果上的關系，如果R R是自反的，反對稱的，傳遞的，則稱是自反的，反對稱的，傳遞的，則稱R R為為A A上的偏上的偏序關系序關系(Partial Order relation)(Partial Order relation)。記作。記作“”“”, ,讀作讀作“小于等于小于等于”； (2) (2)設設R R為非空集合為非空集合A A上的關上的關系，如果系，如果R R是反自反的，反對稱的，傳遞的，則稱是反自反的，反對稱的，傳遞的，則稱R R為為A A上的擬序關系上的擬序關系(Quasi Order re

52、lation)(Quasi Order relation)。記。記作作“ ”表示，讀作表示，讀作“大于大于”。1147/57例：例：(1)(1)集合集合A A上的冪集上的冪集(A)(A)上定義的上定義的“ ”“ ”和和“ “ ”分別是偏序關系和擬序關系；分別是偏序關系和擬序關系；(2)(2)實數(shù)集合實數(shù)集合R R上定義的數(shù)的上定義的數(shù)的“小于等于小于等于”關系，關系，“小于小于”關系，分別是偏序關系和擬序關系；關系，分別是偏序關系和擬序關系；(3)(3)自然數(shù)集合自然數(shù)集合N N上定義的上定義的“整除整除”關系，也是一個關系，也是一個偏序集合。偏序集合。定義定義4.224.22：設設是一個偏序

53、集，對是一個偏序集，對 ，x yx y或或y xy x，則稱，則稱x x與與y y是可比的是可比的(Comparable),(Comparable),若若x x與與y y是可比的，是可比的，xyxy，且不存在，且不存在 ，使得，使得xzyxzy，則稱，則稱y y覆蓋覆蓋( (Overlay)xOverlay)x。Ayx ,Az48/57例：例：(1)(1)集合集合A=aA=a，b b，cc，則偏序集，則偏序集 中中，aa與與aa，bb是可比的；是可比的； a a與與bb，cc是不可比是不可比的；的； a a，bb覆蓋覆蓋aa； a a，b b，cc不覆蓋不覆蓋aa。(2)(2)偏序集偏序集RR

54、，對，對 ，x x與與y y都是可比的都是可比的，但，但x x不覆蓋不覆蓋y y，y y也不覆蓋也不覆蓋x x。(3)(3)偏序集偏序集ZZ，對，對 ，x x與與y y都是可比的都是可比的，x x覆蓋覆蓋x-1x-1。(4)(4)偏序集偏序集N|中，中，2 2與與3 3不是可比的，不是可比的，2 2與與6 6是可是可比的，并且比的，并且6 6覆蓋覆蓋2,22,2與與8 8可比，但可比，但8 8不覆蓋不覆蓋2 2。Ayx ,Ayx ,49/574.6.24.6.2：偏序集的哈斯圖：偏序集的哈斯圖由于偏序關系本身具有自反，反對稱，傳遞的性質由于偏序關系本身具有自反，反對稱，傳遞的性質，在用關系圖來

55、描述偏序關系且不引起混淆，可，在用關系圖來描述偏序關系且不引起混淆，可以對其進行簡化，得到的圖叫做偏序圖或哈斯圖以對其進行簡化，得到的圖叫做偏序圖或哈斯圖( (HasseHasse) )。哈斯圖的作圖方法如下：哈斯圖的作圖方法如下：(1):(1):用小圓圈或點表示用小圓圈或點表示A A中的元素，省掉關系圖中中的元素，省掉關系圖中的所有環(huán)的所有環(huán)( (因自反性因自反性) )；(2):(2):對對 ，若，若xyxy則將則將x x畫在畫在y y的下方，可省的下方，可省掉關系圖中所有邊的箭頭；掉關系圖中所有邊的箭頭；(3):(3):對對 ，若，若y y覆蓋覆蓋x x，則在，則在x x與與y y之間連條

56、線之間連條線，否則無線相連。，否則無線相連。Ayx ,Ayx ,50/57按按(1)(1)，(2)(2)，(3)(3)所作成的圖稱為哈斯圖。所作成的圖稱為哈斯圖。例例4-164-16：設設A=2,3,6,12,24,36A=2,3,6,12,24,36，“”“”是是A A上的上的整除關系，畫出其一般關系圖和哈斯圖。整除關系，畫出其一般關系圖和哈斯圖。例例4-174-17：設集合設集合A=aA=a，B=aB=a，bb，C=aC=a，b b，cc分別畫出集合分別畫出集合A A，B B，C C之冪集上定義的之冪集上定義的“ ”“ ”的哈的哈斯圖。斯圖。51/574.6.34.6.3：偏序集中的特殊元素：偏序集中的特殊元素定義定義4.234.23：設設為偏序集，為偏序集，最小元與極小元不一樣，最小元是最小元與極小元不一樣，最小元是B B中最小的元素中最小的元素，它與，它與B B中其它元素都是可比的，而極小元不一定中其它元素都是可比的，而極小元不一定與與B B中的元素都可比，只要沒有比它小的元素，它中的元素都可比，只要沒有比它小的元素，它就是極小元；就是極小元；對于有窮集，極小元一定存在，但最小元不一定對于有窮集，極小元一定存在，但最小元不一定存在；存在；ByAB,的極大元。為成立，則稱若的極小元；為成立，則稱若的最大元；為成