離散數(shù)學二元關系

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

2、2的第一和第二個分量。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 設nN， A1,A2,An是n個集合，它們的Cartesian積(直積，叉積)記為A1A2An ，定義為A1A2An = a1,a2,an|aiAi1in對一切i, Ai=A時, A1A2An 可簡記為Ann顯然AB BAn若存在i, Ai=, A1A2An =n如果所有Ai(i=1,2,n)都是有限集合, 則|A1A2An|=|A1|A2|A3

3、|An|例n設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 設A 、B和C是三個集合，若C,則 ABACBC CAC

4、B證明(1):必要性：必要性：設AB，求證 ACBC任取ACBC則xA 且 yC由AB ，得xB 且 yC即：所以ACBC充分性：充分性：設ACBC ，求證AB任取xAxBy0C 使得 A C由ACBC ，得 B C即：所以AB綜上有ABACBC n定理定理5.1.2 設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笛卡爾積的應用令A1=x|x是學號 A2=x|x是姓名 A3=男,女 A4=x|x是出生日期 A5=x|x是班級 A6 =x|x是籍貫 n A1A2A3 A4A5

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

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

8、關系的相等R1是 A1 A2 An上 的 n 元 關 系 , R2是B1B2Bm上的m元關系.那么R1=R2,當且僅當n=m,且對一切i,1in,Ai=Bi,并且R1和R2是相等的有序n元組集合n二元關系簡稱為關系關系nR xRy 也稱之為x與y有R關系nR xRy 也稱之為x與y沒有R關系后綴表示法后綴表示法中綴表示法中綴表示法關系的定義域與值域n定義定義5.2.3 設R ：AB定義域定義域(domain)：由所有R的第一個分量組成的集合，稱為R的定義域，記作dom R，即 dom R=x|y(R) 值域值域(range)：由所有R的第二個分量組成的集合，稱為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ù)集合， R上的幾個關系x2+y2=4=xy關系矩陣和關系圖n關系矩陣有限集合之間的關系可以用矩陣表示便于用計算機來處理設A=a1, a2, , am，B=b1, b2, , bn是有限集， RAB， A到B的二元關系R可用mn階矩陣表示：MR=(rij)mn，其中rij= 1,如果aiRbj 0,如aiRbj 則稱矩陣MR=rij是R的關系矩陣n例A=a1,a2,B=b1,b2,b3nR是A到B的關系，R=, b1 b2 b3a1 1 0 1a2 1 1 0MR=1

10、0 11 1 0nS是B上的關系，S=, b1 b2 b3b1 1 0 1b2 1 1 0b3 0 1 0MS= 1 0 1 1 1 0 0 1 0n關系圖有向圖兩種情況nR ABnR AA例：設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關系的集合運算n關系就是集合n、-、和補運算對關系也適用n特別的R=(AB)-R思考題n設A和B分別是n元和m元有限集，則共有多少個不同的A到B的關系？mn2n設A(和B)都是非空有限集，則A上的空關系、恒等關系和A上(A到B的)全關系的關系圖和關系矩陣有何特點。n怎樣

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

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

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

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

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

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

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

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

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

20、逆(或叫R的逆關系)記為R-1(Rc),是一從B到A的二元關系,定義如下:R-1=|Rn例I上的關系“”集合族上的關系的逆是關系 空關系的逆是空關系(AB) -1 =BAIA -1 = IA R=,nR-1=,逆關系的關系圖和關系矩陣nR-1的關系圖將R關系圖的所有邊的方向顛倒n R-1的矩陣 R矩陣的轉置：M=(MR)T43110110000101RM341101010001011RMn定理定理5.4.1 設R, S都是從A到B的關系,那么下列各式成立: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上關系，則 R是對稱的，當且僅當 R-1 =R R是反對稱的，當且僅當 RR-1 IA證明： 充分性，已知 R-1 =R (證明R對稱) 任取x,yA 設R,則R-1,而R-1 =R 即有R ，所以R對稱必要性，已知R對稱，(證明R-1 =R)先證R-1R，任取R-1,則R,又R對稱所以有R，所以R-1R。再證R R-1，任取R, 因R對稱，所以有R，則RC, 所以RR-1。綜上R-1 =R證明 充分性，已知RR-1IA，(證明R反對稱) 任取x,yA

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

23、6=,S=y-z=1=,R S=,練習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設A=1,2,3,4,5,R和S都是A上二元關系.如果R=,S=,求RS，SR ，(RS)R ，R(SR) ，RR ，SSRS=,SR=,(RS)R=R(SR)=RR=,SS=, 不滿足交換律滿足結合律？復合關系的矩陣表達n為了討論復合關系的關系矩陣，引入/矩陣的復合運算n定義定義5.4.3 設MR=aij是nm的/矩陣, MS=bij是mp的/矩陣.則MRS

24、=cij=MRMS,這里是邏輯乘,是邏輯加，否則。為真；，若0) 11(11kjikmkijbacn定理定理5.4.3 設A=a1, a2, an, B=b1, b2, bm, C=c1, c2, cp, R是從A到B的關系， S是從B到C的關系。則MRS=MRMSn例：設 X=1,2, Y=a,b,c, Z=, R是X到Y的關系， S是Y到Z的關系， R=, S=,則100011RM101010SM1010101010100011SRM關系復合運算的性質n定理定理5.4.4設R是A到B的二元關系,IA,IB分別是A和B上的相等關系,則IAR=RIB=Rn例：令A=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設R1是從A到B的關系,R2和R3是從B到C的關系,R4是從C到D的關系,則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設R1和R2是由A到B的關系， S1和S2是由B到C的關系，若 R1 R2 , S1 S

27、2 ,則 R1S1 R2S2n定理定理5.4.7設R1是從A到B的關系,R2是從B到C的關系,R3是從C到D的關系,則 (R1R2)R3=R1(R2R3) (復合運算滿足結合律) 證明：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關系R的冪n當R是A上的一個關系時,R可與自身合成任意次而形成A上的一個新關系，即 RR=R2， R2R=RR2 =R3，n定義定義5.4.4設R是集合A上的二元

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

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

30、，Rs+kp+n+1=Rs+kp+nR=Rs+nR=Rs+n+1得證證明(c)：只需證q t時, RqS由q t s, 必存在i,jZ使得q=s+ip+j (0jp-1)因為 i. q=t時，t=s+1*p+0 =s+t-s ii. 設q=n時，存在i,j使得k=s+ip+j (0td-1)則q=n+1時, n+1=s+ip+j +1, 分兩種情況討論情況1: jp-1, 則i和j +1就是要求的兩個數(shù)情況2: j=p-1, 則j+1=p， n+1=s+(i+1)p+0, 即i+1和0是要求的兩個數(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 設R是集合A上的關系，則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設A=a,b,c,d,R=,求R0, R2, R3, R4R0=, R2=, R3=, R4=,nR4=R2,根據定理3.25(c)對nN, RnR0,R1,R2,R3易證R5=R3,R6=R4=R2用歸

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

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

34、( )iit RRRRR證明(1): 設R =R IA.顯然, R是自反的，且R R. 假設R是A上的自反關系且R R.因R是自反的,所以R IA,又R R,所以R R IA =R所以,R=r(R). 證畢1iiRR證明(2): 設R =R R-1 (i) 顯然R R(ii) 又 (R R-1 ) -1 = R-1 R= R R-1 R是對稱的(iii)假設R是A上的對稱關系且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, 設有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) 這個過程可以一直進行下去，即得Rit(R) Rt(R)綜合(i)(ii) R=t(R)例(a)整數(shù)集合I上的關系的自反閉包是,對稱閉包是關系,傳遞閉包是關系自身(b)整數(shù)集合I上的關系的自反閉包是自身,對稱閉包是全域關系,傳遞閉包是自身(c)的自反閉包是全域關系,對稱閉包是,的傳遞閉包是全域關系(d)空關

36、系的自反閉包是恒等關系,對稱閉包和傳遞閉包是自身(e)設R是I上的關系,xRy當且僅當y=x+1,那么t(R)是關系n定理定理5.5.3 設R是n元有限集A上的關系,則存在自然數(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、的假設矛盾例nA=1,2,3， A上關系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閉包的性質n定理定理5.5.4設R和S都是集合A上的關系且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) 閉包的應用n例：傳遞閉包在語法分析中的應用設有一字母表V = A ,B

38、, C,D , e, d , f . 假設文法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 上的二元關系, (x i, x j ) R 表示從x i 出發(fā)用一條規(guī)則推出一串字符, 使其第一個字母恰好為x jt(R): 每個字母連續(xù)使用文法可能推出的頭字符.n定理定理5.5.5 (a)如果R是自反的,那么s(R)和t(R)都是自反的(b)如果R是對稱的,那么r(R)和t(R)都是對稱的(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 設R是集合A上的二元關系,那么(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)是對稱的（定理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 有序關系有序關系n常遇到的重要關系n例數(shù)值的、關系集合的、關系圖書館的圖書按書名的字母次序排序詞典中的字(詞)的排序計算機中文件按文件名排序程序按語句次序執(zhí)行.偏序關系n定義定義5.6.1如果集合A上的二元關系R是自反的,反對稱的和傳遞的,那么稱R為A上的偏序關系偏序關系,或稱半序關系稱序偶為偏序集偏序集n通常，把偏序關系R記作,如果,則記作ab,讀作“a小于等于b”n注意注意：定義中的“”不是指普通中的實數(shù)中的大小關系的,而是一般的偏序關系例n設集合Aa,b,c,A上的關系R,判斷R是否是偏序關系。n設A是非零自然數(shù)集,DA是A上的整除關系,判斷DA是否是偏序

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

42、)=RIA是偏序關系(b)如果R是一偏序關系,那么R- IA是擬序關系n定義定義5.6.3 可比較設是偏序集， a,bA ,如果ab或ba有一式成立，便稱a和b是可比較的n定義定義5.6.4 全序集線序集在偏序集中.如果a,bA, a，b均可比較.那么叫做A上的線序關系(或全序關系),這時的序偶叫做線序集或全序集、鏈.全序集2。1。84。哈斯圖(Hasse)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 設是偏序集， a,bA(ab) ,如果ab且不存在cA(ca,b)使得 ac和cb同時成立。則稱a是b的直接前輩(元素)，或稱b是a的直接后裔(元素)。 例2。1。642。1。84。6。4。練習1.設A=a,b,c，則“”關系是(A)上的偏序關系，則(A),R)是偏序集,畫出其哈斯圖2.設A =2,3,6,12,24,36,畫出的哈斯圖nA=1,2,12,的哈斯圖偏序集中的重要元素n定義定義5.6.6 極小元與極大元：設是一偏序集合,B是A的非空子集若存在元素bB,使得B中沒有沒有元素x滿足xb且xb,則稱b為B的一個極小元極小元若存

44、在元素bB,使得B中沒有沒有元素x滿足xb且bx,則稱b為B的一個極大元極大元n定義定義5.6.7 最小元與最大元：設是一偏序集合,B是A的非空子集如存在元素bB,使得xB,均有bx,則稱b為B的最小元最小元如存在元素bB,使得xB,均有xb,則稱b為B的最大元最大元例n設的哈斯圖如下所示：討論當B取相應集合時，其最大元,最小元,極大元,極小元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幾點說明n對于有限集，極大(小)元總是存在的n最大(小)元可能不存在n極大(小)元未必是最大(小)元n極大(小)元未必是唯一的n如果B存在最大(小)元x,則x就是B的極大(小)元n孤立點則又是極大元,也是極小元n定理定理5.6.3 設是一偏序集，且BA,如果B有最大(最小)元，那么它是唯一的證明：假設a和b都是B的最大元,那么ab和ba.則a=b(是反對稱性的)類似可證最小元的唯一性n定義定義5.6.8 上界與下界，上確界與下確界：設是一偏序集,B是A的子集如存在aA,使得xB,均有xa,則稱B有上界，并稱a為B的一個上界上界(Upper Bound )如存在aA,使得xB,均有ax

46、,則稱B有下界，并稱a為B的一個下界下界(Lower Bound )若a是B的上界，并且對B的每一個上界a皆有a a，則稱 a是B的上確界上確界 (最小上界，Least Upper Bound )，記作lub若a是B的下界，并且對B的每一個下界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練習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設是一偏序集,且A的每一非空子集B都有最小元, 則稱為良序集n定理定理5.6.4 設是一偏序集，則是良序集的充分必要條件為： 1.是上的全序關系； 2.A的每個非空子集都有極小元 思考題n證明或用反例否定下列命題(1)每一個偏序關系的逆都是偏序關系(2

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

49、先后次序 將DAG的每一個頂點對應一個事件，圖中存在從A指向B的邊表示事件A是事件B的一個前提條件。這樣組成的圖叫做AOV（Activity on Vertex）網。對AOV網進行拓撲排序，每一個排序結果表示一種可行的做事的先后順序 有序關系與拓撲排序n例：早晨穿衣的過程undershortpantsbeltshirttiejacketsocksshoeswatchsocks undershortpantsshoes watchshirtbelttiejacket有序關系與拓撲排序nDAG拓撲排序算法1.開始時，置圖G1=G，q為空序列； 2.如果圖G1是空圖，則拓撲排序完成，算法結束，得到的

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

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

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

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

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

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