《月號離散數(shù)學(xué)》PPT課件.ppt

1、1,第4章 二元關(guān)系與函數(shù),4.4 關(guān)系的閉包 4.5 等價關(guān)系和偏序關(guān)系,2,4.4 關(guān)系的閉包,閉包定義 閉包的構(gòu)造方法 集合表示 矩陣表示 圖表示,3,閉包定義,定義 設(shè)R是非空集合A上的關(guān)系, R的自反（對稱或傳遞）閉包是A上的關(guān)系R, 使得R滿足以下條件：（1）R是自反的（對稱的或傳遞的）（2）RR（3）對A上任何包含R的自反（對稱或傳遞）關(guān)系 R 有 RR. 一般將 R 的自反閉包記作 r(R), 對稱閉包記作 s(R), 傳遞閉包記作 t(R).,4,閉包的構(gòu)造方法1.集合并運(yùn)算,定理1 設(shè)R為A上的關(guān)系, 則有 (1) r(R) = RR0(2) s(R) = RR1(3) t

2、(R) = RR2R3說明： 對于有窮集合A (|A|=n) 上的關(guān)系, (3)中的并最多 不超過 Rn.,5,性質(zhì),6,解法一,7,8,(參考第二節(jié)例3),9,(參考第二節(jié)例3),10,設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系矩陣分別為M, Mr, Ms 和 Mt , 則 Mr = M + E Ms = M + M Mt = M + M2 + M3 + E 是和 M 同階的單位矩陣, M是 M 的轉(zhuǎn)置矩陣. 注意在上述等式中矩陣的元素相加時使用邏輯加.,閉包的構(gòu)造方法（續(xù)）2.利用關(guān)系矩陣,11,閉包的構(gòu)造方法（續(xù)）,設(shè)關(guān)系R, r(R), s(R), t(R)的關(guān)系圖分別記為G,

3、 Gr, Gs, Gt , 則Gr, Gs, Gt 的頂點(diǎn)集與G 的頂點(diǎn)集相等. 除了G 的邊以外, 以下述方法添加新邊： 考察G的每個頂點(diǎn), 如果沒有環(huán)就加上一個環(huán)，最終得到Gr . 考察G的每條邊, 如果有一條 xi 到 xj 的單向邊, ij, 則在G中加一條 xj 到 xi 的反方向邊，最終得到Gs. 考察G的每個頂點(diǎn) xi, 找從 xi 出發(fā)的每一條路徑，如果從 xi 到路徑中任何結(jié)點(diǎn) xj 沒有邊，就加上這條邊. 當(dāng)檢查完所有的頂點(diǎn)后就得到圖Gt .,12,閉包的構(gòu)造方法（續(xù)）3.利用關(guān)系圖,13,14,解法二,15,解法二,16,解法二,17,解法三 利用關(guān)系矩陣(略)。,18,

4、4.5 等價關(guān)系與偏序關(guān)系,等價關(guān)系的定義與實(shí)例 等價類及其性質(zhì) 商集與集合的劃分 等價關(guān)系與劃分的一一對應(yīng) 偏序關(guān)系 偏序集與哈斯圖 偏序集中的特定元素,19,等價關(guān)系的定義,定義 設(shè) R 為非空集合上的關(guān)系. 如果 R 是自反的、對稱的和傳遞的, 則稱 R 為 A 上的等價關(guān)系. 設(shè) R 是一個等價關(guān)系, 若R, 稱 x 等價于y, 記做 xy.,20,21,等價關(guān)系的驗(yàn)證,驗(yàn)證模 3 相等關(guān)系 R 為 A上的等價關(guān)系, 因?yàn)樽苑葱?xA, 有x x(mod 3)對稱性 x, yA, 若 x y(mod 3), 則有 y x(mod 3)傳遞性 x, y, zA, 若x y(mod 3),

5、 y z(mod 3), 則有 xz(mod 3),實(shí)例 設(shè) A=1,2,8, 如下定義A上的關(guān)系 R： R = | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 與 y 模3相等, 即 x 除以3的余數(shù)與 y 除以3的余數(shù)相等.,22,A上模3等價關(guān)系的關(guān)系圖,設(shè) A=1,2,8, R= | x,yAxy(mod 3) ,23,已知,只要證,是等價關(guān)系，,是自反的，要證,是對稱的和傳遞的即可。,24,等價類,定義 設(shè)R為非空集合A上的等價關(guān)系, xA，令xR = y | yAxRy 稱 xR 為 x 關(guān)于R 的等價類, 簡稱為 x 的等價類, 簡 記為x.,實(shí)例 A= 1,

6、 2, , 8 上模 3 等價關(guān)系的等價類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,25,等價類的性質(zhì),定理1 設(shè)R是非空集合A上的等價關(guān)系, 則 (1) xA, x 是A的非空子集. (2) x, yA, 如果 x R y, 則 x=y. (3) x, yA, 如果 x y, 則 x與y不交. (4) x | xA=A，即所有等價類的并集就是A.,26,實(shí)例,A= 1, 2, , 8 上模 3 等價關(guān)系的等價類： 1=4=7=1,4,7， 2=5=8=2,5,8， 3=6=3,6 以上3 類兩兩不交， 1,4,72,5,83,6 = 1,2, ,8,27,商集,定義

7、 設(shè)R為非空集合A上的等價關(guān)系, 以R的所有等價類作為元素的集合稱為A關(guān)于R的商集, 記做A/R, A/R = xR | xA ,實(shí)例 A=1,2,8,A關(guān)于模3等價關(guān)系R的商集為 A/R = 1,4,7, 2,5,8, 3,6 A關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 ,28,集合的劃分,定義 設(shè)A為非空集合, 若A的子集族(P(A) 滿足下面條件： (1) (2) xy (x,yxyxy=) (3) =A 則稱是A的一個劃分, 稱中的元素為A的劃分塊.,29,例題,例1 設(shè)Aa, b, c, d, 給定1,2,3,4,5,6如下： 1

8、= a, b, c, d ， 2= a, b, c, d 3= a, a, b, c, d , 4= a, b, c 5= ,a, b, c, d , 6= a, a, b, c, d 則1和2 是A的劃分, 其他都不是 A 的劃分. 為什么？,30,等價關(guān)系與劃分的一一對應(yīng),商集 A/R 就是 A 的一個劃分 不同的商集對應(yīng)于不同的劃分 任給 A 的一個劃分, 如下定義 A 上的關(guān)系 R： R = | x,yAx 與 y 在的同一劃分塊中則 R 為 A上的等價關(guān)系, 且該等價關(guān)系確定的商集就是.,例2 給出A1,2,3上所有的等價關(guān)系 求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫 出對應(yīng)的

9、等價關(guān)系.,31,等價關(guān)系與劃分之間的對應(yīng),1,2和3分別對應(yīng)等價關(guān)系 R1, R2 和 R3. R1=,IA，R2=,IA R3=,IA,4 對應(yīng)于全域關(guān)系 EA，5 對應(yīng)于恒等關(guān)系 IA,32,實(shí)例,例3 設(shè) A=1, 2, 3, 4，在 AA上定義二元關(guān)系R： ,R x+y = u+v， 求 R 導(dǎo)出的劃分.,解 AA=, , , , , , , , , , , , , ,33,實(shí)例（續(xù)）,根據(jù) 的 x + y = 2,3,4,5,6,7,8 將AA劃分成7個 等價類： (AA)/R= , , , , , , , , , , , , , , ,34,偏序關(guān)系,定義 非空集合A上的自反、反

10、對稱和傳遞的關(guān)系，稱為A上的偏序關(guān)系，記作. 設(shè)為偏序關(guān)系, 如果, 則記作 xy, 讀作 x“小于或等于”y. 實(shí)例 集合A上的恒等關(guān)系 IA 是A上的偏序關(guān)系. 小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.,35,相關(guān)概念,x與 y 可比：設(shè)R為非空集合A上的偏序關(guān)系, x,yA, x與y可比 xy yx.結(jié)論：任取兩個元素x和y, 可能有下述情況： xy (或yx), xy, x與y不是可比的. 全序關(guān)系： R為非空集合A上的偏序, x,yA, x與 y 都是可比的，則稱 R 為全序（或 線序） 實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系 整除關(guān)系不是正整數(shù)集合上的全序關(guān)系

11、,36,覆蓋：設(shè)R為非空集合A上的偏序關(guān)系, x, yA, 如果 x y且不存在 zA 使得 x z y, 則稱 y 覆蓋x. 實(shí)例： 1, 2, 4, 6 集合上的整除關(guān)系, 2 覆蓋 1, 4 和 6 覆蓋 2. 4 不覆蓋 1.,相關(guān)概念（續(xù)）,37,偏序集與哈斯圖,定義 集合A和A上的偏序關(guān)系一起叫做偏序集, 記作 .實(shí)例：整數(shù)集和小于等于關(guān)系構(gòu)成偏序集，冪集P(A)和包含關(guān)系構(gòu)成偏序集. 哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關(guān)系圖 特點(diǎn)：每個結(jié)點(diǎn)沒有環(huán)，兩個連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前，具有覆蓋關(guān)系的兩個結(jié)點(diǎn)之間連邊,38,哈斯圖實(shí)例,例

12、4 ,39,A=a, b, c, d, e, f, g, h R=, ,IA,哈斯圖實(shí)例（續(xù)）,例5 已知偏序集 的哈斯圖如右圖所示, 試求出集合A和關(guān)系 R的表達(dá)式.,40,偏序集的特定元素,定義 設(shè)為偏序集, BA, yB.(1) 若x(xByx) 成立, 則稱 y 為 B 的最小元.(2) 若x(xBxy) 成立, 則稱 y 為 B 的最大元. (3) 若x (xBx y) 成立, 則稱 y 為B的極小元. (4) 若x (xBy x) 成立, 則稱 y 為B的極大元.,41,特殊元素的性質(zhì),對于有窮集，極小元和極大元必存在，可能存在 多個. 最小元和最大元不一定存在，如果存在一定惟一. 最小元一定是極小元；最大元一定是極大元. 孤立結(jié)點(diǎn)既是極小元，也是極大元.,42,定義 設(shè)為偏序集, BA, yA. (1) 若x(xBxy) 成立, 則稱 y 為B的上界. (2) 若x(xByx) 成立, 則稱 y 為B的下界. (3) 令Cy | y為B的上界, 則稱C的最小元為B的最小上界 或 上確界. (4) 令Dy | y為B的下界, 則稱D的最大元為B的最大下界 或 下確界.,偏序集的特定元素(續(xù)),43,下界、上界、下確界、上確界不一定存在 下界、上界存在不一定惟一 下確界、上確界如果存在，則惟