《离散数学课件》7偏序关系.ppt

《《离散数学课件》7偏序关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上节课内容等价关系等价关系等价类定义性质商集、集合的划分等价关系和划分的对应12/497.6偏序关系和格7.6.1偏序关系、偏序集7.6.2哈斯（Hasse）图7.6.3链、反链、全序集7.6.4极大元、极小元、最大元、最小元7.6.5上界、下界、最小上界、最大下界7.6.6格3/49一、偏序关系例在实数集R上定义二元关系S，对于任意的x,y∊R，(x，y)∊S当且仅当x≤y。R有自反性、反对称性、传递性.4/49偏序关系、偏序集定义1设A是一个非空集合，R是A上的一个二元关系，若R有自反性、反对称性、传递性，则称R是A上的一个偏序关系，记作≼

2、。并称(A，≼)是一个偏序集。如果（x,y)∈≼,则记作x≼y,读作x“小于或等于”y。例1A={1,2,3,4}R={(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(1,4),(2,4)}R是A上一个偏序关系。5/49例2(p109)设Z+={n∊Z│n>0}，即Z+是正整数的集合。在Z+上定义一个二元关系R如下:对于任意的x,y∊Z+，(x,y)∊R当且仅当x

3、y。证明(Z+，R)是偏序集6/49例2(p109)证明(Z+，R)是偏序集（1）对于任意的x∊Z+,显然有x

4、x,所以(x,x)∊R,即R是自反的。（2）

5、对于任意的x,y∊Z+,若(x,y)∊R,且(y,x)∊R，则x

6、y,即存在n∊Z+,y=nx且y

7、x,即存在m∊Z+,x=my，所以x=mnx，而n,m∊Z+，所以只有n=m=1，即x=y时才有(x,y)∊R,且(y,x)∊R，即R有反对称性。（3）对于任意的x,y,z∊Z+,若(x,y)∊R,且(y,z)∊R；则由(x,y)∊R,得x

8、y,即∃n0∊Z+，使得y=xn0;再由(y,x)∊R,得y

9、x,即∃m0∊Z+，使得z=m0y。所以z=m0n0x，即x

10、z，所以(x,z)∊R,即R有传递性。综上所述,R是Z+上偏序关系，即(Z+，R)是

11、偏序集。对于任意的x,y∊Z+，(x,y)∊R当且仅当x

12、y。7/49例3设A是任意一个集合，ρ(A)是A的幂集合，在ρ(A)上建立一个二元关系R:对于任意的x,y∊ρ(A)，(x,y)∊R当且仅当x⊆y。不难证明(ρ(A)，R)也是一个偏序集。8/49例在实数集R上定义二元关系S，对于任意的x，y∊R，(x，y)∊S当且仅当x≤y。可以证明S是R上的一个偏序关系。在实数集R上定义二元关系S’，对于任意的x，y∊R，(x，y)∊S’当且仅当x≥y。可以证明S’是R上的一个偏序关系。集合A上的恒等关系IA是A上的偏序关系.9/49关于记号≺对于一

13、个偏序关系，往往用记号“≺”来表示。若(a，b)∊≺，记为a≺b，读做“a小于等于b”。一个偏序集，通常用符号(A，≺)来表示。10/49注意偏序关系“a小于等于b”，并不意味着平时意义上的a小于等于b。一个集合上可以定义不同的偏序关系，得到不同的偏序集。还要说明一下，一个偏序集(A，≺)，包含集合A与集合A上的偏序关系≺。不允许x∊(A，≺)出现，而仅有x∊A，（x，y）∊≺。即谈到元素是从A中取，讲到关系是在≺中取。11/49覆盖设(A，≺)是一个偏序集，A是一个有限集，

14、A

15、=n。对于任意的x，y∊A，且x≠y，假设(x,y)∊≺，即x≺

16、y。如果对于∀z∊A，由x≺z，且z≺y，一定能够推出x=z或y=z，那么我们说y覆盖x。设R为非空集合A上的偏序关系,x,y∈A,如果x≺y且不存在zA使得x≺z≺y,则称y覆盖x.12/49A={1,2,3,4}≺={(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(1,4),(2,4)}显然2覆盖13覆盖14覆盖2，但4不覆盖11234哈斯图13/49二、哈斯图（HasseDiagram)设(A，≺)是一个偏序集，A是一个有限集，

17、A

18、=n。可以用一个图形来表示偏序集（A，≺），这个图形有n个顶点，每一个顶点表示

19、A中一个元素，两个顶点x与y，若有y覆盖x，则点x在点y的下方，且两点之间有一条直线相连结。哈斯图：利用偏序自反、反对称、传递性简化的关系图14/49例A={a,b,c,d,e}≺={(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(a,c),(a,d),(a,e),(b,c),(b,d),(c,d),(e,d)}显然b覆盖a,e覆盖ac覆盖bd覆盖cd覆盖eabcde特点：每个结点没有环，两个连通的结点之间的有序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边。16哈斯图实例例<{1,

20、2,3,4,5,6,7,8,9},R整除>17/49例试画出哈斯图设A={{1},{2},{3},{4},{1,2},{