離散數(shù)學(xué)二元關(guān)系

1、第5章 二元關(guān)系主要內(nèi)容 5.1 Cartesian積積5.2 關(guān)系的概念與表示關(guān)系的概念與表示5.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)5.4 逆關(guān)系和復(fù)合關(guān)系逆關(guān)系和復(fù)合關(guān)系5.5 關(guān)系的閉包關(guān)系的閉包5.6 有序關(guān)系有序關(guān)系5.7 相容關(guān)系與等價(jià)關(guān)系相容關(guān)系與等價(jià)關(guān)系5.8 關(guān)系數(shù)據(jù)庫初步關(guān)系數(shù)據(jù)庫初步5.1 Cartesian積（積（笛卡爾積）n定義定義5.1.1 設(shè)a1,a2,an是n個(gè)元素, 其有序排列用a1,a2,an 表示，稱為有序n元組，元組，或簡稱為n元組元組。其中ai稱為它的第i個(gè)分量兩個(gè)元素a1、a2組成的序列記作a1,a2, 稱為二重(元)組或序偶。a1和a2分別稱為二元組a1,a

2、2的第一和第二個(gè)分量。na,b=c,diff a=c且b=d。序偶、二元組n二元組中元素的次序是重要的例： 2,33,2na1,a2,an=b1,b2,bniff ai=bi, 1in笛卡爾積(Cartesian product)n定義定義5.1.2 設(shè)nN， A1,A2,An是n個(gè)集合，它們的Cartesian積(直積，叉積)記為A1A2An ，定義為A1A2An = a1,a2,an|aiAi1in對(duì)一切i, Ai=A時(shí), A1A2An 可簡記為Ann顯然AB BAn若存在i, Ai=, A1A2An =n如果所有Ai(i=1,2,n)都是有限集合, 則|A1A2An|=|A1|A2|A3

3、|An|例n設(shè)A=a,b, B=1,2,3, C=p,q, D=0, E=(a) AB=a,1,a,2,a,3,b,1,b,2,b,3(b) AB C =a,1,p,a,1,q,a,2,p,a,2,q,a,3,p,a,3,q,b,1,p,b,1,q,b,2,p,b,2,q,b,3,p,b,3,q(c) CD=p,0,q,0(d) D(C2)=Dp,p,p,q,q,p,q,q=0,p,p,0,p,q,0,q,p,0,q,q(e) DC C =0, p,p,0, p,q , 0, q,p , 0, q,q (f) AE=n定理定理5.1.1 設(shè)A 、B和C是三個(gè)集合，若C,則 ABACBC CAC

4、B證明(1):必要性：必要性：設(shè)AB，求證 ACBC任取ACBC則xA 且 yC由AB ，得xB 且 yC即：所以ACBC充分性：充分性：設(shè)ACBC ，求證AB任取xAxBy0C 使得 A C由ACBC ，得 B C即：所以AB綜上有ABACBC n定理定理5.1.2 設(shè)A、B、C、D為非空集合，則 ABCDACBD證明：首先,由ABCD 證明ACBD.任取xA，yB，所以 xAyBABCD (由ABCD )xCyD 所以, ACBD.其次, 由AC，BD. 證明ABCD任取AB AB xAyB xCyD (由AC，BD) CD 所以, ABCD 證畢.n定理定理5.1.3(1) A(BC)=

5、(AB)(AC) (2) (BC) A=(BA)(CA)(3) A(BC)=(AB)(AC)(4) (BC)A =(BA)(CA)(5) A(B-C)=(AB)-(AC) (6) (B-C) A=(BA)-(CA)(7) A(BC)=(AB) (AC) (8) (B C) A=(BA) (CA)證明證明(1) ：任取 A(BC) A(BC) xA yBC xA (yByC) ( xA yB)(xAyC) ABAC (AB)(AC)n笛卡爾積的應(yīng)用令A(yù)1=x|x是學(xué)號(hào) A2=x|x是姓名 A3=男,女 A4=x|x是出生日期 A5=x|x是班級(jí) A6 =x|x是籍貫 n A1A2A3 A4A5

6、A6是學(xué)生檔案數(shù)據(jù)庫的一條信息n學(xué)生的檔案是A1A2A3 A4A5 A6的一個(gè)子集令A(yù)=a,b,z是英文字母表，英文單詞可以看成n元組：nat=, boy=, data=, computer=natA2 ,boyA3,dataA4,computerA8,n英文詞典中的單詞集合可以看成是 AA2An 的一個(gè)子集5.2 關(guān)系的概念與表示關(guān)系的概念與表示 n關(guān)系一個(gè)非常普遍的概念n數(shù)值的大于關(guān)系、整除關(guān)系，人類的父子關(guān)系、師生關(guān)系、同學(xué)關(guān)系例1nA=a,b,c,d是某乒乓球隊(duì)的男隊(duì)員集合，B=e,f,g是女隊(duì)員集合. A和B之間的混雙配對(duì)關(guān)系：AB=|xAyB=,例2n令=1,2,3,4, A中元素

7、間的關(guān)系R ：R= , , , ,AAn定義定義5.2.1關(guān)系如果A1, A2, , An是集合，R A1A2An ，則稱R是定義在A1A2An上的n元關(guān)系；若R =，稱R為A1A2An上的空關(guān)系；若R = A1A2An ，稱R為A1A2An上的全關(guān)系如果 RAn，則稱R是A上的n元關(guān)系n定義定義5.2.2 二元關(guān)系二元關(guān)系設(shè)A、是集合，如果R AB，則稱R是一個(gè)從A到B的關(guān)系，記作： R ：AB；若RA2 ，則稱R是A上的二元關(guān)系n恒等關(guān)系A(chǔ)上的恒等關(guān)系IA定義為： IA AA，且IA =|xA 例A=1,2,3, 則IA =,n思考若R和S都是關(guān)系，且R=,， S=,， R= S？n錯(cuò)誤n

8、關(guān)系的相等R1是 A1 A2 An上 的 n 元 關(guān) 系 , R2是B1B2Bm上的m元關(guān)系.那么R1=R2,當(dāng)且僅當(dāng)n=m,且對(duì)一切i,1in,Ai=Bi,并且R1和R2是相等的有序n元組集合n二元關(guān)系簡稱為關(guān)系關(guān)系nR xRy 也稱之為x與y有R關(guān)系nR xRy 也稱之為x與y沒有R關(guān)系后綴表示法后綴表示法中綴表示法中綴表示法關(guān)系的定義域與值域n定義定義5.2.3 設(shè)R ：AB定義域定義域(domain)：由所有R的第一個(gè)分量組成的集合，稱為R的定義域，記作dom R，即 dom R=x|y(R) 值域值域(range)：由所有R的第二個(gè)分量組成的集合，稱為R的值域，記作ran R，即 r

9、an R=y|x(R)例： A=1,2,3,4, R AA，R= , ndom R =1,2nran R=1,2,3例nR是實(shí)數(shù)集合， R上的幾個(gè)關(guān)系x2+y2=4=xy關(guān)系矩陣和關(guān)系圖n關(guān)系矩陣有限集合之間的關(guān)系可以用矩陣表示便于用計(jì)算機(jī)來處理設(shè)A=a1, a2, , am，B=b1, b2, , bn是有限集， RAB， A到B的二元關(guān)系R可用mn階矩陣表示：MR=(rij)mn，其中rij= 1,如果aiRbj 0,如aiRbj 則稱矩陣MR=rij是R的關(guān)系矩陣n例A=a1,a2,B=b1,b2,b3nR是A到B的關(guān)系，R=, b1 b2 b3a1 1 0 1a2 1 1 0MR=1

10、0 11 1 0nS是B上的關(guān)系，S=, b1 b2 b3b1 1 0 1b2 1 1 0b3 0 1 0MS= 1 0 1 1 1 0 0 1 0n關(guān)系圖有向圖兩種情況nR ABnR AA例：設(shè)A=1,2,3,4,B=a,b,cnR AB，R= ,nS AA，S= ,1。2。 3。 4。A。B。abcGR:GS :1。4。23關(guān)系的集合運(yùn)算n關(guān)系就是集合n、-、和補(bǔ)運(yùn)算對(duì)關(guān)系也適用n特別的R=(AB)-R思考題n設(shè)A和B分別是n元和m元有限集，則共有多少個(gè)不同的A到B的關(guān)系？mn2n設(shè)A(和B)都是非空有限集，則A上的空關(guān)系、恒等關(guān)系和A上(A到B的)全關(guān)系的關(guān)系圖和關(guān)系矩陣有何特點(diǎn)。n怎樣

11、通過關(guān)系圖和關(guān)系矩陣求domR和ranR5.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)n最重要的一節(jié)最重要的一節(jié)n這里關(guān)系都是集合A上的關(guān)系n關(guān)系的性質(zhì)主要有自反性反自反性對(duì)稱性反對(duì)稱性傳遞性反傳遞性n定義定義5.3.1設(shè)R是A上的二元關(guān)系，如果對(duì)于xA都有R (xRx)，則稱R是A上的自反關(guān)系. 即 R是A上的自反關(guān)系x(xAxRx)例：A=1,2,3nR1=,不是自反關(guān)系nR2=,自反關(guān)系n空關(guān)系不是自反關(guān)系n全關(guān)系、恒等關(guān)系自反關(guān)系自反關(guān)系自反關(guān)系的特征n定理定理5.3.1 ：設(shè)R是集合A上的關(guān)系，則R具有自反性 iff IAR證明：必要性xA，由R自反知 R， IAR充分性xA，由IA的定義知 IA ，

12、 R，即R是自反的n自反關(guān)系的關(guān)系矩陣主對(duì)角線上的所有元素均為1n自反關(guān)系的關(guān)系圖每個(gè)結(jié)點(diǎn)都有自環(huán)線n令A(yù)=1,2,3，下列哪些關(guān)系是自反的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8反自反關(guān)系n 定義定義5.3.2設(shè)R是集合A上的關(guān)系，如果對(duì)于xA都有R ，則稱R為A上的反自反關(guān)系。即 R是A上的反自反關(guān)系x(xAR)例： A=1,2,3nS1=,不是反自反關(guān)系nS2=,反自反關(guān)系n空關(guān)系反自反關(guān)系反自反關(guān)系的特征n定理定理5.3.2 ：設(shè)R是集合A上的關(guān)系，則R具有反自反性 iff IAR=證明：必要性xA，由R反自反知

13、R， IAR=充分性假設(shè)R不是反自反的，即存在xA， R ，則 IAR ，與IAR=矛盾 n反自反關(guān)系的關(guān)系矩陣主對(duì)角線上的所有元素均為0n反自反關(guān)系的關(guān)系圖每個(gè)結(jié)點(diǎn)都沒有自環(huán)線n令A(yù)=1,2,3，下列哪些關(guān)系是反自反的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8思考題n設(shè)A是n元有限集共有多少個(gè)A上的不同的自反關(guān)系？共有多少個(gè)A上的不同的反自反關(guān)系？n是否存在滿足下列要求的關(guān)系，若有，請(qǐng)給出實(shí)例既自反又反自反既不自反又不反自反nn 22nn 22空集上的空關(guān)系空集上的空關(guān)系對(duì)稱關(guān)系n定義定義5.3.3設(shè)R是集合A上的關(guān)系，若

14、對(duì)任何x, yA,只要有xRy,就必有yRx,則稱R為A上的對(duì)稱關(guān)系，即 R是A上的對(duì)稱關(guān)系xy(xAyAxRy yRx)n例：鄰居關(guān)系，朋友關(guān)系A(chǔ)=1,2,3nR=,nIAn空關(guān)系n全關(guān)系對(duì)稱關(guān)系的特征n對(duì)稱關(guān)系的關(guān)系矩陣根據(jù)主對(duì)角線對(duì)稱n對(duì)稱關(guān)系的關(guān)系圖在兩個(gè)不同的結(jié)點(diǎn)之間，若有邊的話，則有方向相反的兩條邊（平行線）n令A(yù)=1,2,3，下列哪些關(guān)系是對(duì)稱的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8反對(duì)稱關(guān)系n定義定義5.3.4設(shè)R是集合A上的關(guān)系,若對(duì)x, yA,如果有xRy,和yRx,就有x=y,則稱R為A上的反對(duì)稱關(guān)

15、系 ，即R是A上的反對(duì)稱關(guān)系xy(xAyAxRyyRx)x=y) xy(xAyAxyxRy)y x)Rn例：A=1,2,3R1=,R2 =,IA空關(guān)系反對(duì)稱關(guān)系的特征n反對(duì)稱關(guān)系的關(guān)系矩陣以主對(duì)角線為對(duì)稱的兩個(gè)元素中最多有一個(gè)1n反對(duì)稱關(guān)系的關(guān)系圖兩個(gè)不同的結(jié)點(diǎn)之間最多有一條邊n令A(yù)=1,2,3，下列哪些關(guān)系是反對(duì)稱的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8思考題n是否存在滿足下列要求的關(guān)系，若有，請(qǐng)給出實(shí)例既對(duì)稱又反對(duì)稱既不對(duì)稱又不反對(duì)稱n設(shè)A是n元有限集共有多少個(gè)A上的不同的對(duì)稱關(guān)系？共有多少個(gè)A上的不同的反對(duì)稱關(guān)系？

16、共有多少個(gè)A上不同的既對(duì)稱又反對(duì)稱的關(guān)系？2222222nnnnn2232nnnIAn2傳遞關(guān)系n定義定義5.3.5 R是A上的關(guān)系，對(duì)x,y,zA,如果有xRy,和yRz,就有xRz,則稱R為A上的傳遞關(guān)系，即R是A上的傳遞關(guān)系xyz(xAyAzAxRyyRz)xRz)n例，=，A=1,2,3,4nR1=,nR2=,nIAn空關(guān)系，全關(guān)系傳遞關(guān)系的特征n傳遞關(guān)系的關(guān)系矩陣如果aij=1,且ajk=1,則aik=1n傳遞關(guān)系的關(guān)系圖如果有邊,則也有邊n令A(yù)=1,2,3，下列哪些關(guān)系是傳遞的1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R

17、7R8反傳遞關(guān)系n定義定義5.3.6 R是A上的關(guān)系，對(duì)x,y,zA,如果有xRy,和yRz,就有R,則稱R為A上的反傳遞關(guān)系，即R是A上的反傳遞關(guān)系xyz(xAyAzAxRyyRz)x z)Rn例A=1,2,3,4nR1=,nR2=,n空關(guān)系練習(xí)n設(shè)R是集合A上的一個(gè)自反關(guān)系,求證：R是對(duì)稱和傳遞的，iff 若, R,則 R證明：必要性: 已知R是對(duì)稱和傳遞的， 設(shè)R ，R，(要證明 R )因?yàn)镽對(duì)稱故R,又R 是傳遞的，且R得R充分性: 已知a,b,cA，若， R,則 R先證先證R對(duì)稱對(duì)稱： R，(要證明 R ) 因?yàn)镽是自反的,所以R，由R且R，根據(jù)已知條件得R ，即R是對(duì)稱的再證再證R

18、傳遞傳遞： a,b,cA 設(shè) R，R (要證明R )由R對(duì)稱,得R ，由R且R，根據(jù)已知條件得R 所以R是傳遞的n從下列各題給出的備選答案中選出正確的答案，并將其代號(hào)填入題后面的括號(hào)內(nèi)。(1) 設(shè)A=0,1,2,3，A上的關(guān)系R=,，則R是A.自反的 B. 對(duì)稱的 C. 反對(duì)稱的 D. 可傳遞的 ( )(2) 設(shè)R是整數(shù)集I上的關(guān)系，定義為當(dāng)且僅當(dāng)|i1-i2|10時(shí) ，i1Ri2，則R是A.自反的 B. 對(duì)稱的 C. 反對(duì)稱的 D. 可傳遞的 ( ) B A B n下圖給出了1,2,3上三個(gè)關(guān)系的關(guān)系圖，試對(duì)每一個(gè)圖所表示的關(guān)系的性質(zhì)作出判別，并將選中的性質(zhì)的代號(hào)填入相應(yīng)的括號(hào)內(nèi)A. 自反的

19、 B. 對(duì)稱的 C. 反對(duì)稱的 D. 傳遞的 E. 反自反則1是（ ）則2是（ ）則3是（ ） A AB B A A E E思考題n關(guān)系的性質(zhì)對(duì)于集合運(yùn)算是否保持封閉？即自反（反自反、對(duì)稱、反對(duì)稱、傳遞）關(guān)系的交、并、差、對(duì)稱差及補(bǔ)關(guān)系是否仍是自反（反自反、對(duì)稱、反對(duì)稱、傳遞）的？反對(duì)稱傳遞對(duì)稱反自反自反 R1R1R2R1-R2R1R2R1R2R1,R2不反對(duì)稱不反對(duì)稱反對(duì)稱不反對(duì)稱反對(duì)稱不傳遞不傳遞不傳遞不傳遞傳遞對(duì)稱對(duì)稱對(duì)稱對(duì)稱對(duì)稱不反自反反自反反自反反自反反自反不自反不自反不自反自反自反5.4 逆關(guān)系和復(fù)合關(guān)系逆關(guān)系和復(fù)合關(guān)系n定義定義5.4.1 逆關(guān)系設(shè)R是從A到B的二元關(guān)系,關(guān)系R的

20、逆(或叫R的逆關(guān)系)記為R-1(Rc),是一從B到A的二元關(guān)系,定義如下:R-1=|Rn例I上的關(guān)系“”集合族上的關(guān)系的逆是關(guān)系 空關(guān)系的逆是空關(guān)系(AB) -1 =BAIA -1 = IA R=,nR-1=,逆關(guān)系的關(guān)系圖和關(guān)系矩陣nR-1的關(guān)系圖將R關(guān)系圖的所有邊的方向顛倒n R-1的矩陣 R矩陣的轉(zhuǎn)置：M=(MR)T43110110000101RM341101010001011RMn定理定理5.4.1 設(shè)R, S都是從A到B的關(guān)系,那么下列各式成立:1.(R-1)-1=R2. RS iff R-1S-13. R=S iff R-1=S-14.(RS)-1 = R-1 S-1 5.(RS)

21、-1 = R-1 S-16.(R-S)-1 = R-1 -S-17.(RS)-1 = R-1 S-18. 11 RRn定理定理5.4.2 R是A上關(guān)系，則 R是對(duì)稱的，當(dāng)且僅當(dāng) R-1 =R R是反對(duì)稱的，當(dāng)且僅當(dāng) RR-1 IA證明： 充分性，已知 R-1 =R (證明R對(duì)稱) 任取x,yA 設(shè)R,則R-1,而R-1 =R 即有R ，所以R對(duì)稱必要性，已知R對(duì)稱，(證明R-1 =R)先證R-1R，任取R-1,則R,又R對(duì)稱所以有R，所以R-1R。再證R R-1，任取R, 因R對(duì)稱，所以有R，則RC, 所以RR-1。綜上R-1 =R證明 充分性，已知RR-1IA，(證明R反對(duì)稱) 任取x,yA

22、 設(shè)R 且R，則R 且 R-1，所以RR-1 ，因?yàn)镽R-1IA所以 IA ，即x=y 所以R反對(duì)稱必要性，已知R反對(duì)稱，(證明RR-1 IA) 任取RR-1 則R 且 R-1 即R 且 R因?yàn)镽反對(duì)稱，所以x=y 即IA 所以RR-1 IA復(fù)合關(guān)系復(fù)合關(guān)系n定義定義5.4.2 設(shè)R是從A到B的關(guān)系， S是從B到C的關(guān)系，則R和S的復(fù)合關(guān)系是從A到C的關(guān)系，用 (RS)表示，可簡記為RS，定義為： R S =|xAzCy(yBRS)例nR兄妹關(guān)系，S母子母子關(guān)系， RS舅舅和外甥舅舅和外甥關(guān)系nA=1,2,3,4,B=2,3,4,C=1,2,3, R是A到B的關(guān)系;S是B到C的關(guān)系R=x+y=

23、6=,S=y-z=1=,R S=,練習(xí)nA=1,2,3 B=1,2,3.4 C=1,2,3,4,5R AB S BCR=, S=, 求 R S=, 。C123。41。2。 3。A1。2。 3。A。B123。4RS5 。C123。45SRn設(shè)A=1,2,3,4,5,R和S都是A上二元關(guān)系.如果R=,S=,求RS，SR ，(RS)R ，R(SR) ，RR ，SSRS=,SR=,(RS)R=R(SR)=RR=,SS=, 不滿足交換律滿足結(jié)合律？復(fù)合關(guān)系的矩陣表達(dá)n為了討論復(fù)合關(guān)系的關(guān)系矩陣，引入/矩陣的復(fù)合運(yùn)算n定義定義5.4.3 設(shè)MR=aij是nm的/矩陣, MS=bij是mp的/矩陣.則MRS

24、=cij=MRMS,這里是邏輯乘,是邏輯加，否則。為真；，若0) 11(11kjikmkijbacn定理定理5.4.3 設(shè)A=a1, a2, an, B=b1, b2, bm, C=c1, c2, cp, R是從A到B的關(guān)系， S是從B到C的關(guān)系。則MRS=MRMSn例：設(shè) X=1,2, Y=a,b,c, Z=, R是X到Y(jié)的關(guān)系， S是Y到Z的關(guān)系， R=, S=,則100011RM101010SM1010101010100011SRM關(guān)系復(fù)合運(yùn)算的性質(zhì)n定理定理5.4.4設(shè)R是A到B的二元關(guān)系,IA,IB分別是A和B上的相等關(guān)系,則IAR=RIB=Rn例：令A(yù)=1,2,3, B=a,b,c

25、,d1。2。 3。AIA。Babc。dR1。2。 3。ARIB。abc。d。Babc。d1。2。 3。ABn定理定理5.4.5設(shè)R1是從A到B的關(guān)系,R2和R3是從B到C的關(guān)系,R4是從C到D的關(guān)系,則1.若R2R3 那么 R1R2R1R3且 R2R4R3R42. R1(R2R3)=R1R2R1R33. (R2R3)R4=R2R4R3R44. R1(R2R3)R1R2R1R35.(R2R3)R4R2R4R3R46.(R1R2)-1R2-1R1-1證明(1) R1R2則b，b B使得 aR1b 且 bR2c R2 R3 bR3c即 R1R3 R1R2 R1R3 類似可證R2R4 R3R4證明(2

26、) 任取R1(R2R3) b(bBR1R2R3)b(bBR1(R2R3)b(bBR1R2) (bBR1R3)b(bBR1R2) b(bBR1R3)R1R2R1R3(R1R2)(R1R3)所以R1(R2R3)=(R1R2)(R1R3)證明(4) 任取R1 (R2R3) b(bBR1R2 R3)b(bBR1(R2 R3)b(bBR1R2) (bBR1 R3)b(bBR1R2) b(bBR1 R3)R1R2 R1 R3(R1R2)(R1R3)所以 R1 (R2 R3) (R1R2)(R1R3)n定理定理5.4.6設(shè)R1和R2是由A到B的關(guān)系， S1和S2是由B到C的關(guān)系，若 R1 R2 , S1 S

27、2 ,則 R1S1 R2S2n定理定理5.4.7設(shè)R1是從A到B的關(guān)系,R2是從B到C的關(guān)系,R3是從C到D的關(guān)系,則 (R1R2)R3=R1(R2R3) (復(fù)合運(yùn)算滿足結(jié)合律) 證明：R1 (R2 R3)b(bB R1 R2 R3)b(bB R1 c(cC R2 R3)bc(bB R1 (cC R2 R3)cb(cC(bB R1 R2 R3)c (cCb(bB R1 R2) R3)c (cC R1 R2) R3)(R1 R2) R3關(guān)系R的冪n當(dāng)R是A上的一個(gè)關(guān)系時(shí),R可與自身合成任意次而形成A上的一個(gè)新關(guān)系，即 RR=R2， R2R=RR2 =R3，n定義定義5.4.4設(shè)R是集合A上的二元

28、關(guān)系,nN,那么R的n次冪記為Rn,定義如下: (1) R0 =IA(2) Rn=Rn-1Rn定理定理5.4.8 設(shè)R是A上的關(guān)系, m,n Z,那么 (1) (Rn)-1=(R-1) n (2) RmRn=Rm+n (3) (Rm)n=Rmnn定理定理5.4.9 設(shè)R是n元有限集A上的關(guān)系,那么s,tZ，使Rs=Rt而 0st22n證明：為方便起見，記mn22因?yàn)榭偣仓挥衜個(gè)定義在n元有限集A上的不同的關(guān)系，所以以下m+1個(gè)R的方冪 R0, R1, R2, Rm之中，必有相同者。所以存在s和t， 0stm 使 Rs=Rt鴿巢原理（抽屜原則）n定理定理5.4.10設(shè)R是集合A上的一個(gè)二元關(guān)系.

29、若s,tZ, st,使Rs=Rt.記p=t-s,那么(a) 對(duì)所有iZ, Rs+i=Rt+i(b) 對(duì)所有k,i Z, Rs+kp+i=Rs+i(c) 對(duì)任意qZ,皆有RqR0,R1,R2,Rt-1證明(a)：i. i=0時(shí)，Rs=Rtii. 設(shè)i=n時(shí)，Rs+n=Rt+n則i=n+1時(shí)，Rs+n+1=Rs+nR=Rt+nR=Rt+n+1得證證明(b)：i. i=0時(shí)，證明Rs+kp=Rs k=0時(shí)， Rs=Rs設(shè)k=m時(shí)，Rs+mp=Rs則k=m +1時(shí)，Rs+(m+1)p=Rs+mpRp=RsRp=Rs+p=Rs+t-s=Rt=Rsii. 設(shè)i=n時(shí)，Rs+kp+n=Rs+n則i=n+1時(shí)

30、，Rs+kp+n+1=Rs+kp+nR=Rs+nR=Rs+n+1得證證明(c)：只需證q t時(shí), RqS由q t s, 必存在i,jZ使得q=s+ip+j (0jp-1)因?yàn)?i. q=t時(shí)，t=s+1*p+0 =s+t-s ii. 設(shè)q=n時(shí)，存在i,j使得k=s+ip+j (0td-1)則q=n+1時(shí), n+1=s+ip+j +1, 分兩種情況討論情況1: jp-1, 則i和j +1就是要求的兩個(gè)數(shù)情況2: j=p-1, 則j+1=p， n+1=s+(i+1)p+0, 即i+1和0是要求的兩個(gè)數(shù)總之，存在i,jZ使得q=s+ip+j (0jp-1)由(b)知Rq=Rs+ip+j=Rs+j

31、且jp-1，則 s+j s+p-1= s+t-s-1= t-1即 Rq=Rs+j R0,R1,R2,Rt-1n定理定理5.4.11 設(shè)R是集合A上的關(guān)系，則1.R是傳遞的 iff R2R2.R是反傳遞的 iff R2R=證明1：必要性 R2t, 使得xRt 且 tRy又R是傳遞的，所以xRy，即R2R 充分性 x,y,z A, 若xRy 且 yRz，則 R2 R2R ， R， 即R是傳遞的例n設(shè)A=a,b,c,d,R=,求R0, R2, R3, R4R0=, R2=, R3=, R4=,nR4=R2,根據(jù)定理3.25(c)對(duì)nN, RnR0,R1,R2,R3易證R5=R3,R6=R4=R2用歸

32、納法可得R2n+1=R3和R2n=R2 (n1)思考題n關(guān)系的性質(zhì)對(duì)于復(fù)合運(yùn)算和逆是否保持封閉？即自反（反自反、對(duì)稱、反對(duì)稱、傳遞）關(guān)系的復(fù)合關(guān)系和逆關(guān)系是否仍是自反（反自反、對(duì)稱、反對(duì)稱、傳遞）的？反對(duì)稱傳遞對(duì)稱反自反自反R1-1R1R2R1,R2反對(duì)稱不反對(duì)稱傳遞不傳遞對(duì)稱不對(duì)稱反自反不反自反自反自反5.5 關(guān)系的閉包關(guān)系的閉包n例1。2。31。2。31。2。31。2。3n定義定義5.5.1 設(shè)R是A上的二元關(guān)系, 若有A上的關(guān)系R,滿足：(i) RR(ii) R是自反的(對(duì)稱的、傳遞的)(iii) 對(duì)于任何A上自反(對(duì)稱、傳遞)的關(guān)系R”, 如果RR”, 就有RR”則稱R是R的自反(對(duì)稱

33、、傳遞)閉包。記作r(R)、(s(R) 、t(R) (reflexive、 symmetric、transitive)nR的自反(對(duì)稱,傳遞)閉包是包含R并且具有自反(對(duì)稱,傳遞)性質(zhì)的最小關(guān)系閉包的性質(zhì)n定理定理5.5.1 設(shè)R是集合A上的二元關(guān)系(a)R是自反的當(dāng)且僅當(dāng)r(R)=R(b)R是對(duì)稱的當(dāng)且僅當(dāng)s(R)=R(c)R是傳遞的當(dāng)且僅當(dāng)t(R)=R證明(a)：充分性顯然必要性：由閉包的定義Rr(R)又RR ，且R是自反的根據(jù)閉包的極小性，有r(R )R則r(R) =R閉包的計(jì)算n定理定理5.5.2 設(shè)R是非空集A的關(guān)系,則(1) r(R)=RIA(2) s(R)=RR-1(3) 231

34、( )iit RRRRR證明(1): 設(shè)R =R IA.顯然, R是自反的，且R R. 假設(shè)R是A上的自反關(guān)系且R R.因R是自反的,所以R IA,又R R,所以R R IA =R所以,R=r(R). 證畢1iiRR證明(2): 設(shè)R =R R-1 (i) 顯然R R(ii) 又 (R R-1 ) -1 = R-1 R= R R-1 R是對(duì)稱的(iii)假設(shè)R是A上的對(duì)稱關(guān)系且R R 則 R-1 R-1 R =R R-1 R 綜上， s(R)= R=RR-1證明(3):令R= RR2R3., （只需證明t(R) R 且 R t(R)）(i) 先證t(R) R (利用閉包的極小性)顯然 R R(

35、再證明R是傳遞的) x,y,zA, 設(shè)有R, R, 由R定義得必存在整數(shù)i, j使得Ri , Rj , 則Ri+jR, 所以R, R傳遞由閉包的極小性可得t(R) R (ii) 再證 Rt(R)Rt(R) R2t2(R) t(R)則R3 = R2R t2(R)t(R) t2 (R) t(R) 這個(gè)過程可以一直進(jìn)行下去，即得Rit(R) Rt(R)綜合(i)(ii) R=t(R)例(a)整數(shù)集合I上的關(guān)系的自反閉包是,對(duì)稱閉包是關(guān)系,傳遞閉包是關(guān)系自身(b)整數(shù)集合I上的關(guān)系的自反閉包是自身,對(duì)稱閉包是全域關(guān)系,傳遞閉包是自身(c)的自反閉包是全域關(guān)系,對(duì)稱閉包是,的傳遞閉包是全域關(guān)系(d)空關(guān)

36、系的自反閉包是恒等關(guān)系,對(duì)稱閉包和傳遞閉包是自身(e)設(shè)R是I上的關(guān)系,xRy當(dāng)且僅當(dāng)y=x+1,那么t(R)是關(guān)系n定理定理5.5.3 設(shè)R是n元有限集A上的關(guān)系,則存在自然數(shù)kn，使得ikiRRt1)(證明：顯然iiikiRRtR11)(只需證ikiiiRRRt11)(a,bA, 若t(R), 則存在自然數(shù)p使得Rp, 即存在序列x1,x2,xp-1滿足aRx1, x1Rx2, xp-1Rb若滿足上述條件的最小p值大于n，則由于A是有限集，必存在s,t使得 xs=xt ，其中0s tp，因此可得到 aRx1, x1Rx2, xsRxt+1 , ,xp-1Rb即Rp-(t-s), 與p是最小

37、的假設(shè)矛盾例nA=1,2,3， A上關(guān)系R1,R2,R3,如下：(1) R1=,(2) R2 =,(3) R3 =,求它們的傳遞閉包解：(1) R12 = R13 = t(R)= R1 R12 R13= R1 (2) R22 =, R23 =, =IA R24 = R23 t(R)= R2 R22 R23閉包的性質(zhì)n定理定理5.5.4設(shè)R和S都是集合A上的關(guān)系且RS ，則(a)r(R)r(S)(b)s(R)s(S)(c)t(R)t(S)證明(a)：顯然r(S)是自反的，且RS r(S)，由閉包的極小性可知r(R)r(S) 閉包的應(yīng)用n例：傳遞閉包在語法分析中的應(yīng)用設(shè)有一字母表V = A ,B

38、, C,D , e, d , f . 假設(shè)文法G 為(1)A A f ; (2)B D d e; (3)C e; (4)A B ;(5)B D e; (6)D B fR 為定義在V 上的二元關(guān)系, (x i, x j ) R 表示從x i 出發(fā)用一條規(guī)則推出一串字符, 使其第一個(gè)字母恰好為x jt(R): 每個(gè)字母連續(xù)使用文法可能推出的頭字符.n定理定理5.5.5 (a)如果R是自反的,那么s(R)和t(R)都是自反的(b)如果R是對(duì)稱的,那么r(R)和t(R)都是對(duì)稱的(c)如果R是傳遞的,那么r(R)是傳遞的證明(c)：證明R是傳遞的,那么r(R) 是傳遞的 r2(R) =(RIA)2=(

39、RIA) (RIA) = R2R R IA = R IA( R是傳遞的， R2 R) = r(R) r(R) 是傳遞的n定理定理5.5.6 設(shè)R是集合A上的二元關(guān)系,那么(a)rs(R)=sr(R)(b)rt(R)=tr(R)(c)st(R)ts(R)證明(a)： Rs(R) r(R)rs(R)，sr(R)srs(R) rs(R)是對(duì)稱的（定理3.39） srs(R)= rs(R) 即得sr(R)rs(R) 同理可證rs(R)sr(R) sr(R)=rs(R) n通常將t(R) 記成R+， tr(R)記成R*，即t(R)= R+=RR2.Rn= tr(R)=rt(R) =R*= R0RR2.R

40、n=Rii=1Rii=05.6 有序關(guān)系有序關(guān)系n常遇到的重要關(guān)系n例數(shù)值的、關(guān)系集合的、關(guān)系圖書館的圖書按書名的字母次序排序詞典中的字(詞)的排序計(jì)算機(jī)中文件按文件名排序程序按語句次序執(zhí)行.偏序關(guān)系n定義定義5.6.1如果集合A上的二元關(guān)系R是自反的,反對(duì)稱的和傳遞的,那么稱R為A上的偏序關(guān)系偏序關(guān)系,或稱半序關(guān)系稱序偶為偏序集偏序集n通常，把偏序關(guān)系R記作,如果,則記作ab,讀作“a小于等于b”n注意注意：定義中的“”不是指普通中的實(shí)數(shù)中的大小關(guān)系的,而是一般的偏序關(guān)系例n設(shè)集合Aa,b,c,A上的關(guān)系R,判斷R是否是偏序關(guān)系。n設(shè)A是非零自然數(shù)集,DA是A上的整除關(guān)系,判斷DA是否是偏序

41、關(guān)系n設(shè)A是一個(gè)集合，則集合的“包含”關(guān)系是否是其冪集上的偏序關(guān)系（是）（是）（是）例nA=1,2,4,62。1。64擬序關(guān)系n定義定義5.6.2如果集合A上的二元關(guān)系R是反自反的和傳遞的,那么稱R為A上的擬序關(guān)系擬序關(guān)系, 稱序偶為擬序擬序集集（嚴(yán)格偏序）n通常，把擬序關(guān)系R記作,如果,則記作ab,讀作“a小于b”n例實(shí)數(shù)集合中的是擬序關(guān)系集合的是擬序關(guān)系n定理定理5.6.1 擬序關(guān)系是反對(duì)稱的證明：設(shè)R是A上的擬序關(guān)系假設(shè)R不是反對(duì)稱的，則x,yA, xy, xRy且yRx，由R的傳遞性得xRx，與R反自反矛盾 R反對(duì)稱n定理定理5.6.2 在集合A上,(a)如果R是一擬序關(guān)系,那么r(R

42、)=RIA是偏序關(guān)系(b)如果R是一偏序關(guān)系,那么R- IA是擬序關(guān)系n定義定義5.6.3 可比較設(shè)是偏序集， a,bA ,如果ab或ba有一式成立，便稱a和b是可比較的n定義定義5.6.4 全序集線序集在偏序集中.如果a,bA, a，b均可比較.那么叫做A上的線序關(guān)系(或全序關(guān)系),這時(shí)的序偶叫做線序集或全序集、鏈.全序集2。1。84。哈斯圖(Hasse)n描述偏序集的關(guān)系圖,可以簡化簡化為哈斯圖哈斯圖n簡化規(guī)則用小圓圈代表元素如果xy,并且xy,則將代表y的小圓圈畫在代表x的小圓圈的上方若xy ，且在A中不存在任何其它元素z，使得xz, zy ( x是y的直接前輩，或y是x的直接后裔)，則

43、有一條由x到y(tǒng)的連線直接前輩/直接后裔n定義定義5.6.5 設(shè)是偏序集， a,bA(ab) ,如果ab且不存在cA(ca,b)使得 ac和cb同時(shí)成立。則稱a是b的直接前輩(元素)，或稱b是a的直接后裔(元素)。 例2。1。642。1。84。6。4。練習(xí)1.設(shè)A=a,b,c，則“”關(guān)系是(A)上的偏序關(guān)系，則(A),R)是偏序集,畫出其哈斯圖2.設(shè)A =2,3,6,12,24,36,畫出的哈斯圖nA=1,2,12,的哈斯圖偏序集中的重要元素n定義定義5.6.6 極小元與極大元：設(shè)是一偏序集合,B是A的非空子集若存在元素bB,使得B中沒有沒有元素x滿足xb且xb,則稱b為B的一個(gè)極小元極小元若存

44、在元素bB,使得B中沒有沒有元素x滿足xb且bx,則稱b為B的一個(gè)極大元極大元n定義定義5.6.7 最小元與最大元：設(shè)是一偏序集合,B是A的非空子集如存在元素bB,使得xB,均有bx,則稱b為B的最小元最小元如存在元素bB,使得xB,均有xb,則稱b為B的最大元最大元例n設(shè)的哈斯圖如下所示：討論當(dāng)B取相應(yīng)集合時(shí)，其最大元,最小元,極大元,極小元abcdefghia,ba,b無無無無a,bc無無cB極小元極小元極大元極大元最小元最小元最大元最大元a,ba,b,cabcdefghiB極小元極小元極大元極大元最小元最小元最大元最大元a,b,c,db,c,d,fa,c,f,ia,bc,d無無無無bfb

45、faiai幾點(diǎn)說明n對(duì)于有限集，極大(小)元總是存在的n最大(小)元可能不存在n極大(小)元未必是最大(小)元n極大(小)元未必是唯一的n如果B存在最大(小)元x,則x就是B的極大(小)元n孤立點(diǎn)則又是極大元,也是極小元n定理定理5.6.3 設(shè)是一偏序集，且BA,如果B有最大(最小)元，那么它是唯一的證明：假設(shè)a和b都是B的最大元,那么ab和ba.則a=b(是反對(duì)稱性的)類似可證最小元的唯一性n定義定義5.6.8 上界與下界，上確界與下確界：設(shè)是一偏序集,B是A的子集如存在aA,使得xB,均有xa,則稱B有上界，并稱a為B的一個(gè)上界上界(Upper Bound )如存在aA,使得xB,均有ax

46、,則稱B有下界，并稱a為B的一個(gè)下界下界(Lower Bound )若a是B的上界，并且對(duì)B的每一個(gè)上界a皆有a a，則稱 a是B的上確界上確界 (最小上界，Least Upper Bound )，記作lub若a是B的下界，并且對(duì)B的每一個(gè)下界a皆有 a a，則稱 a是B的下確界下確界 (最大下界 ，Greatest Lower Bound ) ，記作glbabcdefghiB上界上界下界下界上確界上確界下確界下確界a,ba,b,cc,d,e,f,g,h,i無無無無無無c,e,f,h,i無無c無無abcdefghiB上界上界下界下界上確界上確界下確界下確界a,b,c,db,c,d,fa,c,f

47、,if, h,i無無f無無f,h,ibfbiaia練習(xí)n給定一偏序關(guān)系的Hasse圖。12。24。36。最大元上界上確界下界A6,12,241,2,32,3下確界最小元極大元極小元B無24無無無246,12,24,366,12,24,36無246611,2,3,6111124,36166246112,311無2,32,3良序集n定義定義5.6.9設(shè)是一偏序集,且A的每一非空子集B都有最小元, 則稱為良序集n定理定理5.6.4 設(shè)是一偏序集，則是良序集的充分必要條件為： 1.是上的全序關(guān)系； 2.A的每個(gè)非空子集都有極小元 思考題n證明或用反例否定下列命題(1)每一個(gè)偏序關(guān)系的逆都是偏序關(guān)系(2

48、)每一個(gè)擬序關(guān)系的逆都是擬序關(guān)系(3)每一個(gè)全序關(guān)系的逆都是全序關(guān)系(4)每一個(gè)良序關(guān)系的逆都是良序關(guān)系有序關(guān)系與拓?fù)渑判騨有序關(guān)系形式化了排序、順序或排列這個(gè)集合的元素的直覺概念n有序關(guān)系的關(guān)系圖可對(duì)應(yīng)一個(gè)有向無環(huán)圖(DAG)n在圖論中，DAG的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿足下列條件時(shí)，稱為該圖的一個(gè)拓拓?fù)渑判驌渑判?Topological sorting)每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次； 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑有序關(guān)系與拓?fù)渑判騨拓?fù)渑判蚴菍?duì)DAG的頂點(diǎn)的一種排序，它使得如果存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在排序中B出現(xiàn)在A的后面 nDAG經(jīng)常用于說明事件發(fā)生的

49、先后次序 將DAG的每一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)事件，圖中存在從A指向B的邊表示事件A是事件B的一個(gè)前提條件。這樣組成的圖叫做AOV（Activity on Vertex）網(wǎng)。對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判颍恳粋€(gè)排序結(jié)果表示一種可行的做事的先后順序 有序關(guān)系與拓?fù)渑判騨例：早晨穿衣的過程undershortpantsbeltshirttiejacketsocksshoeswatchsocks undershortpantsshoes watchshirtbelttiejacket有序關(guān)系與拓?fù)渑判騨DAG拓?fù)渑判蛩惴?.開始時(shí)，置圖G1=G，q為空序列； 2.如果圖G1是空?qǐng)D，則拓?fù)渑判蛲瓿?，算法結(jié)束，得到的

50、序列q就是圖G的一個(gè)拓?fù)渑判颍?3.在圖G1中找到一個(gè)沒有入邊（即入度為0）的頂點(diǎn)v，將v放到序列q的最后（這樣的頂點(diǎn)v必定存在，否則圖G1必定有圈；因?yàn)閳DG有圈，故不是DAG）； 4.從圖G1中刪去頂點(diǎn)v以及所有與頂點(diǎn)v相連的邊e（通過將與v鄰接的所有頂點(diǎn)的入度減1來實(shí)現(xiàn)），得到新的圖G1，轉(zhuǎn)到第二步 5.7 相容關(guān)系與等價(jià)關(guān)系相容關(guān)系與等價(jià)關(guān)系n定義定義5.7.1 相容關(guān)系如果集合A上的關(guān)系R是自反的和對(duì)稱的,那么稱R是相容關(guān)系。若aRb，則稱a,b是相容的；否則稱a,b不相容例n全關(guān)系n恒等關(guān)系n非空集合之間的“相交不為空”關(guān)系n日常生活中的“同班同學(xué)”關(guān)系 相容關(guān)系的簡化關(guān)系矩陣和關(guān)系

51、圖 n相容關(guān)系關(guān)系矩陣的特點(diǎn)關(guān)系矩陣的主對(duì)角線元素都是矩陣對(duì)稱可將矩陣用梯形(三角矩陣)表示 n相容關(guān)系關(guān)系圖的特點(diǎn)每個(gè)結(jié)點(diǎn)都有自環(huán)線任兩個(gè)相容的元素對(duì)應(yīng)的結(jié)點(diǎn)間的連線都成對(duì)出現(xiàn) 不畫自環(huán)線，并且把每對(duì)有向線改為一條無向邊 相容關(guān)系的簡化關(guān)系矩陣和關(guān)系圖n例5.7.1：設(shè)A是由五個(gè)英文單詞組成的集合：A=cat, cow, dog, let, net，定義A上的關(guān)系為： xRy iff x和y中含有相同的字母，則R是A上的相容關(guān)系 letdogcowcatnetletdogcow1001001101相容類 n定義定義5.7.2 設(shè)R是非空集合A上的相容關(guān)系， SA ，如果對(duì)于S中的任意元素a和

52、b皆有aRb ，則稱S為一個(gè)關(guān)于R的相容類。n定義定義5.7.3 設(shè)R是非空集合A上的相容關(guān)系， S是一個(gè)關(guān)于R的相容類。若S不真包含在任何其它的相容類中，則稱S是關(guān)于R的一個(gè)極大相容類。極大相容類與團(tuán)n例：A=1,2,3,4,5,6,7上的相容關(guān)系 R極大相容類：1,2,3,4 2,53,65,6,7“團(tuán)”極大的完全子圖 “團(tuán)團(tuán)”求極大相容類的算法1.列出R的簡化關(guān)系矩陣，令其中的元素為ij；2.R的n級(jí)相容類為a1, a2, , an ；3.若n =1，則終止；4.若n 1 ，則i = n -1 ；5.A=aj| i 1 ，則i = i -1 ，并轉(zhuǎn)到；9.若i = 1 ；則終止全過程。

53、n=7,第第級(jí)相容類：級(jí)相容類：1,2,3,4,5,6,7從第列開始掃描，從第列開始掃描，7，添加，添加6,7，刪去，刪去6和和7得到級(jí)相容類：得到級(jí)相容類：1,2,3,4,5,6,7對(duì)第列，對(duì)第列，6,7，添加，添加 5,6,7，刪去，刪去5和和6,7得到級(jí)相容類：得到級(jí)相容類：1,2,3,4,5,6,7對(duì)第列，對(duì)第列，級(jí)相容類與級(jí)相容類相同。，級(jí)相容類與級(jí)相容類相同。對(duì)第列，對(duì)第列，4,6，添加，添加 3,4及及3,6，刪去，刪去3和和4得到級(jí)相容類：得到級(jí)相容類：1,2,3,4,3,6,5,6,7對(duì)第列，對(duì)第列，3,4,5，添加，添加 2,3,4、2,3及及2,5，刪去，刪去2、2,3和

54、和3,4， 這樣得到級(jí)相容類：這樣得到級(jí)相容類：1,2,3,4,2,5,3,6,5,6,7對(duì)第列，對(duì)第列，2,3,4，添加，添加 1,2,3,4、1,2及及1,3，刪去，刪去1、1,2、1,3和和2,3,4，這樣得到級(jí)相容類，即關(guān)于，這樣得到級(jí)相容類，即關(guān)于R的所有極大相容類：的所有極大相容類：1,2,3,4,2,5,3,6,5,6,7例654321110000710100600105111411312等價(jià)關(guān)系n定義定義5.7.4如果集合A上的二元關(guān)系R是自反的,對(duì)稱的和傳遞的,那么稱R是等價(jià)關(guān)系例n全關(guān)系n恒等關(guān)系n同學(xué)集合A=a,b,c,d,e,f,g,A中的關(guān)系R是“住在同一房間”n集合

55、A=1,2,3,4,5,6,7, R=|x-y可被3整除(或x/3與y/3的余數(shù)相同)n設(shè)k是一正整數(shù)而a,bZ.如果對(duì)某整數(shù)m,a-b=mk,那么a和b是模k等價(jià),寫成ab(mod k)等價(jià)關(guān)系的關(guān)系矩陣與關(guān)系圖n關(guān)系矩陣可簡化為三角矩陣n關(guān)系圖每一結(jié)點(diǎn)都有一自環(huán)線（可省略）如果有從a到b的弧,那么也有從b到a的?。僧嫵蔁o向圖）如果從a到c有一條路徑,則從a到c有一條弧nA=1,2,3,4,5,6,7, R是模3等價(jià)關(guān)系，畫出其簡化關(guān)系圖2。5。1。4。7。3。6。等價(jià)關(guān)系等價(jià)關(guān)系R R的有向圖可能由若干個(gè)獨(dú)立子圖的有向圖可能由若干個(gè)獨(dú)立子圖構(gòu)成的，每個(gè)獨(dú)立子圖都是完全關(guān)系圖構(gòu)成的，每個(gè)獨(dú)立子圖都是完全關(guān)系圖( (團(tuán)團(tuán)) )判斷下圖中哪些是等價(jià)關(guān)系A(chǔ)=1,2,31。2。1。2。331。2。1。2。1。2。1。2。3333R2R1R5R61。2。1。2。33R3R4R7R8等價(jià)類n定義定義5.7.5 R是A上的等價(jià)