離散數(shù)學(xué)課件：第4章 二元關(guān)系與函數(shù)2

1、14.3 關(guān)系的性質(zhì)關(guān)系的性質(zhì)n自反性自反性n反自反性反自反性n對(duì)稱(chēng)性對(duì)稱(chēng)性n反對(duì)稱(chēng)性反對(duì)稱(chēng)性n傳遞性傳遞性2自反性與反自反性自反性與反自反性定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1) 若若 x(xA R), 則稱(chēng)則稱(chēng)R在在A上是上是自反自反的的.(2) 若若 x(xA R), 則稱(chēng)則稱(chēng)R在在A上是上是反自反反自反的的.實(shí)例：實(shí)例：自反關(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)系 冪集上的真包含關(guān)系冪集上的真包含關(guān)系非自反非自反 與與 反自反反自反，

2、 非反自反非反自反與與自反自反 的區(qū)別的區(qū)別3實(shí)例實(shí)例例例1 A=1,2,3, R1, R2, R3是是A上的關(guān)系上的關(guān)系, 其中其中R1,R2,R3R2自反自反, R3反自反反自反, R1既既不是自反不是自反也也不是反自反不是反自反的的4對(duì)稱(chēng)性與反對(duì)稱(chēng)性對(duì)稱(chēng)性與反對(duì)稱(chēng)性定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, (1)稱(chēng)稱(chēng)R為為A上上對(duì)稱(chēng)對(duì)稱(chēng)的關(guān)系，是指的關(guān)系，是指R滿(mǎn)足滿(mǎn)足 ： x y( x,yA xRy yRx ), (2)稱(chēng)稱(chēng)R為為A上的上的反反對(duì)稱(chēng)對(duì)稱(chēng)關(guān)系，是指關(guān)系，是指R滿(mǎn)足：滿(mǎn)足： x y( x,yA xRy xy yR x ) 或等價(jià)地或等價(jià)地： x y( x,yA xRy yR

3、x x=y) .實(shí)例：實(shí)例：對(duì)稱(chēng)關(guān)系：對(duì)稱(chēng)關(guān)系：A上的全域關(guān)系上的全域關(guān)系EA, 恒等關(guān)系恒等關(guān)系IA和和空關(guān)系空關(guān)系反對(duì)稱(chēng)關(guān)系：反對(duì)稱(chēng)關(guān)系：恒等關(guān)系恒等關(guān)系IA，空關(guān)系空關(guān)系5實(shí)例實(shí)例例例2 設(shè)設(shè)A1,2,3, R1, R2, R3和和R4都是都是A上的關(guān)系上的關(guān)系, R1,， R2, R3,， R4, R1 對(duì)稱(chēng)、反對(duì)稱(chēng)對(duì)稱(chēng)、反對(duì)稱(chēng). R2 對(duì)稱(chēng)，不反對(duì)稱(chēng)對(duì)稱(chēng)，不反對(duì)稱(chēng). R3 反對(duì)稱(chēng)，不對(duì)稱(chēng)反對(duì)稱(chēng)，不對(duì)稱(chēng). R4 不對(duì)稱(chēng)、也不反對(duì)稱(chēng)不對(duì)稱(chēng)、也不反對(duì)稱(chēng).6傳遞性傳遞性 定義定義 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系,稱(chēng)稱(chēng)R是是A上的上的傳遞傳遞關(guān)系，是關(guān)系，是指指R是滿(mǎn)足：是滿(mǎn)足： x y z(

4、x,y,zA xRy yRz xRz),滿(mǎn)足傳遞性的關(guān)系實(shí)例滿(mǎn)足傳遞性的關(guān)系實(shí)例： 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)系7實(shí)例實(shí)例例例3 設(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)系8關(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 (

5、2) R在在A上上反自反反自反當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) RIA= (3) R在在A上上對(duì)稱(chēng)對(duì)稱(chēng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) R=R 1 (4) R在在A上上反對(duì)稱(chēng)反對(duì)稱(chēng)當(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 提示：提示： 利用利用 關(guān)系矩陣關(guān)系矩陣和和關(guān)系圖關(guān)系圖來(lái)幫助理解來(lái)幫助理解9關(guān)系性質(zhì)判別方法關(guān)系性質(zhì)判別方法自反自反反自反反自反對(duì)稱(chēng)對(duì)稱(chēng)反對(duì)稱(chēng)反對(duì)稱(chēng)傳遞傳遞集合表集合表達(dá)式達(dá)式IA RRIA=R=R 1 RR 1 IA R R R關(guān)系關(guān)系矩陣矩陣主對(duì)主對(duì)角線角線元素元素全是全是1主對(duì)角主對(duì)角線元素線元素全是全是0矩陣是對(duì)稱(chēng)矩陣是對(duì)稱(chēng)矩陣矩陣若若rij1,

6、且且ij, 則則rji0凡凡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)點(diǎn)都沒(méi)都沒(méi)有有環(huán)環(huán)如果兩個(gè)頂如果兩個(gè)頂點(diǎn)之間有邊點(diǎn)之間有邊, 一定是雙向一定是雙向邊邊(無(wú)單邊無(wú)單邊)如果兩點(diǎn)如果兩點(diǎn)之間有邊之間有邊, 則則只有只有單單向邊向邊(無(wú)雙無(wú)雙向邊向邊)如果頂點(diǎn)如果頂點(diǎn) xi 到到xk可可達(dá)達(dá), 則從則從 xi到到 xk 有邊有邊 10實(shí)例實(shí)例例例8 判斷下圖中關(guān)系的性質(zhì)判斷下圖中關(guān)系的性質(zhì), 并說(shuō)明理由并說(shuō)明理由.(b) 反自反；非對(duì)稱(chēng)的，反對(duì)稱(chēng)；反自反；非對(duì)稱(chēng)的，反對(duì)稱(chēng)； 是傳遞的是傳遞的.(a) 非自反也非反自反；對(duì)稱(chēng)

7、非自反也非反自反；對(duì)稱(chēng), 不反對(duì)稱(chēng)；不傳遞不反對(duì)稱(chēng)；不傳遞.(c) 自反；非對(duì)稱(chēng)，反對(duì)稱(chēng)；不傳遞自反；非對(duì)稱(chēng)，反對(duì)稱(chēng)；不傳遞. 11自反性證明自反性證明證明模式證明模式 證明證明R在在A上自反上自反 任取任取x, x A . R 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例4 證明若證明若 IA R ，則則 R在在A上自反上自反. 證證 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的.12對(duì)稱(chēng)性證明對(duì)稱(chēng)性證明證明模式證明模式 證明證明R在在A上對(duì)稱(chēng)上對(duì)稱(chēng) 任取任取 R . R 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例5 證明若證明若 R=R 1 , 則則R在在A上對(duì)稱(chēng)

8、上對(duì)稱(chēng). 證證 任取任取 R R 1 R 因此因此 R 在在 A 上是對(duì)稱(chēng)的上是對(duì)稱(chēng)的.13反對(duì)稱(chēng)性證明反對(duì)稱(chēng)性證明證明模式證明模式 證明證明R在在A上反對(duì)稱(chēng)上反對(duì)稱(chēng) 任取任取 R R . x=y 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例6 證明若證明若 RR 1 IA , 則則R在在A上反對(duì)稱(chēng)上反對(duì)稱(chēng). 證證 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反對(duì)稱(chēng)的上是反對(duì)稱(chēng)的.14傳遞性證明傳遞性證明證明模式證明模式 證明證明R在在A上傳遞上傳遞 任取任取， R R . R 前提前提 推理過(guò)程推理過(guò)程 結(jié)論結(jié)論例例7 證明若證明若 R R R , 則則R在

9、在A上傳遞上傳遞. 證證 任取任取， R R R R R 因此因此 R 在在 A 上是傳遞的上是傳遞的.15關(guān)系的運(yùn)算與性質(zhì)的保持關(guān)系的運(yùn)算與性質(zhì)的保持自反性自反性反自反性反自反性對(duì)稱(chēng)性對(duì)稱(chēng)性反對(duì)稱(chēng)性反對(duì)稱(chēng)性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 關(guān)系運(yùn)算與性質(zhì)保持 舉例16對(duì)對(duì) R1R2 ： 不能保持不能保持反對(duì)稱(chēng)性反對(duì)稱(chēng)性 ：R1=, R2 =傳遞性：傳遞性： R1=, R2 = 對(duì)對(duì) R1 R2 ：不能保持不能保持 自反性：自反性：R1=, , R2 =, ; R1-R2 =, 傳遞性：傳遞性：R1=, , R2 = ; R1-R2 =, , 對(duì)對(duì)R1 R2 ：

10、不能保持不能保持 反自反：反自反：R1=R2 =, ;對(duì)稱(chēng)性：對(duì)稱(chēng)性：R1=, ，R2 = ;反對(duì)稱(chēng)：反對(duì)稱(chēng)：R1=, ，R2 =， ;傳遞性：傳遞性：R1=, ，R2 =， ;174.4 關(guān)系的閉包關(guān)系的閉包n閉包定義閉包定義n閉包的構(gòu)造方法閉包的構(gòu)造方法 集合表示集合表示 矩陣表示矩陣表示 圖表示圖表示n閉包的性質(zhì)閉包的性質(zhì) 18閉包定義閉包定義 定義定義 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, R的的自反自反（對(duì)稱(chēng)對(duì)稱(chēng)或或傳遞傳遞）閉包閉包是是A上上滿(mǎn)足滿(mǎn)足以以下條件下條件的關(guān)系的關(guān)系R ：（1）R 是自反的（是自反的（對(duì)稱(chēng)對(duì)稱(chēng)的或的或傳遞傳遞的）的）（2）R R （3）對(duì)）對(duì)A

11、上上任何包含任何包含R的自反的自反（對(duì)稱(chēng)對(duì)稱(chēng)或或傳遞傳遞）關(guān)關(guān)系系 R 有有 RR . 一般將一般將 R 的自反閉包記作的自反閉包記作 r(R), 對(duì)稱(chēng)閉包記作對(duì)稱(chēng)閉包記作 s(R), 傳遞閉包記作傳遞閉包記作 t(R). 顯然顯然：若若 R是自反的，則是自反的，則 r(R)=R; 若若R是對(duì)稱(chēng)的，則是對(duì)稱(chēng)的，則 s(R)=R; 若若R是傳遞的，則是傳遞的，則 t(R)=R. 19閉包的構(gòu)造方法閉包的構(gòu)造方法定理定理4.4 設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則有則有 (1) r(R) = RR0 = RIA(2) s(R) = RR 1(3) t(R) = RR2R3對(duì)于對(duì)于有窮集合有窮集合A

12、(|A|=n) 上的關(guān)系上的關(guān)系, (3)中參與中參與并的集合并的集合最多到最多到Rn. 記關(guān)系記關(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í)使用邏使用邏輯加輯加.】20閉包的構(gòu)造方法（閉包的構(gòu)造方法（關(guān)系矩陣法關(guān)系矩陣法）21閉包的構(gòu)造方法（閉包的構(gòu)造方法（關(guān)系圖法關(guān)系圖法）記關(guān)系記關(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 的邊以外的邊以外, 以下以下述方法添加新邊可得到各閉包的關(guān)系圖：述方法添加新邊可得到各閉包的關(guān)系圖： 為為G沒(méi)有環(huán)沒(méi)有環(huán)的頂點(diǎn)加一個(gè)環(huán)，最終得到的頂點(diǎn)加一個(gè)環(huán)，最終得到Gr . 考察考察G的邊的邊, 若僅存在若僅存在 從從xi 到到 xj （ij）的單向邊的單向邊, 則加入一則加入一條從條從 xj 到到 xi 的反向邊，最終得到的反向邊，最終得到Gs. 考察考察G的的