离散数学群与半群.ppt

第11章 半群与群离 散 数 学江苏科技大学本科生必修课程计算机教研室 周塔本章内容11.1 半群与独异点11.2 群的定义与性质11.3 子群11.4 陪集与拉格朗日定理11.5 正规子群与商群11.6 群的同态与同构11.7 循环群与置换群本章总结例题选讲作业11.1 半群与独异点q 半群与独异点都是具有一个二元运算的代数系统q 半群与独异点的定义，及其子代数的说明q 半群与独异点的幂运算q 半群与独异点的同态映射半群与独异点 定义11.1 (1)设V＝是代数系统，为二元运算，如果运算是可结 合的，则称V为半群（semigroup）2)设V＝是半群,若e∈S是关于运算的单位元,则称V是 含幺半群，也叫做独异点（monoid）有时也将独异点V记作V＝ 半群与独异点的实例q ，，，，都是半群,+是普通加法 这些半群中除外都是独异点q 设n是大于1的正整数,和都是半群,也都 是独异点,其中+和·分别表示矩阵加法和矩阵乘法q 为半群,也是独异点,其中为集合的对称差运算q 为半群,也是独异点,其中Zn＝{0,1,…,n-1},为模n 加法半群中元素的幂q 由于半群V＝中的运算是可结合的,可以定义元素的 幂,对任意x∈S,规定： ￿￿￿￿￿￿￿￿x1＝x xn+1＝xn x, ￿￿￿￿￿￿￿￿n∈Z+用数学归纳法不难证明x的幂遵从以下运算规则： ￿￿￿￿￿￿xn  xm＝xn+m￿￿￿￿￿￿(xn)m＝xnm ￿￿￿￿￿￿￿￿m,n∈Z+ q 普通乘法的幂、关系的幂、矩阵乘法的幂等都遵从这个幂 运算规则。

独异点中的幂独异点是特殊的半群，可以把半群的幂运算推广到独异点中 去由于独异点V中含有单位元e，对于任意的x∈S,可以定义x的 零次幂,即￿￿￿￿￿￿￿￿x0＝e￿￿￿￿￿￿￿￿￿￿￿￿￿￿xn+1＝xn x ￿￿￿￿￿￿￿￿n∈N半群与独异点的直积定义11.2 设V1＝，V2＝是半群(或独异点),令S＝S1×S2,定义S上的·运算如下：,∈S, ＝称为V1和V2的直积，记作V1×V2可以证明V1×V2是半群若V1和V2是独异点，其单位元分别为e1和e2，则是 V1×V2中的单位元，因此V1×V2也是独异点 半群与独异点的同态映射定义11.3 (1)设V1＝,V2＝是半群,: S1→S2若对任意的x,y∈S1有(xy)＝(x)(y)则称为半群V1到V2的同态映射,简称同态(homomorphism)2)设V1＝,V2＝是独异点, : S1→S2.若对任意的x,y∈S1有(xy)＝(x)(y) 且(e1)＝e2,则称为独异点V1到V2的同态映射,简称同态两点说明：q 为了书写的简便，有时经常省略上述表达式中的算符和 ，而简记为(xy)＝(x)(y)q 应该记住，该表达式中左边的xy是在V1中的运算，而右 边的 (x) (y)是在V2中的运算。

本节的主要内容q 集合S和运算构成半群的条件（封闭性、结合律）q 集合S和运算构成独异点的条件（封闭性、结合律、单位元）q 半群与独异点的两条幂运算规则：xn xm＝xn+m ，(xn)m＝xnm q 通过笛卡尔积构造直积 q 同态映射的判别：(xy)＝(x)(y)对于独异点要加上(e)＝e定义11.2说明任取,,S()= = = ()= ()= = 11.2 群的定义与性质q 群是特殊的半群和独异点q 群论中常用的概念或术语：有限群、无限群、平凡群、交换群、元素的幂和阶q 群的运算规则群的定义 定义11.4 设是代数系统，为二元运算如果运算是可结 合的，存在单位元e∈G，并且对G中的任何元素x都有x-1∈G,则 称G为群（group）举例 (1),,都是群,而和不是群2)是群,而不是群因为并非所有的n阶实 矩阵都有逆阵Klein四元群设G＝{a,b,c,d}，为G上的二元运算，见下表eabceeabcaaecbbbceaccbaeG是一个群：e为G中的单位元；运算是可结合的；运算是可交换的；G中任何元素的逆元就是它自己；在a,b,c三个元素中,任何两个元素 运算的结果都等于另一个元素。

称这个群为Klein四元群,简称四元群群的直积设, 是群，在G1G2上定义二元运算如下：,∈G1×G2 , ＝称是G1与G2的直积上一节已经证明： 是独异点，可以证明对任意的∈G1G2 , 是的逆元，因此G1×G2关于运算构成一个群群论中常用的概念或术语定义11.5(1)若群G是有穷集,则称G是有限群，否则称为无限群群G的基数称为群G的阶，有限群G的阶记作|G|2)只含单位元的群称为平凡群3)若群G中的二元运算是可交换的，则称G为交换群或阿贝尔 (Abel)群例q ,是无限群、交换群q 是有限群，也是n阶群、交换群q Klein四元群是4阶群、交换群q 是平凡群、交换群群中元素的n次幂定义11.6 设G是群，a∈G，n∈Z，则a的n次幂q与半群和独异点不同的是：群中元素可以定义负整数次幂群中元素的阶定义11.7 设G是群，a∈G，使得等式 ak＝e成立的最小正整数k称为a的阶，记作|a|＝k，这时也称a为k 阶元若不存在这样的正整数k,则称a为无限阶元举例q 在中，2和4是3阶元，3是2阶元，而1和5是6阶元，0 是1阶元q 在中，0是1阶元，其它的整数都是无限阶元q 在Klein四元群中，e为1阶元，其它元素都是2阶元。

群的性质—群的幂运算规则 定理11.1 设G为群,则G中的幂运算满足：(1) a∈G,(a-1)-1＝a2) a,b∈G，(ab)-1＝b-1a-13) a∈G，anam＝an+m，n,m∈Z4) a∈G，(an)m＝anm，n,m∈Z5) 若G为交换群，则(ab)n＝anbn分析：(1)和(2)可以根据定义证明3)、(4)、(5)中的等式,先利用数学归纳法对于自然数n和m 证出相应的结果，然后讨论n或m为负数的情况定理11.1的证明(1) a∈G,(a-1)-1＝aa-1)-1是a-1的逆元，a也是a-1的逆元或者：a-1是a的逆元，a也是a-1的逆元根据逆元的唯一性， (a-1)-1＝a2) a,b∈G，(ab)-1＝b-1a-1b-1a-1)(ab)＝b-1(a-1a)b＝b-1b＝e (ab)(b-1a-1)＝a(bb-1)a-1＝aa-1＝e故 b-1a-1是 ab 的逆元根据逆元的唯一性等式得证定理11.1的证明(3) a∈G，anam＝an+m，n,m∈Z先考虑n,m都是自然数的情况任意给定n，对m进行归纳m＝0，有ana0＝ane＝an＝an+0成立假设对一切m∈N有anam＝an+m成立，则有anam+1＝an(ama)＝(anam)a＝an+ma＝an+m+1由归纳法等式得证。

下面考虑存在负整数次幂的情况设n0，则定理11.1说明q 定理11.1(2)中的结果可以推广到有限多个元素的情况,即q 注意上述定理中的最后一个等式只对交换群成立q 如果G是非交换群,那么只有。