《离散数学第六章群论》由会员分享,可在线阅读,更多相关《离散数学第六章群论(33页珍藏版)》请在金锄头文库上搜索。
1、第第6章章 群论群论 第六章第六章 群论群论 6.1 半群与单元半群半群与单元半群 6.2 群群 拢张伐硒睡赎裁驰睁呈污獭里讳絮抒捞癣夏饰极浊遮胁祷讯蝴厚践桌违措离散数学第六章群论离散数学第六章群论第第6章章 群论群论 群群在在代代码码的的查查错错、改改错错的的研研究究,自自动动机机理理论论等等方面都有应用。方面都有应用。 名举魔阎冠崔杉酬蔼窃采了服甜烤凸安整勾师梁综掩浮掖睫轮挺镊酪浸幅离散数学第六章群论离散数学第六章群论第第6章章 群论群论 6.1 半群与单元半群半群与单元半群 半半群群与与群群都都是是具具有有一一个个二二元元运运算算的的代代数数系系统统,群群是是半半群群的的特特殊殊例例子子
2、。事事实实上上,群群是是历历史史上上最最早早研研究究的的代代数数系系统统,它它比比半半群群复复杂杂一一些些,而而半半群群概概念念是是在在群群的的理理论论发发展展之之后后才才引引进进的的。逻辑关系见图逻辑关系见图6.1.1。外恐缚丑希教蛾月弊炬扰爱庸赦忽布坚档长搞挫金疤惶财衙武韭斯所四囚离散数学第六章群论离散数学第六章群论第第6章章 群论群论 图图 6.1.1 群群半群半群玉商精彭烈畴玛茸香妆拽鲜馏辆挟趟长宵昼淑恃给满晴碱洼剥朱泊巴识盎离散数学第六章群论离散数学第六章群论第第6章章 群论群论 一、半群一、半群1、半群的有关定义、半群的有关定义 定定义义6.1 设设(S, )是是代代数数系系统统,
3、 是是二二元元运运算算,如果如果 运算满足结合律,则称它为半群。运算满足结合律,则称它为半群。 换换言言之之,a, b, cS, 若若 是是S上上的的封封闭闭运运算算且且满足满足(a b) c=a (b c),则),则(S, )是半群。是半群。 许多代数系统都是半群。例如:许多代数系统都是半群。例如:(I,+),(I,), ( E), ) ,( E), ), (N4,+ 4) , (N4,4)均是半群。均是半群。修倘踪趣卜磐因窒烩褒困俩滁早捅采镍错共袜糕顷挛粘挂伏福溢岗剑舔剪离散数学第六章群论离散数学第六章群论第第6章章 群论群论 再如,设再如,设X是有限字母表,是有限字母表,X+是是 X 中
4、的字母中的字母串,串, X *= X +,其中,其中是不含字母的空串,是不含字母的空串,运算运算 是字母串的是字母串的“并置并置”运算,则运算,则( X *, )是是半群。如半群。如Com X * ,puter X *,经经 运算后,运算后,得得Computer仍是字母串。仍是字母串。 订著童供掷箱棉荣变拇砖竿裁溶忆挚库饶蘑篓邯濒拱赫揍住惊鸳酉夷期苟离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定理定理6.1 一个半群一个半群(S, ),如果它有一个子代,如果它有一个子代数数 (M, ) ,则此子代数也是一个半群。,则此子代数也是一个半群。 定义定义6.2 一个半群一个半群(S,
5、)的子代数的子代数 (M, )也也是半群,称为是半群,称为(S, )的子半群。的子半群。肃攘偷邑吗个夸馋学您督获瞳捅锐螺陇耙坝惑燃殖沿弘糟遥窍蹬跨熔锣字离散数学第六章群论离散数学第六章群论第第6章章 群论群论 一个半群一个半群(S, )中的元素中的元素a ,可定义它的幂:,可定义它的幂: a1=a , a2=a a , ,an+1=an a 即即半半群群中中的的元元素素有有时时可可用用某某些些元元素素的的幂幂表表示示出出来。来。 因为半群满足结合律,所以可得到因为半群满足结合律,所以可得到 a m a n=a m + n, (a n) m=a m n。 如果有如果有a2=a,则称,则称a为半群
6、中的为半群中的等幂元素等幂元素。克届狈尝荷阵怖辊触森旺只显模胆呸译碾阉溺牲网钉坝狐貉知纳盲跋艇硬离散数学第六章群论离散数学第六章群论第第6章章 群论群论 2、一些特殊半群。一些特殊半群。 (1) 可交换半群:可交换半群: 如果半群如果半群(S, )中二元运算中二元运算 是是可交换的,则称可交换的,则称(S, ) 是可交换半群。是可交换半群。 例如:例如:(I,+),(I,), ( E), ) ,( E), ) (N4,+ 4) , (N4,4)均是可交换半群。但均是可交换半群。但( X *, )不是可交换半群。不是可交换半群。(2) 循环半群:循环半群:一个半群一个半群(S, )如果它的每个元
7、如果它的每个元素均为素均为S内某一固定元素内某一固定元素 a 的某一方幂,则此半的某一方幂,则此半群称为由群称为由 a 所生成的循环半群,元素所生成的循环半群,元素 a 称为此半称为此半群的生成元素。群的生成元素。曰昂焉策捧溺袱寸披伟孝髓户茧立爸丛濒板填载拽如杆院株间爵歉骤岛寡离散数学第六章群论离散数学第六章群论第第6章章 群论群论 (3) 单元半群(或单位半群):单元半群(或单位半群):有单位元素有单位元素e的的半群半群(S, ),常记为,常记为(S, ,e)。定理定理6.2:一个循环半群一定是可交换半群。一个循环半群一定是可交换半群。定理定理6.3:一个半群内的任一元素一个半群内的任一元素
8、 a 和它所有的幂和它所有的幂组成一个由组成一个由 a 所生成的循环子半群。所生成的循环子半群。空侣桃约羡襟姜碑漾忽浊阐盂倒者历悸泻吊称献狐豆布烫我捆生南漏枯精离散数学第六章群论离散数学第六章群论第第6章章 群论群论 例:下面半群都是单位半群例:下面半群都是单位半群 (I,+)单位元素单位元素是是0,可,可记为记为(I,+,0); (I,)单位元素单位元素是是1 ,可,可记为记为(I,1) ; ( X *, )单位元素单位元素是是(空串空串) , 可可记为记为( X *, ,) ; ( E), )单位元素单位元素是是 ,可记为,可记为( E), , ) ; ( E), )单位元素单位元素是是E
9、 ,可记为,可记为( E), ,E) 。 (N4,+4)单位元素单位元素是是0 ,可,可记为记为(N4,+4, 0 ) (N4, 4)单位元素单位元素是是1 ,可,可记为记为(N4, 4 , 1 )峪舌岸添锅憾臂队荫野捕号懂奸晰溯咎多从菱怒拍庐饮成院捆拎使抿扎步离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定理定理6.5 一个单位半群一个单位半群(S, ),如果存在一个,如果存在一个子代数子代数 (M, ) ,且其单位元,且其单位元 e M,则则 (M, ) 也是一个单位半群。也是一个单位半群。 定义定义6.5 一个单位半群一个单位半群(S, ),如果存在一个,如果存在一个子代数子
10、代数 (M, ) ,且其单位元,且其单位元 e M,则则 (M, ) 也是一个单位半群,称为也是一个单位半群,称为(S, )的子单位半群的子单位半群 。概泣昏谤因雌法熊起盘郁鸥宛诬痢隘府伍栓苞嘛试侄仙孙脑歹咐揖故澳鸟离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定义定义6.5 :一个单位半群一个单位半群(S, )如果由它的一个如果由它的一个元素元素a 所生成,则称为由所生成,则称为由 a 所生成的循环单位半所生成的循环单位半群,元素群,元素 a 称为此单位半群的生成元素。称为此单位半群的生成元素。定理定理6.6 :一个循环单位半群是一个可换单位半一个循环单位半群是一个可换单位半群。
11、群。寅筏饯瘴沿唉庚恍部召盟步杖阅颜炸检塔辨催预萄盈大扮距瘤科贼歹嫡屎离散数学第六章群论离散数学第六章群论第第6章章 群论群论 6.2 群群一、群与群的同构一、群与群的同构1、群的有关定义、群的有关定义 定义定义6.7 如果代数系统如果代数系统(G, )满足满足 (1) (G, )为一半群;为一半群; (2) (G, )中有中有单位元单位元e; (3) (G, )中每一元素中每一元素aG都有逆元都有逆元 a-1 则称代数系统则称代数系统(G, )为群。为群。冠抑廖辆辣萨梭栅焕丝鄙菇跋榜弊呜扯叼换内柏叶裂诅教曝烘红菊弃米侯离散数学第六章群论离散数学第六章群论第第6章章 群论群论 例如:例如:(I,
12、+)是群,因是群,因 a I 都有逆元都有逆元 - a ; (N4,+4)是群是群,0的逆元是的逆元是0,1的逆元是的逆元是3, 2的逆元是的逆元是2。(I,), ( X *, ),( E), ) ,( E), ), (N4, 4)均不是群。均不是群。定义定义6.8 一个群一个群(G, )如果满足交换律,则称为如果满足交换律,则称为可交换群或称阿贝尔群。可交换群或称阿贝尔群。例如:群例如:群(I,+), (N4,+4)都是阿贝尔群。都是阿贝尔群。坤姨通微效继啤倚牡淖安剂卓娩讨慈激衅恃哺陶未离姑甩梁测械绦门趣桓离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定义定义6.9 一个群一个群
13、(G, )如果它的一个子代数如果它的一个子代数(H, )也是一个群,则称也是一个群,则称(H, )是是(G, )的一个群。的一个群。定义定义6.10 一个群一个群(G, )如果它的元素个数是有限如果它的元素个数是有限的,则称为有限群。如果它的元素个数是无限的,的,则称为有限群。如果它的元素个数是无限的,则称为无限群。则称为无限群。定义定义6.11 一个群一个群(G, )的阶记为的阶记为|G|,如果一个群,如果一个群是有限群,则阶为元素个数,如果一个群为无限群,是有限群,则阶为元素个数,如果一个群为无限群,则阶为无穷大。则阶为无穷大。挣狄吠瑶逗姨阔詹传边雕聚纲睡边舌貉貉摄反干措新匈羌幌棕穿乓甲厢
14、窒离散数学第六章群论离散数学第六章群论第第6章章 群论群论 2、群的一些性质、群的一些性质(1) 群满足消去律群满足消去律(2) 一个阶大于一个阶大于1的群一定没有零元的群一定没有零元(3)除了单位元外,一个群一定没有等幂元素。)除了单位元外,一个群一定没有等幂元素。(4)一个群)一个群(G, )的方程:的方程:a x = b 与与 y a = b,其,其 中中 a, b G 在群内有唯一解。在群内有唯一解。却孵胰牌疹裸椭向烯歧刊受腊撰蕾烈论钝饿桶汪瓢镀禁退镶创刺耪免寥捉离散数学第六章群论离散数学第六章群论第第6章章 群论群论 3、群的第二个定义、群的第二个定义 定义定义6.12 一个代数系统
15、一个代数系统(G, )若满足下列条件,若满足下列条件,则称为群则称为群 (1)满足结合律;)满足结合律; (2)方程:)方程:a x = b 与与 y a = b,其,其 中中 a, b G 在在G内有唯一解。内有唯一解。亏宫啦腆厩跋切垄孝窥墟拦你迟隶炭臃胃抖圃亡解岗樱惩尤堡倪狞茹唱陆离散数学第六章群论离散数学第六章群论第第6章章 群论群论 4、群的同构、群的同构定义定义6.13 设设(G, )与与(H,*)是两个群,若存在一是两个群,若存在一个函数个函数 g : G H,使得对每个,使得对每个a, b G ,有,有 g (a b) = g (a ) * g (b ) 则称则称g是从是从 (G
16、, ) 到到 ( H, * ) 的群同态。的群同态。 若若 g : G H 是一一对应的,则称是一一对应的,则称 g 是从是从 (G, ) 到到 ( H, * ) 的群同构。的群同构。声腿唤吕够怂驮狸激鲸泛汕兰朝沙帕可淫棱卿护怜给事驴签分趁豢座妇蹋离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定理定理6.9 :设设(G, )与与(H,*)是两个群,有一个函数是两个群,有一个函数 g : G H 使其群同态,则有使其群同态,则有 g (e G) = e H g (a-1) = g (a)-1定理定理6.9 :设设(G, )是一个群,若是一个群,若(G, )与与(H,*)满满同态或同构
17、,则同态或同构,则(H,*)也构成群。也构成群。土簿释聚淋邪形废涉私仁鹅鞠扫特柠饺荔依她贮收西澎敌就绕澜泛直鸭择离散数学第六章群论离散数学第六章群论第第6章章 群论群论 二、变换群二、变换群 定义定义6.14 集合集合S上的若干个变换与复合运算若构上的若干个变换与复合运算若构成群,则此种群叫变换群。成群,则此种群叫变换群。定理定理6.9 :任一个群均与一个变换群同构。任一个群均与一个变换群同构。叼亚尘山层据县鄙逐沾工进矮素拘哆搽柳钞皖姚丽遍馁挂庚俱嫂悯利嗓赵离散数学第六章群论离散数学第六章群论第第6章章 群论群论 三、有限群三、有限群群表:群表:对有限群,可用一张组合表将其运算表示出对有限群,
18、可用一张组合表将其运算表示出来,称为群表。来,称为群表。 设有限群设有限群(G,* ),其中,其中G=1,2,3,这个,这个群可用表群可用表6.3所示的群表定义所示的群表定义*123112322313312表表6.3柒渠东卷船桨壬佣权攫话剂读敛丸凤刁玖费连啡佣咎忙鞍驹拴号糠鸯税擦离散数学第六章群论离散数学第六章群论第第6章章 群论群论 群表的特性:群表的特性: (1) 总存在一行(或一列)其元素与横线上(或竖总存在一行(或一列)其元素与横线上(或竖 线左边)的元素一样。线左边)的元素一样。(2) 每一行(列)内元素各不相同,且任两行(列)每一行(列)内元素各不相同,且任两行(列) 对应元素间也
19、均不相同,故群表每一行(列)是对应元素间也均不相同,故群表每一行(列)是 G中元素的一个全排列。中元素的一个全排列。(3) 若群是可换群,则群表是对称的。若群是可换群,则群表是对称的。招辨秤暴啥黍花走颐分枯单赛助溯垄揭或伶资椿运榔辰含战淄栈君氮仟俐离散数学第六章群论离散数学第六章群论第第6章章 群论群论 由群表可知,一个阶为由群表可知,一个阶为n的有限群的有限群(G,* ),它,它的每个元素对应的每个元素对应G的一个置换,就是说:的一个置换,就是说: 设有有限群设有有限群(G,* ),其中,其中G=a1, a2, , an,则存在一个函数则存在一个函数:由这些置换组成一个集合由这些置换组成一个
20、集合则集合则集合P与其复合运算构成一个群,即一个置换群。与其复合运算构成一个群,即一个置换群。陷蔫汐涵夸卢外鹊愚苏坍瘪洽乃润樱遇碎永女异怨鳖妻诀各鲤卉冗惰琼男离散数学第六章群论离散数学第六章群论第第6章章 群论群论 如表如表6.3中中G的每个元素对应的置换所组成的集合为的每个元素对应的置换所组成的集合为存在一个函数存在一个函数:集合集合P与其复合运算构成一个置换群。与其复合运算构成一个置换群。定理定理6.15 :每个有限群均与一个置换群同构。每个有限群均与一个置换群同构。焉诡梆皆翟缩戈需埋斥庶龋去洞惰匹蝗邻清裳青像灯李仪煎惋疡械伏爽棵离散数学第六章群论离散数学第六章群论第第6章章 群论群论 因
21、此,当有限群因此,当有限群(G,* ) 分别为分别为1,2,3阶群时,阶群时,*运运算都只有一个定义方式(即不计元素记号的不同算都只有一个定义方式(即不计元素记号的不同,只只有一张定义有一张定义*运算的运算表,分别如表运算的运算表,分别如表6.4、6.5和和6.3所示),于是可以说:所示),于是可以说:1,2,3阶的群都只有一个。阶的群都只有一个。*111表表6.4*12112223表表6.5宗入境峰缸待疯佣衫剧骂妓侵忻胚阉蝗蚁馅逻怪寞恬衰近搅屋园桨鸽款刚离散数学第六章群论离散数学第六章群论第第6章章 群论群论 4阶群的群表不只一个阶群的群表不只一个*123411234221433342144
22、312*123411234224133314244321娃惕优立裔聂急湾予闭枷溯你囤泪磺钧困恩耳睦猫耽野廖咱陷垢枝贡革炔离散数学第六章群论离散数学第六章群论第第6章章 群论群论 *123411234223413341244123阔牧芜泣迁饼百南选扶线儒童畅数歪碳刷醚块曾般雀姑沛酱抒梨秒融莆慧离散数学第六章群论离散数学第六章群论第第6章章 群论群论 四、循环群四、循环群定义定义6.16: 设设(G, )是一个群,是一个群,aG ,则令:,则令: a0=e , a j+1=a j a ( j 0),), a -j=(a -1) j ( j 0) 由定义可得到由定义可得到 a m a n=a m +
23、 n, (a n) m=a m n群中元素方幂的定义群中元素方幂的定义玖哄孕拙绕嘴肾次藻砒裳雹峪你与甘善竟孜隶威裙淘簇十孙彰诛几妖缀令离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定义定义6.17:若一个群若一个群(G, )的每一个元素均是它的某的每一个元素均是它的某一个固定元素一个固定元素 a 的某次方幂,则称的某次方幂,则称(G, )是由是由 a 生成生成的循环群,而的循环群,而a 称为称为(G, )的生成元素。记为的生成元素。记为定义定义6.18:一个由一个由 a 生成的循环群生成的循环群(G, ),若存在,若存在m,使得,使得 am =e 的最小正整数的最小正整数 m 称为
24、称为 a 的周期,若不的周期,若不存在这样的一个存在这样的一个m,则称,则称 a 的周期为无限。的周期为无限。氛付乞们恍忿蚤剂养辩衬墓裂斟怂菜脐帛襟膘苫派房栽瘴鼎贯添柄啸蚤惋离散数学第六章群论离散数学第六章群论第第6章章 群论群论 例例1:整数加群:整数加群 (I,+) 是一个生成周期为无限的是一个生成周期为无限的循环群。循环群。 1或(或(l)为其生成元。)为其生成元。例例2:剩余类加群:剩余类加群 (Nm,+m)是一个生成周期为是一个生成周期为m的循环群。的循环群。 1 为其生成元。为其生成元。定理定理6.16 :设有一个由设有一个由 a 生成的循环群生成的循环群 (G, ),则有,则有(
25、1)若若a 的周期无限,则的周期无限,则(G, ) 与与(I,+)同构。同构。(2) 若若a 的周期为的周期为m,则,则(G, ) 与与(Nm,+m)同构。同构。铃钞摊苞苑错穴倡瞧铣箕蛤补疵昌芋其兹戈殃鲁丁泅作裔烈仔潘欧呈厕喻离散数学第六章群论离散数学第六章群论第第6章章 群论群论 四、子群四、子群定理定理6.17: 一个群一个群(G, )及由它的一个子集及由它的一个子集H组成组成一个代数一个代数(H, ),该代数构成一个,该代数构成一个 (G, )的子群的子群的充要条件是:的充要条件是: a, b H,则,则 a b H a H,则,则 a -1 H定理定理6.18: 设设(G, )是一个群
26、,而是一个群,而 (H, )是是(G, )的子群,则的子群,则(H, )的单位元素即是的单位元素即是(G, )的单位的单位元素;元素; (H, )内内 a 的逆元素即是的逆元素即是(G, )内内 a 的逆元的逆元素。素。痉韩耻宇啤酮殉化涵门怕英芬札似晚挤柿沈叶宪贮惺壤著恩迪傀礁兆迢弹离散数学第六章群论离散数学第六章群论第第6章章 群论群论 定理定理6.19: 设设(G, )是一个群,是一个群,G的子集的子集H组成一组成一个代数个代数(H, ) 构成构成 (G, )的子群的充要条件是:的子群的充要条件是: 若若 a, b H,则,则 a b-1 H定理定理6.20: 设设(G, )是一个群,是一个群,G的一个有限子集的一个有限子集H组成一个代数组成一个代数(H, ) 构成构成 (G, )的子群的充要的子群的充要条件是:条件是: 若若 a, b H,则,则 a b H忽腺霹钠汉酋亏告迂辫诡薯艳芭占聂捻挑剩稀篱属韵热辈爽颐帐果误宅曼离散数学第六章群论离散数学第六章群论