离散数学几个典型的代数系统群.ppt

《离散数学几个典型的代数系统群.ppt》由会员分享，可在线阅读，更多相关《离散数学几个典型的代数系统群.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学几个典型的代数系统群现在学习的是第1页，共37页半群与独异点-半群定义与性质-交换半群与独异点-半群与独异点的子代数和积代数-半群与独异点的同态群-群的定义与性质-子群与群的直积-循环群-置换群6.1 半群与群半群与群6.1半群与群2现在学习的是第2页，共37页半群的定义与实例半群的定义与实例定义定义 设设 V=是代数系统，是代数系统，o o为二元运算，如果为二元运算，如果 运算是可结合运算是可结合的，则称的，则称 V 为为半群半群.实例实例（1）,都是半群，都是半群，+是普通加法是普通加法.（2）设）设 n 是大于是大于1的正整数，的正整数，和和都是半群，其都是半群，其中中+和和 分

2、别表示矩阵加法和矩阵乘法分别表示矩阵加法和矩阵乘法.（3）为半群，其中为半群，其中 为集合的对称差运算为集合的对称差运算.（4）为半群，其中为半群，其中 Zn=0,1,n 1，为模为模 n 加法加法.（5）为半群，其中为半群，其中 为函数的复合运算为函数的复合运算.（6）为半群，其中为半群，其中R*为非零实数集合，为非零实数集合，运算定义运算定义 如下：如下：x,yR*,x y=y6.1半群与群3现在学习的是第3页，共37页元素的幂运算性质元素的幂运算性质由于半群中的运算是结合的，可以定义运算的幂。设V=为半群，对任意 xS，规定：x1=x xn+1=xnx,nZ+幂运算规则：xn xm=xn

3、+m(xn)m=xnm m,nZ+证明方法：数学归纳法6.1半群与群4现在学习的是第4页，共37页特殊的半群特殊的半群定义定义 设设V V=是半群是半群 (1)(1)若若 运算是可交换的，则称运算是可交换的，则称V V 为为交换半群交换半群 .(2)(2)若若 e eS S 是关于是关于 运算的幺元，则称运算的幺元，则称 V V 是是含幺半群含幺半群，也叫，也叫做做 独异点独异点.独异点独异点 V V 记作记作 V V=6.1半群与群5现在学习的是第5页，共37页独异点的幂独异点的幂独异点的幂运算定义独异点的幂运算定义 x0=e xn+1=xn x,nN幂运算规则幂运算规则 xn xm=xn+

4、m(xn)m=xnm m,nN 6.1半群与群6现在学习的是第6页，共37页交换半群和独异点的实例交换半群和独异点的实例例例1（1）,都是交都是交 换半群，也是独异点，换半群，也是独异点，+是普通加法是普通加法.（2）设）设 n 是大于是大于 1 的正整数，的正整数，和和都是都是 独异点，其中独异点，其中+和和 分别表示矩阵加法和矩阵乘法分别表示矩阵加法和矩阵乘法.加加 法构成交换半群，乘法不是交换半群法构成交换半群，乘法不是交换半群.（3）为交换半群和独异点，其中为交换半群和独异点，其中 为集合的对为集合的对 称差运算称差运算.（4）为交换半群与独异点，其中为交换半群与独异点，其中 Zn=0

5、,1,n 1，为模为模 n 加法加法.（5）为独异点，不是交换半群，其中为独异点，不是交换半群，其中 为函数的复合运为函数的复合运算算.6.1半群与群7现在学习的是第7页，共37页半群与独异点的子代数半群与独异点的子代数定义定义 半群的子代数称为半群的子代数称为子半群子半群，独异点的子代数称，独异点的子代数称为为子独异点。子独异点。判断方法：判断方法：设设 V=S,V=为半群，为半群，T T 是是 S S 的非空子集，的非空子集，T T是是V V的子半群当且仅当的子半群当且仅当T T对对o o运算封闭运算封闭.设设V=S,V=为独异点，为独异点，T T是是V V的子独异点当且仅当的子独异点当且

6、仅当T T 对对o o运算封运算封闭，且闭，且e e T T 实例：实例：Z,+,是是的子半群，的子半群，是是的子独异点，的子独异点，Z,+不是不是的子独异点的子独异点.6.1半群与群8现在学习的是第8页，共37页半群与独异点的积代数半群与独异点的积代数定义 设 V1=，V2=是半群(或独异点)，令S=S1S2，定义 S 上的 运算如下：,S，=称 为 V1 和 V2 的 积半群（直积），记作 V1V2.若 V1=和 V2=是独异点，则 V1V2 =S1S2,也是独异点,称为独异点的 积独异点(直积).6.1半群与群9现在学习的是第9页，共37页半群和独异点的同态半群和独异点的同态定义定义 (

7、1)设设V1=，V2=是半群，是半群，：S1S2.若对任意的若对任意的 x,yS1有有 (x y)=(x)(y)则称则称 为半群为半群 V1 到到 V2 的的同态映射同态映射，简称，简称 同态同态.(2)设设V1=，V2=是独异点，是独异点，:S1S2.若对任意的若对任意的 x,yS1有有 (x y)=(x)(y)且且 (e1)=e2,则称则称 为独异点为独异点 V1 到到 V2 的的同态映射同态映射，简称，简称 同态同态.6.1半群与群10现在学习的是第10页，共37页同态的实例同态的实例例例2 设半群设半群 V1=，独异点，独异点 V2=.其中其中 为矩为矩阵乘法，阵乘法，e 为为 2 阶

8、单位矩阵阶单位矩阵,令令 ：SS,是半群是半群 V1 的自同态的自同态,不是独异点不是独异点 V2 的自同态，因为它没有将的自同态，因为它没有将 V2 的单位元的单位元映到映到 V2 的单位元的单位元.0|,0aSa dRd00000aad6.1半群与群11现在学习的是第11页，共37页群的定义与实例群的定义与实例定义 设是代数系统，为二元运算.如果 运算是可结合的，存在幺元 eG，并且对 G 中的任何元素 x 都有 x1G，则称 G 为 群.群的实例(1),是群；,不是群.(2)是群，而不是群.(3)是群，为对称差运算.(4)是群.Zn=0,1,n1，为模 n 加.6.1半群与群12现在学习

9、的是第12页，共37页Klein四元群四元群设G=e,a,b,c，G上的运算由下表给出，称为 Klein四元群 e a b c e a b c e a b c a e c b b c e a c b a e 运算表特征：e为G中的幺元 对称性-运算可交换 主对角线元素都是幺元 -每个元素是自己的逆元 a,b,c 中任两个元素运算 都等于第三个元素.6.1半群与群13现在学习的是第13页，共37页群中的术语群中的术语若群若群 G 是有穷集，则称是有穷集，则称 G 是是有限群有限群，否则称为，否则称为无无限群限群.群群 G 的基数（元素个数）称为群的基数（元素个数）称为群G的的 阶阶有限群有限群

10、G 的阶记作的阶记作|G|.若群若群G中的二元运算是可交换的，则称中的二元运算是可交换的，则称G为为交换群交换群 或或 阿贝尔阿贝尔(Abel)群群.6.1半群与群14现在学习的是第14页，共37页实例实例 和和 是无限群是无限群 是有限群，也是是有限群，也是 n 阶群阶群 Klein四元群四元群 G=e,a,b,c是是 4 阶群阶群 上述群都是交换群上述群都是交换群 n 阶阶(n2)实可逆矩阵集合关于矩阵乘法构成的实可逆矩阵集合关于矩阵乘法构成的群是非交换群群是非交换群.6.1半群与群15现在学习的是第15页，共37页群中的术语（续）群中的术语（续）实例实例 在在中有中有 2 3=(2 1)

11、3=13=1 1 1=0 在在 中有中有 (2)3=23=2+2+2=6 定义定义 设设G是群，是群，xG，nZ，则，则 x 的的 n 次幂次幂 xn 定义为定义为 Znnnmxnxxnexmnn 0,)(00116.1半群与群16现在学习的是第16页，共37页设设G是群，是群，xG，使得等式，使得等式 xk=e 成立的最小正成立的最小正整数整数 k 称为称为 x 的的阶（或周期）阶（或周期），记作，记作|x|=k，称，称 x为为 k 阶元阶元.若不存在这样的正整数若不存在这样的正整数 k，则称，则称 x 为为无限阶元无限阶元.群中的术语（续）群中的术语（续）在在中，中，2 和和 4 是是 3

12、 阶元，阶元，3 是是 2 阶元，阶元，1 和和 5 是是 6 阶元，阶元，0 是是 1 阶元阶元 在在中，中，0 是是 1 阶元，其它整数的阶都不存在阶元，其它整数的阶都不存在.注：在任何群中，幺元的阶都是注：在任何群中，幺元的阶都是16.1半群与群17现在学习的是第17页，共37页群的性质群的性质-幂运算规则幂运算规则定理1 设 G 为群,则 G 中的幂运算满足：(1)xG，(x1)1=x.(2)x,yG，(xy)1=y1x1.(3)xG，xnxm=xn+m，n,mZ.(4)xG，(xn)m=xnm，n,mZ.注意 (xy)n=(xy)(xy)(xy),是 n 个xy 运算，G为 交换群，

13、才有(xy)n=xnyn.1112111121.).(xxxxxxxnnn6.1半群与群18现在学习的是第18页，共37页群的性质群的性质-群方程存在唯一解群方程存在唯一解定理2 G为群，a,bG，方程 ax=b 和 ya=b 在G中有解且仅有惟一解.a1b 是 ax=b的解.ba1 是 ya=b 的唯一解.例 设 G=，其中为对称差.群方程a X=，Y a,b=b的解 X=a1=a=a，Y=ba,b1=ba,b=a 6.1半群与群19现在学习的是第19页，共37页群的性质群的性质-消去律消去律定理6.3 G为群，则G适合消去律，即a,b,cG 有(1)若ab=ac，则 b=c.(2)若ba=

14、ca，则 b=c.例、设G=a1,a2,an 是 n 阶群，令 aiG=ai aj|j=1,2,n 证明：aiG=G.证：由群中运算的封闭性有 aiGG.假设aiGG，即|aiG|n.必有aj,akG使得 ai aj=ai ak（jk）由消去律得 aj=ak,与|G|=n 矛盾.6.1半群与群20现在学习的是第20页，共37页群的性质群的性质-运算表排列规则运算表排列规则定理定理4 4 设设 G 为有限群，则为有限群，则 G 的运算表中每行每列的运算表中每行每列都是都是 G 中元素的一个置换，且不同的行（或列）中元素的一个置换，且不同的行（或列）的置换都不相同的置换都不相同.理解：理解：G G

15、的运算表的每一行里，的运算表的每一行里，G G的每个元素都出现一次，且只出现的每个元素都出现一次，且只出现一次；不同行的元素排列顺序不同。一次；不同行的元素排列顺序不同。注意：必要条件，用于判断一个运算表不是群注意：必要条件，用于判断一个运算表不是群.a b c d a b c d b c d a b a c d c d b a d b a c a b c d a b c d a b c d c d a b b c d a d a b c 6.1半群与群21现在学习的是第21页，共37页子群的定义子群的定义定义 设 G 是群，H 是 G 的非空子集，如果 H 关于 G 中的运算构成群，则称 H

16、 是 G 的子群,记作 HG.若 H 是 G 的子群，且 HG，则称 H 是 G 的真子群，记作 HG.实例 nZ（n是自然数）是整数加群 的子群.当 n1 时,nZ 是 Z 的真子群.对任何群 G 都存在子群.G 和 e 都是 G 的子群，称为 G 的平凡子群.22现在学习的是第22页，共37页子群判定定理子群判定定理判定定理判定定理 设设 G 为群，为群，H 是是 G 的非空子集的非空子集.H 是是 G 的子群当且的子群当且仅当仅当 x,yH 有有 xy 1H.证明证明 H 为为 G 的子群的步骤：的子群的步骤：通过给出通过给出 H 中的元素说明中的元素说明 H 是是 G 的非空子集的非空

17、子集 任取任取 x,y属于属于 H，证明，证明 xy-1属于属于H6.1半群与群23现在学习的是第23页，共37页重要子群重要子群生成子群：生成子群：设设G G为群，为群，aGaG，令，令H=aH=ak k|kZ kZ，则，则H H是是G G的子群，称为的子群，称为由由a a 生成的生成的子群，记作子群，记作.证：首先由证：首先由a a 知道知道.任取任取 a am m,a,al l，则，则a am m(a(al l)1 1=a=am m a a l l=a=am m l l根据判定定理可知根据判定定理可知G.G.6.1半群与群24现在学习的是第24页，共37页实例实例 整数加群，-由 2 生

18、成的子群是 =2k|kZ =2Z 模 6 加群 中-由 2 生成的子群 =0,2,4 Klein四元群 G=e,a,b,c 的所有生成子群是：-=e,-=e,a,=e,b,=e,c.25现在学习的是第25页，共37页群群G的中心的中心C 设设 G 为群为群,令令 C=a|aG xG(ax=xa)，则，则 C是是 G 的子群，称为的子群，称为 G 的的中心中心.证：证：eC.C是是 G 的非空子集的非空子集.任取任取 a,bC，证明，证明 ab 1与与 G 中所有的元素都可交换中所有的元素都可交换.xG，有，有 (ab 1)x=ab 1x=ab 1(x 1)1=a(x 1b)1 =a(bx 1)

19、1=a(xb 1)=(ax)b 1 =(xa)b 1=x(ab 1)由判定定理可知由判定定理可知 CG.重要子群（续）重要子群（续）6.1半群与群26现在学习的是第26页，共37页循环群的定义循环群的定义定义 设G是群，若存在 aG 使得 G=ak|kZ 则称G是循环群，记作 G=，称 a 为 G 的生成元.实例 整数加群 G=模 6 加群 G=6.1半群与群27现在学习的是第27页，共37页循环群的分类循环群的分类设设 循环群循环群 G=，根据生成元，根据生成元 a 的阶可以分的阶可以分成两类：成两类：n 阶循环群和无限循环群阶循环群和无限循环群.设设 G=是循环群，若是循环群，若a 是是

20、n 阶元，则阶元，则 G=a0=e,a1,a2,an 1 那么那么|G|=n，称，称 G 为为 n 阶循环群阶循环群.若若 a 是无限阶元，则是无限阶元，则 G=a0=e,a1,a2,这时称这时称 G 为为无限循环群无限循环群.28现在学习的是第28页，共37页循环群的生成元循环群的生成元定理设 G=是循环群.(1)若G是无限循环群，则 G 只有 a 和 a1 两个生成元.(2)若 G 是 n 阶循环群，则 ar 是 G 的生成元当且仅当 r 是小于等于 n 且与 n 互质的正整数.29现在学习的是第29页，共37页(1)设设G=e,a,a11是是12阶循环群，则小于或等于阶循环群，则小于或等

21、于12且与且与12互素的数是互素的数是 1,5,7,11,由定理可知由定理可知 a，a5，a7和和 a11是是 G 的生成元的生成元.(2)设设G=是模是模9的整数加群，则小于或等于的整数加群，则小于或等于 9且且与与 9 互素的数是互素的数是 1,2,4,5,7,8.根据定理，根据定理，G的生的生成元是成元是 1,2,4,5,7 和和 8.(3)设设 G=3Z=3z|zZ,G上的运算是普通加法上的运算是普通加法.那么那么G只有两个生成元：只有两个生成元：3 和和 3.生成元的实例生成元的实例30现在学习的是第30页，共37页循环群的子群循环群的子群定理：设G=是循环群.(1)设G=是循环群，

22、则 G 的子群仍是循环群.(2)若G=是无限循环群，则 G 的子群除e以外都是无限循环群.(3)若G=是 n 阶循环群，则对 n 的每个正因子d，G 恰好含有一个d 阶子群.31现在学习的是第31页，共37页(1)G=是1无限循环群，对于自然数mN，1 的 m 次幂是 m，m 生成的子群是 mZ，mN.即 =0 =0Z =mz|zZ =mZ，m0 (2)G=是12阶循环群.12的正因子是1,2,3,4,6 和12，因此G 的子群是（an/d）：1 阶子群=0，2 阶子群 =0,6 3 阶子群=0,4,8，4 阶子群 =0,3,6,9 6 阶子群=0,2,4,6,8,10，12 阶子群=Z12

23、子群的实例子群的实例32现在学习的是第32页，共37页n元置换的定义元置换的定义定义 设 S=1,2,n,S上的双射函数:SS 称为 S上的 n元置换.一般将 n 元置换记为 例如 S=1,2,3,4,5,则 都是 5元置换.12(1)(2)()nn1234512345,354125413233现在学习的是第33页，共37页k 阶轮换与对换阶轮换与对换定义定义 设设是是 S=1,2,n上的上的 n 元置换元置换.若若(i1)=i2,(i2)=i3,(ik 1)=ik,(ik)=i1且保持且保持 S 中的其他元素不变，则称中的其他元素不变，则称为为 S上的上的 k 次轮次轮换换，记作，记作(i1

24、i2ik).若若 k=2，称，称为为S上的上的对换对换.例如例如 5元置换元置换 分别是分别是 5阶和阶和 2 阶轮换阶轮换=(1 2 3 4 5),=(1 3),其中其中 也叫做对换也叫做对换1234512345,234513214534现在学习的是第34页，共37页n元置换分解为轮换元置换分解为轮换设设 S=1,2,n，对于任何，对于任何 S 上的上的 n 元置换元置换，一定存一定存在着一个有限序列在着一个有限序列 i1,i2,ik,k1,（可以取（可以取i1=1）使得使得(i1)=i2,(i2)=i3,(ik 1)=ik,(ik)=i1，令，令1=(i1 i2 ik)，它是从，它是从中分

25、解出来的第一个轮换中分解出来的第一个轮换.根据函根据函数复合定义可将数复合定义可将写作写作1，其中，其中作用于作用于 S i1,i2,ik上的元素上的元素.继续对继续对进行类进行类似的分解似的分解.由于由于S 中只有中只有 n 个元素个元素,经过有限步以经过有限步以后，必得到后，必得到的轮换分解式的轮换分解式=1 2 t 35现在学习的是第35页，共37页分解实例分解实例例例 设设 S=1,2,8,从从中分解出来的第一个轮换式中分解出来的第一个轮换式(1 5 2 3 6)；第二个；第二个轮换为轮换为(4)；第三个轮换为；第三个轮换为(7 8).的轮换表示式的轮换表示式 =(1 5 2 3 6)(4)(7 8)=(1 5 2 3 6)(7 8)用同样的方法可以得到用同样的方法可以得到的分解式的分解式 =(1 8 3 4 2)(5 6 7)注意：在轮换分解式中，注意：在轮换分解式中，1 阶轮换可以省略阶轮换可以省略.1 2 3 4 5 6 7 81 2 3 4 5 6 7 8,5 3 6 4 2 1 8 78 1 4 2 6 7 5 336现在学习的是第36页，共37页n元置换的乘法与求逆元置换的乘法与求逆37现在学习的是第37页，共37页