【正文】 IA ? R (2) R 在 A上反自反當(dāng)且僅當(dāng) R∩IA = ? (3) R 在 A上對(duì)稱當(dāng)且僅當(dāng) R=R?1 (4) R 在 A上反對(duì)稱當(dāng)且僅當(dāng) R∩R?1 ? IA (5) R 在 A上傳遞當(dāng)且僅當(dāng) R?R ? R 40 證明 證明 只證 (1)、 (3)、 (4)、 (5) (1) 必要性 任取 x,y, 由于 R 在 A上自反必有 x,y∈ IA ? x,y∈ A∧ x=y ? x,y∈ R 從而證明了 IA?R 充分性 . 任取 x, 有 x∈ A ? x,x∈ IA ? x,x∈ R 因此 R 在 A上是自反的 . 41 證明 (3) 必要性 . 任取 x,y, x,y∈ R ? y,x∈ R ? x,y∈ R?1 所以 R = R?1 充分性 . 任取 x,y, 由 R = R?1得 x,y∈ R ? y,x∈ R?1 ? y,x∈ R 所以 R在 A上是對(duì)稱的 42 證明 (4) 必要性 . 任取 x,y, 有 x,y∈ R∩R?1 ? x,y∈ R∧ x,y∈ R?1 ? x,y∈ R∧ y,x∈ R ? x=y ? x,y?A ? x,y∈ IA 這就證明了 R∩R?1?IA 充分性 . 任取 x,y, x,y∈ R∧ y,x∈ R ? x,y∈ R∧ x,y∈ R?1 ? x,y∈ R∩R?1 ? x,y∈ IA ? x=y 從而證明了 R在 A上是反對(duì)稱的 . 43 證明 (5) 必要性 . 任取 x,y有 x,y∈ R?R ? ?t (x,t∈ R∧ t,y∈ R) ? x,y∈ R 所以 R?R ? R 充分性 . 任取 x,y,y,z∈ R, 則 x,y∈ R∧ y,z∈ R ? x,z∈ R?R ? x,z∈ R 所以 R 在 A上是傳遞的 44 自反性 反自反性 對(duì)稱性 反對(duì)稱性 傳遞性 集合 IA?R R∩IA=? R=R?1 R∩R?1?IA R?R?R 關(guān)系矩陣 主對(duì)角線元素全是 1 主對(duì)角線元素全是 0 矩陣是 對(duì)稱矩陣 若 rij＝ 1, 且i≠j, 則 rji＝ 0 M2中 1位置 , M中相應(yīng)位置都是 1 關(guān)系圖 每個(gè)頂點(diǎn)都有環(huán) 每個(gè)頂點(diǎn)都沒有環(huán) 兩點(diǎn)之間有邊 , 是一對(duì)方向相反的邊 兩點(diǎn)之間有邊 ,是一條有向邊 點(diǎn) xi到 xj有邊 , xj 到 xk有邊 , 則 xi到 xk也有邊 關(guān)系性質(zhì)的三種等價(jià)條件 45 自反性 反自反性 對(duì)稱性 反對(duì)稱性 傳遞性 R1?1 √ √ √ √ √ R1∩R2 √ √ √ √ √ R1∪ R2 √ √ √ R1?R2 √ √ √ R1 ? R2 √ 關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系 46 關(guān)系的閉包 主要內(nèi)容 ? 閉包定義 ? 閉包的構(gòu)造方法 集合表示 矩陣表示 圖表示 ? 閉包的性質(zhì) 47 閉包定義 定義 設(shè) R是非空集合 A上的關(guān)系 , R的 自反 (對(duì)稱 或 傳遞 )閉 包 是 A上的關(guān)系 R?, 使得 R?滿足以下條件： (1) R?是自反的 (對(duì)稱的或傳遞的 ) (2) R?R? (3) 對(duì) A上任何包含 R的自反 (對(duì)稱或傳遞 )關(guān)系 R?? 有 R??R?? R的自反閉包記作 r(R), 對(duì)稱閉包記作 s(R), 傳遞閉包記作 t(R). 定理 設(shè) R為 A上的關(guān)系 , 則有 (1) r(R)=R∪ R0 (2) s(R)=R∪ R?1 (3) t(R)=R∪ R2∪ R3∪ … 說明：對(duì)有窮集 A(|A|=n)上的關(guān)系 , (3)中的并最多不超過 Rn 48 證明 證 只證 (1)和 (3). (1) 由 IA=R0?R∪ R0 知 R∪ R0是自反的 , 且滿足 R?R∪ R0 設(shè) R?? 是 A上包含 R的自反關(guān)系 , 則有 R?R?? 和 IA ?R?? . 從而有 R∪ R0?R??. R∪ R0滿足閉包定義 , 所以 r(R)=R∪ R0. (1) 先證 R∪ R2∪ … ? t(R)成立 . 用歸納法證明對(duì)任意正整數(shù) n 有 Rn ? t(R). n=1時(shí)有 R1=R ? t(R). 假設(shè) Rn?t(R)成立 , 那么對(duì)任意的 x,y x,y∈ Rn+1=Rn?R ? ?t ( x,t∈ Rn∧ t,y∈ R) ? ?t (x,t∈ t(R)∧ t,y∈ t(R)) ? x,y∈ t(R) 這就證明了 Rn+1?t(R). 由歸納法命題得證 . 49 證明 再證 t(R) ? R∪ R2∪ … 成立 , 為此只須證明 R∪ R2∪ … 傳遞 . 任取 x,y,y,z, 則 x,y∈ R∪ R2∪ … ∧ y,z∈ R∪ R2∪ … ? ?t (x,y∈ Rt)∧ ?s(y,z∈ Rs) ? ?t ?s (x,z∈ Rt?Rs ) ? ?t ?s (x,z∈ Rt+s ) ? x,z∈ R∪ R2∪ … 從而證明了 R∪ R2∪ … 是傳遞的 . 50 閉包的矩陣表示和圖表示 設(shè)關(guān)系 R, r(R), s(R), t(R)的關(guān)系矩陣分別為 M, Mr , Ms 和 Mt 則 Mr=M+E Ms=M+M 39。 證 R是 A上的等價(jià)關(guān)系 . (1) 證自反 任取 x, x?A ? x,x?R ? ?x (x,x?R?x,x?R) ? x,x?S (2) 證對(duì)稱 任取 x,y, x,y?S ? ?c(x,c?R?c,y?R) ? ?c (c,x?R?y,c?R) ?y,x?S (3) 證傳遞 任取 x,y, y,z, x,y?S ? y,z?S ? ?c (x,c?R?c,y?R) ? ?d (y,d?R?d,z?R) ? x,y?R?y,z? R ? x,z?S 81 6．設(shè)偏序集 A,R和 B,S，定義 A?B上二元關(guān)系 T: x,yTu,v ? xRu ? ySv 證明 T為偏序關(guān)系 . 練習(xí) 6 證 (1) 自反性 任取 x,y, x,y?A?B ? x?A?y?B ? xRx?ySy ? x,yTx,y (2) 反對(duì)稱性 任取 x,y,u,v x,yTu,v?u,vTx,y ? xRu ? ySv ? uRx ? vSy ? (xRu ? uRx) ? (ySv ? vSy) ? x=u ? y=v ? x,y=u,v (3) 傳遞性 任取 x,y,u,v, w,t x,yTu,v?u,vTw,t ? xRu ? ySv ? uRw ? vSt ? (xRu ? uRw) ? (ySv ? vSt) ? xRw ? ySt ? x,yTw,t 82 關(guān)系性質(zhì)的證明方法 1. 證明 R在 A上自反 任取 x, x?A ? ……………………..….……. ? x,x?R 前提 推理過程 結(jié)論 2. 證明 R在 A上對(duì)稱 任取 x,y， x,y ?R ? ………………………………. ? y,x?R 前提 推理過程 結(jié)論 83 3. 證明 R在 A上反對(duì)稱 任取 x,y， x,y?R?y,x?R ? …………………….. ? x = y 前提 推理過程 結(jié)論 4. 證明 R在 A上傳遞 任取 x,y,y,z， x,y?R?y,z?R ? …………………….. ? x,z?R 前提 推理過程 結(jié)論 關(guān)系性質(zhì)的證明方法 84 7． R,S為 A上的關(guān)系，證明 R?S ? t(R) ? t(S) 練習(xí) 7 證 只需證明對(duì)于任意正整數(shù) n, Rn ? Sn. 對(duì) n歸納 . n=1, 顯然為真 . 假設(shè)對(duì)于 n，命題為真，任取 x,y x,y?Rn+1 ? x,y?Rn°R ? ?t (x, t?Rn ? t, y?R) ? ?t (x, t?Sn ? t, y?S) ? x,y?Sn°S ? x,y?Sn+1 85 ? 數(shù)學(xué)歸納法（主要用于冪運(yùn)算） ? 證明中用到關(guān)系運(yùn)算的定義和公式 , 如： x?domR ? ?y(x,y?R) y?ranR ? ?x(x,y?R) x,y?R ? y,x?R?1 x,y?R°S ? ?t (x,t?R?t,y?S) x,y?R?A ? x?A ? x,y?R y?R?A] ? ?x (x?A ? x,y?R) r(R) = R?IA s(R) = R?R?1 t(R) = R?R2?… 關(guān)系等式或包含式的證明方法