1、第六章第六章 群论群论 6.1 半群与单元半群半群与单元半群 6.2 群群 群在代码的查错、改错的研究,自动机理论群在代码的查错、改错的研究,自动机理论等方面都有应用。等方面都有应用。6.1 半群与单元半群半群与单元半群 半群与群都是具有一个二元运算的代数系半群与群都是具有一个二元运算的代数系统,群是半群的特殊例子。事实上,群是历史统,群是半群的特殊例子。事实上,群是历史上最早研究的代数系统,它比半群复杂一些,上最早研究的代数系统,它比半群复杂一些,而半群概念是在群的理论发展之后才引进的。而半群概念是在群的理论发展之后才引进的。逻辑关系见图逻辑关系见图6.1.1。图图 6.1.1 群群半群半群
2、 一、半群一、半群1、半群的有关定义、半群的有关定义 定义定义6.1 设设(S,)是代数系统,是代数系统,是二元运算,是二元运算,如果如果 运算满足结合律,则称它为半群。运算满足结合律,则称它为半群。换言之,换言之,a,b,cS,若若 是是S上的封闭运算且上的封闭运算且满足满足(a b)c=a (b c),则),则(S,)是半群。是半群。许多代数系统都是半群。例如:许多代数系统都是半群。例如:(I,+),(I,),(E),),(E),),(N4,+4),(N4,4)均是半均是半群。群。再如,设再如,设X是有限字母表,是有限字母表,X+是是 X 中的字母中的字母串,串,X*=X+,其中,其中是不
3、含字母的空串,是不含字母的空串,运算运算 是字母串的是字母串的“并置并置”运算,则运算,则(X*,)是是半群。如半群。如Com X*,puter X*,经经 运算后,运算后,得得Computer仍是字母串。仍是字母串。定理定理6.1 一个半群一个半群(S,),如果它有一个子代,如果它有一个子代数数(M,),则此子代数也是一个半群。,则此子代数也是一个半群。定义定义6.2 一个半群一个半群(S,)的子代数的子代数(M,)也是也是半群,称为半群,称为(S,)的子半群。的子半群。一个半群一个半群(S,)中的元素中的元素a,可定义它的幂:,可定义它的幂:a1=a,a2=a a,,an+1=an a 即
4、半群中的元素有时可用某些元素的幂表示出即半群中的元素有时可用某些元素的幂表示出来。来。因为半群满足结合律,所以可得到因为半群满足结合律,所以可得到 a m a n=a m+n,(a n)m=a m n。如果有如果有a2=a,则称,则称a为半群中的为半群中的等幂元素等幂元素。2、一些特殊半群。一些特殊半群。(1)可交换半群:可交换半群:如果半群如果半群(S,)中二元运算中二元运算 是可是可交换的,则称交换的,则称(S,)是可交换半群。是可交换半群。例如:例如:(I,+),(I,),(E),),(E),)(N4,+4),(N4,4)均是可交换半群。但均是可交换半群。但(X*,)不是不是可交换半群。
5、可交换半群。(2)循环半群:循环半群:一个半群一个半群(S,)如果它的每个元素如果它的每个元素均为均为S内某一固定元素内某一固定元素 a 的某一方幂,则此半群的某一方幂,则此半群称为由称为由 a 所生成的循环半群,元素所生成的循环半群,元素 a 称为此半群称为此半群的生成元素。的生成元素。(3)单元半群(或单位半群):单元半群(或单位半群):有单位元素有单位元素e的半的半群群(S,),常记为,常记为(S,e)。定理定理6.2:一个循环半群一定是可交换半群。一个循环半群一定是可交换半群。定理定理6.3:一个半群内的任一元素一个半群内的任一元素 a 和它所有的和它所有的幂组成一个由幂组成一个由 a
6、 所生成的循环子半群。所生成的循环子半群。例:下面半群都是单位半群例:下面半群都是单位半群 (I,+)单位元素是单位元素是0,可记为,可记为(I,+,0);(I,)单位元素是单位元素是1,可记为,可记为(I,1);(X*,)单位元素是单位元素是(空串空串),可记为可记为(X*,,);(E),)单位元素是单位元素是,可记为,可记为(E),);(E),)单位元素是单位元素是E,可记为,可记为(E),E)。(N4,+4)单位元素是单位元素是0,可记为,可记为(N4,+4,0)(N4,4)单位元素是单位元素是1,可记为,可记为(N4,4,1)定理定理6.5 一个单位半群一个单位半群(S,),如果存在一
7、个,如果存在一个子代数子代数(M,),且其单位元,且其单位元 e M,则则(M,)也是一个单位半群。也是一个单位半群。定义定义6.5 一个单位半群一个单位半群(S,),如果存在一个,如果存在一个子代数子代数(M,),且其单位元,且其单位元 e M,则则(M,)也是一个单位半群,称为也是一个单位半群,称为(S,)的子单位半群的子单位半群。定义定义6.5:一个单位半群一个单位半群(S,)如果由它的一个如果由它的一个元素元素a 所生成,则称为由所生成,则称为由 a 所生成的循环单位半所生成的循环单位半群,元素群,元素 a 称为此单位半群的生成元素。称为此单位半群的生成元素。定理定理6.6:一个循环单
8、位半群是一个可换单位半一个循环单位半群是一个可换单位半群。群。6.2 群群一、群与群的同构一、群与群的同构1、群的有关定义、群的有关定义 定义定义6.7 如果代数系统如果代数系统(G,)满足满足 (1)(G,)为一半群;为一半群;(2)(G,)中有单位元中有单位元e;(3)(G,)中每一元素中每一元素aG都有逆元都有逆元 a-1 则称代数系统则称代数系统(G,)为群。为群。例如:例如:(I,+)是群,因是群,因 a I 都有逆元都有逆元-a;(N4,+4)是群是群,0的逆元是的逆元是0,1的逆元是的逆元是3,2的逆元是的逆元是2。(I,),(X*,),(E),),(E),),(N4,4)均不是
9、群。均不是群。定义定义6.8 一个群一个群(G,)如果满足交换律,则称为如果满足交换律,则称为可交换群或称阿贝尔群。可交换群或称阿贝尔群。例如:群例如:群(I,+),(N4,+4)都是阿贝尔群。都是阿贝尔群。定义定义6.9 一个群一个群(G,)如果它的一个子代数如果它的一个子代数(H,)也是一个群,则称也是一个群,则称(H,)是是(G,)的一个群。的一个群。定义定义6.10 一个群一个群(G,)如果它的元素个数是有限的,如果它的元素个数是有限的,则称为有限群。如果它的元素个数是无限的,则称则称为有限群。如果它的元素个数是无限的,则称为无限群。为无限群。定义定义6.11 一个群一个群(G,)的阶
10、记为的阶记为|G|,如果一个群,如果一个群是有限群,则阶为元素个数,如果一个群为无限群,是有限群,则阶为元素个数,如果一个群为无限群,则阶为无穷大。则阶为无穷大。2、群的一些性质、群的一些性质(1)群满足消去律群满足消去律(2)一个阶大于一个阶大于1的群一定没有零元的群一定没有零元(3)除了单位元外,一个群一定没有等幂元素。)除了单位元外,一个群一定没有等幂元素。(4)一个群)一个群(G,)的方程:的方程:a x=b 与与 y a=b,其,其 中中 a,b G 在群内有唯一解。在群内有唯一解。3、群的第二个定义、群的第二个定义 定义定义6.12 一个代数系统一个代数系统(G,)若满足下列条件,
11、若满足下列条件,则称为群则称为群 (1)满足结合律;)满足结合律;(2)方程:)方程:a x=b 与与 y a=b,其,其 中中 a,b G 在在G内有唯一解。内有唯一解。4、群的同构、群的同构定义定义6.13 设设(G,)与与(H,*)是两个群,若存在一是两个群,若存在一个函数个函数 g:G H,使得对每个,使得对每个a,b G,有,有 g(a b)=g(a)*g(b)则称则称g是从是从(G,)到到(H,*)的群同态。的群同态。若若 g:G H 是一一对应的,则称是一一对应的,则称 g 是从是从(G,)到到(H,*)的群同构。的群同构。定理定理6.9:设设(G,)与与(H,*)是两个群,有一
12、个函数是两个群,有一个函数 g:G H 使其群同态,则有使其群同态,则有 g(e G)=e H g(a-1)=g(a)-1定理定理6.9:设设(G,)是一个群,若是一个群,若(G,)与与(H,*)满满同态或同构,则同态或同构,则(H,*)也构成群。也构成群。二、变换群二、变换群 定义定义6.14 集合集合S上的若干个变换与复合运算若构上的若干个变换与复合运算若构成群,则此种群叫变换群。成群,则此种群叫变换群。定理定理6.9:任一个群均与一个变换群同构。任一个群均与一个变换群同构。三、有限群三、有限群群表:群表:对有限群,可用一张组合表将其运算表示出对有限群,可用一张组合表将其运算表示出来,称为
13、群表。来,称为群表。设有限群设有限群(G,*),其中,其中G=1,2,3,这个,这个群可用表群可用表6.3所示的群表定义所示的群表定义*123112322313312表表6.3群表的特性:群表的特性:(1)总存在一行(或一列)其元素与横线上(或竖总存在一行(或一列)其元素与横线上(或竖 线左边)的元素一样。线左边)的元素一样。(2)每一行(列)内元素各不相同,且任两行(列)每一行(列)内元素各不相同,且任两行(列)对应元素间也均不相同,故群表每一行(列)是对应元素间也均不相同,故群表每一行(列)是 G中元素的一个全排列。中元素的一个全排列。(3)若群是可换群,则群表是对称的。若群是可换群,则群
14、表是对称的。由群表可知,一个阶为由群表可知,一个阶为n的有限群的有限群(G,*),它,它的每个元素对应的每个元素对应G的一个置换,就是说:的一个置换,就是说:设有有限群设有有限群(G,*),其中,其中G=a1,a2,an,则,则存在一个函数存在一个函数:),2,1(2121nipaaaaaaaaaakiniiini 由这些置换组成一个集合由这些置换组成一个集合 knkkpppP,21 则集合则集合P与其复合运算构成一个群,即一个置换群。与其复合运算构成一个群,即一个置换群。如表如表6.3中中G的每个元素对应的置换所组成的集合为的每个元素对应的置换所组成的集合为 651,pppP 存在一个函数存
15、在一个函数:6513,2,1ppp 集合集合P与其复合运算构成一个置换群。与其复合运算构成一个置换群。定理定理6.15:每个有限群均与一个置换群同构。每个有限群均与一个置换群同构。因此,当有限群因此,当有限群(G,*)分别为分别为1,2,3阶群时,阶群时,*运运算都只有一个定义方式(即不计元素记号的不同算都只有一个定义方式(即不计元素记号的不同,只只有一张定义有一张定义*运算的运算表,分别如表运算的运算表,分别如表6.4、6.5和和6.3所示),于是可以说:所示),于是可以说:1,2,3阶的群都只有一个。阶的群都只有一个。*111表表6.4*12112223表表6.54阶群的群表不只一个阶群的
16、群表不只一个*123411234221433342144312*123411234224133314244321*123411234223413341244123四、循环群四、循环群定义定义6.16:设设(G,)是一个群,是一个群,aG,则令:,则令:a0=e,a j+1=a j a (j 0),),a-j=(a-1)j(j 0)由定义可得到由定义可得到 a m a n=a m+n,(a n)m=a m n群中元素方幂的定义群中元素方幂的定义定义定义6.17:若一个群若一个群(G,)的每一个元素均是它的某的每一个元素均是它的某一个固定元素一个固定元素 a 的某次方幂,则称的某次方幂,则称(G,
17、)是由是由 a 生成生成的循环群,而的循环群,而a 称为称为(G,)的生成元素。记为的生成元素。记为定义定义6.18:一个由一个由 a 生成的循环群生成的循环群(G,),若存在,若存在m,使得使得 am=e 的最小正整数的最小正整数 m 称为称为 a 的周期,若不存的周期,若不存在这样的一个在这样的一个m,则称,则称 a 的周期为无限。的周期为无限。例例1:整数加群:整数加群(I,+)是一个生成周期为无限的循是一个生成周期为无限的循环群。环群。1或(或(l)为其生成元。)为其生成元。例例2:剩余类加群:剩余类加群(Nm,+m)是一个生成周期为是一个生成周期为m的循环群。的循环群。1 为其生成元
18、。为其生成元。定理定理6.16:设有一个由设有一个由 a 生成的循环群生成的循环群(G,),则有,则有(1)若若a 的周期无限,则的周期无限,则(G,)与与(I,+)同构。同构。(2)(2)若若a 的周期为的周期为m,则,则(G,)与与(Nm,+m)同构。同构。四、子群四、子群定理定理6.17:一个群一个群(G,)及由它的一个子集及由它的一个子集H组成组成一个代数一个代数(H,),该代数构成一个,该代数构成一个(G,)的子群的子群的充要条件是:的充要条件是:a,b H,则,则 a b H a H,则,则 a-1 H定理定理6.18:设设(G,)是一个群,而是一个群,而(H,)是是(G,)的子群,则的子群,则(H,)的单位元素即是的单位元素即是(G,)的单位元的单位元素;素;(H,)内内 a 的逆元素即是的逆元素即是(G,)内内 a 的逆元素。的逆元素。定理定理6.19:设设(G,)是一个群,是一个群,G的子集的子集H组成一组成一个代数个代数(H,)构成构成(G,)的子群的充要条件是:的子群的充要条件是:若若 a,b H,则,则 a b-1 H定理定理6.20:设设(G,)是一个群,是一个群,G的一个有限子集的一个有限子集H组成一个代数组成一个代数(H,)构成构成(G,)的子群的充要的子群的充要条件是:条件是:若若 a,b H,则,则 a b H