上节课内容上节课内容 等价关系等价关系等价关系等价关系等价类等价类定义定义性质性质商集、集合的划分商集、集合的划分等价关系和划分的对应等价关系和划分的对应1 2/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≤yR有自反性、有自反性、 反对称性、反对称性、 传递性传递性. 4/49偏序关系、偏序集偏序关系、偏序集定义定义1 设设A是一个非空集合，是一个非空集合，R是是A上的一个二上的一个二元关系，若元关系，若R有自反性、有自反性、反反对称性、传递性，对称性、传递性，则称则称R是是A上的一个上的一个偏序关系偏序关系，，记作作≼ ≼。
并称并称(A，， ≼ ≼)是一个是一个偏序集偏序集 如果如果（（x, y)∈≼∈≼, 则记作作 x≼ ≼y, 读作作 x“小于或小于或等于等于”y例例1 A={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|y证明证明(Z+，，R)是偏序集是偏序集 6/49例例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 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关于记号关于记号 ≺ ≺u 对于一个偏序关系，往往用记号对于一个偏序关系，往往用记号“≺ ≺”来表示u 若若(a，，b) ∊ ∊ ≺ ≺，记为，记为a ≺ ≺ b，读做，读做“ a小于等于小于等于b”u 一个一个偏序集，通常用符号偏序集，通常用符号(A，，≺ ≺)来表示来表示 10/49注意注意n偏序关系偏序关系“a小于等于小于等于b”，并不意味着平时，并不意味着平时意义上的意义上的a小于等于小于等于bn一个集合上可以定义不同的偏序关系，得到一个集合上可以定义不同的偏序关系，得到不同的偏序集不同的偏序集n还要说明一下，一个偏序集还要说明一下，一个偏序集(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. 12/49 A={1, 2, 3, 4}≺ ≺={(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4)} 显然显然 2覆盖覆盖1 3覆盖覆盖1 4覆盖覆盖2，但，但4不覆盖不覆盖11234哈斯图哈斯图 13/49二、哈斯图（二、哈斯图（Hasse Diagram)设设(A，，≺ ≺ )是一个偏序集，是一个偏序集， A是一个有限集，是一个有限集，|A|=n。
可以用一个图形来表示偏序集（可以用一个图形来表示偏序集（A，，≺ ≺），），这个图形有这个图形有 n个顶点，每一个顶点表示个顶点，每一个顶点表示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覆盖覆盖a c覆盖覆盖b d覆盖覆盖c d覆盖覆盖eabcde 特点：特点： 每个结点没有环，每个结点没有环， 两个连通的结点之间的有序关系通两个连通的结点之间的有序关系通过结点位置的高低表示，位置低的元素过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点的顺序在前，具有覆盖关系的两个结点之间连边。
之间连边 16哈斯图实例哈斯图实例例例 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除整除> 17/49例 试画出哈斯图试画出哈斯图设设A={ {1}, {2}, {3}, {4}, {1,2}, {1,5}, {3,6}, {4,6}, {0,3,6}, {1,5,8}, {0,3,4,6} }R是是A上的一个偏序关系上的一个偏序关系: 对于任意的对于任意的x,y∊ ∊A，，(x,y) ∊ ∊R当且仅当当且仅当x⊆ ⊆y{1}{2}{1,5}{1,2}{3}{4}{3.6}{4,6}{1,5,8}{0,3,6}{0,3,4,6} 18A={a, b, c, d, e, f, g, h} R={,,,,,,,,}∪∪IA 哈斯图实例哈斯图实例例例 已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示, 试求出集合试求出集合A和关系和关系R的表达式的表达式. 19注意事项：注意事项： 1、、不出现三角形；不出现三角形； 2、、不出现水平线段；不出现水平线段； 3、、尽量减少交叉线。
尽量减少交叉线 20/49可比、不可比可比、不可比设设(A，，≺ ≺)是一个偏序集，对于任意的是一个偏序集，对于任意的x, y∊ ∊A，若，若x≺ ≺y或者或者y≺ ≺x，，则说则说 x与与y可比可比，否则说，否则说 x与与y不可比不可比例 给出如图所示的偏序集例 给出如图所示的偏序集 2与与1、、2与与4等都是可比的，等都是可比的， 而而2与与3、３与４都是不可比的３与４都是不可比的1234 21/49三、链三、链 、反链、反链 设设(A，，≺ ≺)是一个偏序集，是一个偏序集， B是是A的一个的一个子集子集1)如果Ｂ中任意两个元素都可比如果Ｂ中任意两个元素都可比, 说说(B，，≺ ≺)是一条是一条链链2) 如果Ｂ中任意两个元素都不可比如果Ｂ中任意两个元素都不可比, 说说(B，，≺ ≺)是一条是一条反链反链 22/49例 给出如图所示的偏序集例 给出如图所示的偏序集abcde ({ a, b, c, d }, ≺ ≺) 链链 ({ a, d, e }, ≺ ≺) 链链 ({ b, e }, ≺ ≺) 反链反链 ({ c, e }, ≺ ≺) 反链反链 23/49全序集 设设(A，，≺ ≺)是一个偏序集，是一个偏序集，如果它本身就是一条链，如果它本身就是一条链，那么称之为那么称之为全序集全序集，并称，并称≺ ≺ 为为全序关系全序关系。
例 例 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) }abcdeabcde, (b,e), (e,c) 25/49四、偏序集中的特定元素四、偏序集中的特定元素设设(A，，≺ ≺)是一个偏序集，是一个偏序集，B A, y∈∈B.u若若x (x∈∈B∧∧x ≺ ≺ y) 成立成立, 则称称 y 为B的的极极小元小元. u若若x (x∈∈B∧∧y ≺ ≺ x) 成立成立, 则称称 y 为B的的极极大元大元.1、、极大元、极小元极大元、极小元 26/49例 给出如图所示的偏序集例 给出如图所示的偏序集在在{1，，2}中，中，1是极小元，是极小元， 2是极大元是极大元在在{1，，2，，3}中，中，1是极小元，是极小元， 2、、3是极大元是极大元在在{1，，2，，3，，4}中，中，1是极小元，是极小元， 3和和4是极大元。
是极大元1234 27/49设设(A，，≺ ≺)是一个偏序集，是一个偏序集，B A, y∈∈B.u若若 x(x∈∈B→y≼ ≼x) 成立成立, 则称称 y 为 B 的的最最小元小元.u若若 x(x∈∈B→x≼ ≼y) 成立成立, 则称称 y 为 B 的的最最大元大元. 2、、最大元、最小元最大元、最小元 28/49一个有限的偏序集，一定有极大元和极小元，一个有限的偏序集，一定有极大元和极小元，但不一定有最大元和最小元但不一定有最大元和最小元例 给出如图所示的偏序集例 给出如图所示的偏序集 1是最小元，也是极小元，是最小元，也是极小元， 3和和4是极大元，无最大元是极大元，无最大元1234 29/49例例 考察如图所示偏序集最小元与最大元考察如图所示偏序集最小元与最大元u (a)无最大元无最大元u (c)表示的偏序集没有最小元与最大元表示的偏序集没有最小元与最大元u (b)和和(d)表示的偏序集有最小元与最大元表示的偏序集有最小元与最大元1234abcdeabcdefghijkabcdfegh (a) (b) (c) (d) 极大、极小与最大最小元的找法：极大、极小与最大最小元的找法：1、、孤立点。
孤立点 既是极大元也是极小元既是极大元也是极小元 若图中有孤立点，则必无最大、最小元若图中有孤立点，则必无最大、最小元2、、除孤立点外，除孤立点外， 其他极其他极小小元是图中所有元是图中所有向下向下通路的终点；通路的终点； 其他极其他极大大元是图中所有元是图中所有向上向上通路的终点通路的终点3、、若极小元唯一则其为最小元；若极小元唯一则其为最小元； 若极大元唯一则其为最大元；若极大元唯一则其为最大元； 例例 找出极大、极小元与最大、最小元找出极大、极小元与最大、最小元极小：极小：1极大：极大：5，，6，，7，，8，，9最小：最小：1最大：无最大：无极小：极小：φφ极大：极大：{a，，b，，c}最小：最小：φφ最大：最大：{a，，b，，c} 32/49设设(A，，≺ ≺)是一个偏序集，是一个偏序集， B A, y Au若若 x(x∈∈B→x≼ ≼y) 成立成立, 则称称 y 为B的的上界上界u若若 x(x∈∈B→y≼ ≼x) 成立成立, 则称称 y 为B的的下界下界3、、上界、下界上界、下界 33/49例 给出如图所示的偏序集。
例 给出如图所示的偏序集 h、、i、、j和和k都是都是{f，，g}的上界，的上界， c、、d、、a为其下界为其下界 abcdefghijk 34/49设设(A，，≺ ≺)是一个偏序集，是一个偏序集，B A, y A.u令令C＝＝{y | y为B的上界的上界}, 则称称C的最小元的最小元为B的的最小上界最小上界 或或 上确界上确界. u令令D＝＝{y | y为B的下界的下界}, 则称称D的最大元的最大元为B的的最大下界最大下界 或或 下确界下确界. 4、、上确界、下确界上确界、下确界 35/49例例 给出如图所示的偏给出如图所示的偏 序集 ◆◆ {b，，d}的上界是的上界是h和和f 下界是下界是a；； 上确界是上确界是f，，下确界是下确界是aabcdfegh1、、B中的元素向上走共同能到达的即为上界，中的元素向上走共同能到达的即为上界， 上界中的最大元即为上确界；上界中的最大元即为上确界；2、、B中元素向下走共同能到达的为下界，中元素向下走共同能到达的为下界， 下界中的最小元即为下确界。
下界中的最小元即为下确界 36实例实例例例 设偏序集设偏序集如下图所示，求如下图所示，求 A 的极小元、最的极小元、最小元、极大元、最大元小元、极大元、最大元. 设设 B＝＝{b,c,d}, 求求 B 的下界、的下界、上界、下确界、上确界上界、下确界、上确界. 极小元：极小元：a, b, c, g；；极大元：极大元：a, f, h；；没有最小元与最大元没有最小元与最大元.B无下界和下确界无下界和下确界, 上界有上界有d 和和 f, 上确界为上确界为 d. 小结小结 偏序关系偏序关系偏序关系（自反、反对称、传递）偏序关系（自反、反对称、传递）哈斯图哈斯图画法画法从从图写出关系图写出关系特定元素特定元素极极大、极小元与最大、最小元大、极小元与最大、最小元上界、下界与上、下确界上界、下界与上、下确界37 。