離散數(shù)學課件第3章

1、第3章 二元關系3.1 基本概念基本概念3.2 關系的合成關系的合成3.3 關系上的閉包運算關系上的閉包運算3.4 次序關系次序關系3.5 等價關系和劃分等價關系和劃分 第第3章章 二元關系二元關系第3章 二元關系3.1 基本概念基本概念 3.1.1 關系關系 關系的數(shù)學概念是建立在日常生活中關系的概念之上的.讓我們先看兩個例子 例3.1-1 設A=a,b,c,d是某乒乓球隊的男隊員集合, B=e,f,g是女隊員集合.如果A和B元素之間有混雙配對關系的是a和g,d和e.我們可表達為: R=a,g,d,e第3章 二元關系 這里R表示具有混雙配對關系的序偶集合.所有可能具有混雙配對關系的序偶 集合

2、是: AB=x,y|xAyB =a,e,a,f,a,g,b,e,b,f,b,g, c,e,c,f,c,g,d,e,d,f,d,g第3章 二元關系 例例3.1-2 設學生集合A1=a,b,c,d,選修課集合A2=日語,法語,成績等級集合A3=甲,乙,丙.如果四人的選修內(nèi)容及成績?nèi)缦? a 日 乙 b 法 甲 c 日 丙 d 法 乙 我們可表達為S=a,日,乙,b,法,甲,c,日,丙,d,法,乙第3章 二元關系 這里S表示學生和選修課及成績間的關系.而可能出現(xiàn)的全部情況為 A1A2A3=x,y,z|xA1yA2zA3 =a,日,甲,a,日,乙,a,日,丙,a,法,甲,a,法,乙,=a,法,丙,b,

3、日,甲,b,日,乙,b,日,丙,b,法,甲,=b,法,乙,b,法,丙,c,日,甲,c,日,乙,c,日,丙,=c,法,甲,c,法,乙,c,法,丙,d,日,甲,d,日,乙,=d,日,丙,d,法,甲,d,法,乙,d,法,丙第3章 二元關系 定義定義 3.11 (1)AB的子集叫做A到B的一個二元關系. (2)A1A2An(n1)的子集叫做A1A2An上的一個n元關系. (3) (1)nAAAA n的子集叫做A上的n元關系n個第3章 二元關系 從定義可看出,關系是一個集合,所有定義集合的方法,都可用來定義關系 例3.1-1和例3.1-2是列舉法的例子。一個謂詞P(x1,x2,xn)可以定義一個n元關系

4、R: R=x1,x2,xn|P(x1,x2,xn) 例如,實數(shù)R上的二元關系可定義如下: =x,y|xRyRxy 反之,一個n元關系也可定義一個謂詞:P(x1,x2,xn)= 1(真),當x1,x2,xnR時0(假),當x1,x2,xnR時 第3章 二元關系 當n=1時,R=x|P(x)稱為一元關系.它是一重組集合,表示論述域上具有性質P的元素集合,其意義與R=x|P(x)相同,僅記法不同而已。例如,設P(x)表示“x是質數(shù)”,論述域是N,則質數(shù)集合可表示為 xP(x) 或 xP(x)第3章 二元關系關系也可歸納地定義.自然數(shù)上的小于關系可定義如下: (1) (基礎)0,1 (2) (歸納)如

5、果x,y,那么 (i)x,y+1 (ii)x+1,y+1 (3)(極小性)對一切x,yN,xy當且僅當x,y是由有限次應用條款(1)和(2)構成。第3章 二元關系 定義3.12設R是 的子集,如果R=,則稱R為空關系,如果 ,則稱R為全域關系. 現(xiàn)在定義關系相等的概念,在關系相等的概念中不僅需要n重組集合相等,還需其叉積擴集也相同. 定義3.13設R1是 上的n元關系,R2是 上的m元關系.那么R1=R2,當且僅當n=m,且對一切i,1in,Ai=Bi,并且R1和R2是相等的有序n重組集合1niiA1niiA1niiA1niiB第3章 二元關系 3.1.2 二元關系二元關系 最重要的關系是二元

6、關系.本章主要討論二元關系,今后術語“關系”都指二元關系.若非二元關系將用“三元”或“n元”一類術語指出. 二元關系有自己專用的記法和若干新術語 設 A=x1,x2,x7, B=y1,y2,y6 R=x3,y1,x3,y2,x4,y4,x6,y2 A到B的二元關系R可如圖3.11那樣形象地表示.x3,y1R,也可寫成x3Ry1,稱為中綴記法,讀做x3和y1有關系R.中綴記法常用來表示諸如“=”,“”,“”等關系,例如3,5,通常寫作35.第3章 二元關系 圖 3.11第3章 二元關系 A叫做關系R的前域,B叫做關系R的陪域陪域 D(R)=xy(x,yR)叫做關系R的定義域定義域 R(R)=yx

7、(x,yR)叫做關系R的值域值域 關系是序偶的集合,對它可進行集合運算,運算結果定義一個新關系.設R和S是給定集合上的兩個二元關系,則RS,RS,R-S, 等可分別定義如下: x(RS)y xRyxSy x(RS)y xRyxSy x(R-S)y xRyx$y xy xRyRR第3章 二元關系 例3.1-3平面上的幾何圖形是平面R2的子集,也是一種關系.設(參看圖3.12) R1=x,yx,yR2x2+y29 R2=x,yx,yR21x3) (0y3) R3=x,yx,yR2x2+y24 則 R1R2=x,yx,yR2(x2+y2 9(1x30y3) 第3章 二元關系R1R3=x,yx,yR2

8、(x2+y2 9x2+y24) R1-R3=x,yx,yR2(x2+y29 L (x2+y24) =x,yx,yR2 (x2+y24)3R第3章 二元關系圖 3.12 第3章 二元關系 3.1.3 關系矩陣和關系圖關系矩陣和關系圖 表達有限集合到有限集合的二元關系時,矩陣是一有力工具定義定義3.14給定集合A=a1,a2,am和B=b1,b2,bn,及一個A到B的二元關系R. 使.rij= 1,如果aiRbj 0,如aiRbj 則稱MR=rij矩陣是R的關系矩陣.第3章 二元關系 例例3.1-4 設A=a1,a2,B=b1,b2,b3,R=a1,b1,a2,b1,a1,b3,a2,b2,則其關

9、系矩陣為 b1 b2 b3a1 1 0 1a2 1 1 0即 1011 10RM第3章 二元關系 例例3.1-5 設A=1,2,3,4,A上的二元關系R=x,yxy,試求出關系矩陣 解解R=4,1,4,2,4,3,3,1,3,2,2,10000100011001111RM第3章 二元關系集合A上的二元關系也可用有向圖表示。具體方法如下: 一般用小圓圈標上ai表示元素ai，小圓圈叫圖的結點(node)，如果ai，ajR，則從結點ai到aj畫一帶箭頭的弧(注意ai是始點，aj是終點，次序不能顛倒); 如果ai，aiR，則通過結點ai畫一個叫做自回路的帶箭頭的圓弧。稱帶箭頭的弧為弧或邊。這樣所得的圖

10、叫做關系R的圖示，又稱關系圖。正規(guī)的說法應該是有向圖A，R的圖示，所謂有向是指每條邊都有方向。 第3章 二元關系圖 3.13 第3章 二元關系 例例3.1-6 設A=1,2,3,4,5,R=1,2,2,2,3,2,3,4,4,3,其圖示如圖3.13所示.圖中結點5叫做孤立點。利用關系R的圖示,也可寫出關系R.第3章 二元關系 3.1.4 關系的特性關系的特性 在研究各種二元關系中,關系的某些特性扮演著重要角色,我們將定義這些特性,并給出它的圖示和矩陣的特點 定義定義3.15設R是A上的二元關系, (1)如果對A中每一x,xRx,那么R是自反的.即 A上的關系R是自反的 x(xAxRx)A=1,

11、2,3,R1=1,1,2,2,3,3,1,2 是自反的.其關系圖和關系矩陣的特點如圖3.14所示.第3章 二元關系 圖 3.14 第3章 二元關系 (2)如果對A中每一x,xRx,那么R是反自反的.即 A上的關系R是反自反的 x(xAxRx) 例如,A=1,2,3,R2=2,1,1,3,3,2是反自反的,其關系圖和關系矩陣的特點如圖3.15所示.有些關系既不是自反的,又不是反自反的(如圖3.16),例如,R3=1,1,1,2,3,2,2,3,3,3第3章 二元關系圖 3.15第3章 二元關系圖 3.16第3章 二元關系 (3)如果對每一x,yA,xRy蘊含著yRx,那么R是對稱的.即A上的關系

12、R是對稱的 x y (xAyAxRyyRx) 例如,A=1,2,3,R4=1,2,2,1,1,3,3,1,1,1是對稱的.其關系圖和關系矩陣的特點如圖3.17所示 第3章 二元關系圖 3.17第3章 二元關系 (4)如果對每一x,yA,xRy,yRx蘊含著x=y,那么R是反對稱的.即A上的關系R是反對稱的 x y(xAyAxRyyRxx=y) 例如,A=1,2,3,R5=1,2,2,3是反對稱的,其關系圖和關系矩陣的特點如圖3.18所示. 第3章 二元關系圖 3.18第3章 二元關系 (5)如果對每一x,y,zA,xRy,yRz蘊含著xRz,那么R是傳遞的.即A上的關系R是傳遞的 x y z(

13、xAyAz=AxRyyRzxRz) 例如,A=1,2,3,4,R5=4,1,4,3,4,2,3,2,3,1,2,1是傳遞的.其關系圖和關系矩陣如圖3.110所示. 第3章 二元關系圖 3.19第3章 二元關系 圖 3.110第3章 二元關系 例例3.1-7 (1)任何集合上的相等關系是自反的,對稱的,反對稱的和傳遞的,但不是反自反的 (2)整數(shù)集合I上,關系是自反的,反對稱的,可傳遞的.但不是反自反的和對稱的.關系是反自反的,反對稱的,可傳遞的,但不是自反的和對稱的 (3)設=a,b,試考察上的下列關系: (i)關系“與有同樣長度”是自反的,對稱的,可傳遞的,但不是反自反的和反對稱的第3章 二

14、元關系 (ii)“xRy”當且僅當x是y的真詞頭”,這里R是反自反的,反對稱的,可傳遞的,但不是自反的和對稱的 (iii)“xRy”當且僅當x的某真詞頭是y的一個真詞尾”,這里R既不是自反的又不是反自反的,因為aaRaa,但abRab,既不是對稱的也不是反對稱的,并且不是傳遞的。 (4)非空集合上的空關系是反自反的,對稱的,反對稱的和傳遞的,但不是自反的.空集合上的空關系則是自反的,反自反的,對稱的,反對稱的和可傳遞的。 (5)基數(shù)大于1的集合上的全域關系是自反的,對稱的和傳遞的,但不是反自反的和反對稱的.例如圖3.111所示的關系。第3章 二元關系 圖 3.111第3章 二元關系例題例題1、

15、設、設A是具有是具有n個元素的集合，求出個元素的集合，求出A上具有對稱性的二元上具有對稱性的二元關系的數(shù)目。（關系的數(shù)目。（06年華中科技術大學研究生入學試題年華中科技術大學研究生入學試題）2、求關系、求關系R的自反、對稱和傳遞閉包，并畫出相應的關系圖。的自反、對稱和傳遞閉包，并畫出相應的關系圖。R=、（大連理工大學大連理工大學08年入學試題年入學試題）3、設集合、設集合A=1，2，3，定義，定義A上的關系上的關系R=、（1）判斷關系）判斷關系R的性質的性質（2）求集合）求集合A上具有關系上具有關系R的性質的關系共有多少個？（的性質的關系共有多少個？（河河海大學海大學2005年入學試題年入學試

16、題）第3章 二元關系4、在下圖中給出了一個有向圖，試求、在下圖中給出了一個有向圖，試求D=,此有向圖對應的關系是否可傳遞的？如果不是可傳遞的，此有向圖對應的關系是否可傳遞的？如果不是可傳遞的，試求此圖的傳遞閉包。并且說明此有向圖是否是弱連通試求此圖的傳遞閉包。并且說明此有向圖是否是弱連通圖單向連通圖和強連通圖？圖單向連通圖和強連通圖？(河海大學河海大學2004年入學試題年入學試題)第3章 二元關系 3.2.1 關系的合成關系的合成前邊已經(jīng)指出，關系是序偶的集合，因此可以進行集合運算。本節(jié)介紹一種對關系來說更為重要的運算合成運算。假設R1是A到B的關系，R2是B到C的關系(參看圖3.2-1)。合

17、成關系R1R2是一個A到C的關系: 如果在關系圖上，從aA到cC有一長度(路徑中弧的條數(shù))為2的路徑，其第一條弧屬于R1，其第二條弧屬于R2，那么a，cR1R2。合成關系R1R2就是由a，c這樣的序偶組成的集合。3.2 關系的合成關系的合成第3章 二元關系 其第一條弧屬于R1,其第二條弧屬于R2,那么a,cR1R2.合成關系R1R2就是由a,c這樣的序偶組成的集合.第3章 二元關系圖 3.21第3章 二元關系 定義定義3.21設R1是從A到B的關系,R2是從B到C的關系,從A到C的合成關系記為R1R2,定義為 R1R2=a,caAcCbbBa,b R1b,cR2 例例3.2-1 (1) 如果R

18、1是關系“是的兄弟”,R2是關系“是的父親”,那么R1R2是關系“是的叔伯”.R2R2是關系“是的祖父”第3章 二元關系 (2) 給定集合A=1,2,3,4,B=2,3,4,C=1,2,3,設R是A到B的關系;S是B到C的關系. R=x,yx+y=6=2,4,3,3,4,2 S=y,zy-z=1=2,1,3,2,4,3 則RS=2,3,3,2,4,1.如圖3.22所示.第3章 二元關系 圖 3.22第3章 二元關系(3)設A=1,2,3,4,5,R和S都是A上二元關系.如果R=1,2,3,4,2,2,S=4,2,2,5,3,1,1,3則RS=1,5,3,2,2,5SR=4,2,3,2,1,4(

19、RS)R=3,2R(SR)=3,2RR=1,2,2,2SS=4,5,3,3,1,1 第3章 二元關系 (4)設R是A到B的二元關系,IA,IB分別是A和B上的相等關系,則 IAR=RIB=R (5)如果關系R的值域與關系S的定義域的交集是空集,則合成關系RS是空關系.下邊介紹合成關系的性質第3章 二元關系 定理定理3.21 設R1是從A到B的關系,R2和R3是從B到C的關系,R4是從C到D的關系,那么 (1) R1(R2R3)=R1R2R1R3 (2) R1(R2R3) R1R2R1R3 (3) (R2R3)R4=R2R4R3R4 (4) (R2R3)R4 R2R4R3R4 (1),(2),(

20、3)部分的證明留作練習,我們僅證明(2)部分 第3章 二元關系證先證明公式.因為 a,cR1(R2R3)ba,bR1(b,cR2R3)ba,bR1(b,cR2b,cR3)b(a,bR1b,cR2)(a,bR1b,c R3)ba,bR1b,cR2ba,bR1b,cR3a,cR1R2a,cR1R3a,cR1R2R1R3即a,cR1(R2R3)a,cR1R2R1R3所以,R1(R2R3)R1R2R1R3 第3章 二元關系再證包含可能是真包含.舉反例證明如果A=a,B=b1,b2,b3,C=cA到B的關系R1=a,b1,a,b2B到C的關系R2=b1,c,b3,cB到C的關系R3=b2,c,b3,c

21、那么R1(R2R3)= ,R1R2R1R3=a,c.此時R1(R2R3)R1R2R1R3.證畢第3章 二元關系 定理定理3.22 設R1,R2和R3分別是從A到B,B到C和C到D的關系,那么(R1R2)R3=R1(R2R3)。證證先證(R1R2)R3=R1(R2R3)。 設a,d(R1R2)R3,那么對某cC,a,cR1R2和c,dR3.因為a,cR1R2,存在bB使a,bR1和b,cR2.因為b,cR2和c,dR3,得b,dR2R3,所以a,dR1(R2R3).這樣,就證明了(R1R2)R3R1(R2R3).R1(R2R3)(R1R2)R3的證明是類似的,留給讀者自證.上述證明也可用等價序列

22、表達。第3章 二元關系 3.2.2 關系關系R的冪的冪 當R是A上的一個關系時,R可與自身合成任意次而形成A上的一個新關系.在這種情況下,RR常表示為R2,RRR表示為R3等等,我們能歸納地定義這一符號如下 定義定義3.22 設R是集合A上的二元關系,nN,那么R的n次冪記為Rn,定義如下: (1) R0是A上的相等關系,R0=x,xxA。 (2) Rn+1=RnR。第3章 二元關系 定理定理3.23設R是A上的二元關系,并設m和n是N的元素,那么 (1) RmRn=Rm+n (2) (Rm)n=Rmn 可用歸納法證明.請讀者自證.第3章 二元關系 定理定理3.24 設A=n,R是集合A上的一

23、個關系,那么存在i和j使Ri=Rj而0ij 證證A上的每一二元關系是AA的子集,因為AA=n2,(AA)= ,因此A上有 個不同關系.所以,R的不同的冪不會超過 個.但序列R0,R1, 有 項,因此R的這些冪中至少有兩個是相等的.證畢 。22n22n22n22n221n22nR第3章 二元關系 定理定理3.25設R是集合A上的一個二元關系.若存在i和j,ij,使Ri=Rj.記d=j-i,那么 (1) 對所有k0,Ri+k=Rj+k (2) 對所有k,m0,Ri+md+k=Ri+k (3) 記S=R0,R1,R2,Rj-1,那么R的每一次冪是S的元素,即對nN,RnS第3章 二元關系 證證 (1

24、)和(2)部分用歸納法證明,留作練習。 (3) 對于(c),設nN,如果nj,那么根據(jù)S的定義,RnS.假設nj,那么我們能將n表示為i+md+k,這里kd,根據(jù)(b)部分,得Rn=Ri+k,因為i+kj,這證明了RnS. 定理中的i,j,在實用時宜取最小的非負整數(shù),以保證S中無重復元素.第3章 二元關系圖 3.23第3章 二元關系 例3.2-2 設A=a,b,c,d,R=a,b,c,b,b,c,c,d,其關系圖如圖3.23所示,則 R0=a,a,b,b,c,c,d,d R2=a,c,b,b,b,d,c,c R3=a,b,a,d,b,c,c,b,c,d R4=a,c,b,b,b,d,c,c 它

25、們的關系圖如圖3.24所示第3章 二元關系圖 3.24 第3章 二元關系 由于R4=R2,根據(jù)定理3.25(c),對所有nN,RnR0,R1,R2,R3,可見不必再算了.事實上易證R5=R3,R6=R4=R2,用歸納法可得R2n+1=R3和R2n=R2,這里n1.第3章 二元關系 3.2.3 合成關系的矩陣表達合成關系的矩陣表達 定理定理3.26 設X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是X到Y的關系,MR=aij是mn矩陣,S是Y到Z的關系,MS=bij是np矩陣.則MRS=cij=MRMS,這里11,2,;1,2,nijikkjkcabim jp 第3章 二元

26、關系 證因為如果存在某k使aik和bki都等于1,則cij=1.但aik和bkj都等于1意味著xiRyk和ykSzj.所以xi(RS)zj.可見如此求得的MRS確實表達了RS的關系.因此上述等式是正確的. 如果不僅存在一個k使aik和bki都是1,此時cij仍為1,只是從xi到zj不止一條長度為2的路徑,但等式仍然正確.上段的論證,已隱含了不止一個k的情況. 本定理說明合成關系矩陣可用關系矩陣(布爾矩陣)的乘法表達.第3章 二元關系 例例3.2-3 設X=1,2,Y=a,b,c,Z=,R=1,a,1,b,2,c,S=a,b,則011100100101011101100100100101RSR

27、SRSMMMMM第3章 二元關系圖 3.25 第3章 二元關系 定理定理3.27 關系矩陣的乘法是可結合的 證證 利用關系合成的可結合性證明. (MRMS)MT =MRSMT=M(RS)T=MR(ST)=MRMST =MR(MSMT). 不僅合成關系可用關系矩陣表達,而且關系的集合運算也可用關系矩陣表達.設R和S是X到Y上的二元關系,MR=aij,MS=bij,cij是運算后所得新關系之關系矩陣的元素,則第3章 二元關系MRS=MRMS cij=aijbijMRS=MRMS cij=aijbij cij= aijMR-S=MR cij=aij( bij)RMRM第3章 二元關系例：例：西安建筑

28、科技大學西安建筑科技大學2005年考研試題年考研試題第3章 二元關系 3.3.1 逆關系逆關系 在討論閉包運算時,要用到逆關系的概念,因此我們先介紹逆關系 定義定義3.31設R是從A到B的二元關系,關系R的逆(或叫R的逆關系)記為 ,是一從B到A的二元關系,定義如下:R,Ry xx yR 3.3 關系上的閉包運算關系上的閉包運算第3章 二元關系若把R中的每個序偶的第一和第二成分都加以交換，就可以求得逆關系中的所有序偶。對于xA和yB來說，這意味著 RxRyyRx將MR的行和列交換即可求得，即 RMTRRMM顛倒R的關系圖中每條弧的箭頭，就得的關系圖。 R第3章 二元關系 例3.3-1 (1)

29、I上的關系 (2) 集合族上的關系的逆是關系 (3) 空關系的逆是空關系 (4) =BA,即AB的全域關系的逆等于BA的全域關系. 定理3.31設R是從A到B的關系,而S是從B到C 的關系,則R SS RA B 第3章 二元關系 定理定理3.32 設R,R1和R2都是從A到B的二元關系,那么下列各式成立:21212121221212121(1) ( )(2)(3)(4),(5)(6)RRRRRRRRRRRRRA BRRRRRRRRR這里 表示 第3章 二元關系證(1) 設a，b是R的任一元素，那么 ,( )a bRb aRa bR所以，(R)=R。第3章 二元關系1212121212(2),(

30、),a bRRb aRRb aRb aRa bRa bRa bRR 第3章 二元關系(4),),a bRb aRb aRa bRa bR第3章 二元關系1212,RRRR(5) 由于 所以 2221212111RRRRRRRRRR (3)和(6)部分的證明留作練習。定理定理 3.3-3 設R是A上的二元關系，那么R是對稱的當且僅當R=R。第3章 二元關系 3.3.2 關系的閉包運算關系的閉包運算 關系的閉包運算是關系上的一元運算,它把給出的關系R擴充成一新關系R,使R具有一定的性質,且所進行的擴充又是最“節(jié)約”的定義3.32設R是A上的二元關系,R的自反(對稱,傳遞)閉包是關系R,使 (i)R

31、是自反的(對稱的,傳遞的) (ii)RR (iii)對任何自反的(對稱的,傳遞的)關系R,如果 RR,那么RR第3章 二元關系 R的自反,對稱和傳遞閉包分別記為r(R),s(R)和t(R).由定義可以看出,R的自反(對稱,傳遞)閉包是含有R并且具有自反(對稱,傳遞)性質的最小關系.如果R已經(jīng)是自反的(對稱的,傳遞的),那么,具有該性質并含有R的最小關系就是R自身.下一定理說明這一點. 定理定理3.34設R是集合A上的二元關系,那么 (a) R是自反的當且僅當r(R)=R (b) R是對稱的當且僅當s(R)=R (c) R是傳遞的當且僅當t(R)=R第3章 二元關系 證證 (a)如果R是自反的,

32、那么R具有定義3.32對R所要求的性質,因此r(R)=R.反之,如果r(R)=R.那么,根據(jù)定義3.32的性質(i),R是自反的. (b)和(c)的證明是類似的,略. 構造R的自反,對稱和傳遞閉包的方法就是給R補充必要的序偶,使它具有所希望的特性.下面我們用關系圖來說明如何實現(xiàn)這一點.第3章 二元關系 定理定理3.35 設R是集合A上的二元關系.那么,r(R)=RE(這里E是A上相等關系,在本節(jié)中均如此.) 證證 設R =RE.顯然,R 是自反的且RR.余下只需證明最小性,現(xiàn)假設R是A上的自反關系且RR.因R是自反的,所以RE,又RR,所以RRE=R.這樣,定義3.32都滿足.所以,R=r(R

33、).證畢設G是集合A上二元關系R的關系圖。我們把G的所有弧都畫成“有來有往”，即如果有從a到b的弧，那么也有從b到a的弧，就得到了R的對稱閉包的有向圖。下一定理體現(xiàn)了這一想法。第3章 二元關系定理定理 3.3-6 設R是集合A上的二元關系，那么s(R)=RR。證證 設R=RR，顯然R R。又根據(jù)定理 3.3-3知R是對稱的。 現(xiàn)假設R是對稱的且R R，我們證明R R。設a，bRR，如果a，bR， 那么根據(jù)前提有a,bR。如果a,bR，那么b,aR，所以b,aR，但R是對稱的，所以a，bR，這得出。這樣，定義3.3-2都滿足。所以，。 證畢。設G是集合A上二元關系R的關系圖，G是R的傳遞閉包t(

34、R)的關系圖。如果G有從a到b的非零長度n的路徑，那么G有一條從a到b的弧。上節(jié)已指出該弧出現(xiàn)在Rn的關系圖中，因此傳遞閉包t(R)可用R的冪的術語表達出來。 RRRRRRRRRRR( )s RRR第3章 二元關系 定理3.37 設R是集合A上的二元關系,那么231( )iit RRRRR證 證明分兩部分1( )( ).iiaRt R (1) (基礎)從定義3.32第(ii)條,立即得到Rt(R) (2) (歸納)假設Rnt(R),n1.設a,bRn+1.因為Rn+1=RnR,存在cA,使a,cRn和c,bR.根據(jù)歸納前提和基礎步驟,a,ct(R)和c,bt(R).因為t(R)是傳遞的,得a,

35、bt(R).這證明了Rn+1 t(R). 第3章 二元關系1( )( )iibt RR 我們首先證明是傳遞的。設a，b和b，c是的任意元素，那么對某整數(shù)s1和t1，a,bRs和b,cRt，那么，a,cRsRt，而RsRt=Rs+t，這樣， 所以是傳遞的。因為t(R)包含于每一含有R的傳遞關系中， 故得出。證畢。 1iiR1iiR1,iia cR1iiR1( )iit RR 第3章 二元關系 例3.3-2 (a)整數(shù)集合I上的關系的自反閉包是,對稱閉包是關系,傳遞閉包是關系自身 (b)整數(shù)集合I上的關系的自反閉包是自身,對稱閉包是全域關系,傳遞閉包是自身 (c)E的自反閉包,對稱閉包和傳遞閉包都

36、是E (d)的自反閉包是全域關系,對稱閉包是,的傳遞閉包是全域關系 (e)空關系的自反閉包是相等關系,對稱閉包和傳遞閉包是自身 (f)設R是I上的關系,xRy當且僅當y=x+1,那么t(R)是關系。第3章 二元關系 定理3.38設R是集合A上的二元關系,這里A有n個元素,那么 證 設x,yt(R),于是必存在最小的正整數(shù)k,使x,yRk.現(xiàn)證明kn.若不然,存在A的元素序列x=a0,a1,a2,ak-1,ak=y使xRa1,a1Ra2,ak-1Ry.因kn,a0,a1,ak中必有相同者,不妨設ai=aj,0ijk.于是 xRa1,a1Ra2,ai-1Rai,ajRaj+1,ak-1Ry 成立.

37、即x,yRs,這里s=k-(j-i).但這與k是最小的假設矛盾,于是kn,又x,y是任意的,故定理得證1( )niit RR 第3章 二元關系 例例3.3-3 設A=a,b,c,d,R如圖3.31(a)所示,則t(R)=RR2R3R4,如圖3.31(b)所示.(本例即是3.2-2) 定理定理3.39 (1)如果R是自反的,那么s(R)和t(R)都是自反的 (2)如果R是對稱的,那么r(R)和t(R)都是對稱的 (3)如果R是傳遞的,那么r(R)是傳遞的 第3章 二元關系圖 3.31第3章 二元關系 定理定理3.310 設R是集合A上的二元關系,那么 (1)rs(R)=sr(R) (2)rt(R

38、)=tr(R) (3)ts(R) st(R)證(1) sr( )()()()()( )Rs RERERERERERREr RR rs R第3章 二元關系 (2) 注意到ER=RE=R和對一切nN,En=E,可得 1()nniiREER 于是 111tr( )()()()( )( )iijiijRt REREEREt Rrt R 第3章 二元關系 (3)不難證明如果R1R2,那么s(R1)s(R2)和t(R1)t(R2).現(xiàn)相繼地應用這一結論于對稱閉包的性質:s(R) R. 得 ts(R) t(R)和sts(R) st(R) 但根據(jù)定理 3.3-9，ts(R)是對稱的，有sts(R)=ts(R)

39、。因此，ts(R) st(R)。證畢。 一般地， st(R)ts(R)，例如，整數(shù)集合I上的關系。st()=s()=(即st()是不等關系)，而ts()=t()=II(即ts()是全域關系)。通常用R+表示R的傳遞閉包t(R)，讀做“R正”; 用R*表示R的自反傳遞閉包tr(R)， 讀做“R星”。在研究形式語言和計算模型時經(jīng)常使用R+和R*。 第3章 二元關系3.4 次序關系次序關系 3.4.1 偏序集合偏序集合 定義定義3.41 如果集合A上的二元關系R是自反的,反對稱的和傳遞的,那么稱R為A上的偏序,稱序偶A,R為偏序集合偏序集合.第3章 二元關系 如果R是偏序,A,R常記為A, , 是偏

40、序符號,由于難以書寫,通常寫作,讀做“小于或等于”,因為“小于或等于”也是一種偏序,故不會產(chǎn)生混亂.R是偏序時,aRb就記成ab. 如果R是集合A上的偏序,則 R 也是A上的偏序;如果用表示R ,可用表示R.A,和A,都是偏序集合,并互為對偶.第3章 二元關系例3.4-1(1)I,是偏序集合,這里表示整數(shù)中的“小于或等于”關系(2)(A), 是偏序集合,這里是集合間的包含關系(3)A=2,4,6,8,D代表整除關系,M代表整倍數(shù)關系,則D=2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,8M=2,2,4,4,6,6,8,8,4,2,6,2,8,2,8,4A,D,A,M都是偏序集合,

41、且互為對偶第3章 二元關系圖 3.41 第3章 二元關系例2(a)P=1,2,3,4,P,的哈斯圖為圖3.42(b)A=2,3,6,12,24,36,A,整除的哈斯圖為圖3.43(c)A=1,2,12,A,整除的哈斯圖為圖3.44圖 3.42圖 3.43第3章 二元關系 圖 3.44第3章 二元關系定義定義3.42 設A,是一偏序集合,B是A的子集(a)元素bB是B的最大元素,如果對每一元素xB,xb(b)元素bB是B的最小元素,如果對每一元素xB,bx 例3考慮在偏序“整除”下整數(shù)1到6的集合,其哈斯圖為圖3.45(a)如果B=1,2,3,6,那么1是B的最小元素,6是B的最大元素(b)如果

42、B=2,3,因為2和3互相不能整除,那么B沒有最小元素和最大元素(c)如果B=4,那么4是B的最大元素,也是B的最小元素第3章 二元關系圖 3.45 第3章 二元關系 定理定理3.41 設A,是一偏序集合且BA,如果B有最大(最小)元素,那么它是唯一的證假設a和b都是B的最大元素,那么ab和ba.從的反對稱性得到a=b.當a和b都是B的最小元素時,證明是類似的定義3.43設A,是一偏序集合,B是A的子集 (a) 如果bB,且B中不存在元素x,使bx且bx,那么元素bB叫做B的極大元素. (b)如果bB,且B中不存在元素x,使bx且xb,那么元素bB叫做B的極小元素第3章 二元關系 定義定義3.

43、44設A,是一偏序集合,B是A的子集 (a)如果對每一bB,ba,那么元素aA叫做B的上界;如果對每一bB,ab,那么元素aA叫做B的下界. (b)如果a是一上界并且對每一B的上界a有aa,那么元素aA叫做B的最小上界,記為lub;如果a是一下界并且對每一B的下界a有aa,那么元素aA叫做B的最大下界,記為glb .第3章 二元關系 例3.4-4 (a)考慮偏序集合1,1,1,0,0,1,0,0,這里按 a,bc,dacbd 規(guī)定,其哈斯圖如圖3.46 如果B=1,0,那么1,0是B的最小和最大元素,也是B的極大和極小元素.B的上界是1,0和1,1,1,0是最小上界.B的下界是0,0和1,0,

44、1,0是最大下界.第3章 二元關系 (b)考慮偏序集合I,設B=2iiN,那么B既沒有最大元素和極大元素,也沒有上界和最小上界.B的最小元素和極小元素是0,B的下界集合是iiIi0,0是最大下界. (c)考慮在偏序集合2,5,6,10,15,30,整除,其哈斯圖如圖3.47設B是全集合2,5,6,10,15,30,那么2和5都是B的極小元素,但B沒有最小元素.集合B沒有下界,所以沒有最大下界.元素30是B的最大元素,極大元素,上界,最小上界.第3章 二元關系圖 3.46 第3章 二元關系圖 3.47 第3章 二元關系 定理定理3.42 如果A,是非空有限的偏序集合,則A的極小(大)元素常存在最

45、大下界和最小上界也可能存在或不存在,但如果它們存在,則是唯一的. 定理定理3.43 設A,是偏序集合且B A, 如果B的最小上界(最大下界)存在,那么是唯一的. 第3章 二元關系 下述定理描述了存在于諸特異元素之間的某些關系 定理定理3.44 設A,是偏序集合,B是A的子集 (a)如果b是B的最大元素,那么b是B的極大元素 (b)如果b是B的最大元素,那么b是B的lub (c)如果b是B的一個上界且bB,那么b是B的最大元素 證明證明 可由最大元素,極大元素和lub的定義直接得出,故略去.另外,讀者不難給出表達最小元素,極小元素和glb間關系的定理.第3章 二元關系 3.4.2 擬序集合擬序集

46、合 定義3.45如果集合A上的二元關系R是傳遞的和反自反的,那么R叫做A上的擬序.A,R稱為擬序集合. 常借用符號表示擬序擬序是反對稱的,雖然定義中沒有明確指出,但容易證明這一點.因為如果xRy和yRx,由R的傳遞性得xRx,但這與R的反自反性矛盾,所以xRyyRx常假,于是xRyyRxx=y常真,即R是反對稱的.第3章 二元關系 例例3.4-5 (a) 實數(shù)集合中的是擬序關系 (b) 集合族中的真包含是擬序關系 擬序集合和偏序集合是緊密相關的,唯一區(qū)別是相等關系E.下述定理將說明這一點 定理3.45在集合A上, (a) 如果R是一擬序,那么r(R)=RE是偏序 (b) 如果R是一偏序,那么R

47、-E是一擬序第3章 二元關系 3.4.3 線序集合和良序集合線序集合和良序集合 如果是一偏序,或ab或ba,我們說a和b是可比較的.偏序集合中的元素不一定都可比較,所以叫“偏”序.下面介紹的都是可比較的情況. 定義3.46在偏序集合A,中.如果每一a,bA,或者ab,或者ba.那么叫做A上的線序(或全序),這時的序偶A,叫做線序集合或鏈.第3章 二元關系 例3.4-6 (a)P=,a,a,b,a,b,c,P,是線序集合,其哈斯圖如圖3.48所示 (b)I,是線序集合,其哈斯圖(不完全)如圖3.49所示 (c)設S是區(qū)間套的集合0,a)aR+,則S,是線序集合 (d)1,2,3,6,整除不是線序

48、集合;如果A是多于一個元素的集合,那么(A),不是線序集合.第3章 二元關系 圖3.48第3章 二元關系例例3.4-7 某慈善基金會的一個分會共有7個會員，按照總會規(guī)定需要給每個會員排定在分會中的座次，以便需要時按座次分配權益。排定座次的主要依據(jù)是兩項： 會齡a和捐款額b。如甲和乙的會齡和捐款額分別是a1，b1和a2，b2，若a1a2并且b1b2，則甲的座次不能低于乙。已知分會的7名會員的會齡和捐款額如下：第3章 二元關系試問一個怎樣的座次是允許的？解解 容易看出，若甲的會齡和捐款額不都高于等于乙，或不都低于等于乙，則甲、乙座次不能確定。因為主要條件僅能確定一個偏序，而座次是線序，本題就是要把

49、這個偏序擴展為線序，即拓撲分類。拓撲分類最簡捷的方法是給出偏序集合的哈斯圖。上表給出的偏序集合的哈斯圖如圖3.4-9所示。 第3章 二元關系圖3.49第3章 二元關系從圖中可以看出，它有兩個極小元素C4，2和A3，5，二者可任意排序，我們不妨把C4，2排在左側（左低右高）得如下序列 C4，2，A3，5刪去這兩個極小元素后，G4，3是余下圖中唯一的極小元素。把G4，3加入已排序的序列得 C4，2，A3，5，G4，3如此以往，相繼出現(xiàn)的元素是E4，6、 D8，7和F5，10， 最后是B10，15。刪除B10，15后成為空圖，完成拓撲分類，所得的序列是 C4，2，A3，5，G4，3，E4，6，D8，

50、7，F(xiàn)5，10，B10，15這個序列符合要求，但不是唯一的。 第3章 二元關系 定義定義3.47如果A上的二元關系R是一線序,且A的每一非空子集都有一最小元素,那么R叫做A上的良序,序偶A,R叫做良序集合 定理定理3.46N,是良序集合 證證我們必須證明N的每一非空子集S,在關系之下,都有一最小元素.因為S非空,所以在S中可以取一個數(shù)n,顯然,S中所有不大于n的數(shù)形成非空集TS.如果T有最小數(shù),那么這最小數(shù)就是S中的最小數(shù),但從0到n只有n+1個自然數(shù),于是T中所含的數(shù)最多是n+1個,所以T有最小數(shù).因此定理成立.第3章 二元關系 例3.4-8 (a)每一有限線序集合是良序的 (b)線序集合I

51、,不是良序集合,因為I的某些子集(諸如I自身)不包含最小元素 (c)關系是實數(shù)R的線序,但不是良序.例如子集A=(0,1無最小元素.如果A中的a是最小元素,那么 也在A中,而 a且不相等.這與假設a是線序關系下A的最小元素矛盾2a2a第3章 二元關系3.4.4 詞典序和標準序詞典序和標準序 (1)首先,使集合S上的每個元素與集合N(也可選其它已知的良序或線序集合)的唯一不同的元素對應,然后應用N上的良序定義S上的良序R。定義方法如下: 如果a,bS,且a對應于n1,b對應于n2,那么aRb n1n2例如，i0時，把I的元素i對應于2i-1，i0時，對應于2i。即 N: 0 1 2 3 4 5

52、6 : 0 1 1 -2 2 -3 3 可誘導出I上的良序R，R用式子表示是 aRb ab (a=bab) 第3章 二元關系 (2) 應用N上的良序定義出Nn上的良序 例如n=2時,N2上的次序關系可如下定義: a,bc,dac(a=cbd)N2,是良序集合.關系“嚴格小于”可如下定義:a,bc,da,bc,da,bc,d類似地,應用I上的線序能定義出線序集合In, (3) 應用字母表上的線序,可定義出*上的通常叫詞典序的線序. 第3章 二元關系 定義定義3.48 設是一有限字母表,指定了字母表序(線序).如果x,y*, (a)x是y的詞頭,或 (b)x=zu和y=zv,這里z*是x和y的最長

53、公共詞頭,且在字母表序中u的第一個字符前于v的第一個字符,那么xy.叫做詞典序 (4)由于N, 和有限線序集合都是良序集合,可應用它們定義出*上的一個良序,通常叫標準序 第3章 二元關系 定義定義3.49設是一有限字母表,指定了字母表序,x表示x的長度,如果x,y*, (a)xy,或. (b)x=y且在的詞典序中x前于y.那么xy, 叫做標準序.第3章 二元關系 不論在詞典序和標準序下,的每一元素都有直接后繼者.設=a,b,c且abc,x*.在標準序下 xa和xb的直接后繼者分別是xb和xc, xc的直接后繼者是ya,這里y是x的直接后繼者.在詞典序下x的直接后繼者是xa在標準序下 xb和xc

54、的直接前趨分別是xa和xb, xa的直接前趨是yc,這里y是x的直接前趨.在詞典序下 xa的直接前趨是x,非a結尾的串都無直接前趨,例如b,ab,aab,但有無限個前趨第3章 二元關系 3.4.5 數(shù)學歸納法的推廣數(shù)學歸納法的推廣 前章我們把數(shù)學歸納法第一,第二原理看作是自然數(shù)域上的一個推理規(guī)則,本小節(jié)我們把它推廣到一般的良序集合對任一個自然數(shù)n,我們先取0,如果n0,取0的后繼者1,如果n1,再取1的后繼者2,如此進行下去,最終會得出n. 給定一個良序集合,如果對它的任一元素x,我們先取該集合的最小元素m0,如果xm0,取m0的后繼者m1,如果xm1,再取m1的后繼者m2,如此以往,最終會得

55、出x,那么就稱這樣的良序集合是“像自然數(shù)”的.第3章 二元關系 例例 8 (1) 設=a,b,良序集合*,標準序是像自然數(shù)的.因為定長的串的個數(shù)有限,給定任一個串x,在x之前的串的個數(shù)有限,所以從開始,反復取后繼者,終可得出x. (2)良序集合NN,不像自然數(shù),這里按上一小節(jié)規(guī)定.因為有許多元素沒有直接前趨,例如5,0就是這樣,因而有無限個元素前于5,0,所以,從0,0開始,反復地取后繼者,不可能取得5,0.第3章 二元關系 像自然數(shù)的良序集合,可以應用數(shù)學歸納法第一原理.因為第一原理是建立在后繼運算上,而這種良序集合的每一元素都可通過重復地取后繼者得到,設m0是該良序集合S,的最小元素,S(

56、x)是元素x的后繼者,則推理規(guī)則如下:0() ( )( ( )( )P mx P xP S xxP x 這樣,如果我們能證明m0有性質P,和當x有性質P時,則S(x)有同樣性質,那么我們能得出S的每一元素有性質P.第3章 二元關系 對不像自然數(shù)的良序集合,不能應用數(shù)學歸納法第一原理,因為這種良序集合的有些元素不能由后繼運算得到.但對它可應用數(shù)學歸納法第二原理.第二原理是建立在良序集合上的,適用于一切良序集合.設S,是良序集合,表示-E(即xy表示xy且xy),則推理規(guī)則如下:()( )( )xy yxP yP xxP x 這樣,若每一小于x的元素有性質P,如果我們能證明任意元素x有性質P,那么

57、我們能得出S的每一元素有性質P.第3章 二元關系 下面證明良序集合上這個推理規(guī)則是有效的 假設我們能證明前提( )( )xy yxP yP x 并假設T是S的子集,由S中沒有性質P的所有元素組成.因為S是良序的,如果T ,那么T必有最小元素m;這得出對所有xm,P(x)是真.可是,前提斷言如果對所有xm,P(x)是真,那么P(m)是真,導致矛盾,我們得出T必須是空.因此,第二原理結論xP(x)是真,這得出對任意良序集合S,數(shù)學歸納法第二原理是有效的推理規(guī)則 .第3章 二元關系 例例3.4-10Q+,是線序集合.現(xiàn)說明在此線序集合中第二原理不是有效推理規(guī)則。設謂詞P(x)表示“x小于或等于5”.

58、 (i)當x5時, yyxP(y)是真,P(x)也真. 所以( )( )xy yxP yP x 第3章 二元關系 是真 綜合(i)和(ii),得: 在論述域Q+上, x y(yxP(y)P(x)是真,但結論 x P(x)是假.這說明第二原理不能應用于線序集合Q+, ( )( )xy yxP yP x 是假,所以 (ii)當x5時, 由于x5,所以存在有理數(shù)y0,使5y0 x.這樣P(y0)是假,因而( )y yxP y第3章 二元關系3.5 等價關系和劃分等價關系和劃分 3.5.1 等價關系等價關系 二元關系的另一重要類型是等價關系,其定義如下: 定義定義3.51如果集合A上的二元關系R是自反

59、的,對稱的和傳遞的,那么稱R是等價關系。設R是A上的等價關系,a,b,c是A的任意元素.如果aRb(即a,bR),通常我們記作ab,讀做“a等價于b”.第3章 二元關系通常我們記作ab，讀做“a等價于b”。(1) 因為R具有自反性，所以A上每一元素都和自己等價。反映到R的有向圖上，每一結點都有一自回路。(2) 因為R具有對稱性，所以如果a等價于b，則b也等價于a，反映在有向圖上，如果有從a到b的弧，那么也有從b到a的弧。(3) 因為R具有傳遞性，所以如果a等價于b，b等價于c，則a等價于c。反映在有向圖上，如果從a到c有一條路徑，則從a到c有一條弧。 第3章 二元關系例例 3.5-1(1) 同

60、學集合A=a，b，c，d，e，f，g，A中的關系R是“住在同一房間”。這是等價關系，因為 任一個人和自己同住一間，具有自反性。 若甲和乙同住一間，則乙和甲也同住一間，具有對稱性。 若甲和乙同住一間，乙和丙同住一間，則甲和丙也同住一間,具有傳遞性。現(xiàn)假設a和b同住一間，d、e、f同住一間，c住一間，則R=a，a，a，b，b，a，b，b，c，c，d，d，e，e，f，f，d，e，e，d，e，f，f，e，d，f，f，d 其有向圖如圖 3.5-1所示。 第3章 二元關系圖3.5-1第3章 二元關系 定義3.52設k是一正整數(shù)而a,bI.如果對某整數(shù)m,a-b=mk,那么a和b是模k等價,寫成 ab(mo