离散数学jme-3半群与群4

1、半群与第二半群与第二半群与独异子2.4 陪集与拉格朗日定循环群与置换2.4 陪集与拉格2.4 陪集与拉格朗日主要内容群的分解陪集的定义、实例、性拉格朗日定陪设H是G的子群，a陪设H是G的子群，aG称Ha是子群H在G中的右陪集Ha的代表元素coset)。称a(1)设Ge,a,b,c是Klein四元群，He,a是G子群，求H所有的右不同的右陪集只有两个，即H和b,c陪集例设A1,2,3,f1陪集例设A1,2,3,f1,f2,f6是AHf3f1f3,f2f3f3,f5Hf4例2：是群Z例2：是群的子群，ZE的所有右陪集如ZE0=ZE,ZE2=ZE,ZE-2=ZE,ZE1=Zo,ZE-1=Zo,ZE3

2、=Zo7例3：设为群，其中G=RR例3：设为群，其中G=RR，+定义设H=|y=2x。显是的子群对于任意的a=G，H关于a的右陪集为Ha 8陪集的基本性质设H是群陪集的基本性质设H是群G的子群HeH(1)任取aGaea和得aHa陪集的基本性质陪集的基本性质aHb ab-1H 证明：aHbab-1Hh(hHab-ab-HaHb使得ahb，即bh-1a任取h1aHah1ah1(hb(h1h)bHbHaHb反之，任取h1bHb从而得到 HbHa。综上所述，HaHb在例2.15中在例2.15中可以看出f3Hf5，所Hf3Hf5f3f -5=思思关于陪集，如何建立等价关？陪集的基本性质设陪集的基本性质设

3、H是群G的子群，在G上定义二元关系Rab-任取aG,aa-1eH R ab-1H (ab-1)-ba-1H所以R是对任取a,b,cG任取a,b,cGab-1Hbc-(ab-1)(bc-1)H ac-1R所以R是传递的任取bGR ab-根据定理2.9ab-1HHaHb bHa，从而证明了aRHa推论 设H是群G(1)任取a,b推论 设H是群G(1)任取a,bG，HaHbHaHb 。集合Ha|aGG的一个划分H在G中的右陪集是H和Hb，其中Hbb,c那么了G的一个划分陪集的基本性质设H陪集的基本性质设H是群G的子群f:HHa，f(x)xa任取haHahHf(h1)f(h2)，h1ah2ah1h2，

4、因此， HHa=Ha =aR=Ha =aR=abH b-1aH左陪集举群Gf1,f2,f6。令Hf1,f2，则H在左陪集举群Gf1,f2,f6。令Hf1,f2，则H在GHf3f1f3,f2f3f3,f5Hf4f Hf f ,f f f ,f 1f Hf f ,f f f ,f 2f Hf f ,f f f ,f f 3f f ,f f f ,f f Hf f ,f f f ,f 6结论：一般来说，对于群G的每个子群H不能保证有HaaH左右陪集个数相左右陪集个数相令分别表示H的右陪集和左陪集的集合，定义f:ST，f(Ha)a-可以证明f是S到T对a，bGHaHbab-1H(ab-1)-(b-1)

5、-1a-a-1Hb-这说明对于任意的HaS，必有唯一的f(Ha)T即fbH从而证明了f因此ST关于陪集的进一步说关于陪集的进一步说对于有限群G，H在G中的和|G|,|H|拉格朗日拉格朗日设G是有限群，H是G的子群根据定理2.10的推由于这r个右陪集是两两不交拉格朗日定理的推拉格朗日定理的推论设G是n阶群，则aG，|a|是n的因子anea0e,a1,a2,ar-根据定理2.4(1)，必有ane拉格朗日定理的拉格朗日定理的推论推论2对阶为素数的群G，必存在aG，使得G。证明 设|G|p，p是素数。任取aG，ae，则是G的子群拉格朗日定理的拉格朗日定理的应用实e，即有a-1a任取x,yG则xy (x

6、y)-因此G是Abely-1x-yx证明6阶群中必含有3阶证明6阶群中必含有3阶元如若不然，G中只含1阶和2阶元易证H是G但|H|=4，|G|=6，与拉格朗。例2.17 证明阶小于6例2.17 证明阶小于6的群都是阿贝尔群。2,3和5都是素数。由拉格朗日定理的推论2可知2（因为a i,a jG，有a ia ja i+ja j+ia ja i。），由刚才的分析可知G是阿贝小小有限群G的拉格朗日定理(|G|=|H|G:H)及两个应用：群在纠错码码二号二号控控应用：群在纠错码码二号二号控控码Sn是长度为n的字集，即S码Sn是长度为n的字集，即Sn=x1x2,xn|xi=0or 在Sn上定义一个二元运

7、算，设xx1x2,xn， y= y1y2,yn， 则有z=xy= z1z2,zn，其中 zi=xi yi,运算符 为按位加。证明对于Sn的任意子集C，若是群，则称C是群码(Group Code) 。奇, 就是将编码中的每个码, 使每个奇, 就是将编码中的每个码, 使每个码字所含1的个数)或奇数个()奇能检查出一个错误，但不能纠错验证一是群（为自身信息元校验编成码0110利用陪集性质的查设有一汉明码利用陪集性质的查设有一汉明码C, 它的字长为n, 信息位长为m, 校验位长为k。已知是群，而是它的子群。设有XCX在传递过程中第i位发生了错误变为1，其余为0。而此时有Xei=X或Xei=X。首先列出

8、所有的X可能出现单错的码字即对所有 XC及ei(i=1,2,n) 列出Xei=X, 将它们组成一其次当出现单错时X变成X用X查上表再用公纠的具体实构造群纠的具体实构造群的子群关于ei的左陪集 由拉格朗日定理：C在S中的左陪集个数2n-m=2K个故当2K =n+1时, 上述的左陪集之间互不且3. 2K n+1时, 则需继续构造左陪集, 构造的个数为2K(n+1)=p个。构造的方法是选取一个z1 Sn,使z1 Cz1eiC, 从而构造陪集z1C, 依此类推可构造p个左陪集。码陪码陪a4= a1 a2 ， a5= a1 a3 ， a6a1 a2a3 。CCe1 e2 e3 e4 e5 CCe1 e2

9、 e3 e4 e5 e6 z 设有某一X=011100， 在译码表中找到这个码字，它在第五行第四列，它的正确码字在第四列的C 行，即为：011110。而它的出错位为第五位，其e5在第五行的半群与第二半群与第二半群与独异子2.4 陪集与拉格朗日定循环群与置换2.6群的同态与同2.6群的同态与同和半群的同态类似,也可以定义群的同态与klein奇编码后的码字是群：封闭，可结合，存在幺元，逆元（为自身的与klein奇编码后的码字是群：封闭，可结合，存在幺元，逆元（为自身的信息元校验编成码字0110-1奇偶+偶奇-1-奇奇偶1-1偶f(-1)=奇*ffff0123-1奇偶+偶奇-1-奇奇偶1-1偶f(-

10、1)=奇*ffff0123群的同定义2.11群的同定义2.11 设G1,G2是群，：G1G2，若任意a,bG1则称是群G1到G2的同典型同的实例典型同的实例2.23：(1) G1是模n的整数加群。令n，则是G1到G2因为x,yZ(x+y)(x+y)modn(x)modn (y)modn (x) 典型同的实(2)设G1典型同的实(2)设G1是实数加群，G2：RR*, 则是G1到G2的同态,因为x,yR(3)设G1,G2是群，e2是G2：G1G2, (ab)e2e2e2同态设同态设：G1G2是群G1到G2的同若：G1G2是单射的，则称为单同态若：G1G2是双射的，则称为同构G1G2若G1G2，则称

11、是群G的自同态举例2.23：(1) G1是整数加群，G2Zn举例2.23：(1) G1是整数加群，G2模n的整数加群。令：ZZn, (x)(x)mod 则是G1到G2的同因为x,yZ(x+y)(x+y)modn(x)modn(y)mod(x) (2)设G1是实数加群，G2是非零实：RR*, 则是G1到G2的同态,因为x,yR例：设H=x|x=dn, d是某一例：设H=x|x=dn, d是某一定义函数那么，f是到的一个同构ZH证明又f是双射。故f是到的一个同构证明和是同构的和由此知道，当两个代数系统是同构的话，它们之间的同构函数可以是不唯一的。同态是从一个代数同态是从一个代数结构到同类代数结构的

12、函有诸如幺元、逆元、和二元运算之类的属性不变。形象地说，一个代数系统的同态象特性的情况下，对该述同构就是双射的同态。两个对象称为小本节主要小本节主要同态的分类（单同态、满同态、同构、自同态。2.7循环群与置换2.7循环群与置换主要内容循环群的定义及分循环群的生成置换群置换，置换的乘积，k阶轮换。循环群的设G是群，若存在aG循环群的设G是群，若存在aG则称G是循环群group)，记作G，称为G的生成元(generator)60是群，300，*的生成元，因此，该群是循运算,记f2=f1运算,记f2=f1f1f3=f2f1f4=f3f1.F=f1,f2,f3,f4验证是一个循环群,*abbcdfff

13、f0123f4 *babcf23ff0f23*babcf23ff0f23231f4 f1和f3是它示。 验证是一个循环群(示。 验证是一个循环群(四阶循环群)。*解：由运算表可知运算*是封闭的是幺元。，和2, 3, 4,2 , 3, 4 故群是由或生成，因循环群的根据循环循环群的根据循环群G根据生成元a的阶可以分成两类n阶循环群和无限循环群若a是nGa0e,a1,a2,an-那么|G|n，称G为n阶循环群若a是无限阶元,这时称G为无限循环群例如例如可以将这两个例子的结论定理化循环群的生循环群的生成设G若G是无限循环群，则G只有两个生成元，即a和a-。若G是n阶循环群，则G含有(n)(n)：欧拉

14、函数。对于任何正整数例例由定理2.19可知，a,a5,a7和a11是G的生成四阶循环Klein四元ffff0123四阶循环Klein四元ffff0123*eabc*例题：任何一个四阶群只例题：任何一个四阶群只能是四阶循环群或设四阶群为，其中e的置换n元置换置换n元置换及其表nk轮换分解对换分解n元对称n元置换及其表设S1,2,n，S上的任何双射函数SS称为S上的n元置换一般将n元置换及其表设S1,2,n，S上的任何双射函数SS称为S上的n元置换一般将n元置换 12n(n)例如：S1,2,3,4,55 233241233142都是5元置n元置换的乘定义2.16设,是n元置换，则和的复合也是n例如

15、上n元置换的乘定义2.16设,是n元置换，则和的复合也是n例如上面的5元置换和 412455 21334422354342 (i1)=i2, (i2)=i3, (ik-1)=ik, 且保持S中的其他元素不变,则称为S上的k阶轮换,记作(i1i2ik)。若k=2,这是也称 为S上的对例如5 223144例如5 223144 233441也叫四阶轮=（123轮换轮换(i1)=i2,(i2)=i3,(ik-令1=（i1i2ik）。它是从中分解出来的第一个轮换。根据函数的复合定义可将写作1,其中 后,必得到的轮换分8 12336445268 123364452617878 128是8先考虑所以从先考虑

16、所以从中分解出来的第一个轮换式(1 5 2 3 6), =(15236)(4)(7用同样的方法可以得到=(18342)(561阶轮换,例如可以写作(1 5 2 3 6)(7 8),如果n轮换分解式的特轮换的不交性、分解的唯轮换分解式的特轮换的不交性、分解的唯一2. 将n元置换分解为不交的轮换之积时,它的表这里的唯一性是说：若 = 1 t = 1 是 的两个轮换表示式,s 1, 2, 对换=(i1对换=(i1i2ik)是S上的k对换i4 i4 i4 iiiiiiii11对换i4 i4 i4 iiiiiiii1112iii 4 34113214i4 i 13i 1 23i4 iii1i1 234

17、8 23364452617878 2336445261787 23)(1 =(1 5 2 3 6)(7 =(1 8 3 4 2)(5 6 7)=(1 8)(1 3)(1 4)(1 2)(5 对换分解式的特 423对换分解式的特 42341 =(1 =(1 4)(2 4)(3 所含对换个数的奇偶性是不变的。例如上面的4元置换 表示成偶数个对换之积,而4元置换=（1234）成奇数个对换之积。如果n元置换 积,则称为奇置换,否则称为偶置换,不难证明奇置换和偶置n元对称考虑所有的n元置n元对称考虑所有的n元置恒等置换(1)是Sn中。-1是一个群,称为n例23(1)例23(1) ( 2) (13) (23) ( 23) (1) ( 2) (13) (23) ( 23) (12) ( ) (123) (132)( 3) (13)( 32