南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）代数系统——第19章 代数格

代数格 离散数学一代数结构 南京大学计算机科学与技术系

代数格 离散数学－代数结构 南京大学计算机科学与技术系

内容提要 。代数格的定义 ·格的对偶原理 。子格 。格同态、格同构 ·分配格 ·。有界格 ●有补格 。有补分配格 2

内容提要  代数格的定义  格的对偶原理  子格  格同态、格同构  分配格  有界格  有补格  有补分配格 2

格（回顾） 。(S,≤)的一个（偏序)格，如果下列条件成立： ·设(S,)是偏序集 ●x,yES,存在{x,y}的最小上界Iub{xy},记为Vy。 ·x,y∈S,存在{化，y}的最大下界glb{Ky以，记为xAy。 。设(S,)是格，则(S,A,V)有下列性质： 。结合律：(aAb)Ac=aA(bAc,(vb)Vc=aV(bVc) ●交换律：aAb=bA,vb=bVa 吸收律：aA(avb)=a,aV(aAb)=a

格（回顾）  (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 3

代数格（定义） ·设L是一个集合，A和V是L上的二元运算，且满足结合律、 交换律、吸收律，则称(L,人，V)是代数格。 等式 名称 xAAZ)=(A)AZ 结合律 xv(vvz)=(xvy)vz xAV AX 交换律 xVy=yVx xv(xAy)=x 吸收律 xA(xvy)=x 4

代数格（定义）  设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 吸收律 4

代数格中的偏序关系 ●廿x,y∈B,xAy=xfVy)y ·若xy=x,则xVy=(cy)Vy=yI/吸收律 ·若xVyy,则xAy=xA(Vy)=x/吸收律 ●廿K,y∈B,定义x≤yfxy=x(即xVy=y) ·证明这个关系满足自反性、反对称性、传递性。 。这个偏序构成一个格。 。lub{x,y}即为y。 ·glb{k,y}即为xy。 ·代数格等同于（偏序）格 5

代数格中的偏序关系   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。  代数格等同于（偏序）格 5