离散数学第六章群论课件

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