《《离散数学》课件：8-3-格的性质》由会员分享，可在线阅读，更多相关《《离散数学》课件：8-3-格的性质（21页珍藏版）》请在金锄头文库上搜索。
1、8.3格的性质格的性质8.3.1格的性质格的性质8.3.2格的同态与同构格的同态与同构 1 18.3.1格的性质格的性质定定理理8.3.1设设(L,)是是一一个个格格，a,b是是L中中任任意意元元素，于是素，于是abab=aab=b证明：证明：v若若ab，因因为为aa，所所以以a是是a,b的的下下界界，故故aab。 而而 ab是是 a, b的的 最最 大大 下下 界界 ， 所所 以以aba。故。故ab=a。v若若ab=a，由吸收律知由吸收律知ab=(ab)b=b。v若若ab=b，由由ab的的定定义义知知，b是是a,b的的最最小小上上界，当然有界，当然有ab。2 2设设(L,)是是一一个个格格，
2、a,b,c是是L中中任任意意元元素素，如果如果bc，则有则有：abac，a ba c证明：证明：因为因为bc，所以由定理所以由定理8.3.1知知bc=b又因为又因为(ab)(ac)=(aa)(bc)=a(bc)=ab再由定理再由定理8.3.1知：知：abac。同理可证得第二个不等式。同理可证得第二个不等式。定理定理8.3.23 3设设(L，)是是一一个个格格，a,b,c是是L中中任任意意元元素素。于于是是有有a (bc)(a b)(a c) a(b c)(ab) (ac)其中关系其中关系“”是关系是关系“”的对偶关系。的对偶关系。证证明明：因因为为aa b，aa c，所所以以，由由的的定定义义
3、知知：a(a b)(a c)(1)又因为又因为bcba b，bcca c所以，再由所以，再由的定义知的定义知bc(a b)(a c)(2)由由 的定义及的定义及(1)，(2)式知式知a (bc)(a b)(a c)对偶地可证得另一不等式。对偶地可证得另一不等式。定理定理8.3.34 4注注意意：在在一一般般格格中中，分分配配律律不不是是总总成成立立的的，但上述但上述分配不等式总是成立分配不等式总是成立的。的。因为因为a2(a1 a3)=a2(a2a1) (a2a3)=a3a2a301a15 5设设(L,)是是一一个个格格，a,b,c是是L中中任任意意元元素素，于是，于是，aba (bc)b(a
4、 c)证明：证明：v若若ab，则则由由定定理理8.3.1知知：a b=b。由由定定理理8.3.3知：知：a (bc)(a b)(a c)=b(a c)v若若 a (bc)b(a c)， 则则 由由 的的 定定 义义 知知a (bc)a，由由的定义知的定义知b(a c)b。故故ab。定理定理8.3.46 68.3.2格的同态与同构格的同态与同构定定义义8.3.5设设(L, )和和(S,)是是两两个个格格，L到到S内内的的映映射射g称称为为(L, )到到(S,)的的格格同态映射同态映射，如果对任意，如果对任意a，bL，都有都有g(ab)=g(a)g(b)g(a b)=g(a)g(b)定义：定义：格
5、格L到到L内的同态映射称为内的同态映射称为格的自同态映射格的自同态映射。定定义义：若若g是是L到到S上上的的同同态态映映射射，且且是是一一对对一一的的，则则称称g是是格格同同构构映映射射，并并称称格格L与与格格S是是同同构构的的。此此 时时 ， 对对 任任 意意 xL， 任任 意意 yS， 有有g-1(g(x)=x，g(g-1(y)=y。7 7同态映射例同态映射例例例：设设S=a,b，(S)= ,a,b,a,b，则则(S),)是一个格。是一个格。设设L=0,1，规规定定01，,分分别别是是集集合合L中中两两个个元元素素在在下下的的最最大大下下界界，最最小小上上界界运运算，则算，则(L,)是一个
6、格。是一个格。规定映射规定映射g为：为：g(a)=1，g(a,b)=1，g(b)=0，g( )=0。则显然则显然g是是(S)到到L上的映射。上的映射。8 8往证往证g是同态映射是同态映射。首先证对任意首先证对任意A,B(s)，g(AB)=g(A)g(B)。v若若aAB，则，则aA，aB，故故g(AB)=1，g(A)g(B)=11=1。v若若a AB，则则g(AB)=0，g(A)g(B)=综上，综上，g(AB)=g(A)g(B)。9 9再证对任意再证对任意A,B(s)，g(AB)=g(A)g(B)v若若aAB，则则g(AB)=1，g(A)g(B)=v若若a AB，则，则a A，a B，故故g(A
7、B)=0，g(A)g(B)=00=0。综上，综上，g(AB)=g(A)g(B)。因此，因此，g是是(s)到到L上的同态映射。上的同态映射。1010自同态映射例自同态映射例例例 ： 设设 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)，有：，有：若若bAB，则，则g(AB)=g(A)g(B)=b；若若b AB，则，则g(AB)=g(A)g(B)=
8、 。若若bAB，则，则g(AB)=g(A)g(B)=b；若若b AB，则，则g(AB)=g(A)g(B)= 。故。故g(AB)=g(A)g(B)，g(AB)=g(A)g(B)。g为格为格(S),)的自同态映射。的自同态映射。1111同构映射例同构映射例例：例：设设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
9、。则显然则显然g为为(S)到到S30上的上的1-1映射。映射。不难验证对任意不难验证对任意A,B(S)，有：，有：g(AB)=g(A) g(B)，g(AB)=g(A)g(B)。因此，因此，g为为(S)到到S30上的同构映射上的同构映射.1212格的同态映射一定是保序映射格的同态映射一定是保序映射定定理理8.3.5设设(L, )和和(S,)是是两两个个格格集集合合L上上对对应应于于运运算算, 的的部部分分序序为为L，集集合合S上上对对应应于于运运算算,的的部部分分序序为为s。如如果果g是是L到到S内内的的同同态态映映射射，则则g是是保保序序映映射射，亦亦即即，对对任任意意a，bL，若若aLb，则
10、则g(a)sg(b)。证明：证明：由由ab，知，知ab=a，故，故g(ab)=g(a)，而，而g(ab)=g(a)g(b)=g(a)，故故g(a)sg(b)1313例：例：同态具有保序性，但其逆命题不一定成立，即保同态具有保序性，但其逆命题不一定成立，即保序映射不一定是同态的。下面给出序映射不一定是同态的。下面给出3个格个格L1,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
11、， 3(d)=d2。dd1d2bcaa1a2L1L2L3c c2 2b b2 21414例：例：可以看出这可以看出这3个映射都是保序的，但都不是个映射都是保序的，但都不是同态的。因为同态的。因为 1(b c)= 1(d)=d1， 1(b)1(c)=a1 a1=a1， 2(b c)= 2(a)=a1， 2(b)2(c)=d1 d1=d1， 3(b c)= 3(d)=d2， 3(b)3(c)=b2 c2=c2。1515设设(L, )是是一一个个格格，g是是此此格格的的自自同同态态映射，于是映射，于是g(L)是是(L, )的代数子格的代数子格。证证明明：任任取取a,bg(L)，则则必必有有a,bL，
12、使使a=g(a)，b=g(b)。因为因为g是格是格(L, )的自同态映射，所以的自同态映射，所以ab=g(a)g(b)=g(ab)g(L)，a b=g(a) g(b)=g(a b)g(L)。即在运算即在运算, 下下，g(L)是封闭的。是封闭的。故故(g(L), )是是(L, )的代数子格。的代数子格。定理定理8.3.61616设设(L, ),(S,)是是两两个个格格，若若g是是L到到S上上的的同同构构映映射射，则则g的的逆逆映映射射g-1是是S到到L上的同构映射。上的同构映射。证证明明：显显然然g-1是是S到到L上上的的一一对对一一映映射射。下下面证明面证明g-1是是S到到L上的同态映射。上的
13、同态映射。任任取取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(a b)=a b=g-1(a) g-1(b)。故故g-1是是S到到L上的同构映射。上的同构映射。定理定理8.3.71717若若格格(L,)和和格格(S,)同同构构，g是是其其同构映射，则对同构映射，则对L中任意两个元素中任意两个元素a，b，有，有aLbg(a)sg(b)其中其中L,S分别是集合分别是集合L，S上对应于运算上对应于运算，的部分序关系
14、。的部分序关系。推论：推论：1818n维格维格设设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)=(a
15、1b1,anbn)。1919设设S是是含含n个个元元素素的的集集合合，(s)是是S的的幂幂集集合合，则格则格(s), )与格与格(Ln,n)同构。同构。证明：证明：令令S=s1,sn。令令 g是是 (s)到到 Ln上上 的的 映映 射射 如如 下下 ： 任任 取取A(s)，g(A)=(a1,an)其中其中ai=1siA，i=1,n。显然，显然，g是是(s)到到Ln上的一对一映射。上的一对一映射。例：例：2020任取任取A,B(s)，令，令g(A)=(a1,an)，g(B)=(b1,bn)，g(AB)=(c1,cn)，于是由于是由g的定义知：的定义知：ai=1siA，i=1,nbi=1siB，i=1,nci=1siAB，i=1,n于是，于是，ci=1ai=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, )同构。同构。2121
