文档介绍：第七章格
一偏序集
定义7-1 集合L和定义在 L 上的偏序关系“≤”一起称为偏序集,用<L;≤>表示。
若是集合A上的偏序关系,则的逆关系
也必是A上的偏序关系,证明如下:
<R;≤>,<I:≤>,<2U; >和<N;|>都是偏序集。
a A,因为自反,所以有
(a,a) ,于是(a,a) ,因此
也是自反的。
a ,b A ,若(a,b) 且(b,a) ,
则有(b,a) 且(a,b) ,必有a = b,
因此是反对称的。
,b,c A,若(a,b) ,(b,c) ,
则有(c,b) 且(b,a) ,必有
(c,a) ,于是(a,c) ,因此
是可传递的。
由上证得也是偏序关系。
根据逆关系的定义
=
由定义=
例1 设 A= ,定义 A 上的整除关系:
当旦仅当 a 整除 b 时,有。
的次序图如下的次序图如下
6
1
3
6
2
2
3
1
若<L; >是一个偏序集,则对于任意元素
1, 2, 3 L,有以下六个关系式成立:
1 1 (7- )
若 1 2 , 2 1,则 1= 2 (7- )
若 1 2 , 2 3,则 1 3 (7- )
注意在偏序集<L; >中,对任意元素 1, 2 L,
若 1 2,则必有 2 1,
若 2 1,则必有 1 2,因此, 1 2
等价于 2 1 。
1 1 (7-1)
若 1 2 , 2 1,则 1= 2 (7-2)
若 1 2 , 2 3,则 1 3 (7-3)
定义7-1 设 1和 2是偏序集<L; >中的两个元素,
元素a L,如果满足a 1,a 2 ,则称a是 1和 2的
下界。
定义7-2 设 1和 2是偏序集<L; >中的两个元素,
元素 b L ,如果满足 1 b, 2 b,则称 b是 1和 2的上界。
如果元素a是 1和 2的下界。且对于任意 L,若
也是 1和 2的下界,便有 a ,则称a是 1和 2的最大下界,简记作a=glb( 1 , 2).
如果元素 b是 1和 2的上界,且对于任意 L,若也是 1和 2的上界,便有b ,则称 b 是 1和 2的最小上界,简记作b=lub( 1, 2)
lub(2,3)=?,
glb(12,18)=?,
lub(18,27)=?
有2 6,3 6;2 12,3 12;2 18,3 18。
由于6 12,6 18,6 6,因此,lub(2,3)=6。
6 ≤ 12,6 ≤ 18;2 ≤ 12,2 ≤ 18;3 ≤ 12,3 ≤ 18;1 ≤ 12,1 ≤ 18;
因1 ≤ 6,2 ≤ 6,3 ≤ 6,所以glb(12,18)=6。
例2 设A= “整除”关系是A上的偏序关系,其次序图如下,因此,它们构成一个偏序集<A; >。
1
18
12
27
2
3
6
9
试问 glb(18,12)=?,
lub(2,3)=?
2≤18,2 ≤ 12;3 ≤ 18,3 ≤ 12,1 ≤ 18,1 ≤ 12。
但glb(18,12)不存在。
类似地,12,18 和 36 均是 2 和 3 的上界,
但 lub(2,3)不存在。
例3 设A= ,整除关系是A上
的偏序关系,其次序图如下
36
18
12
2
3
1
定理7-1 设和是偏序集<L;≤>的两个元素,如果和有glb,则glb是唯一的,如果和有lub,则lub是唯一的。
证明设和都是和的glb,
由定义7-1,则≤, ≤,于是有= 。
类似地可以证明, 和若存在lub,则lub也一定是唯一的。
定理7-2 如果偏序集<L;≤>有最小元素,则最小元素是唯一的。如果<L;≤>有最大元素,则最大元素也是唯一的。
3 最小元素和最大元素
定义7-3 设<L;≤>是一偏序集。
(1) 如果存在元素a L,使得对于所有的元素 L,有a ≤,则称a是<L;≤>的最小元素。
(2) 如果存在元素b L,使得对于所有的元素 L,有≤b,则称b是<L;≤>的最大元素。
证明设和都是<L;≤>的最小元素,则有≤,且≤,得= 。
二、格
定义7-4 设<L;≤>是一个偏序集,如果L中任意两个元素都存在着最大下界和最小上界,则称<L;≤>是格。
=glb( , ), =lub( , )。
若<L;≤>是一个格,则意味着<L;≤>也是一个形为<L; , >的代数系统,其中和是L上的两个二元运算, 对于任意, , 表示在偏序“≤”意义下, 和的最小上界, 表示和的最大下界。