離散數(shù)學(xué) 關(guān)系的性質(zhì)優(yōu)秀課件_第1頁(yè)
離散數(shù)學(xué) 關(guān)系的性質(zhì)優(yōu)秀課件_第2頁(yè)
離散數(shù)學(xué) 關(guān)系的性質(zhì)優(yōu)秀課件_第3頁(yè)
離散數(shù)學(xué) 關(guān)系的性質(zhì)優(yōu)秀課件_第4頁(yè)
離散數(shù)學(xué) 關(guān)系的性質(zhì)優(yōu)秀課件_第5頁(yè)
已閱讀5頁(yè),還剩23頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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自反自反反自反反自反對(duì)稱(chēng)對(duì)稱(chēng)反對(duì)稱(chēng)反對(duì)稱(chēng)傳遞傳遞定義定義 xA,有有 R), xA,有有 R,若若 R有有R),若若R且且x y ,則則 R若若RR,則則R),表達(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ì)稱(chēng)矩陣稱(chēng)矩陣若若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è)頂每

2、個(gè)頂點(diǎn)都沒(méi)點(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 有邊有邊 3自反性與反自反性自反性與反自反性例:例:自反關(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)系4實(shí)例實(shí)例例例1 A=1,2,3, R1, R2,

3、 R3是是A上的關(guān)系上的關(guān)系, 其中其中R1,R2,R3R2自反自反, R3反自反反自反, R1既不是自反也不是反自反的既不是自反也不是反自反的5對(duì)稱(chēng)性與反對(duì)稱(chēng)性對(duì)稱(chēng)性與反對(duì)稱(chēng)性實(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)系:恒等關(guān)系反對(duì)稱(chēng)關(guān)系:恒等關(guān)系IA,空關(guān)系是空關(guān)系是A上的反對(duì)稱(chēng)關(guān)系上的反對(duì)稱(chēng)關(guān)系. 6實(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

4、反對(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).7傳遞性傳遞性 實(shí)例:實(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)系8實(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)系9關(guān)系性質(zhì)的充要條件關(guān)系性質(zhì)的充要條件設(shè)設(shè)R為為A上的關(guān)系上的關(guān)系, 則則 (1) R在在A上上自反自反當(dāng)且僅當(dāng)

5、當(dāng)且僅當(dāng) IA R (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 10實(shí)例實(shí)例例例.判斷下圖中關(guān)系的性質(zhì)判斷下圖中關(guān)系的性質(zhì), 并說(shuō)明理由并說(shuō)明理由.(2)反自反,不是自反的;反對(duì)稱(chēng),不是對(duì)稱(chēng)的;反自反,不是自反的;反對(duì)稱(chēng),不是對(duì)稱(chēng)的; 是傳遞的是傳遞的.(1)不自反也不反自反;對(duì)稱(chēng)不自反也不反自反;對(duì)稱(chēng), 不反對(duì)稱(chēng);不傳遞不反對(duì)稱(chēng);不傳遞.(3)自反,不反自反;反對(duì)稱(chēng),不是對(duì)稱(chēng);不傳遞自反,不反自反

6、;反對(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)上對(duì)稱(chēng). 證證 任取任取 R R 1 R 因此因此 R 在在 A 上是對(duì)稱(chēng)的上是對(duì)稱(chēng)的.13反對(duì)稱(chēng)

7、性證明反對(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在在A上傳遞上傳遞. 證證 任取任取, R R R R R 因此因此 R 在在 A 上是傳遞的上是傳

8、遞的.15運(yùn)算與性質(zhì)的關(guān)系運(yùn)算與性質(zhì)的關(guān)系自反性自反性反自反性反自反性對(duì)稱(chēng)性對(duì)稱(chēng)性反對(duì)稱(chēng)性反對(duì)稱(chēng)性傳遞性傳遞性R1 1 R1R2 R1R2 R1 R2 R1 R2 164.4 關(guān)系的閉包關(guān)系的閉包n閉包定義閉包定義n閉包的構(gòu)造方法閉包的構(gòu)造方法 集合表示集合表示 矩陣表示矩陣表示 圖表示圖表示n閉包的性質(zhì)閉包的性質(zhì) 17閉包定義閉包定義 定義定義 設(shè)設(shè)R是非空集合是非空集合A上的關(guān)系上的關(guān)系, R的的自反(對(duì)自反(對(duì)稱(chēng)稱(chēng)或或傳遞)閉包傳遞)閉包是是A上的關(guān)系上的關(guān)系R , 使得使得R 滿(mǎn)足以滿(mǎn)足以下條件:下條件:(1)R 是自反的(對(duì)稱(chēng)的或傳遞的)是自反的(對(duì)稱(chēng)的或傳遞的)(2)R R (3)

9、對(duì))對(duì)A上任何包含上任何包含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). 18閉包的構(gòu)造方法閉包的構(gòu)造方法定理定理1 設(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)中的并是有中的并是有 限的限的. 若若 R是自反的,則是自反的,則 r(R)=R; 若若R是對(duì)稱(chēng)的,則是

10、對(duì)稱(chēng)的,則 s(R)=R; 若若R是傳遞的,則是傳遞的,則 t(R)=R. 19(3)t(R)RR2R3 先證先證RR2 t(R)成立,為此只需證明對(duì)任意成立,為此只需證明對(duì)任意的正整數(shù)的正整數(shù)n有有 Rn t(R)即可。用歸納法。即可。用歸納法。n1時(shí),有時(shí),有 R1R t(R)。假設(shè)假設(shè)Rn t(R)成立,那么對(duì)任意的成立,那么對(duì)任意的有有 Rn+1Rn R t(RnR) t(t(R)t(R) t(R) (因?yàn)椋ㄒ驗(yàn)閠(R)是傳遞的)是傳遞的)這就證明了這就證明了Rn+1 t(R)。由歸納法命題得證。由歸納法命題得證。20再證再證t(R) RR2成立,為此只須證明成立,為此只須證明RR2是

11、傳遞的。是傳遞的。任取任取,,則,則 RR2 RR2 t(Rt) s(Rs) t s(Rt Rs) t s(Rt Rs) t s(Rt+s) RR2從而證明了從而證明了RR2是傳遞的。是傳遞的。21推論推論 設(shè)設(shè)R為有窮集為有窮集A上的關(guān)系,則存在正整數(shù)上的關(guān)系,則存在正整數(shù)r使得使得 t(R)=RR2Rr22閉包的構(gòu)造方法(續(xù))閉包的構(gòu)造方法(續(xù))設(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 同階的單位矩陣同階的單位

12、矩陣, M是是 M 的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣. 注意在上述等式中矩陣的元素相加時(shí)使用邏輯加注意在上述等式中矩陣的元素相加時(shí)使用邏輯加.23閉包的構(gòu)造方法(續(xù))閉包的構(gòu)造方法(續(xù))設(shè)關(guān)系設(shè)關(guān)系R, r(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 的邊以外的邊以外, 以下述方法添加新邊:以下述方法添加新邊: (1)考察考察G的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn), 如果沒(méi)有環(huán)就加上一個(gè)環(huán),最終得到如果沒(méi)有環(huán)就加上一個(gè)環(huán),最終得到Gr . (2)考察考察G的每條邊的每條邊,

13、 如果有一條如果有一條 xi 到到 xj 的單向邊的單向邊, ij, 則在則在G 中加一條中加一條 xj 到到 xi 的反方向邊,最終得到的反方向邊,最終得到Gs. (3)考察考察G的每個(gè)頂點(diǎn)的每個(gè)頂點(diǎn) xi, 找從找從 xi 出發(fā)的每一條出發(fā)的每一條 長(zhǎng)度不超過(guò)長(zhǎng)度不超過(guò)n的的 路徑,如果從路徑,如果從 xi 到路徑中任何結(jié)點(diǎn)到路徑中任何結(jié)點(diǎn) xj 沒(méi)有邊,就加上這條沒(méi)有邊,就加上這條 邊邊. 當(dāng)檢查完所當(dāng)檢查完所 有的頂點(diǎn)后就得到圖有的頂點(diǎn)后就得到圖Gt . 24實(shí)例實(shí)例例例1 設(shè)設(shè)A=a,b,c,d, R=, R和和 r(R), s(R), t(R)的關(guān)系圖如下圖所示的關(guān)系圖如下圖所示. Rr(R)s(R)t(R)25R=,r(R) = RR0=, =,s(R)= RR 1=, =, , t(R) = R1R2R3R4=, ,=, ,26Mr=Ms=Mt=0100100011001010010011100001001000110100000101010100010001001010100110110001010001010100001001100 1 0 01 0 1 00 1 0 11 1 1 01 1 1 11 0 1 00 1 0 11 1 1

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論