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

1、1/564.1 4.1 二元關(guān)系及其表示法二元關(guān)系及其表示法4.1.1 4.1.1 序偶與笛卡爾積序偶與笛卡爾積定義定義4.14.1：由兩個(gè)元素：由兩個(gè)元素x x和和y y按一定的次序按一定的次序組成的二元組稱為有序?qū)蛐蚺冀M成的二元組稱為有序?qū)蛐蚺?Ordered)(Ordered)，記作，記作，其中，其中x x是它是它的第一元素，的第一元素，y y是它的第二元素。是它的第二元素。性質(zhì)性質(zhì)4.14.1：(1)(1)： = = 當(dāng)且當(dāng)且僅當(dāng)僅當(dāng)x=yx=y；(2)(2)： = =當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x=u, x=u, y=v;y=v;例如：平面上的坐標(biāo)例如：平面上的坐標(biāo)，x, y Rx, y R

2、； 等都是序偶。等都是序偶。2/56定義定義4.24.2：設(shè)：設(shè)A A，B B是兩個(gè)集合，稱集合是兩個(gè)集合，稱集合 為集合為集合A A與與B B的的笛卡爾積笛卡爾積(Descartes Product)(Descartes Product)。例：設(shè)例：設(shè)A=1,2A=1,2；B=a, bB=a, b那么那么A A B=B=，；B B A=A=，。性質(zhì)性質(zhì)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). 不適宜結(jié)合律，不適宜結(jié)合律，(A(AB)B)C AC A(B(BC)(C)(除除非非 ) )； (5). (5). 對(duì)對(duì)和和運(yùn)算滿足分配律，運(yùn)算滿足分配律，|,ByAxyxBA AA， CBA 3/56證明：證明：(6). (6). ，且當(dāng)，且當(dāng) 或或 時(shí)，逆命題成立。時(shí)，逆命題成立。 A);(CA)(BAC)(BC),(AB)(AC)(BA),(CA)(BAC)(BC),(AB)(AC)(BAA)()(,)(,)(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyxDCBADBCA

4、 BA BA4/56定義定義4.34.3：一個(gè)有序：一個(gè)有序n(n2)n(n2)元組是一個(gè)有序?qū)?，元組是一個(gè)有序?qū)?，它的第一個(gè)元素為有序的它的第一個(gè)元素為有序的n-1n-1元組元組 ，第二個(gè)元素為，第二個(gè)元素為 ，記為，記為 即：即： ； 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)n n維空間中的點(diǎn)維空間中的點(diǎn)M M的坐標(biāo)的坐標(biāo) 為有序的為有序的n n元元組組 。定義定義4.44.4：設(shè)：設(shè) 為為n n個(gè)集合個(gè)集合(n 2)(n 2)，稱集，稱集合合 為為n n維卡氏積或維卡氏積或n n階笛卡爾積，記作階笛卡爾積，記作 ， 當(dāng)當(dāng) 時(shí)簡(jiǎn)記為時(shí)簡(jiǎn)記為 。121,naaanannaaaa,121nnnaaaaaaa,2112

5、1nnbbbaaa,2121nibaii, 2 , 1,),(21nxxxnxxx,21nAAA,21|,221121nnnAxAxAxxxxnAAA21nAAA21nA5/564.1.2 4.1.2 二元關(guān)系二元關(guān)系定義定義4.54.5：假設(shè)集合：假設(shè)集合F F中的全體元素為有序的中的全體元素為有序的n(n2)n(n2)元組，那么稱元組，那么稱F F為為n n元關(guān)系，特別地，當(dāng)元關(guān)系，特別地，當(dāng)n=2n=2時(shí)，稱時(shí)，稱F F為二元關(guān)系，簡(jiǎn)稱關(guān)系。為二元關(guān)系，簡(jiǎn)稱關(guān)系。對(duì)于二元關(guān)系對(duì)于二元關(guān)系F F，假設(shè)，假設(shè) ，常記作，常記作 ，反，反之之 ；規(guī)定；規(guī)定 為為n n元空關(guān)系，也是二元空關(guān)系，

6、簡(jiǎn)元空關(guān)系，也是二元空關(guān)系，簡(jiǎn)稱空關(guān)系。稱空關(guān)系。定義定義4.64.6：設(shè)：設(shè)A A，B B為兩集合，為兩集合，A AB B的集合子集的集合子集R R稱為稱為A A到到B B的二元關(guān)系，特別地，當(dāng)?shù)亩P(guān)系，特別地，當(dāng)A=BA=B時(shí)，稱時(shí)，稱R R為為A A上的上的二元關(guān)系。二元關(guān)系。例：例：A=a, bA=a, b，B=cB=c，那么，那么A AB B的子集有的子集有 ，, , ，F(xiàn)yx ,xFyyFx 6/56A A到到B B上的全部二元關(guān)系；而上的全部二元關(guān)系；而 ，為為B B上的二上的二元關(guān)系。元關(guān)系。普通來(lái)說(shuō)，假設(shè)普通來(lái)說(shuō)，假設(shè)|A|=m|A|=m，|B|=n|B|=n，A A到到B

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

8、的二元關(guān)系，那么有 。 例例4-14-1：設(shè)：設(shè)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 關(guān)系的表示關(guān)系的表示1. 1. 集合表示法集合表示法 由于關(guān)系也是一種特殊的集合，所以可以用集合由于關(guān)系也是一種特殊的集合，所以可以用集合的兩種根本的表示方法的兩種根本的表示方法( (

9、枚舉法，描畫(huà)法枚舉法，描畫(huà)法) )來(lái)表示來(lái)表示關(guān)系；如：設(shè)關(guān)系；如：設(shè)A=2A=2，B=3B=3，那么，那么A A到到B B上的有關(guān)上的有關(guān)系系R=R=；集合；集合N N上的上的“小于等于關(guān)系：小于等于關(guān)系：R=|(x, y) N(x y) R=|(x, y) N(x y) 。2. 2. 關(guān)系圖法關(guān)系圖法定義定義4.84.8：設(shè)集合：設(shè)集合A= A= 到到B= B= 上的二元關(guān)系上的二元關(guān)系R R，以集合，以集合A A，B B中的元素為頂點(diǎn)，在中的元素為頂點(diǎn)，在圖中用圖中用“表示頂點(diǎn)，假設(shè)表示頂點(diǎn)，假設(shè) 那么可自頂點(diǎn)那么可自頂點(diǎn) 向頂點(diǎn)向頂點(diǎn) 引有向邊引有向邊 ，其箭頭指向，其箭頭指向 ，用這

10、，用這種方法畫(huà)出的圖稱為關(guān)系圖種方法畫(huà)出的圖稱為關(guān)系圖(Graph of Relation)(Graph of Relation)。nxxx,21nyyy,21jiRyxixjy),(jiyxjy9/56例例4-24-2：求集合：求集合A=1,2,3,4A=1,2,3,4的恒等關(guān)系，空關(guān)系，的恒等關(guān)系，空關(guān)系，全關(guān)系和小于關(guān)系的關(guān)系圖。全關(guān)系和小于關(guān)系的關(guān)系圖。3. 3. 關(guān)系矩陣關(guān)系矩陣定義定義4.94.9：設(shè)：設(shè) ，那么，那么R R的關(guān)系矩陣的關(guān)系矩陣 為一為一m mn n矩陣，它的第矩陣，它的第i i，j j分量分量 只取只取0 0或或1 1，且，且,2121nmbbbBaaaABARR

11、MijrjijiijbRaRbar當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)0110/561.1.關(guān)系的交，并，補(bǔ)，差運(yùn)算關(guān)系的交，并，補(bǔ)，差運(yùn)算定義定義4.104.10：設(shè)：設(shè)R R和和S S為為A A到到B B的二元關(guān)系，其并，交的二元關(guān)系，其并，交，補(bǔ)，差運(yùn)算定義如下：，補(bǔ)，差運(yùn)算定義如下：例例4-34-3：設(shè)：設(shè)A=1,2,3,4A=1,2,3,4，假設(shè)，假設(shè)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.關(guān)系的補(bǔ)運(yùn)算是對(duì)全關(guān)系而言的；關(guān)系的補(bǔ)運(yùn)算是對(duì)全關(guān)系而言的；關(guān)系的并，交，差，補(bǔ)的矩陣可用如下方法求?。宏P(guān)系的并，交，差，補(bǔ)的矩陣可用如下方法求?。?SSSRSRSRSRSRSRSRMMMMMMMMMMMM,12/562.2.關(guān)系的逆運(yùn)算關(guān)系的逆運(yùn)算由于關(guān)系是序偶的集合，除了集合的普通運(yùn)算外由于關(guān)系是序偶的集合，除了集合的

13、普通運(yùn)算外，還有一些特有的運(yùn)算。，還有一些特有的運(yùn)算。定義定義4.114.11：設(shè)：設(shè)R R是是A A到到B B的關(guān)系，的關(guān)系，R R的逆關(guān)系或逆是的逆關(guān)系或逆是B B到到A A的關(guān)系，記為的關(guān)系，記為 ，定義為：，定義為：顯然對(duì)恣意顯然對(duì)恣意 ，有，有 ； 為為R R的關(guān)系矩陣，那么的關(guān)系矩陣，那么 . .例：例： ；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：設(shè)：設(shè)R R和和S S都是都是A A到到B B上的二

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

15、合A=0,1,2,3,4A=0,1,2,3,4，R R，S S均為均為A A上的二上的二元關(guān)系，且元關(guān)系，且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：設(shè)：設(shè)F F，G G，H H為恣意二元關(guān)系，那么為恣意二元關(guān)系，那么定理定理4.34.3：設(shè)：設(shè)R R為為A A上的關(guān)系，那么上的關(guān)系，那么定理定理4.44.4：設(shè)：設(shè)F F，G G，H H為恣意二元關(guān)系，那么為恣意二元關(guān)系，那么111).(2(),().(

16、1 (FGGFHGFHGF RRRIIRAA).2( ,).1 (.).(4(,)().3(,).(2(,)().1 (FHFGFHGHFGFHGFFHFGFHGHFGFHGF16/564.4.關(guān)系的冪運(yùn)算關(guān)系的冪運(yùn)算定義定義4.134.13：設(shè)：設(shè)R R是集合是集合A A上的二元關(guān)系，那么上的二元關(guān)系，那么R R的的n n次冪次冪 定義為：定義為：例例4-54-5：設(shè)：設(shè)A=0,1,2,3,4A=0,1,2,3,4，R=R=，。那么那么 = =，； = =，； = =，=nRRRRAxxxIRnnA10).2(,|,).1 (2R3R4R2R17/56定理定理4.54.5：設(shè)：設(shè)R R為為A

17、 A上的二元關(guān)系，上的二元關(guān)系，m m，n n為自然數(shù)，為自然數(shù)，那么那么證證(4)(4)：假設(shè)：假設(shè)n=0n=0時(shí)，那么有時(shí)，那么有 假設(shè)假設(shè)n=kn=k時(shí)，有時(shí)，有 ，那么，那么n=k+1n=k+1時(shí)時(shí)，有，有 命題成立。命題成立。定理定理4.64.6：設(shè)集合：設(shè)集合A A的基數(shù)為的基數(shù)為n n，R R是是A A上的二元關(guān)系上的二元關(guān)系，那么存在自然數(shù)，那么存在自然數(shù)i i，j j使得使得證明：我們知道，當(dāng)證明：我們知道，當(dāng)|A|=n|A|=n時(shí)，時(shí)，A A上的二元關(guān)系合上的二元關(guān)系合計(jì)計(jì) 個(gè)，令個(gè)，令k= k= ，因此在，因此在 這這k+1k+1個(gè)關(guān)個(gè)關(guān)11).1 (mnmnnnRRRR

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

19、對(duì)恣意的knkn，有，有 即可。對(duì)恣意的即可。對(duì)恣意的 ，那么由，那么由“的定義知：存在的定義知：存在 ，使得：，使得：.),20(,2jinRRjiji使iniiiRR11 iiiniRR11iniiiRR11 iniiniiiRRR111inikRR1 kRba ,Aaaak121,),(,012110baaaRaaRaaRaakkk令19/56由于由于|A|=n|A|=n，所以由鴿巢原理；，所以由鴿巢原理；k+1k+1個(gè)元素個(gè)元素 中至少有兩個(gè)元素一樣，無(wú)妨設(shè)為中至少有兩個(gè)元素一樣，無(wú)妨設(shè)為 ，那，那么可么可在在 中刪去中刪去 后仍有后仍有由關(guān)系的復(fù)合運(yùn)算得：由關(guān)系的復(fù)合運(yùn)算得： ，其中

20、，其中 ，此時(shí)：假設(shè)，此時(shí)：假設(shè) ，那么，那么 ；假設(shè)；假設(shè) ，那么反復(fù)上述做法，最終總能找到，那么反復(fù)上述做法，最終總能找到 ，使，使得得 ，即有，即有 ，由此，由此有有 ，由，由k k的恣意性的恣意性 ， kaa,0)(jiaajiRaaRaaRaakk,12110RaaRaaRaajjiiii,1211RaaRaaRaaRaaRaakkjjii,1112110,0kkRaaba)(ijkknk iniRba1,nk nk kkRaaba ,0iniRba1,inikRR1 iniiiRR11 iniiiRR11 20/565 5：集合在關(guān)系下的像：集合在關(guān)系下的像定義定義4.144.14

21、：設(shè)：設(shè)R R為二元關(guān)系，為二元關(guān)系，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：設(shè)：設(shè)F F為關(guān)系，為關(guān)系，A A，B B為集合，那么為集合，那么例例4-64-6：設(shè)：設(shè) ，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我們?cè)谘杏戧P(guān)系的性質(zhì)時(shí)，可以假定關(guān)系是某一非我們?cè)谘杏戧P(guān)系的性質(zhì)時(shí)，可以假定關(guān)系是某一非空集合上的二元關(guān)系，這一假設(shè)不失普通性。因空集合上的二元關(guān)系，這一假設(shè)不失普通性。因此任一此任一A A到到B B上的關(guān)系上的關(guān)系R R，即，即 ，而，而 ，所以關(guān)系，所以關(guān)系R R總可以看成是總可以看成是AB AB 上的關(guān)系，它與原關(guān)系上的關(guān)系，它與原關(guān)系R R具有完全一樣的序具有完全一樣的序偶，對(duì)它的討論替代對(duì)偶，對(duì)它的討論替代對(duì)R R的討論無(wú)損于問(wèn)題的本質(zhì)的討論無(wú)損于問(wèn)題的本質(zhì)1.1.關(guān)系的性質(zhì)關(guān)系的性質(zhì)定義定義4.154.15：設(shè)：設(shè)R R是是A A上的二元關(guān)系，即上

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

25、R是傳送的是傳送的(Transitive)(Transitive)例例4-74-7：設(shè)：設(shè)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在關(guān)系圖上：關(guān)系在關(guān)系圖上：關(guān)系R R是自反的，當(dāng)且僅當(dāng)其關(guān)系圖是自反的，當(dāng)且僅當(dāng)其關(guān)系圖中的每個(gè)節(jié)點(diǎn)都有環(huán)，關(guān)系中的每個(gè)節(jié)點(diǎn)都有環(huán)，關(guān)系R R是反自反的，當(dāng)且僅是反自反的，當(dāng)且僅當(dāng)其關(guān)

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

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

28、的；是傳遞的；是傳遞的；,)4(,)3(,)2(,) 1 (4321dccacbbaRcbbaaaRbaRcacbbaaaR26/56關(guān)系圖上：關(guān)系關(guān)系圖上：關(guān)系R R是傳送的當(dāng)且僅當(dāng)其關(guān)系圖中，是傳送的當(dāng)且僅當(dāng)其關(guān)系圖中，任何三個(gè)節(jié)點(diǎn)任何三個(gè)節(jié)點(diǎn)x, y, z(x, y, z(可一樣可一樣) )之間，假設(shè)從之間，假設(shè)從x x到到y(tǒng) y，y y到到z z均有一條邊，那么從均有一條邊，那么從x x到到z z一定有一條邊存一定有一條邊存在；在；關(guān)系矩陣上：關(guān)系關(guān)系矩陣上：關(guān)系R R是傳送當(dāng)且僅當(dāng)其關(guān)系矩陣中是傳送當(dāng)且僅當(dāng)其關(guān)系矩陣中，對(duì)恣意，對(duì)恣意2.2.利用集合運(yùn)算來(lái)判別關(guān)系的性質(zhì)利用集合運(yùn)算來(lái)

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

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

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

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

33、傳送閉包，傳送閉包t(R)t(R)為為“ ；定義在定義在N N上的上的“= =關(guān)系的自反閉包關(guān)系的自反閉包r(R)r(R)為為“= =，對(duì)稱閉，對(duì)稱閉包包s(R)s(R)為為“= =，傳送閉包，傳送閉包t(R)t(R)為為“= =。例例4-114-11：設(shè)集合：設(shè)集合A=a, b, cA=a, b, c，R=R=，是定義在是定義在A A上的二元關(guān)系，求上的二元關(guān)系，求r(R)r(R)，s(R)s(R)，t(R)t(R)并畫(huà)出并畫(huà)出R R，r(R)r(R)，s(R)s(R)，t(R)t(R)的關(guān)系圖，關(guān)系矩的關(guān)系圖，關(guān)系矩陣。陣。解：解： r(R)=,; r(R)=,;s(R)=,;s(R)=,

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

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

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

37、R); (2)集合集合A A上的關(guān)系上的關(guān)系R R的自反的自反傳送閉包定義為傳送閉包定義為rt(R)=r(t(R); (3)rt(R)=r(t(R); (3)集合集合A A上的關(guān)上的關(guān)系系R R的對(duì)稱傳送閉包定義為的對(duì)稱傳送閉包定義為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：設(shè)：設(shè)R R是集合是集合A A上的關(guān)系，那么上的關(guān)系，那么)()().3(),()().2(),()().1 (RtsRstRtrRrtRsrRrs34/564.5.14.5.1：集合和劃分：集合和

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

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

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

41、即 ，而，而 ，R R傳傳送送RR是是Z Z上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。 )(mod,|,myxZyxyxRZxRxxmxx,)(modZyx,)(mod,myxRyx即Rxymxy,modZzyx,RzyRyx,zymyxmmzymyx|,|),(mod),(modRzxzxmzyyxzx,|),()(37/56調(diào)查關(guān)系調(diào)查關(guān)系R R和集合和集合Z Z；R R將將Z Z分成了如下分成了如下m m個(gè)子集：個(gè)子集：這這m m個(gè)子集特點(diǎn)是：同一個(gè)子集中的元素之間都有關(guān)個(gè)子集特點(diǎn)是：同一個(gè)子集中的元素之間都有關(guān)系系R R，不同子集的元素之間無(wú)關(guān)系，不同子集的元素之間無(wú)關(guān)系R R，每?jī)蓚€(gè)子集，每?jī)蓚€(gè)子

42、集無(wú)公共元素，而一切子集的并正好為無(wú)公共元素，而一切子集的并正好為Z Z，構(gòu)成了，構(gòu)成了Z Z的一個(gè)劃分。的一個(gè)劃分。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：等價(jià)類與商集：等價(jià)類與商集定義定義4.204.20：設(shè)：設(shè)R R是非空集合是非空集合A A上的等價(jià)關(guān)系，對(duì)恣上的等價(jià)關(guān)系，對(duì)恣意意 ，稱集合，稱集合 為為x x關(guān)于關(guān)于R R的等的等價(jià)類價(jià)類(Equivale

43、nce Class)(Equivalence Class)，其中，其中x x稱為稱為 的生成的生成元，由于元，由于 中的任何兩個(gè)元素中的任何兩個(gè)元素a a，b b均相互等價(jià)，均相互等價(jià)，普通記作普通記作abab。例例4-134-13：設(shè)：設(shè)A=1,2,3,4,5,8A=1,2,3,4,5,8，思索，思索R R是是A A上的以上的以3 3為模的同余關(guān)系，求其等價(jià)類。為模的同余關(guān)系，求其等價(jià)類。解：從例解：從例4-124-12知，知，R R是一個(gè)等價(jià)關(guān)系，那么是一個(gè)等價(jià)關(guān)系，那么Ax|xRyAyyxRRxRxRR44 , 1 1 33 ,858 , 5 , 22RRRR39/56定理定理4.114

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

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

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

47、)(A)的的一個(gè)劃分塊，即一個(gè)劃分塊，即y y和和x x同屬于一個(gè)劃分塊，同屬于一個(gè)劃分塊， ，R R是對(duì)稱的；是對(duì)稱的；(3) (3) ，那么，那么x x，y y同同屬于屬于(A)(A)的一個(gè)劃分塊的一個(gè)劃分塊 ，y y，z z同屬于同屬于(A)(A)的的一個(gè)劃分塊一個(gè)劃分塊 ， ，而由于不同劃分塊的，而由于不同劃分塊的交集為空，交集為空， ，即，即x x和和z z屬于同一劃分塊，屬于同一劃分塊， RR是傳送的；是傳送的；RR為等價(jià)關(guān)系。為等價(jià)關(guān)系。假設(shè)設(shè)假設(shè)設(shè) ，那么，那么RyxAyx,若Rxy,RzyRyxAzyx,若iAjAjiAAyjiAA ,)(21mAAAA212211)()()

48、(imimmAAAAAAAR43/56有定理有定理4.12,4.134.12,4.13知，集合知，集合A A上的等價(jià)關(guān)系與集合上的等價(jià)關(guān)系與集合A A的劃分是一一對(duì)應(yīng)的，因此可以說(shuō)：劃分與等價(jià)的劃分是一一對(duì)應(yīng)的，因此可以說(shuō)：劃分與等價(jià)關(guān)系這兩個(gè)不同的概念本質(zhì)上是一樣的，即是同關(guān)系這兩個(gè)不同的概念本質(zhì)上是一樣的，即是同一個(gè)概念的兩種不同的表達(dá)方式。一個(gè)概念的兩種不同的表達(dá)方式。例例4-144-14：設(shè)：設(shè)A=1,2,3A=1,2,3，求，求A A上的一切等價(jià)關(guān)系。上的一切等價(jià)關(guān)系。解：先求解：先求A A的劃分：只需一個(gè)劃分塊的劃分為的劃分：只需一個(gè)劃分塊的劃分為1,2,31,2,3；具有；具有2

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

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

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

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

53、義的上定義的“ 和和“ 分別是偏序關(guān)系和擬序關(guān)系；分別是偏序關(guān)系和擬序關(guān)系；(2)(2)實(shí)數(shù)集合實(shí)數(shù)集合R R上定義的數(shù)的上定義的數(shù)的“小于等于關(guān)系，小于等于關(guān)系，“小小于關(guān)系，分別是偏序關(guān)系和擬序關(guān)系；于關(guān)系，分別是偏序關(guān)系和擬序關(guān)系；(3)(3)自然數(shù)集合自然數(shù)集合N N上定義的上定義的“整除關(guān)系，也是一個(gè)偏整除關(guān)系，也是一個(gè)偏序集合。序集合。定義定義4.224.22：設(shè)：設(shè)是一個(gè)偏序集，對(duì)是一個(gè)偏序集，對(duì) ，x x yy或或y xy x，那么稱，那么稱x x與與y y是可比的是可比的(Comparable),(Comparable),假設(shè)假設(shè)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，對(duì)，對(duì) ，x x與與y y都是可比的都是可比的，但，但x x不覆蓋不覆蓋y y，y y也不覆蓋也不覆蓋x x。(3)(3)偏序集偏序集ZZ，對(duì)，對(duì) ，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：偏序集的哈斯圖：偏序集的哈斯圖由于偏序關(guān)系本身具有自反，反對(duì)稱，傳送的性由于偏序關(guān)系本身具有自反，反對(duì)稱，傳送的性質(zhì)，在用關(guān)系圖來(lái)描畫(huà)偏序關(guān)系且不引起混淆，質(zhì)，在用關(guān)系圖來(lái)描畫(huà)偏序關(guān)系且不引起混淆，可以對(duì)其進(jìn)展簡(jiǎn)化，得到的圖叫做偏序圖或哈斯可以對(duì)其進(jìn)展簡(jiǎn)化，得到的圖叫做偏序圖或哈斯圖圖(Hasse)(Hasse)。

56、哈斯圖的作圖方法如下：哈斯圖的作圖方法如下：(1):(1):用小圓圈或點(diǎn)表示用小圓圈或點(diǎn)表示A A中的元素，省掉關(guān)系圖中中的元素，省掉關(guān)系圖中的一切環(huán)的一切環(huán)( (因自反性因自反性) )；(2):(2):對(duì)對(duì) ，假設(shè)，假設(shè)xyxy那么將那么將x x畫(huà)在畫(huà)在y y的下方，的下方，可省掉關(guān)系圖中一切邊的箭頭；可省掉關(guān)系圖中一切邊的箭頭；(3):(3):對(duì)對(duì) ，假設(shè)，假設(shè)y y覆蓋覆蓋x x，那么在，那么在x x與與y y之間連之間連條線，否那么無(wú)線相連。條線，否那么無(wú)線相連。Ayx ,Ayx ,50/56按按(1)(1)，(2)(2)，(3)(3)所作成的圖稱為哈斯圖。所作成的圖稱為哈斯圖。例例4-164-16：設(shè)：設(shè)A=2,3,6,12,24,36A=2,3,6,12,24,36，“是是A A上的整上的整除關(guān)系，畫(huà)出其普通關(guān)系圖和哈斯圖。除關(guān)系