離散數(shù)學第2章關(guān)系

1、Chapter 2 關(guān)系關(guān)系笛卡兒（笛卡兒（R.DescartesR.Descartes）15961596年年3 3月月3131日生于法國都蘭城，日生于法國都蘭城， 16501650年年2 2月月1111日日卒于瑞典斯德哥爾摩。是偉大的哲學卒于瑞典斯德哥爾摩。是偉大的哲學家、物理學家、數(shù)學家、生理學家。家、物理學家、數(shù)學家、生理學家。是歐洲近代資產(chǎn)階級哲學的奠基人之是歐洲近代資產(chǎn)階級哲學的奠基人之一，黑格爾稱他為一，黑格爾稱他為“現(xiàn)代哲學之父現(xiàn)代哲學之父”。 他是解析幾何的創(chuàng)始人。直角坐標系的創(chuàng)建，他是解析幾何的創(chuàng)始人。直角坐標系的創(chuàng)建，在代數(shù)和幾何上架起了一座橋梁，它使幾何概念可在代數(shù)和幾何

2、上架起了一座橋梁，它使幾何概念可以用代數(shù)形式來表示，幾何圖形也可以用代數(shù)形式以用代數(shù)形式來表示，幾何圖形也可以用代數(shù)形式來表示，于是代數(shù)和幾何就這樣合為一家人了。笛來表示，于是代數(shù)和幾何就這樣合為一家人了。笛卡兒堪稱卡兒堪稱1717世紀的歐洲哲學界和科學界最有影響的世紀的歐洲哲學界和科學界最有影響的巨匠之一，被譽為巨匠之一，被譽為“近代科學的始祖近代科學的始祖”。Chapter 2 關(guān)系關(guān)系賈敏母子母子父父子子母女母女母母女女表兄妹表兄妹舅舅舅舅外甥女外甥女Chapter 2 關(guān)系關(guān)系v 三個學生選修了三個學生選修了5門課程中部分課程，并且根據(jù)門課程中部分課程，并且根據(jù)學習情況由任課教師給出了

3、他們的成績。如何表學習情況由任課教師給出了他們的成績。如何表達學生、課程和成績之間的關(guān)系？達學生、課程和成績之間的關(guān)系？Chapter 2 關(guān)系關(guān)系 學生、課程和成績之間的關(guān)系可以通過表格表示。學生、課程和成績之間的關(guān)系可以通過表格表示。英英 語語數(shù)學實驗數(shù)學實驗離散數(shù)學離散數(shù)學 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 匯編語言匯編語言張三張三優(yōu)優(yōu)優(yōu)優(yōu)良良李四李四優(yōu)優(yōu)王五王五合格合格良良A AB BC CChapter 2 關(guān)系關(guān)系A(chǔ) = 張三張三, 李四李四, 王五王五;B = 英語英語, C語言語言, 離散數(shù)學離散數(shù)學, 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu), 匯編語言匯編語言;C = 優(yōu)優(yōu), 良良, 合格合格, 不合格不合格.C

4、hapter 2 關(guān)系關(guān)系vA與與B之間的關(guān)系之間的關(guān)系: R = (張三張三, 離散數(shù)學離散數(shù)學), (張三張三, 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)), (張三張三, 英語英語), (李四李四, 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)), (王五王五, C語言語言), (王五王五, 匯編語言匯編語言) A B.vA, B與與C之間的關(guān)系之間的關(guān)系: S = (張三張三, 離散數(shù)學離散數(shù)學, 優(yōu)優(yōu)), (張三張三, 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu), 良良), (張三張三, 英語英語, 優(yōu)優(yōu)), (李四李四, 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu), 優(yōu)優(yōu)), (王五王五, C語言語言, 合格合格), (王五王五, 匯編語言匯編語言, 良良) A B C.Chapte

5、r 2 關(guān)系關(guān)系v世間萬物都存在著聯(lián)系世間萬物都存在著聯(lián)系哲理哲理. v在信息科學中在信息科學中,數(shù)據(jù)與數(shù)據(jù)之間總存在一定的關(guān)系數(shù)據(jù)與數(shù)據(jù)之間總存在一定的關(guān)系.v借助于集合可以給出刻劃這種聯(lián)系的數(shù)學模型借助于集合可以給出刻劃這種聯(lián)系的數(shù)學模型. v關(guān)系這些內(nèi)容對今后學習數(shù)據(jù)結(jié)構(gòu)以及數(shù)據(jù)庫等很多關(guān)系這些內(nèi)容對今后學習數(shù)據(jù)結(jié)構(gòu)以及數(shù)據(jù)庫等很多課程都是很重要的課程都是很重要的.v我們不以個別特殊關(guān)系為研究對象我們不以個別特殊關(guān)系為研究對象,而是關(guān)注關(guān)系的而是關(guān)注關(guān)系的一般特性一般特性.nAAAR.1 關(guān)系的概念關(guān)系的概念 n元關(guān)系的定義元關(guān)系的定義設(shè)設(shè)A1，A2,An是是n個集合個集合, 把把A1

6、A2 An的任意的任意子集子集R稱為稱為A1，A2， ，An上的一個上的一個n元關(guān)系。元關(guān)系。 R上的上的n元關(guān)系的定義元關(guān)系的定義 設(shè)設(shè)A1=A2=,=An=A, 且且則稱則稱R為為A上的一個上的一個n元關(guān)系。元關(guān)系。例例 A = a, b, B = 1, 2, 3,判斷下式是否成立。判斷下式是否成立。?)3 ,(),1 ,(),2 ,(),3 ,(BAbbaaR).3 ,(),2 ,(),1 ,(),3 ,(),2 ,(),1 ,(bbbaaaBA 2元關(guān)系的定義元關(guān)系的定義設(shè)設(shè)A,B是集合是集合, 把把A B的任意子集的任意子集R稱為稱為A，B上的上的一個一個2元關(guān)系。即元關(guān)系。即R A

7、B當當B=A時，將時，將R稱為稱為A上的上的2元關(guān)系。即元關(guān)系。即R AA1 關(guān)系的概念關(guān)系的概念空關(guān)系空關(guān)系 設(shè)設(shè)A，B是集合，是集合，R是是A到到B的二元關(guān)系，若的二元關(guān)系，若R= ，則稱則稱R為空關(guān)系。為空關(guān)系。全關(guān)系全關(guān)系 設(shè)設(shè)A，B是集合，是集合，R是是A到到B的二元關(guān)系，若的二元關(guān)系，若R= AB，則稱，則稱R為全關(guān)系。為全關(guān)系。恒等關(guān)系恒等關(guān)系 設(shè)設(shè)A是集合，稱是集合，稱IA=(x，x)| x A 為為A上的恒等上的恒等關(guān)系。關(guān)系。 2.1 關(guān)系的概念關(guān)系的概念vTheorem 若若|A| = m, |B| = n, 則則A到到B的關(guān)系有的關(guān)系有2mn.vHint |A B| =

8、 mn.v顯然顯然, 若若|A| = m, 則則A上的關(guān)系有上的關(guān)系有2mm.2.1 關(guān)系的概念關(guān)系的概念v設(shè)設(shè)R A B, 若若(x, y) R, 則稱元素則稱元素x與與y有關(guān)系有關(guān)系R, 可可記為記為xRy,即即:v關(guān)系符號關(guān)系符號 任意集合符號可以作為關(guān)系符號；其次任意集合符號可以作為關(guān)系符號；其次, 對于常見的很有用的關(guān)系可以給出一個固定的特殊對于常見的很有用的關(guān)系可以給出一個固定的特殊符號符號.),(xRyRyx例題與練習例題與練習例：設(shè)集合例：設(shè)集合A=a，b，c，求集合，求集合A上的全關(guān)系和恒等關(guān)系。上的全關(guān)系和恒等關(guān)系。解：集合解：集合A上全關(guān)系上全關(guān)系RA=（a，a），（），

9、（b，b），（），（c，c），），（a，c），（），（a，b），（），（b，a），（），（b，c），（），（c，a），），（c，b） 集合集合A上恒等關(guān)系上恒等關(guān)系IA=（a，a），（），（b，b），（），（c，c）練習：設(shè)集合練習：設(shè)集合A=1，2，3，4，定義，定義A上的二元關(guān)上的二元關(guān)系系R=（a，b）| a，b A ，且（，且（ab）/2是整數(shù)是整數(shù),求求R。解：解：R=（1，1），（），（1，3），（），（2，2）,（2，4）,（3，1），（），（3，3），（），（4，2），（），（4，4）例例:實數(shù)集合實數(shù)集合R上的大于上的大于“”關(guān)系關(guān)系:.,R,| ),(yxyxyx.|qmn

10、nm.|,| ),(|yxyxyxZ整數(shù)集上的整除的定義整數(shù)集上的整除的定義:例例: 整數(shù)集整數(shù)集Z上的整除關(guān)系上的整除關(guān)系“|”.例題與練習例題與練習例例:整數(shù)集整數(shù)集Z上的模上的模m同余關(guān)系同余關(guān)系 m. (x,y) m當且僅當當且僅當m|(x-y)u設(shè)設(shè)R A B, R的定義域是由所有的定義域是由所有(x, y) R中的中的x組成組成的集合。即的集合。即 dom R = x|x A, 存在存在y B, 使得使得(x, y) Ru也就是也就是R中所有有序?qū)χ兄兴杏行驅(qū)χ械谝晃恢玫谝晃恢迷亟M成的集合元素組成的集合, 它它顯然是顯然是A的子集的子集.例如：例如：R = (1, 1), (1

11、, 3), (2, 2), (2, 4), (3,1), (3, 3), (4, 2), (4, 4), 則則dom R = 1, 2, 3, 4.關(guān)系的定義域與值域關(guān)系的定義域與值域v設(shè)設(shè)R A B, R的值域是由所有的值域是由所有(x, y) R中的中的y組成的集組成的集合。即合。即ran R = y|y B, 存在存在x A, 使得使得(x, y) Rv也就是也就是R中所有有序?qū)χ械诙恢迷亟M成的集合中所有有序?qū)χ械诙恢迷亟M成的集合, 它它是是B的子集的子集.如：如：R = (1, 1), (1, 3), (2, 2), (2, 4), (3,1), (3, 3), (4, 2),

12、 (4, 4), 則則 ran R = 1, 2, 3, 4.vRemark 由后面函數(shù)的關(guān)系定義知由后面函數(shù)的關(guān)系定義知, dom R和和ran R與函與函數(shù)的定義域與值域一致數(shù)的定義域與值域一致.關(guān)系的定義域與值域關(guān)系的定義域與值域v除關(guān)系的集合表示外除關(guān)系的集合表示外, 還可以有下列兩種表示方法還可以有下列兩種表示方法.關(guān)系圖關(guān)系圖直觀直觀,關(guān)系矩陣關(guān)系矩陣可用代數(shù)知識可用代數(shù)知識.v(1)關(guān)系圖關(guān)系圖(Graph of relation) 情形情形1 R是是A到到B(包括包括A上上)的關(guān)系的關(guān)系 A = a, b, c, d, B = 1, 2, 3, R = (a, 2), (a,

13、3), (c, 2), (d, 2).abcd123RG關(guān)系的表示關(guān)系的表示v情形情形2 R是是A上的關(guān)系上的關(guān)系 A = a, b, c, d, R = (a, b), (a, c), (c, a), (d, c), (d, d).abcd關(guān)系的表示關(guān)系的表示關(guān)系圖關(guān)系圖,.,21mxxxA ,.,21nyyyB .BAR,)(nmijRmM.,.,2 , 1,.,2 , 1,),( , 0),( , 1njmiRyxRyxmjijiij.01001000011034dcbaMR321關(guān)系的表示關(guān)系的表示關(guān)系矩陣關(guān)系矩陣例：例：A = a, b, c, d, B = 1, 2, 3, R =

14、 (a, 2), (a, 3), (c, 2), (d, 2).例如例如, A = a, b, c, B = 1, 2, 3, f: A B, f(a) = 2, f(b) = 3, f(c) = 3.),()(fyxyxf).3 ,(),3 ,(),2 ,(cbaf ?)3 , c (),3 , a (),2 , a(R 函數(shù)的關(guān)系定義函數(shù)的關(guān)系定義函數(shù)是如何轉(zhuǎn)換成關(guān)系函數(shù)是如何轉(zhuǎn)換成關(guān)系?A到到B的關(guān)系是不是的關(guān)系是不是A到到B的函數(shù)的函數(shù)?結(jié)論：不是任何一個集合結(jié)論：不是任何一個集合A A到到B B的關(guān)系都可構(gòu)成的關(guān)系都可構(gòu)成集合集合A A到到B B的函數(shù)。的函數(shù)。A到到B的關(guān)系的關(guān)系f

15、 滿足什么條件成為滿足什么條件成為A到到B的函數(shù)的函數(shù)?函數(shù)的關(guān)系定義函數(shù)的關(guān)系定義domf=A:A中任意元素都有中任意元素都有B中元素與之對應(yīng)中元素與之對應(yīng).對于任意對于任意xA，若，若(x, y1)f且且(x,y2)f,則則y1=y2 :一個一個xA只能有唯一的只能有唯一的y與之對應(yīng)。與之對應(yīng)。2.2 關(guān)系的運算關(guān)系的運算集合運算集合運算討論關(guān)系的運算是為了從已知的關(guān)系得出新的關(guān)系討論關(guān)系的運算是為了從已知的關(guān)系得出新的關(guān)系. .:,BASR.,SRSRRSRSR.RBARBAR.RAARAAR定義：定義：則有：則有：計算：計算：例例 A=2, 3, 4, 5, 6，R為為A上的整除關(guān)系上

16、的整除關(guān)系, S為為A上的小于關(guān)系上的小于關(guān)系.,SRSRRSRSR先求出先求出R和和S，再計算。，再計算。解：解：R = (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6)S = (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)為何考慮關(guān)系的逆運算為何考慮關(guān)系的逆運算? 若若x是是y的老師的老師,則則y是是x的學生的學生, .),( | ),(1ABRyxxyRBAR2.2 關(guān)系的運算關(guān)系的運算逆運算逆運算關(guān)系關(guān)

17、系R的逆關(guān)系的逆關(guān)系R-1的定義：的定義：R R-1 -1是集合是集合B B到集合到集合A A的關(guān)系。的關(guān)系。例例 A = a, b, c, d, B = 1, 2, 3, R = (a, 3), (c, 2), (a, 2), (b, 2).求求R-1.解：解：R-1=(3,a),(2,c),(2,a),(2,b)練習練習:畫出畫出GR，MR，和，和GR-1，MR-1。Theorem (逆運算與關(guān)系的集合運算并逆運算與關(guān)系的集合運算并, 交交, 補的關(guān)系補的關(guān)系)(1)(2)(3) R是是A上的關(guān)系上的關(guān)系,則則Proof (2).)(111SRSR.)(111SRSR .11 RR.)(1

18、11SRSR.)(111SRSRSRuvSRvu),()(),(111),( ,),(),( ,),(SvuRvuSuvRuv.),(11SRvu.)(11RR逆運算的性質(zhì)逆運算的性質(zhì)Theorem(對合律對合律) (1)關(guān)系關(guān)系R與關(guān)系與關(guān)系S的復(fù)合的復(fù)合R S為何考慮關(guān)系的復(fù)合運算為何考慮關(guān)系的復(fù)合運算? 若若x是是y的母親的母親, y是是z的妻子的妻子, 則則x是是z的岳母的岳母, .),( ,),( ,| ),(,SzyRyxByzxSRCBSBAR2.2 關(guān)系的運算關(guān)系的運算復(fù)合運算復(fù)合運算關(guān)系關(guān)系R與關(guān)系與關(guān)系S的復(fù)合的復(fù)合R S定義定義: :),4 ,(),3 ,(),2 ,()

19、,2 ,(),1 ,(cdbaaR ), 3(), 2(), 2(), 1(S).,(),(),(),(),(),(dbbaaaSR?),(),(zyyx,4 , 3 , 2 , 1,CBdcbaA.),( ,),( ,| ),(,SzyRyxByzxSRCBSBAR例借助于關(guān)系圖理解復(fù)合運算借助于關(guān)系圖理解復(fù)合運算:可以利用關(guān)系矩陣計算關(guān)系的復(fù)合可以利用關(guān)系矩陣計算關(guān)系的復(fù)合.abcd1234RGSG例例 設(shè)設(shè)A=0,1,2,3，R =(x,y)|x,y A, y = x+1或或y = x/2，S =(x, y)| x,y A, x = y +2，計算，計算R S, S R)1 , 2(),

20、0 , 1(SR)2 , 3 (),0 , 2 (),1 , 2(RSR =(0,1),(1,2) ,(2,3) ,(0,0) ,(2,1)S =(2,0),(3,1)Remark 關(guān)系的復(fù)合運算不滿足交換關(guān)系的復(fù)合運算不滿足交換律。即一般來說律。即一般來說R S S R.TheoremProof (1)(2).)()(TSRTSRTSRTwzSRzxCzTSRwx),( ,),( :)(),(TwzSzyRyxBy),( ,),( ,),( :TSwyRyx),( ,),()(),(TSRwx)()(TSRTSR?)()(TSRTSR關(guān)系復(fù)合的相關(guān)定理關(guān)系復(fù)合的相關(guān)定理Theorem(1)(

21、復(fù)合運算對并運算可分配復(fù)合運算對并運算可分配)(2)Remark 一般來說一般來說).()()(TRSRTSR).()()(TRSRTSR).()()(TRSRTSR關(guān)系復(fù)合的相關(guān)定理關(guān)系復(fù)合的相關(guān)定理下述定理給出復(fù)合運算與逆運算之間的關(guān)系下述定理給出復(fù)合運算與逆運算之間的關(guān)系.Theorem 2-6Proof 本性質(zhì)與矩陣的有關(guān)運算性質(zhì)類似本性質(zhì)與矩陣的有關(guān)運算性質(zhì)類似, 請注意順序請注意順序.)(111RSSRSRuvSRvu),()(),(1SuyRyvBy),( ,),( :.),(),( ,),( :1111RSvuSyuRvyBy.)( ,)(111TTTABABABAB關(guān)系復(fù)合的

22、相關(guān)定理關(guān)系復(fù)合的相關(guān)定理. 2,.,.,:210nRRRRRRRRRIRAARnnA關(guān)系關(guān)系R的方冪運算的方冪運算RnRn的定義的定義:關(guān)系關(guān)系R的方冪運算的方冪運算Rn相關(guān)定理相關(guān)定理設(shè)設(shè)R是是A上的關(guān)系，上的關(guān)系，m，n為任意的自然數(shù)，為任意的自然數(shù)，那么那么 Rm Rn=Rm+n； (Rm)n=Rmn； (Rm)-1=(R-1)m。例例設(shè)設(shè)A=a,b,c,集合集合A上的關(guān)系上的關(guān)系R=(a,b),(b,c),(c,a)，試計，試計算算Rn(n為正整數(shù)為正整數(shù))。解：解：R1=(a,b),(b,c),(c,a) R2=(a,c),(b,a),(c,b) R3=(a,a),(b,b),(c

23、,c)=IA R4=R3 R=IA R=R R5=R4 R=R3 R2=R2 當當n=3k時，時，Rn= IA 當當n=3k+1時，時，Rn= R 當當n=3k+2時，時，Rn=R2設(shè)設(shè)f: A B, g: B C, 按以前的記號按以前的記號,函數(shù)函數(shù)f與函數(shù)與函數(shù)g的復(fù)的復(fù)合記為合記為f g: 若若f (x) = y且且g(y) = z, 則則(f g)(x) = g(f(x) = z. 由于由于f A B, g B C, 關(guān)系關(guān)系f與關(guān)系與關(guān)系g的復(fù)合記為的復(fù)合記為f g: 若若(x, y) f且且(y, z) g, 則則(x, z) f g.所以所以,函數(shù)函數(shù)f與函數(shù)與函數(shù)g的復(fù)合的復(fù)合

24、f g與將其看作關(guān)系時關(guān)系與將其看作關(guān)系時關(guān)系f與關(guān)系與關(guān)系g的復(fù)合是完全的復(fù)合是完全一致一致的的.函數(shù)函數(shù)f與函數(shù)與函數(shù)g的復(fù)合的復(fù)合f g在具體應(yīng)用中在具體應(yīng)用中, 如在數(shù)據(jù)庫理論中如在數(shù)據(jù)庫理論中, 還會涉及到關(guān)系的還會涉及到關(guān)系的其他運算其他運算, 如如關(guān)系的連接運算、關(guān)系的投影運算、關(guān)關(guān)系的連接運算、關(guān)系的投影運算、關(guān)系的限制運算、關(guān)系的除運算系的限制運算、關(guān)系的除運算等等, 由于篇幅限制和側(cè)由于篇幅限制和側(cè)重點不同重點不同, 再此不作討論再此不作討論. 但為了后面討論子格的方便但為了后面討論子格的方便, 用較小的篇幅介紹關(guān)系限定運算中的一種特殊情況用較小的篇幅介紹關(guān)系限定運算中的一

25、種特殊情況: 關(guān)系在一個子集上的限定關(guān)系在一個子集上的限定.關(guān)系的其他運算關(guān)系的其他運算2.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)v前面定義的關(guān)系是一般的關(guān)系前面定義的關(guān)系是一般的關(guān)系,但在實際問題中但在實際問題中,我我們感興趣的是具有某種或同時具有某幾種特殊性質(zhì)們感興趣的是具有某種或同時具有某幾種特殊性質(zhì)的關(guān)系的關(guān)系.v設(shè)設(shè)R是集合是集合A上的關(guān)系上的關(guān)系, 常見的關(guān)系的性質(zhì)有常見的關(guān)系的性質(zhì)有5種種, 分分別介紹如下別介紹如下.國慶八天假你做什么？國慶八天假你做什么？http:/ A A, 若對于任意若對于任意x A, 均有均有(x, x) R, 則稱則稱R是是A上的自反關(guān)系上的自反關(guān)系, 或稱或稱R是

26、自反是自反的的, 或稱或稱R具有自反性具有自反性.v例例 A = a, b, c, d, R A A, 且且 R = (a, a), (a, b), (b, b), (c, c), (c, a), (d, d)?abdc1. 自反性自反性關(guān)系矩陣關(guān)系矩陣Theorem R自反自反 IA R.v顯然顯然, 空集空集上的關(guān)系只有空關(guān)系上的關(guān)系只有空關(guān)系一個一個, 該空關(guān)系該空關(guān)系是空集是空集上的自反關(guān)系上的自反關(guān)系.v如何根據(jù)如何根據(jù)R的關(guān)系圖及關(guān)系矩陣去判斷的關(guān)系圖及關(guān)系矩陣去判斷R是否自反是否自反?1. 自反性自反性定理定理若關(guān)系若關(guān)系R R是自反的，則是自反的，則 關(guān)系矩陣的特點是主對角線元

27、素全為關(guān)系矩陣的特點是主對角線元素全為1 1； 關(guān)系圖的特點是若兩個結(jié)點間存在有向弧，必是成對的。關(guān)系圖的特點是若兩個結(jié)點間存在有向弧，必是成對的。v定義定義:設(shè)設(shè)R A A, 若對于任意若對于任意x A, 均有均有(x, x) R, 則稱則稱R是是A上的反自反關(guān)系上的反自反關(guān)系, 或稱或稱R是是反自反的反自反的, 或稱或稱R具有反自反性具有反自反性.v例例 A = a, b, c, d, R = (b, a), (a, b), (b, c), (c, d), (c, a)?abcd2. 反自反性反自反性關(guān)系矩陣關(guān)系矩陣Theorem R反自反反自反 IA R = .v顯然顯然, 空關(guān)系空關(guān)系

28、是空集是空集上的反自反關(guān)系上的反自反關(guān)系.v如何根據(jù)如何根據(jù)R的關(guān)系圖及關(guān)系矩陣去判斷的關(guān)系圖及關(guān)系矩陣去判斷R是否反自反是否反自反?2.反自反性反自反性定理定理v 空集上的空關(guān)系是其上的反自反關(guān)系?？占系目贞P(guān)系是其上的反自反關(guān)系。v 若關(guān)系若關(guān)系R R是反自反的，則是反自反的，則 關(guān)系矩陣的特點是主對角線元素全為關(guān)系矩陣的特點是主對角線元素全為0 0； 關(guān)系圖的特點是每個結(jié)點處沒都有自回路。關(guān)系圖的特點是每個結(jié)點處沒都有自回路。vA上的自反關(guān)系與反自反關(guān)系的區(qū)別與聯(lián)系上的自反關(guān)系與反自反關(guān)系的區(qū)別與聯(lián)系?v(1)R既自反又反自反既自反又反自反?v(2)R自反但不是反自反自反但不是反自反?v

29、(3)R不是自反的但是反自反不是自反的但是反自反?v(4)R既不是自反的又不是反自反既不是自反的又不是反自反?思考下列問題思考下列問題定義：定義： 設(shè)設(shè)R A A, 對于任意對于任意x, y A,若若(x, y) R, 則則(y, x) R, 則稱則稱R是是A上的上的對稱對稱關(guān)系關(guān)系, 或或稱稱R是是對稱對稱的的, 或稱或稱R具有具有對稱對稱性性.v例例 A = a, b, c, d, R = (b, a), (a, b), (b, b), (d, c), (c, d)?abcd. 對稱性對稱性關(guān)系矩陣關(guān)系矩陣vTheorem R對稱對稱 R = R-1.v如何根據(jù)如何根據(jù)R的關(guān)系圖及關(guān)系矩陣

30、去判斷的關(guān)系圖及關(guān)系矩陣去判斷R是否對稱是否對稱?3.對稱性對稱性定理定理 若關(guān)系若關(guān)系R R是對稱的，則是對稱的，則關(guān)系矩陣的特點是關(guān)系矩陣是對稱矩陣；關(guān)系矩陣的特點是關(guān)系矩陣是對稱矩陣；關(guān)系圖的特點是若兩個結(jié)點間存在有向弧，必是成對的。關(guān)系圖的特點是若兩個結(jié)點間存在有向弧，必是成對的。定義：定義： 設(shè)設(shè)R A A, 對于任意對于任意x, y A,若若(x, y) R且且(y, x) R, 一定有一定有x = y, 則稱則稱R是是A上的上的反對反對稱稱關(guān)系關(guān)系, 或稱或稱R是是反對稱反對稱的的, 或稱或稱R具有具有反對稱反對稱性性.v等價說法等價說法: 設(shè)設(shè)R A A, 對于任意對于任意x,

31、 y A,若若x y, 那那么么(x, y) R與與(y, x) R不能同時成立不能同時成立,則稱則稱R是是A上的上的反反對稱對稱關(guān)系關(guān)系.反對稱性反對稱性v例例 A = a, b, c, d, R = (a, a), (a, b), (b, b), (b, c), (d, c)?abcd.反對稱性反對稱性例例關(guān)系矩陣關(guān)系矩陣Theorem R反對稱反對稱 R R-1 IA .v如何根據(jù)如何根據(jù)R的關(guān)系圖及關(guān)系矩陣去判斷的關(guān)系圖及關(guān)系矩陣去判斷R是否是否反對稱反對稱?.反對稱性反對稱性定理定理v 若關(guān)系若關(guān)系R R是反對稱的，則是反對稱的，則 關(guān)系矩陣的特點是，若關(guān)系矩陣的特點是，若aijai

32、j=1=1（i i j j），則），則ajiaji=0=0，而主對稱，而主對稱線上的元素是線上的元素是1 1或或0 0。 關(guān)系圖的特點是，如果兩個結(jié)點間有弧，則只有一條；結(jié)關(guān)系圖的特點是，如果兩個結(jié)點間有弧，則只有一條；結(jié)點有自回路或沒有自回路。點有自回路或沒有自回路。vA上的對稱關(guān)系與反對稱關(guān)系的區(qū)別與聯(lián)系上的對稱關(guān)系與反對稱關(guān)系的區(qū)別與聯(lián)系?v(1)R既對稱又反對稱既對稱又反對稱?v(2)R對稱但不是反對稱對稱但不是反對稱?v(3)R不是對稱的但是反對稱不是對稱的但是反對稱?v(4)R既不是對稱的又不是反對稱既不是對稱的又不是反對稱?思考下列問題思考下列問題v定義：定義： 設(shè)設(shè)R A A,

33、 對于任意對于任意x, y, z A,若若(x, y) R且且(y, z) R,均有均有(x, z) R, 則稱則稱R是是A上上的傳遞關(guān)系的傳遞關(guān)系, 或稱或稱R是傳遞的是傳遞的, 或稱或稱R具有傳遞性具有傳遞性.v例例 A = a, b, c, d, R = (a, a), (a, b), (b, b), (b, c), (a, c), (c, a)?vHint (c, c) R.abcd5.傳遞性傳遞性vTheorem R傳遞傳遞 R R R.vProof ()設(shè)設(shè)(x, z) R R, 則存在則存在y A, 使得使得(x, y) R, (y, z) R. 因為因為R傳遞傳遞, 所以所以(

34、x, z) R. v()對于任意對于任意x, y, z A,若若(x, y) R且且(y, z) R, 則則(x, z) R R R, (x, z) R. 5.傳遞性傳遞性定理定理v例例 A = a, b, c, d, R1 = (a, b), (a, c)傳遞傳遞, R2 = (a, b)也傳遞也傳遞?v如何根據(jù)如何根據(jù)R的關(guān)系圖及關(guān)系矩陣去判斷的關(guān)系圖及關(guān)系矩陣去判斷R是否是否傳遞傳遞?xyz111RRR222RRR5.傳遞性傳遞性例例v上面介紹的是常見的上面介紹的是常見的5種關(guān)系的性質(zhì)種關(guān)系的性質(zhì), 在實際在實際問題中可能會遇到其他性質(zhì)的關(guān)系問題中可能會遇到其他性質(zhì)的關(guān)系(參見習題參見習

35、題).v歐性歐性(Eucidean): for all x, y, z A, whenever (x, y) R and (x, z) R, then (y, z) R. v持續(xù)性持續(xù)性(serial): for all x A, there is some y A, such that (x, y) R. 1.設(shè)設(shè)A=0，1，2，3，4，5，A上的關(guān)系上的關(guān)系R=（x,y）|x,y A,x+y=5，試判斷，試判斷R具有的性質(zhì)。具有的性質(zhì)。 解：解：R=（0，5），（），（5，0），（），（1，4），）， （4，1），（），（2，3），（），（3，2） R具有反自反性、對稱性。具有反自反性、對

36、稱性。 不具有自反性，反對稱性和傳遞性。不具有自反性，反對稱性和傳遞性。例題例題2.設(shè)設(shè)R、S是集合是集合A上的對稱關(guān)系，說舉例說明上的對稱關(guān)系，說舉例說明 R S不一定對稱；不一定對稱； R S對稱對稱R S= S R。解：解： A=a,b,c,R=(a,b),(b,a),S=(b,c),(c,b) 則則 R S=(a,c),(c,a) R, R S不對稱。不對稱。 證明：證明：R，S對稱，對稱，R-1=R，S-1=S， （必要性）（必要性）R S對稱，對稱， （R S）-1=R S=S-1 R-1=S R （充分性）（充分性）（R S）-1= S-1 R-1= S R= R S R S對稱

37、對稱例題例題3.設(shè)設(shè)R1和和R2是集合是集合A上的自反關(guān)系，試證明上的自反關(guān)系，試證明R1-1，R1 R2，R1 R2也是集合也是集合A上的自反關(guān)系。上的自反關(guān)系。證明：對于集合證明：對于集合A中的任意元素中的任意元素a，若，若 R1為為A上的自反上的自反關(guān)系，有（關(guān)系，有（a，a）R1則（則（a，a）R1-1，因此，因此R1-1是是A上的自反關(guān)系。上的自反關(guān)系。 對于集合對于集合A中的任意元素中的任意元素a，若，若R1和和R2為為A上的自反關(guān)上的自反關(guān)系，有（系，有（a，a）R1且（且（a，a）R2，則，則（a，a）R1R2，因此，因此R1R2是是A上的自反關(guān)系。上的自反關(guān)系。同理可證同理可

38、證R1R2是是A上的自反關(guān)系。上的自反關(guān)系。例題例題關(guān)系的性質(zhì)與關(guān)系運算之間的關(guān)系關(guān)系的性質(zhì)與關(guān)系運算之間的關(guān)系自反自反反自反反自反對稱對稱反對稱反對稱傳遞傳遞R S R S R-S R-1 R S 2.4 關(guān)系的閉包關(guān)系的閉包 通過關(guān)系的一些運算可以得到新的關(guān)系通過關(guān)系的一些運算可以得到新的關(guān)系. 對于對于A上的關(guān)系上的關(guān)系R, 希望希望R具有某些有用的具有某些有用的性質(zhì)性質(zhì),如自反性如自反性. 若若R不具有自反性不具有自反性,通過在通過在R中添加一些有序?qū)κ蛊渥兂勺苑搓P(guān)系中添加一些有序?qū)κ蛊渥兂勺苑搓P(guān)系, 這樣也可以得到一些新的這樣也可以得到一些新的A上的關(guān)系上的關(guān)系. v例例2-38 設(shè)

39、設(shè)A = a, b, c, R = (a, a), (b, a), (b, c), (c, a), (a, c), 求出所有包含求出所有包含R的自反關(guān)系的自反關(guān)系.解：解：R1 = R (b, b), (c, c);R2 = R (b, b), (c, c), (a, b);R3 = R (b, b), (c, c), (c, b);R4 = R (b, b), (c, c), (a, b), (c, b).v顯然顯然 R1稱為稱為R的自反閉包的自反閉包., 4 , 3 , 2 , 1,1iRRi).,(),(),(),(),(),(),(),(),(ccbcaccbbbabcabaaaAA1

40、. 自反閉包自反閉包r(R)Def 2-14 設(shè)設(shè)R A A, 稱最小的包含稱最小的包含R的自反關(guān)系為的自反關(guān)系為R的自反閉包的自反閉包, 記為記為r(R).r(R)滿足滿足3個條件個條件:(1)包含包含R；(2)自反性；自反性；(3)最小性最小性.Theorem .)(AIRRr1. 自反閉包自反閉包r(R)自反閉包自反閉包r(R)的關(guān)系圖的關(guān)系圖?Def 設(shè)設(shè)R A A, 稱最小的包含稱最小的包含R的對稱關(guān)系為的對稱關(guān)系為R的對的對稱閉包稱閉包, 記為記為s(R).s(R)滿足滿足3個條件個條件:(1)包含包含R；(2)對稱性；對稱性；(3)最小性最小性.Theorem .)(1RRRs.

41、 對稱閉包對稱閉包s(R)對稱閉包對稱閉包s(R)的關(guān)系圖的關(guān)系圖?3. 傳遞閉包傳遞閉包t(R) Def 設(shè)設(shè)R A A, 稱最小的包含稱最小的包含R的的傳遞傳遞關(guān)系為關(guān)系為R的的傳遞傳遞閉包閉包, 記為記為t(R).t(R)滿足滿足3個條件個條件:(1)包含R；(2)傳遞性；(3)最小性.例例 設(shè)設(shè)A = a, b, c, R = (a, b), (b, c), (b, a), 求求t(R).解解 t(R) = (a, b), (b, c), (b, a), (a, c), (a, a), (b, b). 3. 傳遞閉包傳遞閉包t(R)Remark 由于由于(a, b), (b, c) R

42、, 要保證傳遞必須添加要保證傳遞必須添加(a, c), 但僅添加但僅添加(a, c)是不夠的是不夠的. 因為因為(a, b), (b, c), (b, a), (a, c)不傳遞不傳遞. 根據(jù)根據(jù)(a, b)和和(b, a), 還要加還要加(a, a); 根據(jù)根據(jù)(b, a)和和(a, b), 還要加還要加(b, b), 這時這時(a, b), (b, c), (b, a), (a, c), (a, a), (b, b)傳遞了傳遞了. abc)(RtG傳遞傳遞閉包閉包t(R) 的關(guān)系圖的關(guān)系圖?3. 傳遞閉包傳遞閉包t(R)例例: : A = a, b, c, dR = (a, b), (b,

43、 c), (c, d)t(R)=(a, b), (b, c), (c, d), (a, c), (b, d), (a, d)abcd)(RtG3. 傳遞閉包傳遞閉包t(R)Theorem .)(32RRRRtTheorem (1)(2)(3)Remark ).()()(2121RrRrRRr).()()(2121RsRsRRs).()()(2121RtRtRRt).()()(2121RtRtRRt關(guān)系的閉包運算與其他運算之間的聯(lián)系關(guān)系的閉包運算與其他運算之間的聯(lián)系Theorem (1)R自反自反, 則則r(R), s(R)及及t(R)自反自反.(2)R對稱對稱, 則則r(R), s(R)及及t

44、(R)對稱對稱.(3)R傳遞傳遞, 則則r(R), t(R)傳遞傳遞, s(R)不一定傳遞不一定傳遞.Remark R自反自反(對稱、傳遞對稱、傳遞) r(R) = R(s(R) = R 、 t(R) = R).閉包運算與關(guān)系的性質(zhì)的聯(lián)系閉包運算與關(guān)系的性質(zhì)的聯(lián)系下表列舉關(guān)系的性質(zhì)與閉包運算的聯(lián)系下表列舉關(guān)系的性質(zhì)與閉包運算的聯(lián)系自反自反反自反反自反對稱對稱反對稱反對稱傳遞傳遞r(R) s(R) t(R) 2.5 等價關(guān)系等價關(guān)系v在實際應(yīng)用時，具有某幾種性質(zhì)的關(guān)系是有用的在實際應(yīng)用時，具有某幾種性質(zhì)的關(guān)系是有用的.v等價關(guān)系是一種非常重要的特殊關(guān)系，它是相等關(guān)等價關(guān)系是一種非常重要的特殊關(guān)系

45、，它是相等關(guān)系系“=”、全等關(guān)系、全等關(guān)系“ ”等的一種推廣等的一種推廣.等價關(guān)系基于等價關(guān)系基于某種觀點將不同的事物看成是同一類，例如研究整某種觀點將不同的事物看成是同一類，例如研究整數(shù)時，基于能否被數(shù)時，基于能否被2整除觀點將整數(shù)分為奇數(shù)和偶數(shù)整除觀點將整數(shù)分為奇數(shù)和偶數(shù)兩類，進而有兩類，進而有“奇數(shù)加偶數(shù)是奇數(shù)奇數(shù)加偶數(shù)是奇數(shù)”的結(jié)論的結(jié)論.v等價關(guān)系以及根據(jù)它對集合進行劃分是粗糙集理論等價關(guān)系以及根據(jù)它對集合進行劃分是粗糙集理論的基礎(chǔ)的基礎(chǔ), 粗糙集理論是智能信息處理的重要方法之一粗糙集理論是智能信息處理的重要方法之一.Def 設(shè)設(shè)R A A, 若若R具有自反性、對稱性以及傳遞具有自反

46、性、對稱性以及傳遞性性, 則稱則稱R為為A上的上的等價關(guān)系.等價關(guān)系定義等價關(guān)系定義例例 設(shè)設(shè)A = a, b, c, R = (a, a), (b, b), (c, c), (b, c), (c, b), 則則R具有自反性、對稱性以及傳遞性具有自反性、對稱性以及傳遞性, 因此因此R為為A上的上的等價關(guān)系等價關(guān)系.例例 Z上的模上的模3同余關(guān)系同余關(guān)系R:則則R具有自反性、對稱性以及傳遞性具有自反性、對稱性以及傳遞性, 因此因此R為為Z上上的等價關(guān)系的等價關(guān)系.).( |3 ,Z,| ),(yxyxyxRvTheorem 設(shè)設(shè)R和和S為為A上的等價關(guān)系上的等價關(guān)系,則則R-1及及R S為為A上

47、的等價關(guān)系上的等價關(guān)系.v設(shè)設(shè)R和和S是集合是集合A上的兩個等價關(guān)系上的兩個等價關(guān)系,下表列出了等價下表列出了等價關(guān)系與關(guān)系運算的聯(lián)系關(guān)系與關(guān)系運算的聯(lián)系:R S R SR - SR SR-1R S R等價關(guān)系的關(guān)系運算等價關(guān)系的關(guān)系運算Def 設(shè)設(shè)R是是A上的等價關(guān)系，對于任意上的等價關(guān)系，對于任意a A，稱集合：，稱集合： x| x A，且（，且（a ，x） R 為元素為元素a關(guān)于等價關(guān)系關(guān)于等價關(guān)系R所在的等價類，記為所在的等價類，記為aR。等價類定義等價類定義.),( ,|aRxaAxxaR.,cbbR.,cbcR例例 設(shè)設(shè)A = a, b, c, R = (a, a), (b, b)

48、, (c, c), (b, c), (c, b), 設(shè)設(shè)A=1,2,3,4,5,6,7,8，R為為A上的關(guān)系上的關(guān)系 R=|x,y A x y(mod 3)求關(guān)系求關(guān)系R的等價類。的等價類。解：可以證明關(guān)系解：可以證明關(guān)系R是等價關(guān)系，則其等價類為：是等價關(guān)系，則其等價類為： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6 例例,.;9 , 6 , 3 , 0 , 3, 6, 9.,0R,.;10, 7 , 4 , 1 , 2, 5, 8., 1 R,.;11, 8 , 5 , 2 , 1, 4, 7.,2R;.25 ; 1 4 ;03

49、RRRRRR;.03 ; 1 2 ;2 1RRRRRR例例 Z上的模上的模3同余關(guān)系同余關(guān)系R:Theorem 設(shè)設(shè)R為為A上的等價關(guān)系上的等價關(guān)系, 對于任意對于任意x , y A, 則：則：).( |3 ,Z,| ),(yxyxyxR等價類相關(guān)定理等價類相關(guān)定理Theorem 設(shè)設(shè)R為為A上的等價關(guān)系上的等價關(guān)系, 對于任意對于任意x , y A, 則則: .RRRRyxyx.),(RyxyxRR設(shè)設(shè)R是集合是集合A上的等價關(guān)系，稱所有等價類組成上的等價關(guān)系，稱所有等價類組成的集合的集合xR|x A為集合為集合A關(guān)于等價關(guān)系關(guān)于等價關(guān)系R的商的商集，簡稱集，簡稱A的商集，記為的商集，記為A

50、/R（讀作（讀作A模模R）。）。 即：即：A/R = xR|x A: A關(guān)于關(guān)于R的商集的商集.商集的定義商集的定義Theorem 設(shè)設(shè)R是集合是集合A上的等價關(guān)系，則上的等價關(guān)系，則A關(guān)于關(guān)于R的商的商集集A/R是集合是集合A的劃分的劃分. (1)每個等價類非空每個等價類非空.(2)不同的等價類不相交不同的等價類不相交.(3)所有等價類的并就是所有等價類的并就是A.例例 Z上的模上的模3同余關(guān)系同余關(guān)系R的商集。的商集。A/R = 0R, 1R, 2RA/R = a, b, c例例 設(shè)設(shè)A = a, b, c, R = (a, a), (b, b), (c, c), (b, c), (c,

51、b),則則R的商集。的商集。 商集練習商集練習給定集合給定集合A的一個劃分的一個劃分 , 按下面的方式可以得按下面的方式可以得出出A上的一個關(guān)系上的一個關(guān)系R: (x, y) R x和和y在劃分在劃分 的同一個塊的同一個塊.思考思考 R是等價關(guān)系是等價關(guān)系?例例 設(shè)設(shè)A = a, b, c, = a, b, c, 則則R = (a, a), (b, b), (c, c), (b, c), (c, b), 它是它是A上的一個等上的一個等價關(guān)系價關(guān)系. 等價關(guān)系與集合的劃分等價關(guān)系與集合的劃分2.6 相容關(guān)系相容關(guān)系在實際問題中在實際問題中, 兩個事物具有某種共同的性質(zhì)兩個事物具有某種共同的性質(zhì),

52、 但與等價關(guān)系不同的是這種共性可能不具有傳但與等價關(guān)系不同的是這種共性可能不具有傳遞性遞性.例例 設(shè)設(shè)A = set, logic, algebra, graph, R = (x, y)|x, y A, x 和和 y有相同的字母有相同的字母, 試驗證試驗證R具有具有自反性和對稱性自反性和對稱性,但不具有傳遞性但不具有傳遞性.(set, algebra) R, (algebra, graph) R, 但但(set, graph) R. v相容關(guān)系就是對具有這種性質(zhì)的事物進行的數(shù)學描相容關(guān)系就是對具有這種性質(zhì)的事物進行的數(shù)學描述述,根據(jù)它可以得出集合的覆蓋根據(jù)它可以得出集合的覆蓋.v1.相容關(guān)系相

53、容關(guān)系vDef 設(shè)設(shè)R A A, 若若R具有自反性、對稱性則稱具有自反性、對稱性則稱R為為A上的相容關(guān)系上的相容關(guān)系.v等價關(guān)系等價關(guān)系相容關(guān)系相容關(guān)系,但相容關(guān)系不一定是等價關(guān)系但相容關(guān)系不一定是等價關(guān)系, 前例就是這方面的例子前例就是這方面的例子.相容關(guān)系定義相容關(guān)系定義v例例2-54 設(shè)設(shè)R和和S為為A上的相容關(guān)系上的相容關(guān)系, R S為為A上的相上的相容關(guān)系容關(guān)系?v設(shè)設(shè)R和和S是集合是集合A上的兩個相容關(guān)系上的兩個相容關(guān)系,下表列出了相容下表列出了相容關(guān)系與關(guān)系運算的聯(lián)系關(guān)系與關(guān)系運算的聯(lián)系:R S R SR - S R SR-1R S R相容關(guān)系的關(guān)系運算相容關(guān)系的關(guān)系運算v在上節(jié)

54、知道在上節(jié)知道, 由集合由集合A的劃分可得出集合的劃分可得出集合A的等價關(guān)系的等價關(guān)系,同樣同樣,根據(jù)集合根據(jù)集合A的覆蓋可產(chǎn)生集合的覆蓋可產(chǎn)生集合A的相容關(guān)系的相容關(guān)系. 先看先看一個例子一個例子.v例例 設(shè)設(shè)A = a, b, c , d, A1, A2是是A的覆蓋的覆蓋, 其中其中A1 = a, b, c, A2 = c, d, 令令R = (A1 A1) (A2 A2), 容易驗證容易驗證R是是A上的一個上的一個相容相容關(guān)系關(guān)系. vTheorem 若若Ai|i I是集合是集合A的覆蓋的覆蓋, 則則 是是A上的相容關(guān)系上的相容關(guān)系.IiiiAAR),(), (),(), (), (),

55、(), (),(),(),(), (),(),(cddcddccbccbaccaabbaccbbaaRvRemark 集合集合A的不同覆蓋可得出相同的的不同覆蓋可得出相同的A上的相容上的相容關(guān)系關(guān)系.v例例2-56(P70) 設(shè)設(shè)A = a, b, c , d, a, b, c, c, d和和a, b, b, c, a, c, c, d是是A的兩個不同覆蓋的兩個不同覆蓋, 按上面按上面的方式可得出相同的的方式可得出相同的A上的相容關(guān)系上的相容關(guān)系.),(),(),(),(),(),(),(),(),(bccbaccaabbaccbbaaR),(),(),(),(cddcddccsetlogic

56、setlogicalgebraalgebragraphgraphA上相容關(guān)系上相容關(guān)系R的簡化關(guān)系圖的簡化關(guān)系圖vDef 設(shè)設(shè)R是集合是集合A上的相容關(guān)系上的相容關(guān)系, C A,若對于若對于任意任意x, y C, 均有均有(x, y) R, 則稱則稱C是由相容關(guān)系是由相容關(guān)系R產(chǎn)生的相容類產(chǎn)生的相容類.v在前例中在前例中, set, set, algebra, logic, logic, algebra, logic, graph, logic, algebra, graph等是等是由相容關(guān)系由相容關(guān)系R產(chǎn)生的相容類產(chǎn)生的相容類, 而而set, logic, set, graph等不是等不是.

57、v由相容關(guān)系由相容關(guān)系R產(chǎn)生的相容類是很多的產(chǎn)生的相容類是很多的, 我們主要關(guān)心我們主要關(guān)心的是極大相容類的是極大相容類.相容類定義相容類定義Def 設(shè)設(shè)R是集合是集合A上的相容關(guān)系上的相容關(guān)系, C是由相容關(guān)系是由相容關(guān)系R產(chǎn)生產(chǎn)生的相容類的相容類, 若對于任意若對于任意C D, D不是相容類不是相容類, 則稱則稱C是由是由相容關(guān)系相容關(guān)系R產(chǎn)生的產(chǎn)生的極大相容類極大相容類.可以證明可以證明, 集合集合A中的任意元素至少在由相容關(guān)系中的任意元素至少在由相容關(guān)系R產(chǎn)生產(chǎn)生的一個極大相容類中的一個極大相容類中.在前例中在前例中, set, algebra和和logic, algebra, gra

58、ph由相容由相容關(guān)系關(guān)系R產(chǎn)生的兩個極大相容類產(chǎn)生的兩個極大相容類.極大相容類定義極大相容類定義在相容關(guān)系在相容關(guān)系R的簡化關(guān)系圖中的簡化關(guān)系圖中, 一個極大的完全一個極大的完全多邊形對應(yīng)的多邊形對應(yīng)的A中元素構(gòu)成一個極大相容類中元素構(gòu)成一個極大相容類. 所所謂謂完全多邊形完全多邊形是指該多邊形的任意兩個頂點都有是指該多邊形的任意兩個頂點都有邊邊. 一個點一個點, 一條線段一條線段? 由于集合由于集合A中的任意元素至少在由相容關(guān)系中的任意元素至少在由相容關(guān)系R產(chǎn)產(chǎn)生的一個極大相容類中生的一個極大相容類中, 所以所以所有的極大相容類所有的極大相容類構(gòu)成集合構(gòu)成集合A的一種覆蓋的一種覆蓋. 2.7

59、 偏序關(guān)系偏序關(guān)系v在解決實際問題時在解決實際問題時, 我們常依據(jù)某個標準我們常依據(jù)某個標準對事物進行比較對事物進行比較, 同時按這個標準對兩個同時按這個標準對兩個事物之間的先后進行事物之間的先后進行排序排序. 在計算機科學在計算機科學中中, 對數(shù)據(jù)進行排序是十分有意義的工作對數(shù)據(jù)進行排序是十分有意義的工作.v偏序關(guān)系是最基本、最常用的一種序關(guān)系偏序關(guān)系是最基本、最常用的一種序關(guān)系, 它本質(zhì)上是兩實數(shù)之間的小于等于關(guān)系它本質(zhì)上是兩實數(shù)之間的小于等于關(guān)系“ ”的一種推廣的一種推廣. v本節(jié)在偏序的基礎(chǔ)上本節(jié)在偏序的基礎(chǔ)上, 介紹偏序集中的特介紹偏序集中的特殊元素殊元素.Def 設(shè)設(shè)R A A,

60、若若R具有自反性、反對稱性和具有自反性、反對稱性和傳遞性傳遞性, 則稱則稱R為為A上的上的偏序關(guān)系偏序關(guān)系.偏序關(guān)系定義偏序關(guān)系定義Remark 借用數(shù)的借用數(shù)的 表示偏序表示偏序, 可讀作可讀作“小于等于小于等于”, (A, ) 稱為偏序集稱為偏序集.Def 設(shè)設(shè) 是是A上的偏序上的偏序,若對任意若對任意x, y A, 有有x y或或y x, 則稱則稱 是線性序關(guān)系是線性序關(guān)系, 簡稱簡稱線性序線性序, 又稱又稱為為全序全序.顯然顯然, 實數(shù)集實數(shù)集R上的數(shù)的小于等于關(guān)系上的數(shù)的小于等于關(guān)系 是線性序是線性序. 線性序定義線性序定義線性序關(guān)系是最常見、最簡單的一種偏序關(guān)系線性序關(guān)系是最常見、