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

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

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章 二元關(guān)系 例例3.1-2 設(shè)學(xué)生集合A1=a,b,c,d,選修課集合A2=日語,法語,成績等級(jí)集合A3=甲,乙,丙.如果四人的選修內(nèi)容及成績?nèi)缦? a 日 乙 b 法 甲 c 日 丙 d 法 乙 我們可表達(dá)為S=a,日,乙,b,法,甲,c,日,丙,d,法,乙第3章 二元關(guān)系 這里S表示學(xué)生和選修課及成績間的關(guān)系.而可能出現(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章 二元關(guān)系 定義定義 3.11 (1)AB的子集叫做A到B的一個(gè)二元關(guān)系. (2)A1A2An(n1)的子集叫做A1A2An上的一個(gè)n元關(guān)系. (3) (1)nAAAA n的子集叫做A上的n元關(guān)系n個(gè)第3章 二元關(guān)系 從定義可看出,關(guān)系是一個(gè)集合,所有定義集合的方法,都可用來定義關(guān)系 例3.1-1和例3.1-2是列舉法的例子。一個(gè)謂詞P(x1,x2,xn)可以定義一個(gè)n元關(guān)系

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

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

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

7、(x,yR)叫做關(guān)系R的值域值域 關(guān)系是序偶的集合,對(duì)它可進(jìn)行集合運(yùn)算,運(yùn)算結(jié)果定義一個(gè)新關(guān)系.設(shè)R和S是給定集合上的兩個(gè)二元關(guān)系,則RS,RS,R-S, 等可分別定義如下: x(RS)y xRyxSy x(RS)y xRyxSy x(R-S)y xRyx$y xy xRyRR第3章 二元關(guān)系 例3.1-3平面上的幾何圖形是平面R2的子集,也是一種關(guān)系.設(shè)(參看圖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章 二元關(guān)系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章 二元關(guān)系圖 3.12 第3章 二元關(guān)系 3.1.3 關(guān)系矩陣和關(guān)系圖關(guān)系矩陣和關(guān)系圖 表達(dá)有限集合到有限集合的二元關(guān)系時(shí),矩陣是一有力工具定義定義3.14給定集合A=a1,a2,am和B=b1,b2,bn,及一個(gè)A到B的二元關(guān)系R. 使.rij= 1,如果aiRbj 0,如aiRbj 則稱MR=rij矩陣是R的關(guān)系矩陣.第3章 二元關(guān)系 例例3.1-4 設(shè)A=a1,a2,B=b1,b2,b3,R=a1,b1,a2,b1,a1,b3,a2,b2,則其關(guān)

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

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

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

12、R是對(duì)稱的 x y (xAyAxRyyRx) 例如,A=1,2,3,R4=1,2,2,1,1,3,3,1,1,1是對(duì)稱的.其關(guān)系圖和關(guān)系矩陣的特點(diǎn)如圖3.17所示 第3章 二元關(guān)系圖 3.17第3章 二元關(guān)系 (4)如果對(duì)每一x,yA,xRy,yRx蘊(yùn)含著x=y,那么R是反對(duì)稱的.即A上的關(guān)系R是反對(duì)稱的 x y(xAyAxRyyRxx=y) 例如,A=1,2,3,R5=1,2,2,3是反對(duì)稱的,其關(guān)系圖和關(guān)系矩陣的特點(diǎn)如圖3.18所示. 第3章 二元關(guān)系圖 3.18第3章 二元關(guān)系 (5)如果對(duì)每一x,y,zA,xRy,yRz蘊(yùn)含著xRz,那么R是傳遞的.即A上的關(guān)系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是傳遞的.其關(guān)系圖和關(guān)系矩陣如圖3.110所示. 第3章 二元關(guān)系圖 3.19第3章 二元關(guān)系 圖 3.110第3章 二元關(guān)系 例例3.1-7 (1)任何集合上的相等關(guān)系是自反的,對(duì)稱的,反對(duì)稱的和傳遞的,但不是反自反的 (2)整數(shù)集合I上,關(guān)系是自反的,反對(duì)稱的,可傳遞的.但不是反自反的和對(duì)稱的.關(guān)系是反自反的,反對(duì)稱的,可傳遞的,但不是自反的和對(duì)稱的 (3)設(shè)=a,b,試考察上的下列關(guān)系: (i)關(guān)系“與有同樣長度”是自反的,對(duì)稱的,可傳遞的,但不是反自反的和反對(duì)稱的第3章 二

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

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

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

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

18、1是關(guān)系“是的兄弟”,R2是關(guān)系“是的父親”,那么R1R2是關(guān)系“是的叔伯”.R2R2是關(guān)系“是的祖父”第3章 二元關(guān)系 (2) 給定集合A=1,2,3,4,B=2,3,4,C=1,2,3,設(shè)R是A到B的關(guān)系;S是B到C的關(guān)系. 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章 二元關(guān)系 圖 3.22第3章 二元關(guān)系(3)設(shè)A=1,2,3,4,5,R和S都是A上二元關(guān)系.如果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章 二元關(guān)系 (4)設(shè)R是A到B的二元關(guān)系,IA,IB分別是A和B上的相等關(guān)系,則 IAR=RIB=R (5)如果關(guān)系R的值域與關(guān)系S的定義域的交集是空集,則合成關(guān)系RS是空關(guān)系.下邊介紹合成關(guān)系的性質(zhì)第3章 二元關(guān)系 定理定理3.21 設(shè)R1是從A到B的關(guān)系,R2和R3是從B到C的關(guān)系,R4是從C到D的關(guān)系,那么 (1) R1(R2R3)=R1R2R1R3 (2) R1(R2R3) R1R2R1R3 (3) (R2R3)R4=R2R4R3R4 (4) (R2R3)R4 R2R4R3R4 (1),(2),(

20、3)部分的證明留作練習(xí),我們僅證明(2)部分 第3章 二元關(guān)系證先證明公式.因?yàn)?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章 二元關(guān)系再證包含可能是真包含.舉反例證明如果A=a,B=b1,b2,b3,C=cA到B的關(guān)系R1=a,b1,a,b2B到C的關(guān)系R2=b1,c,b3,cB到C的關(guān)系R3=b2,c,b3,c

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

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

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

24、)和(2)部分用歸納法證明,留作練習(xí)。 (3) 對(duì)于(c),設(shè)nN,如果nj,那么根據(jù)S的定義,RnS.假設(shè)nj,那么我們能將n表示為i+md+k,這里kd,根據(jù)(b)部分,得Rn=Ri+k,因?yàn)閕+kj,這證明了RnS. 定理中的i,j,在實(shí)用時(shí)宜取最小的非負(fù)整數(shù),以保證S中無重復(fù)元素.第3章 二元關(guān)系圖 3.23第3章 二元關(guān)系 例3.2-2 設(shè)A=a,b,c,d,R=a,b,c,b,b,c,c,d,其關(guān)系圖如圖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、們的關(guān)系圖如圖3.24所示第3章 二元關(guān)系圖 3.24 第3章 二元關(guān)系 由于R4=R2,根據(jù)定理3.25(c),對(duì)所有nN,RnR0,R1,R2,R3,可見不必再算了.事實(shí)上易證R5=R3,R6=R4=R2,用歸納法可得R2n+1=R3和R2n=R2,這里n1.第3章 二元關(guān)系 3.2.3 合成關(guān)系的矩陣表達(dá)合成關(guān)系的矩陣表達(dá) 定理定理3.26 設(shè)X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是X到Y(jié)的關(guān)系,MR=aij是mn矩陣,S是Y到Z的關(guān)系,MS=bij是np矩陣.則MRS=cij=MRMS,這里11,2,;1,2,nijikkjkcabim jp 第3章 二元

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

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

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

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

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

31、是自反的(對(duì)稱的,傳遞的) (ii)RR (iii)對(duì)任何自反的(對(duì)稱的,傳遞的)關(guān)系R,如果 RR,那么RR第3章 二元關(guān)系 R的自反,對(duì)稱和傳遞閉包分別記為r(R),s(R)和t(R).由定義可以看出,R的自反(對(duì)稱,傳遞)閉包是含有R并且具有自反(對(duì)稱,傳遞)性質(zhì)的最小關(guān)系.如果R已經(jīng)是自反的(對(duì)稱的,傳遞的),那么,具有該性質(zhì)并含有R的最小關(guān)系就是R自身.下一定理說明這一點(diǎn). 定理定理3.34設(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第3章 二元關(guān)系 證證 (a)如果R是自反的,

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

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

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

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

36、是E (d)的自反閉包是全域關(guān)系,對(duì)稱閉包是,的傳遞閉包是全域關(guān)系 (e)空關(guān)系的自反閉包是相等關(guān)系,對(duì)稱閉包和傳遞閉包是自身 (f)設(shè)R是I上的關(guān)系,xRy當(dāng)且僅當(dāng)y=x+1,那么t(R)是關(guān)系。第3章 二元關(guān)系 定理3.38設(shè)R是集合A上的二元關(guān)系,這里A有n個(gè)元素,那么 證 設(shè)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中必有相同者,不妨設(shè)ai=aj,0ijk.于是 xRa1,a1Ra2,ai-1Rai,ajRaj+1,ak-1Ry 成立.

37、即x,yRs,這里s=k-(j-i).但這與k是最小的假設(shè)矛盾,于是kn,又x,y是任意的,故定理得證1( )niit RR 第3章 二元關(guān)系 例例3.3-3 設(shè)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是對(duì)稱的,那么r(R)和t(R)都是對(duì)稱的 (3)如果R是傳遞的,那么r(R)是傳遞的 第3章 二元關(guān)系圖 3.31第3章 二元關(guān)系 定理定理3.310 設(shè)R是集合A上的二元關(guān)系,那么 (1)rs(R)=sr(R) (2)rt(R

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

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

40、序符號(hào),由于難以書寫,通常寫作,讀做“小于或等于”,因?yàn)椤靶∮诨虻扔凇币彩且环N偏序,故不會(huì)產(chǎn)生混亂.R是偏序時(shí),aRb就記成ab. 如果R是集合A上的偏序,則 R 也是A上的偏序;如果用表示R ,可用表示R.A,和A,都是偏序集合,并互為對(duì)偶.第3章 二元關(guān)系例3.4-1(1)I,是偏序集合,這里表示整數(shù)中的“小于或等于”關(guān)系(2)(A), 是偏序集合,這里是集合間的包含關(guān)系(3)A=2,4,6,8,D代表整除關(guān)系,M代表整倍數(shù)關(guān)系,則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、且互為對(duì)偶第3章 二元關(guān)系圖 3.41 第3章 二元關(guān)系例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章 二元關(guān)系 圖 3.44第3章 二元關(guān)系定義定義3.42 設(shè)A,是一偏序集合,B是A的子集(a)元素bB是B的最大元素,如果對(duì)每一元素xB,xb(b)元素bB是B的最小元素,如果對(duì)每一元素xB,bx 例3考慮在偏序“整除”下整數(shù)1到6的集合,其哈斯圖為圖3.45(a)如果B=1,2,3,6,那么1是B的最小元素,6是B的最大元素(b)如果

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

43、44設(shè)A,是一偏序集合,B是A的子集 (a)如果對(duì)每一bB,ba,那么元素aA叫做B的上界;如果對(duì)每一bB,ab,那么元素aA叫做B的下界. (b)如果a是一上界并且對(duì)每一B的上界a有aa,那么元素aA叫做B的最小上界,記為lub;如果a是一下界并且對(duì)每一B的下界a有aa,那么元素aA叫做B的最大下界,記為glb .第3章 二元關(guān)系 例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章 二元關(guān)系 (b)考慮偏序集合I,設(shè)B=2iiN,那么B既沒有最大元素和極大元素,也沒有上界和最小上界.B的最小元素和極小元素是0,B的下界集合是iiIi0,0是最大下界. (c)考慮在偏序集合2,5,6,10,15,30,整除,其哈斯圖如圖3.47設(shè)B是全集合2,5,6,10,15,30,那么2和5都是B的極小元素,但B沒有最小元素.集合B沒有下界,所以沒有最大下界.元素30是B的最大元素,極大元素,上界,最小上界.第3章 二元關(guān)系圖 3.46 第3章 二元關(guān)系圖 3.47 第3章 二元關(guān)系 定理定理3.42 如果A,是非空有限的偏序集合,則A的極小(大)元素常存在最

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

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

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

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

49、這個(gè)偏序擴(kuò)展為線序，即拓?fù)浞诸悺Ｍ負(fù)浞诸愖詈喗莸姆椒ㄊ墙o出偏序集合的哈斯圖。上表給出的偏序集合的哈斯圖如圖3.4-9所示。 第3章 二元關(guān)系圖3.49第3章 二元關(guān)系從圖中可以看出，它有兩個(gè)極小元素C4，2和A3，5，二者可任意排序，我們不妨把C4，2排在左側(cè)（左低右高）得如下序列 C4，2，A3，5刪去這兩個(gè)極小元素后，G4，3是余下圖中唯一的極小元素。把G4，3加入已排序的序列得 C4，2，A3，5，G4，3如此以往，相繼出現(xiàn)的元素是E4，6、 D8，7和F5，10， 最后是B10，15。刪除B10，15后成為空?qǐng)D，完成拓?fù)浞诸悾玫男蛄惺?C4，2，A3，5，G4，3，E4，6，D8，

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

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

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

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

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

55、出x,那么就稱這樣的良序集合是“像自然數(shù)”的.第3章 二元關(guān)系 例例 8 (1) 設(shè)=a,b,良序集合*,標(biāo)準(zhǔn)序是像自然數(shù)的.因?yàn)槎ㄩL的串的個(gè)數(shù)有限,給定任一個(gè)串x,在x之前的串的個(gè)數(shù)有限,所以從開始,反復(fù)取后繼者,終可得出x. (2)良序集合NN,不像自然數(shù),這里按上一小節(jié)規(guī)定.因?yàn)橛性S多元素沒有直接前趨,例如5,0就是這樣,因而有無限個(gè)元素前于5,0,所以,從0,0開始,反復(fù)地取后繼者,不可能取得5,0.第3章 二元關(guān)系 像自然數(shù)的良序集合,可以應(yīng)用數(shù)學(xué)歸納法第一原理.因?yàn)榈谝辉硎墙⒃诤罄^運(yùn)算上,而這種良序集合的每一元素都可通過重復(fù)地取后繼者得到,設(shè)m0是該良序集合S,的最小元素,S(

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

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

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

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

60、學(xué)集合A=a，b，c，d，e，f，g，A中的關(guān)系R是“住在同一房間”。這是等價(jià)關(guān)系，因?yàn)?任一個(gè)人和自己同住一間，具有自反性。 若甲和乙同住一間，則乙和甲也同住一間，具有對(duì)稱性。 若甲和乙同住一間，乙和丙同住一間，則甲和丙也同住一間,具有傳遞性?，F(xiàn)假設(shè)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章 二元關(guān)系圖3.5-1第3章 二元關(guān)系 定義3.52設(shè)k是一正整數(shù)而a,bI.如果對(duì)某整數(shù)m,a-b=mk,那么a和b是模k等價(jià),寫成 ab(mo