离散数学代数系统课件

第第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上是上是封闭封闭的。的。代数系统举例代数系统举例I+(S)是是是是代数系统举例代数系统举例N N4 4=0=0，1 1，2 2，3,i+3,i+4 4j=(i+j)(mod4)j=(i+j)(mod4)问：问：N 是代数系统吗？是代数系统吗？+4 401230123验证验证+4在在N4集合上是否满足封闭性集合上是否满足封闭性0123123023013012由运算表可知运算满足封闭性由运算表可知运算满足封闭性是代数系统是代数系统代数系统举例代数系统举例设设A=1A=1，2 2，3 3，4 4，6 6，1212A A上的运算上的运算*定义为：定义为：a*b=|a-b|a*b=|a-b|（1 1）写出二元运算的运算表；写出二元运算的运算表；（2 2）能构成代数系统吗？能构成代数系统吗？解答解答由由运算表可知运算表可知*运算在集合运算在集合A A上不封闭上不封闭所以：所以：不能构成代数系统不能构成代数系统*1234612123461201235111012410210139321028543206111098603、子代数系统、子代数系统V=:代数系统代数系统SS S每一个运算每一个运算 在在S上均封闭上均封闭V=是一个代数系统是一个代数系统V为为V的子代数系统的子代数系统子系统或子代子系统或子代数数子代数系统举例子代数系统举例是一个代数系统是一个代数系统设设E E：偶数集合偶数集合则：则：是是的的子代数系统。子代数系统。4、同类型的代数系统、同类型的代数系统V1=:代数系统代数系统V2=:代数系统代数系统存在一个双射函数存在一个双射函数f:1 2每一个每一个1和和f()2具有相同的阶具有相同的阶同元运算同元运算V1和和V2是同类型的代数系统是同类型的代数系统类型映射类型映射f同类型的代数系统举例同类型的代数系统举例V V1 1=N=和和V V2 2=R,+,=是同是同类类型的代数系统吗？其中：型的代数系统吗？其中：i+i+m mj j=(i+j)(mod m)=(i+j)(mod m)i i m m j=(ij=(i j)(mod m)j)(mod m)解答解答双射双射函数（类型映射）函数（类型映射）f:f:f(+f(+m m)=+,f()=+,f(m m)=)=且且+m m和和+、m m和和 均为二元运算均为二元运算所以：所以：V V1 1=N=和和V V2 2=R,+,=是同类型的代数系统。是同类型的代数系统。同类型的代数系统举例同类型的代数系统举例V V1 1=N=和和V V2 2=I,+,=是同类型的是同类型的代数系统吗？代数系统吗？V V1 1=I,+=和和V V2 2=R,+,=是同类型是同类型的代数系统吗？其中：的代数系统吗？其中：“-”-”为取负运为取负运算。算。（不是）（不是）（不是）（不是）不存在双射函数不是同元运算不是同元运算第二节第二节 同态和同构同态和同构一、同态一、同态二、同构二、同构一、同态一、同态1、同态的定义、同态的定义2、同态的特点、同态的特点3、满同态、单一同态、自同态、满同态、单一同态、自同态1、同态的定义、同态的定义同类型的代数系统同类型的代数系统A上的二元运算上的二元运算B上的二元运算上的二元运算存在一个映射存在一个映射g：AB对任意的对任意的a,bAg(a b)=g(a)g(b)*运算的象运算的象象的运算象的运算从从到到的一个同态映射的一个同态映射与与同态同态同态的一般定义同态的一般定义(略略)设设V1=，V2=是两个是两个同类型的代数系统；同类型的代数系统；f:12为类型映射，为类型映射，如果存在函数如果存在函数 g：S1S2，使得对任意的使得对任意的n元运算元运算1及任意的元素及任意的元素a1,a2,anS1均有：均有：g()=f()则称则称V1与与V2同态。同态。解释解释两个代数系统同态：两个代数系统同态：（1）两个代数系统）两个代数系统同类型同类型；（2）运算的象运算的象=象的运算象的运算2、同态的特点、同态的特点（1）g映射可以是内射、单射、满射、双射；（2）g(S1)S2 像点集单一同态满同态同构同态示意图同态示意图S1x1x2x3S2gg(x1)=y1g(x2)=y1g(x3)=y3y1y3g(x1 x3)=g(x1)*g(x3)=x1x3y1*y3y1*y3g(x2 x3)=g(x2)*g(x3)=y1*y3x2x3g(S1)同态举例同态举例证明：证明：I和和B 是同态的，其中：是同态的，其中：B=B=正，负，零正，负，零，*运算的运算表如下：运算的运算表如下：*正正负负零零正正正正负负零零负负负负正正零零零零零零零零零零解答解答(1)显然I和和B 是同是同类型的；类型的；(2)g:I(2)g:IB B(3)验证运算的象验证运算的象=象的运算象的运算g(Ig(I)=)=i0i0i0i0,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,j0时时: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:Ng:N0,10,1，且，且定义为：定义为：g(n)=0g(n)=0 (n (n N)N)证明：证明：同态同态证明证明（1 1）显然）显然与与同同类型；类型；（2 2）运算的象）运算的象=象的运算象的运算对任意的对任意的m,nm,n N N运算的象运算的象=g(mn)=g(mn)=0 0象的运算象的运算=g(m)g(n)=00=g(m)g(n)=00=0 0所以：所以：N 与与0 同态同态3、满同态、单一同态、自同态、满同态、单一同态、自同态(1)如果如果g为满射为满射函数，则称函数，则称g为关于类型映为关于类型映射射f的满同态；的满同态；(2)如果如果g为单射为单射函数，则称函数，则称g为关于类型映为关于类型映射射f的单一同态；的单一同态；(3)若若V1=V2，且类型映射且类型映射f为恒等函数为恒等函数，则，则称称g为关于类型映射为关于类型映射f的自同态。的自同态。自自同态举例同态举例其中：其中：g:Ig:II I，且定义为：且定义为：g(n)=3ng(n)=3n (n (n I)I)证明：证明：自同态自同态证明证明(1)显然显然I+与与I+同类型同类型,且且f(+)=+f(+)=+；(2)(2)运算的象运算的象=象的运算象的运算对任意的对任意的m,nm,n N N运算的象运算的象=g(m+ng(m+n)=3(m+n)=3m+3n=3(m+n)=3m+3n=g(m)+g(ng(m)+g(n)=)=象的运算象的运算所以：所以：I+与与I+同态同态,且是自同态。且是自同态。满同态举例满同态举例证明：证明：U=V=满同态满同态g:INm对于所有的对于所有的i I,有：有：g(i)=(i)(modm)证明证明类型映射类型映射f f定义为：定义为：f(+)=+f(+)=+m m,f(,f()=)=m m (1)(1)显然显然U=I,+,U=和和V=NV=同类型同类型(2)(2)运算的象运算的象=象的运算象的运算对任意的对任意的x,yx,y I:I:g(x+y)=g(x)+g(x+y)=g(x)+m m g(y)g(y)g(x g(x y)=g(x)y)=g(x)m m g(y)g(y)证明证明:g(x+y)=g(x)+:g(x+y)=g(x)+m m g(y)g(y)g(x+y)g(x+y)=(x+y)(mod m)=(x+y)(mod m)=(x)(mod m)+(y)(mod m)(mod m)=(x)(mod m)+(y)(mod m)(mod m)=(x)(mod m)+=(x)(mod m)+m m(y)(mod m)(y)(mod m)=g(x)+=g(x)+m m g(y)g(y)证明证明:g(x:g(x y)=g(x)y)=g(x)m m g(y)g(y)g(xg(x y)y)=(x=(x y)(mod m)y)(mod m)=(x)(mod m)=(x)(mod m)(y)(mod m)(mod m)(y)(mod m)(mod m)=(x)(mod m)=(x)(mod m)m m(y)(mod m)(y)(mod m)=g(x)=g(x)m m g(y)g(y)所以：所以：U=I,+,U=和和V=NV=同态同态证明证明g g是满射函数是满射函数对于任意的对于任意的x x N Nm m,均有均有x x I I，使得：使得：g(x)=(x)(mod m)=xg(x)=(x)(mod m)=x 所以：所以：U=I,+,U=和和V=NV=是满同是满同态态满同态的特点满同态的特点满满同态对性质的保持是同态对性质的保持是单方向单方向的，即：的，即：与与满同态满同态的的性质性质，均保持均保持交交换换律律结结合合律律分分配配律律吸吸收收律律幺幺元元零零元元逆逆元元等等幂幂元元交换律、结合律交换律、结合律设设与与满同态，则：满同态，则：（1）若）若 运算可交换，则运算可交换，则*运算也可交换；运算也可交换；（2 2）若若 运算可结合，则运算可结合，则*运算也可结合；运算也可结合；分配律分配律V1=V2=满同态满同态f:类型映射类型映射*1 1*对对可分配可分配f(*)对对f()也可分配也可分配 2幺元、零元、逆元幺元、零元、逆元设设与与满同态，则：满同态，则：(1)若若 有幺元有幺元e，则则*有幺元有幺元g(e);(2)若若 有零元有零元 ，则则*有零元有零元g();(3)若若x X有逆元有逆元x-1,则则g(x)Y有逆元有逆元g(x-1)满同态的特点举例满同态的特点举例I,+,和和N 满同态，则：满同态，则：(1)(1)可交换，可交换，f(f()=+)=+3 3也可交换；也可交换；(2)(2)可交换，可交换，f(f()=)=3 3也可交换；也可交换；(3)(3)可结合，则可结合，则f(+)f(+)+3 3也可结合；也可结合；(4)(4)可结合，则可结合，则f(f()3 3也可结合；也可结合；满同态举例（续）满同态举例（续）(5)(5)对对“”存在存在e=0,e=0,则则:对对“+3 3”存在存在e=g(0)=0;e=g(0)=0;(6)(6)对对“”存在存在e=1,e=1,则则:对对“3 3”存在存在e=g(1)=1;e=g(1)=1;(7)(7)对对“”存在零元存在零元=0,=0,则则:对对“3 3”存在零元存在零元=g(0)=0;=g(0)=0;(8)(8)对对“”，8 8的逆元是的逆元是-8,-8,则则:对对“+3 3”g(8)=g(8)=2 2g(-8)=g(-9+1)=g(-8)=g(-9+1)=(-9+1)(mod3)=1(mod3)=(-9+1)(mod3)=1(mod3)=1 1满同态举例（续）满同态举例（续）2+3 1=(2+1)(mod3)=0=e2和和1互为逆元互为逆元单一同态举例单一同态举例证明：证明：单一同态单一同态实数集合g:RR对于对于x Rg(x)=2x证明证明(1)(1)显然显然和和 R,同类型同类型(2)(2)运算的象运算的象=象的运算象的运算对于任意的对于任意的x,yx,y R R，有：有：g(x+yg(x+y)=2=2x+yx+y=2=2x x 2 2y y=g(x)=g(x)g(y)g(y)(3)g(3)g映射是单射函数映射是单射函数y=2x定理定理V1=V2=g为同态映射为同态映射V3=为为V2=的子系统的子系统象点集象点集V1的同态象点的同态象点推论推论g为同态映射为同态映射的性质的性质的同态象点的同态象点均保持均保持二、同构二、同构1、同构的定义、同构的定义2、同构的特点、同构的特点3、自同构、自同构1、同构的定义、同构的定义同类型的代数系统同类型的代数系统A上的二元运算上的二元运算B上的二元运算上的二元运算存在一个存在一个双射映射双射映射g：AB对任意的对任意的a,bAg(a b)=g(a)g(b)*运算的象运算的象象的运算象的运算从从到到的一个同构映射的一个同构映射与与同构同构同构的一般定义同构的一般定义V1=V2=同类型的代数系统同类型的代数系统f:12类型映射类型映射存在一个存在一个双射映射双射映射g：G1G2 对任意的对任意的n元运算元运算1任意的元素任意的元素a1,a2,anG1()g()=f()V1与与V2同同构构同构满足的条件同构满足的条件（1）同类型）同类型（2）g为双射函数（为双射函数（|S1|S2|）（3）运算的象象的运算运算的象象的运算同构举例同构举例S=4,5,6,S=4,5,6,运算运算 见表见表(a)(a)P=1,2,3,P=1,2,3,运算运算*见表见表(b)(b)则则S,与与同构。同构。456445454556456*123112121223123表表(a)(a)表表(b)(b)解答解答（1 1）显然）显然S,与与同同类型；类型；（2 2）寻找双射函数）寻找双射函数g g：S SP P方法：特异元素对应特异元素方法：特异元素对应特异元素在在S,中中e=6e=6在在中中e=3e=3 g(6)=3 g(5)=2 g(4)=1 g(5)=1 g(4)=2或者g g1 1(4)=1,g(4)=1,g1 1(5)=2,g(5)=2,g1 1(6)=3(6)=3g g2 2(4)=2,g(4)=2,g2 2(5)=1,g(5)=1,g2 2(6)=3(6)=3（3 3）运算的象象的运算）运算的象象的运算g g1 1(4)=1,g(4)=1,g1 1(5)=2,g(5)=2,g1 1(6)=3(6)=3例：例：g(4g(4 5)=g(5)=25)=g(5)=2g(4)*g(5)=1*2=2g(4)*g(5)=1*2=2 g g2 2(4)=2,g(4)=2,g2 2(5)=1,g(5)=1,g2 2(6)=3(6)=3例：例：g(4g(4 6)=g(4)=26)=g(4)=2g(4)*g(6)=2*3=2g(4)*g(6)=2*3=2g g1 1 、g g2 2均为均为同构映射同构映射变换运算表的方法变换运算表的方法g g1 1一致一致g g2 21、2列交换列交换1,2行交换行交换一致一致同构举例同构举例S=a,b,c,d,S=a,b,c,d,运算运算 见表见表(a)(a)P=1,2,3,4,P=1,2,3,4,运算运算*见表见表(b)(b)则则S,与与同构。同构。abcdadabdbdbcdcadccdabaa表表(a)(a)*123412224211423323141134表表(b)(b)解答解答（1 1）显然）显然S,与与同类型；同类型；（2 2）寻找双射函数）寻找双射函数g g：S SP P由由表表(a)(a)的第的第4 4行和表行和表(b)(b)的第的第1 1行行可知：可知：g(a)=2,g(b)=4g(a)=2,g(b)=4在在S,中中c c是等幂元是等幂元在在中中3 3是等幂元是等幂元g(c)=3g(a)=2,g(b)=4,g(c)=3,g(d)=1变换运算表变换运算表g g1,2列交换列交换2,4列交换列交换1,2行交换行交换2,4行交换行交换一致一致2、同构的特点、同构的特点（1）g为双射函数；为双射函数；（2）g(X)=YS1x1x2S2gx1x2g(x1)*g(x1)g(x1)g(x2)同构对运算保持相同的性质同构对运算保持相同的性质设设与与同构，则：同构，则：(1)若若 有幺元有幺元e,则则*有幺元有幺元g(e),反之亦然；反之亦然；(2)若若 有零元有零元,则则*有零元有零元g(),反之亦然；反之亦然；(3)若若x X有逆元有逆元x-1,则则g(x)Y有逆元有逆元g(x-1),反之亦然；反之亦然；(4)若若 运算可交换运算可交换,则则*运算也可交换运算也可交换,反之亦反之亦然；然；(5)若若 运算可结合运算可结合,则则*运算也可结合运算也可结合,反之亦反之亦然；然；3、自同构、自同构若若V1=V2，且类型映射且类型映射f为恒等函数为恒等函数，则称则称g为关于类型映射为关于类型映射f的自同构。的自同构。同构举例同构举例证明：证明：同构同构给定：给定：g:R+R,g(x)=lnx证明证明(1)(1)显然显然R 和和同同类型；类型；(2)g(x)=(2)g(x)=lnxlnx是是双射函数；双射函数；(3)(3)运算的象象的运算运算的象象的运算:对于任意的对于任意的a,ba,b R R+g(ag(a b)b)=ln(aln(a b b)=)=lna+lnblna+lnb=g(a)+g(b)g(a)+g(b)所以：所以：R 和和同构。同构。第三节第三节 同余关系同余关系 一、代换性质一、代换性质二、同余关系二、同余关系一、代换性质一、代换性质V=:代数系统代数系统R:G上的等价关系上的等价关系:n元运算元运算对任意的对任意的a1,b1,a2,b2,an,bn Ga1Rb1a2Rb2anRbn()()RR关于关于具有代换性质具有代换性质代换性质举例代换性质举例I,+,为代数系统，为代数系统，I I中的等价关系中的等价关系如下：对任意的如下：对任意的a,ba,b I I，aRbaRb|a|a|=|b|=|b|问：等价关系问：等价关系R 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|(i1j1)R(i2j2)即：即：对于乘法运算对于乘法运算“”来说，来说，R具有代换具有代换性质。性质。二、同余关系二、同余关系V=:代数系统代数系统R:G上的等价关系上的等价关系R关于每一个运算关于每一个运算 都具有代换性质都具有代换性质R为为上的同余关系。上的同余关系。同余关系举例同余关系举例为代数系统，在为代数系统，在N N上定义一个模上定义一个模m m同余关系同余关系m m证明：证明：m m关于具有代换性质，且是关于具有代换性质，且是上的同余关系上的同余关系证明证明x1,y1,x2,y2 Nx1 m y1x2 m y2(x1+x2)m(y1+y2)x1 m y1x1=p1m+r1y1=p2m+r1x2 m y2x2=q1m+r2y2=q2m+r2p1,p2,q1,q2,r1,r2 N0r1、r2m-1x1+x2=p1m+r1+q1m+r2=(p1+q1)m+(r1+r2)y1+y2=p2m+r1+q2m+r2=(p2+q2)m+(r1+r2)(x1+x2)m(y1+y2)m是同余关系是同余关系同余关系举例同余关系举例给定代数系统给定代数系统V=V=，其中其中*是是I I上的上的一元运算，定义为：一元运算，定义为：*(i)=i(i)=i2 2(mod m)m(mod m)m I I+问：问：m m 是是V V上的同余关系吗？上的同余关系吗？解答解答设：设：i i1 1 m m i i2 2,证明：证明：*(i(i1 1)m m*(i*(i2 2)令：令：i i1 1=a=a1 1m+r,im+r,i2 2=a=a2 2m+rm+r其中：其中：a a1 1,a a2 2,r r N,N,且且0rm-10rm-1*(i*(i1 1)=(a)=(a1 1m+r)m+r)2 2(mod m)(mod m)=(a=(a1 12 2m m2 2+2a+2a1 1mr+rmr+r2 2)(mod m)=r)(mod m)=r2 2(mod m)(mod m)*(i*(i2 2)=(a)=(a2 2m+r)m+r)2 2(mod m)(mod m)=(a=(a2 22 2m m2 2+2a+2a2 2mr+rmr+r2 2)(mod m)=r)(mod m)=r2 2(mod m)(mod m)*(i*(i1 1)m m*(i*(i2 2)m m关于关于*具有代换性质具有代换性质 m m是是上的同余关系上的同余关系 定理定理U=V=f:同态映射同态映射Rf:X上的二元关系上的二元关系对于任意的对于任意的x1,x2 Xx1Rfx2 f(x1)=f(x2)Rf是是U上的同余关系上的同余关系证明证明(1)Rf是等价关系：是等价关系：自反性：自反性：对任意的对任意的x Xf(x)=f(x)xRx对称性：对称性：x1Rfx2f(x1)=f(x2)f(x2)=f(x1)x2Rfx1可传递性：可传递性：x1Rfx2x2Rfx3f(x1)=f(x2)f(x2)=f(x3)f(x1)=f(x3)x1Rfx3证明（续）证明（续）(2)Rf关于关于 具有代换性质：具有代换性质：x1,y1,x2,y2 Xx1 Rf y1x2 Rf y2(x1 x2)Rf(y1 y2)f(x1 x2)=f(y1 y2)f(x1 x2)f:同态映射同态映射=f(x1)*f(x2)x1 Rf y1f(x1)=f(y1)=f(y1)*f(x2)x2 Rf y2f(x2)=f(y2)=f(y1)*f(y2)f:同态映射同态映射=f(y1 y2)(x1 x2)Rf(y1 y2)R f是是U上的同余关系上的同余关系第四节第四节 商代数和积代数商代数和积代数一、商代数一、商代数二、积代数二、积代数一、商代数一、商代数1、商代数的定义、商代数的定义2、正则映射、正则映射1、商代数的定义、商代数的定义R:代数系统代数系统V=上的同余关系上的同余关系:V=关于关于R的商代数的商代数V/R(1)对于对于x1,x2 Xx1R x2R=x1 x2R(2)X/R=xR|x X商集商集证明证明验证验证是是一个代数系统一个代数系统(1)封闭性：封闭性：任取任取x1R、x2R X/Rx1R x2R由由 定义定义=x1 x2R 在在X上封闭上封闭x1 x2 X x1 x2R X/R 在在X/R上封闭上封闭x1R x2R X/R证明（续）证明（续）(2)是良是良定的定的y1 x1R y2 x2Rx1R x2R=y1R y2Rx1R x2R与等价类的代表元素与等价类的代表元素x1和和x2的选取无关的选取无关y1 x1Ry2 x2R等价类的定义等价类的定义x1Ry1x2Ry2R为同余关系为同余关系R关于关于 具有代换性质具有代换性质 x1 x2 R y1 y2 x1 x2R=y1 y2R x1R x2R=y1R y2R由由 定义定义商代数举例商代数举例设设代数系统代数系统F=,F=,其中其中A=aA=a1 1,a,a2 2,a,a3 3,a,a4 4,a,a5 5*和和的的运算表如下：运算表如下：*a a1 1a a4 4a a3 3a a2 2a a3 3a a2 2a a3 3a a4 4a a1 1a a4 4a a2 2a a3 3a a5 5a a1 1a a5 5R R为为A A上的等价关系上的等价关系,A/R=aA/R=a1 1,a,a3 3,a,a2 2,a,a5 5,a,a4 4证明：证明：R R是是F F上的同余关系，并求上的同余关系，并求F F的商代数。的商代数。证明证明(1)R(1)R是是F F上的同余关系上的同余关系R R关于关于*运算具有代换性质运算具有代换性质R R关于关于运算具有代换性质运算具有代换性质(2)(2)求求F F的商代数的商代数证明证明:R:R关于关于*具有代换性质具有代换性质A/R=aA/R=a1 1,a,a3 3,a,a2 2,a,a5 5,a,a4 4 R=aR=,a1Ra1:*a1=a4(a4Ra4)*a1R*a1a1Ra3:*a1=a4*a3=a4(a4Ra4)*a1R*a3a3Ra1:*a3=a4*a1=a4(a4Ra4)*a3R*a1 R R关于关于*具有代换性质具有代换性质(续续)a3Ra3:*a3=a4(a4Ra4)*a3R*a3a2Ra2:*a2=a3(a3Ra3)*a2R*a2a2Ra5:*a2=a3*a5=a1(a3Ra1)*a2R*a5a5Ra2:*a5=a1*a2=a3(a1Ra3)*a5R*a2 R R关于关于*具有代换性质具有代换性质(续续)a5Ra5:*a5=a1(a1Ra1)*a5R*a5a4Ra4:*a4=a2(a2Ra2)*a4R*a4对任意的对任意的x,y AxRy*xR*y R关于关于*具有代换性质具有代换性质 证明证明:R:R关于关于具有代换性质具有代换性质a1Ra1:a1=a3(a3Ra3)a1R a1a1Ra3:a1=a3 a3=a1(a3Ra1)a1R a3a3Ra1:a3=a1 a1=a3(a1Ra3)a3R a1a3Ra3:a3=a1(a1Ra1)a3R a3a2Ra2:a2=a2(a2Ra2)a2R a2 证明证明:R:R关于关于具有代换性质具有代换性质a2Ra5:a2=a2 a5=a5(a2Ra5)a2R a5a5Ra2:a5=a5 a2=a2(a5Ra2)a5R a2a5Ra5:a5=a5(a5Ra5)a5R a5a4Ra4:a4=a3(a3Ra3)a4R a4对任意的对任意的x,y AxRy xR y R关于关于 具有代换性质具有代换性质F F的商代数的商代数设设F的商代数为的商代数为A/Raa1 1,a,a3 3,a,a2 2,a,a5 5,a,a4 4 aa1 1 R R,a,a2 2 R R,a,a4 4 R R*RRaa1 1 R Raa2 2 R Raa4 4 R R*R(a1R)=*a1R=a4Ra4R*R(a2R)=*a2R=a3R=a1Ra1R*R(a4R)=*a4R=a2Ra2R R(a1R)=a1R=a3R R(a2R)=a2R=a2Ra2R R(a4R)=a4R=a3R=a1Ra1R=a1Ra1R2、正则映射、正则映射正则映射正则映射R:集合集合G上的等价关系上的等价关系函数函数g:GG/Rg(x)=xR定理定理R:上的同余关系上的同余关系g:XX/R正则映射正则映射g是从是从到商代数到商代数的的满同态满同态自然同态自然同态g(x)=xR证明证明(1)显然显然与与同同类型类型；(2)证明：证明：运算的象象的运算运算的象象的运算对任意的对任意的x,y Xg(xyy)(正则映射定义正则映射定义)=xyyR R (商代数定义商代数定义)=xxR RyyR R (正则映射定义正则映射定义)=g(x)g(y)=g(x)g(y)(3)g(3)g是是满射满射函数：函数：任意的任意的 xxR R X/R，在在X中至少有一个原象中至少有一个原象x与之对应，使得：与之对应，使得：g(x)=xR R g g是满射函数是满射函数证明证明(续续)自然同态举例自然同态举例上例：求代数系统上例：求代数系统F=F=到到F F的商代的商代数为数为A/R,*的的自然同态。自然同态。求解求解自然同态自然同态g:g(x)=xRg(a a1 1)=g(a a3 3)=a a1 1Rg(a a2 2)=g(a a5 5)=a a2 2Rg(a a4 4)=a a4 4RAa1a2a3a4a5A/Ra1Ra2Ra4Rg定理定理f:从从到到的同态映射的同态映射R f:上的同余关系上的同余关系:xRfyf(x)=f(y)g:从从到到的自然同态的自然同态存在从存在从到到的同构映射的同构映射 g=f示意图示意图xxRf商代数商代数gf(x)f同态象点同态象点f(X)g=f同构映射同构映射证明证明设映射设映射：X/R ff(X)，且且(xRf)=f(x)证明：证明：(1)显然同类型；显然同类型；(2)是单射函数；是单射函数；(3)是满射函数；是满射函数；(4)运算的象象的运算运算的象象的运算证明：证明：是单射函数是单射函数单射即：象点相同证明原象相同单射即：象点相同证明原象相同对任意的对任意的x,y X若若(xRf)=(yRf)(由由 的定义）的定义）f(x)=f(y)(由由xRfyf(x)=f(y)xRfyxRf=yRf 是单射函数是单射函数 证明：证明：是满射函数是满射函数f:Xf:Xf(X)f(X)的满同态映射的满同态映射对任意的对任意的y f(X),必必存在存在x X,使得使得f(x)=y又又(xRf)f(x)=y即：即：对任意的对任意的y f(X)，必存在必存在xRf X/Rf 使得：使得：(xRf)y 是满射函数。是满射函数。证明：证明：运算的象象的运算运算的象象的运算对对任意的任意的x,y X，有：有：运算的象运算的象(xRf yRf)(g(x)=xRf）=(g(x)g(y)(g为自然同态为自然同态,运算的象象的运算运算的象象的运算)=(g(x y)(g(x)=xRf）=(x yRf)(的定义的定义)=f(x y)(f为为同态映射同态映射,运算的象象的运算运算的象象的运算)f(x)*f(y)(的定义的定义)(xRf)*(yRf)象的运算象的运算 是从是从到到的的同构映射。同构映射。证明：证明：g=fg=f 对对任意的任意的x X g(xg(x)=(g(x)=(xRf)=f(x)g=fg=f 二、积代数二、积代数A1=A2=同类型的代数系统同类型的代数系统A1A2=:A1与与A2的积代数的积代数 定义为：定义为：对任意的对任意的,G1G2=A1,A2:A1A2的因子代数的因子代数积积代数举例代数举例F F2 2=N=F F3 3=N=求：求：F F2 2FF3 3解答解答N N2 2=0,1=0,1N N3 3=0,1,2=0,1,2则：则：N N2 2NN3 3=,设：设：F F2 2FF3 3=N=+23 23、2323的运算表的运算表+23=23=第五节第五节 典型的代数系统典型的代数系统一、半群一、半群二、群二、群三、格三、格四、布尔代数四、布尔代数一、半群一、半群1、半群、半群2、可交换半群、可交换半群3、独异点（含幺半群）、独异点（含幺半群）4、可交换含幺半群、可交换含幺半群5、子半群、子半群6、循环半群、循环半群1、半群、半群:代数系统代数系统*:二元运算二元运算*运算是可结合运算是可结合:半群半群2、可交换半群、可交换半群:半群半群*运算是可交换运算是可交换:可交换半群可交换半群3、独异点（含幺半群）、独异点（含幺半群）:半群半群*运算有运算有幺元幺元e:含幺半群含幺半群独异点独异点4、可交换含幺半群、可交换含幺半群:独异点独异点*运算是可交换运算是可交换S,*:可交换含幺半群可交换含幺半群半群举例半群举例下列各代数系统是否为半群？若是半群，下列各代数系统是否为半群？若是半群，是什么半群？是什么半群？(1)(1)(2)N,(2)(3)(S),(3)，其中其中S S为非空集合。为非空集合。(4)(S),(4)其中其中S S为非空集合。为非空集合。半群半群可交换半群可交换半群含幺半群含幺半群e=0可交换含幺半群可交换含幺半群半群半群可交换半群可交换半群含幺半群含幺半群e=1可交换含幺半群可交换含幺半群半群半群可交换半群可交换半群含幺半群含幺半群e=S可交换含幺半群可交换含幺半群半群半群可交换半群可交换半群含幺半群含幺半群e=可交换含幺半群可交换含幺半群半群举例半群举例I:I:整整数数集集合合，对对于于下下列列*运运算算，哪哪些些代代数数系系统统是半群是半群?a*b=a*b=a ab b a*b=a a*b=a a*b=a*b=a+aba+ab a*b=max(a,b)a*b=max(a,b)解答解答对任意的对任意的a,b,ca,b,c I (a*b)*c=(a*b)*c=a ab b*c=(*c=(a ab b)c c=a abcbc，a*(b*c)=a*ba*(b*c)=a*bc c=，不是半群不是半群所以所以(a*b)*c a*(b*c)(a*b)*c a*(b*c)。解答解答:a*b=aa*b=a*的封闭性是显然的的封闭性是显然的;(a*b)*c=a*c=a,(a*b)*c=a*c=a,a*(b*c)=a*b=aa*(b*c)=a*b=a，*是可结合运算是可结合运算是半群是半群解答解答:a*b=a*b=a+aba+ab (a*b)*c=(a*b)*c=(a+aba+ab)*c)*c=a+ab+(a+ab)ca+ab+(a+ab)c=a+ab+ac+abca+ab+ac+abca*(b*c)=a*(a*(b*c)=a*(b+bcb+bc)=a+a(b+bca+a(b+bc)=)=a+ab+abca+ab+abc(a*b)*ca*(b*c)(a*b)*ca*(b*c)不是半群不是半群解答解答:a*b=max(a,b)a*b=max(a,b)(4)*(4)*的封闭性是显然的的封闭性是显然的;(a a*b b)*)*c c=a=a*(*(b b*c c)=max(max(a a,b b,c c)，*是可结合运算是可结合运算是半群是半群5、子半群、子半群:半群半群H S集合集合H在运算在运算*作用下封闭作用下封闭是是 的的子半群子半群:含幺半群含幺半群H S集合集合H在运算在运算*作用下封闭作用下封闭是是 的的子含幺半群子含幺半群子含幺半群子含幺半群e H子半群举例子半群举例例：例：S 是一个半群，是一个半群，*运算的运算表如下：运算的运算表如下：问：问：(1)(2)(3)(4)(5)是是的子半群吗？的子半群吗？子半群子半群含幺子半群含幺子半群子半群子半群含幺子半群含幺子半群子半群子半群子半群子半群不是子半群不是子半群子含幺子含幺半群举例半群举例集合集合A=0,2,4(1)是含幺半群是含幺半群;(2)不是不是的子含幺半群。的子含幺半群。解答解答 的幺元是的幺元是4 4，所以，所以 是独异是独异点；点；的幺元是的幺元是1 1。而。而1 1 A A,，因此因此 不是不是 的子含幺半群。的子含幺半群。定理定理:含幺半群含幺半群*运算表中运算表中任何两行或两列都是不相同的任何两行或两列都是不相同的证明证明a,b Sab假设假设a行和行和b行完全相同行完全相同a*e=b*e a=b与与ab矛盾矛盾结论成立结论成立定理定理:可交换含幺半群可交换含幺半群H:S的的等幂元等幂元所构成的集合所构成的集合是是的子含幺半群的子含幺半群证明证明(1)证明证明e He*e=ee是等幂元是等幂元e H(2)*在在H上封闭上封闭对任意的对任意的a,b Ha*b Ha*b是等幂元是等幂元(a*b)*(a*b)（*运算可交换）运算可交换）=(a*b)*(b*a)（*运算可结合）运算可结合）=a*(b*b)*a（b是等幂元）是等幂元）=a*b*a（*运算可交换）运算可交换）=(a*a)*b（a是等幂元）是等幂元）=a*b元素的幂的定义元素的幂的定义在在含幺含幺半群半群中，任意元素中，任意元素a S,它的幂被定义为：它的幂被定义为：a0=e a1=a a2=a*a a k+1=ak*a6、循环半群、循环半群:半群半群:含幺半群含幺半群存在一个元素存在一个元素g S对任意的对任意的a S都有一个相应的都有一个相应的n Na=gn循环半群循环半群循环含幺半群循环含幺半群生成员生成员循环含幺半群举例循环含幺半群举例设设S=a,b,c,dS=a,b,c,d，定义定义S S中的二元运算中的二元运算*，*运算的运算表如下：运算的运算表如下：(1)(1)证明证明是是一个一个循环含幺半群，并给出循环含幺半群，并给出它的生成员；它的生成员；(2)(2)把把中的每一个元素都表示成生成员中的每一个元素都表示成生成员的幂；的幂；(3)(3)列出列出中所有的等幂元。中所有的等幂元。解答解答(1)(1)由运算表可知：由运算表可知：e=ae=ab b和和d d均为生成员均为生成员(2)(2)生成员的幂的形式：生成员的幂的形式：b b0 0=a=ab b1 1=b=bb b2 2=b*b=c=b*b=cb b3 3=b=b2 2*b=c*b=d*b=c*b=dd d0 0=a=ad d1 1=d=dd d2 2=d*d=c=d*d=cd d3 3=d=d2 2*d=c*d=b*d=c*d=b(3)a(3)a为等幂元为等幂元定理定理每一个循环半群（或含幺循环半群）都每一个循环半群（或含幺循环半群）都是可交换半群（或可交换含幺半群）。是可交换半群（或可交换含幺半群）。证明证明:循环半群循环半群g:生成员生成员对任意的对任意的a,b X 都存在都存在m,n Na=gmb=gna*b=gm*gn=gm+n=gn+m=gn*gm=b*a*运算是可交换的运算是可交换的是可交换半群是可交换半群二、群二、群1、群的定义、群的定义2、阿贝尔群、阿贝尔群3、循环群、循环群4、子群、子群1、群的定义、群的定义（1）是代数系统；是代数系统；（2）“*”运算满足结合律；运算满足结合律；（3）中存在幺元中存在幺元e；注意：注意：群中无零元群中无零元群群含幺半群含幺半群（4）中任意一个元素都有逆元素；中任意一个元素都有逆元素；群群举例举例R和和R-0是群吗？为什么？是群吗？为什么？解：解：R:0 0是是R的零元，而零元是不可逆的。的零元，而零元是不可逆的。R-0：（1 1）R-0是是代数系统；代数系统；（2 2）存在幺元）存在幺元e=1;e=1;（3 3）“”可结合；可结合；（4 4）对任意实数）对任意实数x,xx,x-1-1=1/x=1/x不是不是是是有限群和无限群有限群和无限群设设是一个群，若集合是一个群，若集合S是有限集是有限集则称则称 是有限群，是有限群，|S|称为有限群的称为有限群的阶阶数数。若集合若集合S是无限集则称是无限集则称 是无限群。是无限群。注意：注意：群的运算表中没有两行或两列是相同的群的运算表中没有两行或两列是相同的定理定理:群群对于任意的对于任意的a,bA方程方程a*x=by*a=b在在A中都有中都有唯一唯一的解的解证明证明(1)证明方程有解：证明方程有解：x=a-1*by=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）证明方程有唯一的解：）证明方程有唯一的解：假设方程有其他的解分别为假设方程有其他的解分别为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即证明即证明:(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=e2、阿贝尔群、阿贝尔群:群群“*”:可交换可交换阿贝尔群阿贝尔群交换群交换群定理定理是阿贝尔群的是阿贝尔群的充分必要条件充分必要条件是：是：对任意的对任意的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)=右式右式证明：充分性证明：充分性已知：已知：(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*b3、循环群、循环群若群若群中每个元素均是它的某个中每个元素均是它的某个 元素元素a的整数幂，则称的整数幂，则称是由是由a生成的生成的循环群。循环群。a称为称为的的生成元素生成元素。定理定理:有限循环群有限循环群a:生成元素生成元素|G|=ne:幺元幺元an=eG=a,a2,a3,an=e 使使an=e的最小的正整数的最小的正整数元素元素a的阶或周期的阶或周期循环群举例循环群举例设设G=0G=0，11，22，33（1 1）G,+是循环群吗？是循环群吗？（2 2）找出生成元。）找出生成元。a+4b=a+4b解答解答（1 1）G,+是循环群；是循环群；（2 2）生成元：）生成元：1,31,3111 1=11112 2=1+=1+4 4 1122113 3=1=12 2+4 4 112+2+4 4 1=1=33114 4=113 3+4 4 113+3+4 4 1=1=00=e=e11的周期为的周期为4 4解答（续）解答（续）生成元：生成元：33331 1=33332 2=3+=3+4 4 3322333 3=3=32 2+4 4 332+2+4 4 3=3=11334 4=333 3+4 4 331+1+4 4 3=3=00=e=e33的周期为的周期为4 44、变换群、变换群A:非空集合非空集合PA:从从A到到A的所有双射函数的集合的所有双射函数的集合 :函数的复合运算函数的复合运算:群群变换群变换群|A|!变换群举例变换群举例A=1,2,3A=1,2,3f1=,=IAf2=,f3=,f4=,f5=,f6=,P PA A=f1,f2,f3,f4,f5,f6 变换群举例（续）变换群举例（续）（1）在在P PA A上封闭；上封闭；（2 2）可结合；可结合；（3 3）幺元存在，）幺元存在，e=e=f1（4 4）每个元素均可逆：每个元素均可逆：f1-1=f1，f2-1=f2，f3-1=f3，f4-1=f4，f5-1=f6，f6-1=f5f1f2f3f4f5f6f1f1f2f3f4f5f6f2f2f1f6f5f4f3f3f3f5f1f6f2f4f4f4f6f5f1f3f2f5f5f3f4f2f6f1f6f6f4f2f3f1f55、子群、子群是是的子群的子群:群群H AH也是一个群也是一个群平凡子群平凡子群:群群是是的一个子群的一个子群H=e或或H=A是是的平凡子群的平凡子群判断子群的方法判断子群的方法（1）含幺元；）含幺元；（2）封闭性；）封闭性；（3）每个元素均可逆；）每个元素均可逆；定理定理:群群H AH是是 的子群的充要条件是的子群的充要条件是:(1)a,b Ha*b H（封闭性）（封闭性）(2)a Ha-1 H（可逆性）（可逆性）证明：充分性证明：充分性封闭性、可逆性封闭性、可逆性 是是 的的子群子群子群子群H A封闭性封闭性可逆性可逆性H中存在幺元中存在幺元e已知已知已知已知已知已知由由(2)可逆性可逆性a Ha-1 H由由(1)封闭性封闭性a*a-1 He H证明：必要性证明：必要性是是 的的子群子群 封闭性、可逆性封闭性、可逆性(1)封闭性封闭性是是 的的子群子群群的定义群的定义*运算在运算在H上封闭上封闭证明：必要性（续）证明：必要性（续）(2)可逆性：可逆性：e:群群中的幺元中的幺元a的逆元是的逆元是a-1中的幺元就是中的幺元就是的幺元的幺元是是 的的子群子群中必有幺元中必有幺元e对于任意的对于任意的a He*a=ae*a=ae*a=e*a消去律消去律e=e H证明：必要性（续）证明：必要性（续）中中a的逆元是的逆元是a-1中中a的逆元就是的逆元就是中中a的逆元的逆元是是 子群子群对于任意的对于任意的a H,必存在逆元必存在逆元a a*a=ea-1*a=ea*a=a-1*a消去律消去律a=a-1 H 定理定理:群群H AH是是 的子群的充要条件是的子群的充要条件是:对任意的对任意的a,b Ha*b-1 H证明证明:必要性必要性是是的子群的子群若若a,b H，则，则a*b-1 H是是的子群的子群对任意的对任意的a,b H a-1,b-1 H a*b-1 H可逆性可逆性封闭性封闭性证明证明:充分性充分性若若a,b H，则，则a*b-1 H 是是的子群的子群可逆性：可逆性：对任意的对任意的a H由由a,b Ha*b-1 Ha*a-1 He HH中存在幺元中存在幺元对任意的对任意的a He*a-1 Ha-1 HH中每个元素均可逆中每个元素均可逆证明证明:充分性充分性(续续)封闭性：封闭性：对任意的对任意的a,b H可逆性可逆性 a,b-1 H由由a,b Ha*b-1 Ha*(b-1)-1 Ha*b H*运算在运算在H上封闭上封闭子群举例子群举例求出求出Z 的所有子群。的所有子群。解答解答e=0e=011-1-1=5,5=5,5-1-1=1=122-1-1=4,4=4,4-1-1=2=233-1-1=3,0=3,0-1-1=0=0(1)0,+(1)(2)0,3,+(2),(3)0,2,4,+(3)(4)Z(4)是是Z 的子的子群。群。拉格朗日定理拉格朗日定理:有限群有限群|G|=n:的子群的子群|H|=mm|nm是是n的因子的因子推论推论任何任何素数阶素数阶的群不可能有非平凡子群。的群不可能有非平凡子群。三、格三、格1、偏序格、偏序格2、格的性质、格的性质3、特殊格、特殊格1、偏序格、偏序格:偏序集偏序集对于任意的对于任意的a,b La,b都有上确界和下确界都有上确界和下确界偏序格偏序格a b=LUBa,ba*b=GLBa,b保联运算保联运算保交运算保交运算偏序格举例偏序格举例S=S=a,b,ca,b,c 问偏序集问偏序集(s),是偏序格吗？是偏序格吗？解答解答(s)(s),a,b,c,a,b,a,c,b,c,a,a,b,c,a,b,a,c,b,c,a,b,cb,c对任意的对任意的S S1 1,S,S2 2(s)(s)GLBSGLBS1 1,S,S2 2=a*b=a*b=S=S1 1S S2 2LUBSLUBS1 1,S,S2 2=ab=S=ab=S1 1S S2 2偏序集偏序集(s),是偏序格是偏序格偏序格举例偏序格举例n:n:正整数正整数S S n n:n:n的所有因子的集合的所有因子的集合:定义在定义在S S n n上的整除关系，问：上的整除关系，问：(1)S(1),(2)S(2),(3)S