离散数学jme-3格与代数

1、第4章 代数系统School of Microelectronics, Fudan UniversityJing Minge复习1.偏序关系，偏序集定义：设R是集合A上的二元关系，若R是自反的、称的和传递的，则称R是A上的一个“偏序关系”，并记R为 (读作“小于等于”)。当R时，记作x y。定义：同时，称集合A和A上的偏序关系一起为“偏序集”(partially ordered set,。et) ，记为A,复习2. 覆盖，哈斯图定义： 设为偏序集，对任意的x、yA，如果xy且不存在其他元素z，使xzy，则称元素y覆盖元素x。对于给定偏序集，它的覆盖关系是唯一的，所以可用覆盖的性质画出偏序集合图

2、，或称哈斯图，其作图规则为：小圆圈代表元素。如果xy，将代表y的小圆圈画在代表x的小圆圈之上。 (3)如果y 覆盖x，则在x与y之间用直线连结。复习3.上界，下界，最小上界，最大下界设为偏序集, BA, yA上界(upper bound): y是B的上界 x( xB xy )设 C = y | y是B的上界 , C的最小元称为B的最小上界,或上确界下界(lower bound): y是B的下界 x( xB yx )设 C = y | y是B的下界 , C的最大元称为B的最大下界,或下确界.说明：偏序集中，子集B不一定存在最小上界和最大下界，如果存在最大下界或者最小上界，一定是唯一的。例如，在由

3、图所示的偏序集中，a，b的最小上界是c，但没有最大下界；e，f的最大下界是d，但没有最小上界。fedcab的偏序集都有这样一个共同的特性，那就是在这些偏序集中，任何两个元素都有最小上界和最大下界。本章研究具有这种性质的偏序集。代数结构代数系统半群与群 12.环与域 13.格与代数7格与代数这一章将介绍另一类代数系统，这就是格。格论大体上是在1935年左右形成的，它不仅是代数学的一个分支，而且在近代序空间等方面也都有重要的作用。几何，半数字逻辑就是代数。第13章格与代数13.1 格的偏序定义与性质13.2与格的同态13.3 分配格与有补格13.4代数913.1 格的定义与性质格的偏序定义对偶原理

4、格的性质1.2.3.101 格的偏序定义定义13.1设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S为关于偏序的一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x与y的二元运算和。xy：表示x与y的最小上界 xy：表示x和y的最大下界。本章出现的和符号只代表格中的运算，而不再有其它的含义。格？abcde均是格！12格的实例例13.1 设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集格。x,ySn，xy是lcm(x,y)，即x与y的最小公倍数。xy是(x,y)，即x与y的最大公约数。给出格，和。格的实例S=是不是格？

5、例13.130156251满足格的定义。但xylcm(x,y)，xy(x,y)，例13.2 判断下列偏序集是否格,并说明理由。，其中P(B)是集合B的幂集。，其中Z是整数集,为小于或等于关系。偏序集的哈斯图如下：解答 :x,yP(B)，xy就是xy，xy就是xy。由于和运算在P(B)上是封闭的，所以xy，xyP(B).故为格。称,为B的幂集格。(2)是格。 x,yZ,xymax(x,y)，xymin(x,y)，它们都是整数。格？中的a,b没有最大下界。中的b,d有两个上界c和e,但没有最小上界。 (c)中的b,c有三个上界d,e,f,但没有最小上界。 (d)中的a,g没有最大下界。子群格例13

6、.2 设G是群，L(G)是G的所有子群的集合。即L(G) H|HG 对任意的H1,H2L(G)，H1H2也是G的子群，而是由H1H2生成的子群（即包含着H1H2的最小的子群）。在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。易见在L(G)中，H1H2就是H1H2，H1H2就是。2.格的对偶原理定义13.2 设f是含有格中元素以及符号、题。令f*是将f中的替换成，替换和成，替换成，替换成所得到题。称f*为f的对偶命题。例如 在格中令f是(ab)cc，则f*是(ab)cc。格的对偶原理：设f是含有格中元素以及符号、和题。若f对一切格为真，则f的对偶命题f*也对一切格为真

7、。对偶原理例如 对一切格L都有a,bL，aba(因为a和b的交是a的一个下界)那么对一切格L都有a,bL，aba说明许多格的性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。偏序关系上的两个二元运算和满足什么性质呢？交换律结合律幂等律结合律213 格的运算性质定理13.1 设是格，则运算和适合交换律、结合律、幂等律和吸收律，即(1)交换律 a,bL 有abbaabba结合律 a,b,cL 有(ab)ca(bc)幂等律 aL 有aaa吸收律 a,bL 有(ab)ca(bc)aaaa(ab)aa(ab)a定理13.2 设是具有两个二元运算的代数系统，若对于*和

8、运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得且a,bS有aba*b，abab。一个格，证明在S中*和运算都适合幂等律。在S上定义二元关系R，并证明R为偏序关系。思路(3)证明格。说明通过规定运算及其基本性质可以给出格的定义。格的代数系统等价定义根据定理13.2，可以给出格的另一个等价定义。定义13.3 设是代数系统，*和是二元运算，如果*和满换律，结合律和吸收律，则构成一个格(lattice)。说明格中的幂等律可以由吸收律推出。以后不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格L。格的性质定理13.3 设L是格，则a,bL 有ab aba abb先证 ab aba

9、由aa和ab可知，a是a,b的下界，故aab。显然又有aba。证明称性得aba。由再证 aba abb。根据吸收律有 bb(ba)由aba得 bba, 即abb。最后证abb ab。由aab得 aabb。定理13.4 设L是格，a,b,c,dL，若ab且cd，则acbd，acab accdacbd证明因此， acbd。 同理可证 acbd。分配不等式例13.4 设L是格，证明 a,b,cL 有a(bc)(ab)(ac)由 aa，bcb 得a(bc)ab由 aa，bcc 得a(bc)ac证明a(bc)(ab)(ac)从而得到说明在格中分配不等式成立。一般说来，格中的和运算并不是互相满足分配律的。

10、第13章格与代数13.1 格的定义与性质13.2与格的同态13.3 分配格与有补格13.4代数35定义13.4 设是格，S是L的非空子集，若S关于L中的运算和仍格，则称S是L的。例13.5例是一个格，其中L=a,b,h,取S1=a,b,d,fS ,S ,S 是格S2=c,e,g,hS3=h,e,b,aS4=a,b,c S5=a,b,c,d,e,g,h S6 =a,b,d,h判断哪些是L的123S4不是格一般地，S5, S6不是格？例题：如果运算是最小公倍数和最格，但如果运算是整除关系时，则是。大公约数时不是格的同态定义13.5 : 设和是格，： L1L2，若x,y L1，有 (x 1 y) (

11、x) 2 (y)， (x 1 y) (x) 2 (y)，则称 是从L1到L2 的同态，简称同态。40(1)设例13.6L1=2n|nZ+，L2=2n1|nN则L1和L2关于通常数的小于或等于关系格。令f:L1L2,f(x)=x-1验证f是L1到L2的同态证明：对任意的x,yL1，有xymax(x,y)f(xy)=f(max(x,y)=max(x,y)-1f(x)f(y)=(x-1)(y-1)=max(x-1,y-1)=max(x,y)-1即有f(xy)=f(x)f(y),同理f(xy)=f(min(x,y)=min(x,y)-1f(x)f(y)=(x-1)(y-1)=min(x-1,y-1)=

12、min(x,y)-1即f(xy)=f(x)f(y)所以f是L1到L2的同态(2)如图13.4中的格L1,L2和L3，若定义L2L1L3问f1和f2是否格同态？解：f1和f2都不是格同态.第13章格与代数13.1 格的定义与性质13.2与格的同态13.3 分配格与有补格13.4代数45分配格一般说来，格中运算对满足分配不等式，即a,b,cL，有a(bc)(ab)(ac)但是不一定满足分配律。满足分配律的格称为分配格。定义13.7 设是格，若a,b,cL，有a(bc)(ab)(ac)a(bc)(ab)(ac)则称L为分配格。说明 上面两个等式互为对偶式。在证明L为分配格时，只须证明其中的一个等式即

13、可。分配格？eebadbcb adccbcaa五角格d钻石格b(cd)=b e=b (bc)(b d)=a a=ac (b d)=c a=c(c b) (c d)=e d=d47分配格的判别定理13.12 设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的。证明推论略。(1) 小于五元的格都是分配格。(2) 任何一条链都是分配格。eebdbdccaa五角格钻石格例13.9说明下图中的格是否为分配格，为什么？解：L1, L2和L3都不是分配格。a,b,c,d,e是L1的a,b,c,e,f是L2的a,b,c,e,f是L3的，并且同构于钻石格。，并且同构于五角格.，也同构于钻石格。定理1

14、3.7格L是分配格当且仅当a,b,cL,ab=ac且ab=ac b=c.证:必要性。a,b,cL,有 b=b(ab)=b(ac)=(ba)(bc)=(ac)(bc)=(ab)c=(ac)c=c(吸收律,交换律)(已知条件代入) (分配律)(交换律)(分配律)(已知条件代入)(交换律,吸收律)充分性。（反证法）假若a,b,cL,有ab=ac且ab=ac 成立，而L不是分配格.根据定理13.6，L中必含有与钻石格或五角格同构的b=c。假设L中含有与钻石格同构的,且该为u,v,x,y,z,其中u为它的最小元,v为它的最大元。从而推出 xy=xz=u,但yz,与已知vxy=xz=v。x对五角格的情况同

15、理可证。uzy使用定理13.7也可以判别一个格是否为分配格。在L1中有在L2中有在L3中有bc=bd,bc=be, cb=cd,bc=bd,bc=be, cb=cd,但cd但ce但bd有补格全上界、全下界有界格及其性质补元有补格53格的全下界和全上界定义13.8 设L是格，若存在aL使得xL有ax，则称a为L的全下界；若存在bL使得xL有xb，则称b为L的全上界。命题 格L若存在全下界或全上界，一定是唯一的。证明 以全下界为例，假若a1和a2都是格L的全下界,则有a1a2和a2a1。称性必有a1a2。根据偏序关系的记法 将格L的全下界记为0，全上界记为1。有界格定义13.9 设L是格，若L存在

16、全下界和全上界，则称L为有界格，并将L记为。说明 有限格L一定是有界格。举例例：设S=2，3，4，100，对于普通的数之间的小于或等于关系，S，是一个格，其全上界1=100，全下界0=2。设L是n，且La1,a2,an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是有界格。有限格有界格有界格的性质定理13.8 设是有界格，则aL有a00a0aa1aa11由 a00 和 0a0 可知 a00。在有界格中，全下界0是关于运算的零元，运算的全上界1是关于运算的零元，运算的证明说明元。元。对偶原理 对于涉及到有界格题，如果其中含有全下界0或全上界1，在求该命题的对偶命题时，必须将0

17、替换成1，而将1替换成0。例如 a00 和 a11 互为对偶命题，a0a 和 a1a 互为对偶命题。有界格中的补元定义13.10 设是有界格，aL，若存在bL 使得ab0 和 ab1成立，则称b是a的补元。说明 若b是a的补元，那么a也是b的补元。换句话说，a和b互为补元。例13.9考虑下图中的四个格。L1中的a与c互为补元，其中a为全下界，c为全上界，b没有补元。L2中的a与d互为补元，其中a为全下界，d为全上界，b与c也互为补元。L3中的a与e互为补元，其中a为全下界，e为全上界，b的补元是c和 d，c的补元是b和d，d的补元是b和c。b,c,d每个元素都有两个补元。L4中的a与e互为补元

18、。其中a为全下界。e为全上界。b的补元是c和 d，c的补元是b，d的补元是b。有界格中补元的说明在任何有界格中，1b a0全下界0与全上界1互补。对于其他元素，可能存在补元，也可能不存在补元。如果存在补元，可能是唯一的，也可能是多个补元。例如,在图所示的格中c没有补元,d和d.有两个补元b和e,e有两个补元a对于有界分配格，如果一个元素存在补元，则一定是唯一的。有界分配格中补元唯一定理13.9设是有界分配格。若aL，且对于a存在补元b，则b是a的唯一补元。证明 假设cL也是a的补元，则有ac1，ac0又知b是a的补元，故ab1，ab0从而得到acab，acab由于L是分配格，从而有b=b(ba

19、)=b(ca)=(bc)(ba)=(bc)(ac)=(ba)c=(ac)c=c有补格的定义定义13.11 设是有界格，若L中所有元素都有补元存在，则称L为有补格。L2,L3和L4是有补格，L1不是有补格。L2和L3是有补格，L1不是有补格。第13章格与代数13.1 格的定义与性质13.2与格的同态13.3 分配格与有补格13.4代数6313.4代数1.2.3.4.5.6.代数代数的性质尔代数有限代数表达式函数641.代数定义13.12 如果一个格是有补分配格，则称它为布或在代数。代数中，每个元素都存在着唯一的补说明元。可以把求补元的运算看作是代数中的一代数标记为，为求补运算, aB，a是a的补

20、元。例13.11设S1101,2,5,10,11,22,55,110是110的正,lcm分别表示求最大公约数和最因子集合。令小公倍数的运算。问是否代数？为什么？解答 证明容易验证格。x,y,zS110，有(x,y)S110lcm(x,y)S110封闭性(x,y)(y,x)交换律lcm(x,y)lcm(y,x)(x,y),z)(x,(y,z)结合律lcm(lcm(x,y),z)lcm(x,lcm(y,z)(x,lcm(x,y)x吸收律lcm(x,(x,y)x证明 是分配格。易验证 x,y,zS110 有(x,lcm(y,z)lcm(x,y),(x,z)证明 是有补格。1 为S110中的全下界11

21、0为S110中的全上界1和110互为补元，2和55互为补元，5和22互为补元，10和11互为补元。综上所述，为代数。集合代数例13.12 设B为任意集合,证明B的幂集格代数，称为集合代数。证明 P(B)关于和格，因为和运算满换律、结合律和吸收律。由于和互相可分配，因此P(B)是分配格，且全下界是空集,全上界是B。根据绝对补的定义，取全集为B，xP(B)，x是x的补元。从而证明P(B)是有补分配格，即代数。2.代数的性质定理13.10 设是(1) aB，(a)a(2) a,bB，(ab) ab,(ab)ab说明 (1)称为双重否定律。代数，则(2)称为德律。命题代数与集合代数的双重否定律与德际上

22、是这个定理的特例。律实可以证明德律对有限个元素也是正确的。证明 (1) (a)是a的补元，a也是a的补元。由补元的唯一性得(a)a。(2) a,bB，(ab)ab,(ab)ab(ab)(ab) (aab)(bab) (1b)( a1) 11 1 (ab)(ab) (aba)(abb) (0b)(a0) 000所以ab是ab的补元，根据补元的唯一性有(ab)ab同理可证(ab)= ab。代数系统分运算满换任何两个元素都有最大下界和最小上界律，结合律，吸收律？存在全上界和全下界满足分配律每个元素有补分配格有补格同时满足71代数（格）有界格格偏序集别满足代数系统定义的代数定义13.13设是代数系统，

23、*和是二元运算。若*和运算满足：(1)交换律，即a,bB 有a*bb*a，abba(2)分配律，即a,b,cB有a*(bc)(a*b)(a*c)a(b*c)(ab)*(ac)同一律，即存在0,1B，使得aB 有(3)a*1a，a0a(4)补元律，即aB,存在aB，使得a*a0，则称是一个aa1代数。代数系统分运算满换任何两个元素都有最大下界和最小上界律，结合律，吸收律运算满换存在全上界和全下界律，分配律，同一律，补元律满足分配律每个元素有补分配格有补格同时满足73代数（格）有界格格偏序集别满足关于代数定义的说明元的性质，这里的1是元。所谓同一律就是指运算含有*运算的元，0是运算的可以证明1和0

24、分别也是和*运算的零元。 aB有a1 (a1)*1 1*(a1) (aa)*(a1)（同一律）（交换律）（补元律） (a*a)(a*a) (a*1)(a*1) 分配律） a(a*1) aa 1同理可证 a*00。（等幂律）（同一律）（补元律）关于代数定义的说明定义13.13设是代数系统，*和是二元运算。若*和运算满足：交换律，分配律，同一律，补元律，则称是一个所有元素都有补元，则一定是有补格。代数。为证明以上定义的是代数，只需先证明它是一个格（有补分配格即为代数，而有补分配已满足），即证明*和运算满足结合律和吸收律（交换律已满足）。3.尔代数定义13.14设为代数，若AB且A含有元素0和1，并

25、且对、运算封闭，那么为的尔代数。例13.14：设s110=1,2,5,10,11,22,55,110是110的正, lcm分别表示两个数的最大公约因子集合，令数和最小公倍数的运算。求的80例13.14：设s30=1,2,3,5,6,10,15,30是30的正, lcm分别表示两个数的最因子集合，令大公约数和最小公倍数的运算。求的尔代数。解：1,301,2, 15,301, 5, 6, 301, 3,10,301,2,3,5,6,10,15,301,2, 5, 6, 15, 30(不是，不是分配格)81例13.14：设s110=1,2,5,10,11,22,55,110是110的正因子集合，令, lcm分别表示两个数的最大公约数和最小公倍数的运算。求的尔代数。解：1,1101,2, 55,110