1、1,4.3 關(guān)系的性質(zhì),關(guān)系的性質(zhì)及特點(diǎn) 關(guān)系性質(zhì)的充要條件 關(guān)系性質(zhì)的證明 運(yùn)算和性質(zhì)的關(guān)系,2,1. 自反的二元關(guān)系,(1).定義：R是上的二元關(guān)系，若x(xAR), 則稱R在A上是自反的二元關(guān)系。,例如 a,b,c, R= (a,a),(b,b),(c,c),(a,b)， 則是自反的。,又如1,2,3, R是上的整除關(guān)系， 顯然，是自反的，因?yàn)椋?, 1）,（2, 2）,（3, 3） 都屬于R。,即如果對(duì)于中的每一個(gè)元素a,都有(a,a) R，則稱為自反的二元關(guān)系。,一、關(guān)系的性質(zhì)及特點(diǎn),3,注意，在關(guān)系的自反性定義中，要求對(duì)于A中 的每一個(gè)元素a都有(a,a) R。所以當(dāng)A=a,b,c

2、，而 R=(a,a),(b,b)時(shí)，R并不是自反的，因?yàn)?c,c) R。,又如A=1,2,3，R是A上的二元關(guān)系，當(dāng)a,bA， 且a和b都是素?cái)?shù)時(shí)，(a,b) R。,可見(jiàn)(2,2),(3,3),(2,3),(3,2)，也不是自反關(guān) 系，因?yàn)?1,1) R。,4,(2). 關(guān)系矩陣的特點(diǎn)：,關(guān)系矩陣中主對(duì)角線上的元素全為1。,(3). 關(guān)系圖的特點(diǎn)：,關(guān)系圖中每個(gè)頂點(diǎn)都有環(huán)。,實(shí)例： A上的全域關(guān)系EA, 恒等關(guān)系IA，小于等于關(guān)系LA, 整除關(guān)系DA都是自反關(guān)系：,5,2反自反的二元關(guān)系,(1). 定義： R是上的二元關(guān)系，若x(xAR), 則稱R在A上是反自反的二元關(guān)系.,例如a,b,c,

3、R= (a,b),(b,c),(b,a)，則是反自反的。,又如1,2,3, R是上的小于關(guān)系，即當(dāng)ab時(shí)， (a,b) R。顯然，是反自反的。,注意，非自反的二元關(guān)系不一定是反自反的二元關(guān)系， 因?yàn)榇嬖谥@樣的二元關(guān)系，它既不是自反的又不是反自 反的，如=a,b,c,R=(a,a),(a,b)，那么不是自反的(因 為(b,b), (c,c)都不屬于)，也不是反自反的(因?yàn)?a,a) R)。,即對(duì)于中的每一個(gè)元素a,都有(a,a) R，則稱為 反自反的二元關(guān)系。,6,實(shí)例： 實(shí)數(shù)集上的小于關(guān)系，空關(guān)系，冪集上的 真包含關(guān)系都是反自反關(guān)系。,(2). 關(guān)系矩陣的特點(diǎn)：,關(guān)系矩陣中主對(duì)角線上的元素全

4、為0。,(3). 關(guān)系圖的特點(diǎn)：,關(guān)系圖中每個(gè)頂點(diǎn)都沒(méi)有環(huán)。,7,例1 A=1,2,3, R1, R2, R3是A上的關(guān)系, 其中R1,R2,R3,R1既不是自反也不是反自反的,R2為自反關(guān)系,R3為反自反關(guān)系。,8,3. 對(duì)稱的二元關(guān)系,(1). 定義: R是上的二元關(guān)系， 若x，y(x,yARR), 則稱R為A上對(duì)稱的二元關(guān)系.,例如=a,b,c,d, R=(a,a),(a,b),(b,a),(b,d),(d,b) 則是對(duì)稱的二元關(guān)系。,又如=1,2,3,4,5,對(duì)于中元素a和b,如果a,b是模 3同余關(guān)系，則(a,b) , 易見(jiàn)是對(duì)稱關(guān)系。,即如果(a,b) R, 就一定有(b,a) R

5、, 則稱為對(duì)稱的二元關(guān)系。,9,實(shí)例： A上的全域關(guān)系EA, 恒等關(guān)系IA和空關(guān)系 都是對(duì)稱關(guān)系。,(2). 關(guān)系矩陣的特點(diǎn)：,關(guān)系矩陣為對(duì)稱矩陣。,(3). 關(guān)系圖的特點(diǎn)：,關(guān)系圖中如果兩個(gè)頂點(diǎn)之間有邊一定是一對(duì)方向相反的邊。,10,4反對(duì)稱的二元關(guān)系,即R是上的二元關(guān)系，每當(dāng)有(a,b) 和有(b,a) 時(shí)，必有a=b,則稱是反對(duì)稱的二元關(guān)系。,反對(duì)稱的定義也可寫(xiě)為：是上的二元關(guān)系， 當(dāng)ab時(shí)，如果(a,b) ,則必有(b,a) R, 稱為反對(duì)稱的二元關(guān)系。,例如=1,2,3,R是上的小于關(guān)系，即ab，（a,b）。 易見(jiàn)=(1,2),(1,3),(2,3),所以是反對(duì)稱的。,又如是一些整數(shù)

6、組成的集合，如果a整除b，則(a,b) , R也是反對(duì)稱的。,(1). 定義：若 x，y(x,yARRx=y), 則稱R為A上的反對(duì)稱關(guān)系.,11,注意，“對(duì)稱的”和“反對(duì)稱的”這兩個(gè)概念并非相互對(duì)立， 相互排斥的。存在著既不是對(duì)稱的又不是反對(duì)稱的二元 關(guān)系，也存在著既是對(duì)稱的又是反對(duì)稱的二元關(guān)系。,又如A=a,b,c, R=(a,a), 可知是對(duì)稱的，又是反對(duì)稱的。,因?yàn)殡m有(a,b) R, (b,a) R，但(c,d) R時(shí)(d,c) R, 因此R不是對(duì)稱的，,例如A=a,b,c,d R=(a,b),(b,a),(c,d) 這里R既不是對(duì)稱的，也不是反對(duì)稱的。,因?yàn)橛?a,b) R和(b,

7、a) R，因此R不是反對(duì)稱的。,12,實(shí)例： 恒等關(guān)系IA，空關(guān)系都是A上的反對(duì)稱關(guān)系。,(2). 關(guān)系矩陣的特點(diǎn)：,關(guān)系矩陣中以主對(duì)角線對(duì)稱的元素不能同時(shí)為1。,(3). 關(guān)系圖的特點(diǎn)：,關(guān)系圖中如果兩個(gè)頂點(diǎn)之間有邊一定是一條有向邊。,13,例2 設(shè)A1,2,3, R1, R2, R3和R4都是A上的關(guān)系, 其中 R1,， R2, R3,， R4,R1 對(duì)稱、反對(duì)稱. R2 對(duì)稱，不反對(duì)稱. R3 反對(duì)稱，不對(duì)稱. R4 不對(duì)稱、也不反對(duì)稱.,14,5. 可傳遞的二元關(guān)系,(1). 定義： R是A上的二元關(guān)系，xyz(x,y,zARRR),則稱R是A上的傳遞關(guān)系.,例如整除關(guān)系是可傳遞的，因

8、為每當(dāng)（a，b） R時(shí)， 即 a 能整除 b，b能整除c時(shí)，顯然 a 能整除 c， 所以必有（a，c） R 。,又如A=a，b，c，d，e，其中a、b、c、d、e分別是表示 5個(gè)人，且a、b、c同住一個(gè)房間；d和e同住另一個(gè)房間。 如果同住一房間的人認(rèn)為是相關(guān)的，顯然這種同房間關(guān)系 是可傳遞的。,每當(dāng)有(a,b) R和(b,c) R 時(shí)，必有(a,c) R ，則稱為可傳遞的二元關(guān)系。,15,實(shí)例： A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系 小于等于關(guān)系, 小于關(guān)系，整除關(guān)系，包含關(guān)系， 真包含關(guān)系都是傳遞的二元關(guān)系。,(2). 關(guān)系矩陣的特點(diǎn)：,(3). 關(guān)系圖的特點(diǎn)：,關(guān)系圖中如果兩個(gè)頂點(diǎn)x

9、i到xj之間有邊, xj到 xk之間有邊,則從xi到xk之間有邊。,16,關(guān)系性質(zhì)判別匯總,例3 設(shè)A1,2,3, R1, R2是A上的關(guān)系, 其中 R1, R2,R1 是A上的傳遞關(guān)系 R2不是A上的傳遞關(guān)系,18,例4 判斷下圖中關(guān)系的性質(zhì), 并說(shuō)明理由.,(2)反自反，不是自反的；反對(duì)稱，不是對(duì)稱的；,(1)不自反也不反自反；對(duì)稱, 不反對(duì)稱；不傳遞.,(3)自反，不反自反；反對(duì)稱，不是對(duì)稱；不傳遞.,19,二、關(guān)系性質(zhì)的充要條件,設(shè)R為A上的關(guān)系, 則 (1) R在A上自反當(dāng)且僅當(dāng) IA R (2) R在A上反自反當(dāng)且僅當(dāng) RIA= (3) R在A上對(duì)稱當(dāng)且僅當(dāng) R=R1 (4) R在

10、A上反對(duì)稱當(dāng)且僅當(dāng) RR1IA (5) R在A上傳遞當(dāng)且僅當(dāng) RRR,20,1.自反性證明,證明模式 證明R在A上自反 任取x, xA . R 前提 推理過(guò)程 結(jié)論,例5 證明若 IA R ，則 R在A上自反.,三、關(guān)系類型的證明,證 任取x, xA IA R 因此 R 在 A 上是自反的.,21,2. 對(duì)稱性證明,證明模式 證明R在A上對(duì)稱 任取 R . R 前提 推理過(guò)程 結(jié)論,例6 證明若 R=R1 , 則R在A上對(duì)稱.,證 任取 R R 1 R 因此 R 在 A 上是對(duì)稱的.,22,3. 反對(duì)稱性證明,證明模式 證明R在A上反對(duì)稱 任取 RR . x=y 前提 推理過(guò)程 結(jié)論,例7 證

11、明若 RR1IA , 則R在A上反對(duì)稱.,證 任取 R R R R 1 RR 1 IA x=y 因此 R 在 A 上是反對(duì)稱的.,23,4. 傳遞性證明,證明模式 證明R在A上傳遞 任取， RR . R 前提 推理過(guò)程 結(jié)論,例8 證明若 RRR , 則R在A上傳遞.,證 任取， R R RR R 因此 R 在 A 上是傳遞的.,思考1. 設(shè)A=a,b,c, R是A上的二元關(guān)系 且 R=(a,a),(b,b),(a,c),(c,a),問(wèn)R是自反的嗎？ 是反自反的嗎？是對(duì)稱的嗎？是反對(duì)稱的嗎？ 是可傳遞的嗎？,解：由于cR,但(c,c)R,所以R不是自反關(guān)系；,又由于 (c,a)R, (a,c)

12、R,但(c,c) R, 所以R不是傳遞關(guān)系。,顯然R是對(duì)稱關(guān)系， R不是反對(duì)稱關(guān)系；,由于 (a,a) R, (b,b) R, 所以R也不是反自反關(guān)系；,思考2. 設(shè)A=a,b，寫(xiě)出 （1）A上所有的自反關(guān)系；（2）A上所有的反自反關(guān)系； （3）A上所有的對(duì)稱關(guān)系；（4）A上所有的反對(duì)稱關(guān)系。,解 （1） 由于AA= (a,a),(b,b),(a,b),(b,a)，,而A上的自反關(guān)系必須含有(a,a),(b,b)。,所以A上的自反關(guān)系共有4種。,它們是 (a,a),(b,b)， (a,a),(b,b),(a,b)， (a,a),(b,b),(b,a)， (a,a),(b,b),(a,b),(b

13、,a)。,(2) 由于A上的反自反關(guān)系必須不含有(a,a),(b,b)。,所以A上的反自反關(guān)系也有4種。,它們是(空關(guān)系)， (a,b)，(b,a)，(a,b),(b,a)。,(3) 由于A上的對(duì)稱關(guān)系R, 當(dāng)(a,b) R時(shí),必有(b,a) R, 所以只需考慮在(a,a),(b,b),(a,b)中選取0個(gè)，1個(gè)，2個(gè)， 3個(gè)有序?qū)?gòu)成的集合。,它們是空關(guān)系, (a,a), (b,b), (a,b) ,(b,a), (a,a),(b,b), (a,a),(a,b),(b,a)， (b,b),(a,b),(b,a), (a,a),(b,b),(a,b),(b,a)。,所以A上的對(duì)稱關(guān)系有8種。,

14、27,所以在AA的子集中刪去同時(shí)含有(a ,b)和(b,a) 的子集 后，其它子集都是反對(duì)稱關(guān)系，共有12種。,即(空關(guān)系)， (a,a), (a,b), (b,a), (b,b), (a,a) ,(a,b), (a,a),(b,a), (a,a),(b,b), (a,b),(b,b), (b,a),(b,b), (a,a),(a,b),(b,b)， (a,a),(b,a),(b,b)。,（4）由于A上的反對(duì)稱關(guān)系，當(dāng)(a,b) R必有(b,a)R。,28,思考3. 設(shè)A=1，2，3，問(wèn)在A上有多少種不同的自反關(guān)系？,解：當(dāng)R是A上的自反關(guān)系時(shí)，R必須含有表格中對(duì)角線上的 3個(gè)小方格所表示的有

15、序?qū)Γ瑢?duì)于表格中余下的6個(gè)小 方格，可以依次選取1個(gè)，2個(gè)，6個(gè)小方格， 也可以不取，它們所表示的二元關(guān)系都是A上的自反關(guān)系，,因此，A上共有64個(gè)自反關(guān)系。,5.傳遞性的判定方法,判定定理1：設(shè)集合A=a1,a2, ,an，R是A上的二元關(guān)系，R 的關(guān)系矩陣為MR，令MR2 = MR MR，則R是A上的傳遞關(guān)系的充要條件是對(duì)MR2中1所在位置,MR中相應(yīng)位置都是1。,例9：設(shè)A=a，b，c，d，e， R=, 試判斷R的傳遞性。,判定定理2：設(shè)集合A=a1,a2 , ,an，R是A上的二元關(guān)系，R 的關(guān)系矩陣為MR， R是A上的傳遞關(guān)系的充要條件是若MR中的零元素aij=0所對(duì)應(yīng)的MR2的元素bij=0時(shí)，則R是A上的傳遞關(guān)系。,思考：設(shè)A=a1，a2， a3 ， a4 ， a5， R=, , , , , , 試