離散數(shù)學(xué)3.12序關(guān)系

1、1,離散數(shù)學(xué)(Discrete Mathematics),張捷,第三章 集合與關(guān)系（Sets and Relations),,3.6 關(guān)系的閉包運(yùn)算(Closure Operations)3.7 集合的劃分與覆蓋(Partition & Cover of Sets) 3.8 等價(jià)關(guān)系(Equivalent Relations) 3.9 相容關(guān)系(Compatibility　Relations) 3.10 序關(guān)系(Or

2、dered Relations),3.1 集合及其運(yùn)算(Sets & Operations with sets) 3.2 序偶與笛卡爾積(Ordered Pairs & Cartesian Product)3.3 關(guān)系 (Relations) 3.4 關(guān)系的性質(zhì)(The Propeties of Relations) 3.5 復(fù)合關(guān)系與逆關(guān)系(Compound Relations & Inverse

3、 Relations),3.10 序關(guān)系(Ordered Relations)3.10.1 偏序關(guān)系的定義(Partially Ordered Relations)3.10.2 偏序關(guān)系的哈斯圖(The Hasse Diagram of Posets )3.10.3 偏序集中特殊位置的元素3.10.4 幾種特殊的偏序集,第三章 集合與關(guān)系(Sets & Relations),3.10

4、 偏序關(guān)系 3.10.1 偏序關(guān)系的定義(Partially Ordered Relations)定義3.10.1 集合A上的關(guān)系ρ,如果它是自反的,反對(duì)稱的且可傳遞的,則稱ρ是A上的偏序關(guān)系.記作“≤”,序偶 稱為偏序集(partially ordered set or poset for short ).,例1 實(shí)數(shù)集R上的“≤”關(guān)系顯然是一個(gè)偏序關(guān)系。,證明 對(duì)于任意 ，有 ，所以“ ”是自反

5、的。,對(duì)任意 ，若 且 ，則 所以“ ” 是反對(duì)稱的。,例2 全集合U的冪集2U上的“ ”關(guān)系也是一個(gè)偏序關(guān)系。,對(duì)任意 ，若 ， ，則 所以“ ”是可傳遞的。,例3 設(shè)A={1,2,3,4,6,8,12}，定義A上的整除關(guān)系 如下：則ρ是A上的偏序關(guān)系。,例4 自然數(shù)集上的整除關(guān)系是偏序關(guān)系。,3

6、.10.2 偏序關(guān)系的哈斯圖(The Hasse Diagram of Posets ),a≤c,c≤b，則稱元素b蓋住元素a，并且記,稱 為偏序集 中的蓋住關(guān)系。顯然 。,定義3.10.2 在偏序集中 ，若元素 ，a≠b，a≤b，且在集A中不存在任何其它元素c，使得,3.10.2 偏序關(guān)系的哈斯圖(The Hasse Diagram

7、 of Posets ),,例5 設(shè)U={a,b,c}，則“ ”關(guān)系是2U上的偏序關(guān)系，,偏序關(guān)系“ ”的哈斯圖如下：,例6 設(shè)A={2,3,6,12,24,36}，A上的整除關(guān)系是一偏序關(guān)系，其哈斯圖如下：,3.10.3 偏序集中特殊位置的元素,既然偏序集的元素之間 具有分明的層次關(guān)系， 則其中必有一些處于特殊位置的元素。,定義3-10.3（極大元，極小元，最大元，最小元）,設(shè),是一個(gè)偏序集，且B,A，如果存

8、在元素b∈B,使得,B滿足x,b且x,（2）不存在x,b，則稱b為B的極小元；,,,,,,,,｛a,b,c｝ ｛a,b,c｝,{a},例7. 設(shè)A＝｛a,b,c｝，對(duì)于偏序集,,，,例8 在例6中取B={6，12}，C={2，3，6}，則,ABC,24，36126,2，362，3,無126,無6無,,,,,,最大（?。┰蜆O大（?。┰男再|(zhì)：,（1）最大（?。┰厥菢O大（小）元

9、，反之不然。,（2）最大（?。┰灰欢ù嬖?，若存在，則是唯一的。,（3）極大（小）元不唯一，當(dāng)B＝A時(shí)，偏序集 的,,極大元即是其哈斯圖中最頂層元素，其極小元是哈斯圖中最底層元素，不同的極大（?。┰g不可比，它們處在哈斯圖中的同一個(gè)層次。,證：,,定義3.10.4（上界，下界，上確界，下確界),,,,,,,,,則稱a為B的最小上界（上確界），記作LUB(B)；,則稱a為B的最大下界（下確界），記作GLB(B)。,,

10、,,,,,,,｛a,b,c｝ ｛a,b,c｝,{a},,例9. 設(shè)A＝｛a,b,c｝，對(duì)于偏序集,,，,{{a},,{c}},{a,b,c},,{a,b,c},{{a},{a,b}},{a,b},{a,b,c},{a,b},{a},,例10 在例6中取B={12,24,36}，C={2，3，6}，則,ABC,無無6,12,24,36,無12,6,3,2無,無無6,無12無

11、,A={2,3,6,12,24,36},,,,,,,,,,,,通過以上例子可以看出界有以下性質(zhì)：,（1）一個(gè)集合可能沒有上界或下界，若有，則不一定唯一，并且它們可能在B中，也可能在B外；（2）一個(gè)集合若有上下確界，必定是唯一的，并且若是B的最大（?。┰?，則它必是B的上（下）確界。,3.10.4 兩種特殊的偏序集1.全序設(shè)“≤”是集合A上的一個(gè)偏序關(guān)系，對(duì)于任意a,b∈A，當(dāng)a≠b時(shí)，a≤b和b≤a至多一個(gè)成立，這意味著允許a≤b

12、和b≤a可以都不成立。,例如 在例3的整除關(guān)系中，3≤4，4≤3均不成立。,在例4的包含關(guān)系中,定義3.10.5 設(shè)≤是集合A上的一個(gè)偏序，若對(duì)于任意元素a,b∈A，必有a≤b或b≤a，則稱它為A上的一個(gè)全序。,例如 實(shí)數(shù)集R上的數(shù)之間的小于或等于關(guān)系“≤”就是R上的一個(gè)全序，,正整數(shù)集N上的小于或等于關(guān)系“≤”也是N上的一個(gè)全序。,N上的整除關(guān)系就僅是一個(gè)偏序而不是全序。,例11 設(shè)A={1,2,8,24,48}，則A上的整除

13、關(guān)系是A上的偏序，并且也是一個(gè)全序.,3.10.4 兩種特殊的偏序集 2.良序定義3.10.6 設(shè)“≤”是集合A上的一個(gè)偏序關(guān)系，若A的任意子集B均有最小元素,則稱≤為A上的一個(gè)良序。 稱為良序集。,例如 (1)正整數(shù)集N上的小于等于關(guān)系“≤”是良序關(guān)系。,(2)In ={1,2,…,n}上的小于等于關(guān)系“≤”是良序關(guān)系。,(3)整數(shù)集Z和實(shí)數(shù)集R上的小于等于關(guān)系“≤”不是良序關(guān)系 (因?yàn)閆或R本身無最小元) 。,

14、定理3.10.1 每一個(gè)良序集一定是全序集.,注意: 定理3.10.1的逆不成立 。,例如: 整數(shù)集Z和實(shí)數(shù)集R上的小于等于關(guān)系“≤”是全序關(guān)系,但不是良序關(guān)系 。,,證: 設(shè) 為良序集,則對(duì)任意的a ,b∈A,{a,b}構(gòu)成A的子集,因此它必有最小元素,最小元素非a則b,故一定有a≤b或b≤a.所以 是一個(gè)全序集.,但是,對(duì)于有限的全序集,定理3.10.1的逆也成立.即有,定理3.10.2 每一個(gè)有限

15、的全序集一定是良序集.,綜合練習(xí) 1.對(duì)下述論斷判斷正確與否，在相應(yīng)括號(hào)中鍵入“Y”或“N”。（1）設(shè)A={2,3,6,12,24,36}，A上的整除關(guān)系是一偏序關(guān)系， 用“≤”表示。,(b)“≤”={〈2,2〉,〈2,6〉,〈3,3〉, 〈3,6〉,〈6,6〉,〈6,12〉,〈12,12〉, 〈12,24〉,〈24,24〉,〈36,36〉} （ ）,N,

16、Y,（2）集合A={3,9,27,54}上的整除關(guān)系是A上的全序 （ ）,Y,（a）該偏序關(guān)系的哈斯圖是 （ ）,解 滿足上述條件的最小基數(shù)的關(guān)系 ρ2 ={〈2,3〉，〈2,4〉，〈4,3〉｝,一般說，給定ρ1和ρ1·ρ2，不能唯一的確定ρ2 。 例如ρ2=｛〈2,3〉，〈2,4〉，〈4,3〉，〈0

17、,0〉，〈3,3〉｝也可以.,2．給定ρ1=｛〈0,1〉,〈1,2〉,〈3,4〉}, ρ1·ρ2 =｛〈1,3〉，〈1,4〉，〈3,3〉｝, 求滿足上述條件的一個(gè)基數(shù)最小的關(guān)系 ρ2. 一般地說,若給定ρ1和ρ1·ρ2 ，ρ2 能被唯一地確定嗎? 基數(shù)最小的ρ2能被唯一確定嗎 ？,,,,給定ρ1和ρ1·ρ2，也不能唯一的確定出最小基數(shù)的ρ2。,則ρ2=｛〈2,3〉，〈2,4〉，〈4,3〉｝或　ρ2=｛

18、〈2,3〉，〈2,4〉，〈3,3〉｝都可以。,例如ρ1=｛〈0,1〉，〈1,2〉，〈3,3〉，〈3,4〉｝，　　　 ρ1·ρ2=｛〈1,3〉，〈1,4〉，〈3,3〉｝，,4,,,,3,,3．下列關(guān)系哪一個(gè)是自反的、對(duì)稱的、反對(duì)稱的或可傳　　遞的？　　〈1〉當(dāng)且僅當(dāng)n1n2<8(n1,n2∈N)時(shí),有n1ρn2　　〈2〉當(dāng)且僅當(dāng)r1≤ | r2| (r1,r2∈R)時(shí),有r1ρr2,解〈1〉ρ不是自反的，如4∈N，但

19、4·4=16>8。,ρ是對(duì)稱的，因?yàn)?對(duì)于任意的 n1, n2∈N，若有 n1n2< 8，則 n2n1 = n1n2 < 8。,ρ不是可傳遞的，例如，3·28。,ρ不是反對(duì)稱的，例，2·3<8，3·2<8，但3≠2.,〈2〉ρ是自反的，因?yàn)閷?duì)任意的r∈R，有r ≤|r|。,ρ不是對(duì)稱的，如-1≤|3|，但3>|-1|。,ρ不是可傳遞的，100≤|-101|， -

20、101≤|2|，但100>|2|,ρ不是反對(duì)稱的，如-3≤|2|，2≤|-3|，但-3≠2。,4.設(shè)ρ1和ρ2是集合A上的任意兩個(gè)關(guān)系,判斷下列 命題是否正確,并說明理由. 〈1〉若ρ1和ρ2是自反的，則ρ1·ρ2也是自反的； 〈2〉若ρ1和ρ2是非自反的，則ρ1·ρ2也是非自反的；,證明 〈1〉正確。,〈2〉否。,所以對(duì)任意的a ∈A , 有 a〈ρ1·ρ2〉a ，因此ρ1

21、·ρ2也是自反的。,例如，設(shè)集合A=｛a,b｝. ρ1={〈a ,b〉, 〈b ,a〉} ,ρ2 ={〈a, b〉 ,〈b,a〉},顯然ρ1和ρ2都是非自反的，但ρ1·ρ2自反。,〈3〉若ρ1和ρ2是對(duì)稱的，則ρ1·ρ2也是對(duì)稱的； 〈4〉若ρ1和ρ2是反對(duì)稱的，則ρ1·ρ2也是反對(duì)稱的； 〈5〉若ρ1和ρ2是可傳遞的，則ρ1·ρ2也是可傳遞的；,例如 ，設(shè)集合A=｛

22、1,2,3｝， ρ1=｛〈1,2〉，〈2, 1〉｝ ,ρ2=｛〈1,3〉，〈3,1〉｝， 顯然 ρ1和ρ2都是對(duì)稱的，,例如設(shè) A =｛1,2,3｝,ρ1={〈1,2〉,〈3，3〉｝, ρ2 ={〈2,3〉,〈3，1〉｝顯然ρ1和ρ2都是反對(duì)稱的，,例如設(shè) A =｛1,2,3},ρ1={〈1,2〉,〈2,3〉,〈1,3〉}, ρ2 =｛〈2，3〉，〈3，1〉，〈

23、2，1〉｝，　　　顯然ρ1和ρ2都可傳遞的.,但ρ1·ρ2=｛〈2,3〉｝不是對(duì)稱的。,但ρ1·ρ2={〈1,3〉,〈2,1〉,〈1,1〉} 不是可傳遞的。,但ρ1·ρ2 =｛〈1, 3〉，〈3,1〉｝不是反對(duì)稱的。,證明〈3〉否 .,〈4〉 否 .,〈5〉否 .,5 .有人說，集合A上的關(guān)系　 ，如果是對(duì)稱的且可　　傳遞，則它也是自反的。其理由是，從,,對(duì)稱性,,,傳遞性,例 設(shè) A＝｛1,2，3

24、｝ρ＝｛〈1,2〉,〈2,1〉,〈1,1〉,〈2,2〉},6． 設(shè)ρ1是集合A上的一個(gè)關(guān)系，ρ2=｛〈a,b〉| 存在 c， 　　　使〈a,c〉∈ρ1且〈c,b〉∈ρ1｝，試證明： 若 ρ1是一個(gè)等價(jià)關(guān)系，則ρ2也是一個(gè)等價(jià)關(guān)系。,證明 因?yàn)棣?是自反的，所以對(duì)于任意的 a ∈A　, 有〈a, a〉∈ρ1,，

25、　由〈a,a〉∈ρ1 ,〈a,a〉 ∈ρ1,由ρ1的對(duì)稱性,又有〈b, c〉∈ρ1 ,且〈c, a〉∈ρ1 ,,因而有〈b, a〉∈ρ2 ,故ρ2 是對(duì)稱的。,對(duì)于任意的a, b∈A,若〈a, b〉∈ρ2 ,,則必有元素c∈A，使得〈a, c〉∈ρ1, 且〈c, b〉∈ρ1 ,,因此有 〈a,a〉∈ρ2 ,ρ2 是自反的。,,對(duì)于任意的a, b, c∈A , 若〈a, b〉∈ρ2 , 〈b, c〉 ∈ρ2,,則必有元素 d , e

26、∈ A , 使得 〈a, d〉∈ρ1 〈d, b〉∈ρ1 　〈b, e〉∈ρ1 〈e, c〉 ∈ρ1,由ρ1的可傳遞性，又有〈a, b〉∈ρ1, 〈b, c〉 ∈ρ1,于是有〈a, c〉∈ρ2,故ρ2 是可傳遞的。,由上證得ρ2 是一個(gè)等價(jià)關(guān)系。,證法二,設(shè)〈a, b〉∈ρ1,,由ρ1的自反性，又有〈a, a〉∈ρ1,,反之，設(shè)〈a, b〉∈ρ2 ，,則必存在c∈A,使得〈a, c〉∈ρ1,〈c, b〉 ∈ρ

27、1,,由上可知ρ2=ρ1，因此ρ2是等價(jià)關(guān)系。,由〈a, a〉∈ρ1,〈a, b〉 ∈ρ1, 于是有〈a, b〉∈ρ2 , 因此ρ1 ρ2 。,而由ρ1的可傳遞性，又有〈a, b〉∈ρ1,因此ρ2 ρ1 .,第三章 集合與關(guān)系(Sets & Relations),小結(jié)：本節(jié)介紹了偏序關(guān)系及幾種特殊的偏序。重點(diǎn)掌握偏序的概念，哈斯圖的畫法及偏序關(guān)系中特異位置元素。,作業(yè)：P145 (1),(6),