chapter4_34(1)

1、1 集合論集合論2 第四章第四章 二元關(guān)系與函數(shù)二元關(guān)系與函數(shù)34.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)l自反性自反性l反自反性反自反性l對(duì)稱性對(duì)稱性l反對(duì)稱性反對(duì)稱性l傳遞性傳遞性4自反性與反自反性自反性與反自反性定義定義4.10 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x(xA R), 則稱則稱R在在A上是上是自反自反的的.(2) 若若 x(xA R), 則稱則稱R在在A上是上是反自反反自反的的.例例21： 自反關(guān)系：自反關(guān)系：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA 小于等于關(guān)系小于等于關(guān)系LA, 整除關(guān)系整除關(guān)系DA 反自反關(guān)系：實(shí)數(shù)集上的小于關(guān)系反自反關(guān)系：實(shí)數(shù)集上的小于關(guān)系

2、 冪集上的真包含關(guān)系冪集上的真包含關(guān)系5實(shí)例實(shí)例例例22 A=1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3，求各關(guān)系的自反和反自反性質(zhì)，求各關(guān)系的自反和反自反性質(zhì)解：解： R2自反自反, R3反自反反自反, R1既不是自反也不是反自反的既不是自反也不是反自反的6對(duì)稱性與反對(duì)稱性對(duì)稱性與反對(duì)稱性定義定義4.11 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x y(x,yARR), 則稱則稱R為為A上上對(duì)稱對(duì)稱的關(guān)系的關(guān)系. (2) 若若 x y(x,yARxy R), 則稱則稱R為為A上的上的反對(duì)稱反對(duì)稱關(guān)系關(guān)系.例例23：對(duì)稱關(guān)系：對(duì)稱關(guān)系：A上

3、的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA和空關(guān)系和空關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系反對(duì)稱關(guān)系：恒等關(guān)系IA，空關(guān)系是空關(guān)系是A上的反對(duì)稱關(guān)上的反對(duì)稱關(guān) 系系.7實(shí)例實(shí)例例例24 設(shè)設(shè)A1,2,3, R1, R2, R3和和R4都是都是A上的關(guān)系上的關(guān)系, 其中其中 R1,， R2, R3,， R4, R1 對(duì)稱、反對(duì)稱對(duì)稱、反對(duì)稱. R2 對(duì)稱，不反對(duì)稱對(duì)稱，不反對(duì)稱. R3 反對(duì)稱，不對(duì)稱反對(duì)稱，不對(duì)稱. R4 不對(duì)稱、也不反對(duì)稱不對(duì)稱、也不反對(duì)稱.8傳遞性傳遞性 定義定義4.12 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 若若 x y z(x,y,zARRR),則稱則稱R是是A上的上的傳遞傳遞關(guān)

4、系關(guān)系.例例25： A上的全域關(guān)系上的全域關(guān)系EA,恒等關(guān)系恒等關(guān)系IA和空關(guān)系和空關(guān)系 小于等于關(guān)系小于等于關(guān)系, 小于關(guān)系，整除關(guān)系，包含關(guān)小于關(guān)系，整除關(guān)系，包含關(guān) 系，真包含關(guān)系系，真包含關(guān)系9實(shí)例實(shí)例例例26 設(shè)設(shè)A1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中 R1, R2, R3R1 和和 R3 是是A上的傳遞關(guān)系上的傳遞關(guān)系 R2不是不是A上的傳遞關(guān)系上的傳遞關(guān)系10關(guān)系性質(zhì)的充要條件關(guān)系性質(zhì)的充要條件設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則則 (1) R在在A上上自反自反當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) IA R (2) R在在A上上反自反反自反當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) RIA= (

5、3) R在在A上上對(duì)稱對(duì)稱當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) R=R 1 (4) R在在A上上反對(duì)稱反對(duì)稱當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) RR 1 IA (5) R在在A上上傳遞傳遞當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) R R R 11關(guān)系性質(zhì)判別關(guān)系性質(zhì)判別自反自反反自反反自反對(duì)稱對(duì)稱反對(duì)稱反對(duì)稱傳遞傳遞表達(dá)式表達(dá)式 IA RRIA=R=R 1 RR 1 IA R R R關(guān)系關(guān)系矩陣矩陣主對(duì)主對(duì)角線角線元素元素全是全是1主對(duì)角主對(duì)角線元素線元素全是全是0矩陣是對(duì)稱矩陣是對(duì)稱矩陣矩陣若若rij1, 且且ij, 則則rji0對(duì)對(duì)M2中中1所在位置所在位置,M中相應(yīng)中相應(yīng)位置都是位置都是1關(guān)系圖關(guān)系圖 每個(gè)每個(gè)頂點(diǎn)頂點(diǎn)都有都有環(huán)環(huán)每個(gè)頂每個(gè)頂點(diǎn)都沒(méi)

6、點(diǎn)都沒(méi)有環(huán)有環(huán)如果兩個(gè)頂如果兩個(gè)頂點(diǎn)之間有邊點(diǎn)之間有邊, 是一對(duì)方向是一對(duì)方向相反的邊相反的邊(無(wú)單邊無(wú)單邊)如果兩點(diǎn)如果兩點(diǎn)之間有邊之間有邊, 是一條有是一條有向邊向邊(無(wú)雙無(wú)雙向邊向邊)如果頂點(diǎn)如果頂點(diǎn) xi 連通到連通到xk , 則從則從 xi到到 xk 有邊有邊 12實(shí)例實(shí)例例例27 判斷下圖中關(guān)系的性質(zhì)判斷下圖中關(guān)系的性質(zhì), 并說(shuō)明理由并說(shuō)明理由.(2)反自反，不是自反的；反對(duì)稱，不是對(duì)稱的；反自反，不是自反的；反對(duì)稱，不是對(duì)稱的； 是傳遞的是傳遞的.(1)不自反也不反自反；對(duì)稱不自反也不反自反；對(duì)稱, 不反對(duì)稱；不傳遞不反對(duì)稱；不傳遞.(3)自反，不反自反；反對(duì)稱，不是對(duì)稱；不傳遞

7、自反，不反自反；反對(duì)稱，不是對(duì)稱；不傳遞. 13自反性證明方法自反性證明方法證明證明R在在A上自反：上自反： 任取任取x, x A . R 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例28 證明若證明若 IA R ，則則 R在在A上自反上自反. 證明：證明：任取任取x x, , x x A A I IA A R R 因此因此 R R 在在 A A 上是自反的上是自反的. .14對(duì)稱性證明方法對(duì)稱性證明方法證明證明R在在A上對(duì)稱上對(duì)稱 ： 任取任取 R . R 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例29 證明若證明若 R=R 1 , 則則R在在A上對(duì)稱上對(duì)稱. 證明：證明：任取任取 R R 1 R

8、 因此因此 R 在在 A 上是對(duì)稱的上是對(duì)稱的.15反對(duì)稱性證明方法反對(duì)稱性證明方法證明證明R在在A上反對(duì)稱上反對(duì)稱 任取任取 R R . x=y 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例30 證明若證明若 RR 1 IA , 則則R在在A上反對(duì)稱上反對(duì)稱. 證明：證明：任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反對(duì)稱的上是反對(duì)稱的.16傳遞性證明方法傳遞性證明方法證明證明R在在A上傳遞上傳遞 任取任取， R R . R 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例31 證明若證明若 R R R , 則則R在在A上傳遞上傳遞. 證明證明 任取任取， R R

9、R R R 因此因此 R 在在 A 上是傳遞的上是傳遞的.17運(yùn)算與性質(zhì)的關(guān)系運(yùn)算與性質(zhì)的關(guān)系自反性自反性 反自反性反自反性對(duì)稱性對(duì)稱性反對(duì)稱性反對(duì)稱性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 184.4 關(guān)系的閉包關(guān)系的閉包l閉包定義閉包定義l閉包的構(gòu)造方法閉包的構(gòu)造方法l 集合表示集合表示l 矩陣表示矩陣表示l 圖表示圖表示l閉包的性質(zhì)閉包的性質(zhì) 19閉包定義閉包定義 定義定義4.13 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, R的的自反（對(duì)稱自反（對(duì)稱或或傳遞）閉包傳遞）閉包是是A上的關(guān)系上的關(guān)系R , 使得使得R 滿足以下條件：滿足以下條件：（1）R 是自

10、反的（對(duì)稱的或傳遞的）是自反的（對(duì)稱的或傳遞的）（2）R R （3）對(duì)）對(duì)A上任何包含上任何包含R的自反（對(duì)稱或傳遞）關(guān)系的自反（對(duì)稱或傳遞）關(guān)系 R 有有 RR . 一般將一般將 R 的自反閉包記作的自反閉包記作 r(R), 對(duì)稱閉包記作對(duì)稱閉包記作 s(R), 傳遞閉包記作傳遞閉包記作 t(R). 20閉包的構(gòu)造方法閉包的構(gòu)造方法定理定理5 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則有則有 (1) r(R) = RR0 (2) s(R) = RR 1 (3) t(R) = RR2R3說(shuō)明：說(shuō)明： 對(duì)于有窮集合對(duì)于有窮集合A (|A|=n) 上的關(guān)系上的關(guān)系, (3)中的并最多中的并最多 不超過(guò)不超

11、過(guò) Rn. 若若 R是自反的，則是自反的，則 r(R)=R; 若若R是對(duì)稱的，則是對(duì)稱的，則 s(R)=R; 若若R是傳遞的，則是傳遞的，則 t(R)=R. 21設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為的關(guān)系矩陣分別為M, Mr, Ms 和和 Mt , 則則 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和是和 M 同階的單位矩陣同階的單位矩陣, M是是 M 的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣. 注意在上述等式中矩陣的元素相加時(shí)使用邏輯加注意在上述等式中矩陣的元素相加時(shí)使用邏輯加.閉包的構(gòu)造方法（續(xù)）閉包的構(gòu)造方法（續(xù)）22閉包的構(gòu)造方法（

12、續(xù)）閉包的構(gòu)造方法（續(xù)）設(shè)關(guān)系設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為的關(guān)系圖分別記為G, Gr, Gs, Gt , 則則Gr, Gs, Gt 的頂點(diǎn)集與的頂點(diǎn)集與G 的頂點(diǎn)集相等的頂點(diǎn)集相等. 除了除了G 的邊以外的邊以外, 以下述方法添加新邊：以下述方法添加新邊： 考察考察G的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn), 如果沒(méi)有環(huán)就加上一個(gè)環(huán)，最如果沒(méi)有環(huán)就加上一個(gè)環(huán)，最終得到終得到Gr . 考察考察G的每條邊的每條邊, 如果有一條如果有一條 xi 到到 xj 的單的單向邊向邊, ij, 則在則在G中加一條中加一條 xj 到到 xi 的反方向邊，最終的反方向邊，最終得到得到Gs. 考察考察G的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn) xi, 找從