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

1、2020/8/11,1,第四章 二元關(guān)系,主要內(nèi)容： 關(guān)系的概念及表示方法 關(guān)系的性質(zhì) 關(guān)系的運(yùn)算: 關(guān)系的復(fù)合，求逆關(guān)系，關(guān)系的閉包。 三種關(guān)系: 等價關(guān)系，相容關(guān)系， 次序關(guān)系。,2020/8/11,2,一、序偶與有序n元組 1.定義:由兩個對象x、y組成的序列稱為有序二元組，也稱之為序偶，記作；稱x、y分別為序偶的第一，第二元素。 注意，序偶與集合x,y不同： 序偶：元素x和y有次序； 集合x,y：元素x和y的次序無關(guān)緊要。,4-1 序偶與集合的笛卡爾積,2020/8/11,3,2.定義：設(shè)，是兩個序偶， 如果x=u和y=v則稱和相等， 記作=。 3 .定義：有序3元組是一個序偶,其第一

2、個元素也是個序偶。 有序3元組, c可以簡記成， 但不是有序3元組。,2020/8/11,4,4.定義：有序n元組是一個序偶,其第一個元素本身是個有序n-1元組, 記作, xn。且可以簡記成。 5. 定義= ( x1= y1) ( x2= y2) ( xn= yn),2020/8/11,5,例如“斗獸棋”的16顆棋子，,設(shè)：A=紅,藍(lán) B=象,獅,虎,豹,狼,狗,貓,鼠 每個棋子可以看成一個序偶，斗獸棋可記成集合AB ： , , , , ,2020/8/11,6,1.定義:設(shè)A、B是集合，由A的元素為第一元素，B的元素為第二元素組成序偶的集合，稱為A和B的笛卡爾積，記作AB，即 AB=|xAy

3、B 例1 設(shè)A=0,1，B=a,b，求AB ， BA， AA 。 解： AB=, BA=, AA=, 可見 ABBA 所以，集合的笛卡爾積運(yùn)算不滿足交換律。,2020/8/11,7,另外 (AB)C=,c|AB cC A(BC)=|aA BC, 因 不是有序三元組, 所以(AB)CA(BC)。故也不滿足結(jié)合律。,2.性質(zhì) 1) 如果A、B都是有限集，且|A|=m, |B|=n，則 |AB |=mn。 證明：由笛卡爾積的定義及排列組合中的乘法原理，直接推得此定理。 2) A=B=,2020/8/11,8,3) 對和滿足分配律。 設(shè)A,B,C是任意集合，則 A(BC)= (AB)(AC)； A(B

4、C)= (AB)(AC)； (AB)C= (AC)(BC)； (AB)C= (AC)(BC)； 證明 ：任取A(BC) xA yBC xA(yByC) ( xA yB)(xAyC) ABAC (AB)(AC) 所以式成立。（其余可以類似證明）,2020/8/11,9,4) 若C, 則 AB(ACBC) (CACB) 證明：充分性： 設(shè)AB，求證 ACBC 任取AC xAyC xByC (因AB) BC 所以, ACBC。 必要性：若C, 由ACBC 求證 AB 取C中元素y, 任取 xA xAyC AC BC (由ACBC ) xByC xB 所以, AB。 所以 AB(ACBC) 類似可以證

5、明 AB (CACB)。,2020/8/11,10,5) 設(shè)A、B、C、D為非空集合，則 ABCDACBD 證明：首先,由ABCD 證明ACBD 任取xA，任取yB，所以 xAyBAB CD (由ABCD ) xCyD 所以, ACBD。 其次, 由AC，BD 證明ABCD 任取AB xAyB xCyD (由AC，BD) CD 所以, ABCD 證畢。,2020/8/11,11,6)約定 (A1A2)An-1)An)=A1A2An 特別 AAA = An 設(shè)R是實(shí)數(shù)集合，則R2表示笛卡爾坐標(biāo)平面， R3表示三維空間，Rn表示n維空間。 3. 應(yīng)用 1)令A(yù)1=x|x是學(xué)號 A2=x|x是姓名

6、A3=男,女 A4=x|x是出生日期 A5=x|x是班級 A6 =x|x是籍貫 則A1A2A3 A4A5 A6中一個元素： 這就是學(xué)生檔案數(shù)據(jù)庫的一條信息，所以學(xué)生的檔案就是A1A2A3 A4A5 A6的一個子集。,2020/8/11,12,2) 令A(yù)=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z 是英文字母表 一個英文單詞可以看成有序n元組：如 at=, boy=, data=, computer= 于是可以說： atA2 ,boyA3,dataA4,computerA8, 所以英文詞典中的單詞集合可以看成是 AA2An 的一個子集

7、。 作業(yè) P105 ,2020/8/11,13,4-2 關(guān)系及其表示法,相關(guān) 按照某種規(guī)則，確認(rèn)了二個對象或多個對象之間有關(guān)系，稱這二個對象或多個對象是相關(guān)的。,例1： 大寫英文字母與五單位代碼的對應(yīng)關(guān)系R1: 令=A,B,C,D,Z =30,23,16,22,21是五單位代碼集合 =11000, 10011, 01110, 10010, 10001 R1=,.,2020/8/11,14,例2：令=1,2,3,4, A中元素間的關(guān)系R2 ： R2= , , , ,AA,關(guān)系的定義 定義1: 設(shè)A、是集合，如果AB，則稱R是一個從A到B的二元關(guān)系。如果 RAA，則稱R是A上的二元關(guān)系。二元關(guān)系簡

8、稱為關(guān)系。 定義2: 任何序偶的集合，都稱之為一個二元關(guān)系。如:R=,基本概念,2020/8/11,15,R xRy 也稱之為x與y有關(guān)系。,R xRy 也稱之為x與y沒有關(guān)系。,例3. R是實(shí)數(shù)集合，R上的幾個熟知的關(guān)系,從例3中可以看出關(guān)系是序偶(點(diǎn))的集合(構(gòu)成線、面)。,2020/8/11,16,關(guān)系的定義域與值域 定義域(domain)：設(shè)RAB，由所有R的第一個元素組成的集合，稱為R的定義域。 記作dom R，即 dom R=x|y(R) 值域(range)：設(shè)RAB，由所有R的第二個元素組成的集合，稱為R的值域。 記作ran R，即 ran R=y|x(R) 令： R1= , ,

9、 , , , , dom R1 =1,2,3,4 ran R1 =1,2,3,4,2020/8/11,17,枚舉法： 即將關(guān)系中所有序偶一一列舉出，寫在大括號內(nèi)。如R = , , , , , , , 。 謂詞公式法： 即用謂詞公式表示序偶的第一元素與第二元素間的關(guān)系。例如 R=|xR時，從x到y(tǒng)引一條有向弧(邊)。這樣得到的圖形稱為R的關(guān)系圖。,關(guān)系的表示方法,2020/8/11,18,例 設(shè)A=1,2,3,4,B=a,b,c, R1 AB,R2 AA， R1 = , R2 = , ,R1 、R2的關(guān)系圖如下：,2020/8/11,19,矩陣表示法： 設(shè)A=a1, a2, , am，B=b1,

10、 b2, , bn是個有限集， RAB，定義R的mn階矩陣 MR=(rij)mn，其中,例：R1= , R2= , ,2020/8/11,20,空關(guān)系： 因?yàn)锳B，(或AA)，所以也是一個從A到B(或A上)的關(guān)系，稱之為空關(guān)系。 即無任何元素的關(guān)系，它的關(guān)系圖中只有結(jié)點(diǎn),無任何邊；它的矩陣中全是0。 完全關(guān)系(全域關(guān)系) ： AB(或AA)本身也是一個從A到B(或A上) 的關(guān)系，稱之為完全關(guān)系。 即含有全部序偶的關(guān)系。它的矩陣中全是1。,三個特殊關(guān)系,2020/8/11,21,A上的恒等關(guān)系IA： IAAA,且IA =|xA為A上的恒等關(guān)系。 例如 A=1,2,3, 則IA =, A上的、完全

11、關(guān)系及IA的關(guān)系圖及矩陣如下：,2020/8/11,22,由于關(guān)系就是集合，所以集合的、-、 和運(yùn)算對關(guān)系也適用。 例如 A是學(xué)生集合，R是A上的同鄉(xiāng)關(guān)系，S是A上的同姓關(guān)系，則 RS：或同鄉(xiāng)或同姓關(guān)系 RS：既同鄉(xiāng)又同姓關(guān)系 R-S ：同鄉(xiāng)而不同姓關(guān)系 RS：同鄉(xiāng)而不同姓,或同姓而不同鄉(xiāng)關(guān)系 R：不是同鄉(xiāng)關(guān)系, 這里R=(AA)-R 作業(yè) P109 、c)d),關(guān)系的集合運(yùn)算,2020/8/11,23,本節(jié)中所討論的關(guān)系都是集合A中的關(guān)系。 關(guān)系的性質(zhì)主要有：自反性、反自反性、對稱性、反對稱性和傳遞性。 一. 自反性 定義:設(shè)R是集合A中的關(guān)系，如果對于任意xA都有R (xRx)，則稱R是A

12、中自反關(guān)系。 即 R是A中自反的關(guān)系x(xAxRx) 例如：在實(shí)數(shù)集合中,“”是自反關(guān)系，因?yàn)?，對任意?shí)數(shù)x，有x x.,4-3 關(guān)系的性質(zhì),2020/8/11,24,從關(guān)系有向圖看自反性:每個結(jié)點(diǎn)都有環(huán)。 從關(guān)系矩陣看自反性：主對角線都為1。,令A(yù)=1,2,3，確定以下八個關(guān)系中哪些是自反的？,2020/8/11,25,二.反自反性 定義：設(shè)R是集合A中的關(guān)系，如果對于任意的xA都有R ，則稱R為A中的反自反關(guān)系。 即 R是A中反自反的x(xAR) 從關(guān)系有向圖看反自反性:每個結(jié)點(diǎn)都無環(huán)。 從關(guān)系矩陣看反自反性：主對角線都為0。 如 實(shí)數(shù)的大于關(guān)系，父子關(guān)系是反自反的。 注意：一個不是自反的

13、關(guān)系，不一定就是反自反 的，如前邊R6、R7非自反,也非反自反。,2020/8/11,26,R2、R5、 R8、均是反自反關(guān)系。,觀察下圖：,2020/8/11,27,三.對稱性 定義:R是集合A中關(guān)系,若對任何x, yA,如果有xRy,必有yRx,則稱R為A中的對稱關(guān)系。 R是A上對稱的 xy(xAyAxRy) yRx) 從關(guān)系有向圖看對稱性:在兩個不同的結(jié)點(diǎn)之間，若有邊的話，則有方向相反的兩條邊。 從關(guān)系矩陣看對稱性：以主對角線為對稱的矩陣。 例 鄰居關(guān)系和朋友關(guān)系是對稱關(guān)系。,2020/8/11,28,R3、R4、 R6 、 R8均是對稱關(guān)系。,2020/8/11,29,四.反對稱性 定

14、義:設(shè)R為集合A中關(guān)系,若對任何x, yA,如果有xRy,和yRx,就有x=y,則稱R為A中反對稱關(guān)系 。,由R的關(guān)系圖看反對稱性：兩個不同的結(jié)點(diǎn)之間最多有一條邊。 從關(guān)系矩陣看反對稱性：以主對角線為對稱的兩個元素中最多有一個1。 另外對稱與反對稱不是完全對立的，有些關(guān)系它既是對稱也是反對稱的，如空關(guān)系和恒等關(guān)系。,2020/8/11,30,上面R1、R2、R4、R5、R8均是反對稱關(guān)系。 R4、R8既是對稱也是反對稱的。,2020/8/11,31,五. 傳遞性 定義:R是A中關(guān)系，對任何x,y,zA,如果有xRy,和yRz,就有xRz,則稱R為A中傳遞關(guān)系。 即R在A上傳遞 xyz(xAyA

15、zAxRyyRz)xRz) 例 實(shí)數(shù)集中的、，集合、是傳遞的。 從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳遞性。必須直接根據(jù)傳遞的定義來檢查。 檢查時要特別注意使得傳遞定義表達(dá)式的前件為F的時候此表達(dá)式為T，即是傳遞的。 即若R與R有一個是F時(即定義的前件為假)，R是傳遞的。,例如 A=1,2,下面A中關(guān)系R是傳遞的。 通過帶量詞的公式在論域展開式說明R在A上傳遞,xyz(xAyAzAxRyyRz)xRz) xyz(xRyyRz)xRz) (為了簡單做些刪改) yz(1RyyRz)1Rz)yz(2RyyRz)2Rz) (z(1R11Rz)1Rz)z(1R22Rz)1Rz) (z(2R11Rz)

16、2Rz) (z(2R22Rz)2Rz) (1R11R1)1R1)(1R11R2)1R2) (1R22R1)1R1)(1R22R2)1R2) (2R11R1)2R1) (2R11R2)2R2) (2R22R1)2R1) (2R22R2)2R2) (FF)F)(FT)T)(TF)F)(TF)T) (FF)F) (FT)F)(FF)F)(FF)F)T,2020/8/11,33,以上R1、R3、R4、R5、R8均是傳遞的關(guān)系。,本節(jié)要求： 1.準(zhǔn)確掌握這五個性質(zhì)的定義。 2.熟練掌握五個性質(zhì)的判斷和證明。 R是A中自反的x(xAxRx) R是A中反自反的x(xAR) R是A上對稱的xy(xAyAxRy

17、) yRx) R是A上反對稱的 xy(xAyAxRyyRx) x=y) xy(xAyAxyxRy)y x) R在A上傳遞 xyz(xAyAzAxRyyRz)xRz) 注意 性質(zhì)表達(dá)式的前件為F時此表達(dá)式為T，即R是滿足此性質(zhì)的。 (自反和反自反性除外),2020/8/11,35,2020/8/11,36,下面歸納這八個關(guān)系的性質(zhì)：Y-有 N-無,2020/8/11,37,2020/8/11,38,練習(xí)1:令I(lǐng)是整數(shù)集合，I上關(guān)系R定義為： R=|x-y可被3整除， 求證R是自反、對稱和傳遞的。 證明：自反性：任取xI, 因 x-x=0, 0可被3整除,所以有R, 故R自反。 對稱性：任取x,y

18、I,設(shè)R, 由R定義得 x-y可被3整除, 即x-y=3n(nI)， y-x=-(x-y)=-3n=3(-n), -nN R, R是對稱的。 傳遞性:任取x,y,zI,設(shè)xRy, yRz, 由R定義得 x-y=3m, y-z=3n (m.nI) x-z= (x-y)+(y-z)=3m+3n=3(m+n), m+nN 所以xRz, 所以R傳遞。 證畢,2020/8/11,39,練習(xí)2：設(shè)R是集合A上的一個自反關(guān)系,求證： R是對稱和傳遞的，當(dāng)且僅當(dāng)和 在R中,則有也在R中。 證明：必要性 已知R是對稱和傳遞的。 設(shè)R 又R，(要證出 R ) 因R對稱的故R,又已知R 由傳遞 性得R。所以有如果和

19、在R 中,則有也在R中。 充分性 已知任意 a,b,cA，如和在 R中,則有也在R中。,2020/8/11,40,先證R對稱 任取 a,bA 設(shè)R，(要證出 R ) 因R是自反的,所以R，由 R且R，根據(jù)已知條件得 R ，所以R是對稱的。 再證R傳遞 任取 a,b,cA 設(shè)R，R。 (要證出R ) 由R是對稱的,得R ，由 R且R，根據(jù)已知條件得 R ， 所以R是傳遞的。 作業(yè) 第113頁 、,2020/8/11,41,4-4 關(guān)系的復(fù)合,下面介紹由兩個關(guān)系生成一種新的關(guān)系，即關(guān)系的復(fù)合運(yùn)算。 例如，有3個人a,b,c，A=a,b,c， R是A上兄妹關(guān)系， S是A上母子關(guān)系， RS 即a是b的

20、哥哥, b是a的妹妹; b是c的母親，c是b的兒子。 則a和c間就是舅舅和外甥的關(guān)系,記作 RS, 稱它是R和S的復(fù)合關(guān)系。,2020/8/11,42,1.定義:設(shè)R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，則R和S的復(fù)合關(guān)系記作RS 。定義為： RS =|xXzZ y(yY RS) 顯然， RS 是從X到Z的關(guān)系。 2.復(fù)合關(guān)系的計(jì)算方法(俗稱過河拆橋法) A=1,2,3 B=1,2,3.4 C=1,2,3,4,5 RAB SBC 枚舉法 R=, S=, 則 RS =,2020/8/11,43,有向圖法, 關(guān)系矩陣法 令A(yù)=a1, a2, am B=b1, b2, bn C=c1, c2, ct

21、 RAB SBC,2020/8/11,44,2020/8/11,45, 謂詞公式法 設(shè)I是實(shí)數(shù)集合，R和S都是I上的關(guān)系，定義如下： R=| y=x2+3x S=| y=2x+3,所以 RS =| y=2x2+6x+3,三.性質(zhì) 關(guān)系復(fù)合運(yùn)算不滿足交換律，但是 1.滿足結(jié)合律: RAB SBC TCD 則,2020/8/11,46,b(bBR (S T) b(bBRc(cCST) bc(bBR(cCST) cb(cC(bBRST) c (cCb(bBRS)T) c (cC(R S)T) ,所以,可以用下圖形象表示:,證明：任取,2020/8/11,47,2. RAB SBC TBC,證明 任取

22、R (ST) b(bBRST) b(bBR(ST) b(bBRS) (bBRT) b(bBRS) b(bBRT) R SR T (R S)(R T) 所以R (ST)=(R S)(R T),2020/8/11,48,證明 任取R (ST) b(bBRST) b(bBR(ST) b(bBRS) (bBRT) b(bBRS) b(bBRT) R S R T (R S)(R T) 所以 R (ST)(R S)(R T) x(A(x)B(x) xA(x)xB(x),2020/8/11,49,3. R是從A到B的關(guān)系，則,驗(yàn)證:,令A(yù)=1,2,3, B=a,b,c,d,從這兩個圖看出它們的復(fù)合都等于R。

23、,2020/8/11,50,4. 關(guān)系的乘冪 令R是A上關(guān)系，由于復(fù)合運(yùn)算可結(jié)合，所以 關(guān)系的復(fù)合可以寫成乘冪形式。即,例如R是A上關(guān)系，如上圖所示,可見 R2,表明在R圖上有從a到c有兩條邊的路徑: abc;R3,表明在R圖上有從a到d有三條 邊的路徑:abcd。.如果Rk,表明在 R圖上有從x到y(tǒng)有k條邊(長為k)的路徑(x,yA)。,有,(m,n為非負(fù)整數(shù)),2020/8/11,51,4-5 逆關(guān)系,一.定義 R是從A到B的關(guān)系，如果將R中的所有序偶的 兩個元素的位置互換，得到一個從B到A的關(guān)系， 稱之為R的逆關(guān)系，記作RC，或 R-1。 RC=|R RC R 二. 計(jì)算方法 1. R=

24、, RC =,2020/8/11,52,2. RC的有向圖：是將R的有向圖的所有邊的方向顛倒一下即可。 3. RC的矩陣 M =(MR)T 即為R矩陣的轉(zhuǎn)置。如,三.性質(zhì) 令R、S都是從X到Y(jié)的關(guān)系，則 1. (RC)C = R 2. (RS)C = RCSC 。 3. (RS)C = RCSC 。 4. (RS)C = RCSC 。,2020/8/11,53,證明1：任取(RS)C，則 (RS)C RS RS RCSC RCSC 所以 (RS)C = RCSC ，其它類似可證。 5. RS RC SC 。 證明：充分性，已知RC SC ，則任取R RC SC S RS 必要性，已知R S，則

25、任取RC R S SC RCSC,2020/8/11,54,6.(R)C=RC 證明:任取(R)C RR RC RC (R)C=RC,7.令R是從X到Y(jié)的關(guān)系，S是Y到 Z的關(guān)系，則 (R S)C= SC RC 。 (注意RC SC ) 證明：任取(R S)C R S y(yYRS) y(yYSCRC) SC RC 所以(R S)C= SC RC,2020/8/11,55,8. R是A上關(guān)系，則 R是對稱的，當(dāng)且僅當(dāng) RC =R R是反對稱的，當(dāng)且僅當(dāng) RRC IA。 證明： 充分性，已知 RC =R (證出R對稱) 任取x,yA 設(shè)R,則RC,而RC =R 所以有R ，所以R對稱。 必要性，

26、已知R 對稱，(證出RC =R) 先證RCR，任取RC,則R,因R對稱 所以有R，所以RCR。 再證R RC，任取R, 因R對稱，所以有 R，則RC, 所以RRC。 最后得RC =R 。,2020/8/11,56,證明 充分性，已知RRC IA，(證出R反對稱) 任取x,yA 設(shè)R 且R， RRRRC， RRC IA (因RRC IA ) x=y 所以R反對稱。 必要性，已知R反對稱，(證出RRC IA) 任取RRC RRCRRC RR x=y (因R反對稱) IA 所以RRC IA 。,作業(yè)：第118頁 a)b)、,2020/8/11,57,4-6 關(guān)系的閉包運(yùn)算,關(guān)系的閉包是通過關(guān)系的復(fù)合

27、和求逆構(gòu)成的一個新的關(guān)系。 這里要介紹關(guān)系的自反閉包、對稱閉包和傳遞閉包。,一.例子 給定 A中關(guān)系R，如圖所示， 求A上另一個關(guān)系R，使 得它是包含R的“最小的”(序偶 盡量少)具有自反(對稱、傳遞)性的關(guān)系。 這個R就是R的自反(對稱、傳遞)閉包。,2020/8/11,58,這三個關(guān)系圖分別是R的自反、對稱、傳遞閉包。,二.定義：給定 A中關(guān)系R,若A上另一個關(guān)系R， 滿足：RR； R是自反的(對稱的、傳遞的)； R是“最小的”，即對于任何A上自反(對稱、傳遞)的關(guān)系R,如果RR,就有RR。則稱R是R的自反(對稱、傳遞)閉包。記作r(R)、s(R)、t(R)(reflexive、symme

28、tric、transitive),2020/8/11,59,三.計(jì)算方法 定理1.給定 A中關(guān)系R,則 r(R)=RIA。 證明：令R =RIA,顯然R是自反的和R R ，下面證明R是“最小的”：如果有A上自反關(guān)系R且R R,又IA R,所以 RIA R,即R R 。所以R就是R的自反閉包。即r(R)=RIA 。 定理2.給定 A中關(guān)系R,則 s(R)=RRC 。 證明方法與1.類似。 定理3.給定 A中關(guān)系R,則 t(R)=RR2R3. 。 證明：令R = RR2R3., 顯然有 R R ；,2020/8/11,60,證R是傳遞的：任取x,y,zA,設(shè)有 R R, 由R定義得必存在整數(shù)i,j

29、使得Ri , Rj ,根據(jù)關(guān)系的復(fù)合得Ri+j, 又因Ri+j R,所以 R, R傳遞。 證R是“最小的”：如果有A上傳遞關(guān)系R且RR,（證出R R ）任取 R ,則由R定義得必存在整數(shù)i,使得Ri ,根據(jù)關(guān)系的復(fù)合得A中必存在i-1個元素e1, e2,.,ei-1，使得 (見49頁) RR.R。因RR, 有 R R .R 。 由于R傳遞，所以有 R 。 R R 。 綜上所述， R就是R的傳遞閉包，即 t(R)=RR2R3=Ri,2020/8/11,61,用上述公式計(jì)算t(R)，要計(jì)算R的無窮大次冪,好象無法實(shí)現(xiàn)似的。其實(shí)則不然，請看下例: A=1,2,3 A中關(guān)系R1,R2,R3,如下： R

30、1=, R2 =, R3 =, R12 = ,R13 = R14 = 所以 t(R1)= R1 R12 R13 = R1 R22 =, R23=, R23=IA, R24= R2 . t(R2)= R2 R22 R23 R32 =, ,R33 = R32 t(R3)= R3R32,2020/8/11,62,定理4.給定 A中關(guān)系R,如果A是有限集合，|A|=n 則 t(R)=RR2.Rn 。 證明：令R =RR2R3., R =RR2.Rn 顯然有R R ,下面證明R R ： 任取 R,由R定義得必存在最小的正整數(shù)i 使得Ri , (下面證明in)如果in,根據(jù)關(guān)系的復(fù)合得A中必存在i-1個元

31、素e1, e2,.,ei-1，使得 RR.R。上述元素序列: x=e0, e1, e2,.,ei-1,y=ei中共有i+1個元素，i+1n , 而A 中只有n個元素，所以上述元素中至少有兩個相同，設(shè)ej=ek (jk)，于是R的關(guān)系圖中會有下面這些邊：,2020/8/11,63,從此圖中刪去回路中k-j(k-j1)條邊后得Ri-(k-j)，i-(k-j)R, 于是 R R 。 最后得 R = R ，所以 t(R)=RR2.Rn 定理證畢。,2020/8/11,64,求t(R)的矩陣Warshall算法： |X|=n, RXX,令MR=A R2的矩陣為A2， Rk的矩陣為Ak .于是t(R)的矩

32、陣記作MR+=A+A2+Ak + (+是邏輯加) 置新矩陣 A :=MR ; 置 i=1; 對所有 j ,如果Aj,i =1 ,則對k=1,2,n Aj,k:=Aj,k+Ai,k; /*第j行+第i行,送回第j行*/ i加1; 如果in, 則轉(zhuǎn)到步驟，否則停止。,2020/8/11,65,舉例，令X=1,2,3,4, X中關(guān)系R圖如右圖所示。 運(yùn)行該算法求t(R)的矩陣：,A=MR=,i=1 (i-列, j-行) A4,1=1 L1+L4L4,最后 A=Mt(R),i=2 A1,2=1 A2,2=1 A4,2=1 L1+L2L1 L2+L2L2 L4+L2L4,i=3 A1,3=1, A2,3

33、=1, A4,3=1 L1+L3L1 L2+L3L2 L4+L3L4,i=4 A1,4=1 A4,4=1 L1+L4L1 L4+L4L4,2020/8/11,66,四.性質(zhì) 定理5. R是A上關(guān)系，則 R是自反的，當(dāng)且僅當(dāng) r(R)=R. R是對稱的，當(dāng)且僅當(dāng) s(R)=R. R是傳遞的，當(dāng)且僅當(dāng) t(R)=R. 定理6. R是A上關(guān)系，則 R是自反的，則s(R)和t(R)也自反。 R是對稱的，則r(R)和t(R)也對稱。 R是傳遞的，則r(R)也傳遞。 證明: 因?yàn)镽自反,由定理5得r(R)=R,即 RIA=R, r(s(R)=s(R)IA=(RRC)IA = (RIA)RC=r(R)RC

34、=RRC =s(R)s(R)自反,2020/8/11,67,類似可以證明t(R)也自反。 證明. 證明t(R)對稱: (t(R)C=(RR2.Rn.)C = RC(R2)C .(Rn)C. = RC(RC)2 .(RC)n. =RR2.Rn. (R對稱，RC =R) =t(R) 所以t(R)也對稱。 類似可以證明r(R)也對稱。 證明. 證明r(R)傳遞:先用歸納法證明下面結(jié)論: (RIA)i= IARR2.Ri i=1時 RIA= IAR 結(jié)論成立。 假設(shè)ik 時結(jié)論成立，即 (RIA)k= IARR2.Rk,2020/8/11,68,當(dāng)i=k+1時 (RIA)k+1=(RIA)k (RIA

35、) = (IARR2.Rk） (IAR) = (IARR2.Rk)(RR2.Rk+1) = IARR2.RkRk+1 所以結(jié)論(RIA)i= IARR2.Ri成立. t(r(R)=t(RIA) = (RIA)(RIA)2(RIA)3. =(IAR)(IARR2)(IARR2R3). = IARR2R3.= IAt(R) = IAR (R傳遞t(R)=R) =r(R) 所以r(R)也傳遞。,2020/8/11,69,定理7：設(shè)R1、R2是A上關(guān)系，如果R1R2 ，則 r(R1) r(R2) s(R1) s(R2) t(R1)t(R2) 證明 r(R1)=IAR1IAR2= r(R2) ，類似可證

36、。 定理8：設(shè)R是A上關(guān)系，則 sr(R)=rs(R) tr(R)=rt(R) st(R)ts(R) 證明： sr(R)=r(R)(r(R)c=(RIA)(RIA)c = (RIA)(RcIAc) =RIARcIA = (RRc)IA= s(R)IA=rs(R) 的證明用前邊證明的結(jié)論： (RIA)k= IARR2.Rk可證，這里從略。,2020/8/11,70, 因 Rs(R) 由定理7得 t(R)ts(R) st(R)sts(R) 因s(R)對稱，有定理6得ts(R) 也對稱，由定理5得 sts(R)=ts(R) 所以有st(R)ts(R) 。 證明完畢。,練習(xí)：給定A中關(guān)系R如圖所示：分

37、別畫出r(R)、s(R) 、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R) 、ts(R)的圖。,2020/8/11,72,本節(jié)重點(diǎn)掌握閉包的定義、計(jì)算方法和性質(zhì)。 作業(yè)：P127 、,2020/8/11,73,4-7 集合的劃分與覆蓋,一.定義 設(shè)X是一個非空集合,A=A1, A2,. ,An,Ai AiX (i=1,2,.,n),如果滿足A1A2.An =X (i=1,2,., n)則稱A為集合X的覆蓋。 設(shè)A=A1, A2,. ,An是X一個覆蓋, 且AiAj= (ij,1i,jn)則稱A是X的劃分,每個Ai均稱為這個劃分的一個劃分類。 例 X=1,2,3, A1=1

38、,2,3, A2=1,2,3, A3=1,2,3, A4=1,2,2,3, A5=1,3 A1, A2 ,A3 ,A4 是覆蓋。 A1, A2 ,A3也是劃分。 劃分一定是覆蓋；但覆蓋不一定是劃分。,2020/8/11,74,二.最小劃分與最大劃分 最小劃分：劃分塊最少的劃分。即只有一個劃分塊的劃分，這個劃分塊就是X本身。如A1=1,2,3 。 最大劃分：劃分塊最多的劃分。即每個劃分塊里只有一個元素的劃分。如A2 =1,2,3 。 A1,A2,A3是一種劃分,其中A1是最小劃分,A2是最大劃分。,2020/8/11,75,三.交叉劃分 例 X是東大學(xué)生集合, A和B都是X的劃分： A=M,W,

39、MX, WX, M=男生,W=女生 B=L,N,LX, NX, L=遼寧人,N=非遼寧人,C=LM , LW , NM , NW ,稱C是X的交叉劃分。,2020/8/11,76,定義：若A=A1, A2,. ,Am與B=B1,B2,.,Bn都是集合X的劃分,則其中所有的AiBj,組成的集合C,稱為C是A與B兩種劃分的交叉劃分。 證明:在C中任取元素, AiBjX (AiX,BjX) (A1B1)(A1B2).(A1Bn)(A2B1) (A2Bn). (AmB1)(AmB2).(AmBn) =(A1( B1B2B3.Bn)(A2( B1B2B3. Bn). (Am( B1B2B3. Bn) =

40、 (A1A2A3.Am) ( B1B2B3. Bn) =XX=X,2020/8/11,77,再驗(yàn)證C中任意兩個元素不相交： 在C中任取兩個不同元素AiBh和AjBk,考察 (AiBh) (AjBk) (i=j和h=k不同時成立) = (AiAj)(BhBk) ij ,hk (AiAj)(BhBk) =Ai= ij ,hk (AiAj)(BhBk)= ij, h=k (AiAj)(BhBk)= Bh = 綜上所述，C是X的劃分。 作業(yè)：第130頁 (1),2020/8/11,78,一.等價關(guān)系 1.定義:設(shè)R是A上關(guān)系,若R是自反的、對稱的和傳遞的，則稱R是A中的等價關(guān)系。 若a,bA，且aRb

41、，則稱a與b等價。 例子，集合A=1,2,3,4,5,6,7, R是A上的模3同余關(guān)系，即 R=|x-y可被3整除(或x/3與y/3的余數(shù)相同) 即R x(mod 3)=y(mod3),4-8 等價關(guān)系與等價類,2020/8/11,79,上例中的關(guān)系為： R=, ,2.等價關(guān)系的有向圖 1)完全關(guān)系(全域關(guān)系A(chǔ)A)圖，下面分別是當(dāng)A中只有1、2、3個元素時的完全關(guān)系圖。,A=1,A=1,2,A=1,2,3,2020/8/11,80,2.等價關(guān)系的有向圖 模3同余關(guān)系R的圖： 從關(guān)系圖可看出R是自反、對稱、傳遞的關(guān)系，所以R是等價關(guān)系。,等價關(guān)系R的有向圖可能由若干個獨(dú)立子圖(R圖的一部分)構(gòu)成

42、的，每個獨(dú)立子圖都是完全關(guān)系圖。 上述關(guān)系R圖就是由三個獨(dú)立的完全圖構(gòu)成的。 下面給出八個關(guān)系如圖所示，根據(jù)等價關(guān)系有向圖的特點(diǎn)，判斷哪些是等價關(guān)系。,2020/8/11,81,下面是A =1,2,3中關(guān)系：,2020/8/11,82,思考題：A=1,2,3,可構(gòu)造多少個A中不同的等價關(guān)系？可以根據(jù)等價關(guān)系有向圖的特點(diǎn)來考慮。 如果等價關(guān)系R中有 a)三個獨(dú)立子圖的情形，則( )個等價關(guān)系 。 b)二個獨(dú)立子圖的情形，則( )個等價關(guān)系 。 c)一個獨(dú)立子圖的情形，則( )個等價關(guān)系 。 一共有( )個中不同的等價關(guān)系。,2020/8/11,83,二. 等價類,1.定義：R是A上的等價關(guān)系，a

43、A,由a確定的集合aR: aR=x|xAR 稱集合aR為由a形成的R等價類。簡稱a等價類。 可見 xaR R 上例，A=1,2,3,4,5,6,7, R是A上的模3同余關(guān)系， 1R=1,4,7= 4R = 7R -余數(shù)為1的等價類 2R=2,5= 5R -余數(shù)為2的等價類 3R=3,6= 6R -余數(shù)為0的等價類 思考題：此例為什么只有三個等價類？,2020/8/11,84,2. 由等價關(guān)系圖求等價類：R圖中每個獨(dú)立子圖上的結(jié)點(diǎn)，構(gòu)成一個等價類。 不同的等價類個數(shù)=獨(dú)立子圖個數(shù)。,上述三個等價關(guān)系各有幾個等價類？說出對應(yīng)的各個等價類。,2020/8/11,85,3.等價類性質(zhì) R是A上等價關(guān)系

44、，任意a,b,cA 同一個等價類中的元素，彼此有等價關(guān)系R。 即任意x,yaR，必有R 證明：任取x,yaR，由等價類定義得R, R ,由R對稱得R，又由R傳遞得R。,2020/8/11,86, aRbR=， 當(dāng)且僅當(dāng) R。 證明:設(shè)R，假設(shè)aRbR,則存在xaRbR， xaRxbR, R ,R,由R對稱得R又由R傳遞得R,產(chǎn)生矛盾。 若aRbR=,而R,由等價類定義得baR, 又因?yàn)閎Rb,所以bbR，所以baRbR，產(chǎn)生矛盾。,2020/8/11,87, aR=bR 當(dāng)且僅當(dāng) R。 證明：若R，則任何xaR，有R，由對稱性得R，再由傳遞性得R,xbR，所以aRbR。 類似可證bRaR。 a

45、R=bR。 如果aR=bR，由于有aRa,所以aaR ，abR ，所以有R，由對稱性得R。 .A中任何元素a,a必屬于且僅屬于一個等價類。 證明：A中任何元素a,由于有aRa,所以aaR ，如果 abR ，所以有R. 由性質(zhì)得：aR=bR 。,2020/8/11,88,.任意兩個等價類 aR、bR， 要么aR=bR ，要么aRbR= 。 (因?yàn)橐碦，要么R。) . R的所有等價類構(gòu)成的集合是A的一個劃分。 (由性質(zhì)即得。) (這個劃分稱之為商集) 性質(zhì)（4）說明了覆蓋性，性質(zhì)（5）說明了不相交性,2020/8/11,89,三. 商集,定義：R是A上等價關(guān)系，由R的所有等價類構(gòu)成的集合稱之為A

46、關(guān)于R的商集。記作A/R。即 A/R=aR |aA,例如A=1,2,3,4,5,6,7 , R上模3同余關(guān)系，則 A/R= 1R,2R,3R =1.4.7,2,5,3,6,2020/8/11,90,練習(xí): X=1,2,3,X上關(guān)系R1、R2 、R3，如上圖所示。 X/R1=1R1,2R1,3R1=1,2,3 X/R2=1R2 ,2R2=1,2,3 X/R3=1R3=1,2,3,2020/8/11,91,定理: 集合A上的等價關(guān)系R，決定了A的一個劃分，該劃分就是商集A/R。 證明：由等價類性質(zhì)可得 ： 1) A/R中任意元素aR，有aRA。 2) 設(shè)aR,bR是A/R的兩個不同元素，有aRbR

47、= 3) 因?yàn)锳中每個元素都屬于一個等價類，所以所有等價類的并集必等于A。 所以商集A/R是A的一個劃分。 定理： 設(shè)R1和R2是非空集合A上的等價關(guān)系，則 A/R1=A/R2 當(dāng)且僅當(dāng) R1=R2 。 (這個定理顯然成立。),2020/8/11,92,四. 由劃分確定等價關(guān)系,例如，X=1,2,3,4,A=1,2,3,4, A是X的一個劃分， 求X上一個等價關(guān)系R，使得X/R=A。 顯然由圖可得：R=1,223242 。,一般地A=A1,A2,An是X的一個劃分，則構(gòu)造一個X中的等價關(guān)系R，使得X/R=A。R=A12A22,An2 其中Ai= Ai2Ai2， 下面證明R是X中的等價關(guān)系。,定

48、理: 集合X的一個劃分可以確定X上的一個等價關(guān)系。 證明：假設(shè)A=A1, A2,. ,An是X的一個劃分，如下構(gòu)造X 上的一個等價關(guān)系R: RA12A22An2，其中Ai2=Ai2Ai2， 1) 證R自反：任取aX，因?yàn)锳是X的劃分，必存在 AiA使aAi ,于是AiAi , 又AiAi R 有aRa。 2) 證R對稱：任取a,bX, 設(shè)aRb，必存在AiA使得 AiAi ,于是a,bAi , bRa, R是對稱的。 3) 證R傳遞：任取a,b,cX, 設(shè)aRb，bRc, 必存在AiA使得AiAi ,AiAi ,于是a,b,cAi , 所以AiAi ，又AiAi R 有aRc 所以R傳遞。最后

49、得R是集合X中的等價關(guān)系。,2020/8/11,94,本節(jié)重點(diǎn)： 等價關(guān)系概念、證明。 等價類概念、性質(zhì)。 求商集。 作業(yè)：P134 、,2020/8/11,95,4-9 相容關(guān)系,定義:給定集合X上的關(guān)系r, 若r是自反的、對稱的,則r是A上相容關(guān)系。 例子：X 是由一些英文單詞構(gòu)成的集合。 X=fly, any, able, key, book, pump, fit, X上關(guān)系r: r=|X,X且與含有相同字母,2020/8/11,96,r的有向圖： 看出有自反、 對稱性。而 不傳遞。,相容關(guān)系的簡化圖和簡化矩陣,圖的簡化：不畫環(huán)； 兩條對稱邊用一條無向直線代替。,矩陣的簡化：因?yàn)閞的矩陣

50、是對稱陣且主對角線全是1，用下三角矩陣(不含主對角線)代替r的矩陣。,令x1=fly, x2= any, x3= able, x4=key, x5=book, x6= pump, x7= fit, X=x1 ,x2, x3, x4, x5, x6 ,x7, r的簡化圖為：,2020/8/11,98,相容類及最大相容類,定義：設(shè)r是集合X上的相容關(guān)系,CX,如果對于C中任意元素x,y有r ,稱C是r的一個相容類。 上例中x1,x2,x3,x4,x1,x2,x3,x2,x3,x4,x1,x2, x4, x3,x4,x5,x1,x3,x4,x1,x2,x3,x4,x1,x7,x6 都是相容類。上述相

51、容類中，有些相容類間有真包含關(guān)系。,定義：設(shè)r是集合X上的相容關(guān)系，C是r的一個相容類，如果C不能被其它相容類所真包含，則稱C是一個最大相容類。 也可以說，C是一個相容類，如果C中加入任意一個新元素，就不再是相容類，C就是一個最大相容類。 x1,x2,x3,x4 , x3, x4, x5, x1,x7 , x6都是最大相容類。,2020/8/11,99,從簡化圖找最大相容類：-找最大完全多邊形。 即：含有結(jié)點(diǎn)最多的多邊形中，每個結(jié)點(diǎn)都與其它結(jié)點(diǎn)相聯(lián)結(jié)。,在相容關(guān)系簡化圖中，每個最大完全多邊形的結(jié)點(diǎn)集合構(gòu)成一個最大相容類。 上例中最大相容類x1,x2,x3,x4, x3, x4,x5, x1,x

52、7, x6分別對應(yīng)最大完全四、三、一、零邊形。,2020/8/11,100,給定X上相容關(guān)系r ,如圖所示, r的最大相容類：x1,x2,x5, x2, x3, x5, x3, x4,x5, x1,x4 ,x5,完全覆蓋： 定義：r是X中的相容關(guān)系，由r的所有最大相容類為元素構(gòu)成的集合，稱之為X的完全覆蓋。記作Cr(X)。 Cr(X)=x1,x2,x3,x4, x3, x4, x5,x1,x7,x6 Cr(X)=x1,x2,x5,x2, x3, x5, x3, x4, x5, x1,x4 ,x5,作業(yè) P139 (2),2020/8/11,101,4-10 次序關(guān)系,一. 偏序(半序)關(guān)系(p

53、artial order relation),定義：R是A上自反、反對稱和傳遞的關(guān)系，則稱R是A上的偏序關(guān)系。并稱是偏序集。 例如數(shù)值的、關(guān)系和集合的都是偏序關(guān)系。 用符號“”表示任意偏序關(guān)系，但要注意“”不一定是“小于或等于”的含義。,例1 A=1,2,4,6, 是A中的整除關(guān)系，其關(guān)系圖如右圖，顯然是自反、反對稱和傳遞的，即它是個偏序。,2020/8/11,102,注： （1）用矩陣表示半序關(guān)系，不能明顯看到二元關(guān)系的特征。 （2）用簡化的關(guān)系圖表示較適合。,簡化的關(guān)系圖： (1)自反性：每個頂點(diǎn)都有自回路，省去。 (2)反對稱性：兩個頂點(diǎn)間只可能有一個箭頭從左右，或從下上的方向從小到大安

54、置頂點(diǎn)，可省略箭頭。 (3)傳遞性：由于有(a,b)，(b,c)R 則(a,c) R 故只畫(a,b)，(b,c)對應(yīng)的邊,省略邊(a,c)。,2020/8/11,103,定義：Hasse圖 設(shè)是上的一個半序關(guān)系，如果ab ，則將畫在下面，且不，使ac，cb，則，間用直線連接。并符合簡化的關(guān)系圖的繪制，稱這樣得到關(guān)系圖為Hasse圖。,例： ， ， 1（，） ， 2（，） |， 3(s1,s2)12，s1，s2p(B),2020/8/11,104,2020/8/11,105,定義 全序： 上半序關(guān)系，如果,，都有，或，則稱為上的全序關(guān)系。,二.全序(線序、鏈),全序的含義：中每兩個元素均能比大

55、小，即任何兩個元素都相關(guān)。 半序則是部分有序。 1是全序，2，3都是半序 如：2中，1，2，6,1，2，4，8，1，3，9都排成了序，但2與3，5與7，7與9，在整除的意義上來說無法排出大小來。,2020/8/11,106,練習(xí)： C=1,2,3,6,12,24,36, D=1,2,3,5,6,10,15,30 是C、D上整除關(guān)系：, 的Hasse圖：,2020/8/11,107,三. 偏序集中的重要元素,y是B的極小元 y(yAx(xAxyxy) y是B的極大元 y(yAx(xAxyyx),定義極大元與極小元： 設(shè)（，）是半序集，若，且在中找不到一個元素（），使（），則稱為中的極大元（極小元

56、）。,2020/8/11,108,例（N，|）是半序集，A=2，3，4，5，6，7，8，9則 中極大元：， 極小元：， 注： 極大元，極小元并不要求唯一，且同一元素，可以既是極大元，又是極小元，如，。 極大元，極小元必須是子集中的元素。,2020/8/11,109,定義 最大元與最小元： 設(shè)（，）是半序集，若，(），則稱為的最大元（最小元）。,例：上例 其Hasse圖如下圖所示,結(jié)論：子集中是不存在最大元（最小元）的。,2020/8/11,110,定理是偏序集，B是A的非空子集，如果B有最小元(最大元)，則最小元(最大元)是唯一的。 證明：假設(shè)B有兩個最小元a、b,則 因?yàn)閍是最小元，bB，根

57、據(jù)最小元定義，有ab; 類似地，因?yàn)閎是最小元，aB，根據(jù)最小元定義，有ba。因?yàn)橛蟹磳ΨQ性，所以有a=b。 同理可證最大元的唯一性。 小結(jié)：是偏序集，B是A的非空子集，則 B的極小(大)元總是存在的，就是子集中處在最下(上)層的元素是極小(大)元。 B的最小元(最大元)有時可能不存在，只要有唯一的極小(大)元，則這個極小(大)元就是最小(大)元。否則就沒有最小(大)元。,2020/8/11,111,定義上界與下界： 設(shè)（P,）是半序集，AP，若aP，對 ,（）稱為的上界（下界）。,例：B=a,b,c,R3= (s1,s2) | s1 s2，s1P(B) , (P(B), )是半序集。 設(shè)，a,b,c,a,c,a,b,a,c 其Hasse圖如右圖所示:,2020/8/11,112,注： （1）上例中，無最大元，但存在的上界，。 （2）為的最小元，也是的下界 （3）最大（小）元是的一個上（下）界 （4）上（下）界可以不唯一，也可以不存在,定義上確界與下確界： 設(shè)（，）是半序集，若是的一個上界（下界），而的上界（下界），都有（），則稱是的上確界（下確界）。,2020/8/11,113,注： 上確界：最小上界 下確界：最大下界 如果存在上（下）確界，則上（下）確界一定是唯一的,舉例，給定的Hasse圖如圖所