1離散數(shù)學DiscreteMathematics主講：陳哲云青島理工大學計算機工程學院2023.09第1頁第4章二元關系第2頁二元關系4.1二元關系基本概念(重點)4.2關系運算4.3關系性質(zhì)(重點)4.4關系閉包4.5等價關系和偏序關系(重點及難點)4.6函數(shù)基本概念第3頁偏序關系偏序關系Hasse圖（重點）主要元素（重點）拓撲排序第4頁偏序關系定義

偏序關系：設A上二元關系R,假如R是自反,

反對稱，傳遞，則稱R為偏序關系，記為“?”,<A,

?

>稱為偏序集。若<x，y>∈R，稱“x不大于等于y”，記作x

?

y。第5頁偏序關系例1

幾個常見偏序關系：(1)A上不大于等于關系，A={1,2,3,4,5,6}：Ｒ1={<x，y>｜x≤y，x，y∈A}(2)

A上整除關系，A={1,2,3,4,5,6}：Ｒ2＝{<x，y>｜x|y，x，y∈A}(3)P(A)上包括關系，A={1,2,3}：Ｒ3＝{<s1，s2>｜s1

s2，s1，s2∈P(A)}(4)任務集S={T1,T2,....,Tn}上關系R4={<Ti,Tj>|Ti=Tj或Ti必須在Tj之前完成}????第6頁偏序關系有關例1(4)一種舉例：如完成室內(nèi)閃光拍照任務，任務集T包括任務：1、打開鏡頭蓋；2、照相機調(diào)焦；3、打開閃光燈；4、按下快門按鈕。在T上定義關系R：<i,j>∈R假如i=j或者任務i必須在任務j之前完成。則R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}第7頁偏序關系定義

設R為非空集合A上偏序關系,x,y∈A,則x與y可比

x?y∨y?x定義設R為非空集合A上偏序關系,x,y∈A,則y蓋住x

x?y且不存在z∈A使得x?z?y第8頁Hasse（哈斯）圖例2

設A={2,3,6,12,24,36}，“?”是A上整除關系R，畫出其關系圖。

關系圖236123624236123624簡化關系圖——Hasse圖第9頁Hasse圖簡化關系圖——Hasse圖（哈斯圖）

(1)自反性：每個頂點都有自回路，省去。

(2)反對稱性：兩個頂點間只也許有一種箭頭，從小到大(或從低到高)安頓頂點，可省略箭頭。

(3)傳遞性：由于有<x，y>，<y，z>∈R，則<x，z>∈R，故只畫<x，y>，<y，z>對應邊，省略邊<x，z>。第10頁Hasse圖Hasse圖畫法——“層次”與“連線”(1)極小元放在第一層（最底層）。(2)若第n層已放好，則第n+1層元素滿足最少能蓋住第n層一種元素。（層次）(3)若y蓋住x，則x，y之間連線。（連線）注：哈斯圖體現(xiàn)了偏序集中元素間“大小”和“層次”關系。第11頁Hasse圖例3

畫出例1中各關系Hasse圖：

A＝{1,2,3,4,5,6,7,8,9},

B＝{a,b,c},S={1,2,3,4}

Ｒ1＝｛<x，y>｜x≤y，x，y∈A｝Ｒ2＝｛<x，y>｜x|y，x，y∈A｝Ｒ3＝｛<s1，s2>｜s1

s2，s1，s2∈P(B)｝R4={<Ti,Tj>|Ti=Tj或Ti必須在Tj之前完成且Ti,Tj∈S}

={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}第12頁Hasse圖Ｒ1Ｒ2——全序集第13頁Hasse圖1243Ｒ3Ｒ4第14頁全序關系定義

全序關系——任意兩個元素都可比

設<A,?>是一種偏序集，若對任意x,y∈A，總有x?y或y?x，二者必居其一，則稱“”為全序關系，或者線序關系。稱<A,≤>為全序集，或者線序集，或者鏈。第15頁偏序集中主要元素設偏序集<A,

?

>,B

A，b表達對應特殊元素，B極小元——B中沒有比b小元素

b∈B且x(x∈Bx?b)B最小元——B中所有元素都比b大b∈B且

x(x∈B→b?x)極大元和最大元類似定義。

注：上述元素都在B中尋找。第16頁偏序集中主要元素設偏序集<A,

?

>,B

A，b表達對應特殊元素，B上界—B中所有元素都比b小

b∈A且

x(x∈B→x?b)

B上確界

上確界——B上界最小元下界和下確界類似定義。

注：上述元素都在A中尋找。

第17頁偏序集中主要元素例4

設偏序集<A,?>，求A極小元、極大元、最小元、最大元。設B＝{b,c,d},求B下界、上界、下確界、上確界.解：極小元：a,b,c,g；極大元：a,f,h；沒有最小元與最大元.B下界和下確界都不存在；上界有d和f,上確界為d.

第18頁偏序集中主要元素性質(zhì)：

(1)對于有窮集，極小元和極大元一定存在，也許存在多種。(2)最小元和最大元不一定存在，假如存在一定惟一。(3)最小元一定是極小元；最大元一定是極大元。

(4)孤立結點既是極小元，也是極大元。(5)下界、上界、下確界、上確界不一定存在，存在不一定唯一。(6)下確界、上確界假如存在，則惟一。第19頁偏序集中主要元素練習

<A，?>Hasse圖如下所示，討論當B取對應集合時，其最大元，最小元，極大元，極小元，上界，下界，上確界，下確界。B1={a,b},B2={a,b,c},B3={a,b,c,d},B4={b,c,d,f},B5={a,c,f,i}

abcdefghi第20頁B極小元極大元最小元最大元{a,b}{a,b,c}a,ba,b無無a,bc無c{a,b,c,d}{b,c,d,f}{a,c,f,i}a,bc,d無bfbaia無fiabcdefghi第21頁無bB上界下界上確界下確界{a,b}{a,b,c}c,d,e,f,g,h,i無無c,e,f,h,i無c無{a,b,c,d}{b,c,d,f}{a,c,f,i}f,h,i無f無f,h,ibfiaiaabcdefghi第22頁小結偏序關系是“次序”關系，但不一定是“全序”關系。哈斯圖是偏序集簡化圖，通過“層次”關系來體現(xiàn)元素“大小”關系。偏序集中特殊元素能夠通過哈斯圖來尋找。第23頁作業(yè)1.下列圖中給出了偏序集<A,?>Hasse圖。