《离散数学第六章群论.ppt》由会员分享，可在线阅读，更多相关《离散数学第六章群论.ppt（33页珍藏版）》请在三一办公上搜索。
1、第六章 群论,6.1 半群与单元半群 6.2 群,群在代码的查错、改错的研究，自动机理论等方面都有应用。,6.1 半群与单元半群,半群与群都是具有一个二元运算的代数系统，群是半群的特殊例子。事实上，群是历史上最早研究的代数系统，它比半群复杂一些，而半群概念是在群的理论发展之后才引进的。逻辑关系见图。,图 6.1.1,群,半群,一、半群1、半群的有关定义 定义6.1 设(S，)是代数系统，是二元运算，如果运算满足结合律，则称它为半群。换言之，a,b,cS,若是S上的封闭运算且满足(a b）c=a（b c），则(S，)是半群。许多代数系统都是半群。例如：(I,+)，(I,)，(E),)，(E),)
2、,(N4，+4),(N4，4)均是半群。,再如，设X是有限字母表，X+是 X 中的字母串，X*=X+，其中是不含字母的空串，运算是字母串的“并置”运算，则(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 即半群中的元素有时可用某些元素的幂表示出来。因为半群满足结合律，所以可得到 a m a n=a m+
3、n，(a n)m=a m n。如果有a2=a，则称a为半群中的等幂元素。,2、一些特殊半群。(1)可交换半群：如果半群(S，)中二元运算是可交换的，则称(S，)是可交换半群。例如：(I,+)，(I,)，(E),)，(E),)(N4，+4),(N4，4)均是可交换半群。但(X*，)不是可交换半群。,(2)循环半群：一个半群(S，)如果它的每个元素均为S内某一固定元素 a 的某一方幂，则此半群称为由 a 所生成的循环半群，元素 a 称为此半群的生成元素。,(3)单元半群（或单位半群）：有单位元素e的半群(S，)，常记为(S，e)。,定理6.2：一个循环半群一定是可交换半群。,定理6.3：一个半群内
4、的任一元素 a 和它所有的幂组成一个由 a 所生成的循环子半群。,例：下面半群都是单位半群(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，)，如果存在一个子代数(M，)，且其单位元 e M，则(M，)也是一个单位半群。,定义6.5 一个单位半群(S，)，如果存在一个子代数(M，)，且其单位元 e
5、 M，则(M，)也是一个单位半群，称为(S，)的子单位半群。,定义6.5：一个单位半群(S，)如果由它的一个元素a 所生成，则称为由 a 所生成的循环单位半群，元素 a 称为此单位半群的生成元素。,定理6.6：一个循环单位半群是一个可换单位半群。,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),)，
6、(E),),(N4，4)均不是群。,定义6.8 一个群(G，)如果满足交换律，则称为可交换群或称阿贝尔群。,例如：群(I,+)，(N4，+4)都是阿贝尔群。,定义6.9 一个群(G，)如果它的一个子代数(H，)也是一个群，则称(H，)是(G，)的一个群。,定义6.10 一个群(G，)如果它的元素个数是有限的，则称为有限群。如果它的元素个数是无限的，则称为无限群。,定义6.11 一个群(G，)的阶记为|G|，如果一个群是有限群，则阶为元素个数，如果一个群为无限群，则阶为无穷大。,2、群的一些性质,（1）群满足消去律,（2）一个阶大于1的群一定没有零元,（3）除了单位元外，一个群一定没有等幂元素。
7、,（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
8、使其群同态，则有 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所示的群表定义,表6.3,群表的特性：,(1)总存在一行（或一列）其元素与横线上（或竖 线左边）的元素一样。(2)每一行（列）内元素各不相同，且任两行（列）对应元素间也均不相同，故群
9、表每一行（列）是 G中元素的一个全排列。(3)若群是可换群，则群表是对称的。,由群表可知，一个阶为n的有限群(G，*)，它的每个元素对应G的一个置换，就是说：设有有限群(G，*)，其中G=a1,a2,an，则存在一个函数：,由这些置换组成一个集合,则集合P与其复合运算构成一个群，即一个置换群。,如表6.3中G的每个元素对应的置换所组成的集合为,存在一个函数：,集合P与其复合运算构成一个置换群。,定理6.15：每个有限群均与一个置换群同构。,因此，当有限群(G，*)分别为1，2，3阶群时，*运算都只有一个定义方式（即不计元素记号的不同,只有一张定义*运算的运算表，分别如表6.4、6.5和6.3所
10、示），于是可以说：1，2，3阶的群都只有一个。,表6.4,表6.5,4阶群的群表不只一个,四、循环群,定义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，)是由 a 生成的循环群，而a 称为(G，)的生成元素。记为,定义6.18：一个由 a 生成的循环群(G，)，若存在m，使得 am=e 的最小正整数 m 称为 a 的周期，若不存在这样的一个m，则称
11、 a 的周期为无限。,例1：整数加群(I,+)是一个生成周期为无限的循环群。1或（l）为其生成元。,例2：剩余类加群(Nm，+m)是一个生成周期为m的循环群。1 为其生成元。,定理6.16：设有一个由 a 生成的循环群(G，)，则有若a 的周期无限，则(G，)与(I,+)同构。(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,
