《离散数学第六章ppt课件》由会员分享，可在线阅读，更多相关《离散数学第六章ppt课件（49页珍藏版）》请在金锄头文库上搜索。
1、.,第六章 几个典型的代数系统,6.1 半群与群 6.1.1 半群与独异点 6.1.2 群的定义与性质 6.1.3 子群 6.1.4 陪集与拉格朗日定理 6.1.5 正规子群与商群 6.1.6 循环群和置换群 6.2 环与域 6.2.1 环的定义与性质 6.2.2 整环与域 6.3 格与布尔代数,.,6.1 半群与群,半群、可交换半群和独异点 定义6.1 设V=是代数系统, 为二元运算,如果是可结合的, 则称V为半群 如果半群V=中的二元运算含有幺元, 则称V为含幺半群, 也可叫做独异点. 定义6.2 如果半群V=中的二元运算是可交换的, 则称V为可交换半群. 注: 为了强调幺元的存在, 有时
2、将独异点记为,6.1.1 半群与独异点,.,例6.1 是半群 ,都是半群和独异点，其中+表示普通加法,幺元是0, 是半群和独异点,其中表示矩阵乘法,矩阵乘法的幺元是n阶单位矩阵E.记作 是半群和独异点,其中表示集合的对称差运算, 其幺元是, 记作 是半群和独异点, 其中Zn =0,1,n-1, 表示模n加法, 模n加法的幺元是0. 其中: 为可交换半群.,6.1.1 半群与独异点,.,6.1.1 半群与独异点,例6.2 判断下述论断正确与否, 在相应的括号中键入“Y”或“N”. (1) 在实数集R上定义二元运算*为：对于任意的a,bR, a*b=a+b+ab (a) 是一个代数系统；( ) (
3、b) 是一个半群； ( ) (c) 是一个独异点。( ) (2) 在实数集R上定义二元运算为, 对任意 a,bR, ab=|a|b (其中表示数学的乘法运算) (a) 是一个代数系统； ( ) (b) 是一个半群； ( ) (c) 是一个独异点。 ( ),N,Y,Y,Y,Y,Y,.,子半群和子独异点 定义: 半群的子代数叫做子半群, 即: 如果V=是半群, 就是V的子半群,需要满足如下两个条件: T是S的非空子集; T对V中的运算是封闭的. 定义: 独异点的子代数叫做子独异点, 对独异点V=, 构成V的子独异点,需要满足如下条件: T是S的非空子集; T要对V中的运算封闭; eT.,6.1.1
4、 半群与独异点,.,群的定义 定义6.3 设是代数系统,为二元运算.如果是可结合的,存在幺元eG,并且G中的任意元素x,都有x-1G, 则称G是群. 例6.3 ,都是群; 是群, 其中表示集合的对称差运算, 任意元素的逆元是其自身; 是群,其中Zn=0,1,n-1, 表示模n加法, 0的逆元是0,非0元素的逆元是n-x.,6.1.2 群的定义与性质,.,6.1.2 群的定义与性质,e为G中的幺元, 是可交换的. 任何G中的元素与自己运算的结果都等于e. 在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素. 一般称这个群为Klein四元群.,例6.4 设Ge,a,b,c, 为G上的二
5、元运算, 它由以下运算表给出, 不难证明G是一个群.,.,6.1.2 群的定义与性质,群的术语 (1) 若群G中的二元运算是可交换的, 则称群G为交换群, 也叫做阿贝尔(Abel)群 例 , ,都是群, 也是阿贝尔(Abel)群; 是群, 也是阿贝尔(Abel)群; 是群, 也是阿贝尔(Abel)群. Klein四元群也是阿贝尔群 (2) 若群G中有无限多个元素, 则称G为无限群, 否则称为有限群, 只含幺元的群为平凡群. 例如, , 都是无限群. 是有限群. Klein四元群也是有限群.,.,6.1.2 群的定义与性质,群的术语 (3) 群的阶: 对于有限群G,G中的元素个数也叫做G的阶,
6、记作|G|. 例如: 是有限群, 其阶是n; Klein四元群也是有限群, 其阶是4. (4) xn定义: x0=e, xn+1=xnx, x-n=(x-1)n (5) 元素x的阶: 设G是群,xG,使得xke成立的最小的正整数k叫做x的阶(或周期).如果不存在正整数k,使xke, 则称x是无限阶元. 注: 对有限阶的元素x, 通常将它的阶记为|x|. 在任何群G中幺元e的阶都是1,6.1.2 群的定义与性质,群的术语 例.在Klein四元群中,|a|=?,|b|=?,|c|=?,|e|=?,返回,.,6.1.2 群的定义与性质,群的性质 定理6.1 设G为群, 则G中的幂运算满足(群中元素的
7、幂) (1) xG, (x-1)-1x (2) x,yG, (xy)-1y-1x-1 (3) xG, xnxmxn+m (4) xG, (xn)mxnm (5) 若G为交换群, 则(ab)n=anbn,.,定理6.1的证明,(1) aG,(a-1)-1a (a-1)-1是a-1的逆元，a也是a-1的逆元。 （或者：a-1是a的逆元，a也是a-1的逆元。） 根据逆元的唯一性， (a-1)-1a。 (2) a,bG，(ab)-1b-1a-1 (b-1a-1)(ab)b-1(a-1a)bb-1be (ab)(b-1a-1)a(bb-1)a-1aa-1e 故 b-1a-1是 ab 的逆元。 根据逆元的
8、唯一性等式得证。,6.1.2 群的定义与性质,群的性质 定理6.2 G为群, a,bG, 则 (1) G有唯一的单位元, G中每个元素恰有一个逆元; (2) G适合消去律, 即对任意a,b,cG 有 若abac, 则bc; 若baca, 则bc; (3) 单位元是G的唯一的幂等元素;,.,6.1.3 子群,子群的定义 定义6.4 设群, H是G的非空子集. 如果H关于G中的运算*构成群, 则称H为G的子群, 记作HG. 若H是G的子群, 且HG, 则称H是G的真子群. 例如: 在群中, 取2Z2x|xZ, 则2Z关于加法构成的子群. 同样, 0也是的子群. 注意: 类似于子代数, 任何群G都存
9、在子群, G和e是G的平凡子群.,.,6.1.3 子群,子群的判断方法 判定定理1 设G为群, H是G的非空子集, H是G的子群当且仅当: (1) a,bH都有abH; (2) aH有a-1H. 判定定理2 设G为群, H是G的非空子集, 则H是G的子群当且仅当a,bH都有ab-1H. 判定定理3 设G为群, H是G的非空子集. 若H是有穷集, 则H是G的子群当且仅当a,bH都有abH .,.,6.1.3 子群,子群的判断方法 例6.5 设G为群, 对任何xG, 令Hxk|kZ, 即x的所有幂的集合, 则H是G的子群, 称为由元素x生成的子群, 记作. 证明:G 由x可知不为空. 任取H中的元
10、素xm,xl,都有 xm(xl)-1xmx-lxm-lH 根据判定定理二可知G.,.,6.1.3 子群,例如, 群中由2生成的子群包含2的各次幂, 20=0, 21=2, 22=22=4, 23=222=0, 所以 =0,2,4. 对于Klein四元群G=e,a,b,c来说, 由它的每个元素生成的子群是 =e, =e,a, =e,b, =e,c,.,6.1.3 子群,群的中心 设G为群,令C是与G中所有的元素都可交换的元素构成的集合,即 Ca|aGxG(ax=xa), 称C为群G的中心.,6.1.4 陪集与拉格朗日定理,陪集的定义 定义6.4 H是G的子群, aG, 令Ha=ha|hH 称Ha
11、是子群H在G中的右陪集, 称a为Ha的代表元素. 例6.6 设G=e,a,b,c是Klein四元群, H=e,a是G的子群, 那么H的所有右陪集是: He=e,a=H Ha=e,a=H Hb=b,c Hc=c,b 注: 类似地可以定义左陪集.,6.1.4 陪集与拉格朗日定理,陪集的定义 例6.6 设A=1,2,3, f1,f2,f6是A上的双射函数, 其中:f1=, f2=, f3=, f4=, f5=, f6=, 令G=f1,f2,f3,f4,f5,f6, 则G关于复合(本题为右复合)运算构成了群, G的子群H=f1,f2, 求H的全部右陪集. H f1=f1f1, f2f1=f1,f2=H
12、 H f2=f1f2, f2f2=f1,f2=H H f3=f1f3, f2f3=f3,f5 H f4=f1f4, f2f4=f4,f6 H f5=f1f5, f2f5=f5,f3 H f6=f1f6, f2f6=f6,f4,6.1.4 陪集与拉格朗日定理,陪集的性质 定理6.3(定理10.7-10.9): 设H是G的子群, 则 He=H aG有aHa a,bG, aHbab-1HHa=Hb 在G上定义关系R:a,bG, Rab-1H, 则R是G上的等价关系, 且aR=Ha. aG, HHa(指势相等) 注意: 左陪集的性质与此类似.,6.1.4 陪集与拉格朗日定理,Lagrange定理 对G
13、的子群H来说, H的左陪集和右陪集一般是不相等的,但左右陪集的个数是相等的.因此将左右陪集数统称为H在G中的陪集数, 也叫做H在G中的指数, 记为G:H. 定理6.4(定理10.10): 设G是有限群, H是G的子群, 则|G|=|H|G:H. 推论1 设G是n阶群, 则aG, |a|是n的因子, 且an=e. 推论2 对阶为素数的群G, 必存在aG使得G=.,6.1.5 正规子群和商群,正规子群 定义6.5 设H是G的子群, 如果aG都有Ha=aH, 则称H是G的正规子群, 记作 H G. 定义6.6 设G是群, N是G的正规子群, 令G/N是N在G中的全体左陪集(或右陪集)构成的集合, 即
14、G/N=Ng|gG 在G/N上定义二元运算如下: Na,NbG/N, NaNb=Nab G/N关于构成了群, 称为G的商群.,.,6.1.6 循环群和置换群,循环群 定义6.7 在群G中, 如果存在aG使得 G=ak|kZ 则称G为循环群, 记作G=,称a为G的生成元. 循环群必定是阿贝尔群, 但阿贝尔群不一定是循环群. 证明: 设是一个循环群, 它的生成元是a,那么,对于任意x,yG, 必有r,sZ, 使得 x=as,y=at, 而且x*y=as*at=as+t=at*as=y*x 由此可见是一个阿贝尔群. 例如,是一个循环群, 其生成元是1或-1.,6.1.6 循环群和置换群,循环群 在循
15、环群G=中, 生成元a的阶与群G的阶是一样的. 如果a是有限阶元, |a|n, 则称G为n阶循环群. 如果a是无限阶元, 则称G为无限阶循环群. 例如: 是无限阶循环群; 是n阶循环群. 注意:(1) 对无限阶循环群G=, G的生成元是a和a-1; (2) 对n阶循环群G=,G的生成元是at当且仅当t与n互素, 如12阶循环群中, 与12互素的数有1、5、7、11. 那么G的生成元有a1=a、a5、a7、a11. (3) N阶循环群G=, 对于n的每个正因子d, G恰好有一个d阶子群H=.,6.1.6 循环群和置换群,n元置换 定义6.7 设S1,2,n,S上的任何双射函数:S S构成了S上n
16、个元素的置换,称为n元置换. 例如, S=1,2,3, 令:SS, 且有: (1)=2, (2)=3, (3)=1 则将1,2,3分别置换成2,3,1, 此置换常被记为 = 采用这种记法, 一般的n元置换可 记为,.,n元置换 n个不同元素有n!种排列的方法, 所以, S上有n!个置换. 例如,上有3!=6种不同的置换,即,6.1.6 循环群和置换群,.,n元置换 对于n元置换也可以用不交的轮换之积来表示. =(a1a2am), mn 那么的映射关系是 a1a2,a2a3,am-1am,ama1, 而其他的元素都有aa. 称为m次轮换. 这样, 任何n元置换都可表成不交的轮换之积.,6.1.6 循环群和置换群,.,n元置换 例如, 是1,2,6上的置换,且 = 那么的映射关系是 1 6, 25, 33, 44, 52, 61. 去掉3和4这两个保持不变的元素,可得 1 6, 61, 25, 52 所以 =(1 6) (2 5)
