离散数学代数系统ppt课件.ppt

《离散数学代数系统ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学代数系统ppt课件.ppt（205页珍藏版）》请在三一办公上搜索。

1、第6章代数系统,第一节代数系统的一般概念第二节同态和同构第三节同余关系第四节商代数和积代数第五节典型的代数系统,第一节代数系统的一般概念,1、代数系统的定义2、代数系统满足的条件3、子代数系统4、同类型的代数系统,1、代数系统的定义,X:非空集合,:X上运算的非空集合,V=:代数系统,1，2，n,有限代数系统,|X|为V的阶,解释：一个非空集合X,连同若干个定义在该集合上的运算1，2，n所组成的系统称为代数系统。,2、代数系统满足的条件,（1）非空集合X；（2）有一些建立在集合X上的运算；（3）这些运算在集合X上是封闭的。,代数系统举例,是,是,代数系统举例,N4=0，1，2，3,i+4j=(

2、i+j)(mod4)问：是代数系统吗？,验证+4在N4集合上是否满足封闭性,0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2,由运算表可知运算满足封闭性,是代数系统,代数系统举例,设A=1，2，3，4，6，12A上的运算*定义为：a*b=|a-b|（1）写出二元运算的运算表；（2）能构成代数系统吗？,解答,由运算表可知*运算在集合A上不封闭所以：不能构成代数系统,0,1,2,3,5,11,1,0,1,2,4,10,2,1,0,1,3,9,3,2,1,0,2,8,5,4,3,2,0,6,11,10,9,8,6,0,3、子代数系统,V=:代数系统,S,S S,每一个运算 在S上均封闭

3、,V=是一个代数系统,V为V的子代数系统,子系统或子代数,子代数系统举例,是一个代数系统设E：偶数集合则：是的子代数系统。,4、同类型的代数系统,V1=:代数系统,V2=:代数系统,存在一个双射函数f:1 2,每一个1和f()2具有相同的阶,同元运算,V1和V2是同类型的代数系统,类型映射,f,同类型的代数系统举例,V1=和V2=是同类型的代数系统吗？其中：i+mj=(i+j)(mod m)im j=(ij)(mod m),解答,双射函数（类型映射）f:f(+m)=+,f(m)=且+m和+、m和均为二元运算所以：V1=和V2=是同类型的代数系统。,同类型的代数系统举例,V1=和V2=是同类型的

4、代数系统吗？V1=和V2=是同类型的代数系统吗？其中：“-”为取负运算。,（不是）,（不是）,不存在双射函数,不是同元运算,不是同元运算,第二节同态和同构,一、同态二、同构,一、同态,1、同态的定义2、同态的特点3、满同态、单一同态、自同态,1、同态的定义,同类型的代数系统,A上的二元运算,B上的二元运算,存在一个映射g：AB,对任意的a,bA,g(ab)=,g(a),g(b),*,运算的象,象的运算,从到的一个同态映射,与同态,同态的一般定义(略),设V1=，V2=是两个同类型的代数系统；f:12为类型映射，如果存在函数 g：S1S2，使得对任意的n元运算1及任意的元素a1,a2,anS1均

5、有：g()=f()则称V1与V2同态。,解释,两个代数系统同态：（1）两个代数系统同类型；（2）运算的象=象的运算,2、同态的特点,（1）g映射可以是内射、单射、满射、双射；（2）g(S1)S2,像点集,单一同态,满同态,同构,同态示意图,S1,x1,x2,x3,S2,g,g(x1)=y1,g(x2)=y1,g(x3)=y3,y1,y3,g(x1x3)=,g(x1)*g(x3)=,x1x3,y1*y3,y1*y3,g(x2x3)=,g(x2)*g(x3)=,y1*y3,x2x3,g(S1),同态举例,证明：和是同态的，其中：B=正，负，零，*运算的运算表如下：,解答,(1)显然和是同类型的；(

6、2)g:IB,(3)验证运算的象=象的运算,g(I)=,i0,i0,i=0,正,负,零,(3)运算的象=象的运算,i0,j0时:g(ij)=正，g(i)*g(j)=正*正=正i0,j0,j=0时:g(ij)=零，g(i)*g(j)=正*零=零i0时:g(ij)=负，g(i)*g(j)=负*正=负i0时:g(ij)=零，g(i)*g(j)=零*正=零i=0,j0时:g(ij)=零，g(i)*g(j)=零*负=零i=0,j=0时:g(ij)=零，g(i)*g(j)=零*零=零,同态举例,其中：g:N0,1，且定义为：g(n)=0(nN),证明：,同态,证明,（1）显然与同类型；（2）运算的象=象的

7、运算对任意的m,nN运算的象=g(mn)=0象的运算=g(m)g(n)=00=0所以：与同态,3、满同态、单一同态、自同态,(1)如果g为满射函数，则称g为关于类型映射f的满同态；(2)如果g为单射函数，则称g为关于类型映射f的单一同态；(3)若V1=V2，且类型映射f为恒等函数，则称g为关于类型映射f的自同态。,自同态举例,其中：g:II，且定义为：g(n)=3n(nI),证明：,自同态,证明,(1)显然与同类型,且f(+)=+；(2)运算的象=象的运算对任意的m,nN运算的象=g(m+n)=3(m+n)=3m+3n=g(m)+g(n)=象的运算所以：与同态,且是自同态。,满同态举例,证明：

8、,U=,V=,满同态,g:INm,对于所有的iI,有：,g(i)=(i)(modm),证明,类型映射f定义为：f(+)=+m,f()=m(1)显然U=和V=同类型(2)运算的象=象的运算对任意的x,yI:g(x+y)=g(x)+m g(y)g(x y)=g(x)m g(y),证明:g(x+y)=g(x)+m g(y),g(x+y)=(x+y)(mod m)=(x)(mod m)+(y)(mod m)(mod m)=(x)(mod m)+m(y)(mod m)=g(x)+m g(y),证明:g(x y)=g(x)m g(y),g(xy)=(xy)(mod m)=(x)(mod m)(y)(mod

9、 m)(mod m)=(x)(mod m)m(y)(mod m)=g(x)m g(y)所以：U=和V=同态,证明g是满射函数,对于任意的x Nm,均有xI，使得：g(x)=(x)(mod m)=x 所以：U=和V=是满同态,满同态的特点,满同态对性质的保持是单方向的，即：,与满同态,的性质，均保持,交换律,结合律,分配律,吸收律,幺元,零元,逆元,等幂元,交换律、结合律,设与满同态，则：（1）若运算可交换，则*运算也可交换；（2）若运算可结合，则*运算也可结合；,分配律,V1=,V2=,满同态,f:类型映射,*1,1,*对可分配,f(*)对f()也可分配,2,幺元、零元、逆元,设与满同态，则：

10、(1)若有幺元e，则*有幺元g(e);(2)若有零元，则*有零元g();(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1),满同态的特点举例,和满同态，则：(1)可交换，f()=+3也可交换；(2)可交换，f()=3也可交换；(3)可结合，则f(+)+3也可结合；(4)可结合，则f()3也可结合；,满同态举例（续）,(5)对“”存在e=0,则:对“+3”存在e=g(0)=0;(6)对“”存在e=1,则:对“3”存在e=g(1)=1;(7)对“”存在零元=0,则:对“3”存在零元=g(0)=0;,(8)对“”，8的逆元是-8,则:对“+3”g(8)=2g(-8)=g(-9+1)=(-9+1

11、)(mod3)=1(mod3)=1,满同态举例（续）,2+3 1=(2+1)(mod3)=0=e,2和1互为逆元,单一同态举例,证明：,单一同态,实数集合,g:RR,对于xR,g(x)=2x,证明,(1)显然和同类型(2)运算的象=象的运算对于任意的x,yR，有：g(x+y)=2x+y=2x2y=g(x)g(y)(3)g映射是单射函数,y=2x,定理,V1=,V2=,g为同态映射,V3=为V2=的子系统,象点集,V1的同态象点,推论,g为同态映射,的性质,的同态象点均保持,二、同构,1、同构的定义2、同构的特点3、自同构,1、同构的定义,同类型的代数系统,A上的二元运算,B上的二元运算,存在一

12、个双射映射g：AB,对任意的a,bA,g(ab)=,g(a),g(b),*,运算的象,象的运算,从到的一个同构映射,与同构,同构的一般定义,V1=,V2=,同类型的代数系统,f:12,类型映射,存在一个双射映射g：G1G2,对任意的n元运算1,任意的元素a1,a2,anG1,(),g()=,g(a1),g(a2),g(an),f(),V1与V2同构,同构满足的条件,（1）同类型（2）g为双射函数（|S1|S2|）（3）运算的象象的运算,同构举例,S=4,5,6,运算见表(a)P=1,2,3,运算*见表(b)则与同构。,表(a),表(b),解答,（1）显然与同类型；（2）寻找双射函数g：SP方法

13、：特异元素对应特异元素在中e=6在中e=3,g(6)=3,g(5)=2,g(4)=1,g(5)=1,g(4)=2,或者,g1(4)=1,g1(5)=2,g1(6)=3g2(4)=2,g2(5)=1,g2(6)=3,（3）运算的象象的运算,g1(4)=1,g1(5)=2,g1(6)=3例：g(45)=g(5)=2g(4)*g(5)=1*2=2 g2(4)=2,g2(5)=1,g2(6)=3例：g(46)=g(4)=2g(4)*g(6)=2*3=2g1、g2均为同构映射,变换运算表的方法,g1,一致,g2,1、2列交换,1,2行交换,一致,同构举例,S=a,b,c,d,运算见表(a)P=1,2,3

14、,4,运算*见表(b)则与同构。,表(a),表(b),解答,（1）显然与同类型；（2）寻找双射函数g：SP由表(a)的第4行和表(b)的第1行可知：g(a)=2,g(b)=4在中c是等幂元在中3是等幂元,g(c)=3,g(a)=2,g(b)=4,g(c)=3,g(d)=1,变换运算表,g,1,2列交换,2,4列交换,1,2行交换,2,4行交换,一致,2、同构的特点,（1）g为双射函数；（2）g(X)=Y,S1,x1,x2,S2,g,x1x2,g(x1)*g(x1),g(x1),g(x2),同构对运算保持相同的性质,设与同构，则：(1)若有幺元e,则*有幺元g(e),反之亦然；(2)若有零元,则

15、*有零元g(),反之亦然；(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1),反之亦然；(4)若运算可交换,则*运算也可交换,反之亦然；(5)若运算可结合,则*运算也可结合,反之亦然；,3、自同构,若V1=V2，且类型映射f为恒等函数，则称g为关于类型映射f的自同构。,同构举例,证明：,同构,给定：g:R+R,g(x)=lnx,证明,(1)显然和同类型；(2)g(x)=lnx是双射函数；(3)运算的象象的运算:对于任意的a,bR+g(ab)=ln(ab)=lna+lnb=g(a)+g(b)所以：和同构。,第三节同余关系,一、代换性质二、同余关系,一、代换性质,V=:代数系统,R:G上的等

16、价关系,:n元运算,对任意的a1,b1,a2,b2,an,bn G,a1Rb1,a2Rb2,anRbn,(),(),R,R关于具有代换性质,代换性质举例,为代数系统，I中的等价关系如下：对任意的a,bI，aRb|a|=|b|问：等价关系R对于运算和是否具有代换性质？,解答,（1）对加法运算“”：设a、-a、b I,|a|=|-a|,aR(-a),|b|=|b|,bRb,|a+b|-a+b|,(a+b)(-a+b),R关于“”不具有代换性质,解答（续）,（2）对乘法运算“”：设i1、i2、j1、j2 I若i1Ri2 则|i1|=|i2|若j1Rj2 则|j1|=|j2|i1j1|=|i2j2|(

17、i1j1)R(i2j2)即：对于乘法运算“”来说，R具有代换性质。,二、同余关系,V=:代数系统,R:G上的等价关系,R关于每一个运算都具有代换性质,R为上的同余关系。,同余关系举例,为代数系统，在N上定义一个模m同余关系m证明：m关于具有代换性质，且是上的同余关系,证明,x1,y1,x2,y2N,x1 m y1,x2 m y2,(x1+x2)m(y1+y2),x1 m y1,x1=p1m+r1,y1=p2m+r1,x2 m y2,x2=q1m+r2,y2=q2m+r2,p1,p2,q1,q2,r1,r2N,0r1、r2m-1,x1+x2=,p1m+r1,+,q1m+r2,=(p1+q1)m+

18、(r1+r2),y1+y2=,p2m+r1,+,q2m+r2,=(p2+q2)m+(r1+r2),(x1+x2)m(y1+y2),m是同余关系,同余关系举例,给定代数系统V=，其中*是I上的一元运算，定义为：*(i)=i2(mod m)mI+问：m 是V上的同余关系吗？,解答,设：i1 m i2,证明：*(i1)m*(i2)令：i1=a1m+r,i2=a2m+r其中：a1,a2,rN,且0rm-1*(i1)=(a1m+r)2(mod m)=(a12m2+2a1mr+r2)(mod m)=r2(mod m)*(i2)=(a2m+r)2(mod m)=(a22m2+2a2mr+r2)(mod m)

19、=r2(mod m)*(i1)m*(i2)m关于*具有代换性质 m是上的同余关系,定理,U=,V=,f:同态映射,Rf:X上的二元关系,对于任意的x1,x2X,x1Rfx2,f(x1)=f(x2),Rf是U上的同余关系,证明,(1)Rf是等价关系：自反性：对任意的xXf(x)=f(x)xRx对称性：x1Rfx2f(x1)=f(x2)f(x2)=f(x1)x2Rfx1,可传递性：,x1Rfx2x2Rfx3,f(x1)=f(x2)f(x2)=f(x3),f(x1)=f(x3),x1Rfx3,证明（续）,(2)Rf关于具有代换性质：,x1,y1,x2,y2X,x1 Rf y1,x2 Rf y2,(x

20、1x2)Rf(y1y2),f(x1x2)=f(y1y2),f(x1x2),f:同态映射,=f(x1)*f(x2),x1 Rf y1,f(x1)=f(y1),=f(y1)*f(x2),x2 Rf y2,f(x2)=f(y2),=f(y1)*f(y2),f:同态映射,=f(y1y2),(x1x2)Rf(y1y2),R f是U上的同余关系,第四节商代数和积代数,一、商代数二、积代数,一、商代数,1、商代数的定义2、正则映射,1、商代数的定义,R:代数系统V=上的同余关系,:,V=关于R的商代数,V/R,(1)对于x1,x2X,x1R x2R=,x1x2R,(2)X/R,=xR|xX,商集,证明,验证

21、是一个代数系统(1)封闭性：任取x1R、x2R X/R,x1Rx2R,由定义,=x1x2R,在X上封闭,x1x2 X,x1x2R X/R,在X/R上封闭,x1Rx2R X/R,证明（续）,(2)是良定的,y1x1R,y2x2R,x1Rx2R=y1Ry2R,x1Rx2R与等价类的代表元素x1和x2的选取无关,y1x1Ry2x2R,等价类的定义,x1Ry1x2Ry2,R为同余关系,R关于具有代换性质,x1x2 R y1y2,x1x2R=y1y2R,x1Rx2R=y1Ry2R,由定义,商代数举例,设代数系统F=,其中A=a1,a2,a3,a4,a5*和的运算表如下：,R为A上的等价关系,A/R=a1

22、,a3,a2,a5,a4,证明：R是F上的同余关系，并求F的商代数。,证明,(1)R是F上的同余关系R关于*运算具有代换性质R关于运算具有代换性质(2)求F的商代数,证明:R关于*具有代换性质,A/R=a1,a3,a2,a5,a4R=,a1Ra1:,*a1=a4,(a4Ra4),*a1R*a1,a1Ra3:,*a1=a4,*a3=a4,(a4Ra4),*a1R*a3,a3Ra1:,*a3=a4,*a1=a4,(a4Ra4),*a3R*a1,R关于*具有代换性质(续),a3Ra3:,*a3=a4,(a4Ra4),*a3R*a3,a2Ra2:,*a2=a3,(a3Ra3),*a2R*a2,a2Ra

23、5:,*a2=a3,*a5=a1,(a3Ra1),*a2R*a5,a5Ra2:,*a5=a1,*a2=a3,(a1Ra3),*a5R*a2,R关于*具有代换性质(续),a5Ra5:,*a5=a1,(a1Ra1),*a5R*a5,a4Ra4:,*a4=a2,(a2Ra2),*a4R*a4,对任意的x,yA,xRy,*xR*y,R关于*具有代换性质,证明:R关于具有代换性质,a1Ra1:,a1=a3,(a3Ra3),a1Ra1,a1Ra3:,a1=a3,a3=a1,(a3Ra1),a1Ra3,a3Ra1:,a3=a1,a1=a3,(a1Ra3),a3Ra1,a3Ra3:,a3=a1,(a1Ra1)

24、,a3Ra3,a2Ra2:,a2=a2,(a2Ra2),a2Ra2,证明:R关于具有代换性质,a2Ra5:,a2=a2,a5=a5,(a2Ra5),a2Ra5,a5Ra2:,a5=a5,a2=a2,(a5Ra2),a5Ra2,a5Ra5:,a5=a5,(a5Ra5),a5Ra5,a4Ra4:,a4=a3,(a3Ra3),a4Ra4,对任意的x,yA,xRy,xRy,R关于具有代换性质,F的商代数,设F的商代数为A/Ra1,a3,a2,a5,a4a1R,a2R,a4R,*R(a1R)=,*a1R,=a4R,a4R,*R(a2R)=,*a2R,=a3R,=a1R,a1R,*R(a4R)=,*a4R

25、,=a2R,a2R,R(a1R)=,a1R,=a3R,R(a2R)=,a2R,=a2R,a2R,R(a4R)=,a4R,=a3R,=a1R,a1R,=a1R,a1R,2、正则映射,正则映射,R:集合G上的等价关系,函数g:GG/R,g(x)=xR,定理,R:上的同余关系,g:XX/R正则映射,g是从到商代数的满同态,自然同态,g(x)=xR,证明,(1)显然与同类型；(2)证明：运算的象象的运算对任意的x,y Xg(xy)(正则映射定义)=xyR(商代数定义)=xRyR(正则映射定义)=g(x)g(y),(3)g是满射函数：任意的xRX/R，在X中至少有一个原象x与之对应，使得：g(x)=xR

26、 g是满射函数,证明(续),自然同态举例,上例：求代数系统F=到F的商代数为的自然同态。,求解,自然同态g:g(x)=xRg(a1)=g(a3)=a1Rg(a2)=g(a5)=a2Rg(a4)=a4R,A,a1,a2,a3,a4,a5,A/R,a1R,a2R,a4R,g,定理,f:从到的同态映射,R f:上的同余关系:,xRfyf(x)=f(y),g:从到的自然同态,存在从到的同构映射,g=f,示意图,x,xRf,商代数,g,f(x),f,同态象点,f(X),g=f,同构映射,证明,设映射：X/R ff(X)，且(xRf)=f(x)证明：(1)显然同类型；(2)是单射函数；(3)是满射函数；(

27、4)运算的象象的运算,证明：是单射函数,单射即：象点相同证明原象相同对任意的x,yX若(xRf)=(yRf)(由的定义）f(x)=f(y)(由xRfyf(x)=f(y)xRfyxRf=yRf 是单射函数,证明：是满射函数,f:Xf(X)的满同态映射对任意的yf(X),必存在x X,使得f(x)=y又(xRf)f(x)=y即：对任意的yf(X)，必存在xRf X/Rf 使得：(xRf)y 是满射函数。,证明：运算的象象的运算,对任意的x,yX，有：运算的象(xRfyRf)(g(x)=xRf）=(g(x)g(y)(g为自然同态,运算的象象的运算)=(g(xy)(g(x)=xRf）=(xyRf)(的

28、定义)=f(xy)(f为同态映射,运算的象象的运算)f(x)*f(y)(的定义)(xRf)*(yRf)象的运算 是从到的同构映射。,证明：g=f,对任意的xXg(x)=(g(x)=(xRf)=f(x)g=f,二、积代数,A1=,A2=,同类型的代数系统,A1A2=:,A1与A2的积代数,定义为：,对任意的,G1G2,=,A1,A2:A1A2的因子代数,积代数举例,F2=F3=求：F2F3,解答,N2=0,1N3=0,1,2则：N2N3=,设：F2F3=,+23、23的运算表,+23,=,=,23,=,=,第五节典型的代数系统,一、半群二、群三、格四、布尔代数,一、半群,1、半群2、可交换半群3

29、、独异点（含幺半群）4、可交换含幺半群5、子半群6、循环半群,1、半群,:代数系统,*:二元运算,*运算是可结合,:半群,2、可交换半群,:半群,*运算是可交换,:可交换半群,3、独异点（含幺半群）,:半群,*运算有幺元e,:含幺半群,独异点,4、可交换含幺半群,:独异点,*运算是可交换,S,*:可交换含幺半群,半群举例,下列各代数系统是否为半群？若是半群，是什么半群？(1)(2)(3)，其中S为非空集合。(4)其中S为非空集合。,半群,可交换半群,含幺半群,e=0,可交换含幺半群,半群,可交换半群,含幺半群,e=1,可交换含幺半群,半群,可交换半群,含幺半群,e=S,可交换含幺半群,半群,可

30、交换半群,含幺半群,e=,可交换含幺半群,半群举例,I:整数集合，对于下列*运算，哪些代数系统是半群?a*b=ab a*b=a a*b=a+ab a*b=max(a,b),解答,对任意的a,b,cI(a*b)*c=ab*c=(ab)c=abc，a*(b*c)=a*bc=，,不是半群,所以(a*b)*c a*(b*c)。,解答:a*b=a,*的封闭性是显然的;(a*b)*c=a*c=a,a*(b*c)=a*b=a，*是可结合运算,是半群,解答:a*b=a+ab,(a*b)*c=(a+ab)*c=a+ab+(a+ab)c=a+ab+ac+abca*(b*c)=a*(b+bc)=a+a(b+bc)=

31、a+ab+abc(a*b)*ca*(b*c),不是半群,解答:a*b=max(a,b),(4)*的封闭性是显然的;(a*b)*c=a*(b*c)=max(a,b,c)，*是可结合运算,是半群,5、子半群,:半群,HS,集合H在运算*作用下封闭,是 的子半群,:含幺半群,HS,集合H在运算*作用下封闭,是 的子含幺半群,子含幺半群,eH,子半群举例,例：是一个半群，*运算的运算表如下：,问：(1)(2)(3)(4)(5)是的子半群吗？,子半群,含幺子半群,子半群,含幺子半群,子半群,子半群,不是子半群,子含幺半群举例,集合A=0,2,4(1)是含幺半群;(2)不是的子含幺半群。,解答,的幺元是4

32、，所以是独异点；的幺元是1。而1A,，因此不是的子含幺半群。,定理,:含幺半群,*运算表中任何两行或两列都是不相同的,证明,a,bS,ab,假设a行和b行完全相同,a*e=b*e,a=b,与ab矛盾,结论成立,定理,:可交换含幺半群,H:S的等幂元所构成的集合,是的子含幺半群,证明,(1)证明eH,e*e=e,e是等幂元,eH,(2)*在H上封闭,对任意的a,bH,a*bH,a*b是等幂元,(a*b)*(a*b),（*运算可交换）,=(a*b)*(b*a),（*运算可结合）,=a*(b*b)*a,（b是等幂元）,=a*b*a,（*运算可交换）,=(a*a)*b,（a是等幂元）,=a*b,元素的

33、幂的定义,在含幺半群中，任意元素aS,它的幂被定义为：a0=e a1=a a2=a*a a k+1=ak*a,6、循环半群,:半群,:含幺半群,存在一个元素gS,对任意的aS都有一个相应的nN,a=gn,循环半群,循环含幺半群,生成员,循环含幺半群举例,设S=a,b,c,d，定义S中的二元运算*，*运算的运算表如下：(1)证明是一个循环含幺半群，并给出它的生成员；(2)把中的每一个元素都表示成生成员的幂；(3)列出中所有的等幂元。,解答,(1)由运算表可知：e=ab和d均为生成员(2)生成员的幂的形式：b0=ab1=bb2=b*b=cb3=b2*b=c*b=d,d0=ad1=dd2=d*d=c

34、d3=d2*d=c*d=b(3)a为等幂元,定理,每一个循环半群（或含幺循环半群）都是可交换半群（或可交换含幺半群）。,证明,:循环半群,g:生成员,对任意的a,bX,都存在m,n N,a=gm,b=gn,a*b,=gm*gn,=gm+n,=gn+m,=gn*gm,=b*a,*运算是可交换的,是可交换半群,二、群,1、群的定义2、阿贝尔群3、循环群4、子群,1、群的定义,（1）是代数系统；（2）“*”运算满足结合律；（3）中存在幺元e；,注意：群中无零元,群,含幺半群,（4）中任意一个元素都有逆元素；,群举例,和是群吗？为什么？解：:0是的零元，而零元是不可逆的。：（1）是代数系统；（2）存在

35、幺元e=1;（3）“”可结合；（4）对任意实数x,x-1=1/x,不是,是,有限群和无限群,设是一个群，若集合S是有限集则称 是有限群，|S|称为有限群的阶数。若集合S是无限集则称 是无限群。,注意：群的运算表中没有两行或两列是相同的,定理,:群,对于任意的a,bA,方程,a*x=b,y*a=b,在A中都有唯一的解,证明,(1)证明方程有解：,x=a-1*b,y=b*a-1,方程的解是:,左式a*x,a*(a-1*b),（*运算可结合）,=(a*a-1)*b,=e*b,=b,=右式,左式y*a,(b*a-1)*a,（*运算可结合）,=b*(a-1*a),=b*e,=b,=右式,证明（续）,（2

36、）证明方程有唯一的解：假设方程有其他的解分别为x1,y1,则：a*x1=b a-1*a*x1=a-1*b(a-1*a)*x1=a-1*be*x1=a-1*bx1=a-1*b同理：y1 b*a-1,定理,:群,对于任意的a,b,cA,(a*b=a*c)(b*a=c*a),消去律,b=c,证明,设a的逆元是a-1，则：a*b=a*c a-1*a*b=a-1*a*c(a-1*a)*b=(a-1*a)*ce*b=e*cb=c同理：b*a=c*ab=c,定理,对于任意的a,bA，有：(a*b)-1=b-1*a-1,:群,证明,由逆元的定义：x*x-1=x-1*x=e要证明：(a*b)-1=b-1*a-1

37、即证明:(a*b)*(b-1*a-1)=(b-1*a-1)*(a*b)=e(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=a*a-1=e(b-1*a-1)*(a*b)=b-1*(a-1*a)*b=b-1*e*b=b-1*b=e,2、阿贝尔群,:群,“*”:可交换,阿贝尔群,交换群,定理,是阿贝尔群的充分必要条件是：对任意的a,bA，有：(a*b)*(a*b)=(a*a)*(b*b),:群,证明：必要性,已知：是阿贝尔群，证明：(a*b)*(a*b)=(a*a)*(b*b)证明：左式(a*b)*(a*b)(“*”运算可交换，可结合)=(a*a)*(b*b)=右式,证明

38、：充分性,已知：(a*b)*(a*b)=(a*a)*(b*b)证明：是阿贝尔群要证明是阿贝尔群，即证明*运算可交换，即：a*b=b*a(a*b)*(a*b)=(a*a)*(b*b)a-1*a*(b*a)*b*b-1=a-1*a*(a*b)*b*b-1 e*a*(b*a)*e=e*(a*b)*eb*a=a*b,3、循环群,若群中每个元素均是它的某个 元素a的整数幂，则称是由a生成的循环群。a称为的生成元素。,定理,:有限循环群,a:生成元素,|G|=n,e:幺元,an=e,G=a,a2,a3,an=e,使an=e的最小的正整数,元素a的阶或周期,循环群举例,设G=0，1，2，3（1）是循环群吗？

39、（2）找出生成元。,a+4b,=a+4b,解答,（1）是循环群；（2）生成元：1,311=112=1+4 1213=12+4 12+4 1=314=13+4 13+4 1=0=e1的周期为4,解答（续）,生成元：331=332=3+4 3233=32+4 32+4 3=134=33+4 31+4 3=0=e3的周期为4,4、变换群,A:非空集合,PA:从A到A的所有双射函数的集合,:函数的复合运算,:群,变换群,|A|!,变换群举例,A=1,2,3f1=,=IAf2=,f3=,f4=,f5=,f6=,PA=f1,f2,f3,f4,f5,f6,变换群举例（续）,（1）在PA上封闭；（2）可结合；

40、（3）幺元存在，e=f1（4）每个元素均可逆：f1-1=f1，f2-1=f2，f3-1=f3，f4-1=f4，f5-1=f6，f6-1=f5,5、子群,是的子群,:群,HA,H,也是一个群,平凡子群,:群,是的一个子群,H=e,或H=A,是的平凡子群,判断子群的方法,（1）含幺元；（2）封闭性；（3）每个元素均可逆；,定理,:群,HA,H,是 的子群的充要条件是:,(1)a,bHa*bH,（封闭性）,(2)aHa-1H,（可逆性）,证明：充分性,封闭性、可逆性,是 的子群,子群,HA,封闭性,可逆性,H中存在幺元e,已知,已知,已知,由(2)可逆性,aHa-1H,由(1)封闭性,a*a-1,H

41、,eH,证明：必要性,是 的子群,封闭性、可逆性,(1)封闭性,是 的子群,群的定义,*运算在H上封闭,证明：必要性（续）,(2)可逆性：,e:群中的幺元,a的逆元是a-1,中的幺元就是的幺元,是 的子群,中必有幺元e,对于任意的aH,e*a=a,e*a=a,e*a=e*a,消去律,e=e H,证明：必要性（续）,中a的逆元是a-1,中a的逆元就是中a的逆元,是 子群,对于任意的aH,必存在逆元a,a*a=e,a-1*a=e,a*a=a-1*a,消去律,a=a-1 H,定理,:群,HA,H,是 的子群的充要条件是:,对任意的a,bH,a*b-1 H,证明:必要性,是的子群,若a,bH，则a*b

42、-1 H,是的子群,对任意的a,bH,a-1,b-1 H,a*b-1H,可逆性,封闭性,证明:充分性,若a,bH，则a*b-1 H,是的子群,可逆性：,对任意的aH,由a,bHa*b-1 H,a*a-1 H,e H,H中存在幺元,对任意的aH,e*a-1 H,a-1 H,H中每个元素均可逆,证明:充分性(续),封闭性：,对任意的a,bH,可逆性,a,b-1H,由a,bHa*b-1 H,a*(b-1)-1 H,a*bH,*运算在H上封闭,子群举例,求出的所有子群。,解答,e=01-1=5,5-1=12-1=4,4-1=23-1=3,0-1=0(1)(2),(3)(4)是的子群。,拉格朗日定理,:

43、有限群,|G|=n,:的子群,|H|=m,m|n,m是n的因子,推论,任何素数阶的群不可能有非平凡子群。,三、格,1、偏序格2、格的性质3、特殊格,1、偏序格,:偏序集,对于任意的a,b L,a,b都有上确界和下确界,偏序格,ab,=LUBa,b,a*b,=GLBa,b,保联运算,保交运算,偏序格举例,S=a,b,c 问偏序集是偏序格吗？,解答,(s),a,b,c,a,b,a,c,b,c,a,b,c对任意的S1,S2(s)GLBS1,S2=a*b=S1S2LUBS1,S2=ab=S1S2偏序集是偏序格,偏序格举例,n:正整数S n:n的所有因子的集合:定义在S n上的整除关系，问：(1)(2)

44、(3)(4)是否为偏序格？,解答（1）,S6=1,2,3,6是偏序格。对于任意的a,b S6a*b=a和b的最大公约数；ab=a和b的最小公倍数；,解答（2）,S8=1,2,4,8是偏序格。,解答（3）,S24=1,2,3,4,6,8,12,24是偏序格。,解答（4）,S30=1,2,3,5,6,10,15,30是偏序格。,偏序格举例,判断以下的偏序集是否构成偏序格？,解答（1）,对于子集b,d：上界有两个：c,e而c,e没有偏序关系子集b,d没有上确界,不是偏序格,解答（2）,对于子集b,c：上界有三个：d,e,f而d,e没有偏序关系子集b,c没有上确界,不是偏序格,2、格的性质,（1）等幂

45、律（2）交换律（3）结合律（4）吸收律,（1）等幂律,:格任意的a,b L,均有：a*a=aaa=a,（2）交换律,:格任意的a,b L,均有：a*b=b*aab=ba,（3）结合律,:格任意的a,b,c L,均有：a*b*c=(a*b)*c=a*(b*c)abc=(ab)c=a(bc),（4）吸收律,:格任意的a,b L,均有：a*(ab)=aa(a*b)=a,3、特殊格,（1）有界格（2）有补格（3）分配格,*和运算的一般定义,对L的一个无穷子集，结论不一定成立,:格,S=a1,a2,an:L的一个有限子集,S的上确界和下确界均存在,LUB(S)=a1*a2*an,GLB(S)=a1a2a

46、n,（1）有界格,有限格是有界格,:格,L有最大元素和最小元素,有界格,有界格的界,最大元素:,1,最小元素:,0,:,有界格的性质,:有界格对于任意的a L：0 a 1 a0=a a*0=0 a1=1 a*1=a,（2）有补格,补元 有补格,补元,:有界格 a,bL,如果：a*b=0ab=1则称a和b互为补元。,0和1互为补元补元不唯一,补元举例,求图1、图2、图3、图4中各有界格的补元,解答（1）,a*b=bab=aa*c=cac=ab*c=0bc=a a,b,c都没有补元。,解答（2）,a*b=0ab=1a,b互为补元a*c=0ac=1 a,c互为补元b*c=0bc=1b,c互为补元 a

47、,b,c互为补元。,解答（3）,a*b=bab=aa*c=0ac=1 a,c互为补元b*c=0bc=1 b,c互为补元 a,b的补元是c;c的补元是a,b;,解答（4）,a*b=0ab=1 a,b互为补元b*c=0bc=1 b,c互为补元c*e=0ce=1 c,e互为补元a*e=0ae=1 a,e互为补元 a,c的补元是b,e;b,e的补元是a,c;d没有补元。,有补格,:有界格,每一个元素至少有一个补元,有补格,有补格举例,上例中：图1、图4不是有补格；图2、图3是有补格。,（3）分配格,:格对任意的 a,b,cL,都满足：a*(b c)=(a*b)(a*c)(*对可分配)a(b*c)=(ab)*(ac)(对*可分配),分配格,分配格举例,问图2、图3是否为分配格？,解答（1）,a*(bc)=a*1=a(a*b)(a*c)=00=0a*(bc)(a*b)(a*c)不是分配格。,解答（2）,a*(bc)=a*1=a(a*b)(a*c)=b0=ba*(bc)(a*b)(a*c)不是分配格。,四、布尔代数,一个有补分配格称为布尔代数，表示为：其中：是一个格；“”是B中的一元求补运算；0和1是格的界；,布尔代数具有格、有界格、有补格、分配格的全部性质,