离散数学II课件:7_3格的性质-1_第1页
离散数学II课件:7_3格的性质-1_第2页
离散数学II课件:7_3格的性质-1_第3页
离散数学II课件:7_3格的性质-1_第4页
离散数学II课件:7_3格的性质-1_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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的定义知:

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论