《离散数学群与半群幻灯片》由会员分享，可在线阅读，更多相关《离散数学群与半群幻灯片（25页珍藏版）》请在金锄头文库上搜索。
1、第11章 半群与群,离 散 数 学,江苏科技大学本科生必修课程,计算机教研室 周塔,本章内容,11.1 半群与独异点 11.2 群的定义与性质 11.3 子群 11.4 陪集与拉格朗日定理 11.5 正规子群与商群 11.6 群的同态与同构 11.7 循环群与置换群 本章总结 例题选讲 作业,11.1 半群与独异点,半群与独异点都是具有一个二元运算的代数系统。 半群与独异点的定义，及其子代数的说明。 半群与独异点的幂运算。 半群与独异点的同态映射。,半群与独异点,定义11.1 (1)设V是代数系统，为二元运算，如果运算是可结合的，则称V为半群（semigroup）。 (2)设V是半群,若eS是
2、关于运算的单位元,则称V是含幺半群，也叫做独异点（monoid）。 有时也将独异点V记作V。,半群与独异点的实例,，都是半群,+是普通加法。这些半群中除外都是独异点。 设n是大于1的正整数,和都是半群,也都是独异点,其中+和分别表示矩阵加法和矩阵乘法。 为半群,也是独异点,其中为集合的对称差运算。 为半群,也是独异点,其中Zn0,1,n-1,为模n加法。,半群中元素的幂,由于半群V中的运算是可结合的,可以定义元素的幂,对任意xS,规定： x1x xn+1xn x, nZ+ 用数学归纳法不难证明x的幂遵从以下运算规则： xn xmxn+m (xn)mxnm m,nZ+ 普通乘法的幂、关系的幂、矩
3、阵乘法的幂等都遵从这个幂运算规则。,独异点中的幂,独异点是特殊的半群，可以把半群的幂运算推广到独异点中去。 由于独异点V中含有单位元e，对于任意的xS,可以定义x的零次幂,即 x0e xn+1xn x nN,半群与独异点的直积,定义11.2 设V1，V2是半群(或独异点), 令SS1S2,定义S上的运算如下： ,S, 称为V1和V2的直积，记作V1V2。 可以证明V1V2是半群。 若V1和V2是独异点，其单位元分别为e1和e2，则是V1V2中的单位元，因此V1V2也是独异点。,半群与独异点的同态映射,定义11.3 (1)设V1,V2是半群,: S1S2。 若对任意的x,yS1有 (xy)(x)
4、(y) 则称为半群V1到V2的同态映射,简称同态(homomorphism)。 (2)设V1,V2是独异点, : S1S2. 若对任意的x,yS1有 (xy)(x)(y) 且(e1)e2, 则称为独异点V1到V2的同态映射,简称同态。,两点说明：,为了书写的简便，有时经常省略上述表达式中的算符和，而简记为 (xy)(x)(y) 应该记住，该表达式中左边的xy是在V1中的运算，而右边的 (x) (y)是在V2中的运算。,本节的主要内容,集合S和运算构成半群的条件（封闭性、结合律）。 集合S和运算构成独异点的条件（封闭性、结合律、单位元）。 半群与独异点的两条幂运算规则：xn xmxn+m ，(x
5、n)mxnm 。 通过笛卡尔积构造直积 。 同态映射的判别：(xy)(x)(y) 对于独异点要加上(e)e。,定义11.2说明,任取,S () = = = () = () = = ,11.2 群的定义与性质,群是特殊的半群和独异点。 群论中常用的概念或术语： 有限群、无限群、平凡群、交换群、元素的幂和阶。 群的运算规则。,群的定义,定义11.4 设是代数系统，为二元运算。如果运算是可结合的，存在单位元eG，并且对G中的任何元素x都有x-1G,则称G为群（group）。 举例 (1),都是群,而和不是群。 (2)是群,而不是群。因为并非所有的n阶实矩阵都有逆阵。,Klein四元群,设Ga,b,c
6、,d，为G上的二元运算，见下表。,G是一个群： e为G中的单位元； 运算是可结合的； 运算是可交换的； G中任何元素的逆元就是它自己； 在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素。,称这个群为Klein四元群,简称四元群。,群的直积,设, 是群，在G1G2上定义二元运算如下： ,G1G2 , 称是G1与G2的直积。 上一节已经证明： 是独异点， 可以证明对任意的G1G2 , 是的逆元， 因此G1G2关于运算构成一个群。,群论中常用的概念或术语,定义11.5 (1)若群G是有穷集,则称G是有限群，否则称为无限群。 群G的基数称为群G的阶，有限群G的阶记作|G|。 (2)只含单
7、位元的群称为平凡群。 (3)若群G中的二元运算是可交换的，则称G为交换群或阿贝尔(Abel)群。,例,是无限群、交换群。 是有限群，也是n阶群、交换群。 Klein四元群是4阶群、交换群。 是平凡群、交换群。,群中元素的n次幂,定义11.6 设G是群，aG，nZ，则a的n次幂,与半群和独异点不同的是：群中元素可以定义负整数次幂。,群中元素的阶,定义11.7 设G是群，aG，使得等式 ake 成立的最小正整数k称为a的阶，记作|a|k，这时也称a为k阶元。若不存在这样的正整数k,则称a为无限阶元。 举例 在中，2和4是3阶元，3是2阶元，而1和5是6阶元，0是1阶元。 在中，0是1阶元，其它的整
8、数都是无限阶元。 在Klein四元群中，e为1阶元，其它元素都是2阶元。,群的性质群的幂运算规则,定理11.1 设G为群,则G中的幂运算满足： (1) aG,(a-1)-1a。 (2) a,bG，(ab)-1b-1a-1。 (3) aG，anaman+m，n,mZ。 (4) aG，(an)manm，n,mZ。 (5) 若G为交换群，则(ab)nanbn。 分析： (1)和(2)可以根据定义证明。 (3)、(4)、(5)中的等式,先利用数学归纳法对于自然数n和m证出相应的结果，然后讨论n或m为负数的情况。,定理11.1的证明,(1) aG,(a-1)-1a。 (a-1)-1是a-1的逆元，a也是
9、a-1的逆元。 （或者：a-1是a的逆元，a也是a-1的逆元。） 根据逆元的唯一性， (a-1)-1a。 (2) a,bG，(ab)-1b-1a-1。 (b-1a-1)(ab)b-1(a-1a)bb-1be (ab)(b-1a-1)a(bb-1)a-1aa-1e 故 b-1a-1是 ab 的逆元。 根据逆元的唯一性等式得证。,定理11.1的证明,(3) aG，anaman+m，n,mZ。 先考虑n,m都是自然数的情况。任意给定n，对m进行归纳。 m0，有ana0aneanan+0成立。 假设对一切mN有anaman+m成立，则有 anam+1an(ama)(anam)aan+maan+m+1
10、由归纳法等式得证。 下面考虑存在负整数次幂的情况。 设n0，m0，令n-t，tZ+，则,anama-tam(a-1)tam,a-(t-m)am-tan+m tm,am-tan+m tm,对于n0,m0以及n0,m0的情况同理可证。,定理11.1的证明,(5) 若G为交换群，则(ab)nanbn。 当n为自然数时，对n进行归纳。,(ab)n,(ba)n,(ba)-m,(ba)-1)m,(a-1b-1)m,(a-1)m(b-1)m,a-mb-m,anbn,n0，有,(ab)0,e,ee,a0b0。,假设(ab)kakbk，则有,(ab)k+1,(ab)k(ab),(akbk)ab,ak(bka)b,ak(abk)b,(aka)(bk)b,(ak+1)(bk+1),由归纳法等式得证。 设n0，则,定理11.1说明,定理11.1(2)中的结果可以推广到有限多个元素的情况,即,注意上述定理中的最后一个等式只对交换群成立。 如果G是非交换群,那么只有,
