南京大学：《离散数学 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

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

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

关于格的对偶命题 。对偶命题的例子 ·aAb≤a和vb≥a互为对偶命题 ·对偶命题构成规律 。格元素名不变 。≤与产，A与v全部互换

关于格的对偶命题  对偶命题的例子  ab≼a和ab≽a互为对偶命题  对偶命题构成规律  格元素名不变  ≼与≽，与全部互换。 7

格的对偶原理 ·如果命题P对一切格为真，则P的对偶命题P*也对 一切格为真。 。证明思路：证明P对任意格(S,≤)为真 ·定义S上的二元关系≤*，Va,b∈S,a≤*b台b≤4，显然≤* 是偏序。 ●a,b∈S,aA*b=vb,aV*b=aAb所以(S,≤*)也是格 。这里aA*b,v*b分别是，b关于偏序<*的最大下界和最小上界。 ·P*在(S,)中为真当且仅当P在(S,≤*)中为真。 。P在一切格中为真，P*在一切格中为真。 8

格的对偶原理  如果命题P对一切格为真，则P的对偶命题P*也对 一切格为真。  证明思路：证明P*对任意格(S, ≼)为真  定义S上的二元关系≼* , a,bS, a≼*b  b≼a, 显然≼* 是偏序。  a,bS, a*b=ab, a*b=ab 所以(S, ≼*)也是格  这里a*b, a*b分别是a,b关于偏序≼*的最大下界和最小上界。  P*在(S, ≼)中为真当且仅当 P在(S, ≼*)中为真。  P在一切格中为真，P*在一切格中为真。 8

子格 ▣子格 (sub lattice)是格的子代数。设 (L,∧，V)是格，非空集合S≤L,若S关于L中 的运算A,V仍构成格，称(S,A,V)是L的子格 例13.5设格L如图3所示.令 S=a,e,f,gh,S2-a,b,e,gy S不是L的子格，因为 e,feS1但e∧f=ceS S2是L的子格

子 格 9

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

格同态 10