离散数学第六章群论.ppt

《离散数学第六章群论.ppt》由会员分享，可在线阅读，更多相关《离散数学第六章群论.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 群论群论 第六章第六章 群论群论 6.1 半群与单元半群半群与单元半群 6.2 群群 第第6章章 群论群论 群群在在代代码码的的查查错错、改改错错的的研研究究，自自动动机机理理论论等等方面都有应用。方面都有应用。第第6章章 群论群论 6.1 半群与单元半群半群与单元半群 半半群群与与群群都都是是具具有有一一个个二二元元运运算算的的代代数数系系统统，群群是是半半群群的的特特殊殊例例子子。事事实实上上，群群是是历历史史上上最最早早研研究究的的代代数数系系统统，它它比比半半群群复复杂杂一一些些，而而半半群群概概念念是是在在群群的的理理论论发发展展之之后后才才引引进进的的。逻辑关系见图。逻

2、辑关系见图。第第6章章 群论群论 图图 6.1.1 群群半群半群第第6章章 群论群论 一、半群一、半群1、半群的有关定义、半群的有关定义 定定义义6.1 设设(S，)是是代代数数系系统统，是是二二元元运运算算，如果如果 运算满足结合律，则称它为半群。运算满足结合律，则称它为半群。换换言言之之，a,b,cS,若若 是是S上上的的封封闭闭运运算算且且满足满足(a b）c=a （b c），则），则(S，)是半群。是半群。许多代数系统都是半群。例如：许多代数系统都是半群。例如：(I,+)，(I,)，(E),)，(E),),(N4，+4),(N4，4)均是半群。均是半群。第第6章章 群论群论 再如，设再

3、如，设X是有限字母表，是有限字母表，X+是是 X 中的字母中的字母串，串，X*=X+，其中，其中是不含字母的空串，是不含字母的空串，运算运算 是字母串的是字母串的“并置并置”运算，则运算，则(X*，)是是半群。如半群。如Com X*，puter X*，经经 运算后，运算后，得得Computer仍是字母串。仍是字母串。第第6章章 群论群论 定理定理6.1 一个半群一个半群(S，)，如果它有一个子代，如果它有一个子代数数(M，)，则此子代数也是一个半群。，则此子代数也是一个半群。定义定义6.2 一个半群一个半群(S，)的子代数的子代数(M，)也也是半群，称为是半群，称为(S，)的子半群。的子半群。

4、第第6章章 群论群论 一个半群一个半群(S，)中的元素中的元素a，可定义它的幂：，可定义它的幂：a1=a,a2=a a,，an+1=an a 即即半半群群中中的的元元素素有有时时可可用用某某些些元元素素的的幂幂表表示示出出来。来。因为半群满足结合律，所以可得到因为半群满足结合律，所以可得到 a m a n=a m+n，(a n)m=a m n。如果有如果有a2=a，则称，则称a为半群中的为半群中的等幂元素等幂元素。第第6章章 群论群论 2、一些特殊半群。一些特殊半群。(1)可交换半群：可交换半群：如果半群如果半群(S，)中二元运算中二元运算 是是可交换的，则称可交换的，则称(S，)是可交换半群

5、。是可交换半群。例如：例如：(I,+)，(I,)，(E),)，(E),)(N4，+4),(N4，4)均是可交换半群。但均是可交换半群。但(X*，)不是可交换半群。不是可交换半群。(2)循环半群：循环半群：一个半群一个半群(S，)如果它的每个元如果它的每个元素均为素均为S内某一固定元素内某一固定元素 a 的某一方幂，则此半的某一方幂，则此半群称为由群称为由 a 所生成的循环半群，元素所生成的循环半群，元素 a 称为此半称为此半群的生成元素。群的生成元素。第第6章章 群论群论 (3)单元半群（或单位半群）：单元半群（或单位半群）：有单位元素有单位元素e的的半群半群(S，)，常记为，常记为(S，e)

6、。定理定理6.2：一个循环半群一定是可交换半群。一个循环半群一定是可交换半群。定理定理6.3：一个半群内的任一元素一个半群内的任一元素 a 和它所有的幂和它所有的幂组成一个由组成一个由 a 所生成的循环子半群。所生成的循环子半群。第第6章章 群论群论 例：下面半群都是单位半群例：下面半群都是单位半群 (I,+)单位元素是单位元素是0，可记为，可记为(I,+,0);(I,)单位元素是单位元素是1，可记为，可记为(I,1)；(X*，)单位元素是单位元素是(空串空串)，可记为可记为(X*，,)；(E),)单位元素是单位元素是，可记为，可记为(E),)；(E),)单位元素是单位元素是E，可记为，可记为

7、(E),E)。(N4，+4)单位元素是单位元素是0，可记为，可记为(N4，+4，0)(N4，4)单位元素是单位元素是1，可记为，可记为(N4，4，1)第第6章章 群论群论 定理定理6.5 一个单位半群一个单位半群(S，)，如果存在一个，如果存在一个子代数子代数(M，)，且其单位元，且其单位元 e M，则则(M，)也是一个单位半群。也是一个单位半群。定义定义6.5 一个单位半群一个单位半群(S，)，如果存在一个，如果存在一个子代数子代数(M，)，且其单位元，且其单位元 e M，则则(M，)也是一个单位半群，称为也是一个单位半群，称为(S，)的子单位半群的子单位半群。第第6章章 群论群论 定义定义

8、6.5：一个单位半群一个单位半群(S，)如果由它的一个如果由它的一个元素元素a 所生成，则称为由所生成，则称为由 a 所生成的循环单位半所生成的循环单位半群，元素群，元素 a 称为此单位半群的生成元素。称为此单位半群的生成元素。定理定理6.6：一个循环单位半群是一个可换单位半一个循环单位半群是一个可换单位半群。群。第第6章章 群论群论 6.2 群群一、群与群的同构一、群与群的同构1、群的有关定义、群的有关定义 定义定义6.7 如果代数系统如果代数系统(G，)满足满足 （1）(G，)为一半群；为一半群；（2）(G，)中有单位元中有单位元e；（3）(G，)中每一元素中每一元素aG都有逆元都有逆元

9、a-1 则称代数系统则称代数系统(G，)为群。为群。第第6章章 群论群论 例如：例如：(I,+)是群，因是群，因 a I 都有逆元都有逆元-a；(N4，+4)是群是群,0的逆元是的逆元是0，1的逆元是的逆元是3，2的逆元是的逆元是2。(I,)，(X*，)，(E),)，(E),),(N4，4)均不是群。均不是群。定义定义6.8 一个群一个群(G，)如果满足交换律，则称为如果满足交换律，则称为可交换群或称阿贝尔群。可交换群或称阿贝尔群。例如：群例如：群(I,+)，(N4，+4)都是阿贝尔群。都是阿贝尔群。第第6章章 群论群论 定义定义6.9 一个群一个群(G，)如果它的一个子代数如果它的一个子代数

10、(H，)也是一个群，则称也是一个群，则称(H，)是是(G，)的一个群。的一个群。定义定义6.10 一个群一个群(G，)如果它的元素个数是有限如果它的元素个数是有限的，则称为有限群。如果它的元素个数是无限的，的，则称为有限群。如果它的元素个数是无限的，则称为无限群。则称为无限群。定义定义6.11 一个群一个群(G，)的阶记为的阶记为|G|，如果一个群，如果一个群是有限群，则阶为元素个数，如果一个群为无限群，是有限群，则阶为元素个数，如果一个群为无限群，则阶为无穷大。则阶为无穷大。第第6章章 群论群论 2、群的一些性质、群的一些性质（1）群满足消去律群满足消去律（2）一个阶大于一个阶大于1的群一定

11、没有零元的群一定没有零元（3）除了单位元外，一个群一定没有等幂元素。）除了单位元外，一个群一定没有等幂元素。（4）一个群）一个群(G，)的方程：的方程：a x=b 与与 y a=b，其，其 中中 a,b G 在群内有唯一解。在群内有唯一解。第第6章章 群论群论 3、群的第二个定义、群的第二个定义 定义定义6.12 一个代数系统一个代数系统(G，)若满足下列条件，若满足下列条件，则称为群则称为群 （1）满足结合律；）满足结合律；（2）方程：）方程：a x=b 与与 y a=b，其，其 中中 a,b G 在在G内有唯一解。内有唯一解。第第6章章 群论群论 4、群的同构、群的同构定义定义6.13 设

12、设(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章章 群论群论 定理定理6.9：设设(G，)与与(H，*)是两个群，有一个函数是两个群，有一个函数 g:G H 使其群同态，则有使其群同态，则有 g(e G)=e H g(a-1)=g(a)-1定理定理6.9：设设(G，)是一个群，若是一个群，若(G，)与与(H，

13、*)满满同态或同构，则同态或同构，则(H，*)也构成群。也构成群。第第6章章 群论群论 二、变换群二、变换群 定义定义6.14 集合集合S上的若干个变换与复合运算若构上的若干个变换与复合运算若构成群，则此种群叫变换群。成群，则此种群叫变换群。定理定理6.9：任一个群均与一个变换群同构。任一个群均与一个变换群同构。第第6章章 群论群论 三、有限群三、有限群群表：群表：对有限群，可用一张组合表将其运算表示出对有限群，可用一张组合表将其运算表示出来，称为群表。来，称为群表。设有限群设有限群(G，*)，其中，其中G=1，2，3，这个，这个群可用表群可用表6.3所示的群表定义所示的群表定义*123112

14、322313312表表6.3第第6章章 群论群论 群表的特性：群表的特性：(1)总存在一行（或一列）其元素与横线上（或竖总存在一行（或一列）其元素与横线上（或竖 线左边）的元素一样。线左边）的元素一样。(2)每一行（列）内元素各不相同，且任两行（列）每一行（列）内元素各不相同，且任两行（列）对应元素间也均不相同，故群表每一行（列）是对应元素间也均不相同，故群表每一行（列）是 G中元素的一个全排列。中元素的一个全排列。(3)若群是可换群，则群表是对称的。若群是可换群，则群表是对称的。第第6章章 群论群论 由群表可知，一个阶为由群表可知，一个阶为n的有限群的有限群(G，*)，它，它的每个元素对应的

15、每个元素对应G的一个置换，就是说：的一个置换，就是说：设有有限群设有有限群(G，*)，其中，其中G=a1,a2,an，则存在一个函数则存在一个函数：由这些置换组成一个集合由这些置换组成一个集合则集合则集合P与其复合运算构成一个群，即一个置换群。与其复合运算构成一个群，即一个置换群。第第6章章 群论群论 如表如表6.3中中G的每个元素对应的置换所组成的集合为的每个元素对应的置换所组成的集合为存在一个函数存在一个函数：集合集合P与其复合运算构成一个置换群。与其复合运算构成一个置换群。定理定理6.15：每个有限群均与一个置换群同构。每个有限群均与一个置换群同构。第第6章章 群论群论 因此，当有限群因

16、此，当有限群(G，*)分别为分别为1，2，3阶群时，阶群时，*运运算都只有一个定义方式（即不计元素记号的不同算都只有一个定义方式（即不计元素记号的不同,只只有一张定义有一张定义*运算的运算表，分别如表运算的运算表，分别如表6.4、6.5和和6.3所示），于是可以说：所示），于是可以说：1，2，3阶的群都只有一个。阶的群都只有一个。*111表表6.4*12112223表表6.5第第6章章 群论群论 4阶群的群表不只一个阶群的群表不只一个*123411234221433342144312*123411234224133314244321第第6章章 群论群论 *1234112342234133412

17、44123第第6章章 群论群论 四、循环群四、循环群定义定义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章章 群论群论 定义定义6.17：若一个群若一个群(G，)的每一个元素均是它的某的每一个元素均是它的某一个固定元素一个固定元素 a 的某次方幂，则称的某次方幂，则称(G，)是由是由 a 生成生成的循环群，而的循环群，而a 称为称为(G，)的生成元素。记为的生成元素。记为定义定义

18、6.18：一个由一个由 a 生成的循环群生成的循环群(G，)，若存在，若存在m，使得，使得 am=e 的最小正整数的最小正整数 m 称为称为 a 的周期，若不的周期，若不存在这样的一个存在这样的一个m，则称，则称 a 的周期为无限。的周期为无限。第第6章章 群论群论 例例1：整数加群：整数加群(I,+)是一个生成周期为无限的是一个生成周期为无限的循环群。循环群。1或（或（l）为其生成元。）为其生成元。例例2：剩余类加群：剩余类加群(Nm，+m)是一个生成周期为是一个生成周期为m的循环群。的循环群。1 为其生成元。为其生成元。定理定理6.16：设有一个由设有一个由 a 生成的循环群生成的循环群(

19、G，)，则有，则有(1)若若a 的周期无限，则的周期无限，则(G，)与与(I,+)同构。同构。(2)(2)若若a 的周期为的周期为m，则，则(G，)与与(Nm，+m)同构。同构。第第6章章 群论群论 四、子群四、子群定理定理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章章 群论群论 定理定理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