《离散之格的性质.ppt》由会员分享，可在线阅读，更多相关《离散之格的性质.ppt（21页珍藏版）》请在金锄头文库上搜索。
1、1,8.3 格的性质,8.3.1 格的性质 8.3.2 格的同态与同构,2,8.3.1 格的性质,定理8.3.1 设(L, )是一个格，a, b是L中任意元素，于是 ab ab=a ab=b 证明： 若ab，因为aa，所以a是a, b的下界，故aab。而ab是a, b的最大下界，所以aba。故ab=a。 若ab=a，由吸收律知ab=(ab)b=b。 若ab=b，由ab的定义知，b是a, b的最小上界，当然有ab。,3,设(L, )是一个格，a,b,c是L中任意元素，如果bc，则有 ： abac，abac 证明：因为bc，所以由定理8.3.1知 bc=b 又因为(ab)(ac)=(aa)(bc)
2、 = a(bc) = ab 再由定理8.3.1知：abac。 同理可证得第二个不等式。,定理8.3.2,4,设(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) 对偶地可证得另一不等式。,定理8.3.3,5,注意：在一般格中，分配律不是总成立的，但上述分配不等式总是成立的。 因为a2(a1a3)=a
3、2 (a2a1)(a2a3)=a3,6,设(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。,定理8.3.4,7,8.3.2 格的同态与同构,定义8.3.5 设(L,)和(S,)是两个格，L到S内的映射g称为(L,)到(S,)的格同态映射，如果对任意a，bL，都有 g(ab)=g(a)g(b) g(ab)=g(a)g(b) 定义：格L到L内的同态映射称为格的自同态映射。 定
4、义：若g是L到S上的同态映射，且是一对一的，则称g是格同构映射，并称格L与格S是同构的。此时，对任意xL，任意yS ，有 g-1(g(x)=x，g(g-1(y)=y。,8,同态映射例,例：设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上的映射。,9,往证g是同态映射。 首先证对任意A,B(s)， g(AB)=g(A)g(B)。 若aAB，则aA，aB，故 g(AB)=1，g(A)
5、g(B)=11=1。 若aAB，则 g(AB)=0，g(A)g(B)= 综上，g(AB)=g(A)g(B)。,10,再证对任意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)=00=0。 综上，g(AB)=g(A)g(B)。 因此，g是(s)到L上的同态映射。,11,自同态映射例,例：设S=a,b，(S)=,a,b,a,b，则(S),)是一个格。规定映射g为：g()=g(a)=，g(b)=g(a,b)=b。 显然，g为(S)到(S)内的映射。往证g是同态映射。不难验证对任意A,B(S)，有
6、： 若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)=。故 g(AB)=g(A)g(B)，g(AB)=g(A)g(B)。 g为格(S),)的自同态映射。,12,同构映射例,例：设S=a,b,c， (S)=,a,b,c,a,b,b,c,a,b,c，则(S),)是一个格。 (S30,)是一个格，、分别是求两个正整数的最高公因、最小公倍。 规定映射g为：1，a2，b3，c5，a,b6，a,c10，b,c15，a,b,c30。 则显然g为(S)到S30上的1-1映射。
7、不难验证对任意A,B(S)，有： g(AB)=g(A)g(B)，g(AB)=g(A)g(B)。 因此，g为(S)到S30上的同构映射.,13,格的同态映射一定是保序映射,定理8.3.5 设(L,)和(S,)是两个格集合L上对应于运算,的部分序为L，集合S上对应于运算,的部分序为s。如果g是L到S内的同态映射，则g是保序映射，亦即，对任意a，bL，若aLb，则g(a)sg(b)。 证明：由ab，知ab=a，故 g(ab)=g(a)，而 g(ab)=g(a)g(b)=g(a)， 故g(a)sg(b),14,例：,同态具有保序性，但其逆命题不一定成立，即保序映射不一定是同态的。下面给出3个格L1,
8、L2, L3。定义映射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 a a1 a2 L1 L2 L3,c2,b2,15,例：,可以看出这3个映射都是保序的，但都不是同态的。因为 1(bc)=1(d)=d1，1(b)1(c)=a1a1=a1， 2(bc)=2(a)=a1， 2(b)2(c)=d1d1=d1， 3(bc)=3(d)=d2， 3(b)3(c)=b2c2=c2。,16
9、,设(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,)的代数子格。,定理8.3.6,17,设(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
10、)=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上的同构映射。,定理8.3.7,18,若格(L,)和格(S,)同构，g是其同构映射，则对L中任意两个元素a，b，有 aLb g(a)sg(b) 其中L,S分别是集合L，S上对应于运算，的部分序关系。,推论：,19,n维格,设L=0,1，规定01。于是，(L,)是格。令(L,)是与之等价的代数格。 令Ln=(a1,an)aiL，i=1,n 规定：
11、(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)。,20,设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上的一对一映射。,例：,21,任取A,B(s)，令 g(A)=(a1,an)，g(B)=(b1,bn)，g(AB)=(c1,cn)，于是由g的定义知： ai=1 siA，i=1, ,n bi=1 siB，i=1, ,n ci=1 siAB，i =1, ,n 于是，ci=1 ai=1同时bi=1，i =1, ,n。 因此，ci=aibi，故 (c1, ,cn)=(a1b1, ,anbn) =(a1, ,an)(b1, ,bn) 即，g(AB)=g(A)g(B)。同理： g(AB)=g(A)g(B)。 故(s),)与(Ln,)同构。,
