南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 16 代数格

1 代数格

代数格 1

回顾 2 问题1：什么是循环群 口通过某个元素（生成元)生成所有元素 口无限循环群有两个生成元，有限循环群有Φ()个 生成元 口问题2：循环群的子群是否存在、如何构造？ 口对于n阶循环以及n的因子d,恰有一个d阶子群， 为 口问题3：循环群是否存在统一的规律性？ 口无限循环群皆与整数加群同构，n阶有限群循环 群皆与模n加法群同构

回顾  问题1：什么是循环群？  通过某个元素（生成元）生成所有元素  无限循环群有两个生成元，有限循环群有Φ(n)个 生成元  问题2：循环群的子群是否存在、如何构造？  对于n阶循环以及n的因子d，恰有一个d阶子群， 为  问题3：循环群是否存在统一的规律性？  无限循环群皆与整数加群同构，n阶有限群循环 群皆与模n加法群同构 2

本节提要 3 ▣内容1：代数格的定义与性质 口内容2：格同态、格同构 口内容3：分配格、有补格、有补分配格

 内容1：代数格的定义与性质  内容2：格同态、格同构  内容3：分配格、有补格、有补分配格 3 本节提要

格（回顾） 4 (S,≤)的一个（偏序)格，如果下列条件成立： 口设(S,≤)是偏序集 口x,y∈S,存在{xy}的最小上界lubx},记为vyo 口x,y∈S,存在{ky以的最大下界glb{xy以，记为xy。 口设(S,)是格，则(S,入，V)有下列性质： 口结合律：(aAb)Ac=a∧(bAc),(Vb)Vc=aV(bVc) 口交换律：Ab=bAa,vb=bvM 口吸收律：aA(vb)=a,MV(aAb)=t

 (S,≼)的一个（偏序）格，如果下列条件成立：  设(S,≼)是偏序集  x, yS, 存在{x,y}的最小上界lub{x,y}, 记为xy。  x, yS, 存在{x,y}的最大下界glb{x,y}, 记为xy。  设(S, ≼)是格，则(S, ,  )有下列性质:  结合律：(ab)  c = a  (bc), (ab)  c = a  (bc)  交换律：ab = ba, ab = ba  吸收律：a  (ab) = a, a  (ab)=a 4 格(回顾)

代数格（定义） 5 设L是一个集合，∧和V是L上的二元运算，且满足结合律、 交换律、吸收律，则称(L,入，V)是代数格。 等式 名称 XA(AZ)=(xA)AZ 结合律 xv(v)=(xvy)vz xAV=AX 交换律 xVy=yVx xv(xAv)=x 吸收律 xA(xvp)=x

 设L是一个集合， 和是L上的二元运算，且满足结合律、 交换律、吸收律，则称(L, , )是代数格。 等 式 名 称 x(yz)=(xy)z x(yz)=(xy)z 结合律 xy =yx xy= yx 交换律 x(xy) = x x(xy) = x 吸收律 5 代数格(定义)

代数格中的偏序关系 6 aVx,y∈B,xAy=x iffxvy=y 口若xAy=x,则Vy=(cAy)Vy=y∥吸收律 口若Vyy,则xΛy=xΛ(Vy)=x∥吸收律 ▣Hx,y∈B,定义x≤y iffxny=x(即Vy) ▣证明这个关系满足自反性、反对称性、传递性。 ▣这个偏序构成一个格。 ■lub{xy}即为xvyo ■glb{x,y}即为xΛyo ▣代数格等同于（偏序）格

  x, yB, xy =x iff xy =y  若 xy =x，则 xy = (xy)  y = y //吸收律  若 xy =y，则 x y = x (xy) = x //吸收律   x, yB, 定义 x ≼ y iff xy =x (即 xy =y)  证明这个关系满足自反性、反对称性、传递性。  这个偏序构成一个格。 ◼ lub{x,y} 即为 xy。 ◼ glb{x,y} 即为 xy。  代数格等同于（偏序）格 6 代数格中的偏序关系

格的代数性质 结合律 交换律 吸收律 幂等律 吸收律 幂等律 xAx=xA(xycx)=x(两次应用吸收律) 同理可证：xVx=X

结合律 交换律 吸收律 幂等律 吸收律 幂等律 x  x = x  ( x  (xx) ) = x （两次应用吸收律） 同理可证：x  x = x 7 格的代数性质

本节提要 8 ▣内容1：代数格的定义与性质 口满足结合律、交换律、吸收律，亦可通过此三性质定义 代数格 ▣内容2：格同态、格同构 口内容3：分配格、有补格、有补分配格

 内容1：代数格的定义与性质  满足结合律、交换律、吸收律，亦可通过此三性质定义 代数格  内容2：格同态、格同构  内容3：分配格、有补格、有补分配格 8 本节提要

格同态 9 定义13.5设L1和L2是格 fL1→L2, 若Va,b∈L1有 a∧b)=a∧b), favb)=f(a)vfb) 成立，则称∫为格L,到L2的同态映射，简称格同态

格同态 9

格同态与格同构 10 设f是格L1到L2的映射， 0(1)若f为格同态映射，则f保序，即 (x,y∈L1)(x≤y→f(x)≤f(y) 0(2)若f为双射，则f为格同构映射（即格同构)当 且仅当 (付x,y∈L1)(x≤y台f(x)≤fy)

格同态与格同构 10