离散数学群与半群

,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,第11章 半群与群,离 散 数 学,江苏科技大学本科生必修课程,计算机教研室 周塔,本章内容,11.1,半群与独异点,11.2,群的定义与性质,11.3,子群,11.4,陪集与拉格朗日定理,11.5,正规子群与商群,11.6,群的同态与同构,11.7,循环群与置换群,本章总结,例题选讲,作业,11.1 半群与独异点,半群与独异点都是具有一个二元运算的代数系统。,半群与独异点的定义，及其子代数的说明。,半群与独异点的幂运算。,半群与独异点的同态映射。,半群与独异点,定义11.1,(1)设V是代数系统，,为,二元运算,，如果运算是,可结合的,，则称V为,半群,（semigroup）,。,(2)设V是,半群,若eS是关于,运算的,单位元,则称V是,含幺半群,，也叫做,独异点,（monoid）,。,有时也将独异点V记作V。,半群与独异点的实例,，都是半群,+是普通加法。这些半群中除外都是独异点。,设n是大于1的正整数,和都是半群,也都是独异点,其中+和分别表示矩阵加法和矩阵乘法。,为半群,也是独异点,其中,为集合的对称差运算。,为半群,也是独异点,其中Zn0,1,n-1,为模n加法,。,半群中元素的幂,由于半群V中的运算是可结合的,可以定义,元素的幂,对任意xS,规定：,x,1,x,x,n+1,x,n,x,nZ,+,用数学归纳法不难证明x的幂遵从以下运算规则：,x,n,x,m,x,n+m,(x,n,),m,x,nm,m,nZ,+,普通乘法的幂,、,关系的幂,、,矩阵乘法的幂,等都遵从这个幂运算规则。,独异点中的幂,独异点是特殊的半群，可以把半群的幂运算推广到独异点中去。,由于独异点V中含有单位元e，对于任意的xS,可以定义x的零次幂,即,x,0,e,x,n+1,x,n,x,nN,半群与独异点的直积,定义11.2,设V,1,，V,2,是半群(或独异点),令SS,1,S,2,定义S上的运算如下：,S,称为V,1,和V,2,的,直积,，记作V,1,V,2,。,可以,证明,V,1,V,2,是半群。,若V,1,和V,2,是独异点，其单位元分别为e,1,和e,2,，则是V,1,V,2,中的单位元，因此V,1,V,2,也是独异点。,半群与独异点的同态映射,定义11.3,(1)设V,1,V,2,是半群,:S,1,S,2,。,若对任意的x,yS,1,有,(x,y),(x),(y),则称,为半群V,1,到V,2,的,同态映射,简称,同态,(,homomorphism,),。,(2)设V,1,V,2,是独异点,:S,1,S,2,.,若对任意的x,yS,1,有,(x,y),(x),(y)且,(e,1,)e,2,则称,为独异点V,1,到V,2,的,同态映射,简称,同态,。,两点说明：,为了书写的简便，有时经常省略上述表达式中的算符,和,，而简记为,(xy),(x),(y),应该记住，该表达式中左边的xy是在V,1,中的运算，而右边的,(x),(y)是在V,2,中的运算。,本节的主要内容,集合S和运算构成半群的条件（封闭性、结合律）。,集合S和运算构成独异点的条件（封闭性、结合律、单位元）。,半群与独异点的两条幂运算规则：x,n,x,m,x,n+m,，(x,n,),m,x,nm,。,通过笛卡尔积构造直积。,同态映射的判别：,(xy),(x),(y),对于独异点要加上,(e)e。,定义11.2说明,任取,S,(,),=,=,=,(,),=,(),=,=,11.2 群的定义与性质,群是特殊的半群和独异点。,群论中常用的概念或术语：,有限群、无限群、平凡群、交换群、元素的幂和阶。,群的运算规则。,群的定义,定义11.4,设是代数系统，,为,二元运算,。如果,运算是,可结合,的，,存在单位元,eG，并且对G中的任何元素x都,有x,-1,G,则称G为,群,（,group,）,。,举例,(1),都是群,而和不是群。,(2)是群,而不是群。因为并非所有的n阶实矩阵都有逆阵。,Klein四元群,设Ga,b,c,d，,为G上的二元运算，见下表。,e,a,b,c,e,e,a,b,c,a,a,e,c,b,b,b,c,e,a,c,c,b,a,e,G是一个群：,e为G中的单位元；,运算是可结合的；,运算是可交换的；,G中任何元素的逆元就是它自己；,在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素。,称这个群为,Klein四元群,简称,四元群,。,群的直积,设,是群，在G,1,G,2,上定义二元运算,如下：,G,1,G,2,称是,G,1,与,G,2,的,直积,。,上一节已经证明：是独异点，,可以证明对任意的,G,1,G,2,是的逆元，,因此,G,1,G,2,关于运算构成一个群。,群论中常用的概念或术语,定义11.5,(1)若群G是,有穷集,则称G是,有限群,，否则称为,无限群,。,群G的基数,称为群G的,阶,，有限群G的阶记作|G|。,(2),只含单位元,的群称为,平凡群,。,(3)若群G中的二元运算是,可交换,的，则称G为,交换群,或,阿贝尔(Abel)群,。,例,是无限群、交换群。,是有限群，也是n阶群、交换群。,Klein四元群是4阶群、交换群。,是平凡群、交换群。,群中元素的n次幂,定义11.6,设G是群，aG，nZ，则a的,n次幂,与半群和独异点不同的是：群中元素可以定义负整数次幂。,群中元素的阶,定义11.7,设G是群，aG，使得等式,a,k,e,成立的,最小正整数k,称为,a的阶,，记作|a|k，这时也称,a为k阶元,。若不存在这样的正整数k,则称,a为无限阶元,。,举例,在中，2和4是3阶元，3是2阶元，而1和5是6阶元，0是1阶元。,在中，0是1阶元，其它的整数都是无限阶元。,在Klein四元群中，e为1阶元，其它元素都是2阶元。,群的性质,群,的幂运算规则,定理11.1,设G为群,则G中的幂运算满足：,(1)aG,(a,-1,),-1,a。,(2)a,bG，(ab),-1,b,-1,a,-1,。,(3)aG，a,n,a,m,a,n+m,，n,mZ。,(4)aG，(a,n,),m,a,nm,，n,mZ。,(5)若G为交换群，则(ab),n,a,n,b,n,。,分析：,(1)和(2)可以根据定义证明。,(3)、(4)、(5)中的等式,先利用数学归纳法对于自然数n和m证出相应的结果，然后讨论n或m为负数的情况。,定理11.1的证明,(1)aG,(a,-1,),-1,a。,(a,-1,),-1,是a,-1,的逆元，a也是a,-1,的逆元。,（或者：a,-1,是a的逆元，a也是a,-1,的逆元。）,根据逆元的唯一性，,(a,-1,),-1,a,。,(2)a,bG，(ab),-1,b,-1,a,-1,。,(b,-1,a,-1,)(ab)b,-1,(a,-1,a)bb,-1,be,(ab)(b,-1,a,-1,)a(bb,-1,)a,-1,aa,-1,e,故 b,-1,a,-1,是 ab 的逆元。,根据逆元的唯一性等式得证。,定理11.1的证明,(3)aG，a,n,a,m,a,n+m,，n,mZ。,先考虑n,m都是自然数的情况。任意给定n，对m进行归纳。,m0，有a,n,a,0,a,n,ea,n,a,n+0,成立。,假设对一切mN有a,n,a,m,a,n+m,成立，则有,a,n,a,m+1,a,n,(a,m,a)(a,n,a,m,)aa,n+m,aa,n+m+1,由归纳法等式得证。,下面考虑存在负整数次幂的情况。,设n0，m0，令n-t，tZ,+,，则,a,n,a,m,a,-t,a,m,(a,-1,),t,a,m,a,-(t-m),a,m-t,a,n+m,tm,a,m-t,a,n+m,tm,对于n0,m0以及n0,m0的情况同理可证。,定理11.1的证明,(5)若G为交换群，则(ab),n,a,n,b,n,。,当n为自然数时，对n进行归纳。,(ab),n,(ba),n,(ba),-m,(ba),-1,),m,(a,-1,b,-1,),m,(a,-1,),m,(b,-1,),m,a,-m,b,-m,a,n,b,n,n0，有,(ab),0,e,ee,a,0,b,0,。,假设(ab),k,a,k,b,k,，则有,(ab),k+1,(ab),k,(ab),(a,k,b,k,)ab,a,k,(b,k,a)b,a,k,(ab,k,)b,(a,k,a)(b,k,)b,(a,k+1,)(b,k+1,),由归纳法等式得证。,设n0，则,定理11.1说明,定理11.1(2)中的结果可以推广到有限多个元素的情况,即,注意上述定理中的最后一个等式只对交换群成立。,如果,G,是非交换群,那么只有,