四章節(jié)二元關系ppt課件

1、1/564.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, x=u, y=v;y=v;例如：平面上的坐標例如：平面上的坐標，x, y Rx, y R

2、； 等都是序偶。等都是序偶。2/56定義定義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=，。性質性質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/56證明：證明：(6). (6). ，且當，且當 或或 時，逆命題成立。時，逆命題成立。 A);(CA)(BAC)(BC),(AB)(AC)(BA),(CA)(BAC)(BC),(AB)(AC)(BAA)()(,)(,)(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyxDCBADBCA

4、 BA BA4/56定義定義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,2112

5、1nnbbbaaa,2121nibaii, 2 , 1,),(21nxxxnxxx,21nAAA,21|,221121nnnAxAxAxxxxnAAA21nAAA21nA5/564.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/56A A到到B B上的全部二元關系；而上的全部二元關系；而 ，為為B B上的二上的二元關系。元關系。普通來說，假設普通來說，假設|A|=m|A|=m，|B|=n|B|=n，A A到到B

7、 B上的二元關系共上的二元關系共有有 個，個，A A上的共有上的共有 個二元關系；個二元關系；特殊的二元關系：特殊的二元關系： (1). (1). 空關系；空關系； (2). (2). 全域關系：全域關系： ； (3). (3). 恒等關系：恒等關系： 。 mn222mAAAyAxyxEA|,|,AxxxIA7/56定義定義4.74.7：設：設R R為二元關系，那么為二元關系，那么 (1). (1). 為為R R的定義域；的定義域； (2). (2). 為為R R的值域；的值域； (3). (3). 為為R R的域。的域。普通地，假設普通地，假設R R是是A A到到B B上的二元關系，那么有上

8、的二元關系，那么有 。 例例4-14-1：設：設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，那么，那么domR=2,3,4,6domR=2,3,4,6，ranR=a, b, cranR=a, b, c。)(|xRyyxdomR)(|xRyxyranRranRdomRfldRBranRAdomR,8/564.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中的元素為頂點，在中的元素為頂點，在圖中用圖中用“表示頂點，假設表示頂點，假設 那么可自頂點那么可自頂點 向頂點向頂點 引有向邊引有向邊 ，其箭頭指向，其箭頭指向 ，用這

10、，用這種方法畫出的圖稱為關系圖種方法畫出的圖稱為關系圖(Graph of Relation)(Graph of Relation)。nxxx,21nyyy,21jiRyxixjy),(jiyxjy9/56例例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，且，且,2121nmbbbBaaaABARR

11、MijrjijiijbRaRbar當且僅當當且僅當0110/561.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=，|,|,|,

12、|,xRyyxRxSyxRyyxSRxSyxRyyxSRxSyxRyyxSR11/56S=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/562.2.關系的逆運算關系的逆運算由于關系是序偶的集合，除了集合的普通運算外由于關系是序偶的集合，除了集合的

13、普通運算外，還有一些特有的運算。，還有一些特有的運算。定義定義4.114.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=，c, 2， = =，。1R|,1xRyxyRByAx ,xyRxRy1RMRRMM1 11,AAII1R13/56定理定理4.14.1：設：設R R和和S S都是都是A A到到B B上的二

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

15、合A=0,1,2,3,4A=0,1,2,3,4，R R，S S均為均為A A上的二上的二元關系，且元關系，且R=|x+y=4=R=|x+y=4=，S= =|y-S= =|y-x=1=x=1=，；求；求普通地，普通地，SR)(|,tSyxRttyxSRRR2R2RR)(SRR,S)(R,SSRRRSSRRSSR15/56定理定理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(),().(

16、1 (FGGFHGFHGF RRRIIRAA).2( ,).1 (.).(4(,)().3(,).(2(,)().1 (FHFGFHGHFGFHGFFHFGFHGHFGFHGF16/564.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/56定理定理4.54.5：設：設R R為為A

17、 A上的二元關系，上的二元關系，m m，n n為自然數(shù)，為自然數(shù)，那么那么證證(4)(4)：假設：假設n=0n=0時，那么有時，那么有 假設假設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 (mnmnnnRRRR

18、RRR.)().(4( ,).(3( ,).2(11nnmnnmnmnmRRRRRRR AAnAIIRIR1101)()( ,)(11)()(kkRR111111111)()()()()()(kkkkkRRRRRRRR)20(2njijiRR22n22n1210,kRRRR18/56系中，至少有兩個是一樣的系中，至少有兩個是一樣的( (鴿巢原理鴿巢原理) )，即有，即有定理定理4.74.7：設：設A A是有限集合，且是有限集合，且|A|=n|A|=n，R R是是A A上的二上的二元關系，那么元關系，那么證明：顯然證明：顯然 ，下面證：，下面證： 。而而 ，為此，只需證明對恣意的，為此，只需證明

19、對恣意的knkn，有，有 即可。對恣意的即可。對恣意的 ，那么由，那么由“的定義知：存在的定義知：存在 ，使得：，使得：.),20(,2jinRRjiji使iniiiRR11 iiiniRR11iniiiRR11 iniiniiiRRR111inikRR1 kRba ,Aaaak121,),(,012110baaaRaaRaaRaakkk令19/56由于由于|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/565 5：集合在關系下的像：集合在關系下的像定義定義4.144.14

21、：設：設R R為二元關系，為二元關系，A A是集合是集合(1)(1)：R R在在A A上的限制上的限制 定義為：定義為： (2)(2)：A A在在R R下的像下的像RARA定義為定義為RA=ran( )RA=ran( )。例：例：R=R=，那么，那么： Ra= Ra=，；Ra= ;Ra= ; Ra, a=R Ra, a=R； Ra=b,aRa=b,a；Ra,a=b,a,a,aRa,a=b,a,a,a；|,AxxRyyxARARAR,1aaaR;11aaRaR 21/56定理定理4.84.8：設：設F F為關系，為關系，A A，B B為集合，那么為集合，那么例例4-64-6：設：設 ，A=0,1

22、,2A=0,1,2，B=0,-1,-2B=0,-1,-2。(1)(1)求求RABRAB和和RARBRARB；(2)(2)求求RA-RBRA-RB和和RA-BRA-B。解解(1)(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|

23、,|,xyZyxyxR 22/56我們在研討關系的性質時，可以假定關系是某一非我們在研討關系的性質時，可以假定關系是某一非空集合上的二元關系，這一假設不失普通性。因空集合上的二元關系，這一假設不失普通性。因此任一此任一A A到到B B上的關系上的關系R R，即，即 ，而，而 ，所以關系，所以關系R R總可以看成是總可以看成是AB AB 上的關系，它與原關系上的關系，它與原關系R R具有完全一樣的序具有完全一樣的序偶，對它的討論替代對偶，對它的討論替代對R R的討論無損于問題的本質的討論無損于問題的本質1.1.關系的性質關系的性質定義定義4.154.15：設：設R R是是A A上的二元關系，即上

24、的二元關系，即 ，那，那么么(1)(1)假設假設 ，那么稱，那么稱R R是自反的是自反的(Reflexive)(Reflexive)；(2)(2)假設假設 ，那么稱，那么稱R R是反自反是反自反的的(Irreflexive)(Irreflexive)；BAR)()(BABABAAAR),(RxxAxx),(RxxAxx23/56(3)(3)假設假設 ，那么稱，那么稱R R是對是對稱的稱的(Symmetric)(Symmetric)(4)(4)假設假設 ，那么稱，那么稱R R是反對稱的是反對稱的(Antisymmetric)(Antisymmetric)(5)(5)假設假設 ，那么，那么稱稱R

25、R是傳送的是傳送的(Transitive)(Transitive)例例4-74-7：設：設A=a, b, c, dA=a, b, c, d(1):R=(1):R=，c, c，是自反的；是自反的；S=S=，是反自反的；是反自反的；T=,c, T=,c,既不是自反的也不是反自反的；既不是自反的也不是反自反的；),(yRxxRyAyxyx),(yxyRxxRyAyxyx),(xRzyRzxRyAzyxzyx24/56在關系圖上：關系在關系圖上：關系R R是自反的，當且僅當其關系圖是自反的，當且僅當其關系圖中的每個節(jié)點都有環(huán)，關系中的每個節(jié)點都有環(huán)，關系R R是反自反的，當且僅是反自反的，當且僅當其關

26、系圖中的每個節(jié)點上都無環(huán)；當其關系圖中的每個節(jié)點上都無環(huán)；在關系矩陣上：關系在關系矩陣上：關系R R是自反的，當且僅當其關系是自反的，當且僅當其關系矩陣的主對角線上全為矩陣的主對角線上全為1 1，關系，關系R R是反自反的，當是反自反的，當且僅當其關系矩陣的主對角線上全為且僅當其關系矩陣的主對角線上全為0 0。例例4-84-8：設：設A=a, b, cA=a, b, c稱的。既是對稱的，也是反對反對稱的；既不是對稱的，也不是是反對稱的；是對稱的；,)4(,)3(,)2(,) 1 (4321ccaaRaccabaaaRcaaaRaccaaaR25/56關系圖上：關系關系圖上：關系R R是對稱的當

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

28、的；是傳遞的；是傳遞的；,)4(,)3(,)2(,) 1 (4321dccacbbaRcbbaaaRbaRcacbbaaaR26/56關系圖上：關系關系圖上：關系R R是傳送的當且僅當其關系圖中，是傳送的當且僅當其關系圖中，任何三個節(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.利用集合運算來判別關系的性質利用集合運算來

29、判別關系的性質定理定理4.94.9：設：設R R是集合是集合A A上的二元關系，那么上的二元關系，那么。則必有若1, 1, 1, 1 ,ikjkijrrrnkji.)5(;)4(;)3(;)2(;) 1 (11RRRRIRRRRRRIRRRIRAAA 傳遞的是反對稱的是對稱的是反自反的是自反的27/563.3.關系性質的保守性關系性質的保守性定理定理4.104.10：設：設R R，S S是是A A上的二元關系，那么上的二元關系，那么例例4-104-10：設：設R=R=， S=S=，是定義在是定義在A=a, b, A=a, b, cc上的兩個二元關系。上的兩個二元關系。傳遞。傳遞反對稱；反對稱對

30、稱；對稱反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR,)5(,)4(,) 3(,)2(,) 1 (1111128/56顯然顯然R R，S S是反自反的，反對稱的，傳送的，那么是反自反的，反對稱的，傳送的，那么 也是反自反的，反對稱的，傳送也是反自反的，反對稱的，傳送的；的； 也具備上述的一切性質；也具備上述的一切性質；(3)RS=, ,c, (3)RS=, ,b,僅是對稱的和反自反的；僅是對稱的和反自反的； 那么是傳送那么是傳送的和對稱的。的和對稱的。111,).1 (SRSR SR)2(,)4(abbabbaaSR29/56關系的限制

31、于擴展：對于任何一個具備某種性質關系的限制于擴展：對于任何一個具備某種性質( (如如自反、對稱、傳送自反、對稱、傳送) )的關系來說，在實際研討與運的關系來說，在實際研討與運用上都非常重要，但遺憾的是，許多我們要研討用上都非常重要，但遺憾的是，許多我們要研討的關系并不具有我們所希望的良好性質。因此，的關系并不具有我們所希望的良好性質。因此，我們往往要在給定的關系中刪去一些或添加一些我們往往要在給定的關系中刪去一些或添加一些元素，以改動原有關系的性質，即所謂的關系的元素，以改動原有關系的性質，即所謂的關系的限制與擴展。限制與擴展。關系的閉包那么是關系的擴展。關系的閉包那么是關系的擴展。定義定義4

32、.164.16：設：設R R是定義在是定義在A A上的二元關系，假設存在上的二元關系，假設存在滿足：滿足：(1) (1) 是自反的是自反的( (對稱的或傳送的對稱的或傳送的) )；(2).(2). ；(3)(3)對對R R的任何擴展的任何擴展 是自反的是自反的( (對稱的對稱的或傳送的或傳送的) )，那么，那么 。普通將。普通將R R的自反、對稱的自反、對稱、傳送閉包記作、傳送閉包記作r(R)r(R)，s(R)s(R)，t(R)t(R)。RRRRR RR 30/56例：定義在例：定義在N N上的上的“ 關系的自反閉包關系的自反閉包r(R)r(R)為為“，對稱閉包對稱閉包s(R)s(R)為為“，

33、傳送閉包，傳送閉包t(R)t(R)為為“ ；定義在定義在N N上的上的“= =關系的自反閉包關系的自反閉包r(R)r(R)為為“= =，對稱閉，對稱閉包包s(R)s(R)為為“= =，傳送閉包，傳送閉包t(R)t(R)為為“= =。例例4-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)=,

34、;t(R)=,;t(R)=,;31/56利用關系圖，關系矩陣求閉包的方法：利用關系圖，關系矩陣求閉包的方法：(1).(1).求一個關系的自反閉包，即將圖中一切的無求一個關系的自反閉包，即將圖中一切的無環(huán)節(jié)點加上環(huán)，矩陣中的對角線上的值全定義為環(huán)節(jié)點加上環(huán)，矩陣中的對角線上的值全定義為1 1；(2).(2).求一個關系的對稱閉包，那么在圖中，任何求一個關系的對稱閉包，那么在圖中，任何一對節(jié)點之間，假設僅存在一條邊，那么加一條一對節(jié)點之間，假設僅存在一條邊，那么加一條反方向的邊；矩陣中那么為：假設反方向的邊；矩陣中那么為：假設 ，那，那么令么令 ，即，即 ；(3).(3).求一個關系的傳送閉包，那

35、么在圖中，對恣求一個關系的傳送閉包，那么在圖中，對恣意節(jié)點意節(jié)點a a，b b，c c，假設，假設a a到到b b有一條邊，同時有一條邊，同時b b到到c c也也有一條邊，那么從有一條邊，那么從a a到到c c必添加一條邊必添加一條邊( (當當a a到到c c無邊無邊時時) )，在矩陣中，假設，在矩陣中，假設 。)( 1jirij) 1( 1jijirr若1)(RRRsMMM）（若則令111, 1ikikjkijrrrr32/56定理定理4.114.11：設：設R R是是A A上的二元關系，那么上的二元關系，那么定理定理4.124.12：設：設R R是集合是集合A A上的關系，那么上的關系，那

36、么定理定理4.144.14：設：設R R是集合是集合A A上的關系，那么上的關系，那么iniiiARRtnARRtRRRsIRRRRr1110)(|,)(: )3(,)(: )2( ,)(: ) 1 (則若.)(: )3(,)(: )2(,)(: ) 1 (RRtRRRsRRRrR是傳遞的是對稱的是自反的.)(: ) 3(,)(),(: )2(,)(),(: ) 1 (傳遞傳遞對稱對稱自反自反RrRRtRrRRtRsR33/56定義定義4.174.17：(1)(1)集合集合A A上的關系上的關系R R的自反對稱閉包定的自反對稱閉包定義為義為rs(R)=r(s(R); (2)rs(R)=r(s(

37、R); (2)集合集合A A上的關系上的關系R R的自反的自反傳送閉包定義為傳送閉包定義為rt(R)=r(t(R); (3)rt(R)=r(t(R); (3)集合集合A A上的關上的關系系R R的對稱傳送閉包定義為的對稱傳送閉包定義為st(R)=s(t(R);st(R)=s(t(R);類似的類似的，可有，可有sr(R)sr(R)，tr(R)tr(R)，ts(R)ts(R)。定理定理4.154.15：設：設R R是集合是集合A A上的關系，那么上的關系，那么)()().3(),()().2(),()().1 (RtsRstRtrRrtRsrRrs34/564.5.14.5.1：集合和劃分：集合和

38、劃分定義定義4.184.18：設：設A A是一個非空集合，是一個非空集合， 是是A A的恣意的恣意n n個非空子集，假設個非空子集，假設 滿足：滿足： 那么稱集合那么稱集合 為集合為集合A A的一個劃的一個劃分分(Partition)(Partition)，而，而 叫做這個劃分的塊叫做這個劃分的塊或類?；蝾?。例如：例如：(1) (1) 構成集合構成集合U U的一個劃分；的一個劃分；(2) (2) 構成了構成了U U上的一個劃上的一個劃分。分。nAAA,21nAAA,21AAnjijiAAiniji 1).2( ;, 1,).1 (,)(21nAAAAnAAA,21,AA,21212121AAA

39、AAAAA35/564.5.24.5.2：等價關系：等價關系定義定義4.194.19：設：設R R為非空集合為非空集合A A上的關系，假設上的關系，假設R R是自是自反的，對稱的，傳送的，那么稱反的，對稱的，傳送的，那么稱R R為為A A上的等價關上的等價關系系(Equivalent Relation)(Equivalent Relation)。假設。假設 ，稱，稱x x等價于等價于y,y,記作記作xyxy。例：例：(1)(1)一群人，同姓，同年齡，同性別都是等價一群人，同姓，同年齡，同性別都是等價關系，朋友，同窗關系不是等價關系：不傳送；關系，朋友，同窗關系不是等價關系：不傳送；(2) (2

40、) 都是都是A A上的等價關系；上的等價關系；(3)(3)三角形三角形“類似，類似，“全等都是等價關系；全等都是等價關系；(4)(4)冪集上定義的冪集上定義的 關系，整數(shù)集上定義的關系，整數(shù)集上定義的不是不是等價關系，不對稱。等價關系，不對稱。Ryx ,AAIA,36/56例例4-124-12：設：設m m為正整數(shù)，整數(shù)集合上的關系為正整數(shù)，整數(shù)集合上的關系 證明關系證明關系R R是等價關系。是等價關系。 證：證：(1)(1)對恣意對恣意 ，有，有 R R自反；自反； (2)(2)對恣意對恣意 ，假設，假設 , ,那么那么 ，即，即R R對稱；對稱；(3)(3)對恣意對恣意 ，假設，假設 ，即

41、即 ，而，而 ，R R傳傳送送RR是是Z Z上的等價關系。上的等價關系。 )(mod,|,myxZyxyxRZxRxxmxx,)(modZyx,)(mod,myxRyx即Rxymxy,modZzyx,RzyRyx,zymyxmmzymyx|,|),(mod),(modRzxzxmzyyxzx,|),()(37/56調查關系調查關系R R和集合和集合Z Z；R R將將Z Z分成了如下分成了如下m m個子集：個子集：這這m m個子集特點是：同一個子集中的元素之間都有關個子集特點是：同一個子集中的元素之間都有關系系R R，不同子集的元素之間無關系，不同子集的元素之間無關系R R，每兩個子集，每兩個子

42、集無公共元素，而一切子集的并正好為無公共元素，而一切子集的并正好為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,mmmmmmmmmmmmmmmmmmmmmmmm38/564.5.34.5.3：等價類與商集：等價類與商集定義定義4.204.20：設：設R R是非空集合是非空集合A A上的等價關系，對恣上的等價關系，對恣意意 ，稱集合，稱集合 為為x x關于關于R R的等的等價類價類(Equivale

43、nce 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 3為模的同余關系，求其等價類。為模的同余關系，求其等價類。解：從例解：從例4-124-12知，知，R R是一個等價關系，那么是一個等價關系，那么Ax|xRyAyyxRRxRxRR44 , 1 1 33 ,858 , 5 , 22RRRR39/56定理定理4.114

44、.11：設：設R R為非空集合為非空集合A A上的等價關系，那么上的等價關系，那么證：證：(1) (1) ，R R是等價關系，那么是等價關系，那么R R自反，因此自反，因此即即(2)(2).).4(;,).3(;,).2(; ,).1 (AxyxyRxAyxyxxRyAyxxAxRAxRRRRR 則則AxRxx , RRxxxRxzRzxxzz,RRRRyxyzxzRzyRyzRyxRxz,40/56同理：同理：(3)(3)假設假設 ，那么存在，那么存在 ，即：即：定義定義4.214.21：設：設R R是集合是集合A A上的等價關系，由上的等價關系，由R R確定的確定的一切等價類的集合，稱為集

45、合一切等價類的集合，稱為集合A A上關于上關于R R的商集的商集(Quotient Set)(Quotient Set)，記為，記為A/RA/R，即，即RRRRyxxy RRyxRRyzxz矛盾與yRxRyxRzyRzx,AxxAxxAxxxxxxRxxAxxAxAxAxxRAxRAxRAxRAxRRAxR, ,)4(即|/AxxRAR41/56定理定理4.124.12：設：設R R是非空集合是非空集合A A上的等價關系，那么上的等價關系，那么A A上的關于上的關于R R的商集的商集A/RA/R是是A A的一個劃分，稱之為由的一個劃分，稱之為由R R導出的等價劃分。導出的等價劃分。證：由定理證

46、：由定理4.114.11知，命題成立。知，命題成立。定理定理4.134.13：設：設(A)(A)是非空集合是非空集合A A的一個劃分，那的一個劃分，那么么A A上的關系上的關系 是是A A上的等價關系，稱之為由上的等價關系，稱之為由(A)(A)所導出的等價所導出的等價關系。關系。證明：證明：(1) (1) 為為A A的一個劃分，的一個劃分， 使得使得 ，即，即x x和和x x同屬于同屬于(A)(A)的一個劃分塊，的一個劃分塊， RR是自反的；是自反的；)(,|,的一個劃分塊同屬于AyxAyxyxR)(,AAx)(AAiiAx42/56(2) (2) ，那么，那么x x和和y y同屬于同屬于(A

47、)(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屬于同一劃分塊，屬于同一劃分塊， RR是傳送的；是傳送的；RR為等價關系。為等價關系。假設設假設設 ，那么，那么RyxAyx,若Rxy,RzyRyxAzyx,若iAjAjiAAyjiAA ,)(21mAAAA212211)()()

48、(imimmAAAAAAAR43/56有定理有定理4.12,4.134.12,4.13知，集合知，集合A A上的等價關系與集合上的等價關系與集合A A的劃分是一一對應的，因此可以說：劃分與等價的劃分是一一對應的，因此可以說：劃分與等價關系這兩個不同的概念本質上是一樣的，即是同關系這兩個不同的概念本質上是一樣的，即是同一個概念的兩種不同的表達方式。一個概念的兩種不同的表達方式。例例4-144-14：設：設A=1,2,3A=1,2,3，求，求A A上的一切等價關系。上的一切等價關系。解：先求解：先求A A的劃分：只需一個劃分塊的劃分為的劃分：只需一個劃分塊的劃分為1,2,31,2,3；具有；具有2

49、 2個劃分塊的劃分為個劃分塊的劃分為 1 1，2,32,3， 2 2，1,31,3， 3 3，1,21,2，具有，具有3 3個劃分塊的劃分為個劃分塊的劃分為 1 1，22，33；相應的等價關系為：相應的等價關系為： 12345AIRAAR2 , 3,3 , 2,21AAAIRIRIR543,1 , 2,2 , 1,1 , 3,3 , 144/56例例4-154-15：設：設R R是集合是集合A A上的一個關系，對恣意上的一個關系，對恣意a a，b b，c Ac A，假設，假設 那么稱那么稱R R為為A A上的循環(huán)關系。試證明上的循環(huán)關系。試證明R R是是A A上的一個上的一個等價關系的充要條件

50、是等價關系的充要條件是R R是循環(huán)關系和自反關系。是循環(huán)關系和自反關系。證明：必要性：假設證明：必要性：假設R R是等價關系；是等價關系；(1)R(1)R等價等價=R=R自反自反(2) (2) ，R R等價等價RR對對稱稱 ，即，即R R是循環(huán)是循環(huán)關系；關系；充分性：假設充分性：假設R R自反且循環(huán)：自反且循環(huán)：(1)(1)自反性顯然；自反性顯然；(2) (2) ，R R是自反，得是自反，得 ，因，因R R是循環(huán)是循環(huán)的的 ，即，即R R是對稱的；是對稱的；RcbRcaRba,，則有且RcaRbaAcba,若RcbRcaRab,R,傳遞，而Aba ,Raa ,RabRba,則若45/56(3

51、) (3) ，那么由，那么由R R對對稱得稱得 ，由，由R R循環(huán)，循環(huán)， 得得 ， R R是傳送的；是傳送的；RR等價。等價。RcbRbaAcba,，若Rab ,Rab ,Rcb ,Rca ,46/56在一些研討中，需求把研討的對象排出次序，因此在一些研討中，需求把研討的對象排出次序，因此，集合的元素之間還有一種重要關系，稱為，集合的元素之間還有一種重要關系，稱為“先后先后次序關系，即偏序關系。次序關系，即偏序關系。定義定義4.214.21：(1)(1)設設R R為非空集合為非空集合A A上的關系，假設上的關系，假設R R是是自反的，反對稱的，傳送的，那么稱自反的，反對稱的，傳送的，那么稱R

52、 R為為A A上的偏上的偏序關系序關系(Partial Order relation)(Partial Order relation)。記作。記作“, ,讀作讀作“小于等于；小于等于； (2) (2)設設R R為非空集合為非空集合A A上的關系上的關系，假設，假設R R是反自反的，反對稱的，傳送的，那么稱是反自反的，反對稱的，傳送的，那么稱R R為為A A上的擬序關系上的擬序關系(Quasi Order relation)(Quasi Order relation)。記。記作作“ 表示，讀作表示，讀作“大于。大于。1147/56例：例：(1)(1)集合集合A A上的冪集上的冪集(A)(A)上定

53、義的上定義的“ 和和“ 分別是偏序關系和擬序關系；分別是偏序關系和擬序關系；(2)(2)實數(shù)集合實數(shù)集合R R上定義的數(shù)的上定義的數(shù)的“小于等于關系，小于等于關系，“小小于關系，分別是偏序關系和擬序關系；于關系，分別是偏序關系和擬序關系；(3)(3)自然數(shù)集合自然數(shù)集合N N上定義的上定義的“整除關系，也是一個偏整除關系，也是一個偏序集合。序集合。定義定義4.224.22：設：設是一個偏序集，對是一個偏序集，對 ，x x yy或或y xy x，那么稱，那么稱x x與與y y是可比的是可比的(Comparable),(Comparable),假設假設x x與與y y是可比的，是可比的，xyxy，

54、且不存在，且不存在 ，使得，使得xyzxyz，那么稱，那么稱y y覆蓋覆蓋(Overlay)x(Overlay)x。Ayx ,Az48/56例：例：(1)(1)集合集合A=aA=a，b b，cc，那么偏序集，那么偏序集(A), 中，中，aa與與aa，bb是可比的；是可比的； a a與與bb，cc是是不可比的；不可比的； a a，bb覆蓋覆蓋aa； a a，b b，cc不覆蓋不覆蓋aa。(2)(2)偏序集偏序集RR，對，對 ，x x與與y y都是可比的都是可比的，但，但x x不覆蓋不覆蓋y y，y y也不覆蓋也不覆蓋x x。(3)(3)偏序集偏序集ZZ，對，對 ，x x與與y y都是可比的都是可

55、比的，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/564.6.24.6.2：偏序集的哈斯圖：偏序集的哈斯圖由于偏序關系本身具有自反，反對稱，傳送的性由于偏序關系本身具有自反，反對稱，傳送的性質，在用關系圖來描畫偏序關系且不引起混淆，質，在用關系圖來描畫偏序關系且不引起混淆，可以對其進展簡化，得到的圖叫做偏序圖或哈斯可以對其進展簡化，得到的圖叫做偏序圖或哈斯圖圖(Hasse)(Hasse)。

56、哈斯圖的作圖方法如下：哈斯圖的作圖方法如下：(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之間連之間連條線，否那么無線相連。條線，否那么無線相連。Ayx ,Ayx ,50/56按按(1)(1)，(2)(2)，(3)(3)所作成的圖稱為哈斯圖。所作成的圖稱為哈斯圖。例例4-164-16：設：設A=2,3,6,12,24,36A=2,3,6,12,24,36，“是是A A上的整上的整除關系，畫出其普通關系圖和哈斯圖。除關系