离散数学第六章.ppt

《离散数学第六章.ppt》由会员分享，可在线阅读，更多相关《离散数学第六章.ppt（55页珍藏版）》请在三一文库上搜索。

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) 是一个代数系统；( ) (b) 是一个半群； (

3、 ) (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的阶, 记作|G|. 例如: 是有限群, 其阶是n

6、; 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中的幂运算满足(群中元素的幂) (1) xG, (x-1)-1x (2)

7、 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 的逆元。 根据逆元的唯一性等式得证。,6.1.2 群的定义与性质,群的

8、性质 定理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都存在子群, G和e是G的平凡子群.,6.1.3 子群,子

9、群的判断方法 判定定理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中的元素xm,xl,都有 xm(xl)-1xmx-lxm-lH 根据

10、判定定理二可知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是子群H在G中的右陪集, 称a为Ha的代表元素. 例6.6 设G=e,

11、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 H f2=f1f2, f2f2=f1,f2=H H f3=f1f3,

12、 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的子群H来说, H的左陪集和右陪集一般是不相等的,但左右陪集的个数是相

13、等的.因此将左右陪集数统称为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中的全体左陪集(或右陪集)构成的集合, 即G/N=Ng|gG 在G/N上定义二元运算如下: Na,NbG/N,

14、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 循环群和置换群,循环群 在循环群G=中, 生成元a的阶与群G的阶是一样的. 如果a是有限阶元, |a|

15、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个元素的置换,称为n元置换. 例如, S=1,2,3, 令:SS, 且有:

16、 (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上的置换,且 = 那么的映射关系是

17、 1 6, 25, 33, 44, 52, 61. 去掉3和4这两个保持不变的元素,可得 1 6, 61, 25, 52 所以 =(1 6) (2 5) (3) (4),6.1.6 循环群和置换群,n元置换 又如, 也是1,2,6上的置换, 且 = 则有 =(1 4 3 2 5) (6) 为使表达式简洁,可以去掉1次轮换，则有 =(1 6) (2 5) = (1 4 3 2 5),6.1.6 循环群和置换群,n元置换 用轮换法表示 1,2,3 上的置换 可记为： 1= (1), 2= (12), 3= (13), 4= (23), 5= (123), 6=(132) 轮换可以进一步表示成对换之

18、积, 如6=(13)(12) 奇置换: 能表示成奇数个对换之积的置换; 偶置换: 能表示成偶数个对换之积的置换.,6.1.6 循环群和置换群,n元对称群、n元置换群 设S=1,2,n, S上的n!个置换构成集合Sn, 其中恒等置换Is=(1)Sn. 在Sn上规定二元运算, 对于任意n元置换, Sn, 表示与的复合(乘法). 显然也是S上的n元置换, 所以, Sn对运算是封闭的, 且是可结合的. 任取Sn中的置换, 有 Is= Is = 所以,恒等置换Is=(1)是Sn中的幺元.,6.1.6 循环群和置换群,n元对称群、n元置换群 与的逆置换的复合为Is, 因此: -1= 就是的逆元. 即:Sn

19、关于置换的复合构成一个群, 称之为S上的n元对称群. Sn的任何子群称为S上的n元置换群.,6.1.6 循环群和置换群,n元对称群、n元置换群 例如 S3=(1),(12),(13),(23),(123),(132), S3的运算表如表6.1所示.(注意它与例6.6中G的联系),6.1.6 循环群和置换群,从上表6.1可以看到: (13)(12)(12)(13) 所以, S3不是阿贝尔群, 在 S3中, (12),(13)和(23)都是2阶元, 而(123)和(132)是3阶元. S3有6个子群, 即 =(1), =(1),(12), =(1),(13), =(1),(23), =(1),(1

20、23),(132), 其中(1)和S3是平凡的, 除S3自己以外, 都是S3的真子群. 设An是Sn上所有偶置换组成的集合, An是Sn子群, 叫做n元交错群.,6.1.6 循环群和置换群,6.2 环与域,6.2.1 环 定义6.8 设是代数系统, R为集合, +和为二元运算, 如果 (1) 为阿贝尔群, (2) 为半群, (3) 乘法对加法+适合分配律, 则称是环. 例如: , , , 都是环,+和表示普通加法和乘法, 分别叫整数环Z、有理数环Q、实数环R和复数环C. 是环,+,分别是矩阵加法和乘法. 注: 环中关于加法的逆元称为负元, 记为-x; 关于乘法的逆元称为逆元, 记为x-1,6.

21、2 环与域,6.2.2 交换环和含幺环 在环中, 如果乘法适合交换律, 则称R是交换环. 如果对于乘法有幺元, 则称R是含幺环. 为了区别含幺环中加法幺元和乘法幺元, 通常把加法幺元记作0, 乘法幺元记作1. 可以证明加法幺元0恰好是乘法的零元. 例如: , , , 都是交换环吗? 它们是含幺环吗?,6.2 环与域,6.2.3 左零因子、右零因子、无零因子环 在环中, 如果存在a,bR, a0, b0, 但ab0, 则称a为R中的左零因子, b为R中的右零因子. 如果环R中既不含左零因子, 也不含右零因子, 即 a,bR, ab0a0b0 则称R为无零因子环.,6.2 环与域,6.2.3 整环

22、和域 整环: 若环是交换、含幺和无零因子的, 称R为整环. 域: 设环整环, 且R至少含有2个元素, 若 aR (a0)有a-1R, 则称R是域. 例如: 有理数集Q、实数集R和复数集C关于普通的加法和乘法都构成了域, 整数集Z只能构成整数环, 而不是域, 因为并不是任意非零整数的倒数都属于Z.,例6.6 设S为下列集合,+和.为普通加法和乘法. (1) Sxx2nnZ. (2) Sxx2n+1nZ. (3) SxxZx0N, 问S和+,能否构成整环？能否构成域？为什么？,6.2 环与域,解: (1)不是整环也不是域,因为乘法幺元是1,1S. (2)不是整环也不是域,因为S不是环,普通加法的幺

23、元是0,0S, (3)S不是环,因为除0以外任何正整数x的加法逆元是-x,而-xS当然也不是整环和域.,6.2.4 环的性质 定理6.6 设是环, 则 (1) aR, a00a0. (2) a,bR,(-a)ba(-b)-(ab). (3) a,bR,(-a)(-b)ab. (4) a,b,cR, a(b-c)=ab-ac, (b-c)aba-ca.,6.2 环与域,6.3 格和布尔代数,6.3.1 格 定义6.10 设是偏序集, 如果 x,yS, x,y都有最小上界和最大下界, 则称S关于构成一个格. xy表示x和y的最小上界 xy表示x和y的最大下界. 例6.7 设n为正整数, Sn为n的

24、正因子的集合, D为整除关系, 则构成格. x,ySn, xy是x,y的最小公倍数x,y, xy是x,y的最大公约数(x,y),6.3 格和布尔代数,格,和 xy是x,y的最小公倍数x,y, xy是x,y的最大公约数(x,y),15 5,例6.8 判断图中偏序集是否构成格,说明为什么.,6.3 格和布尔代数,6.3 格和布尔代数,6.3.2 对偶原理 对偶命题: 设f是含有格中的元素以及符号=, ,的命题,令f*是将f中的改写成,将改写成, 改写成,改写成所得到的命题, 称为f的对偶命题. 根据格的对偶原理, 若f对一切格为真, 则f*也对一切格为真. 例如, 若在格中有 (ab)cc 成立,

25、 则有(ab)cc 成立.,定理6.7 设为格, 则运算和适合交换律、结合律、幂等律和吸收律, 即 (1)a,bL, 有abba, abba (2) a,b,cL, 有(ab)ca(bc), (ab)ca(bc). (3)aL, 有aaa, aaa. (4) a,bL,有 a(ab)a, a(ab)a.,6.3 格和布尔代数,6.3 格和布尔代数,格的另一个等价的定义 设是具有两个二元运算的代数系统,且对于*和运算适合交换律、结合律、吸收律, 则可以适当定义S中的偏序使得构成一个格, 且 a,bS ab=a*b, ab=ab.,6.3 格和布尔代数,6.3.3 分配格 定义6.11 设是格,

26、若a,b,cL有 a(bc)(ab)(ac) a(bc)(ab)(ac) 成立, 则称L为分配格.,图中(1)、(2)、(3)、(4)是分配格吗？ (3)a(bc)aea (ab)(ac)ddd (4)b(ac)beb (ba)(bc)dc=c.,6.3 格和布尔代数,6.3.4 全上界和全下界 定义6.12 若在格中存在一个元素a,bL, ab或(ba), 则称a为格L的全下界(或全上界) 对于一个格L, 全下界如果存在,则是唯一的,记为0.同样地,若全上界存在也是唯一的,记为1,具有全上界和全下界的格称为有界格,记作,6.3.5 有补格 定义6.13 设是有界格aL, 若存在bL使得ab0

27、, ab1, 则称b为a的补元. 例. (1)的a,b,c都不存在补元, 0与1互为补元; (2)的a,b,c中任意两个都互为补元, 0与1互为补元; (3)中a和b的补元都是c, 而c的补元是a和b,0与1互为补元.,6.3 格和布尔代数,6.3 格和布尔代数,6.3.5 有补格 有补格: 在格中有的元素无补元,有的元素有补元,有的元素有多个补元,如果格中每个元素都至少有一个补元,则称这个格为有补格.图6,4中(2)和(3)是有补格,而(1)不是. 对分配格L来说, 如果aL有补元, 则一定有唯一的补元a.,6.3 格和布尔代数,6.3.6 布尔代数 定义6.14 如果格是有补分配格, 则称

28、L为布尔格,也叫做布尔代数. 由于布尔代数L中的每个元都有唯一的补元,求补运算也可以看成是L中的一元运算. 因此, 布尔代数L可记为, 其中表示求补运算.,6.3 格和布尔代数,布尔代数有以下性质: 定埋6.8 设是布尔代数, 则有: aL, (a)a, a,bL, (ab)=ab, (ab)=ab . 证明: (ab)(ab)(aba)(abb) (aa)b)(a(bb)(1b)(a1) (ab)(ab)(aab)(bab) (aa)b)(bb)a) (0b)(0a)0. 所以ab是ab的补元,即(ab)ab. 同理可证 (ab)ab,本章小结,1. 掌握半群、独一点和群的概念; 给定一个代数系统能准确地判断它是一个什么代数系统;掌握这三种代数系统之间的关系. 2. 掌握环和域的概念, 明白环、整环和域之间的关系. 3. 掌握格和布尔代数的概念, 理解偏序集、格和布尔代数之间的关系.,