1、离离 散散 数数 学学浙江工业大学计算机学院浙江工业大学软件学院第五章 代数结构n引言n5-1 代数系统的引入n5-2 运算及其性质n5-3 半群和独异点n5-4 群与子群n5-5 阿贝尔群和循环群n5-6 置换群与伯恩赛德定理n5-7 陪集与拉格朗日定理n5-8 同态与同构n5-9 环与域2022-8-5离散数学2n代数系统也称为近世代数或抽象代数，是近代数学的重要分支。n法国数学家伽罗瓦1811-1832在1832年运用群的思想彻底解决了用根式求解代数方程的可能性问题，成为近世代数的创始人。n抽象代数学对于全部现代数学和一些其它科学领域都有重要的影响。2022-8-5离散数学3n本章讨论的
2、数学结构就是由集合上定义若干运由集合上定义若干运算而组成的系统算而组成的系统代数系统代数系统。n在计算机科学中，研究机器可计算性语言、算法计算的复杂性、刻划抽象的数据结构等等，都需要这现代代数系统知识。2022-8-5离散数学45.1 代数系统的引入n先引进在一个集合A上的运算运算概念。2022-8-5离散数学5n一元运算例1：将实数集合R上的每一个数a 0映射成它的倒数 。例2：求一个复数的共轭复数是复数集合C上的一元运算。n二元运算例3：在集合R上，对任意两个数所进行的普通”+”和”。例4：f：NNN，f()x+y 是自然数集合N上的二元运算。n三元运算例5：对于集合R上的任意三个数，条件
3、算术表达式if x=0 then y else z。2022-8-5离散数学6a1n共同的特征：其运算结果都是在原来的集合R或N中。n具有这种特征的运算是封闭封闭的，简称闭运算闭运算。相反地，没有这种特征的运算就是不封闭的。例5：f：NNN，f()x-y N对减法不封闭。例6：自动售货机系统 不封闭思考：例5例6中的运算封闭吗？2022-8-5离散数学7*一元硬币一元硬币二元硬币二元硬币一元硬币一元硬币矿泉水矿泉水可口可乐可口可乐二元硬币二元硬币可口可乐可口可乐酷儿酷儿n封闭封闭定义：对于集合对于集合A，一个从，一个从An到到B的映射，称的映射，称为集合为集合A上的一个上的一个n元运算元运算。
4、如果。如果B A，则称该，则称该n元运算是元运算是封闭封闭的。的。n一般情况下，不经说明，我们总是讨论封闭的代数系统。2022-8-5离散数学8例：以下哪些运算是封闭的？(1)自然数集合N上的减法运算。(2)整数集合I上的除法运算。(3)设A=1,2,3,10,二元运算x*y=质数p的个数，使得x py。2022-8-5离散数学9不封闭不封闭不封闭，当x=y=4时，x与y之间的质数个数为0n代数系统代数系统定义：一个非空集合A连同若干个定义在该集合上的运算f1,f2,fk所组成的系统就称为一个代数系统，记作。n例：,都是代数系统,其中+和分别表示普通加法和乘法。n例：是代数系统,其中和分别表示
5、n阶(n2)实矩阵的加法和乘法。n例：也是代数系统，其中含有两个二元运算和以及一个一元运算。2022-8-5离散数学1030 01 12 20 00 01 12 21 11 12 20 02 22 20 01 12022-8-5离散数学11*例：代数系统和的运算表分别如下图所示：n我们主要讨论同种类代数系统同种类代数系统的特性。n例如：V1=n V2=nV1、V2是同类型的代数系统，因为它们都含有2个二元运算，2个代数常数。但是它们的运算性质不一样。2022-8-5离散数学12本节学习要求n判断给定集合和运算能否构成代数系统判断给定集合和运算能否构成代数系统2022-8-5离散数学135.2
6、运算及其性质运算及其性质n一般的二元运算的性质。封闭性 结合性 交换性 分配性 吸收律 幂等律 消去律n特殊元素2022-8-5离散数学14二元运算n定义：设A为任意非空集合，函数f：AAA称为集合A上的一个二元运算二元运算。n推广：设A为任意非空集合，函数f：AnA称为集合集合A上上的一个n元运算元运算。n判断一种运算是否是A上的二元运算，最根本是运算关于集合是封闭的。2022-8-5离散数学15封闭性n定义5-2.1：设*是定义在集合A上的二元运算，如果对于任意的x，yA，都有x*yA，则称二元运算二元运算*在在A上是封闭上是封闭的。运算表中的每个元素都属于A。【例】设A=xx=2n,nN
7、，问，封闭吗？解：（1）2r,2sA，2r2s=2r+sA,r+sN 运算封闭（2）2,4A，2+4A，运算不封闭（3）2,4A，2/4A，运算不封闭2022-8-5离散数学16结合性n定义5-2.2：设*是定义在集合A上的二元运算，如果对于任意的x，y，zA，都有(x*y)*zx*(y*z)，则称该二元运算*是可结合的。【例】设A是一个非空集合，是A上的二元运算，对于任意a，bA，有abb，证明 是可结合运算。证明：对于任意的a，b，cA 有 (ab)cbcc a(bc)acc (ab)ca(bc)2022-8-5离散数学17【例】在自然数集N上，运算 是不可结合的。(A)a*b=a+b+3
8、(B)a*b=mina,b(C)a*b=a+2b(D)a*b=ab(mod 3)答案为C容易验证：(a*b)*c=(a+2b)*c=a+2b+2ca*(b*c)=a+2(b*c)=a+2(b+2c)=a+2b+4c2022-8-5离散数学18交换性n定义5-2.3：设*是定义在集合A上的二元运算，如果对于任意的x，yA，都有x*yy*x，则称该二元运算*是可交换的。n特点：运算表中的元素关于主对角线对称运算表中的元素关于主对角线对称。n【例】设Q是有理数集合，是Q上的二元运算，对任意的a，bQ，aba+b-ab，问运算是否可交换。n解：对于a,bA，有 aba+b-abb+a-baba 运算是
9、可交换的。2022-8-5离散数学19分配性n定义5-2.4：，若x,y,zA，有 x*(yz)=(x*y)(x*z)和(yz)*x=(y*x)(z*x)，称运算*对于运算是可分配的。n注：（1）*对+左可分配左可分配 x,y,zA，有x*(y+z)=x*y+x*z（2）*对+右可分配右可分配 x,y,zA，有(x+y)*z=x*z+y*z 只有当（1）（2）两式同时成立时，才能说运算*对运算+可分配。2022-8-5离散数学20【例】设A=a,b，二元运算*，定义如下表，问分配律成立否？n解：（1）运算对运算*可分配，n即证：x,y,zA,x(y*z)=(xy)*(xz)n证明：当x=a时(
10、运算结果为左边)，即x(y*z)=x=a；(xy)*(xz)=x*x=x=a；当x=b时(运算结果为右边)，即x(y*z)=y*z；(xy)*(xz)=y*zn（2）运算*对运算不可分配n证：b*(ab)=b*a=b，而(b*a)(b*b)=ba=a2022-8-5离散数学21a ab ba aa aa ab ba ab b*a ab ba aa ab bb bb ba a吸收律定义5-2.5：设，若x,y,zA,有x*(xz)=x称运算*满足吸收律；有x(x*y)=x称运算满足吸收律。【例】N为自然数集,x,yN，x*y=maxx,y，xy=minx,y，试证：*，满足吸收律。证明：x,yN
11、，x*(xy)=maxx,minx,y=x *满足吸收律 x,yN，x(x*y)=minx,maxx,y=x 满足吸收律。2022-8-5离散数学22幂等律n定义5-2.6：设，若对于xA，有x*x=x，则称运算*是幂等律幂等律。n如果S中的某些x满足x*x=x，则称x为运算*的幂幂等元等元。n特征：特征：运算表中主对角线上的每个元素关于运算表中主对角线上的每个元素关于主对角线与它所在行主对角线与它所在行(列列)的表头元素相同的表头元素相同.2022-8-5离散数学23【例】设(s)是集合S的幂集，在(s)上定义的两个二元运算，集合的“并”运算和集合的“交”运算，验证,满足幂等律。证明：对于任
12、意的A(s)，有AA=A和AA=A，因此运算和都满足等幂律。【例】普通的加法和乘法不适合幂等律。但0是加法的幂等元，0和1是乘法的幂等元。2022-8-5离散数学24消去律定义：设*为S上的二元运算，如果对于任意的 x,y,zS，满足以下条件：（1）若x*y x*z，则y z（左消去律）（2）若y*x z*x，则yz（右消去律）则称*运算满足消去律。【例】整数集合上的加法和乘法。加法满足消去律；乘法不满足。但x0时乘法满足消去律。【例】幂集P(S)上的并和交运算。一般不满足消去律。2022-8-5离散数学25特殊元素特殊元素n在某些代数系统中存在着一些特定的元素，它们对于系统的一元或二元运算起
13、着重要的作用。n例如：中的+运算有单位元0。n例如：矩阵乘法运算中的单位矩阵。n将这些特殊元素作为代数系统的性质进行讨论，这时称这些元素为该代数系统的特异元素特异元素或代数代数常数常数。2022-8-5离散数学26幺元n定义5-2.7：设，eR,eL,eA，有n若xA，有eL*x=x，称eL为A中关于运算*的左幺元；n若xA，有x*eR=x，称eR为A中关于运算*的右幺元；n若xA，有e*x=x*e=x，称e为A中关于运算*的幺元，即元素e既是左幺元又是右幺元。n幺元也称为“单位元”。2022-8-5离散数学27【例】设集合S，在S上定义的两个二元运算*和如下表所示。试指出左幺元或右幺元。幺元
14、所对应的行和列依次与运算表的行和列一致。2022-8-5离散数学28n定理5-2.1 设，若el和er分别是*的左、右幺元，则el=er=e，且A中的幺元是唯一的。n证明：el el*er (er为右幺元)el*er er (el为左幺元)el=er，将这个幺元记作e。假设e也是A中的幺元，则有 e=e*e=e e 是A中关于运算*的唯一的幺元。2022-8-5离散数学29零元定义5-2.8：设，R,L,A，有若xA，有L*x=L，称L为运算*的左零元；若xA，有x*R=R，称R为运算*的右零元；若xA，有*x=x*=，称为运算*的零元。即既是左零元又是右零元。n【例】设集合S浅色，深色，定义
15、在S上的一个二元运算*如表5-2.3所示，试指出零元和幺元。n零元所对应的行和列中的元素都与该元素相同。2022-8-5离散数学30【例】代数系统A=，*用下表定义，请指出左（右）幺元、零元。n解：b是左幺元，无右幺元；a是右零元，b是右零元，无左零元。2022-8-5离散数学31*a ab bc ca aabbb babcc caba【例】指出代数系统、和的幺元和零元。n解：n的幺元为1，零元为0。n对运算，是幺元，s是零元；对运算，s是幺元，是零元。n 有幺元0，无零元。2022-8-5离散数学32定理5-2.2：设，l和r分别为运算*的左零元和右零元，则有l=r=，且为A上关于运算*的唯
16、一的零元。证明与证明幺元唯一相似，请同学们自己证明。2022-8-5离散数学33定理5-2.3：设，e 和分别为运算*的幺元和零元，如果A中元素个数大于1，则e。证明：用反证法。假设 e=，则xA有 x x*e x*这表示A中元素都是相同的，全都为 这与A中至少含有两个元素矛盾。所以，假设不成立，即e。2022-8-5离散数学34逆元逆元n定义5-2.9：设代数系统，e是运算*的幺元 若对某一元素aA，bl A，使bl*a e，则称 bl为a的左逆元，也称a是左可逆的。若对某一元素aA，br A，使a*br e，则称 br为a的右逆元，也称a是右可逆的。如果一个元素b，既是a的左逆元又是a的右
17、逆元，则称b是a 的一个逆元。2022-8-5离散数学35【例1】考虑代数系统，其中R是实数集，和是通常的加法和乘法。问：每个元素是否都有逆元？若有逆元，逆元是什么？对运算而言，R中的任何元素a都有逆元-a。对运算而言，R中除了数0外任何元素a都有逆元1/a，元素0无逆元。【例2】指出代数系统的逆元，其中N是自然数集，是通常的加法。中，仅幺元0有逆元0。2022-8-5离散数学36【例3】代数系统满足哪些性质？并指出其特殊元素，运算表示：x,yZ+，xylcm(x,y)，即求x和y的最小公倍数。解：运算可交换、可结合、是幂等的。xZ+，x1=x，1x=x，1为单位元。不存在零元。只有1有逆元，
18、是它自己，其他正整数无逆元2022-8-5离散数学37【例4】设A=a,b,c，A上的二元运算、如表所示。(1)说明、运算是否满足交换律、幂等律。(2)求出关于、运算的幺元、零元和所有可逆元素的逆元。abcaabcbbcaccab运算满足交换律，不满足幂等律。幺元是a，没有零元，且a-1=a，b-1=c，c-1=b。运算满足交换律和幂等律。幺元是a，零元是b，只有a有逆元，a-1=a。运算满足幂等律，不满足交换律。没有幺元，没有零元，更谈不上逆元。abcaabcbbbbccbc abcaabcbabccabc【例5】设集合设集合S=S=,，定义在，定义在S S上的一个二元上的一个二元运算运算*
19、如表所示。试指出代数系统如表所示。试指出代数系统S,中的特殊元素。中的特殊元素。a,b互逆互逆：a所在行所在行、b所在列的元素所在列的元素，以及，以及b所在行所在行、a所所在列的元素都是幺元。在列的元素都是幺元。2022-8-5离散数学39*n（1）幺元幺元e和零元和零元z是是全局全局的概念。的概念。且：如果幺元和零元存在，一定是唯一的。n（2）左逆元、右逆元、左逆元、右逆元、逆元是逆元是局部局部的概念的概念，它仅针对集合A中的某一元素。n一个元素的左逆元不一定等于该元素的右逆元，一个元素可以有左逆元而没有右逆元，一个元素的左（右）逆元可以不止一个。但但，对于，对于一个元一个元素素而言，而言，
20、若有逆元若有逆元，则唯一。则唯一。2022-8-5离散数学40定理5-2.4 设代数系统，A中存在幺元存在幺元e，且xA，都存在左逆元存在左逆元，若*是可结合的是可结合的运算，那么 中任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元唯一。证明：设任意a,b,cA，且b是a的左逆元，c是b的左逆元。（1）因为b=e*b=(bb=(b*a)a)*b b 所以 a a*b=(eb=(e*a)a)*b=(cb=(c*b)b)*a)a)*b=cb=c*(b(b*a a*b)=cb)=c*b=eb=e 所以 b也是a的右逆元，即b是a的逆元。（2）设任意元素a除了逆元b外，还存在一个逆元t，那
21、么 b=bb=b*e=be=b*(a(a*t)=(bt)=(b*a)a)*t=et=e*t=tt=t 所以，任意元素的逆元唯一。本节学习要求n判断给定二元运算的性质和特异元素。n作业：P178 1)ACE 2)n P184 1,2)AC,52022-8-5离散数学425.3 半群和独异点半群和独异点n群论是代数系统中研究得比较成熟的一个分支，在计算机形式语言，自动机理论，编码理论等得到广泛应用。2022-8-5离散数学43半群、独异点定义：(1)设V是代数系统，S 非空非空，*为S上的一个二元运算，若运算运算*封闭封闭，则称V为广群。(2)设V是代数系统，S 非空非空，*为S上的一个二元运算，
22、若运算运算*封闭封闭，且且运算运算*是可结合是可结合的，则称V为半群。(3)含有幺元的半群称为独异点，也称含幺半群、单位半群。有时也将独异点记作。2022-8-5离散数学44【例1】判断、是否半群、独异点？其中为普通乘法，-为普通减法，+为普通加法。n解：（1）封闭，可结合，存在幺元1。（半群、独异点）（2）封闭，可结合，存在幺元1。（半群、独异点），且是的子半群。（3）封闭，不可结合，为广群，不是半群。（4）虽是一个半群，但关于+不存在幺元，所以，不是独异点。2022-8-5离散数学45半群中元素的幂n对于半群中的元素，我们有一种简便的记法。由于半群中的运算是可结合的,可以定义元素的幂,对任
23、意xS,规定：x1xxn+1xn*x,nZ+用数学归纳法不难证明x的幂遵从以下运算规则：xn*xmxn+m(xn)mxnm m,nZ+n普通乘法的幂、关系的幂、矩阵乘法的幂等都遵从这个幂运算规则。如果有a2=a，则称a为半群中的幂等元幂等元。2022-8-5离散数学46独异点中的幂n独异点是特殊的半群，可以把半群的幂运算推广到独异点中去。n由于独异点V中含有单位元e，对于任意的xS,可以定义x的零次幂,即 x0exn*xmxn+m (xn)mxnm nNn不难证明，独异点的幂运算也遵从半群的幂运算规则，只不过m和和n不一定限于正整数不一定限于正整数，只要是自然数就成立。2022-8-5离散数学
24、47半群的性质1、有限半群必有幂等元。证明（P187定理5-3.2）：设是一个半群，如果S是一个有限集，则必 aS，有a*a=a。2、独异点运算表中任何两行两列均不相同。（P188 定理5-3.3）证明3、若是独异点，幺元为e,a,bS，若a，b均有逆元，则 a)(a-1)-1=a b)(a*b)-1=b-1*a-1（P189 定理5-3.4）证明2022-8-5离散数学48【例】设是半群，u A，若BAu，且在B上定义二元运算 为a ba bab(a,bA)(b=u)(a=u)试证是独异点。即证：运算 在B上封闭，运算 可结合，且存在幺元。证明：a,bB，由定义可知a bB，所以运算 在B上
25、封闭封闭。下面对a，b分种情况讨论运算 的结合性：1)若若a，bA，则a ba*b 当当cA时时，(a b)c(a*b)c(a*b)*c 因为是半群，所以*在A上可结合，有 (a*b)*ca*(b*c)a (b c)，当当cu时时，(a b)c(a*b)ua*b，a (b c)a (b u)a ba*b，故无论c为何元素，都有(ab)ca(bc)。2)若若bu，则(a b)ca c，而 a (b c)a c，所以(a b)ca (b c)。3)若若au，则(a b)cb c，而a (b c)b c，所以(a b)ca (b c)。由讨论可知，运算运算 在在B上可结合上可结合。又由定义知，对任一
26、元素aB，有a uu aa，所以 u是B中关于运算 的单位元。综上可知，是独异点。n运算如下表所示，能使成为独异点。n (a)(b)(c)(d)2022-8-5离散数学52*abaabbab*abaaabbb*abaaabaa*abaabbba本节本节学习要求n独异点定义。n证明一个代数系统为独异点。n作业：P190 3,5,62022-8-5离散数学535.4 群和子群群和子群n群论是抽象代数发展充分的一个分支，广泛应用于计算，通讯，计算机科学，是我们这一章的重点。n群的定义n群的性质n子群n元素的阶2022-8-5离散数学54群n定义5-4.1：对于代数系统，其中G为非空集合，若对二元运算
27、*满足下列性质，则称为群：(1)运算封闭，即 a，bG，a*bG；(2)运算*可结合，即a,b,cG，a*(b*c)=(a*b)*c；(3)存在幺元e，即aG，e*a=a*e=a；(4)G中每个元素存在逆元。即 aG，a-1G,使a*a-1=a-1*a=e 2022-8-5离散数学55n群是每个元素都可逆每个元素都可逆的独异点。n 群 独异点 半群 广群2022-8-5离散数学56【例1】考察下列代数系统：(1)，I为整数集合，+是通常的加法运算；(2)，Q是有理数集合，是通常的 乘法运算；(3)，(S)为S的幂集，为对称差运算.问：以上代数系统是群吗？2022-8-5离散数学57【例2】Q是
28、有理集，（其中*为普通乘法）不能构成 。（A）群 （B）独异点 （C）半群 （D）交换半群2022-8-5离散数学58【例3】，Z4=0,1,2,3即R是Z上的模4同余关系，Z4上运算+4，定义为：m,nZ4，m+4n=(m+n)(mod4)，运算表见下。判断的代数结构。2022-8-5离散数学59定义5-4.2：若是一个群，如果G为有限集，则称为有限群有限群，G中元素个数|G|称为群的阶数阶数；若G是无限集，称为无限群无限群。只含幺元的群称为平凡群平凡群。（1），与即为无限群。（2）是有限群，也是n阶群。（3）是平凡群。2022-8-5离散数学60群的性质1、群中不可能有零元。证明2、群中任
29、一元素的逆元素是唯一的。证明3、方程a*xb，y*ab都有解且有唯一解。证明 (即方程解的唯一性：该唯一解为a-1*b)作业：证明“群中不可能有零元”。2022-8-5离散数学61定理5-4.3：为群,则G中适用消去律，即对任意a,b,cG 有 (1)若a*ba*c，则bc。(2)若b*ac*a，则bc。证明：(1)a*ba*c a-1*(a*b)a-1*(a*c)(a-1*a)*b(a-1*a)*c e*be*c bc (2)同理可证消去律群中的幂n对群的任意元素a，我们可以同独异点一样来定义它的幂：a0=e，对任何正整数n，an+1=an*a，群的幂运算有下列性质：n定理：对群的任意元素a
30、,bG，有（1）(a-1)-1a（2）(a*b)-1b-1*a-1（3）(an)-1=(a-1)n（记为a-n）（n为整数）证明2022-8-5离散数学63n定理：对群的任意元素a,b，及任何整数m，n,有n （1）am*an=am+nn （2）(am)n=amn2022-8-5离散数学64【例1】设S=1,2，试给出(S)上的对称差运算表，并指出的代数系统。的运算表121,21,211,22221,2111,221 1,221解答【例2】设g=a,b,c,d，*为G上的二元运算，*运算表如下。不难证明G是一个群。e是G中的幺元；G中任何元素的逆元就是它自身；在a,b,c三个元素中（即除幺元外
31、），任何两个元素运算的结果都等于另一个元素；除幺元外，其余元素都是二阶元，即a*a=a2=e。这个群称为klein四元群。置换n定义5-3.3：设S是一个非空集合，从集合S到S的一个双射双射称为S的一个置换。n定理5-4.4：群的运算表中的每一行或每一列都是G的元素的一个置换。n即G中的每个元素，在运算表的每行或每列中出现且仅出现一次。2022-8-5离散数学67子群定义：设是群，H是G的非空子集，如果也构成群，则称是的一个子群(subgroup)。说明：任何群都存在子群。和 都是的子群，称为的平凡子群平凡子群。例：是一个群，其中I为整数集合，+为普通加法运算。设H=x|x=2n，nI，则是的
32、一个子群。2022-8-5离散数学68子群判定定理一定理：设为群，那么为的子群的充分必要条件是：（1）G的幺元eH；（2）对a，bH，则a*bH；（3）对aH，则a-1H。证明。即运算在运算在H H上封闭，且上封闭，且H H中每个元素都有逆元。中每个元素都有逆元。思考：条件（1）是必须的吗？对于有限集合，子群的判定更加简单。2022-8-5离散数学69子群判定定理二定理5-4.7：设为群，H是G的非空非空子集。如果H为有限集，则 是是的子群的子群 运算运算*在在H上封闭上封闭证明2022-8-5离散数学70子群判定定理三n定理5-4.8：设为群，H是G的非空非空子集，则是是的子群的子群 a,b
33、H有有a*b-1H证明2022-8-5离散数学71【例】设是群，对任一个aG，令C是与G中所有的元素都可交换的元素构成的集合，即 C=y|y*a=a*y，yG 则是G的子群，称为G的中心。证明：因为对任意xG，都有e*a=a*e，所以eC，所以C是G的非空子集非空子集。由y*a=a*y可得y=a*y*a-1 因此对任意x,yC，有 x*y-1=(a*x*a-1)*(a*y-1*a-1)=a*x*y-1*a-1 因此 x*y-1*a=a*x*y-1 所以x*y-1H，故是G的子群。2022-8-5离散数学72【例】设是群，,是G的子群。证明：(1)也是的子群。(2)是的子群当且仅当 HK 或 K
34、H。证明：证明：(1)由eHK 知 HK非空非空。对a,bHK，必有aH，aK，bH，bK。由于H和K是G的子群，必有 a*b-1H 和 a*b-1K，从而推出 a*b-1HK。根据子群判定定理三，命题得证。(2)是的子群当且仅当 HK 或或 KH。证明：充分性是显然的。必要性，用反证法。假设 HK 且且 KH，那么存在h和k使得 hHhK 并且 kKkH这就推出 h*kH。若不然，由是G的子群且hH可知：h-1H则对任意k，有kh-1*(h*k)H，与假设“存在k，使得kH”矛盾。同理可证，h*kK。从而得到 h*kHK，这与是子群矛盾。【习题1】设S=1,2,3,4，S上的二元运算如下：x
35、 y(xy)mod 5，x,yS试求运算的运算表(X与Y的乘积除5得到的余数)，并指出的代数系统。解答 1 12 23 34 41 11 12 23 34 42 22 24 41 13 33 33 31 14 42 24 44 43 32 21 1【习题2】设为群，a,bG，且(a*b)2a2*b2，证明a*bb*a。证明：由(a*b)2a2*b2 得(a*b)*(a*b)(a*a)*(b*b)根据群中的消去律，a-1*(a*b)*(a*b)*b-1a-1*(a*a)*(b*b)*b-1可得 b*aa*b，得证。【习题3】设是一个独异点,并且每个元素都有右逆元,证明为群。证明：设e是中的幺元。
36、每个元素都有右逆元，即xG，yG使得x*y=e；而对于此y，又有zG使得y*z=e。由于xG均有x*e=e*x=x，因此 z=e*z=x*y*z=x*e=x 即：x*y=e=y*z=y*x=e 所以，y既是x的右逆元，又是x的左逆元，故xG均有逆元，为群。【习题4选讲】设为群，a,bG,kZ+，证明（a-1*b*a)ka-1*b*a bkb证明：充分性充分性(a-1*b*a)k(a-1*b*a)*(a-1*b*a)*(a-1*b*a)*(a-1*b*a)(k个a-1ba)a-1*b*(a*a-1)*b*(a*a-1)*(a*a-1)*b*a a-1*bk*a a-1*b*a(因为 bkb)必要
37、性必要性由（a-1*b*a)ka-1*b*a 得(a-1*b*a)*(a-1*b*a)(a-1*b*a)a-1*b*a化简得a-1*bk*aa-1*b*a由消去律得bkb。本节学习要求n利用子群的三个判定定理，证明群的子集是子群。n作业：P197 1,2,32022-8-5离散数学79子半群定义：设是一个半群，BS且在B上是封闭的，那么也是一个半群，通常称是半群的子半群。例：设表示普通的乘法运算，那么、和都是的子半群。2022-8-5离散数学80return定理5-3.2证明：是半群，对于b S，由运算*封闭可知：b2=b*bS，b2*b=b*b2=b3S，b4，b5 S S有限，所以必定存在
38、，j；j，有bi=bj bi=bj=bj-i*bi当qi,必有bi=bq,所以有bq=bj-i*bq令p=ji，bq=bp*bq又p1 k，有kpi，使得bkp=bp*bkp(1)由(1)得：bkp=bp*bkp=bp*(bp*bkp)=bkp*bkp令a=bkp S 则a*a=a，bkp是等幂元。2022-8-5离散数学81return定理5-3.3证明n只要任意两行（两列）中至少有一对元素不相等，则可证明任意的两行（两列）不等。n证明：设独异点的幺元为e，对于任意 a，bS且a b，总有（1）a*e=a b=b*e由a，b任意性，有运算表中任两行不同；（2）e*a=a b=e*b由a，b任
39、意性，有运算表中任两列不同。2022-8-5离散数学82return定理5-3.4证明a)a-1是a的逆元，所以a-1既是a的左逆元又是a的右逆元 即：a-1*a=a*a-1=e a既是a-1的右逆元又是a-1的左逆元，a是a-1的逆元 即(a-1)-1=ab)要证(a*b)-1=b-1*a-1，即证b-1*a-1为a*b的逆元。(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=e b-1*a-1是a*b的右逆元，又（b-1*a-1）*（a*b）=b-1*（a-1*a）*be b-1*a-1是a*b的左逆元，(a*b)-1=b-1*a-12022-8-5离散数学83r
40、eturn证明(an)-1=(a-1)n 证明：对n进行归纳。群首先是独异点，所以an+1=an*a。设n=1，命题显然成立。设n=k时(ak)-1=(a-1)k成立，即(a-1)k是ak的逆元，那么ak+1*(a-1)k+1=(ak*a)*(a-1*(a-1)k)=ak*(a*a-1)*(a-1)k =ak*e*(a-1)k=ak*(a-1)k=e (a-1)k+1*ak+1=(a-1)k*(a-1*a)*ak=(a-1)k*ak=e 故ak+1的逆元为(a-1)k+1，即(ak+1)-1=(a-1)k+1。归纳完成，得证。return群中不可能有零元。证明：（1）当群的阶为1时，它的唯一元
41、素视作幺元e；（2）设|G|1且群中有零元，那么群中 xG，都有*x=x*=e(定理5-2.3，若|G|1，且同时存在e和，则 e)所以，零元就不存在逆元，这与是群矛盾。2022-8-5离散数学85return群中任一元素逆元唯一n请同学们自己证明。2022-8-5离散数学86return群中a*xb方程解唯一证明：（1）存在性 设群的单位元为e，令xa-1*b，则 a*xa*(a-1*b)(a*a-1)*be*b=b 所以xa-1*b是方程a*xb的解。（2）唯一性 若还有xG，使得a*xb，则 xe*x (a-1*a)*xa-1*(a*x)a-1*b=x 故xa-1*b是方程a*xb的唯一
42、解。2022-8-5离散数学87return证明：先证：为子群 (1)(2)(3)式成立。（1）设的幺元为e,对于xH G,那么e*x=x=e*x。由于群中满足消去律,xG，故e=e,所以eH。（2）*在H上封闭是显然的（由子群定义可知）。（3）设中a在H中逆元为b,那么a*b=b*a=e,因为HG,所以a,bG由逆元的唯一性,b就是a在G中的逆元,即b=a-1H。2022-8-5离散数学88再证：(1)(2)(3)式成立 为子群很明显：H非空；由条件(2)，运算*在H上封闭；由条件(1)“G的幺元eH”，eH由条件(3)“对aH，则a-1H”可知，a-1Hx,y,zH G，为群，所以(x*y
43、)*z=x*(y*z)，即运算*是可结合的。由群的定义可知，为群，即为的子群。2022-8-5离散数学89return（判定定理二）证明：必要性是显然的。充分性。只需证明H中含有幺元且每个元素有逆元。任取aH，若ae，则a-1e-1eH。若ae,令 Sa,a2,，因为运算*封闭，所以SH。由于H是有穷集，必有aiaj(i1时，由aj-i-1*a=e 和 a*aj-i-1=e可知aj-i-1为a的逆元；j-i=1时，由ai=ai*aj-i可知a即为幺元，幺元以自身为逆元；从而证明了 a-1=aj-i-1H（H中每个元素存在逆元）。return（判定定理三）证明：必要性：任取a,bH，由于是的子群
44、，必有b-1H，由封闭性有 a*b-1H。充分性：因为H非空，必aH。由a,aH，得a*a-1H，即eH。任取aH，由e,aH 得 e*a-1H，即a-1H。任取a,bH，由上一 步的证明可知 b-1H；由a,b-1H，得a*(b-1)-1H，即 a*bH。综合所述，根据判定定理一，是的子群。return5-5 阿贝尔群和循环群n定义5-5.1 如果群中的运算*是可交换的，则称该群为阿贝尔群阿贝尔群，或称交换群交换群。n定义5-5.2 设为群，若在G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称该群为循环群循环群，元素a 称为循环群G的生成元生成元。阿贝尔群n例题例题1 1 设S=a
45、,b,c,d，在S上定义一个双射函数f：f(a)=b，f(b)=c，f(c)=d，f(d)=a，对于 xS，构造复合函数 f2(x)=f f(x)=f(f(x)f3(x)=f f2(x)=f(f2(x)f4(x)=f f3(x)=f(f3(x)如果f0表示S上的恒等映射，即 f0(x)=x,xS 易知f4(x)=f0(x)，记f1=f，构造集合 F=f0,f1,f2,f3，那么是一个阿贝尔群阿贝尔群。(1)F是封闭的是封闭的(2)F是可结合的是可结合的(3)存在幺元存在幺元(4)都有逆元都有逆元(5)可交换可交换f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f
46、3f0f1f2阿贝尔群n定理5-5.1 设是一个群，是阿贝尔群的充要条件是对任意的a,bG，有(a*b)*(a*b)=(a*a)*(b*b)。证明证明 充分性充分性 即证a*b=b*a。a*(a*b)*b=(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b 所以a-1*(a*(a*b)*b)*b-1=a-1*(a*(b*a)*b)*b-1 即有：a*b=b*a。因此是阿贝尔群。必要性必要性 因为是阿贝尔群，则对任意的a,bG，有：a*b=b*a 因此(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)循环群n定理5-5.2 任何一个循环群必定是阿贝
47、尔群任何一个循环群必定是阿贝尔群。证明：设是一个循环群，它的生成元是a,那么，对于任意的x,yG，必有r,sI，使得 x=ar,y=as 而且 x*y=ar*as=ar+s=as+r=as*ar=y*x 因此，是一个阿贝尔群。广群半群群独异点循环群循环群阿贝尔群阿贝尔群有限循环群n定理5-5.3 设是一个由元素aG生成的有限有限循环群。如果G的阶数是n，即|G|=n，则an=e，且 G=a,a2,a3,an-1,an=e 其中e是中的幺元，n是使an=e的最小正整数。证明证明：先证明n是使an=e的最小正整数。然后证明a,a2,a3,an各不相同。(1)假设存在一个正整数m，mn，使得am=e
48、，由于是一个循环群，所以G中的任何元素都能写成ak,而且k=mq+r，其中q是某个整数，0rm。这就有:ak=amq+r=(am)q*ar=(e)q*ar=ar 这就导致了G中每一个元素都可以表示成ar，这样，G中最多有m个不同(a0,a,a2,a3,an-1)的元素，与|G|=n相矛盾。(2)反证法，假设有限循环群中存在两个元素相同：ai=aj,其中1ijn，就有e=aj-i(ai=aj右侧同*a-i)，而这是不可能的(群中幺元唯一，此题中为an=e)。所以a,a2,a3,an都不相同。循环群 【例】设G=,，在G上定义的二元运算*如下表所示：*验证是一个循环群循环群。G,是一个群是一个群G
49、,可由可由生成生成G,可由可由生成生成一个循环群的生成元可以不是唯一的。一个循环群的生成元可以不是唯一的。【例】Nk=0，1,k-1，是循环群吗？如果是，它的生成元是什么？2022-8-5离散数学100+4 0 1 2 30 0 1 2 3112 3 022 3 0 13 30 1 2元素的阶n定义：设a是G中的一个元素，若kI+，使得ak=e，则使得使得ak=e的最小正整数的最小正整数k称为称为元素元素a的阶的阶（或称“a的周期”），记为O(a)，并称a是有限阶的元素。2022-8-5离散数学101元素的阶n定理：设a是群中的一个r阶元素，k是正整数，则：(1)ak=e r|k（即k一定是r
50、的整数倍）(2)O(a)=O(a-1)（元素与其逆元的阶相同）(3)r|G|（元素的阶一定小于等于群的阶）若若a为为的生成元，则的生成元，则O(a)=|G|2022-8-5离散数学102证明:(1)充分性充分性：r|k ak=e 设 r|k，则存在整数m，使得k=rm，ak=arm=(ar)m=em=e必要性必要性：ak=e r|k若ak=e，由带余除法，一定存在整数p,q，使得k=pr+q(0 qr)，于是ak=apr+q=apr*aq=(ar)p*aq=(e)p*aq=e*aq=aq=e（ak=e）因为r是a的阶，所以q不是a的阶，只有q=0才可能有aq=e，所以r|k。(2)(3)证明略
