離散數學：第4章 二元關系與函數2

1、14.3 關系的性質關系的性質n自反性自反性n反自反性反自反性n對稱性對稱性n反對稱性反對稱性n傳遞性傳遞性2自反性與反自反性自反性與反自反性定義定義 設設R為為A上的關系上的關系, (1) 若若 x(xA R), 則稱則稱R在在A上是上是自反自反的的.(2) 若若 x(xA R), 則稱則稱R在在A上是上是反自反反自反的的.實例：實例：自反關系：自反關系：A上的全域關系上的全域關系EA, 恒等關系恒等關系IA 小于等于關系小于等于關系LA, 整除關系整除關系DA反自反關系：實數集上的小于關系反自反關系：實數集上的小于關系 冪集上的真包含關系冪集上的真包含關系3實例實例例例1 A=1,2,3,

2、 R1, R2, R3是是A上的關系上的關系, 其中其中 R1, R2, R3R1既不是自反也不是反自反的既不是自反也不是反自反的R2自反自反, R3反自反反自反, 4對稱性與反對稱性對稱性與反對稱性定義定義 設設R為為A上的關系上的關系, (1) 若若 x y(x,yARR), 則稱則稱R為為A上上對稱對稱的關系的關系. (2) 若若 x y(x,yARx y R), 則稱則稱R為為A上的上的反對稱反對稱關系關系實例：實例： 對稱關系：對稱關系：A上的全域關系上的全域關系EA, 恒等關系恒等關系IA和空和空關系關系 反對稱關系：恒等關系反對稱關系：恒等關系IA，空關系是空關系是A上的反對上的

3、反對稱關系稱關系. 5實例實例例例2 設設A1,2,3, R1, R2, R3和和R4都是都是A上的關系上的關系, 其中其中 R1, R2, R3, R4, R1 對稱、反對稱對稱、反對稱. R2 對稱，不反對稱對稱，不反對稱. R3 反對稱，不對稱反對稱，不對稱. R4 不對稱、也不反對稱不對稱、也不反對稱.6傳遞性傳遞性 定義定義 設設R為為A上的關系上的關系, 若若 x y z(x,y,zARRR),則稱則稱R是是A上的上的傳遞傳遞關系關系.實例：實例： A上的全域關系上的全域關系EA,恒等關系恒等關系IA和空關系和空關系 小于等于關系小于等于關系, 小于關系，整除關系，包含關系，小于關

4、系，整除關系，包含關系， 真包含關系真包含關系7實例實例R1 是是A上的傳遞關系上的傳遞關系 R2不是不是A上的傳遞關系上的傳遞關系R3 是是A上的傳遞關系上的傳遞關系例例3 設設A1,2,3, R1, R2, R3是是A上的關系上的關系, 其中其中R1, , R2,R3, 8關系性質的充要條件關系性質的充要條件設設R為為A上的關系上的關系, 則則 (1) R在在A上上自反自反當且僅當當且僅當 IA R (2) R在在A上上反自反反自反當且僅當當且僅當 RIA= (3) R在在A上上對稱對稱當且僅當當且僅當 R=R 1 (4) R在在A上上反對稱反對稱當且僅當當且僅當 RR 1 IA (5)

5、R在在A上上傳遞傳遞當且僅當當且僅當 R R R 9關系性質判別關系性質判別自反自反反自反反自反對稱對稱反對稱反對稱傳遞傳遞表達式表達式 IA RRIA=R=R 1 RR 1 IA R R R關系關系矩陣矩陣主對主對角線角線元素元素全是全是1主對角主對角線元素線元素全是全是0矩陣是對稱矩陣是對稱矩陣矩陣若若rij1, 且且ij, 則則rji0對對M2中中1所在位置所在位置,M中相應中相應位置都是位置都是1關系圖關系圖 每個每個頂點頂點都有都有環(huán)環(huán)每個頂每個頂點都沒點都沒有環(huán)有環(huán)如果兩個頂如果兩個頂點之間有邊點之間有邊, 是一對方向是一對方向相反的邊相反的邊(無單邊無單邊)如果兩點如果兩點之間有

6、邊之間有邊, 是一條有是一條有向邊向邊(無雙無雙向邊向邊)如果頂點如果頂點 xi 連通到連通到xk , 則從則從 xi到到 xk 有邊有邊 10實例實例例例8 判斷下圖中關系的性質判斷下圖中關系的性質, 并說明理由并說明理由.(2)反自反，不是自反的；反對稱，不是對稱的；反自反，不是自反的；反對稱，不是對稱的； 是傳遞的是傳遞的.(1)不自反也不反自反；對稱不自反也不反自反；對稱, 不反對稱；不傳遞不反對稱；不傳遞.(3)自反，不反自反；反對稱，不是對稱；不傳遞自反，不反自反；反對稱，不是對稱；不傳遞. 11自反性證明自反性證明證明模式證明模式 證明證明R在在A上自反上自反 任取任取x, x

7、A . R 前提前提 推理過程推理過程 結論結論例例4 證明若證明若 IA R ，則則 R在在A上自反上自反. 證證 任取任取x, x A IA R 因此因此 R 在在 A 上是自反的上是自反的.12實例實例n設 ,在A上定義二元關系R如下： 證明：R是A上的自反關系。證證：對于任意的ZZAZvuyxyuxvRvuyx,其中Ayx ,Ryxyxyxxy,13對稱性證明對稱性證明證明模式證明模式 證明證明R在在A上對稱上對稱 任取任取 R . R 前提前提 推理過程推理過程 結論結論例例5 證明若證明若 R=R 1 , 則則R在在A上對稱上對稱. 證證 任取任取 R R 1 R 因此因此 R 在

8、在 A 上是對稱的上是對稱的.14實例實例n設 ,在A上定義二元關系R如下： 證明：R是A上的對稱關系。證證：對于任意的ZZAZvuyxyuxvRvuyx,其中Rvuyx,Ryxvuvxuyyuxv,15反對稱性證明反對稱性證明證明模式證明模式 證明證明R在在A上反對稱上反對稱 任取任取 R R . x=y 前提前提 推理過程推理過程 結論結論例例6 證明若證明若 RR 1 IA , 則則R在在A上反對稱上反對稱. 證證 任取任取 R R R R 1 RR 1 IA x=y 因此因此 R 在在 A 上是反對稱的上是反對稱的.16傳遞性證明傳遞性證明證明模式證明模式 證明證明R在在A上傳遞上傳遞

9、 任取任取， R R . R 前提前提 推理過程推理過程 結論結論例例7 證明若證明若 R R R , 則則R在在A上傳遞上傳遞. 證證 任取任取， R R R R R 因此因此 R 在在 A 上是傳遞的上是傳遞的.17運算與性質的關系運算與性質的關系自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 184.4 關系的閉包關系的閉包n閉包定義閉包定義n閉包的構造方法閉包的構造方法 集合表示集合表示 矩陣表示矩陣表示 圖表示圖表示n閉包的性質閉包的性質 19閉包定義閉包定義 定義定義 設設R是非空集合是非空集合A上的關系上的

10、關系, R的的自反（對自反（對稱稱或或傳遞）閉包傳遞）閉包是是A上的關系上的關系R , 使得使得R 滿足以滿足以下條件：下條件：（1）R 是自反的（對稱的或傳遞的）是自反的（對稱的或傳遞的）（2）R R （3）對）對A上任何包含上任何包含R的自反（對稱或傳遞）的自反（對稱或傳遞）關系關系 R 有有 RR . 一般將一般將 R 的自反閉包記作的自反閉包記作 r(R), 對稱閉包記作對稱閉包記作 s(R), 傳遞閉包記作傳遞閉包記作 t(R). 20閉包的構造方法閉包的構造方法定理定理1 設設R為為A上的關系上的關系, 則有則有 (1) r(R) = RR0 (2) s(R) = RR 1 (3)

11、 t(R) = RR2R3說明：說明： 對于有窮集合對于有窮集合A (|A|=n) 上的關系上的關系, (3)中的并最多中的并最多 不超過不超過 Rn. 若若 R是自反的，則是自反的，則 r(R)=R; 若若R是對稱的，則是對稱的，則 s(R)=R; 若若R是傳遞的，則是傳遞的，則 t(R)=R. 21設關系設關系R, r(R), s(R), t(R)的關系矩陣分別為的關系矩陣分別為M, Mr, Ms 和和 Mt , 則則 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和是和 M 同階的單位矩陣同階的單位矩陣, M是是 M 的轉置矩陣的轉置矩陣. 注意

12、在上述等式中矩陣的元素相加時使用邏輯加注意在上述等式中矩陣的元素相加時使用邏輯加.閉包的構造方法（續(xù)）閉包的構造方法（續(xù)）22關系矩陣的加法CcccccccccbbbbbbbbbaaaaaaaaaBAnmnnmmnmnnmmnmnnmm.212222111211212222111211212222111211對應元素相加元素相加是邏輯加對應元素相加元素相加是邏輯加(邏輯或邏輯或) ijijba ijc23閉包的構造方法（續(xù)）閉包的構造方法（續(xù)）設關系設關系R, r(R), s(R), t(R)的關系圖分別記為的關系圖分別記為G, Gr, Gs, Gt , 則則Gr, Gs, Gt 的頂點集與的

13、頂點集與G 的頂點集相等的頂點集相等. 除了除了G 的邊以外的邊以外, 以下述方法添加新邊：以下述方法添加新邊： 考察考察G的每個頂點的每個頂點, 如果沒有環(huán)就加上一個環(huán)，最如果沒有環(huán)就加上一個環(huán)，最終得到終得到Gr . 考察考察G的每條邊的每條邊, 如果有一條如果有一條 xi 到到 xj 的單的單向邊向邊, ij, 則在則在G中加一條中加一條 xj 到到 xi 的反方向邊，最終的反方向邊，最終得到得到Gs. 考察考察G的每個頂點的每個頂點 xi, 找從找從 xi 出發(fā)的每一條路出發(fā)的每一條路徑，如果從徑，如果從 xi 到路徑中任何結點到路徑中任何結點 xj 沒有邊，就加上沒有邊，就加上這條邊這條邊. 當檢查完所有的頂點后就得到圖當檢查完所有的頂點后就得到圖Gt . 24實例實例例例1 設設A=a,b,c,d, R=, R和和 r(R), s(R), t(R)的關系圖如下圖所示的關系圖如下圖所示. Rr(R)s