離散數(shù)學(xué)習(xí)題課-關(guān)系

1、1主要內(nèi)容主要內(nèi)容 有序?qū)εc笛卡兒積的定義與性質(zhì)有序?qū)εc笛卡兒積的定義與性質(zhì) 二元關(guān)系、從二元關(guān)系、從A到到B的關(guān)系、的關(guān)系、A上的關(guān)系上的關(guān)系 關(guān)系的表示法：關(guān)系表達(dá)式、關(guān)系矩陣、關(guān)系的表示法：關(guān)系表達(dá)式、關(guān)系矩陣、關(guān)系圖關(guān)系圖 關(guān)系的運(yùn)算：逆、合成關(guān)系的運(yùn)算：逆、合成(復(fù)合復(fù)合)、冪、冪 關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì): A上關(guān)系的自反、反自反、上關(guān)系的自反、反自反、對稱、反對稱、傳遞的性質(zhì)對稱、反對稱、傳遞的性質(zhì) A上關(guān)系的自反、對稱、傳遞閉包上關(guān)系的自反、對稱、傳遞閉包 A上的等價(jià)關(guān)系、等價(jià)類、商集與上的等價(jià)關(guān)系、等價(jià)類、商集與A的劃分的劃分 A上的偏序關(guān)系與偏序集上的偏序關(guān)系與偏序集2

2、 熟練掌握關(guān)系的表示法熟練掌握關(guān)系的表示法 能夠判定關(guān)系的性質(zhì)能夠判定關(guān)系的性質(zhì) 掌握含有關(guān)系運(yùn)算的集合等式掌握含有關(guān)系運(yùn)算的集合等式 掌握等價(jià)關(guān)系、等價(jià)類、商集、劃分、哈斯掌握等價(jià)關(guān)系、等價(jià)類、商集、劃分、哈斯圖、偏序集等概念圖、偏序集等概念 計(jì)算計(jì)算A B, R 1, R S , Rn , r(R), s(R), t(R), Mi,求等價(jià)類和商集求等價(jià)類和商集A/R 給定給定A的劃分的劃分 ，求出，求出 所對應(yīng)的等價(jià)關(guān)系所對應(yīng)的等價(jià)關(guān)系3 求偏序集中的極大元、極小元、最大元、求偏序集中的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界最小元、上界、下界、上確界、下確界 掌握基本的

3、證明方法掌握基本的證明方法 證明涉及關(guān)系運(yùn)算的集合等式證明涉及關(guān)系運(yùn)算的集合等式 證明關(guān)系的性質(zhì)、閉包性質(zhì)的證明證明關(guān)系的性質(zhì)、閉包性質(zhì)的證明 、證、證明關(guān)系是等價(jià)關(guān)系或偏序關(guān)系明關(guān)系是等價(jià)關(guān)系或偏序關(guān)系4設(shè)設(shè)A = 1, 2, 3, R = , , , , S = , , 求求: (1) R 1(2) R S, R3(3) r(R), s(R), t(R)5(1) R 1 = , , , , (2) R S = , , , , , R3 = , , , , , (3) r(R) = , , , , , s(R) = , , , t(R) = , , , , , 6已知集合 X 與關(guān)系 R,試

4、求 r(R) s(R) t(R). ,dcbaX ,addccbbaRacdb:Racdb: )(Rr解：7,dcbaX ,addccbbaRacdb:Racdb: )(Rs8acdb2:RRacdb:Racdb23:RRRacdb234:RRRR9設(shè)設(shè)R是是A上的二元關(guān)系，上的二元關(guān)系， 設(shè)設(shè) S = | c( R R).證明如果證明如果R是等價(jià)關(guān)系，則是等價(jià)關(guān)系，則S也是等也是等價(jià)關(guān)系。價(jià)關(guān)系。10關(guān)系性質(zhì)的證明方法1. 證明證明R在在A上自反上自反 任取任取x, x A . R 前提前提 推理過程推理過程 結(jié)論結(jié)論2. 證明證明R在在A上對稱上對稱 任取任取， R . R 前提前提 推理

5、過程推理過程 結(jié)論結(jié)論11關(guān)系性質(zhì)的證明方法3. 證明證明R在在A上反對稱上反對稱 任取任取， R R . x = y 前提前提 推理過程推理過程 結(jié)論結(jié)論4. 證明證明R在在A上傳遞上傳遞 任取任取,， R R . R 前提前提 推理過程推理過程 結(jié)論結(jié)論12 設(shè)設(shè)R是是A上的二元關(guān)系，上的二元關(guān)系， 設(shè)設(shè) S = | c( R R).證明如果證明如果R是等價(jià)關(guān)系，則是等價(jià)關(guān)系，則S也是等價(jià)關(guān)系。也是等價(jià)關(guān)系。(1) 證自反證自反 任取任取x, x A R x ( R R) S(2) 證對稱證對稱 任取任取, S c( R R) c ( R R) S (3) 證傳遞證傳遞 任取任取, , S

6、 S c ( R R) d ( R R) R R S13試證試證 性質(zhì) rs(R) = sr(R)( )()Asr Rs RI( )( )As RIrs R1()()AARIRI11AARIRI1ARRI證明：設(shè) IA 是 A 上的恒等關(guān)系14BB AB BA AA 求2, 1,BbaA已知15BB AB BA AA 求解：2 ,1 ,2 ,1 ,bbaaBA, 2, 2, 1, 1babaAB,bbabbaaaAA2 , 2,1 , 2,2 , 1,1 , 1BB2, 1,BbaA已知ABBA16已知有五個(gè)城市的航班服務(wù)，下表是從ci到cj的航線的票價(jià)，R是定義在城市的集合A=c1,c2,c

7、3,c4,c5上的關(guān)系，ci R cj當(dāng)且僅當(dāng)從ci到cj的票價(jià)小于1500. C1C2C3C4C5C1 1400100015002000C21900 200016002200C311001800 19002500C4190020001200 1500C52000100020001500 FromTo17已知有五個(gè)城市的航班服務(wù)，下表是從ci到cj的航線的票價(jià)，R是定義在城市的集合A=c1,c2,c3,c4,c5上的關(guān)系，ci R cj當(dāng)且僅當(dāng)從ci到cj的票價(jià)小于1500.解解： R = , , , , C1C2C3C4C5C1 1400100015002000C21900 20001600

8、2200C311001800 19002500C4190020001200 1500C52000100020001500 FromTo 18Test3已知求關(guān)系及關(guān)系矩陣abdc19Test3-Answer已知求關(guān)系及關(guān)系矩陣R=, , , 1010011100100001RM解：abdc20,6cacbbaR,7accbbaR,8cabaR,1ccbbbaaaR,2acbbbaaaR,3ccabbacaR,4ccabbaaaR,5ccbbabbaaaR21,6cacbbaR,7accbbaR,8cabaR ,1ccbbbaaaR,2acbbbaaaR,3ccabbacaR,4ccabbaaa

9、R,5ccbbabbaaaR22,6cacbbaR,7accbbaR,8cabaR ,1ccbbbaaaR,2acbbbaaaR,3ccabbacaR,4ccabbaaaR,5ccbbabbaaaR23,6cacbbaR,7accbbaR,8cabaR ,1ccbbbaaaR,2acbbbaaaR,3ccabbacaR,4ccabbaaaR,5ccbbabbaaaR24,6cacbbaR,7accbbaR,8cabaR ,1ccbbbaaaR,2acbbbaaaR,3ccabbacaR,4ccabbaaaR,5ccbbabbaaaR25,6cacbbaR,7accbbaR,8cabaR ,1c

10、cbbbaaaR,2acbbbaaaR,3ccabbacaR,4ccabbaaaR,5ccbbabbaaaR26一個(gè)關(guān)系不是自反的，就一一個(gè)關(guān)系不是自反的，就一定是反自反的嗎？定是反自反的嗎？不一定。不一定。如：如：A=1,2,3, S=,則則 S 既不是自反的也不是反自反的。既不是自反的也不是反自反的。？27 一個(gè)關(guān)系不是對稱的，就一定一個(gè)關(guān)系不是對稱的，就一定是反對稱的嗎？是反對稱的嗎？不一定。不一定。如：如：A=1,2,3, S=, 則則 S 既不是對稱的也不是反對稱的。既不是對稱的也不是反對稱的。 IA=,IA即是對稱的，也是反對稱的。即是對稱的，也是反對稱的。？28關(guān)系性質(zhì)成立的充要

11、條件關(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 = (3) R 在在A上對稱當(dāng)且僅當(dāng)上對稱當(dāng)且僅當(dāng) R=R 1(4) R 在在A上反對稱當(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 29 已知集合X與關(guān)系R，求r(R) s(R) t(R). ,cbaX ,cbbaR30 求r(R) s(R) t(R). ,cbaX ,ccbbaaRXIRRr)(,cbbaR,cbba,ccbbaa-1RRRs)(,bc

12、abcbba解：31Test5-Answer,cbaX ,cbbaR23( )t RRRR, ,a bb ca c ,cacbba2,Ra c 3R32Test6-Answer已知X=a,b,c,d,e, C=a,b,c,d,e試寫出由 C 導(dǎo)出的 X 中的等價(jià)關(guān)系 R ,并給出關(guān)系矩陣和關(guān)系圖.33Test6-Answer,abbaaa,ddccbb,eedeed,eded,ccbabaR解：已知X=a,b,c,d,e, C=a,b,c,d,e試寫出由 C 導(dǎo)出的 X 中的等價(jià)關(guān)系 R ,并給出關(guān)系矩陣和關(guān)系圖.34Test6-Answer（續(xù)）cdeba110001100000100000

13、1100011RM35,dcbaX bbabbaaaR,ddcddccc已知試畫出 R 的等價(jià)關(guān)系圖, 并求出各元素的 R 等價(jià)類.36,dcbaX bbabbaaaR,ddcddccc已知試畫出 R 的等價(jià)關(guān)系圖, 并求出各元素的 R 等價(jià)類.badc ,babaRR , dcdcRR解：37 已知已知 A=a,b,c,d,e,bbeadacabaaaR,eeedddecccebcb驗(yàn)證驗(yàn)證 是偏序集，畫出哈斯圖是偏序集，畫出哈斯圖38 已知已知 A=a,b,c,d,e,bbeadacabaaaR,eeedddecccebcb驗(yàn)證驗(yàn)證 是偏序集，畫出哈斯圖是偏序集，畫出哈斯圖解：解： 100

14、0011000101001011011111RM關(guān)系矩陣對角線關(guān)系矩陣對角線都為都為1，且，且rij 和和rji 不同時(shí)為不同時(shí)為1，所以，所以 R 是是自反的自反的和和反反對稱對稱的的。39abcde關(guān)系圖關(guān)系圖R是傳遞的。是傳遞的。COVA=, , ,eabcd哈斯圖哈斯圖40Test9 已知已知21,15,14,7,5,3,2A14,21, 3 ,7 ,2B2753142115偏序關(guān)系哈斯圖如下偏序關(guān)系哈斯圖如下B 的極大元：B 的極小元：當(dāng) B=A 時(shí)，其極大元是？，極小元是？41Test9-Answer 已知已知21,15,14,7,5,3,2A14,21, 3 ,7 ,2B2753142115偏序關(guān)系哈斯圖如下偏序關(guān)系哈斯圖如下B 的極大元：14, 212, 7, 3B 的極小元：當(dāng) B=A 時(shí)，其極大元是14,21,15，極小元是2,7,3,5極大元與極小元不惟一極大元與極小元不惟一42B=a,b,c,d,e,f,g Test10abcdefghijk上界： 下界：B=h,i,j,k上界：下界：B=上界： 下界：43B=a,b,c,d,e,f,g T