离散数学第六章群论

,第二级,第三级,第四级,第五级,第6章,群论,第六章 群论,6.1 半群与单元半群,6.2 群,群在代码的查错、改错的研究，自动机理论等方面都有应用。,6.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仍是字母串。,定理6.1,一个半群(,S,，,)，如果它有一个子代数 (M，,) ，则此子代数也是一个半群。,定义6.2,一个半群(,S,，,)的子代数 (M，,)也是半群，称为(,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,为半群中的,等幂元素,。,2、,一些特殊半群。,(1) 可交换半群：,如果半群(,S,，,)中二元运算,是可交换的，则称(,S,，,) 是可交换半群。,例如：(I,+)，(I,)， (,( E), ) ，(,( E), ) (N,4,，+,4,) , (N,4,，,4,)均是可交换半群。但( X,*,，,)不是可交换半群。,(2) 循环半群：,一个半群(,S,，,)如果它的每个元素均为S内某一固定元素,a,的某一方幂，则此半群称为由,a,所生成的循环半群，元素,a,称为此半群的生成元素。,(3) 单元半群（或单位半群）：,有单位元素,e,的半群(S，,)，常记为(S，,，,e,)。,定理6.2：,一个循环半群一定是可交换半群。,定理6.3：,一个半群内的任一元素,a,和它所有的幂组成一个由,a,所生成的循环子半群。,例：下面半群都是单位半群,(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,，,)如果由它的一个元素,a,所生成，则称为由,a,所生成的循环单位半群，元素,a,称为此单位半群的生成元素。,定理6.6,：,一个循环单位半群是一个可换单位半群。,6.2 群,一、群与群的同构,1、群的有关定义,定义6.7,如果代数系统(,G,，,)满足,（1） (,G,，,)为一半群；,（2） (,G,，,)中有单位元,e,；,（3） (,G,，,)中每一元素,a,G,都有逆元,a,-1,则称代数系统(,G,，,)为群。,例如：(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,)都是阿贝尔群。,定义6.9,一个群(,G,，,)如果它的一个子代数(,H,，,)也是一个群，则称(,H,，,)是(,G,，,)的一个群。,定义6.10,一个群(,G,，,)如果它的元素个数是有限的，则称为有限群。如果它的元素个数是无限的，则称为无限群。,定义6.11,一个群(,G,，,)的阶记为|G|，如果一个群是有限群，则阶为元素个数，如果一个群为无限群，则阶为无穷大。,2、群的一些性质,（1） 群满足消去律,（2） 一个阶大于1的群一定没有零元,（3）除了单位元外，一个群一定没有等幂元素。,（4）一个群(,G,，,)的方程：,a,x = b,与,y,a = b,，其 中,a, b,G,在群内有唯一解。,3、群的第二个定义,定义6.12,一个代数系统(,G,，,)若满足下列条件，则称为群,（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，*)是两个群，有一个函数,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,：,任一个群均与一个变换群同构。,三、有限群,群表：,对有限群，可用一张组合表将其运算表示出来，称为群表。,设有限群(,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) 若群是可换群，则群表是对称的。,由群表可知，一个阶为n的有限群(,G,，,*,)，它的每个元素对应G的一个置换，就是说：,设有有限群(,G,，,*,)，其中G=,a,1,a,2, ,a,n,，则存在一个函数,：,由这些置换组成一个集合,则集合P与其复合运算构成一个群，即一个置换群。,如表6.3中G的每个元素对应的置换所组成的集合为,存在一个函数,：,集合P与其复合运算构成一个置换群。,定理6.15,：,每个有限群均与一个置换群同构。,因此，当有限群(,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,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,*,1,2,3,4,1,1,2,3,4,2,2,3,4,1,3,3,4,1,2,4,4,1,2,3,四、循环群,定义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.17：,若一个群(,G,，,)的每一个元素均是它的某一个固定元素,a,的某次方幂，则称(,G,，,)是由,a,生成的循环群，而,a,称为(,G,，,)的生成元素。记为,定义6.18：,一个由,a,生成的循环群(,G,，,)，若存在,m,，使得,a,m,=e,的最小正整数,m,称为,a,的周期，若不存在这样的一个,m,，则称,a,的周期为无限。,例1：整数加群 (I,+) 是一个生成周期为无限的循环群。 1或（l）为其生成元。,例2：剩余类加群 (N,m,，+,m,)是一个生成周期为m的循环群。 1 为其生成元。,定理6.16,：,设有一个由,a,生成的循环群 (,G,，,)，则有,若,a,的周期无限，则,(,G,，,),与,(I,+),同构。,(2),若,a,的周期为,m,，则,(,G,，,),与,(N,m,，,+,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,