离散数学第六章群论课件.ppt

《离散数学第六章群论课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第六章群论课件.ppt（33页珍藏版）》请在三一办公上搜索。

1、第六章 群论,6.1 半群与单元半群 6.2 群,第六章 群论 6.1 半群与单元半群,群在代码的查错、改错的研究，自动机理论等方面都有应用。,群在代码的查错、改错的研究，自动机理论等方面都有应,6.1 半群与单元半群,半群与群都是具有一个二元运算的代数系统，群是半群的特殊例子。事实上，群是历史上最早研究的代数系统，它比半群复杂一些，而半群概念是在群的理论发展之后才引进的。逻辑关系见图6.1.1。,6.1 半群与单元半群 半群与群,图 6.1.1,群,半群,图 6.1.1 群半群,一、半群1、半群的有关定义 定义6.1 设(S，)是代数系统，是二元运算，如果运算满足结合律，则称它为半群。 换言

2、之，a, b, cS, 若是S上的封闭运算且满足(a b） c=a （b c），则(S，)是半群。 许多代数系统都是半群。例如：(I,+)，(I,)， ( E), ) ，( E), ), (N4，+ 4) , (N4，4)均是半群。,一、半群,再如，设X是有限字母表，X+是 X 中的字母串， X *= X +，其中是不含字母的空串，运算是字母串的“并置”运算，则( X *， )是半群。如Com X * ，puter X *，经 运算后，得Computer仍是字母串。,再如，设X是有限字母表，X+是 X,定理6.1 一个半群(S，)，如果它有一个子代数 (M， ) ，则此子代数也是一个半群。,定

3、义6.2 一个半群(S，)的子代数 (M， )也是半群，称为(S，)的子半群。,定理6.1 一个半群(S，)，如果它有一,一个半群(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为半群中的等幂元素。,一个半群(S，)中的元素a ，可定义它的,2、一些特殊半群。 (1) 可交换半群： 如果半群(S，)中二元运算是可交换的，则称(S，) 是可交换半群。 例如：(I,+)，(I,)， ( E),

4、 ) ，( E), ) (N4，+ 4) , (N4，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，),例：下

5、面半群都是单位半群 (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 一个单位半群(

6、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，)中每一元素aG都

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

8、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 一个代数系统

9、(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 ：设

10、(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，这个

11、群可用表6.3所示的群表定义,表6.3,三、有限群群表：对有限群，可用一张组合表将其运算表示出来，称,群表的特性：,(1) 总存在一行（或一列）其元素与横线上（或竖 线左边）的元素一样。(2) 每一行（列）内元素各不相同，且任两行（列） 对应元素间也均不相同，故群表每一行（列）是 G中元素的一个全排列。(3) 若群是可换群，则群表是对称的。,群表的特性： (1) 总存在一行（或一列）其元素与横线上（或,由群表可知，一个阶为n的有限群(G，* )，它的每个元素对应G的一个置换，就是说： 设有有限群(G，* )，其中G=a1, a2, , an，则存在一个函数：,由这些置换组成一个集合,则集合P与

12、其复合运算构成一个群，即一个置换群。,由群表可知，一个阶为n的有限群(G，* )，它的,如表6.3中G的每个元素对应的置换所组成的集合为,存在一个函数：,集合P与其复合运算构成一个置换群。,定理6.15 ：每个有限群均与一个置换群同构。,如表6.3中G的每个元素对应的置换所组成的集合为存在一个函数,因此，当有限群(G，* ) 分别为1，2，3阶群时，*运算都只有一个定义方式（即不计元素记号的不同,只有一张定义*运算的运算表，分别如表6.4、6.5和6.3所示），于是可以说：1，2，3阶的群都只有一个。,表6.4,表6.5,因此，当有限群(G，* ) 分别为1，2，3阶群时，*运算都,4阶群的群

13、表不只一个,4阶群的群表不只一个*1234112342214333421,*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.16： 设(G，)是一个群，aG ，则,定义6.17：若一个群(G，)的每一个元素均是它的某一个固定元素 a 的某次方幂，则称(G，)是由 a 生成的循环群，而a 称为(G，)的生成元素。记为,定义6

14、.18：一个由 a 生成的循环群(G，)，若存在m，使得 am =e 的最小正整数 m 称为 a 的周期，若不存在这样的一个m，则称 a 的周期为无限。,定义6.17：若一个群(G，)的每一个元素均是它的某一个固,例1：整数加群 (I,+) 是一个生成周期为无限的循环群。 1或（l）为其生成元。,例2：剩余类加群 (Nm，+m)是一个生成周期为m的循环群。 1 为其生成元。,定理6.16 ：设有一个由 a 生成的循环群 (G，)，则有若a 的周期无限，则(G，) 与(I,+)同构。(2) 若a 的周期为m，则(G，) 与(Nm，+m)同构。,例1：整数加群 (I,+) 是一个生成周期为无限的循

15、环群。,四、子群,定理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,定理6.19： 设(G， )是一个群，G的子集H组成一个代,