离散数学代数系统公开课获奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第6章代数系统,第一节代数系统一般概念,第二节同态和同构,第三节同余关系,第四节商代数和积代数,第五节经典代数系统,第1页,第一节代数系统一般概念,1、代数系统定义,2、代数系统满足条件,3、子代数系统,4、同类型代数系统,第2页,1、代数系统定义,X:非空集合,:X上运算非空集合,V=:代数系统,1,，,2,，,n,有限代数系统,|X|为V阶,解释：一种非空集合X,连同若干个定义在该集合上运算1，2，n所构成系统称为代数系统。,第3页,2、代数系统满足条件,（1）非空集合X；,（2）有某些建立在集合X上运算；,（3）这些运算在集合X上是封闭。,第4页,代数系统举例,是,是,第5页,代数系统举例,N,4,=0，1，2，3,i+,4,j=(i+j)(mod4),问：是代数系统吗？,+,4,0,1,2,3,0,1,2,3,验证+4在N4集合上与否满足封闭性,0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2,由运算表可知运算满足封闭性,是代数系统,第6页,代数系统举例,设A=1，2，3，4，6，12,A上运算*定义为：a*b=|a-b|,（1）写出二元运算运算表；,（2）能构成代数系统吗？,第7页,解答,由运算表可知*运算在集合A上不封闭,因此：不能构成代数系统,*,1,2,3,4,6,12,1,2,3,4,6,12,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,第8页,3、子代数系统,V=:代数系统,S,S,S,每一种运算 在S上均封闭,V=是一种代数系统,V为V子代数系统,子系统或子代数,第9页,子代数系统举例,是一种代数系统,设E：偶数集合,则：是子代数系统。,第10页,4、同类型代数系统,V,1,=:代数系统,V,2,=:代数系统,存在一种双射函数f:1 2,每一种1和f()2具有相似阶,同元运算,V,1,和V,2,是同类型代数系统,类型映射,f,第11页,同类型代数系统举例,V,1,=和V,2,=是同类型代数系统吗？其中：,i+,m,j=(i+j)(mod m),i,m,j=(i,j)(mod m),第12页,解答,双射函数（类型映射）f:,f(+m)=+,f(m)=,且+m和+、m和均为二元运算,因此：V1=和V2=是同类型代数系统。,第13页,同类型代数系统举例,V,1,=和V,2,=是同类型代数系统吗？,V,1,=和V,2,=是同类型代数系统吗？其中：“-”为取负运算。,（不是）,（不是）,不存在双射函数,不是同元运算,不是同元运算,第14页,第二节同态和同构,一、同态,二、同构,第15页,一、同态,1、同态定义,2、同态特点,3、满同态、单一同态、自同态,第16页,1、同态定义,同类型代数系统,A上二元运算,B上二元运算,存在一种映射g：AB,对任意a,bA,g(ab)=,g(a),g(b),*,运算象,象运算,从到一种同态映射,与同态,第17页,同态一般定义(略),设V1=，V2=是两个同类型代数系统；f:12为类型映射，假如存在函数 g：S1S2，使得对任意n元运算1及任意元素a1,a2,anS1均有：,g()=f(),则称V1与V2同态。,第18页,解释,两个代数系统同态：,（1）两个代数系统,同类型,；,（2）,运算象=象运算,第19页,2、同态特点,（1）g映射可以是内射、单射、满射、双射；,（2）g(S1)S2,像点集,单一同态,满同态,同构,第20页,同态示意图,S,1,x,1,x,2,x,3,S,2,g,g(x,1,)=y,1,g(x,2,)=y,1,g(x,3,)=y,3,y,1,y,3,g(x,1,x,3,)=,g(x,1,)*g(x,3,)=,x,1,x,3,y,1,*y,3,y,1,*y,3,g(x,2,x,3,)=,g(x,2,)*g(x,3,)=,y,1,*y,3,x,2,x,3,g(,S,1,),第21页,同态举例,证明：和是同态，其中：,B=正，负，零，*运算运算表如下：,*,正,负,零,正,正,负,零,负,负,正,零,零,零,零,零,第22页,解答,(1)显然,和是同类型；,(2)g:I,B,(3)验证运算象=象运算,g(I)=,i0,i0,j0时:g(i,j)=正，g(i)*g(j)=正*正=正,i0,j0,j=0时:g(i,j)=零，g(i)*g(j)=正*零=零,i0时:g(i,j)=负，g(i)*g(j)=负*正=负,i0,j0时:g(i,j)=正，g(i)*g(j)=负*负=正,i0时:g(i,j)=零，g(i)*g(j)=零*正=零,i=0,j0时:g(i,j)=零，g(i)*g(j)=零*负=零,i=0,j=0时:g(i,j)=零，g(i)*g(j)=零*零=零,第24页,同态举例,其中：g:N,0,1，且定义为：,g(n)=0,(n,N),证明：,同态,第25页,证明,（1）显然与同类型；,（2）运算象=象运算,对任意m,nN,运算象=g(mn)=0,象运算=g(m)g(n)=00=0,因此：与同态,第26页,3、满同态、单一同态、自同态,(1)假如g为满射函数，则称g为有关类型映射f满同态；,(2)假如g为单射函数，则称g为有关类型映射f单一同态；,(3)若V1=V2，且类型映射f为恒等函数，则称g为有关类型映射f自同态。,第27页,自同态举例,其中：g:I,I，且定义为：,g(n)=3n,(n,I),证明：,自同态,第28页,证明,(1)显然与同类型,且f(+)=+；,(2)运算象=象运算,对任意m,nN,运算象=g(m+n),=3(m+n)=3m+3n,=g(m)+g(n)=象运算,因此：与同态,且是自同态。,第29页,满同态举例,证明：,U=,V=,满同态,g:IN,m,对于所有iI,有：,g(i)=(i)(modm),第30页,证明,类型映射f定义为：f(+)=+,m,f(,)=,m,(1)显然U=和V=同类型,(2)运算象=象运算,对任意x,y,I:,g(x+y)=g(x)+,m,g(y),g(x,y)=g(x),m,g(y),第31页,证明: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),第32页,证明:g(x y)=g(x)m g(y),g(xy),=(xy)(mod m),=(x)(mod m)(y)(mod m)(mod m),=(x)(mod m)m(y)(mod m),=g(x)m g(y),因此：U=和V=同态,第33页,证明g是满射函数,对于任意x Nm,均有xI，使得：,g(x)=(x)(mod m)=x,因此：U=和V=是满同态,第34页,满同态特点,满同态对性质保持是,单方向,，即：,与满同态,性质,，均保持,互换律,结合律,分派律,吸取律,幺,元,零,元,逆,元,等幂元,第35页,互换律、结合律,设与满同态，则：,（1）若运算可互换，则*运算也可互换；,（2）若运算可结合，则*运算也可结合；,第36页,分派律,V,1,=,V,2,=,满同态,f:类型映射,*,1,1,*对可分派,f(*)对f()也可分派,2,第37页,幺元、零元、逆元,设与满同态，则：,(1)若,有幺元e，则*有幺元g(e);,(2)若,有零元,，则*有零元g(,);,(3)若x,X有逆元x,-1,则g(x)Y有逆元g(x,-1,),第38页,满同态特点举例,和满同态，则：,(1)可互换，f()=+3也可互换；,(2)可互换，f()=3也可互换；,(3)可结合，则f(+)+3也可结合；,(4)可结合，则f()3也可结合；,第39页,满同态举例（续）,(5)对“”存在e=0,则:,对“+,3,”存在e=g(0)=0;,(6)对“,”存在e=1,则:,对“,3,”存在e=g(1)=1;,(7)对“,”存在零元,=0,则:,对“,3,”存在零元=g(0)=0;,第40页,(8)对“”，8逆元是-8,则:,对“,+,3,”,g(8)=,2,g(-8)=g(-9+1)=,(-9+1)(mod3)=1(mod3)=,1,满同态举例（续）,2,+,3,1=(2+1)(mod3)=0=e,2和1互为逆元,第41页,单一同态举例,证明：,单一同态,实数集合,g:RR,对于x,R,g(x)=2,x,第42页,证明,(1)显然和同类型,(2)运算象=象运算,对于任意x,y,R，有：,g(x+y),=2,x+y,=2,x,2,y,=g(x),g(y),(3)g映射是单射函数,y=2,x,第43页,定理,V,1,=,V,2,=,g为同态映射,V,3,=为V,2,=子系统,象点集,V,1,同态象点,第44页,推论,g为同态映射,性质,同态象点均保持,第45页,二、同构,1、同构定义,2、同构特点,3、自同构,第46页,1、同构定义,同类型代数系统,A上二元运算,B上二元运算,存在一种双射映射g：AB,对任意a,bA,g(ab)=,g(a),g(b),*,运算象,象运算,从到,一种同构映射,与同构,第47页,同构一般定义,V,1,=,V,2,=,同类型代数系统,f:,1,2,类型映射,存在一种双射映射g：G1G2,对任意n元运算,1,任意元素a,1,a,2,a,n,G,1,(),g(,)=,f,(,),V,1,与V,2,同构,第48页,同构满足条件,（1）同类型,（2）g为双射函数（|,S,1,|,S,2,|）,（3）运算象象运算,第49页,同构举例,S=4,5,6,运算见表(a),P=1,2,3,运算*见表(b),则与同构。,4,5,6,4,4,5,4,5,4,5,5,6,4,5,6,*,1,2,3,1,1,2,1,2,1,2,2,3,1,2,3,表(a),表(b),第50页,解答,（1）显然与同类型；,（2）寻找双射函数g：SP,措施：特异元素对应特异元素,在中e=6,在中e=3,g(6)=3,g(5)=2,g(4)=1,g(5)=1,g(4)=2,或者,g,1,(4)=1,g,1,(5)=2,g,1,(6)=3,g,2,(4)=2,g,2,(5)=1,g,2,(6)=3,第51页,（3）运算象象运算,g,1,(4)=1,g,1,(5)=2,g,1,(6)=3,例：g(45)=g(5)=2,g(4)*g(5)=1*2=2,g,2,(4)=2,g,2,(5)=1,g,2,(6)=3,例：g(46)=g(4)=2,g(4)*g(6)=2*3=2,g,1,、g,2,均为同构映射,第52页,变换运算表措施,g,1,一致,g,2,1、2列互换,1,2行互换,一致,第53页,同构举例,S=a,b,c,d,运算见表(a),P=1,2,3,4,运算*见表(b),则与同构。,a,b,c,d,a,d,a,b,d,b,d,b,c,d,c,a,d,c,c,d,a,b,a,a,表(a),*,1,2,3,4,1,2,2,2,4,2,1,1,4,2,3,3,2,3,1,4,1,1,3,4,表(b),第54页,解答,（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,第55页,变换运算表,g,1,2列互换,2,4列互换,1,2行互换,2,4行互换,一致,第56页,2、同构特点,（1）g为双射函数；,（2）g(X)=Y,S,1,x,1,x,2,S,2,g,x,1,x,2,g(,x,1,)*g(,x,1,),g(,x,1,),g(,x,2,),第57页,同构对运算保持相似性质,设与同构，则：,(1)若有幺元e,则*有幺元g(e),反之亦然；,(2)若有零元,则*有零元g(),反之亦然；,(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1),反之亦然；,(4)若运算可互换,则*运算也可互换,反之亦然；,(5)若运算可结合,则*运算也可结合,反之亦然；,第58页,3、自同构,若V1=V2，且类型映射f为恒等函数，则称g为有关类型映射f自同构。,第59页,同构举例,证明：,同构,给定：g:R,+,R,g(x)=lnx,第60页,证明,(1)显然和同类型；,(2)g(x)=lnx是双射函数；,(3)运算象象运算:,对于任意a,bR+,g(ab)=ln(ab)=lna+lnb=g(a)+g(b),因此：和同构。,第61页,第三节同余关系,一、代换性质,二、同余关系,第62页,一、代换性质,V=:代数系统,R:G上等价关系,:n元运算,对任意a,1,b,1,a,2,b,2,a,n,b,n,G,a,1,Rb,1,a,2,Rb,2,a,n,Rb,n,(),(),R,R有关具有代换性质,第63页,代换性质举例,为代数系统，I中等价关系如下：对任意a,bI，,aRb|a|=|b|,问：等价关系R对于运算和与否具有代换性质？,第64页,解答,（1）对加法运算“”：,设a、-a、b,I,|a|=|-a|,aR(-a),|b|=|b|,bRb,|,a+b|-a+b|,(a+b)(-a+b),R有关“”不具有代换性质,第65页,解答（续）,（2）对乘法运算“”：,设i1、i2、j1、j2 I,若i1Ri2 则|i1|=|i2|,若j1Rj2 则|j1|=|j2|,|i1j1|=|i2j2|(i1j1)R(i2j2),即：对于乘法运算“”来说，R具有代换性质。,第66页,二、同余关系,V=:代数系统,R:G上等价关系,R有关每一种运算都具有代换性质,R为上同余关系。,第67页,同余关系举例,为代数系统，在N上定义一种模m同余关系m,证明：m有关具有代换性质，且是上同余关系,第68页,证明,x,1,y,1,x,2,y,2,N,x,1,m,y,1,x,2,m,y,2,(x,1,+x,2,),m,(y,1,+y,2,),x,1,m,y,1,x,1,=p,1,m+r,1,y,1,=p,2,m+r,1,x,2,m,y,2,x,2,=q,1,m+r,2,y,2,=q,2,m+r,2,p,1,p,2,q,1,q,2,r,1,r,2,N,0r,1,、r,2,m-1,x,1,+x,2,=,p,1,m+r,1,+,q,1,m+r,2,=(p,1,+q,1,)m+(,r,1,+r,2,),y,1,+y,2,=,p,2,m+r,1,+,q,2,m+r,2,=(p,2,+q,2,)m+(,r,1,+r,2,),(x,1,+x,2,),m,(y,1,+y,2,),m,是同余关系,第69页,同余关系举例,给定代数系统V=，其中*是I上一元运算，定义为：,*(i)=i,2,(mod m)m,I,+,问：,m,是V上同余关系吗？,第70页,解答,设：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)=r2(mod m),*(i1)m*(i2),m有关*具有代换性质,m是上同余关系,第71页,定理,U=,V=,f:同态映射,R,f,:,X上二元关系,对于任意x,1,x,2,X,x,1,R,f,x,2,f(x,1,)=f(x,2,),R,f,是U上同余关系,第72页,证明,(1)R,f,是等价关系：,自反性：,对任意x,X,f(x)=f(x),xRx,对称性：,x,1,R,f,x,2,f(x,1,)=f(x,2,),f(x,2,)=f(x,1,),x,2,R,f,x,1,可传递性：,x,1,R,f,x,2,x,2,R,f,x,3,f(x,1,)=f(x,2,)f(x,2,)=f(x,3,),f(x,1,)=f(x,3,),x,1,R,f,x,3,第73页,证明（续）,(2)Rf有关具有代换性质：,x,1,y,1,x,2,y,2,X,x,1,R,f,y,1,x,2,R,f,y,2,(x,1,x,2,)R,f,(y,1,y,2,),f(x,1,x,2,)=f(y,1,y,2,),f(x,1,x,2,),f:同态映射,=f(x,1,)*f(x,2,),x,1,R,f,y,1,f(x,1,)=f(y,1,),=f(y,1,)*f(x,2,),x,2,R,f,y,2,f(x,2,)=f(y,2,),=f(y,1,)*f(y,2,),f:同态映射,=f(y,1,y,2,),(x,1,x,2,)R,f,(y,1,y,2,),R,f,是U上同余关系,第74页,第四节商代数和积代数,一、商代数,二、积代数,第75页,一、商代数,1、商代数定义,2、正则映射,第76页,1、商代数定义,R:代数系统V=上同余关系,:,V=有关R商代数,V/R,(1)对于x1,x2,X,x,1,R,x,2,R,=,x,1,x,2,R,(2)X/R,=x,R,|x,X,商集,第77页,证明,验证是一种代数系统,(1)封闭性：,任取x1R、x2R X/R,x,1,R,x,2,R,由定义,=x,1,x,2,R,在X上封闭,x,1,x,2,X,x,1,x,2,R,X/R,在X/R上封闭,x,1,R,x,2,R,X/R,第78页,证明（续）,(2),是良定,y,1,x,1,R,y,2,x,2,R,x,1,R,x,2,R,=y,1,R,y,2,R,x1Rx2R与等价类代表元素x1和x2选用无关,y,1,x,1,R,y,2,x,2,R,等价类定义,x,1,R,y,1,x,2,R,y,2,R为同余关系,R有关具有代换性质,x,1,x,2,R,y,1,y,2,x,1,x,2,R,=y,1,y,2,R,x,1,R,x,2,R,=y,1,R,y,2,R,由定义,第79页,商代数举例,设代数系统F=,其中A=a1,a2,a3,a4,a5,*和运算表如下：,*,a,1,a,4,a,3,a,2,a,3,a,2,a,3,a,4,a,1,a,4,a,2,a,3,a,5,a,1,a,5,R为A上等价关系,A/R=a,1,a,3,a,2,a,5,a,4,证明：,R是F上同余关系，并求F商代数。,第80页,证明,(1)R是F上同余关系,R有关*运算具有代换性质,R有关运算具有代换性质,(2)求F商代数,第81页,证明:R有关*具有代换性质,A/R=a,1,a,3,a,2,a,5,a,4,R=,a,1,Ra,1,:,*a,1,=a,4,(a,4,Ra,4,),*a,1,R*a,1,a,1,Ra,3,:,*a,1,=a,4,*a,3,=a,4,(a,4,Ra,4,),*a,1,R*a,3,a,3,Ra,1,:,*a,3,=a,4,*a,1,=a,4,(a,4,Ra,4,),*a,3,R*a,1,第82页,R有关*具有代换性质(续),a,3,Ra,3,:,*a,3,=a,4,(a,4,Ra,4,),*a,3,R*a,3,a,2,Ra,2,:,*a,2,=a,3,(a,3,Ra,3,),*a,2,R*a,2,a,2,Ra,5,:,*a,2,=a,3,*a,5,=a,1,(a,3,Ra,1,),*a,2,R*a,5,a,5,Ra,2,:,*a,5,=a,1,*a,2,=a,3,(a,1,Ra,3,),*a,5,R*a,2,第83页,R有关*具有代换性质(续),a,5,Ra,5,:,*a,5,=a,1,(a,1,Ra,1,),*a,5,R*a,5,a,4,Ra,4,:,*a,4,=a,2,(a,2,Ra,2,),*a,4,R*a,4,对任意x,y,A,xRy,*xR*y,R有关*具有代换性质,第84页,证明:R有关具有代换性质,a,1,Ra,1,:,a,1,=a,3,(a,3,Ra,3,),a,1,Ra,1,a,1,Ra,3,:,a,1,=a,3,a,3,=a,1,(a,3,Ra,1,),a,1,Ra,3,a,3,Ra,1,:,a,3,=a,1,a,1,=a,3,(a,1,Ra,3,),a,3,Ra,1,a,3,Ra,3,:,a,3,=a,1,(a,1,Ra,1,),a,3,Ra,3,a,2,Ra,2,:,a,2,=a,2,(a,2,Ra,2,),a,2,Ra,2,第85页,证明:R有关具有代换性质,a,2,Ra,5,:,a,2,=a,2,a,5,=a,5,(a,2,Ra,5,),a,2,Ra,5,a,5,Ra,2,:,a,5,=a,5,a,2,=a,2,(a,5,Ra,2,),a,5,Ra,2,a,5,Ra,5,:,a,5,=a,5,(a,5,Ra,5,),a,5,Ra,5,a,4,Ra,4,:,a,4,=a,3,(a,3,Ra,3,),a,4,Ra,4,对任意x,y,A,xRy,xR,y,R有关具有代换性质,第86页,F商代数,设F商代数为,A/R,a,1,a,3,a,2,a,5,a,4,a,1,R,a,2,R,a,4,R,*,R,R,a,1,R,a,2,R,a,4,R,*,R,(a,1,R,)=,*a,1,R,=a,4,R,a,4,R,*,R,(a,2,R,)=,*a,2,R,=a,3,R,=a,1,R,a,1,R,*,R,(a,4,R,)=,*a,4,R,=a,2,R,a,2,R,R,(a,1,R,)=,a,1,R,=a,3,R,R,(a,2,R,)=,a,2,R,=a,2,R,a,2,R,R,(a,4,R,)=,a,4,R,=a,3,R,=a,1,R,a,1,R,=a,1,R,a,1,R,第87页,2、正则映射,正则映射,R:集合G上等价关系,函数g:GG/R,g(x)=x,R,第88页,定理,R:上同余关系,g:XX/R,正则映射,g是从到商代数,满同态,自然同态,g(x)=x,R,第89页,证明,(1)显然与同类型；,(2)证明：运算象象运算,对任意x,y X,g(xy)(正则映射定义),=xyR (商代数定义),=xRyR (正则映射定义),=g(x)g(y),第90页,(3)g是满射函数：,任意xRX/R，,在X中至少有一种原象x与之对应，使得：g(x)=xR,g是满射函数,证明(续),第91页,自然同态举例,上例：求代数系统F=到F商代数为自然同态。,第92页,求解,自然同态g:,g(x)=x,R,g(,a,1,)=g(,a,3,)=,a,1,R,g(,a,2,)=g(,a,5,)=,a,2,R,g(,a,4,)=,a,4,R,A,a,1,a,2,a,3,a,4,a,5,A/R,a,1,R,a,2,R,a,4,R,g,第93页,定理,f:从到同态映射,R,f,:上同余关系:,xR,f,y,f(x)=f(y),g:从到自然同态,存在从到同构映射,g=f,第94页,示意图,x,x,Rf,商代数,g,f(x),f,同态象点,f(X),g=f,同构映射,第95页,证明,设映射：X/R ff(X)，且(xRf)=f(x),证明：,(1)显然同类型；,(2)是单射函数；,(3)是满射函数；,(4)运算象象运算,第96页,证明：是单射函数,单射即：象点相似证明原象相似,对任意x,yX,若(xRf)=(yRf)(由定义）,f(x)=f(y)(由xRfyf(x)=f(y),xRfy,xRf=yRf,是单射函数,第97页,证明：是满射函数,f:Xf(X)满同态映射,对任意y,f(X),必存在x,X,使得f(x)=y,又,(x,Rf,)f(x)=y,即：,对任意y,f(X)，必存在,x,Rf,X/R,f,使得：,(x,Rf,)y,是满射函数。,第98页,证明：运算象象运算,对任意x,y,X，有：,运算象(x,Rf,y,Rf,),(g(x)=x,Rf,）,=(g(x),g(y),(g为自然同态,运算象象运算),=(g(x,y),(g(x)=x,Rf,）,=(x,y,Rf,),(定义),=f(x,y),(f为同态映射,运算象象运算),f(x)*f(y),(定义),(x,Rf,)*(y,Rf,)象运算,是从,到同构映射。,第99页,证明：g=f,对任意x,X,g(x),=,(g(x),=(x,Rf,),=f(x),g=f,第100页,二、积代数,A,1,=,A,2,=,同类型代数系统,A,1,A,2,=,:,A,1,与A,2,积代数,定义为：,对任意,G,1,G,2,=,A,1,A,2,:A,1,A,2,因子代数,第101页,积代数举例,F,2,=,F,3,=,求：F,2,F,3,第102页,解答,N,2,=0,1,N,3,=0,1,2,则：N,2,N,3,=,设：F,2,F,3,=,第103页,+,23,、,23,运算表,+,23,=,=,23,=,=,第104页,第五节经典代数系统,一、半群,二、群,三、格,四、布尔代数,第105页,一、半群,1、半群,2、可互换半群,3、独异点（含幺半群）,4、可互换含幺半群,5、子半群,6、循环半群,第106页,1、半群,:代数系统,*:二元运算,*运算是可结合,:半群,第107页,2、可互换半群,:半群,*运算是可互换,:可互换半群,第108页,3、独异点（含幺半群）,:半群,*运算有,幺元e,:含幺半群,独异点,第109页,4、可互换含幺半群,:,独异点,*运算是可互换,S,*:可互换含幺半群,第110页,半群举例,如下各代数系统与否为半群？若是半群，是什么半群？,(1),(2),(3)，其中S为非空集合。,(4)其中S为非空集合。,半群,可互换半群,含幺半群,e=0,可互换含幺半群,半群,可互换半群,含幺半群,e=1,可互换含幺半群,半群,可互换半群,含幺半群,e=S,可互换含幺半群,半群,可互换半群,含幺半群,e=,可互换含幺半群,第111页,半群举例,I:整数集合，对于如下*运算，哪些代数系统是半群?,a*b=ab,a*b=a,a*b=a+ab,a*b=max(a,b),第112页,解答,对任意a,b,c,I,(a*b)*c=a,b,*c=(a,b,),c,=a,bc,，,a*(b*c)=a*b,c,=,，,不是半群,因此(a*b)*c a*(b*c)。,第113页,解答:,a*b=a,*封闭性是显然;,(a*b)*c=a*c=a,a*(b*c)=a*b=a，,*是可结合运算,是半群,第114页,解答:,a*b=a+ab,(a*b)*c=(a+ab)*c,=a+ab+(a+ab)c,=a+ab+ac+abc,a*(b*c)=a*(b+bc),=a+a(b+bc)=a+ab+abc,(a*b)*ca*(b*c),不是半群,第115页,解答:,a*b=max(a,b),(4)*封闭性是显然;,(,a,*,b,)*,c,=a,*(,b,*,c,),=,max(,a,b,c,)，,*是可结合运算,是半群,第116页,5、子半群,:半群,H,S,集合H在运算*作用下封闭,是,子半群,第117页,:含幺半群,H,S,集合H在运算*作用下封闭,是,子含幺半群,子含幺半群,e,H,第118页,子半群举例,例：是一种半群，*运算运算表如下：,问：,(1),(2),(3),(4),(5),是子半群吗？,子半群,含幺子半群,子半群,含幺子半群,子半群,子半群,不是子半群,第119页,子含幺半群举例,集合,A=,0,2,4,(1),是含幺半群;,(2),不是,子含幺半群。,第120页,解答,幺元是4，因此是独异点；,幺元是1。而1A,，因此不是子含幺半群。,第121页,定理,:,含幺半群,*运算表中任何两行或两列都是不相似,第122页,证明,a,b,S,ab,假设a行和b行完全相似,a*e=b*e,a=b,与ab矛盾,结论成立,第123页,定理,:可互换含幺半群,H:S等幂元所构成集合,是子含幺半群,第124页,证明,(1)证明eH,e*e=e,e是等幂元,e,H,(2)*在H上封闭,对任意a,b,H,a*b,H,a*b是等幂元,(a*b)*(a*b),（*运算可互换）,=(a*b)*(b*a),（*运算可结合）,=a*(b*b)*a,（b是等幂元）,=a*b*a,（*运算可互换）,=(a*a)*b,（a是等幂元）,=a*b,第125页,元素幂定义,在含幺半群中，任意元素a,S,它幂被定义为：,a,0,=e,a,1,=a,a,2,=a*a,a,k+1,=a,k,*a,第126页,6、循环半群,:半群,:含幺半群,存在一种元素gS,对任意aS均有一种对应nN,a=g,n,循环半群,循环含幺半群,生组员,第127页,循环含幺半群举例,设S=a,b,c,d，定义S中二元运算*，*运算运算表如下：,(1)证明是一种循环含幺半群，并给出它生组员；,(2)把中每一种元素都表到达生组员幂；,(3)列出中所有等幂元。,第128页,解答,(1)由运算表可知：e=a,b和d均为生组员,(2)生组员幂形式：,b,0,=a,b,1,=b,b,2,=b*b=c,b,3,=b,2,*b=c*b=d,d,0,=a,d,1,=d,d,2,=d*d=c,d,3,=d,2,*d=c*d=b,(3)a为等幂元,第129页,定理,每一种循环半群（或含幺循环半群）都是可互换半群（或可互换含幺半群）。,第130页,证明,:循环半群,g:生组员,对任意a,b,X,都存在m,n N,a=g,m,b=g,n,a*b,=g,m,*g,n,=g,m+n,=g,n+m,=g,n,*g,m,=b*a,*运算是可互换,是可互换半群,第131页,二、群,1、群定义,2、阿贝尔群,3、循环群,4、子群,第132页,1、群定义,（1）是代数系统；,（2）“*”运算满足结合律；,（3）中存在幺元e；,注意：,群中无零元,群,含幺半群,（4）中任意一种元素均有逆元素；,第133页,群举例,和是群吗？为何？,解：,:,0是零元，而零元是不可逆。,：,（1）是代数系统；,（2）存在幺元e=1;,（3）“”可结合；,（4）对任意实数x,x,-1,=1/x,不是,是,第134页,有限群和无限群,设是一种群，若集合S是有限集则称 是有限群，|S|称为有限群阶数。,若集合S是无限集则称 是无限群。,注意：群运算表中没有两行或两列是相似,第135页,定理,:群,对于任意a,bA,方程,a*x=b,y*a=b,在A中均有唯一解,第136页,证明,(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,=右式,第137页,证明（续）,（2）证明方程有唯一解：,假设方程有其他解分别为x1,y1,则：,a*x1=b,a-1*a*x1=a-1*b,(a-1*a)*x1=a-1*b,e*x1=a-1*b,x1=a-1*b,同理：y1 b*a-1,第138页,定理,:群,对于任意a,b,cA,(,a,*b=,a,*c)(b*a=c*,a,),消去律,b=c,第139页,证明,设a逆元是a,-1,，则：,a*b=a*c,a,-1,*,a*b=,a,-1,*a*c,(,a,-1,*,a)*b=(,a,-1,*a)*c,e,*b=e*c,b=c,同理：b*a=c*a,b=c,第140页,定理,对于任意a,bA，有：,(a*b),-1,=b,-1,*a,-1,:群,第141页,证明,由逆元定义：x*x-1=x-1*x=e,要证明：(a*b)-1=b-1*a-1即证明:,(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,第142页,2、阿贝尔群,:群,“*”:可互换,阿贝尔群,互换群,第143页,定理,是阿贝尔群充足必要条件是：对任意a,bA，有：,(a*b)*(a*b)=(a*a)*(b*b),:群,第144页,证明：必要性,已知：是阿贝尔群，证明：(a*b)*(a*b)=(a*a)*(b*b),证明：左式,(a*b)*(a*b)(“*”运算可互换，可结合),=(a*a)*(b*b),=右式,第145页,证明：充足性,已知：(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)*e,b*a=a*b,第146页,3、循环群,若群中每个元素均是它某个 元素a整数幂，则称是由a生成循环群。a称为,生成元素,。,第147页,定理,:有限循环群,a:生成元素,|G|=n,e:幺元,a,n,=e,G=a,a,2,a,3,a,n,=e,使a,n,=e最小正整数,元素a阶或周期,第148页,循环群举例,设G=0，1，2，3,（1）是循环群吗？,（2）找出生成元。,a+,4,b,=a+,4,b,第149页,解答,（1）,是循环群；,（2）生成元：1,3,1,1,=,1,1,2,=1+,4,1,2,1,3,=1,2,+,4,12+,4,1=,3,1,4,=,1,3,+,4,13+,4,1=,0,=e,1周期为4,第150页,解答（续）,生成元：3,3,1,=,3,3,2,=3+,4,3,2,3,3,=3,2,+,4,32+,4,3=,1,3,4,=,3,3,+,4,31+,4,3=,0,=e,3周期为4,第151页,4、变换群,A:非空集合,PA:从A到A所有双射函数集合,:函数复合运算,:群,变换群,|A|!,第152页,变换群举例,A=1,2,3,f,1,=,=I,A,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,P,A,=f,1,f,2,f,3,f,4,f,5,f,6,第153页,变换群举例（续）,（1）,在,P,A,上封闭；,（2）,可结合；,（3）幺元存在，e=,f,1,（4）每个元素均可逆：,f,1,-1,=,f,1,，f,2,-1,=,f,2,，,f,3,-1,=,f,3,，,f,4,-1,=,f,4,，,f,5,-1,=,f,6,，,f,6,-1,=,f,5,f,1,f,2,f,3,f,4,f,5,f,6,f,1,f,1,f,2,f,3,f,4,f,5,f,6,f,2,f,2,f,1,f,6,f,5,f,4,f,3,f,3,f,3,f,5,f,1,f,6,f,2,f,4,f,4,f,4,f,6,f,5,f,1,f,3,f,2,f,5,f,5,f,3,f,4,f,2,f,6,f,1,f,6,f,6,f,4,f,2,f,3,f,1,f,5,第154页,5、子群,是子群,:群,H,A,H,也是一种群,第155页,平凡子群,:群,是一种子群,H=e,或H=A,是平凡子群,第156页,判断子群措施,（1）含幺元；,（2）封闭性；,（3）每个元素均可逆；,第157页,定理,:群,H,A,H,是 子群充要条件是:,(1)a,b,Ha*bH,（封闭性）,(2)aHa,-1,H,（可逆性）,第158页,证明：充足性,封闭性、可逆性,是,子群,子群,H,A,封闭性,可逆性,H中存在幺元e,已知,已知,已知,由,(2)可逆性,aHa,-1,H,由,(1),封闭性,a*a,-1,H,eH,第159页,证明：必要性,是,子群,封闭性、可逆性,(1)封闭性,是,子群,群定义,*运算在H上封闭,第160页,证明：必要性（续）,(2)可逆性：,e:,群,中幺元,a逆元是,a,-1,中幺元就是幺元,是,子群,中必有幺元e,对于任意a,H,