离散数学-群ppt课件.ppt

《离散数学-群ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-群ppt课件.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学课程讲义课件课程讲义课件大连海事大学计算机科学与技术学院计算机科学与技术学院u本章及第本章及第8章讨论一些具体的代数系统：章讨论一些具体的代数系统： 群、环、域、格与布尔代数群、环、域、格与布尔代数等内容。等内容。u具有具有一个一个二元运算的二元运算的群；群；u具有具有两个两个二元运算的二元运算的环环和和域；域；u具有具有两个两个二元运算的二元运算的格；格；u具有具有两个两个二元运算和二元运算和一个一个一元运算的一元运算的布尔代数布尔代数；u我们只讲一下我们只讲一下 群群 。7.1 7.1 半群与独异点半群与独异点1. 1. 半群与独异点半群与独异点定义定义7.1.17.1.1

2、 给定给定 ， * *是是S S上的二元运算，上的二元运算，（1 1）若）若* *是是可结合可结合的，则称的，则称 为为半群半群。 注：注：半群就是由集合及其上定义的半群就是由集合及其上定义的一个可结合的二元运算一个可结合的二元运算组成的组成的代数系统。代数系统。（2 2）若）若* *是可结合的是可结合的且具有幺元且具有幺元e e，则称，则称 为为含幺半含幺半群群或或独异点独异点，并记作，并记作 .例例7.1.1 7.1.1 N+，N 是是半群半群，也是，也是含幺半群含幺半群。例例7.1.3 7.1.3 是半群是半群, , 幺元是幺元是， 也是半群也是半群, , 幺元是幺元是S,S,都是含幺半

3、群都是含幺半群 P196P196习题习题-2 -2 x(yz)=x(y*a*z)=x*a*(y*a*z)= (xy)z=(x*a*y)z=(x*a*y)*a*z ( 由由*可结合的）可结合的）2. 2. 可交换半群可交换半群定义定义7.1.27.1.2 若若 是半群，是半群， 若运算若运算*是可交换的，是可交换的，则称则称为为可交换半群可交换半群。例例 ，是是半群半群，且是，且是可交换半群可交换半群。 例例 设设S S为非空集合，则为非空集合，则(S(S) )，, ,(S(S) )，（1 1）运算）运算“”和和“”可结合可结合，是，是半群半群；（2 2）运算）运算“”存在存在幺元幺元S S，“

4、”存在存在幺元幺元，是，是含幺半含幺半群群；（3 3）运算运算“”和和“”可交换可交换，是，是可交换半群可交换半群； 故故(S(S) )，和和(S(S) )，是是可交换含幺半群可交换含幺半群。3 3 子半群子半群( (定义定义7.1.3)7.1.3) l 设设是半群，且非空是半群，且非空H S. 若运算若运算*在在H上上是是封闭封闭的，的，则则也是一个半群，称也是一个半群，称是是的的子半群子半群。l 设设是含幺半群，且是含幺半群，且H S. 若运算若运算*在在H上封闭上封闭且且e H，则称，则称是是的的子含幺半群子含幺半群(子独异点子独异点)。例例 是半群，是半群，I R，且，且在集合在集合I

5、上封闭，则上封闭，则是是的的子半群子半群。例例 是一个半群，是一个半群，*运算的运算表如左下：运算的运算表如左下： d是是幺元幺元； , , 是其是其含幺子半群含幺子半群； , 是其是其子半群子半群； 不是其子半群不是其子半群。*abcdadcaabbbbbcccccdabcd定理定理7.1.1 设设是一个半群，若是一个半群，若S是个有限集，则必有是个有限集，则必有a S，使得，使得 a*a=a.定理定理7.1.2 设设是一个含幺半群，则关于运算是一个含幺半群，则关于运算*的运的运算表中算表中任何两行或两列都是不相同的任何两行或两列都是不相同的。 定理定理7.1.3 设设是一个可交换含幺半群，

6、是一个可交换含幺半群，H 是是S的的等幂等幂元素所构成的集合元素所构成的集合，则，则是是的的子含幺半群子含幺半群。证证 由幺元由幺元e S且是等幂的，所以且是等幂的，所以e H；设设a,b H, 因因H中元素都是等幂的，故中元素都是等幂的，故a*a=a, b*b=b,可得可得 (a*b)*(a*b)=(a*b)*(b*a)=a*(b*b)*a=a*b*a=a*a*b=a*b说明说明a*b也是等幂的，故也是等幂的，故a*b H，即，即*对于对于H是封闭的是封闭的。故故 是是的子含幺半群。的子含幺半群。4 循环半群循环半群定义定义7.1.4 给定给定半群半群 (或或含幺半群含幺半群 ),若存在若存

7、在gS，对，对任意任意aS，都有，都有nN，使得，使得a=gn，则称该半群为则称该半群为循环半群循环半群（或（或循环含幺半群循环含幺半群）。）。称称g为循环半群的为循环半群的生成元生成元，亦称元素，亦称元素g生成了循环半群。生成了循环半群。例例 代数系统代数系统是个是个循环半群，循环半群，它的它的生成元生成元是是1.1. 例例7.1.8 P172 循环半群证明循环半群证明定理定理7.1.4 任何一个任何一个循环半群循环半群（或含幺循环半群）都是（或含幺循环半群）都是可可交换半群交换半群（或含幺可交换半群）。（或含幺可交换半群）。定理定理7.1.5 设设是一个半群，是一个半群，H 是是S中任一元

8、素的幂所中任一元素的幂所构成的集合构成的集合，则，则是是的的子半群子半群，且是个，且是个循环子循环子 半群半群。 (该定理的证明自己练习该定理的证明自己练习)5 半群同态半群同态定义定义7.1.5 设设U=和和V=是两个半群，是两个半群，和和*都是都是二元运算，函数二元运算，函数f：XY，若对任意的，若对任意的x,yX，有：，有： f(xy)=f(x)*f(y) (运算的象运算的象=象的运算）象的运算）则称则称f是代数系统是代数系统U到到V的一个的一个半群同态映射半群同态映射（简称（简称同态同态） l 与代数系统与代数系统 同态同态 概念完全一样。概念完全一样。定理定理7.1.6 设设f为从代

9、数系统为从代数系统和和满同态映射，满同态映射，若若是半群（或含幺半群，可交换半群），则是半群（或含幺半群，可交换半群），则也是半群（或含幺半群，可交换半群）。也是半群（或含幺半群，可交换半群）。由满同态单方向地保持性质由满同态单方向地保持性质 可直接得到结论。可直接得到结论。1.1.群的基本概念群的基本概念 l群的定义群的定义 设设G 是一个代数系统，若二元运算是一个代数系统，若二元运算* *满足满足（1 1）可结合性）可结合性 （结合律）（结合律） 半群半群（2 2）存在幺元）存在幺元 （单位元素）（单位元素） 含幺半群含幺半群（3 3）G G中每个元素都存在逆元中每个元素都存在逆元. .

10、群群 则称则称 代数系统代数系统G 是是群群。注注：群是半群和含幺半群的特例。：群是半群和含幺半群的特例。l有限群有限群 设设是一个群，若集合是一个群，若集合G是是无限集无限集, 则称则称 是无限群。否则称为是无限群。否则称为有限群有限群，|G|称为称为群的阶群的阶。l阿贝尔群阿贝尔群 设设是一个群，若是一个群，若*是可交换的是可交换的, 则称则称 群群为为可交换群可交换群或或阿贝尔群阿贝尔群。 例例 不是不是群群；而；而 是是群群。 例例 7.2.1 是是阿贝尔群。阿贝尔群。例例 7.2.2 G=，验证，验证是是群群。可验证运算可验证运算*是可结合的，是可结合的， 是幺元，是幺元，且每个元素

11、都可逆，且每个元素都可逆，*可交换，可交换，故是阿贝尔群，故是阿贝尔群，|G|=4, 4阶群。阶群。*2.群的基本性质群的基本性质 定理定理 群中群中无零元无零元；定理定理 设设 是一个群，对于任意是一个群，对于任意a,bG，方程，方程a*x=b和和y*a=b在在G中都有中都有唯一解唯一解。定理定理 设设 是是半群半群（或满足（或满足结合律结合律），对任意），对任意 a,bG，若方程，若方程a*x=b和和y*a=b在在G中中有解有解， 则则是群是群。定理定理 设设 是一个群，对于任意的是一个群，对于任意的a,b,cG，有，有 (a*b=a*c) b=c , (b*a=c*a) b=c ( 消去

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

13、b*a 故故是阿贝尔群。是阿贝尔群。例例 7.2.4 P175: 自己练习自己练习例例 P198习题习题-17 是有限可交换含幺半群，且对任意的是有限可交换含幺半群，且对任意的a,b,cS，若若a*b=a*c b=c. 证证是阿贝尔群。是阿贝尔群。证证 只需证只需证S中每个元素都可逆。中每个元素都可逆。因因是有限可交换含幺半群，所以是有限可交换含幺半群，所以S是有限集。是有限集。不妨令不妨令S=a1,a2,an, 对任意对任意aS，有，有 a*a1, a*a2 , , a*an S,又由对又由对任意的任意的ai , ajS，若，若a*ai=a*aj, 可推得可推得ai=aj. 所以所以a*ai

14、互不相同，即互不相同，即 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.61 循环群循环群定义定义 设设是群，若是群，若G中的每个元素都是中的每个元素都是G中某个固定中某个固定元素元素a的整数幂，则称群的整数幂，则称群为为循环群循环群。称群是由称群是由a生成的生成的, 记为记为 G=

15、(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:设循环

16、群设循环群G=(a)，若，若a的所有不同的整数幂中的所有不同的整数幂中有两个是相等的，则有两个是相等的，则G中存在最小的正整数中存在最小的正整数n使使得得an=e，且有，且有 G=(a)=a0,a1,a2,an-1 定义定义 设群设群中任一元素中任一元素a，若存在使，若存在使an=e的最小的正的最小的正整数整数n，则称，则称a的的周期周期(或或阶阶)为为n。 若正整数若正整数n不存在，则称不存在，则称a的的周期周期（或（或阶阶）是）是无限无限的。的。注注 周期周期的概念是对群中任的概念是对群中任一元素一元素来定义的，任意群其来定义的，任意群其幺幺元的周期一定是元的周期一定是1。 对循环群，有时

17、称其对循环群，有时称其生成元的周期生成元的周期为为循环群的周期循环群的周期。例例 整数加群整数加群, 其幺元其幺元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的周期

18、为的周期为m，则，则 (a)与与同构；同构；注注 循环群只有两种，循环群只有两种，生成元的周期无限时，它与生成元的周期无限时，它与整数加群整数加群 代数相等；代数相等；生成元的周期为生成元的周期为m时，它与模为时，它与模为m的的剩余加群剩余加群 代数相等。代数相等。例例 定理定理 任何一个任何一个循环群循环群必是必是阿贝尔群阿贝尔群。证证 设设G=(a)，则，则G中任一元素都可写成中任一元素都可写成a的幂的形式。的幂的形式。 对任意对任意x,yG，x*y=am*an=am+n =an*am=y*x *可交换，故是可交换，故是阿贝尔群。阿贝尔群。群中元素周期的性质：群中元素周期的性质：定理定理

19、设设a是群是群一个元素，若一个元素，若a的周期为的周期为n, 则则 am = e n | m （ n整除整除m）定理定理 群中元素群中元素a和它的和它的逆元逆元a-1必具有必具有相同的周期相同的周期。定理定理 在有限群在有限群中，每个元素都有一个中，每个元素都有一个有限周期有限周期，且，且每个元素的周期每个元素的周期不超过该群的阶不超过该群的阶|G|。2 变换群变换群定义定义 集合集合A上的一些上的一些双变换的集合双变换的集合与与复合运算复合运算构成的群构成的群叫做叫做变换群变换群。 （A的双变换指的双变换指 A上的双射函数）上的双射函数）Cayley定理定理 任一个群与一个变换群任一个群与一

20、个变换群同构同构。* 对群的研究归结为对变换群的研究对群的研究归结为对变换群的研究3 置换群置换群定义定义 含含n个元素的有限集个元素的有限集A上的一些上的一些置换的集合置换的集合与与复合运复合运算算构成的群叫做构成的群叫做置换群置换群。A的的所有置换的集合所有置换的集合与与复合运算复合运算构成的群叫做叫做构成的群叫做叫做A的的n次对称群次对称群。（A的置换指的置换指 有限集合有限集合A上的双射函数）上的双射函数）定理定理 任一个有限群与一个置换群任一个有限群与一个置换群同构同构。* 对有限群的研究归结为对置换群的研究对有限群的研究归结为对置换群的研究7.4 7.4 子群子群 1 子群定义子群

21、定义 定义定义 设设是一个群，是一个群，H是是G的非空子集，若的非空子集，若也是一个群也是一个群，则称，则称是是的的子群子群。简称简称H是是G的子群的子群。注注 和和都是都是的子群，称为的子群，称为平凡子群平凡子群， 其他的子群称为其他的子群称为非平凡子群（或真子群）非平凡子群（或真子群）。判断判断H是子群的步骤：是子群的步骤：（1）封闭性；（）封闭性；（2）含幺元；（）含幺元；（3）每个元素均可逆；）每个元素均可逆；2 判断子群的方法判断子群的方法 定理定理 群群的非空子集的非空子集H构成构成G的子群的子群的充要条件：的充要条件：（1）封闭性：）封闭性：a,bH a*bH ;（2）可逆性）可

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

23、x)*b= (x*a)*b= = x*(a*b) 故故 a*bC; 可逆性可逆性：若：若aC, 证证a-1C。明显。明显eC，对任，对任xG， a-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中的任意元素，则：中的任意元素，则： 把集合把集合

24、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