离散数学第151156陈瑜.ppt

《离散数学第151156陈瑜.ppt》由会员分享，可在线阅读，更多相关《离散数学第151156陈瑜.ppt（226页珍藏版）》请在三一办公上搜索。

1、陈瑜,Email：yu2023/10/21,离散数学,计算机学院,2023/10/21,计算机科学与工程学院,2,第15章：半群与群15.1 半群,2023/10/21,计算机科学与工程学院,3,群是一种特殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。,2023/10/21,计算机科学与工程学院,4,群是一种特

2、殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。,2023/10/21,计算机科学与工程学院,5,例：满足封闭、可结合、有幺元0的条件，因而是含幺半群。另外，它还满足可换性，每个元xR都有加法逆元-x，因此，也是一个可换群。满足封闭、可结合、有幺元1，因此是含幺半群。注意，因为0无乘法逆元，所以只能是含幺半群。,

3、2023/10/21,计算机科学与工程学院,6,例 设Mm,n表示全休m行n列矩阵构成的集合，+是矩阵加法，那么满足封闭、可结合的条件，元素全为0的m行n列矩阵是幺元，因此是含幺半群。此外，Mm,n中每个矩阵Am,n都有加法逆矩阵-Am,n，因而还满足逆元条件。,2023/10/21,计算机科学与工程学院,7,例 设F是由定义在非空集合S上的全体函数构成的集合，即F=f:SS。对于函数的复合运算“”，满足封闭性和可结合性，所以是半群。此外，定义在S上的恒等函数Is是的幺元，所以又是含幺半群。,2023/10/21,计算机科学与工程学院,8,例 设是非空有限字母表，*是由定义在上的全体有限长字母

4、串构成的集合，或叫做上全体字的集合。在*上定义运算为字的连接“”，则满足封闭和可结合的条件，并且空字 是系统的幺元，所以是一个含幺半群。半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。,2023/10/21,计算机科学与工程学院,9,例 设是非空有限字母表，*是由定义在上的全体有限长字母串构成的集合，或叫做上全体字的集合。在*上定义运算为字的连接“”，则满足封闭和可结合的条件，并且空字 是系统的幺元，所以是一个含幺半群。半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的

5、形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。,2023/10/21,计算机科学与工程学院,10,例 设一个简单的液晶显示电子表仅有显示时、分的两个功能，有0、1两个按键。按1键时由正常状态转入调分状态，此时按0键m次可以调增分数m；再按1键则转入调时状态，此时按0键n次，则时数增加n；最后再按1键回复到正常状态。这一调节过程如图(b)所示。,(a),(b),2023/10/21,计算机科学与工程学院,11,上面的调分和调时过程可表示为:,或由符号1和0组成的形如10m10n1的字符串集，即字母表=0，1上的一个语言L=10m10n1|m，n0。这种字

6、母串可以被电子表中的微处理器(可以看成是一个小小的计算机)识别并执行，其动作原理就是图15-1.1(b)所示的状态图，称为一个有限自动机，它反映了电子表依令而行的规则。语言L被相应地称为这个自动机所识别的语言。,2023/10/21,计算机科学与工程学院,12,幂,设是一个半群,由于*满足结合律，可定义幂运算，即对xS，可定义：x=x，x=x*x，x=x*x=x*x=x*x*x，xn=xn-1*x=x*xn-1=x*x*x*x。如果有单位元e，可以定义：x0=e幂运算有如下的公式：（见下页）,2023/10/21,计算机科学与工程学院,13,定理15-1.1 设是半群，aS，m和n是正整数，则

7、：am*an=am+n；(am)n=amn。当是含幺半群时，上述结论对任意非负整数m和n都成立。证明：设m是一个固定的正整数，对n进行归纳。对于：当n=1时，由幂的定义可知结论成立；设结论对n=k时成立，则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性）=(am+k)*a（归纳假设）=am+(k+1)由归纳法可知，结论成立。,2023/10/21,计算机科学与工程学院,14,定理15-1.1 设是半群，aS，m和n是正整数，则：am*an=am+n；(am)n=amn。当是含幺半群时，上述结论对任意非负整数m和n都成立。证明：设m是一个固定的正整数，对n进行归

8、纳。对于：当n=1时，由幂的定义可知结论成立；设结论对n=k时成立，则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性）=(am+k)*a（归纳假设）=am+(k+1)由归纳法可知，结论成立。,2023/10/21,计算机科学与工程学院,15,定理15-1.1 设是半群，aS，m和n是正整数，则：am*an=am+n；(am)n=amn。当是含幺半群时，上述结论对任意非负整数m和n都成立。证明：设m是一个固定的正整数，对n进行归纳。对于：当n=1时，由幂的定义可知结论成立；设结论对n=k时成立，则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)

9、*a(可结合性）=(am+k)*a（归纳假设）=am+(k+1)由归纳法可知，结论成立。,对于可以类似的进行归纳证明。,2023/10/21,计算机科学与工程学院,16,注意：当运算为加法“+”时，上述定理应写成：ma+na=(m+n)a n(ma)=(mn)a,2023/10/21,计算机科学与工程学院,17,定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji，由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1

10、，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。,注意此处的a2的正确含义！a*a=a2,不是数学中的乘法！,2023/10/21,计算机科学与工程学院,18,定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji。由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i

11、)，则得到幂等元。,2023/10/21,计算机科学与工程学院,19,定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji。由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。,2023/10/21,计算机科学与工程学院,20,定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材

12、p277）证明：因为是半群，S是有限集，对bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji。由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。,2023/10/21,计算机科学与工程学院,21,定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji，由bi=bj-i*bi，则对 ti都得到b

13、t=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。,注意，若S不是有限集，则不一定有幂等元。例如，正整数集关于加法运算是一个半群，但是不存在幂等元。含幺半群至少含有一个幂等元，那就是幺元。一个半群甚至含幺半群也可以含有多个幂等元。不难验证是以S为幺元的含幺半群。由于集合交运算是幂等的，所以中每个元都是幂等元。,2023/10/21,计算机科学与工程学院,22,子半群,定义15-1.1如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群；如果是含幺半群，TS，eT，且

14、T对运算*是封闭的，则称是含幺半群的子含幺半群。例：半群的子代数，都是的子半群。,2023/10/21,计算机科学与工程学院,23,子半群,定义15-1.1如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群；如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。例：半群的子代数，都是的子半群。,2023/10/21,计算机科学与工程学院,24,子半群,定义15-1.1如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群；如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。例：半群的子代数，都是的子半群。,2

15、023/10/21,计算机科学与工程学院,25,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。证明：(1)显然，MS；(2)是含幺半群，所以幺元e存在，又e*ee，则e是一个等幂元，即有eM，所以M是非空的；(3)eM；(4)对任意a，bM，有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b，即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知：是的一个子含幺半群。,2023/10/21,计算机科学与工程学院,26,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。证明：

16、(1)显然，MS；(2)是含幺半群，所以幺元e存在，又e*ee，则e是一个等幂元，即有eM，所以M是非空的；(3)eM；(4)对任意a，bM，有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b，即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知：是的一个子含幺半群。,2023/10/21,计算机科学与工程学院,27,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。证明：(1)显然，MS；(2)是含幺半群，所以幺元e存在，又e*ee，则e是一个等幂元，即有eM，所以M是非空的；(3)eM；(4)对任意a，

17、bM，有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b，即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知：是的一个子含幺半群。,2023/10/21,计算机科学与工程学院,28,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。证明：(1)显然，MS；(2)是含幺半群，所以幺元e存在，又e*ee，则e是一个等幂元，即有eM，所以M是非空的；(3)eM；(4)对任意a，bM，有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b，即运算“*”关于集合M是封闭的运算。由(

18、1)、(2)、(3)、(4)知：是的一个子含幺半群。,2023/10/21,计算机科学与工程学院,29,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。证明：(1)显然，MS；(2)是含幺半群，所以幺元e存在，又e*ee，则e是一个等幂元，即有eM，所以M是非空的；(3)eM；(4)对任意a，bM，有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b，即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知：是的一个子含幺半群。,2023/10/21,计算机科学与工程学院,30,习题,P278 2,2023/1

19、0/21,计算机科学与工程学院,31,15.2 群和子群,2023/10/21,计算机科学与工程学院,32,主要内容,一个非常重要的代数系统群。主要从以下几个方面来介绍：群的概念和基本性质。群的子群和性质。群中元素的周期和性质。特殊群及其性质，如交换群（Abel群）、循环群。陪集和拉格郎日定理。,2023/10/21,计算机科学与工程学院,33,在14.2中已经为群下了定义，把群看成是在含幺半群的基础上加上每元有逆元的条件，其核心内容可用“闭、结、幺、逆”四个字予以概括。下面是一些典型的群的例子。,2023/10/21,计算机科学与工程学院,34,例：我们已经知道是含幺半群，由于每个整数a都有

20、加法逆元-a，所以是群，一般叫做整数加群。同理，是实数加群，是有理数加群。对于数的乘法，是含幺半群而不是群，因为整数一般无Z中的乘法逆元。是实数乘群，它的幺元是1，每元的乘法逆元为1/a。,2023/10/21,计算机科学与工程学院,35,例：设Zk表示整数集Z上的模k剩余类集合，即:Zk=0,1,2,k-1。在Zk上定义运算 和 如下：那么，是群。这是因为封闭性和可结合性是明显成立的，0是幺元，每元i的逆元是k-i。群 习惯上又称为剩余类加群。,2023/10/21,计算机科学与工程学院,36,例 设n个元素的集合A上的全体置换构成集合Sn。由第6章中关于置换的讨论，Sn中两个置换的复合仍然

21、是A上的一个置换，因而运算是封闭的；其次，由于函数的复合是可结合的，因而置换的复合也是可结合的；在Sn中存在幺置换=(1)，使对任何Sn中的置换 均有，因而=(1)是幺元；把每个元素的x变成y的置换，其逆置换则把元素y变成x，因而每个置换都有逆。由此可知，构成群，这个群一般称为n次对称群，是一类重要的群。群尽管是用“闭、结、幺、逆”四个条件来定义的，但是它还可以用别的形式等价地定义。,2023/10/21,计算机科学与工程学院,37,例 设n个元素的集合A上的全体置换构成集合Sn。由第6章中关于置换的讨论，Sn中两个置换的复合仍然是A上的一个置换，因而运算是封闭的；其次，由于函数的复合是可结合

22、的，因而置换的复合也是可结合的；在Sn中存在幺置换=(1)，使对任何Sn中的置换 均有，因而=(1)是幺元；把每个元素的x变成y的置换，其逆置换则把元素y变成x，因而每个置换都有逆。由此可知，构成群，这个群一般称为n次对称群，是一类重要的群。群尽管是用“闭、结、幺、逆”四个条件来定义的，但是它还可以用别的形式等价地定义。,2023/10/21,计算机科学与工程学院,38,群,定理15-2.1 如果是半群，并且对a，bG，都存在x，yG 使x*a=b，a*y=b，则是群。群中元素的数目称为群的阶。证明：设 aG，方程 x*a=a 的解为e1，对tG，方程 a*y=t 有解y0，e1*t=e1*（

23、a*y0）=（e1*a）*y0=a*y0=t 即对tG，必有e1*t=t，e1是G中的左幺元。同样可以证明G中有右幺元e2，所以G中有幺元e。同理，对bG，方程x*b=e有解x0，这个x0是b的左逆元，方程b*y=e的解是b的右逆元，从而b有逆元。所以，是群。,2023/10/21,计算机科学与工程学院,39,群,定理15-2.1 如果是半群，并且对a，bG，都存在x，yG 使x*a=b，a*y=b，则是群。群中元素的数目称为群的阶。证明：设 aG，方程 x*a=a 的解为e1，对tG，方程 a*y=t 有解y0，e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t 即对tG，必有e

24、1*t=t，e1是G中的左幺元。同样可以证明G中有右幺元e2，所以G中有幺元e。同理，对bG，方程x*b=e有解x0，这个x0是b的左逆元，方程b*y=e的解是b的右逆元，从而b有逆元。所以，是群。,2023/10/21,计算机科学与工程学院,40,群,定理15-2.1 如果是半群，并且对a，bG，都存在x，yG 使x*a=b，a*y=b，则是群。群中元素的数目称为群的阶。证明：设 aG，方程 x*a=a 的解为e1，对tG，方程 a*y=t 有解y0，e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t 即对tG，必有e1*t=t，e1是G中的左幺元。同样可以证明G中有右幺元e2，

25、所以G中有幺元e。同理，对bG，方程x*b=e有解x0，这个x0是b的左逆元，方程b*y=e的解是b的右逆元，从而b有逆元。所以，是群。,2023/10/21,计算机科学与工程学院,41,群,定理15-2.1 如果是半群，并且对a，bG，都存在x，yG 使x*a=b，a*y=b，则是群。群中元素的数目称为群的阶。证明：设 aG，方程 x*a=a 的解为e1，对tG，方程 a*y=t 有解y0，e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t 即对tG，必有e1*t=t，e1是G中的左幺元。同样可以证明G中有右幺元e2，所以G中有幺元e。同理，对bG，方程x*b=e有解x0，这个x

26、0是b的左逆元，方程b*y=e的解是b的右逆元，从而b有逆元。所以，是群。,2023/10/21,计算机科学与工程学院,42,群,定理15-2.1 如果是半群，并且对a，bG，都存在x，yG 使x*a=b，a*y=b，则是群。群中元素的数目称为群的阶。证明：设 aG，方程 x*a=a 的解为e1，对tG，方程 a*y=t 有解y0，e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t 即对tG，必有e1*t=t，e1是G中的左幺元。同样可以证明G中有右幺元e2，所以G中有幺元e。同理，对bG，方程x*b=e有解x0，这个x0是b的左逆元，方程b*y=e的解是b的右逆元，从而b有逆元。

27、所以，是群。,这个定理说明，在群的定义中幺元及逆元的条件可用方程有解来代替。另外，群定义中的幺元条件可以用存在左幺元(或右幺元)的条件代替，逆元的条件可以用左逆元(或右逆元)代替。,2023/10/21,计算机科学与工程学院,43,定理15-2.2群G中每个元素都是可消去的，即运算满足消去律；（即如果a*b=a*c，则必有b=c）群G中除幺元e外无其它幂等元；群G的运算表中任意一行(列)都没有两个相同的元素（重复元素）；,2023/10/21,计算机科学与工程学院,44,定理15-2.2群G中每个元素都是可消去的，即运算满足消去律；（即如果a*b=a*c，则必有b=c）群G中除幺元e外无其它幂

28、等元；群G的运算表中任意一行(列)都没有两个相同的元素（重复元素）；,证明：由于群G中每个元素都有逆元a-1，由a*b=a*c a-1*a*b=a-1*a*c，即b=c,2023/10/21,计算机科学与工程学院,45,定理15-2.2群G中每个元素都是可消去的，即运算满足消去律；（即如果a*b=a*c，则必有b=c）群G中除幺元e外无其它幂等元；群G的运算表中任意一行(列)都没有两个相同的元素（重复元素）；,2023/10/21,计算机科学与工程学院,46,定理15-2.2群G中每个元素都是可消去的，即运算满足消去律；（即如果a*b=a*c，则必有b=c）群G中除幺元e外无其它幂等元；群G的

29、运算表中任意一行(列)都没有两个相同的元素（重复元素）；,证明：（反证法）假设a是群G中非幺元的幂等元，即a*aa，且ae。因此a*aa*e，由（1）知ae，矛盾。,2023/10/21,计算机科学与工程学院,47,定理15-2.2群G中每个元素都是可消去的，即运算满足消去律；（即如果a*b=a*c，则必有b=c）群G中除幺元e外无其它幂等元；群G的运算表中任意一行(列)都没有两个相同的元素（重复元素）；,2023/10/21,计算机科学与工程学院,48,定理15-2.2群G中每个元素都是可消去的，即运算满足消去律；（即如果a*b=a*c，则必有b=c）群G中除幺元e外无其它幂等元；群G的运算

30、表中任意一行(列)都没有两个相同的元素（重复元素）；,证明：（反证法）假设群G的运算表中某一行(列)有两个相同的元素，设为a，并设它们所在的行表头元素为b，列表头元素分别为c1,c2，这时显然有c1c2。而abc1bc2，由(1)得c1c2，矛盾。,2023/10/21,计算机科学与工程学院,49,补充,例：构造一个3阶群。解：设e是幺元，G=e,a,b 则可构造的3阶群如下：,2023/10/21,计算机科学与工程学院,50,定理15-2.3 设是群，aG。构造映射，使得对任意xG，令，则对于函数的复合运算“”，是群。定理的证明留与读者练习,这个定理说明：可以由一个已知的群来构造出一个新的群

31、。,2023/10/21,计算机科学与工程学院,51,例：设X是任意集合，S=f:XX|f是双射函数，即S是X上的所有双射函数的集合，运算“。”是函数的复合运算，证明是群。证明：（1）封闭性：f,gS，f、g是双射，则f。g也是双射，因此f。g S，故封闭性成立。（2）结合律：由函数的运算“。”满足结合律，因此在S中也满足结合律。,2023/10/21,计算机科学与工程学院,52,例：设X是任意集合，S=f:XX|f是双射函数，即S是X上的所有双射函数的集合，运算“。”是函数的复合运算，证明是群。证明：（1）封闭性：f,gS，f、g是双射，则f。g也是双射，因此f。g S，故封闭性成立。（2）

32、结合律：由函数的运算“。”满足结合律，因此在S中也满足结合律。,2023/10/21,计算机科学与工程学院,53,例：设X是任意集合，S=f:XX|f是双射函数，即S是X上的所有双射函数的集合，运算“。”是函数的复合运算，证明是群。证明：（1）封闭性：f,gS，f、g是双射，则f。g也是双射，因此f。g S，故封闭性成立。（2）结合律：由函数的运算“。”满足结合律，因此在S中也满足结合律。,2023/10/21,计算机科学与工程学院,54,例：设X是任意集合，S=f:XX|f是双射函数，即S是X上的所有双射函数的集合，运算“。”是函数的复合运算，证明是群。证明：（续）（3）幺元：恒等映射IX

33、S,且fS，有：IX。f=f。IX=f，因此IX是的幺元。（4）f,gS是双射，则f的逆函数f-1存在，f-1也 是双射，即f-1S，且有：f-1。f=f。f-1=IX，因此，f的逆函数f-1就是f关于“。”的逆元，即S的任意元素都有逆元。综合（1）（2）（3）（4）知是群。,2023/10/21,计算机科学与工程学院,55,例：设X是任意集合，S=f:XX|f是双射函数，即S是X上的所有双射函数的集合，运算“。”是函数的复合运算，证明是群。证明：（续）（3）幺元：恒等映射IX S,且fS，有：IX。f=f。IX=f，因此IX是的幺元。（4）f,gS是双射，则f的逆函数f-1存在，f-1也 是

34、双射，即f-1S，且有：f-1。f=f。f-1=IX，因此，f的逆函数f-1就是f关于“。”的逆元，即S的任意元素都有逆元。综合（1）（2）（3）（4）知是群。,2023/10/21,计算机科学与工程学院,56,课外练习：设A=R-0，1，在A上定义6个映射如下：对于任意xA有：令G=f1,f2,f3,f4,f5,f6。试证明G关于函数的复合运算“。”构成群。,2023/10/21,计算机科学与工程学院,57,子群,定义15-2.1设是一个群，S是G的一个非空子集，若S也是群，则称是的一个子群。一般来说，对任意的群，都有两个子群，我们称此两个子群为该群的平凡子群,而若有子群,且Se和SG，则称

35、为的真子群。另外，由群中的一个元素也可生成一个子群。定义为：a-k=（ak）-1。,2023/10/21,计算机科学与工程学院,58,子群,定义15-2.1设是一个群，S是G的一个非空子集，若S也是群，则称是的一个子群。一般来说，对任意的群，都有两个子群，我们称此两个子群为该群的平凡子群,而若有子群,且Se和SG，则称为的真子群。另外，由群中的一个元素也可生成一个子群。为此，需要将群中元素的幂扩充到负指数的形式，即定义为：a-k=（ak）-1。,2023/10/21,计算机科学与工程学院,59,子群,定义15-2.1设是一个群，S是G的一个非空子集，若S也是群，则称是的一个子群。一般来说，对任

36、意的群，都有两个子群，我们称此两个子群为该群的平凡子群,而若有子群,且Se和SG，则称为的真子群。另外，由群中的一个元素也可生成一个子群。为此，需要将群中元素的幂扩充到负指数的形式，即定义为：a-k=（ak）-1。,2023/10/21,计算机科学与工程学院,60,定理15-2.4 设是一个群，对任意的aG，令 San|nZ，Z是整数，则是的子群。证明：因为aS，所以显然S是G的非空子集。对任意的an，amS，则an*aman+m，由n,mZ，有n+mZ，所以an+mS，即运算是封闭的；由S是G的子集可得结合律也成立；由于 e=a0S，所以S中有幺元；又an S有逆元a-n使an*a-n=e

37、综上所述，是的子群。,2023/10/21,计算机科学与工程学院,61,定理15-2.4 设是一个群，对任意的aG，令 San|nZ，Z是整数，则是的子群。证明：因为aS，所以显然S是G的非空子集。对任意的an，amS，则an*aman+m，由n,mZ，有n+mZ，所以an+mS，即运算是封闭的；由S是G的子集可得结合律也成立；由于 e=a0S，所以S中有幺元；又an S有逆元a-n使an*a-n=e 综上所述，是的子群。,2023/10/21,计算机科学与工程学院,62,定理15-2.4 设是一个群，对任意的aG，令 San|nZ，Z是整数，则是的子群。证明：因为aS，所以显然S是G的非空子

38、集。对任意的an，amS，则an*aman+m，由n,mZ，有n+mZ，所以an+mS，即运算是封闭的；由S是G的子集可得结合律也成立；由于 e=a0S，所以S中有幺元；又an S有逆元a-n使an*a-n=e 综上所述，是的子群。,2023/10/21,计算机科学与工程学院,63,定理15-2.4 设是一个群，对任意的aG，令 San|nZ，Z是整数，则是的子群。证明：因为aS，所以显然S是G的非空子集。对任意的an，amS，则an*aman+m，由n,mZ，有n+mZ，所以an+mS，即运算是封闭的；由S是G的子集可得结合律也成立；由于 e=a0S，所以S中有幺元；又an S有逆元a-n使

39、an*a-n=e 综上所述，是的子群。,2023/10/21,计算机科学与工程学院,64,定理15-2.4 设是一个群，对任意的aG，令 San|nZ，Z是整数，则是的子群。证明：因为aS，所以显然S是G的非空子集。对任意的an，amS，则an*aman+m，由n,mZ，有n+mZ，所以an+mS，即运算是封闭的；由S是G的子集可得结合律也成立；由于 e=a0S，所以S中有幺元；又an S有逆元a-n使an*a-n=e 综上所述，是的子群。,2023/10/21,计算机科学与工程学院,65,特别把由群的一个元素a生成的子群记为(a)。例如在中，由元素2生成的子群(2)是由全体偶数关于加法构成的

40、群，而由元素1生成的子群正好是Z本身。,2023/10/21,计算机科学与工程学院,66,定理15-2.5 设是一个群,是的子群,则:1）子群的幺元eS也是群的幺元eG；2）对aS，a在S中的逆元aS-1就是a在G中的逆元aG-1。证明：1)对aS，由于eS是S的幺元，所以有：eS*aa*eSa 又SG,所以aG,由eG是G的幺元，所以有：eG*aa*eGa 由、有：eS*aa*eSaeG*aa*eG，由于G满足消去律，所以有：eSeG。2)对aS，由于SG，所以aG，即a在S中的逆元就是a在G中的逆元。,2023/10/21,计算机科学与工程学院,67,定理15-2.5 设是一个群,是的子群

41、,则:1）子群的幺元eS也是群的幺元eG；2）对aS，a在S中的逆元aS-1就是a在G中的逆元aG-1。证明：1)对aS，由于eS是S的幺元，所以有：eS*aa*eSa 又SG,所以aG,由eG是G的幺元，所以有：eG*aa*eGa 由、有：eS*aa*eSaeG*aa*eG，由于G满足消去律，所以有：eSeG。2)对aS，由于SG，所以aG，即a在S中的逆元就是a在G中的逆元。,2023/10/21,计算机科学与工程学院,68,定理15-2.5 设是一个群,是的子群,则:1）子群的幺元eS也是群的幺元eG；2）对aS，a在S中的逆元aS-1就是a在G中的逆元aG-1。证明：1)对aS，由于e

42、S是S的幺元，所以有：eS*aa*eSa 又SG,所以aG,由eG是G的幺元，所以有：eG*aa*eGa 由、有：eS*aa*eSaeG*aa*eG，由于G满足消去律，所以有：eSeG。2)对aS，由于SG，所以aG，即a在S中的逆元就是a在G中的逆元。,2023/10/21,计算机科学与工程学院,69,定理15-2.5 设是一个群,是的子群,则:1）子群的幺元eS也是群的幺元eG；2）对aS，a在S中的逆元aS-1就是a在G中的逆元aG-1。证明：1)对aS，由于eS是S的幺元，所以有：eS*aa*eSa 又SG,所以aG,由eG是G的幺元，所以有：eG*aa*eGa 由、有：eS*aa*e

43、SaeG*aa*eG，由于G满足消去律，所以有：eSeG。2)对aS，由于SG，所以aG，即a在S中的逆元就是a在G中的逆元。,2023/10/21,计算机科学与工程学院,70,定理15-2.5 设是一个群,是的子群,则:1）子群的幺元eS也是群的幺元eG；2）对aS，a在S中的逆元aS-1就是a在G中的逆元aG-1。证明：1)对aS，由于eS是S的幺元，所以有：eS*aa*eSa 又SG,所以aG,由eG是G的幺元，所以有：eG*aa*eGa 由、有：eS*aa*eSaeG*aa*eG，由于G满足消去律，所以有：eSeG。2)对aS，由于SG，所以aG，即a在S中的逆元就是a在G中的逆元。,

44、2023/10/21,计算机科学与工程学院,71,定理15-2.6 设是一个群，S是G的一个非空子集，则 是的子群的充要条件是：对a，bS，有a*b-1S。证明：“”设S是G的子群，对aS，由群的定义知，b-1S，即有a*b-1S。所以必要性成立；,“”由子群的定义知，需证明如下四点：1)S是非空的子集；,2023/10/21,计算机科学与工程学院,72,定理15-2.6 设是一个群，S是G的一个非空子集，则 是的子群的充要条件是：对a，bS，有a*b-1S。证明：“”设S是G的子群，对aS，由群的定义知，b-1S，即有a*b-1S。所以必要性成立；,“”由子群的定义知，需证明如下四点：1)S

45、是非空的子集；,2023/10/21,计算机科学与工程学院,73,定理15-2.6 设是一个群，S是G的一个非空子集，则 是的子群的充要条件是：对a，bS，有a*b-1S。证明：“”设S是G的子群，对aS，由群的定义知，b-1S，即有a*b-1S。所以必要性成立；,“”由子群的定义知，需证明如下四点：1)S是非空的子集；,2023/10/21,计算机科学与工程学院,74,2)幺元存在：由于S，所以有aS，由对a,bS,有a*b-S,取ab,有eGa*a-S;3)逆元存在：对a,bS，有a*b-1S，对bS，由eGS，有b-eG*b-S；4)封闭性：对a,bS，由3)知：b-S，由条件知：a*(

46、b-)-S，即a*bS.由1)、2)、3)、4)知:是的子群。,2023/10/21,计算机科学与工程学院,75,2)幺元存在：由于S，所以有aS，由对a,bS,有a*b-S,取ab,有eGa*a-S;3)逆元存在：对a,bS，有a*b-1S，对bS，由eGS，有b-eG*b-S；4)封闭性：对a,bS，由3)知：b-S，由条件知：a*(b-)-S，即a*bS.由1)、2)、3)、4)知:是的子群。,2023/10/21,计算机科学与工程学院,76,2)幺元存在：由于S，所以有aS，由对a,bS,有a*b-S,取ab,有eGa*a-S;3)逆元存在：对a,bS，有a*b-1S，对bS，由eGS

47、，有b-eG*b-S；4)封闭性：对a,bS，由3)知：b-S，由条件知：a*(b-)-S，即a*bS.由1)、2)、3)、4)知:是的子群。,2023/10/21,计算机科学与工程学院,77,例:,设是一个群，令：Ca|aG且对xG，有：a*xx*a 证明是的一个子群。证明:1)非空性：对xG，由于幺元eG存在，所以有:e*xx*ex，即eC，所以C是非空的；2)封闭性：对a，bC，则有：对xGa*xx*a，b*xx*b，(a*b)*xa*(b*x)a*(x*b)(a*x)*b(x*a)*bx*(a*b)，即：a*bC；,2023/10/21,计算机科学与工程学院,78,例:,设是一个群，令

48、：Ca|aG且对xG，有：a*xx*a 证明是的一个子群。证明:1)非空性：对xG，由于幺元eG存在，所以有:e*xx*ex，即eC，所以C是非空的；2)封闭性：对a，bC，则有：对xGa*xx*a，b*xx*b，(a*b)*xa*(b*x)a*(x*b)(a*x)*b(x*a)*bx*(a*b)，即：a*bC；,2023/10/21,计算机科学与工程学院,79,例:,设是一个群，令：Ca|aG且对xG，有：a*xx*a 证明是的一个子群。证明:1)非空性：对xG，由于幺元eG存在，所以有:e*xx*ex，即eC，所以C是非空的；2)封闭性：对a，bC，则有：对xGa*xx*a，b*xx*b，

49、(a*b)*xa*(b*x)a*(x*b)(a*x)*b(x*a)*bx*(a*b)，即：a*bC；,2023/10/21,计算机科学与工程学院,80,3)、逆元存在：对aC，有：对xG，a*xx*aCG，aG，即有：a-1G，有：a-1*(a*x)*a-1a-1*(x*a)*a-1，即有：x*a-1a-1*x，所以a-1C。由1)、2)、3)知:是的一个子群。,2023/10/21,计算机科学与工程学院,81,3)、逆元存在：对aC，有：对xG，a*xx*aCG，aG，即有：a-1G，有：a-1*(a*x)*a-1a-1*(x*a)*a-1，即有：x*a-1a-1*x，所以a-1C。由1)、

50、2)、3)知:是的一个子群。,2023/10/21,计算机科学与工程学院,82,3)、逆元存在：对aC，有：对xG，a*xx*aCG，aG，即有：a-1G，有：a-1*(a*x)*a-1a-1*(x*a)*a-1，即有：x*a-1a-1*x，所以a-1C。由1)、2)、3)知:是的一个子群。,2023/10/21,计算机科学与工程学院,83,例:,设是一个整数加群，令：Hnk|kZ且n是一个取定的自然数，证明是的一个子群。证明:1)非空性：显然；2)封闭性：对a，bH，有ank1，bnk2(k1，k2Z)，a+bnk1+nk2n(k1+k2)H(k1+k2Z)；3)逆元存在：对aH，有ank1