半序（偏序）關(guān)系課件.ppt

《半序（偏序）關(guān)系課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第六節(jié)半序（偏序）關(guān)系定義1設(shè)R為非空集合A上的關(guān)系。如果R是自反的、反對(duì)稱(chēng)的和傳遞的，則稱(chēng)R為A上的半序(偏序)關(guān)系，記為?。對(duì)一個(gè)偏序關(guān)系?，如果??，則記為x?y。注：1.集合A上的恒等關(guān)系IA是A上的偏序關(guān)系，但空關(guān)系和全域關(guān)系EA一般不是A上的偏序關(guān)系。2.實(shí)數(shù)域上的小于等于關(guān)系（大于等于關(guān)系），自然數(shù)域上的整除關(guān)系，集合的包含關(guān)系等都是偏序關(guān)系。一.偏序關(guān)系與偏序集2注：在具有偏序關(guān)系的集合A中任二元素x和y之間必有下列四種情形之一：x?y，y?x，x=y，x與y不可比。例設(shè)A={1,2,3}?是A上的整除關(guān)系，則：1?2,1?3,1＝1,2＝2,3＝3，2

2、和3不可比；(2)?是A上的大于等于關(guān)系，則:2?1,3?1,3?2,1＝1,2＝2，3＝3。定義2設(shè)R為非空集合A上的偏序關(guān)系，定義(1)?x,y?A,x?y當(dāng)且僅當(dāng)x?y且x≠y(2)?x,y?A,x與y可比當(dāng)且僅當(dāng)x?y或y?x3定義3設(shè)R為非空集合A上的偏序關(guān)系，如果?x,y?A,x與y都是可比的,則稱(chēng)R為A上的全序關(guān)系。例如大于等于關(guān)系（小于等于關(guān)系）是全序集，但整除關(guān)系一般不是全序集。定義4帶有某種指定的偏序關(guān)系?的集合A稱(chēng)為偏序集，記為.例如整數(shù)集Z和數(shù)的小于等于關(guān)系≤構(gòu)成偏序集;集合A的冪集P(A)和集合的包含關(guān)系?構(gòu)成偏序集.

3、定義5設(shè)為偏序集，?x,y?A,如果x?y且不存在z?A,使得x?z?y,則稱(chēng)y覆蓋x。例如A={1,2,4,6}上的整除關(guān)系，有2覆蓋1，4和6都覆蓋2，但4不覆蓋1,6不覆蓋4。4利用偏序關(guān)系的自反性、反對(duì)稱(chēng)性和傳遞性可簡(jiǎn)化偏序關(guān)系的關(guān)系圖，得到偏序集的哈斯圖。設(shè)有偏序集,其哈斯圖的畫(huà)法如下：(1)以A的元素作為頂點(diǎn)，適當(dāng)排列各頂點(diǎn)的順序,使得對(duì)?x,y?A，若x?y,則將x畫(huà)在y的下方。(2)對(duì)A中兩個(gè)不同元素x和y,如果y覆蓋x,則用一條線段連接x和y.例畫(huà)出偏序集<{1,2,3,…,9},R整除}和的哈斯圖.二.哈斯圖解：

4、它們的哈斯圖分別為圖A、圖B表示如下：847236951圖A{a,b}{a,b,c}{a}{b,c}{c}{a,c}?圖B5例已知偏序集的哈斯圖如下：求集合A和關(guān)系R的表達(dá)式。aedfhgbc解:A={a,b,c,d,e,f,g,h},R={,,,,,,,,}∪IA.6定義6設(shè)為偏序集，B?A.存在y?B,使得(1)?x(x?B→y?x)成立，則稱(chēng)y是B的最小元；(2)?x(x?B→x?y)成立，則稱(chēng)y是B的最大元；(3)?x(x?B∧x?y→x=y)成立，則稱(chēng)y是

5、B的極小元；(4)?x(x?B∧y?x→x=y)成立，則稱(chēng)y是B的極大元；注：極大(極小)元未必是最大(最小)元。極大(極小)元未必與B中任何元素都可比；(2)對(duì)有限集B，極大(極小)元一定存在，但最大(最小)元不一定存在;(3)最大(最小)元如果存在，必定是唯一的;而極大(極小)元一般不唯一。但如果B中只有一個(gè)極大(極小)元,則它一定是B的最大(最小)元。三.偏序集中的特殊元素7解：極大元：a,f,h;極小元:a,b,c,g;無(wú)最大元和最小元。例求上例中A的極大元、極小元、最大元、最小元，8定義7設(shè)為偏序集，B?A.(1)若存在y?A,使得?x(x?B→x?y)成立,

6、則稱(chēng)y為B的上界;(2)若存在y?A,使得?x(x?B→y?x)成立，則稱(chēng)y為B的下界；(3)令C＝{y

7、y為B的上界}，則稱(chēng)C的最小元為B的最小上界或上確界；(4)令D＝{y

8、y為B的下界}，則稱(chēng)D的最大元為B的最大下界或下確界.注：B的最大元(最小元)必定是B的上界(下界)，也是B的上確界(下確界)。2.B的上界和上確界都未必是B的最大元，因它們可能不在B中。同理，下界和下確也未必是B的最小元。3.B的上界、上確界、下界、下確界都可能不存在。但如果上確界(下確界)存在，則它是唯一的。9例考慮下圖中的偏序集.令B={b,c,d},試討論B的上(下)界，最大下界，最小上界等。

9、解析：(1)則B的下界和最大下界都不存在;(2)上界有d和f,最小上界為d.例設(shè)A={2,3,4,6,7,8,12,36,60},在半序集(A,

10、)上，半序關(guān)系

11、是整除關(guān)系。取B1={7,8},B2={8,12},B3={2,3},B4={2,4,12}，則Bi(i=1,2,3,4)集合上的上(下)界,上(下)確界，極大(下)元？作出哈斯圖！集合上界下界上確界下確界極大元極小元B1無(wú)無(wú)無(wú)無(wú)7,87,8B2無(wú)4,2無(wú)48,128,12B36,12,36,60無(wú)6無(wú)2,32,3B41