离散数学II课件：7_3格的性质-1

1、7.3 格 的 性 质,7.3.1 格 的 性 质 7.3.2 格的同态与同构,7.3.1 格 的 性 质,定理7.3.1 设（L，）是一个格，a，b是L中任 意元素，于是 ab ab = a a b = b 证明： 若ab，因为aa，所以a是a，b的下界，故aab。而ab是a，b的最大下界，所以aba。故ab=a。 若ab=a，由吸收律知ab=(ab)b=b,由ab的定义知，b是a，b的 最小上界，显然有ab。 若ab=b，由ab的定义知，b是a，b的 最小上界，显然有ab。,定理7.3.2 设（L，）是一个格，a，b，c是 L中任意元素， 如果bc，则有 abac abac 证明： 因为b

2、c，所以由定理8.3.1知 bc=b 又因为(ab)(ac)=(aa)(bc) = a(bc) = ab 再由定理8.3.1知：abac。 同理可证得第二个不等式。,定理7.3.3 设（L，）是一个格，a，b，c是L中任意元素。于是有 a（bc） （ab）（ac） a（bc）（ab）（ac） 其中关系“”是关系“”的对偶关系。 证明：因为aab，aac，所以，由的定义知 a（ab）（ac） （1） 又因为 bcbab bccac 所以，再由的定义知 bc（ab）（ac） （2） 由的定义及（1），（2）式知 a（bc）（ab）（ac） 对偶地可证得另一不等式.,Note:在一般格中，分配律不是

3、总成立的，但上 述分配不等式总是成立的。 因为a2（a1a3）= a2 （a2a1）（a2a3）=a3 只有对特殊的格（分配格、模格）分配律才成立,定理7.3.4 设（L，）是一个格，a，b，c是L中任意元素，于是， ab a（bc）b（ac） 证明： 若ab，则由定理8.3.1知：ab=b。由定理8.3.3知 a（bc）（ab）（ac） = b（ac） 若a（bc）b（ac），则由的定义知 a（bc）a 由的定义知 b（ac）b 故ab。,7.3.2 格的同态与同构,定义. 设(L,)和(S,)是两个格，L到S 内的映射g称为(L,)到(S,)的格同态映 射，如果对任意a，bL，都有 g（a

4、b）= g（a）g（b） g（ab）= g（a）g（b）. 定义. 格L到L内的同态映射称为格的自同态映射。 定义. 若g是L到S上的同态映射,且是一对一的，则称g是格同构映射,并称格L与格S是同构的。此时，对任意xL，任意yS ，有 g-1(g()=，g(g-1(y)=y。,同态映射例,例. 设S=a,b,(S)=,a,b,a,b， 则（S），）是一个格。 设L=0，1，规定01，分别是集合L中两个元素在下的最大下界，最小上界运算，则（L，）是一个格。 规定映射g为： g（a） = 1， g（a，b） = 1， g（b） = 0， g（ ） = 0。 则显然g是（S）到L上的映射.,往证g是

5、同态映射。首先证对任意A,B(s)， g（AB） = g（A） g（B）。 若aAB，则aA，aB，故 g(AB) = 1, g(A) g(B) = 1 1 = 1。 若aAB，则 g(AB) = 0, g(A) g(B) = 综上，g（AB） = g（A） g（B）。,再证对任意A,B(s)，g(AB)=g(A)g(B) 若aAB，则 g(AB)=1，g(A)g(B)= 若aAB，则aA，aB，故 g(AB)= 0 ， g(A)g(B)=0 0 = 0。 综上，g（AB） = g（A） g（B）。 因此，g是(s)到L上的同态映射。,自同态映射例,例. 设S=a,b,(S)=,a,b,a,b

6、， 则(S)，）是一个格。规定映射g为： g() = g(a) =， g(b)=g(a，b)= b。 显然,g为(S)到(S)内的映射。往证g是同 态映射。不难验证对任意A,B(S),有: 若bAB,则g(AB)=g(A)g(B)=b； 若bAB，则g(AB)=g(A)g(B)=。 若bAB，则g(AB)=g(A)g(B)=b； 若bAB，则g(AB)=g(A)g(B)=。 故 (AB)=g(A)g(B),g(AB)=g(A)g(B)。 g为格（S），）的自同态映射。,同构映射例,例. 设S=a,b,c, (S)=,a,b,c,a,b,b,c,a,b,c, 则(S),)是一个格。 （S30，）

7、是一个格,、分别是求两个 正整数的最高公因、最小公倍。 规定映射g为： 1, a2, b3, c5,a,b6,a,c10,b,c15,a,b,c30。 则显然g为(S)到S30上的1-1映射。 不难验证对任意A,B（S），有： g(AB)=g(A)g(B), g(AB)=g(A)g(B)。 因此，g为(S)到S30上的同构映射.,格的同态映射一定是保序映射,定理7.3.5 设(L,)和(S,)是两个格。 集合L上对应于运算，的部分序为L， 集合S上对应于运算，的部分序为s。 如果g是L到S内的同态映射，则g是保序映射， 亦即，对任意a，bL， 若aLb，则g（a）sg（b）。 证明： 由ab,

8、 知ab=a，故g(ab)= g(a), 而 g（ab）= g（a）g（b） = g（a） 故g（a）sg（b）,例子,例 同态具有保序性，但其逆不一定成立，保序映射不一定是同态的。下面给出3个格L1,L2L3。定义映射1, 2和3： 1：L1L2, 1(a)= 1(b)= 1(c)=a1, 1(d)=d1. 2：L1L2, 2(b)= 2(c)= 2(d)=d1, 2(a)=a1. 3：L1L3, 3(a)=a2, 3(b)=b2, 3(c)=c2, 3(d)=d2. d d1 d2 b c b2 a a1 a2 L1 L2 L3,c2,例子,可以看出这3个映射都是保序的，但都不是同态的。因

9、为 1(bc)= 1(d)=d1, 1(b) 1(c)= a1 a1=a1, 2(bc)= 2(a)=a1, 2(b) 2(c)= d1 d1=d1, 3(bc)= 3(d)=d2, 3(b) 3(c)=b2 c2=c2,定理7.3.6 设(L,)是一个格，g是此格的 自同态映射，于是g(L)是(L，)的代数 子格。 证明： 任取a,bg(L),则必有a,bL, 使 a= g（a）， b= g（b） 因为g是格（L，）的自同态映射，所以 ab=g(a)g(b)= g(ab)g(L)， ab= g(a)g(b)=g(ab)g(L)。 即在运算，下，g（L）是封闭的。 故（g（L）， ，）是（L，

10、）的代 数子格。,定理7.3.7 设(L,）,(S,)是两个格， 若g是L到S上的同构映射， 则g的逆映射g-1是S到L上的同构映射。 证明： 显然g-1是S到L上的一对一映射。 下面证明g-1是S到L上的同态映射。 任取a,bS,令g-1(a)=a,g-1(b)=b。于是 g（a）= a， g（b）= b。 g-1(ab)=g-1(g(a)g(b)=g-1(g(ab) = ab =g-1(a)g-1(b)。 g-1(ab)= g-1(g(a)g(b)=g-1(g(ab) = ab= g-1（a）g-1（b）。 故g-1是S到L上的同构映射。,推论 若格（L，）和格（S，） 同构，g是其同构映

11、射，则对L中任意两个元素a，b，有 aLb g（a）sg（b） 其中L，S分别是集合L，S上对应于运算， 的部分序关系。,n维格,设L=0，1，规定01。于是，（L，）是格。 令（L，）是与之等价的代数格。 令 Ln=(a1，an)aiL，i=1，n 规定：(a1,an )n ( b1,bn ) aibi (i=1,n) 不难证明：(Ln，n)是一个格，通常称为n维格。令与(Ln，n)等价的代数格为(Ln,)，对Ln中任意两个元素(a1,an)，(b1,bn)，显然有(a1,an)(b1,bn)=(a1b1,anbn) (a1,an)(b1,bn)=(a1b1,anbn)。,例. 设S是含n个元素的集合，(s)是S的幂集 合，则格（(s)，）与格（Ln，n）同构。 证明：令S=s1，sn。 令g是(s)到Ln上的映射如下：任取A(s)， g（A）=（a1，an） 其中ai=1 siA，i=1，n。 显然，g是（s）到Ln上的一对一映射。,任取A,B(s),令 g(A)=(a1,an),g(B)=(b1,bn)，g(AB)=(c1,cn)，于是由g的定义知：