离散数学第13章群

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程离离 散散 数数 学学20222022年年1 1月月1 1日星期六日星期六电子科技大学计算机科学与工程学院电子科技大学计算机科学与工程学院电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-2 22022-1-12022-1-1第第1313章章 群群正规子群正规子群5特殊群特殊群3半群与含幺半群半群与含幺半群1群及其性质群及其性质2陪集与拉格朗日定理陪集与拉格朗日定理4电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品

2、国家精品课程课程 双语示范课程双语示范课程157-157-3 32022-1-12022-1-113.1 13.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 半群、群、子半群、群、子群及性质群及性质2 2 元素的周期及计元素的周期及计算算3 3 生成元与循环群生成元与循环群4 4 陪集与拉氏定理陪集与拉氏定理 3商群及性质商群及性质2正规子群性质正规子群性质与同态核与同态核电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-4 42022-1-12022-1-113.213.2半群与含幺半群半群与

3、含幺半群定义定义13.2.113.2.1 在二元代数在二元代数S, 中，若二元运算中，若二元运算“ ”满足结合律，则称满足结合律，则称S, 为为半群半群；若半群若半群S, 中的二元运算中的二元运算“ ”满足交换律，则满足交换律，则称称S, 为为可交换半群可交换半群。定义定义13.2.213.2.2 设设S, 为半群，若为半群，若S S中存在关于运中存在关于运算算“ ”的幺元的幺元e e，则称此半群为，则称此半群为含幺半群（或独异含幺半群（或独异点），点），有时也记为有时也记为S, , e；若若含幺半群含幺半群S, , e中运算中运算“ ”满足交换律，则满足交换律，则称称S, , e为为可交换含

4、幺半群（可交换独异点）可交换含幺半群（可交换独异点）。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-5 52022-1-12022-1-1例例13.2.1 13.2.1 设设A A是非空集合，是非空集合，A AA A表示所有表示所有A A到到A A的函数集合，的函数集合，运算运算“ ”表示映射的复合运算，证明表示映射的复合运算，证明A 是半是半群。群。分析分析 只需证明运算只需证明运算“ ”满足封闭性和结合律。满足封闭性和结合律。证明证明 对任意对任意f, f, g gA AA A， 显然有显然有f f g gA AA A

5、， 故封闭性成立。故封闭性成立。又函数复合运算又函数复合运算“ ”满足结合律，满足结合律，所以所以A 是半群。是半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-6 62022-1-12022-1-1例例13.2.2 13.2.2 设设S S是一个集合，是一个集合，P(S)P(S)是是S S的幂集合，试证明代的幂集合，试证明代数系统数系统 与与都是可交换的含都是可交换的含幺半群。幺半群。分析分析 运算运算“”和和“”显然满足交换律，因此显然满足交换律，因此只需说明只需说明 与与是半群，并计是半群，并计算它们的幺元即可。算

6、它们的幺元即可。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-7 72022-1-12022-1-1例例13.2.213.2.2（续）（续）证明证明 显然运算显然运算“”和和“”均满足结合律和交均满足结合律和交换律，因此它们是可交换的半群。换律，因此它们是可交换的半群。易证易证和和S S分别是分别是 和和的幺的幺元。因此，元。因此， 与与是可交换的是可交换的含幺半群。含幺半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-8 82022-1-12022

7、-1-1例例13.2.3 13.2.3 设设 n n0, 1, 2, 0, 1, 2, , n-1, n-1, , 定义定义n n上的运上的运算算n n 如下：如下：x, x, yyn n, x, xn ny yx xy (mod n)y (mod n)( (即即x xy y除以除以n n的余数的余数) )。证明证明 是含么半群。是含么半群。证明证明：封闭性封闭性：x, x, yyn n, , 令令k kx xy (mod n), y (mod n), 则则0k0kn-1, n-1, 即即kkn n, , 所以封闭性成立；所以封闭性成立；电子科技大学离散数学课程组电子科技大学离散数学课程组国家

8、精品国家精品课程课程 双语示范课程双语示范课程157-157-9 92022-1-12022-1-1例例13.2.313.2.3（续）（续）结合律结合律：x, y, x, y, zzn n, , 有有(x(xn n y)y)n n z zx xy+zy+z (mod n) (mod n)x xn n (y(yn n z)z)所以结合律成立。所以结合律成立。么元么元：xxn n, , 显然有显然有 0 0n nx xx xn n0=x0=x所以所以0 0是么元。是么元。故故 是含么半群。是含么半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范

9、课程157-157-10102022-1-12022-1-1子半群和子含幺半群子半群和子含幺半群将子代数应用于半群，可得下面的定义：将子代数应用于半群，可得下面的定义：定义定义13.2.313.2.3 如果如果S, 是半群，是半群，T T是是S S的非空子集，的非空子集，且运算且运算“ ” 对对T T封闭，则称封闭，则称T 是半群是半群S, 的的子半群子半群；如果如果S, , e是含幺半群，是含幺半群，T T是是S S的非空子集，的非空子集，eTeT。且运算。且运算“ ”对对T T封闭，则称封闭，则称T, , e是含是含幺半群幺半群S, , e的的子含幺半群子含幺半群。电子科技大学离散数学课程

10、组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-11112022-1-12022-1-1例例13.2.4 13.2.4 设设S, 是含幺半群，是含幺半群，M = a | M = a | aSaS，对任意对任意xSxS 有有a a x x = = x x a a ，则则 M, 是是S, 的子含幺半群。的子含幺半群。分析分析 需证明两点：幺元存在，运算需证明两点：幺元存在，运算“ ” 封闭。封闭。证明证明 (1) (1) 设设e e是半群是半群S, 的幺元，则的幺元，则对任意对任意xSxS，显然有，显然有e e x = x x = x e e，因此，因

11、此，eMeM。进而。进而M M是是S S的非空子集。的非空子集。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-12122022-1-12022-1-1例例13.2.413.2.4（续）（续）（2 2）对任意）对任意a,bMa,bM，由，由M M的定义知，的定义知，对任意对任意xSxS，有，有a a x = x x = x a a， b b x = x x = x b b，又运算又运算“* *”满足结合律，则满足结合律，则(a (a b) b) x = a x = a (b (b x) x) = a = a (x (x b)

12、 = (a b) = (a x) x) b b = (x = (x a) a) b = x b = x (a (a b) b)，即即 对任意对任意xSxS, (a , (a b) b) x = x x = x (a (a b) b)，因此，因此，( (a a b)Mb)M。由由(1)(1)、(2)(2)可知：可知：M, 是的一个子含幺半群。是的一个子含幺半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-13132022-1-12022-1-1半群同态半群同态利用代数系统中同态与同构概念，得到半群（含幺利用代数系统中同态与

13、同构概念，得到半群（含幺半群）的同态与同构。半群）的同态与同构。设设S, 和和T, 是两个半群，映射是两个半群，映射f f：STST，对，对任意元素任意元素a, a, bSbS，都有，都有f(af(a b) = b) = f(a)f(a) f(bf(b) )，则映射则映射f f就是半群就是半群S, 到半群到半群T, 的同态映射。的同态映射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-14142022-1-12022-1-1半群同态（续）半群同态（续）如果半群如果半群S, 和和T, 是含幺半群，其中是含幺半群，其中e e，

14、1 1分分别是别是S, 和和T, 的幺元，而且映射的幺元，而且映射f f满足：满足：对任意对任意 a, a, bSbS, , f(af(a b) = b) = f(af(a) ) f(bf(b) )，且，且f(ef(e) = 1) = 1。则映射则映射f f就是含幺半群就是含幺半群S, , e到到T, , 1的同态的同态映射。映射。当当f f是单射、满射、双射时，相应的同态为是单射、满射、双射时，相应的同态为单一同态、单一同态、满同态、同构满同态、同构。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-15152022-1-1

15、2022-1-1例例13.2.5 13.2.5 设映射设映射f f：NN6 6，且，且对任意对任意xNxN，f(xf(x) = ) = x(modx(mod 6) 6)，则，则（1 1）f f是半群是半群到到 的同态映射；的同态映射；（2 2）f f是含幺半群是含幺半群到到 , 0的同态的同态映射。映射。分析分析 （1 1），需证明），需证明对任意对任意 a, a, bNbN，有，有f(af(a + b) + b) = = f(af(a) +) +6 6 f(bf(b) ) ； （2 2），在（），在（1 1）的基础上，还需说明）的基础上，还需说明f(0) = 0f(0) = 0。电子科技大学

16、离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-16162022-1-12022-1-1例例13.2.513.2.5（续）（续）证明证明 （1 1）对任意对任意 a, a, bNbN，有，有 f (a + b) = (a + f (a + b) = (a + b)(modb)(mod 6) 6) = (a (mod 6) + b (mod 6)(mod 6) = (a (mod 6) + b (mod 6)(mod 6) = a (mod 6)+ = a (mod 6)+6 6 b (mod 6) b (mod 6) = = f(af(

17、a) +) +6 6 f(bf(b) )，所以所以f f是同态映射。是同态映射。（2 2）根据）根据f f的定义，显然有的定义，显然有f(0) = 0f(0) = 0，又根据，又根据（1 1），则），则f f是含幺半群是含幺半群到到 , 0的的同态映射。同态映射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-17172022-1-12022-1-1结论结论设设f f是二元代数是二元代数A, 到到B, 的满同态，则根据的满同态，则根据第第1212章同态的性质，容易得到如下结论：章同态的性质，容易得到如下结论： （1 1）若）

18、若A, 是半群，则是半群，则B, 也是半群；也是半群；（2 2）若）若含幺半群，则含幺半群，则B, 也是含幺半群。也是含幺半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-18182022-1-12022-1-113.2.2 13.2.2 元素的幂元素的幂设设S, S, * *是一个半群是一个半群, , 对任意对任意x x S, S, 可定义：可定义：x x=x, xx, x=x x x, x, x x=x x x x= x x x=x x=x x x x, x, x xn n= =x xn-1 n-1 x=x x=x

19、x xn n - -=x x x x x x x x。 如果如果S, S, * *有幺元有幺元e, e, 可以定义：可以定义：x x0 0= =e e。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-19192022-1-12022-1-1元素的幂（续）元素的幂（续）由于结合律的满足由于结合律的满足, , 同样有同样有 如下的公式：如下的公式： a ax x a ay y=a=ax+ yx+ y (a (a) )=a=a电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程15

20、7-157-20202022-1-12022-1-1例例13.2.6 13.2.6 （1 1）设）设S, 是半群，是半群，aSaS， M = a M = an n | nZ | nZ+ + ，则则M, 是是S, 的子半群；的子半群；（2 2）设）设S, , e是含幺半群，是含幺半群，aSaS， M = a M = an n | nN | nN，则则M, 是是S, 的子含幺半群；的子含幺半群；分析分析 （1 1）M M是非空子集，运算是非空子集，运算“ ” 封闭。封闭。 （2 2）还需说明幺元）还需说明幺元e e在在M M中。中。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精

21、品课程课程 双语示范课程双语示范课程157-157-21212022-1-12022-1-1例例13.2.613.2.6（续）（续）证明证明 （1 1）a = aa = a1 1MM，所以，所以M M是非空集合。是非空集合。对任意对任意nZnZ+ +，a an nSS，因此，因此M M是是S S的非空子集。的非空子集。对任意对任意a an n，a am mMM，n n，mZmZ+ +，则，则a an n a am m = a = an+mn+m，n + mZn + mZ+ +， a an n a am mMM。故运算故运算“ ” 封闭。封闭。M, 是是S, 的子半群。的子半群。（2 2）幺元）

22、幺元e = ae = a0 0MM，即幺元在，即幺元在M M中。类似（中。类似（1 1），），同理可证同理可证M, 是是S, 的子含幺半群。的子含幺半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-22222022-1-12022-1-113.2.3 13.2.3 循环半群循环半群定义定义13.2.413.2.4 （1 1）在半群）在半群S, 中，若存在一个中，若存在一个元素元素aSaS，使得对任意，使得对任意xSxS，都有，都有x = ax = an n，其中，其中nZnZ+ +，则称则称S, 为为循环半群循环半群，并

23、称，并称a a为该循环半群的一为该循环半群的一个个生成元生成元，M = a | (aS)M = a | (aS)且且a a是是S S的生成元的生成元 称为称为该循环半群的该循环半群的生成集生成集。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-23232022-1-12022-1-1定义定义13.2.413.2.4（续）（续）（2 2）在含幺半群）在含幺半群S, , e中，若存在一个中，若存在一个元素元素aSaS，使得对任意，使得对任意xSxS，都有，都有x = ax = an n，其中，其中nNnN，则称此循环含幺半群为则

24、称此循环含幺半群为循环含幺半群（或循循环含幺半群（或循环独异点），环独异点），并称并称a a为该循环含幺半群的一为该循环含幺半群的一个个生成元生成元，M = a | (aS)M = a | (aS)且且a a是是S S的生成的生成元元 称为该循含幺半群的称为该循含幺半群的生成集生成集。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-24242022-1-12022-1-1例例13.2.7 13.2.7 判断含幺半群判断含幺半群是否是一个循环含幺半群？是否是一个循环含幺半群？分析分析 根据定义，判别含幺半群（或半群）是循环根据

25、定义，判别含幺半群（或半群）是循环含幺半群（循环半群）的关键是计算生成元。含幺半群（循环半群）的关键是计算生成元。如何计算生成元呢？如何计算生成元呢？首先假设生成元存在，然后根据定义得到方程，通首先假设生成元存在，然后根据定义得到方程，通过解这个方程来计算生成元。过解这个方程来计算生成元。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-25252022-1-12022-1-1例例13.2.713.2.7（续）（续）如在本例中，不妨假设如在本例中，不妨假设aNaN是是的生成的生成元，则根据生成元的定义，对任意元，则根据生成元

26、的定义，对任意nNnN，存存在在mNmN，使得，使得n = an = am m = ma = ma让让n = 1n = 1，有，有1 = ma1 = ma，因此，因此a = 1a = 1。这说明，。这说明，如果如果有生成元，则生成元必须为有生成元，则生成元必须为1 1。下面还需验证下面还需验证1 1是生成元。是生成元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-26262022-1-12022-1-1例例13.2.713.2.7（续）（续）解解 由于存在元素由于存在元素1N1N，使得对任意，使得对任意nNnN，都有：，都

27、有：n = (nn = (n 1)+1 = 1+1)+1 = 1+（n n 1 1） = 1+1+1+ = 1+1+1+1 = 1+1 = 1n n，特别对幺元特别对幺元0N0N，有，有0 = 10 = 10 0。所以，所以，“1 1”是生成元。是生成元。因此，该半群一定是循环含幺半群。因此，该半群一定是循环含幺半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-27272022-1-12022-1-1定理定理13.2.113.2.1 循环半群都是可交换半群。循环半群都是可交换半群。分析分析 由于循环半群中的每个元素都可以

28、表示为生由于循环半群中的每个元素都可以表示为生成元的方幂形式，可以使用这种表示形式来证明。成元的方幂形式，可以使用这种表示形式来证明。证明证明 设设aSaS是循环半群是循环半群S, 的生成元。则对任的生成元。则对任意意x, ySx, yS，存在，存在m, nZm, nZ+ +，使得，使得x = ax = am m，y = ay = an n，所以，所以x x y = a y = am m a an n = a = am+nm+n = a = an+mn+m = a = an n a am m = y = y x x，故运算故运算“ ”是可交换的，即是可交换的，即S, 是可交换半群。是可交换半群

29、。推论推论13.2.113.2.1 循环含幺半群都是可交换含幺半群。循环含幺半群都是可交换含幺半群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-28282022-1-12022-1-1例例13.2.8 13.2.8 判断含幺半群判断含幺半群 是否是循环含幺半群？若是，是否是循环含幺半群？若是，请求出其所有的生成元。请求出其所有的生成元。分析分析 6 6 = 0, 1, 2, 3, 4, 5 = 0, 1, 2, 3, 4, 5，共有，共有6 6个元素，个元素，则可以判别每一个元素是否是生成元。则可以判别每一个元素是否是生

30、成元。解解 由于由于6 6 = 0, 1, 2, 3, 4, 5 = 0, 1, 2, 3, 4, 5，0 0是幺元，是幺元，则则0 0肯定不是生成元，对其他元，有：肯定不是生成元，对其他元，有： 、1 1 = 0, 1 = 0, 1 = 1, 1 = 1, 1 = 2, 1 = 2, 1 = 3, 1 = 3, 14 4 = 4, 1= 4, 15 5 = 5 = 5， 所以所以“1 1”是是 的生成元；的生成元；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-29292022-1-12022-1-1例例13.2.813.

31、2.8（续）（续）、2 2 = 0, 2 = 0, 2 = 2, 2 = 2, 2 = 4, 2 = 4, 2 = 0, = 0,， 所以所以“2 2”不是不是 的生成元；的生成元； 、3 3 = 0, 3 = 0, 3 = 3, 3 = 3, 3 = 0, 3 = 0, 3 = 3, = 3,， 所以所以“3 3”不是不是 的生成元；的生成元；、4 4 = 0, 4 = 0, 4 = 4, 4 = 4, 4 = 2, 4 = 2, 4 = 0, = 0,， 所以所以“4 4”不是不是 的生成元；的生成元；、5 5 = 0, 5 = 0, 5 = 5, 5 = 5, 5 = 4, 5 = 4,

32、 5 = 3, 5 = 3, 54 4 = 2, = 2, 5 55 5 = 1 = 1， 所以所以“5 5”是是 的生成元。的生成元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-30302022-1-12022-1-1例例13.2.813.2.8（续）（续）因此，因此，含幺半群含幺半群 有两个生成元有两个生成元“1 1”、“5 5”，则，则 是循环含幺半群。是循环含幺半群。另解另解 不妨设不妨设aa6 6是生成元，则是生成元，则对任意对任意xx6 6，存在存在mNmN，有，有x = ax = am m = ma (mo

33、d 6) = ma (mod 6)，特别地，当特别地，当x = 1x = 1时，有时，有1 = ma (mod 6)1 = ma (mod 6)，即，即存在存在kZkZ，使得，使得ma = 6k + 1ma = 6k + 1，即，即ma + (ma + ( k)6 = 1k)6 = 1。因此，因此，(a, 6) = 1(a, 6) = 1，即，即a a与与6 6的最大共因子为的最大共因子为1 1。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-31312022-1-12022-1-1例例13.2.813.2.8（续）（续）反

34、之反之，对任意，对任意 aa6 6，如果，如果(a, 6) = 1(a, 6) = 1，则，则存在存在kZkZ，使得，使得1 = ma + 6k1 = ma + 6k，因此，对任意因此，对任意xx6 6，有，有x = (xm)a + 6(xk)x = (xm)a + 6(xk)，xmxm，xkZxkZ，根据根据“+ +6 6”的定义，则的定义，则x = ax = axmxm，xmZxmZ，因此，因此，a a是生成元。是生成元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-32322022-1-12022-1-1例例13.2

35、.813.2.8（续）（续）综上所述，综上所述，aa6 6是生成元的是生成元的充分必要条件充分必要条件是是(a, 6) = 1(a, 6) = 1。考虑集合考虑集合6 6中，可得中，可得“1 1”、“5 5”是是 的生成的生成元，则元，则 是循环含幺半群。是循环含幺半群。计算生成元方法：计算生成元方法： 首先假设生成元存在，然后根据定义得到方程，通过解首先假设生成元存在，然后根据定义得到方程，通过解这个方程来计算生成元。这个方程来计算生成元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-33332022-1-12022-1

36、-1推广推广（1 1） , +n是循环含幺半群；是循环含幺半群；（2 2）对任意）对任意aan n, , 若若(a, n) = 1(a, n) = 1，则，则a a是是 的生成元；的生成元；（3 3）当）当n n是素数时，是素数时，n n中除幺元中除幺元“0 0”以外，其他一以外，其他一切元素都是生成元。切元素都是生成元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-34342022-1-12022-1-1定理与推论定理与推论定理定理13.2.213.2.2 在每个有限循环半群中，至少有一个在每个有限循环半群中，至少有一个

37、幂等元存在。幂等元存在。 推论推论13.2.213.2.2 设设S, 为一个有限半群，则为一个有限半群，则S, 中至少存在一个幂等元。中至少存在一个幂等元。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-35352022-1-12022-1-113.3 13.3 群及其性质群及其性质定义定义13.3.113.3.1 设设G, 为二元代数系统，满足如下性为二元代数系统，满足如下性质：质：（1 1）“ ”在在G G中满足结合律，即中满足结合律，即对任意对任意a,b,cGa,b,cG，有，有(a(a b)b) c = ac =

38、a (b(b c)c)；（2 2）G G中存在关于中存在关于“ ”的幺元的幺元e e，即，即存在存在eGeG，使得，使得对任意对任意aGaG，e e a = aa = a e = ae = a；（3 3）G G中每个元素中每个元素a a都有逆元都有逆元a a 1 1，即，即对任意对任意aGaG，都，都存在存在a a 1 1GG，a a a a 1 1 = a = a 1 1 a = ea = e。则称二元代数系统则称二元代数系统G, 为为群群，简称，简称G G为群为群。n概括：群是满足概括：群是满足结合律、有幺元，每个元有逆结合律、有幺元，每个元有逆元元的二元的二元代数系统代数系统电子科技大学

39、离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-36362022-1-12022-1-1定义定义13.3.213.3.2在群在群G, 中，中，（1 1）若运算）若运算“ ”满足交换律，即满足交换律，即对任意对任意a,bGa,bG，都有都有a a b = bb = b a a，则称则称G, 为为可换群可换群或或阿贝尔阿贝尔(Abel)(Abel)群群；（2 2）集合）集合G G的基数称为群的基数称为群G G的阶的阶(Order)(Order)，记为，记为|G|G|。若群若群G, 的阶有限，则称之为的阶有限，则称之为有限群有限群，否则称为，

40、否则称为无限群无限群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-37372022-1-12022-1-1例例13.3.1 13.3.1 证明证明 是群，其中是群，其中n n是正整数。是正整数。分析分析 需要证明需要证明4 4点：封闭性；结合律；幺元存在；点：封闭性；结合律；幺元存在；逆元存在。逆元存在。证明证明 （1 1）封闭性封闭性： 对任意对任意x, yx, yn n，令，令k = x + y (mod n)k = x + y (mod n)，则，则0k0kn-1n-1，即，即kkn n，所以封闭性成立。所以封闭性

41、成立。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-38382022-1-12022-1-1例例13.3.113.3.1（续）（续）（2 2）结合律结合律：对任意对任意x, y, zx, y, zn n，有，有(x +(x +n n y) +y) +n n z = x + y + z (mod n) z = x + y + z (mod n) = x + = x +n n (y +(y +n n z), z),所以结合律成立。所以结合律成立。（3 3）幺元幺元：对任意对任意xxn n，显然有，显然有 0 +0 +n n x

42、 = x + x = x +n n 0 0，因此，因此，0 0是幺元。是幺元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-39392022-1-12022-1-1例例13.3.113.3.1（续）（续）（4 4）逆元存在逆元存在：对任意对任意xxn n，如果，如果x = 0 x = 0，显然，显然0 0 1 1 = 0 = 0，如果，如果x0 x0，则有，则有n n - - x xn n，显然显然x +x +n n (n (n- -x) = (nx) = (n- -x) +x) +n n x = 0 x = 0，所以所以

43、x x 1 1 = (n = (n x)x)，因此，因此，对任意对任意xxn n，x x有逆元。有逆元。综上，综上， 是群。是群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-40402022-1-12022-1-1例例13.3.2 13.3.2 设设X X是对任意集合，是对任意集合，S = fS = f：X XX | fX | f是双射函数是双射函数 ，运算运算“ ”是函数的复合运算，证明是函数的复合运算，证明S, 是群。是群。证明证明 （1 1）封闭性封闭性：对任意对任意f, gS, f, gf, gS, f, g是双

44、是双射，则射，则f f g g也是双射，也是双射，即即f f gSgS。故封闭性成立。故封闭性成立。（2 2）结合律结合律：由于函数的复合运算：由于函数的复合运算“ ”满足结满足结合律，合律，因此，在集合因此，在集合S S也满足结合律。也满足结合律。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-41412022-1-12022-1-1例例13.3.213.3.2（续）（续）（3 3）幺元存在幺元存在：恒等映射：恒等映射I IX XGG，且，且对任意对任意fSfS，有，有I IX X f = f f = f I IX X =

45、 f = f，因此，恒等映射因此，恒等映射I IX X是幺元。是幺元。（4 4）逆元存在逆元存在：对任意对任意fS, ffS, f是双射，则是双射，则f f 1 1SS，且有且有f f 1 1 f = f f = f f f 1 1 = I = IX X，因此，因此，f f 1 1就是就是f f关于关于“ ”的逆元。的逆元。由（由（1 1）、（）、（2 2）、（）、（3 3）和（）和（4 4）可知，）可知，S, 是群。是群。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-42422022-1-12022-1-1说明说明S,

46、被称为被称为变换群变换群，如果，如果X X是有限集合，设是有限集合，设|X| |X| = n= n，此时称，此时称S, 为为n n阶置换群阶置换群。变换群在几何。变换群在几何学中有十分广泛的应用。学中有十分广泛的应用。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-43432022-1-12022-1-1定理定理13.3.113.3.1在群在群G, 中，有：中，有：（1 1）群）群G G中每个元素都是可消去的，即运算满足消中每个元素都是可消去的，即运算满足消去律；去律；（2 2）群）群G G中除幺元中除幺元e e外无其他幂等

47、元；外无其他幂等元；（3 3）阶大于）阶大于1 1的群的群G G不可能有零元；不可能有零元；（4 4）对任意对任意a, bGa, bG，都有，都有(a(a b)b) 1 1 = b = b 1 1 a a 1 1；（5 5）群）群G, 的的运算表中对任意一行的的运算表中对任意一行( (列列) )都没都没有两个相同的元素。有两个相同的元素。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-44442022-1-12022-1-1定理定理13.3.113.3.1（续）（续）分析分析 由于可逆元就是可消去元，因此（由于可逆元就是可消

48、去元，因此（1 1）显然）显然可证。可证。（2 2）和（）和（3 3）分别是证明唯一性和存在性问题，通）分别是证明唯一性和存在性问题，通常采用反证法证明。常采用反证法证明。（4 4）显然。）显然。（5 5）采用反证法证明。）采用反证法证明。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-45452022-1-12022-1-1定理定理13.3.113.3.1（续）（续）证明证明 （1 1）由于可逆元就是可消去元，而群）由于可逆元就是可消去元，而群G G中每中每个元素都是可逆元，则个元素都是可逆元，则G G中的任何元素都是可消

49、去中的任何元素都是可消去的，即运算满足消去律。的，即运算满足消去律。（2 2）对幺元）对幺元e e，由于，由于e e e = ee = e，所以，所以e e是幂等元。现是幂等元。现假设假设a a是群是群G G中的幂等元，即中的幂等元，即a a a = aa = a，则则a a a = aa = a e e，使用消去律，则有，使用消去律，则有a = ea = e。因此，幺元因此，幺元e e是是G G的唯一幂等元。的唯一幂等元。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-46462022-1-12022-1-1定理定理13.

50、3.113.3.1（续）（续）（3 3）假设群）假设群G G的阶大于的阶大于1 1且有零元且有零元 ，则，则 = = ，即即 是幂等元，因此由（是幂等元，因此由（2 2）有）有 = e= e，由于由于|G|1|G|1，则，则存在存在xGxG，xx ，由，由 是零元，有是零元，有x x = = ，又又 = e= e是幺元，则有是幺元，则有x x = x = x = x = x，则，则， = x= x，这与，这与xx 矛盾。因此，矛盾。因此，G G中无零元。中无零元。注意注意：如果：如果|G| = 1|G| = 1，则有，则有G = eG = e，此时，此时e e既是幺既是幺元又是零元。元又是零元

51、。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-47472022-1-12022-1-1定理定理13.3.113.3.1（续）（续）（4 4）由于群）由于群G G中的运算满足结合律，且每个元素都中的运算满足结合律，且每个元素都有逆元，有推论有逆元，有推论12.3.112.3.1知，结论成立。知，结论成立。（5 5）假设群）假设群G G的运算表中某一行的运算表中某一行( (列列) )有两个相同的有两个相同的元素，设为元素，设为a a，并设它们所在的行表头元素为，并设它们所在的行表头元素为b b，列，列表头元素分别为表头元素分

52、别为c c1 1, c, c2 2，这时显然有，这时显然有c c1 1cc2 2。而。而a = ba = b c c1 1 = b = b c c2 2，由消去律得由消去律得c c1 1 = c = c2 2，矛盾。矛盾。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-48482022-1-12022-1-1群中元素的周期群中元素的周期设设G G，* *是一个群，对任意是一个群，对任意a a G G，可定义：可定义： a a =e=e，a a =a=a，a a =a=a a,a, a an n= =a an-n- a=aa=

53、a a an-n- =a=a a a a a； a a- -=a a- - ，a a- -= (a (a- -),), a a-n-n= =(a(a- -) )n n= = a a- - a a- - a a- - 。由幂的定义知：由幂的定义知： a amm a an n=a=am+nm+n=a=an+mn+m=a=an n a amm； (a(amm) )n n=a=amnmn。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-49492022-1-12022-1-1元素的周期（续）元素的周期（续）对群对群G, 中的元中的元

54、a a，由幂方可得到如下的一个序，由幂方可得到如下的一个序列：列：, a, a n n，, a, a 2 2，a a 1 1，a a0 0，a a1 1，a a2 2，, a, an n，这个序列有周期吗？如果有周期，其最小正周期为这个序列有周期吗？如果有周期，其最小正周期为多少？多少？分析分析 在上述序列中，如果存在整数在上述序列中，如果存在整数p p和和q q，其中，其中pqpq，使得，使得a ap p = a = aq q，则由消去律有，则由消去律有a aq q p p = e = e，电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程

55、157-157-50502022-1-12022-1-1元素的周期（续）元素的周期（续）此时此时p p q q就是序列的一个周期，因为对任意的整数就是序列的一个周期，因为对任意的整数m m，有，有a am+(pm+(p q)q) = a = am m e = ae = am m，即，对任意的正整数即，对任意的正整数n n，如果，如果a an n = e = e，则，则n n是序列的是序列的周期。周期。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-51512022-1-12022-1-1元素的周期（续）元素的周期（续）反之，

56、如果反之，如果n n是序列的周期，肯定有是序列的周期，肯定有a an n = e = e。为什么呢？为什么呢？因为由周期的定义可知，如果因为由周期的定义可知，如果n n是周期，则是周期，则对任意的整数对任意的整数m m，由，由a am+nm+n = a = am m，即，即a am m a an n = a = am m，由消去律，可得由消去律，可得a an n = e = e。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-52522022-1-12022-1-1定义定义13.3.3 13.3.3 设设e e是群是群G,

57、的幺元，的幺元，aGaG，（1 1）使得）使得a an n = e = e成立的成立的最小正整数最小正整数n n称为称为a a的的周期周期或为元素或为元素a a的的阶阶，记为，记为|a|a|；（2 2）若不存在这样的正整数）若不存在这样的正整数n n，使得，使得a an n = e = e，则称，则称a a的的周期无限周期无限，即对任意，即对任意nZnZ + + ，都有，都有a an n e e。显然，群显然，群G, 中幺元中幺元e e的周期为的周期为1 1 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-53532022-

58、1-12022-1-1定理定理13.3.313.3.3设设a a是群是群G, 中的元素，则：中的元素，则：（1 1）如果）如果a a的周期为的周期为n n，则对任意的整数，则对任意的整数i i，有，有a ai i a a1 1, a, a2 2, , , a, an n ，且对任意的且对任意的p, q1, 2, p, q1, 2, ., n, p ., n, p q q，有，有a ap paaq q；（2 2）如果）如果a a的周期无限，则对任意的整数的周期无限，则对任意的整数p,q, p,q, p p q q，有，有a ap paaq q；（3 3）a a和它的逆元和它的逆元a a 1 1的

59、周期相同。的周期相同。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-54542022-1-12022-1-1例例13.3.3 13.3.3 计算实数加群计算实数加群中元素的周期。中元素的周期。分析分析 在在中幺元为中幺元为“0 0”，所以有，所以有0 0 = 0 = 0，而对任意而对任意aRaR，且，且a0a0，及，及对任意对任意nZnZ + + 有有a an n = a = an n + a = a + a + a = a + an n = a + a + = a + a + + a + a = na0 = na0 ，因

60、此，此时仅有因此，此时仅有“0 0”有周期有周期“1 1”，而其余元素的，而其余元素的周期无限。周期无限。结论结论 在实数加群在实数加群中，中，0 0的周期为的周期为1 1，而其余，而其余实数的周期无限。实数的周期无限。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品国家精品课程课程 双语示范课程双语示范课程157-157-55552022-1-12022-1-1定理定理13.3.313.3.3设设G, 是一个群，是一个群，对任意对任意aGaG，若，若a a的周期为的周期为m m，则则a an n = e = e当且仅当当且仅当m | nm | n。分析分析 a a的周期为的周期为