第十七章 群 北京大学计算机系离散数学讲义(ppt版).ppt

第十七章 群 群的定义与性质 群的定义 群的术语 群的性质 群的性质（续） 群的性质（续） 群的性质（续） 群的性质（续） 关于群性质的证明题 关于群性质的证明题（续） 关于群性质的证明题（续） 关于群性质的证明题（续） 关于群性质的证明题（续） 关于群性质的证明题（续） 作业 复习要点: 群的定义 证明代数系统是群有哪些方法 群的性质及其应用 书面作业： 习题17.2, 17.9, 17.10, 17.11 * * 主要内容 群的定义与性质 子群 循环群 变换群和置换群 群的分解 正规子群和商群 群的同态与同构 群的直积 一、群的定义 定义与实例 等价定义 相关术语 二、群的性质 幂运算规则 群方程有唯一解 消去律 运算表的置换性质 元素的阶的性质 三、习题分析 可以将群看成代数系统 G, o,-1, e 实例：Z,+, Zn,(, Klein四元群，置换群. 等价定义：G,o, o可结合，若存在右单位元e，且每个元素a相对于e存在右逆元a’，则G是群。 证明：证e为左单位元。(a(G, e = e (e为右单位元) ( e(aa’) = (aa’) ( (ea)a’ = aa’ ( ea = a (右乘a’的右逆元) 证a’为a的左逆元，即a = (a’)’ = a’’ a’’ = ea’’ = (aa’)a’’ = a(a’a’’) = ae = a 平凡群只含单位元的群 {e} 交换群Abel群 有限群与无限群 群G的阶G的基数，有限群记为|G| 元素a的n次幂 元素a的阶 |a|使得ak=e成立的最小正整数k说明：有限群的元素都是有限阶，为群的阶的因子； 反之，元素都是有限阶的群不一定是有限群. 幂运算规则 (a-1)-1=a (ab)-1=b-1a-1 anam=an+m (an)m=anm 若G为Abel群，则(ab)n=anbn 说明：证明用到逆元的定义和唯一性； 等式3和4的证明使用归纳法并加以讨论 等式2可以推广到有限个元素之积.方程ax=b和ya=b在群G中有解且有唯一解. 证: a-1b是ax=b的解. 假设c为解，则 c = ec = (a-1a)c =a-1(ac) = a-1b 说明：此性质可以用于定义群. 设G是半群，如果对任意a,b(G，方程ax=b和ya=b在G中有解，则G为群. 证：找右单位元和任意元素的右逆元. 任取b(G,方程bx=b的解记为e. (a(G,yb=a 的解记为c,即cb = a. ae = (cb)e = c(be) = cb =a e为右单位元。 (a(G, 方程ax=e 有解，得到a的右逆元. 消去律 ab= ac (b=c, ba = ca (b=a 说明：消去律也可以定义群 设G是有限半群，且不含零元.若G中成立消去律，则G是群. 证：设G={a1=e,a2,…,an}，任取ai(G， aiG ={aiaj |j=1,2,…,n} 由封闭性, aiG(G, 假设|aiG|n, 则存在j,k使得aiaj=aiak, 根据消去律，aj=ak, 矛盾. 所以aiG=G. 任取ai,aj, ai,aj(G ( aj(aiG ( 方程aix=aj有解 同理，方程yai=aj有解.G是群. 注：Z5,(不是群，因为有0；Z+,(也不是群，无限. 有限群G的运算表中每行、每列都是G的置换. aG=G 和Ga=G 说明 运算表的行列构成置换的不一定是群，反例： 思考： 3元集上的不同的二元运算有多少个？ 3元集上二元运算表有多少个，使得每行每列能够构成置换？ 3元集上有多少个不同的运算表代表群？ 3元集上同构的群有多少个？ G为群，a(G, 且|a|=r, 则 （1）ak =e ( r | k （2）|a|=|a-1| （3）若|G| = n, 则r(n. 证 （1）充分性. ak = arl =(ar)l=el = e 必要性. k=rl+i, l(Z, i({0,1,…,r-1} ( e = ak = arl+i = ai ( i=0 ( r | k （2）(a-1)r=e ( |a-1| 存在, 令|a-1|=t, 则t|r. r|t. （3）假设rn, 令G’={e,a,a2, …, ar-1}, 则G’中元素两两不同，否则与|a|=r矛盾. 从而|G’|n，与G’(G矛盾. 关于阶的几个重要结果 证明留作思考题. 证明元素的阶相等或求元素的