考试时间：5月8日(周三)9:50 地点： Z2107教室 答疑时间： 5月7日13:30-16:00 地点：软件楼4楼密码与信息安全实验室

定理16.3:如引理16.2所得之偏序集(L;≤)为格。 定义16.4: [L;,]为一代数系统,,为定义在L上的二元运算,当其满足L1～L4时，称L为格。并称为积(或交),为和(或并)

定义：[L;,]为格，若L中存在元素0，使得对任意的xL有x0=x,则称0为的单位元，并称0是格的零元；若L中存在元素1，使得对任意的xL有x1=x,则称1为的单位元，并称1是格的单位元。 例：A的幂集格[P(A);,] 群G的子群格[L(G);,] [Z+;,] (Z;)是格，但既无单位元，又无零元。

零元(单位元)存在则必唯一 定理：若格[L;,]存在零元0和单位元1，则0和1分别是L的最小元和最大元。 由于具有零元和单位元的格一定有最小元和最大元，称为有界格。

定理16.4(保序性):格[L;,],任a,b,cL,当b≤c时有ab≤ac及ab≤ac。 定义16.5:[L;,]为格,T, TL,T关于,封闭(即a,bT则abT, abT)时,则称T为L的子格。

必须注意的是：当T为L的子格时,T一定是格; 但当TL,T关于L中的偏序关系≤为格时,T不一定是L的子格。 例：S={1,2,3},S3={e,1, 2, 3, 4, 5}为三次对称群，则(P(S3);)是格，并且是完全格。取T={{e}, H1,H2,H3,H4,S3},其中H1={e, 1}; H2={e, 2}; H3={e, 3}; H4={e, 4, 5}都是S3的子群，则(T; )是格,但它不是(P(S3);)的子格。

三、格的同态与同构 定义16.6:设[L;,]与[S;+,·]为两个格,如果存在映射:L→S使对任a, bL有: (ab)=(a)+(b), (ab)=(a)·(b),则称为L到S的同态映射,当(L)=S即为满射时又说格L与格S同态;当是一一对应时说格L与S同构;若S=L时又分别称它是自同态与自同构。

定理16.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。 保序映射不一定是同态映射

定理16.6:是格L到格S的一一对应, 则是同构映射,当且仅当:对任何a,bL,a≤b当且仅当(a)≤(b)。 若对任何a,bL,有(a)≤(b),则由≤定义知(a)(b)=(b), 因为同构,故有(ab)=(b) 且ab=b, 因此由≤定义得a≤b

(2) 是格L到格S的一一对应, 且对任何a,bL,a≤b当且仅当(a)≤(b) 主要证明是同态映射,即 (ab)=(a)(b), (ab)=(a)(b) 分别证明(ab)≤(a)(b) (a)(b)≤(ab)

§2 有补格及分配格 一、有补格 定义16.7:一个具有最大元1和最小元0的格[L;,]称为有界格。 定理16.8:[L;,]为有界格, 则任aL有:a1=1; a0=0;a1=a;a0=a。

定义16.8:[L;,]为有界格,对aL,如果存在bL,使ab=1,ab=0,则称b为a的补元,记b为a'。若L中的每个元有补元, 则称L为有补格。 例:S={1,2,3,4,5},其偏序关系由下图所示,则S是有界格,且为有补格.

由此可知补元不唯一. 二、分配格 定理(习题16.9)：对任意格成立分配不等式, 即格[L;,]中任a,b,cL,有: (1)a(bc)≤(ab)(ac); (2)(ab)(ac)≤a(bc)。 但等式不一定成立。

例:如下图所示的格分配等式不成立.

例：S,[P(S);∪,∩]满足分配等式。 分配格 定义16.9:[L;,]为格,当对其任意元a,b,cL成立分配律,即 (1)a(bc)=(ab)(ac); (2)(ab)(ac)=a(bc)。 则称该格为分配格。

定理：设S是分配格，a,x,yS,若ax=ay,且ax=ay，则x=y。 L1～L4

上述两个图所代表的格都不是分配格 可以证明对于任意的格，若|L|4,则一定是分配格。而所有非分配格，一定含有子格是与M5或N5同构的。

定理16.9:[L;,]为任意格, 则下述条件等价: (1)对任意a,b,cL,有 a(bc)=(ab)(ac) (2)对任意a,b,cL,有 a(bc)=(ab)(ac) (3)对任意a,b,cL,有 (ab)(ac)(bc)=(ab)(ac)(bc) (4)不含与M5或N5同构的子格。

(1) (2) (1),(2)(3) 左=((ab)(bc))(ac) =((a(bc))(b(bc)))(ca) =((a(bc))b)(ca) =((ab)(ac))b)(ca) =((b(ab))(ac)))(ca) =(b(ac))(ca)

(3)(1) 1.c≤a时,必有 a(bc)=?(ab)(ac)=(ab)c 2.一般情况 利用c≤a时的结论 (1),(2)(4) (4)(1) 反证,若L不是分配格,推出存在与M5或N5同构的子格 约定:a≤b,且ab,记为a<b 基本设想是在L中构造5个元素的子格,使其与M5或N5同构

{a,e,d,b,0}是M5

分两种情况 1.存在a,b,cL,当c≤a时,有 (ab)c=(ab)(ac)<a(bc) u=a(bc),v=(ab)c,v<u vb=ub vb=ub u,v,b,vb,ub, 2.对任意a,b,cL,当c≤a时,有 (ab)c=(ab)(ac)=a(bc) 关键是构造M5,N5 由此定理可以判定一个格是否为分配格.

作业P220:10, 14,15,16,17, 18(2)(3),27,28? 考试时间：5月8日(周三)9:50 地点： Z2107教室 答疑时间： 5月7日13:30-16:00 地点：软件楼4楼密码与信息安全实验室

L1幂等律:aa=a,aa=a; L2交换律:ab=ba,ab=ba; L3结合律:a(bc)=(ab)c, a(bc)=(ab)c; L4吸收律:a(ab)=a, a(ab)=a。

定理17.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。