离散数学群ppt课件.ppt

《离散数学群ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学群ppt课件.ppt（28页珍藏版）》请在三一办公上搜索。

1、第7章 群、环和域,离散数学课程讲义课件,大连海事大学计算机科学与技术学院,本章及第8章讨论一些具体的代数系统：群、环、域、格与布尔代数等内容。具有一个二元运算的群；具有两个二元运算的环和域；具有两个二元运算的格；具有两个二元运算和一个一元运算的布尔代数；我们只讲一下 群。,7.1 半群与独异点1.半群与独异点,定义7.1.1 给定，*是S上的二元运算，（1）若*是可结合的，则称为半群。注：半群就是由集合及其上定义的一个可结合的二元运算组成的代数系统。（2）若*是可结合的且具有幺元e，则称为含幺半群或独异点，并记作.,例7.1.1，是半群，也是含幺半群。例7.1.3 是半群,幺元是，也是半群,

2、幺元是S,都是含幺半群 P196习题-2 x(yz)=x(y*a*z)=x*a*(y*a*z)=(xy)z=(x*a*y)z=(x*a*y)*a*z(由*可结合的）,2.可交换半群定义7.1.2 若 是半群，若运算*是可交换的，则称为可交换半群。例，是半群，且是可交换半群。,例 设S为非空集合，则(S)，,(S)，（1）运算“”和“”可结合，是半群；（2）运算“”存在幺元S，“”存在幺元，是含幺半群；（3）运算“”和“”可交换，是可交换半群；故(S)，和(S)，是可交换含幺半群。,3 子半群(定义7.1.3)设是半群，且非空HS.若运算*在H上是封闭的，则也是一个半群，称是的子半群。设是含幺半

3、群，且HS.若运算*在H上封闭且eH，则称是的子含幺半群(子独异点)。例 是半群，I R，且在集合I上封闭，则是的子半群。,例 是一个半群，*运算的运算表如左下：d是幺元；,是其含幺子半群；,是其子半群；不是其子半群。,定理7.1.1 设是一个半群，若S是个有限集，则必有aS，使得 a*a=a.定理7.1.2 设是一个含幺半群，则关于运算*的运算表中任何两行或两列都是不相同的。定理7.1.3 设是一个可交换含幺半群，H 是S的等幂元素所构成的集合，则是的子含幺半群。证 由幺元eS且是等幂的，所以eH；设a,bH,因H中元素都是等幂的，故a*a=a,b*b=b,可得(a*b)*(a*b)=(a*

4、b)*(b*a)=a*(b*b)*a=a*b*a=a*a*b=a*b说明a*b也是等幂的，故a*bH，即*对于H是封闭的。故 是的子含幺半群。,4 循环半群定义7.1.4 给定半群(或含幺半群),若存在gS，对任意aS，都有nN，使得a=gn，则称该半群为循环半群（或循环含幺半群）。称g为循环半群的生成元，亦称元素g生成了循环半群。例 代数系统是个循环半群，它的生成元是1.例7.1.8 P172 循环半群证明,定理7.1.4 任何一个循环半群（或含幺循环半群）都是可交换半群（或含幺可交换半群）。定理7.1.5 设是一个半群，H 是S中任一元素的幂所构成的集合，则是的子半群，且是个循环子 半群。

5、(该定理的证明自己练习),5 半群同态定义7.1.5 设U=和V=是两个半群，和*都是二元运算，函数f：XY，若对任意的x,yX，有：f(xy)=f(x)*f(y)(运算的象=象的运算）则称f是代数系统U到V的一个半群同态映射（简称同态）与代数系统 同态 概念完全一样。定理7.1.6 设f为从代数系统和满同态映射，若是半群（或含幺半群，可交换半群），则也是半群（或含幺半群，可交换半群）。由满同态单方向地保持性质 可直接得到结论。,7.2 群的定义及基本性质,1.群的基本概念 群的定义 设是一个代数系统，若二元运算*满足（1）可结合性（结合律）半群（2）存在幺元（单位元素）含幺半群（3）G中每个

6、元素都存在逆元.群 则称 代数系统是群。注：群是半群和含幺半群的特例。有限群 设是一个群，若集合G是无限集,则称 是无限群。否则称为有限群，|G|称为群的阶。阿贝尔群 设是一个群，若*是可交换的,则称 群为可交换群或阿贝尔群。,例 不是群；而 是群。例 7.2.1 是阿贝尔群。例 7.2.2 G=，验证是群。可验证运算*是可结合的，是幺元，且每个元素都可逆，*可交换，故是阿贝尔群，|G|=4,4阶群。,2.群的基本性质 定理 群中无零元；定理 设 是一个群，对于任意a,bG，方程a*x=b和y*a=b在G中都有唯一解。定理 设 是半群（或满足结合律），对任意 a,bG，若方程a*x=b和y*a

7、=b在G中有解，则是群。定理 设 是一个群，对于任意的a,b,cG，有(a*b=a*c)b=c,(b*a=c*a)b=c(消去律）定理 设 是一个群，对于任意a,bG，有(a*b)-1=b-1*a-1(运算的逆=逆的运算的交换）,定理 群的运算表中每一行或每一列都是G中元素的双变换。G中每个元素在每一行必出现且仅出现一次。例 P198习题-18 若群中每个元素的逆是其自身，证该群是阿贝尔群。证 只需证运算*可交换。对任意的a,bG,a*b=a-1*b-1=(b*a)-1=b*a 故是阿贝尔群。例 7.2.4 P175:自己练习,例 P198习题-17 是有限可交换含幺半群，且对任意的a,b,c

8、S，若a*b=a*c b=c.证是阿贝尔群。证 只需证S中每个元素都可逆。因是有限可交换含幺半群，所以S是有限集。不妨令S=a1,a2,an,对任意aS，有 a*a1,a*a2,a*anS,又由对任意的ai,ajS，若a*ai=a*aj,可推得ai=aj.所以a*ai互不相同，即 a*a1,a*a2,a*an=S又S中有幺元e,故必存在某个akS,使 a*ak=e.又*可交换，a*ak=ak*a=e,即a-1=ak,由a任意，每个元素都可逆，即是群，又因可交换，故是阿贝尔群。,3 群同态的例子参见P177 例7.2.6,7.3 循环群与变换群,1 循环群定义 设是群，若G中的每个元素都是G中某

9、个固定元素a的整数幂，则称群为循环群。称群是由a生成的,记为 G=(a).元素a称为群G的生成元。例1 整数加群是循环群：1是其生成元1m=m,1-m=-m-1也是其生成元。故 I=(1)=(-1).例2 G=,5-2,5-1,1,5,25,，则是群，是循环群 故 G=（5）.,讨论一下循环群的结构：命题1:设循环群G=(a)，若a的所有不同的整数幂都互不相等，则G中含有无限多个元素，且有 G=(a)=,a-2,a-1,a0,a1,a2,命题2:设循环群G=(a)，若a的所有不同的整数幂中有两个是相等的，则G中存在最小的正整数n使得an=e，且有 G=(a)=a0,a1,a2,an-1,定义

10、设群中任一元素a，若存在使an=e的最小的正整数n，则称a的周期(或阶)为n。若正整数n不存在，则称a的周期（或阶）是无限的。注 周期的概念是对群中任一元素来定义的，任意群其幺元的周期一定是1。对循环群，有时称其生成元的周期为循环群的周期。例 整数加群,其幺元0的周期是1,其他元素周期无限.其为循环群，生成元是1,故该循环群的周期为无限。例 是群,且是周期为m的循环群(剩余类加法群)Zm=0,1,2,m-1,i+m j=(i+j)(mod m);i,j Zm 证明：见P179例7.3.3的证明,定理 设循环群G=(a),若a为无限周期，则(a)与同构；若a的周期为m，则(a)与同构；注 循环群

11、只有两种，生成元的周期无限时，它与整数加群 代数相等；生成元的周期为m时，它与模为m的剩余加群 代数相等。例 定理 任何一个循环群必是阿贝尔群。证 设G=(a)，则G中任一元素都可写成a的幂的形式。对任意x,yG，x*y=am*an=am+n=an*am=y*x*可交换，故是阿贝尔群。,群中元素周期的性质：定理 设a是群一个元素，若a的周期为n,则 am=e n|m（n整除m）定理 群中元素a和它的逆元a-1必具有相同的周期。定理 在有限群中，每个元素都有一个有限周期，且每个元素的周期不超过该群的阶|G|。,2 变换群定义 集合A上的一些双变换的集合与复合运算构成的群叫做变换群。（A的双变换指

12、 A上的双射函数）Cayley定理 任一个群与一个变换群同构。*对群的研究归结为对变换群的研究3 置换群定义 含n个元素的有限集A上的一些置换的集合与复合运算构成的群叫做置换群。A的所有置换的集合与复合运算构成的群叫做叫做A的n次对称群。（A的置换指 有限集合A上的双射函数）定理 任一个有限群与一个置换群同构。*对有限群的研究归结为对置换群的研究,7.4 子群 1 子群定义 定义 设是一个群，H是G的非空子集，若也是一个群，则称是的子群。简称H是G的子群。注 和都是的子群，称为平凡子群，其他的子群称为非平凡子群（或真子群）。判断H是子群的步骤：（1）封闭性；（2）含幺元；（3）每个元素均可逆；

13、,2 判断子群的方法 定理 群的非空子集H构成G的子群的充要条件：（1）封闭性：a,bH a*bH;（2）可逆性:aH a-1H.定理 群的非空子集H构成G的子群的充要条件：若a,bH,则a*b-1H.特别地，对于有限群，定理 若是有限群的子代数，则 是有限群的子群。,例P189例7.4.5 设是一个群，令C=aG|a*x=x*a,xG,证明是的一个 子群。证 显然CG,下面证封闭性和可逆性。封闭性：若a,bC,证a*bC。对任意xG，(a*b)*x=a*(b*x)=a*(x*b)=(a*x)*b=(x*a)*b=x*(a*b)故 a*bC;可逆性：若aC,证a-1C。明显eC，对任xG，a-

14、1*x=a-1*x*a*a-1=a-1*(x*a)*a-1=a-1*(a*x)*a-1=(a-1*a)*x*a-1=x*a-1 故 a-1C;因此C是G的子群。（习题-25与之类似）,3子群的陪集与拉格朗日定理(P185)1）陪集定义（定义 7.4.2）设是群的子群，a是G中的任意元素，则：把集合aH=a*h|hH称为G中的子群H的左陪集；而把集合=aH|aG称G关于子群H的左商集。把集合Ha=h*a|hH称为G中的子群H的右陪集；而把集合=Ha|aG称G关于子群H的右商集。2）陪集性质 定理7.4.4 设是群的子群，则：若abH,则aH=bH；若aHb,则Ha=Hb；,定理7.4.5 设是群的子群，则H的左/右商集：=aH|aG 或=Ha|aG 恰为群G的一个划分。,3）拉格朗日定理定理 设G是含n个元素的有限群，H为G中含m个元素的子群，即|G|=n，|H|=m，则m|n(m是n的因子）。推论1：任何质数阶的群不可能有非平凡子群。推论2：设是n阶有限群，则对于任意的aG，a的周期必是n的因子且必有 an=e。,例 P189 例7.4.7 习题七：2、5、6、8、17、18、19、25、26,