離散數(shù)學(xué)等價偏序函數(shù)

1、第六節(jié)第六節(jié) 等價關(guān)系與劃分等價關(guān)系與劃分主要內(nèi)容等價關(guān)系的定義與實(shí)例等價類及其性質(zhì)商集與集合的劃分 等價關(guān)系與劃分的一一對應(yīng) 一、等價關(guān)系的定義與實(shí)例一、等價關(guān)系的定義與實(shí)例定義定義7.15 設(shè)設(shè)R為非空集合上的關(guān)系為非空集合上的關(guān)系. 如果如果R是自反的、對是自反的、對稱的和傳遞的稱的和傳遞的, 則稱則稱R為為A上的等價關(guān)系上的等價關(guān)系. 設(shè)設(shè)R是一個等價是一個等價關(guān)系關(guān)系, 若若R, 稱稱x等價于等價于y, 記做記做xy.在我們?nèi)粘Ｉ詈蛯W(xué)習(xí)中，就有一些等價關(guān)系的例子，在我們?nèi)粘Ｉ詈蛯W(xué)習(xí)中，就有一些等價關(guān)系的例子，如：如： （1）在一群人的集合上年齡相等的關(guān)系是等價關(guān)系，）在一群人的集

2、合上年齡相等的關(guān)系是等價關(guān)系，而朋友關(guān)系不一定是等價關(guān)系，因?yàn)樗赡懿皇莻鬟f的。而朋友關(guān)系不一定是等價關(guān)系，因?yàn)樗赡懿皇莻鬟f的。 （2）命題公式間的邏輯等值關(guān)系是等價關(guān)系。）命題公式間的邏輯等值關(guān)系是等價關(guān)系。 （3）集合上的恒等關(guān)系是等價關(guān)系。）集合上的恒等關(guān)系是等價關(guān)系。 （4）在同一平面上直線之間的平行關(guān)系，三角形之間的）在同一平面上直線之間的平行關(guān)系，三角形之間的相似關(guān)系都是等價關(guān)系。相似關(guān)系都是等價關(guān)系。實(shí)例實(shí)例 設(shè)設(shè)A=1,2,8, 如下定義如下定義A上的關(guān)系上的關(guān)系R： R=| x,yAx y(mod 3)其中其中x y(mod 3)叫做叫做x與與y模模3相等相等, 即即x除以

3、除以3的余數(shù)與的余數(shù)與y除以除以3的余數(shù)相等的余數(shù)相等. 不難驗(yàn)證不難驗(yàn)證R為為A上的等價關(guān)系上的等價關(guān)系, 因?yà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), y z(mod 3), 則有則有x z(mod 3)圖6模3等價關(guān)系的關(guān)系圖圖6x二、等價類及其性質(zhì)二、等價類及其性質(zhì) 1 等價類等價類 定義定義7.16 設(shè)設(shè)R為非空集合為非空集合A上的等價關(guān)系上的等價關(guān)系, xA，令，令 xR = y | yAxRy稱稱xR為為x關(guān)于關(guān)于R的等價類的等價類, 簡稱為簡稱為x的等價類的等價類,

4、簡記為簡記為x或或.A=1, 2, , 8上模上模3等價關(guān)系的等價類：等價關(guān)系的等價類：1 = 4 = 7 = 1, 4, 72 = 5 = 8 = 2, 5, 83 = 6 = 3, 6即即A中所有和中所有和x有有R關(guān)系的元素的集合。關(guān)系的元素的集合。2等價類的性質(zhì)等價類的性質(zhì) 定理定理7.14 設(shè)設(shè)R是非空集合是非空集合A上的上的等價關(guān)系等價關(guān)系, 則則（1） x A, x是是A的非空子集的非空子集.（2） x,y A, 如果如果xRy, 則則 x = y.（3） x,y A, 如果如果x y, 則則 x與與y不交不交.（4）x | x A=A三、商集與集合的劃分三、商集與集合的劃分 1.

5、 定義定義7.17 設(shè)設(shè)R為非空集合為非空集合A上的等價關(guān)系上的等價關(guān)系, 以以R的所有等價類作為的所有等價類作為元素的集合稱為元素的集合稱為A關(guān)于關(guān)于R的商集的商集, 記做記做A/R, A/R = xR | xA 實(shí)例實(shí)例 設(shè)設(shè)A=1,2,8，A關(guān)于模關(guān)于模3等價關(guān)系等價關(guān)系R的商集為的商集為 A/R = 1,4,7, 2,5,8, 3,6A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1, 2, , 8 A/EA = 1,2,82集合的劃分集合的劃分 定義定義7.18 設(shè)設(shè)A為非空集合為非空集合, 若若A的子集族的子集族( P(A)滿足下面條件：滿足下面條

6、件：（1） （2） x y(x,y xyxy=)（3） = A則稱則稱是是A的一個劃分的一個劃分, 稱稱中的元素為中的元素為A的劃分塊的劃分塊 例例 設(shè)設(shè)Aa,b,c,d, 給定給定1, 2, 3, 4, 5, 6如下：如下： 1=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的劃分的劃分. 四、商集與劃分的對應(yīng)關(guān)系四、商集與劃分的對應(yīng)關(guān)系商集商集A/R就是就是A的一個劃分的一個劃分, 不同的商集對應(yīng)于不同不同的商集對應(yīng)于不同的劃分的劃分. 任給任給A的一個劃分的一

7、個劃分, 如下定義如下定義A上的關(guān)系上的關(guān)系R： R=| x,y Ax與與y在在的同一劃分塊中的同一劃分塊中 則則R為為A上的等價關(guān)系上的等價關(guān)系, 且該等價關(guān)系所確定的商集就且該等價關(guān)系所確定的商集就是是. A上的等價關(guān)系與上的等價關(guān)系與A的劃分是一一對應(yīng)的的劃分是一一對應(yīng)的. 例例 給出給出A1,2,3上所有的等價關(guān)系上所有的等價關(guān)系解解 如下圖如下圖, 先做出先做出A的所有的所有劃分劃分, 從左到右分別記作從左到右分別記作1,2,3,4,5.123圖7這些劃分與這些劃分與A上的上的等價關(guān)系等價關(guān)系之間的一一對應(yīng)是：之間的一一對應(yīng)是：4對應(yīng)于對應(yīng)于全域關(guān)系全域關(guān)系EA, 5對應(yīng)于對應(yīng)于恒等

8、關(guān)系恒等關(guān)系IA, 1,2和和3分別對應(yīng)于等價關(guān)系分別對應(yīng)于等價關(guān)系R1, R2和和R3. 其中其中 R1=,IAR2=,IAR3=,IA附錄：等價關(guān)系在計(jì)算機(jī)科學(xué)中的應(yīng)用附錄：等價關(guān)系在計(jì)算機(jī)科學(xué)中的應(yīng)用 關(guān)系概念對計(jì)算機(jī)科學(xué)的理論和應(yīng)用都非常重要，關(guān)系概念對計(jì)算機(jī)科學(xué)的理論和應(yīng)用都非常重要，復(fù)合的數(shù)據(jù)結(jié)構(gòu)、如陳列表、樹等，用來表示數(shù)據(jù)的集復(fù)合的數(shù)據(jù)結(jié)構(gòu)、如陳列表、樹等，用來表示數(shù)據(jù)的集合，這些數(shù)據(jù)是由元素間的關(guān)系聯(lián)系的。關(guān)系是數(shù)學(xué)模合，這些數(shù)據(jù)是由元素間的關(guān)系聯(lián)系的。關(guān)系是數(shù)學(xué)模型的一部分，它常常在數(shù)據(jù)結(jié)構(gòu)內(nèi)隱含地體現(xiàn)出來，數(shù)型的一部分，它常常在數(shù)據(jù)結(jié)構(gòu)內(nèi)隱含地體現(xiàn)出來，數(shù)值應(yīng)用、信息檢索

9、、網(wǎng)絡(luò)問題等就是關(guān)系的應(yīng)用領(lǐng)域，值應(yīng)用、信息檢索、網(wǎng)絡(luò)問題等就是關(guān)系的應(yīng)用領(lǐng)域，因而關(guān)系的運(yùn)算和處理是重要的。關(guān)系在包括程序結(jié)構(gòu)因而關(guān)系的運(yùn)算和處理是重要的。關(guān)系在包括程序結(jié)構(gòu)和算法分析的理論方面也有重要的作用。和算法分析的理論方面也有重要的作用。例：在信息檢索系統(tǒng)中，所有生物的集合例：在信息檢索系統(tǒng)中，所有生物的集合X可分割成可分割成P，A，P表示所有植物集合，表示所有植物集合，A表示所有動物集合；表示所有動物集合；也可構(gòu)成也可構(gòu)成E，F(xiàn)，E表示史前生物，表示史前生物，F(xiàn)表示史后生物，表示史后生物，其交叉劃分其交叉劃分Q=P E,P F,A E,A FE,P F,A E,A F第七節(jié) 偏序關(guān)

10、系一、偏序關(guān)系一、偏序關(guān)系 1定義定義7.19 偏序關(guān)系偏序關(guān)系：非空集合：非空集合A上的上的自反自反、反對稱反對稱和和傳遞傳遞的關(guān)系，記作的關(guān)系，記作 .設(shè)設(shè) 為偏序關(guān)系為偏序關(guān)系, 如果如果 , 則記作則記作x y, 讀作讀作x“小于或等于小于或等于”y. 2. 實(shí)例實(shí)例集合集合A上的恒等關(guān)系上的恒等關(guān)系IA是是A上的偏序關(guān)系上的偏序關(guān)系. 小于或等于關(guān)系小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系合上的偏序關(guān)系. 3相關(guān)概念相關(guān)概念定義定義7.20 設(shè)設(shè)R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, x,yA, x與與y可比可比 x yy

11、x. 任取兩個元素任取兩個元素x和和y, 可能有下述幾種情況發(fā)生：可能有下述幾種情況發(fā)生： x y(或或y x), xy, x與與y不是可比的不是可比的.定義定義7.21 R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, x,yA, x與與y都是可比的，則稱都是可比的，則稱R為為全序（或線序）全序（或線序）實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系 定義定義7.22 x,yA, 如果如果x y且不存在且不存在zA使得使得x z y, 則稱則稱y覆蓋覆蓋x.例如例如1,2,4,6集合上的整除關(guān)

12、系集合上的整除關(guān)系2覆蓋覆蓋1, 4和和6覆蓋覆蓋2. 但但4不覆蓋不覆蓋1. 二、偏序集與哈斯圖二、偏序集與哈斯圖1偏序集偏序集定義定義7.23 集合集合A和和A上的偏序關(guān)系上的偏序關(guān)系 一起叫做偏序集一起叫做偏序集, 記記作作.實(shí)例：實(shí)例：整數(shù)集合整數(shù)集合Z和數(shù)的小于或等于關(guān)系和數(shù)的小于或等于關(guān)系構(gòu)成偏序集構(gòu)成偏序集集合集合A的冪集的冪集P(A)和包含關(guān)系和包含關(guān)系R 構(gòu)成偏序集構(gòu)成偏序集. 2哈斯圖哈斯圖利用偏序關(guān)系的自反、反對稱、傳遞性進(jìn)行簡化的關(guān)利用偏序關(guān)系的自反、反對稱、傳遞性進(jìn)行簡化的關(guān)系圖系圖特點(diǎn)：特點(diǎn)：每個結(jié)點(diǎn)沒有環(huán)每個結(jié)點(diǎn)沒有環(huán)兩個連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高兩個

13、連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高 低表示，位置低的元素的順序在前低表示，位置低的元素的順序在前具有覆蓋關(guān)系的兩個結(jié)點(diǎn)之間連邊具有覆蓋關(guān)系的兩個結(jié)點(diǎn)之間連邊三、偏序集中的特殊元素.1. 最小元、最大元、極小元、極大元最小元、最大元、極小元、極大元定義7.24 設(shè)為偏序集, BA, yB.（1）若x(xByx)成立, 則稱y為B的最小元.（2）若x(xBxy)成立, 則稱y為B的最大元. （3）若x(xBxyx=y)成立, 則稱y為B的極小元. （4）若x(xByxx=y)成立, 則稱y為B的極大元. 性質(zhì)：對于有窮集，極小元和極大元一定存在，還可能存在多個. 最小元和最大元不一定存在，如果

14、存在一定惟一.最小元一定是極小元；最大元一定是極大元. 孤立結(jié)點(diǎn)既是極小元，也是極大元.2下界、上界、下確界（最大下界）、上確界（最下界、上界、下確界（最大下界）、上確界（最小上界）小上界）定義定義7.25 設(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的最大下界或下確界.性質(zhì)：性質(zhì)：下界、上界、下確界、上確界不一定存在 下界、上界存在不一定惟一 下確界、上確界如果存在，則惟一 集合的最小元就

15、是它的下確界，最大元就是它的 上確界；反之不對.12 84610例例 畫出畫出和和的哈的哈斯圖，并指出其中的特殊元。斯圖，并指出其中的特殊元。解：解： (1) 的哈斯圖如下：的哈斯圖如下：92513711由圖可知由圖可知1為最小元，沒有最大元；為最小元，沒有最大元；7,8,9,10,11, 12均為極大元，極小元為均為極大元，極小元為1；1為為1,2,12的下界，也是下確界；的下界，也是下確界；1,2,12中沒有上確界或上界。中沒有上確界或上界。(2) 的哈斯圖如下：的哈斯圖如下：P(a,b,c)= ,a,b,c,a,b,a,c,b,c,a,b,ca,b,ca,ca,bb,cca b由圖可知：

16、由圖可知： 為為P(a,b,c)的最小元，的最小元，a,b,c為它的為它的最大元；最大元；同時同時 ，a,b,c也分別為它們也分別為它們的極小元和極大元、下確界和上確界。的極小元和極大元、下確界和上確界。abcde例例 已知偏序集已知偏序集的哈斯圖如下：的哈斯圖如下：hgf 試寫出對應(yīng)的試寫出對應(yīng)的A和和A上的偏序關(guān)系上的偏序關(guān)系R ，, , , , ,解：解： A = a,b,c,d,e,f, g,hR = ,abcdehgf, ,例 設(shè)偏序集如下圖所示，求A的極小元、最小元、極大元、最大元. 設(shè)Bb,c,d, 求B的下界、上界、下確界、上確界. 圖10 解 極小元：a, b, c, g；

17、極大元：a, f, h；沒有最小元與最大元. B的下界和最大下界都不存在, 上界有d和f, 最小上界為d. 例：畫出集合例：畫出集合S=1,2,3,4,5,6在偏序關(guān)系在偏序關(guān)系“整除整除”下下的哈斯圖，并討論：的哈斯圖，并討論：寫出寫出1,2,3,4,5,6的極大（小）元，最大（小）元，的極大（?。┰?，最大（小）元，分別寫出分別寫出2,3,6及及2,3,5的上界，下界，上確界，的上界，下界，上確界，a) 下確界。下確界。解：設(shè)解：設(shè)為整除關(guān)系：為整除關(guān)系：“”=,在偏序集在偏序集中，中，COV（S）=,COV（S）=,123546極大元：極大元：4，5，6極小元：極小元：1最大元：沒有最大元

18、：沒有 最小元：最小元：12,3,6的上（確）界：的上（確）界：6 下（確）界：下（確）界：12,3,5的上（確的上（確)界界:無無 下（確）界：下（確）界：1序關(guān)系在項(xiàng)目管理中的應(yīng)用（實(shí)例：調(diào)度問題）序關(guān)系在項(xiàng)目管理中的應(yīng)用（實(shí)例：調(diào)度問題）假設(shè)一個項(xiàng)目由假設(shè)一個項(xiàng)目由20個任務(wù)構(gòu)成，某些任務(wù)只能在其他個任務(wù)構(gòu)成，某些任務(wù)只能在其他任務(wù)結(jié)束之后完成，怎么找到關(guān)于這些項(xiàng)目的順序？任務(wù)結(jié)束之后完成，怎么找到關(guān)于這些項(xiàng)目的順序？如果只有一臺機(jī)器，而且每項(xiàng)任務(wù)的截止時間沒有限如果只有一臺機(jī)器，而且每項(xiàng)任務(wù)的截止時間沒有限制，則對這個問題可用拓?fù)渑判騺斫鉀Q。制，則對這個問題可用拓?fù)渑判騺斫鉀Q。所謂拓?fù)?/p>

19、排序：將原來的偏序集所謂拓?fù)渑判颍簩⒃瓉淼钠蚣瘮U(kuò)張成一個對擴(kuò)張成一個對應(yīng)的全序集應(yīng)的全序集。所以為了構(gòu)造該問題的求解模型，我們首先建立任務(wù)所以為了構(gòu)造該問題的求解模型，我們首先建立任務(wù)集合上的部分序集，使得集合上的部分序集，使得ab當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a和和b是任務(wù)且是任務(wù)且直到直到a結(jié)束后結(jié)束后b才能開始。才能開始。例：例：P129 圖圖7.9 7.10第八節(jié)第八節(jié) 習(xí)題課習(xí)題課 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)系的表示法：關(guān)系表達(dá)式、關(guān)系矩

20、陣、關(guān)系圖關(guān)系的運(yùn)算：定義域、值域、域、逆、合成、限制、關(guān)系的運(yùn)算：定義域、值域、域、逆、合成、限制、像、冪關(guān)系運(yùn)算的性質(zhì)像、冪關(guān)系運(yùn)算的性質(zhì)A上關(guān)系的自反、反自反、對稱、反對稱、傳遞的性質(zhì)上關(guān)系的自反、反自反、對稱、反對稱、傳遞的性質(zhì)A上關(guān)系的自反、對稱、傳遞閉包上關(guān)系的自反、對稱、傳遞閉包A上的等價關(guān)系、等價類、商集與上的等價關(guān)系、等價類、商集與A的劃分的劃分A上的偏序關(guān)系與偏序集上的偏序關(guān)系與偏序集2要求：要求：基本概念要清楚基本概念要清楚熟練掌握關(guān)系的三種表示法熟練掌握關(guān)系的三種表示法 能夠判定關(guān)系的性質(zhì)（等價關(guān)系或偏序關(guān)系）能夠判定關(guān)系的性質(zhì)（等價關(guān)系或偏序關(guān)系）掌握含有關(guān)系運(yùn)算的集

21、合等式掌握含有關(guān)系運(yùn)算的集合等式掌握等價關(guān)系、等價類、商集、劃分、哈斯圖、偏序掌握等價關(guān)系、等價類、商集、劃分、哈斯圖、偏序集等概念集等概念 以下基本運(yùn)算要熟練以下基本運(yùn)算要熟練A B, dom R, ranR, fldR, R 1, R S , Rn , r( R), s( R), t( R)求等價類和商集求等價類和商集A/R給定給定A的劃分的劃分 ，求出，求出 所對應(yīng)的等價關(guān)系所對應(yīng)的等價關(guān)系求偏序集中的極大元、極小元、最大元、最小元、上求偏序集中的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界界、下界、上確界、下確界 掌握基本的證明方法掌握基本的證明方法 證明涉及關(guān)系運(yùn)算的集

22、合等式證明涉及關(guān)系運(yùn)算的集合等式 證明關(guān)系的性質(zhì)、證明關(guān)系是等價關(guān)系或偏序關(guān)證明關(guān)系的性質(zhì)、證明關(guān)系是等價關(guān)系或偏序關(guān)系系2設(shè)設(shè)A=1,2,3,4，在，在A A上定義二元關(guān)系上定義二元關(guān)系R：, R x+y = u+v，求求R導(dǎo)出的劃分導(dǎo)出的劃分. 解解 A A=, , , , , , , , , , , , , , , 根據(jù)有序?qū)Ω鶕?jù)有序?qū)χ械闹械膞+y=2,3,4,5,6,7,8將將A劃分成等劃分成等價類：價類： A/R=, , , , , , , , , , , , , , 4設(shè)偏序集設(shè)偏序集 的哈斯圖如圖所示的哈斯圖如圖所示. （1）寫出）寫出A和和R的集合表達(dá)式的集合表達(dá)式 （2）求

23、該偏序集中的極大元、極小元、最大元）求該偏序集中的極大元、極小元、最大元最小元最小元 （1）A = a, b, c, d, e R = , , , , , , IA （2）極大元和最大元是a, 極小元是d, e；沒有最小元. 主要內(nèi)容主要內(nèi)容函數(shù)的定義函數(shù)的定義函數(shù)的性質(zhì)函數(shù)的性質(zhì)函數(shù)的逆函數(shù)的逆函數(shù)的合成函數(shù)的合成與后面各章的關(guān)系與后面各章的關(guān)系是代數(shù)系統(tǒng)的基礎(chǔ)是代數(shù)系統(tǒng)的基礎(chǔ) 第八章第八章 函數(shù)函數(shù)注：因時間關(guān)系只講函數(shù)定義和性質(zhì)。注：因時間關(guān)系只講函數(shù)定義和性質(zhì)。一、函數(shù)的定義與相關(guān)概念一、函數(shù)的定義與相關(guān)概念1函數(shù)定義函數(shù)定義 定義定義8.1 設(shè)設(shè)F為為二元關(guān)系二元關(guān)系, 若若 xdo

24、mF都存在都存在唯一唯一的的yranF使使xFy成立成立, 則稱則稱F為函數(shù)為函數(shù) 對于函數(shù)對于函數(shù)F, 如果有如果有xFy, 則記作則記作y=F(x), 并稱并稱y為為F在在x的值的值. 例例 F1=, F2=, F1是函數(shù)是函數(shù), F2不是函數(shù)不是函數(shù)二函數(shù)的性質(zhì)二函數(shù)的性質(zhì) 定義定義8.6 設(shè)設(shè)f：AB,（1）若）若ranf=B, 則稱則稱f：AB是滿射的是滿射的.（2）若）若 yranf都存在唯一的都存在唯一的xA使得使得f(x)=y, 則稱則稱f：AB是單射的是單射的.（3）若）若f：AB既是滿射又是單射的既是滿射又是單射的, 則稱則稱 f：AB是雙射的是雙射的例例 判斷下面函數(shù)是否為單射判斷