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

上节课内容等价关系等价关系等价类定义性质商集、集合的划分等价关系和划分的对应1

7.6偏序关系和格2/49格上界、下界、最小上界、最大下界极大元、极小元、最大元、最小元链、反链、全序集哈斯（Hasse）图偏序关系、偏序集

一、偏序关系3/49例在实数集R上定义二元关系S，1对于任意的x,y?R，2(x，y)?S当且仅当x≤y。3R有自反性、4反对称性、5传递性.6

偏序关系、偏序集4/49定义1设A是一个非空集合，R是A上的一个二元关系，若R有自反性、反对称性、传递性，则称R是A上的一个偏序关系，记作?。并称(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上一个偏序关系。

例2(p109)5/49设Z+={n?Z│n0}，即Z+是正整数的集合。1在Z+上定义一个二元关系R如下:2对于任意的x,y?Z+，3(x,y)?R当且仅当x|y。4证明(Z+，R)是偏序集5

例2(p109)证明(Z+，R)是偏序集（1）对于任意的x?Z+,显然有x|x,所以(x,x)?R,即R是自反的。（2）对于任意的x,y?Z+,若(x,y)?R,且(y,x)?R，则x|y,即存在n?Z+,y=nx且y|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|y,即?n0?Z+，使得y=xn0;再由(y,x)?R,得y|x,即?m0?Z+，使得z=m0y。所以z=m0n0x，即x|z，所以(x,z)?R,即R有传递性。综上所述,R是Z+上偏序关系，即(Z+，R)是偏序集。对于任意的x,y?Z+，(x,y)?R当且仅当x|y。

在ρ(A)上建立一个二元关系R:ρ(A)是A的幂集合，(x,y)?R当且仅当x?y。不难证明(ρ(A)，R)也是一个偏序集。例3设A是任意一个集合，对于任意的x,y?ρ(A)，010203040506

例8/49在实数集R上定义二元关系S，对于任意的x，y?R，1(x，y)?S当且仅当x≤y。可以证明S是R上的一个偏序关系。2在实数集R上定义二元关系S’，对于任意的x，y?R，3(x，y)?S’当且仅当x≥y。可以证明S’是R上的一个偏序关系。集合A上的恒等关系IA是A上的偏序关系.4

关于记号?9/49一个偏序集，通常用符号(A，?)来表示。若(a，b)??，记为a?b，读做“a小于等于b”。对于一个偏序关系，往往用记号“?”来表示。

注意10/49偏序关系“a小于等于b”，并不意味着平时意义上的a小于等于b。一个集合上可以定义不同的偏序关系，得到不同的偏序集。还要说明一下，一个偏序集(A，?)，包含集合A与集合A上的偏序关系?。不允许x?(A，?)出现，而仅有x?A，（x，y）??。即谈到元素是从A中取，讲到关系是在?中取。

覆盖11/49设(A，?)是一个偏序集，A是一个有限集，|A|=n。对于任意的x，y?A，且x≠y，假设(x,y)??，即x?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.

A={1,2,3,4}01?={(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(1,4),(2,4)}02显然2覆盖13覆盖14覆盖2，但4不覆盖103哈斯图04

二、哈斯图（HasseDiagram)设(A，?)是一个偏序集，A是一个有限集，|A|=n。可以用一个图形来表示偏序集（A，?），这个图形有n个顶点，每一个顶点表示A中一个元素，两个顶点x与y，若有y覆盖x，则点x在点y的下方，且两点之间有一条直线相连结。哈斯图：利用偏序自反、反对称、传递性简化的关系图

例14/49A={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),(