《《数据结构与算法设计》第十、十一章习题.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法设计》第十、十一章习题.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第十、十一章第十、十一章习题课习题课北京理工大学北京理工大学计算机学院计算机学院刘琼昕刘琼昕2第十章第十章 习题课习题课o主要内容主要内容n半群、独异点与群的定义半群、独异点与群的定义n群的基本性质群的基本性质n子群的判别定理子群的判别定理n陪集的定义及其性质陪集的定义及其性质n拉格朗日定理及其应用拉格朗日定理及其应用n循环群的生成元和子群循环群的生成元和子群n置换群与置换群与Polya定理定理n环的定义与性质环的定义与性质n特殊的环特殊的环3基本要求基本要求o判断或证明给定集合和运算是否构成半群、独判断或证明给定集合和运算是否构成半群、独异点和群异点和群o熟悉群的基本性质熟悉群的基本性质o
2、能够证明能够证明G的子集构成的子集构成G的子群的子群o熟悉陪集的定义和性质熟悉陪集的定义和性质o熟悉拉格朗日定理及其推论，能够简单应用熟悉拉格朗日定理及其推论，能够简单应用o会用会用Polya定理进行计数定理进行计数o熟悉循环群的生成元及其子群性质熟悉循环群的生成元及其子群性质o熟悉熟悉n元置换的表示方法、乘法以及元置换的表示方法、乘法以及n元置换群元置换群o能判断给定代数系统是否为环和域能判断给定代数系统是否为环和域4练习练习1o判断下列集合和运算是否构成半群、独异点判断下列集合和运算是否构成半群、独异点和群和群.(1)a是正整数，是正整数，G=an|n Z,运算是普通运算是普通乘法乘法.(
3、2)Q+是正有理数集，运算为普通加法是正有理数集，运算为普通加法.(3)一元实系数多项式的集合关于多项式加一元实系数多项式的集合关于多项式加法法.5练习练习1解答解答(1)是半群、独异点和群是半群、独异点和群(2)是半群但不是独异点和群是半群但不是独异点和群(3)是半群、独异点和群是半群、独异点和群o方法：根据定义验证，注意运算的封闭性方法：根据定义验证，注意运算的封闭性6练习练习2o设设V1=,V2=,其中其中Z为整数集合为整数集合,+和和 分别代表普通加法和乘法分别代表普通加法和乘法.显然显然V1和和V2是半群和独异点是半群和独异点.判断下述集合判断下述集合S是否构成是否构成V1和和V2的
4、子半群和的子半群和子独异点子独异点.(1)S=2k|k Z(2)S=2k+1|k Z(3)S=1,0,17练习练习2解答解答o(1)S关于关于V1构成子半群和子独异点，但是关构成子半群和子独异点，但是关于于V2仅构成子半群。仅构成子半群。o(2)S关于关于V1不构成子半群也不构成子独异点，不构成子半群也不构成子独异点，S关于关于V2构成子半群和子独异点。构成子半群和子独异点。o(3)S关于关于V1不构成子半群和子独异点，关于不构成子半群和子独异点，关于V2构成子半群和子独异点。构成子半群和子独异点。8练习练习3o判断下列集合和给定运算是否构成环、整环判断下列集合和给定运算是否构成环、整环和域和
5、域,如果不构成如果不构成,说明理由说明理由.(1)A=a+bi|a,bQ,其中其中i2=1,运算为复数运算为复数加法和乘法加法和乘法.(2)A=2z+1|zZ,运算为实数加法和乘法运算为实数加法和乘法(3)A=2z|zZ,运算为实数加法和乘法运算为实数加法和乘法(4)A=x|x0 xZ,运算为实数加法和乘法运算为实数加法和乘法.(5)9练习练习3解答解答o解：解：(1)是环是环,是整环是整环,也是域也是域.(2)不是环不是环,因为关于加法不封闭因为关于加法不封闭.(3)是环是环,不是整环和域不是整环和域,因为乘法没有么元因为乘法没有么元.(4)不是环不是环,因为正整数关于加法的负元不存在因为正
6、整数关于加法的负元不存在.(5)不是环不是环,因为关于乘法不封闭因为关于乘法不封闭.10练习练习4o设设Z18为模为模18整数加群整数加群,求所有元素的阶求所有元素的阶.o解：解：|0|=1|9|=2|6|=|12|=3|3|=|15|=6|2|=|4|=|8|=|10|=|14|=|16|=9|1|=|5|=|7|=|11|=|13|=|17|=1811说明说明o群中元素的阶可能存在，也可能不存在群中元素的阶可能存在，也可能不存在.o对于有限群，每个元素的阶都存在，而且是对于有限群，每个元素的阶都存在，而且是群的阶的因子群的阶的因子.o对于无限群，单位元的阶存在，是对于无限群，单位元的阶存在
7、，是1；而其；而其它元素的阶可能存在，也可能不存在它元素的阶可能存在，也可能不存在.（可能（可能所有元素的阶都存在，但是群还是无限群）所有元素的阶都存在，但是群还是无限群）.12练习练习5(1)设设G为模为模12加群加群,求求在在G中所有的左陪集中所有的左陪集(2)设设X=x|x R,x 0,1,在在X上如下定义上如下定义6个个函数：函数：f1(x)=x，f2(x)=1/x,f3(x)=1 x,f4(x)=1/(1 x),f5(x)=(x 1)/x,f6(x)=x/(x 1),则则G=f1,f2,f3,f4,f5,f6关于函数合成运算构关于函数合成运算构成群成群.求子群求子群H=f1,f2的所
8、有的右陪集的所有的右陪集.13练习练习5解答解答解：解：(1)=0,3,6,9,的不同左陪集有的不同左陪集有3个，即个，即0=,1=1,4,7,10=4=7=102=2,5,8,11=5=8=11(2)f1,f2有有3个不同的陪集，它们是：个不同的陪集，它们是：H，Hf3=f3,f5,Hf4=f4,f6.14练习练习6o设设i 为虚数单位，即为虚数单位，即 i2=1,令令则则G关于矩阵乘法构成群关于矩阵乘法构成群.找出找出G的所有子群的所有子群.15练习练习6解答解答o解解令令A,B,C,D分别为分别为则运算表为则运算表为 G的子群有的子群有6个，即个，即平凡子群：平凡子群：=A,G2阶子群：
9、阶子群：=A,-A,4阶子群：阶子群：=A,B,-A,-B,=A,C,-A,-C,=A,D,-A,-D,17练习练习7o设群设群G的运算表如表所示，问的运算表如表所示，问G是否为循环是否为循环群？如果是，求出它所有的生成元和子群。群？如果是，求出它所有的生成元和子群。解：解：G=是循环群是循环群|b|=|f|=6,b和和f是生成元是生成元.|c|=|e|=3,|d|=2,c,d,e不是生不是生成元成元.子群：阶数子群：阶数1,2,3,61阶：阶：=a2阶：阶：=d,a3阶：阶：=c,e,a6阶：阶：G*练习练习8o试证：任何一个四阶群只可能是四阶循环群试证：任何一个四阶群只可能是四阶循环群或者
10、或者Klein四元群。四元群。o证明：设四阶群为证明：设四阶群为。其中。其中e是单是单位元。位元。n当四阶群含有一个四阶元素时，这个群就当四阶群含有一个四阶元素时，这个群就是循环群。是循环群。n当四阶群不含有四阶元素时，则由当四阶群不含有四阶元素时，则由Lagrange定理的推论定理的推论1可知，除单位元可知，除单位元e外，外，a,b,c的阶一定都是的阶一定都是2。练习练习8（续）（续）na*b不可能等于不可能等于a,b,e,否则将导致否则将导致b=e,a=e或或a=b的矛盾，所以的矛盾，所以a*b=c。n同样可以证明同样可以证明b*a=c,a*c=c*a=b,b*c=c*b=a,因此这个群是
11、因此这个群是Klein四元群。四元群。20练习练习9o证明偶数阶群必含证明偶数阶群必含2阶元阶元.o证：由证：由x2=e|x|=1或或2.换句话说换句话说,对于对于G中元素中元素x，如果，如果|x|2,必有必有x 1 x.由于由于|x|=|x 1|，阶大于，阶大于2的元素成对出现，的元素成对出现，共有偶数个共有偶数个.那么剩下的那么剩下的1阶和阶和2阶元总共应该是偶数个阶元总共应该是偶数个.1阶元只有阶元只有1个，就是单位元，从而证明了个，就是单位元，从而证明了G中必有中必有2阶元阶元.21练习练习10o设设G为群，为群，a是是G中的中的2阶元，证明阶元，证明G中与中与a可可交换的元素构成交换
12、的元素构成G的子群的子群.o证明：令证明：令H=x|x G xa=ax,下面证明下面证明H是是G的子群的子群.因为因为a是是2阶元，所以阶元，所以a=a-1.首先首先e属于属于H，H是是G的非空子集的非空子集.任取任取x,y H，有，有(xy 1)a=x(y 1a)=x(a 1y)1=x(ay)1=x(ya)1=xa 1y 1=xay 1=axy 1=a(xy 1)因此因此xy 1属于属于H.由判定定理二命题得证由判定定理二命题得证.22说明说明o证明子群可以用定义和判定定理，特别是判证明子群可以用定义和判定定理，特别是判定定理二定定理二.o判定定理二：判定定理二：n验证验证H 非空非空n任取
13、任取x,y H，证明，证明xy 1 Ho判定定理三：判定定理三：n验证验证H 非空，有限非空，有限n任取任取x,y H，证明，证明xy H23练习练习11o设设H1,H2分别是群分别是群G 的的r,s阶子群，若阶子群，若(r,s)=1，证明，证明H1 H2=e.o证：证：H1,H2分别是群分别是群G 的子群，的子群，所以所以e H1 H2，且且 a,b H1 H2,ab-1 H1 H2,所以所以H1 H2H1，H1 H2H2.由由Lagrange定理，定理，|H1 H2|整除整除r，也整除，也整除s.从而从而|H1 H2|整除整除r与与s 的最大公因子的最大公因子.因为因为(r,s)=1,从而
14、从而|H1 H2|=1.即即H1 H2=e.24练习练习12o设设G=是循环群是循环群,阶为阶为n.试证明：试证明：对任何自然数对任何自然数r(rn)，如果，如果ar是是G的生成元的生成元,则则n与与r互质互质.o证明：设证明：设ar是是G的生成元，则的生成元，则|ar|=n.令令r与与n的最大公约数为的最大公约数为d，则存在正整数，则存在正整数t 使得使得r=dt.因此因此,(ar)n/d=(adt)n/d=(an)t=e所以是所以是|ar|是是n/d的因子，即的因子，即n整除整除n/d.从而证明了从而证明了d=1，即，即r与与n互质。互质。25练习练习13o设设G=是循环群，试证是循环群，
15、试证G的子群仍是循环群的子群仍是循环群.o证明：证明：n设设H是是G=的子群，若的子群，若H=e，显然，显然H是循是循环群，否则取环群，否则取H中的最小正方幂元中的最小正方幂元am，下面，下面证明证明H=.易见易见 H.n下面证明下面证明H.任取任取alH，由除法可知，由除法可知存在整数存在整数q 和和r，使，使 l=qm+r，其中其中0rm 1 ar=al qm=al(am)q 由由al,amH 且且H 是是G 的子群可知的子群可知arH.因为因为am是是H中最小正方幂元，必有中最小正方幂元，必有r=0.推出推出al=(am)q26练习练习14o证明证明Fermat小定理小定理：设：设p为素
16、数，则为素数，则p|(np n)o证：考虑一个圆环上等距离穿有证：考虑一个圆环上等距离穿有p个珠子，用个珠子，用n 种颜色对珠子着色种颜色对珠子着色.考虑围绕中心旋转，则考虑围绕中心旋转，则群是：群是：G=1,2,p因为因为p是素数，所以除了恒等置换外，其他是素数，所以除了恒等置换外，其他p-1个置换都由个置换都由1个个p阶轮换构成：阶轮换构成：1=()()()2=()p=()27练习练习14（续）（续）o根据根据Polya定理，不同的着色方案数是定理，不同的着色方案数是o于是于是p|(np n)28练习练习15o在整数环中定义在整数环中定义 和和两个运算两个运算,a,bZ有有 a b=a+b
17、 1,ab=a+b ab.证明证明构成环构成环o证证 a,bZ有有a b,abZ,两个运算封闭两个运算封闭.任取任取a,b,cZ(a b)c=(a+b 1)c=(a+b 1)+c 1=a+b+c 2a(b c)=a(b+c 1)=a+(b+c 1)1=a+b+c 229练习练习15（续）（续）(ab)c=(a+b ab)c=a+b+c(ab+ac+bc)+abca(bc)=a(b+c bc)=a+b+c(ab+ac+bc)+abc 与可结合可结合.1为为 的单位元的单位元,2 a为为a关于关于 的逆元的逆元,*可交换可交换.Z关于关于 构成交换群构成交换群,关于关于构成半群构成半群.关于关于
18、满足分配律满足分配律.a(b c)=a(b+c 1)=2a+b+c ab ac 1(ab)(ac)=2a+b+c ab ac 1构成环构成环30练习练习16o设设p为素数，证明为素数，证明Zp是域是域.o证证p为素数，所以为素数，所以|Zp|2.易见易见Zp可交换，单位元是可交换，单位元是1.对于任意的对于任意的i,jZp,设设i 0有有i j=0p 整除整除ij p|j j=0所以所以Zp 中无零因子，中无零因子，Zp为整环为整环.31练习练习16（续）（续）下面证明每个非零元素都有逆元下面证明每个非零元素都有逆元.因为因为Zp 是有限半群是有限半群,且且Zp-0关于关于 适合消去律适合消去
19、律任取任取iZp，i 0，令，令i Zp=i j|jZp则则i Zp=Zp，否则否则 j,kZp，使得，使得i j=i k，由消去律得由消去律得j=k.由由1Zp，存在，存在jZp，使得，使得i j=1.由于交换性可知由于交换性可知j 就是就是i 的逆元的逆元.练习练习17o在域在域Z5中解方程：中解方程：3x=2o解：解：x=3-1 2=2 2=4第十一章第十一章习题课习题课o主要内容主要内容n格的两个等价定义格的两个等价定义n格的性质格的性质n子格子格n特殊格：分配格、有界格、有补格、布尔特殊格：分配格、有界格、有补格、布尔代数代数第十一章第十一章习题课习题课o基本要求基本要求n能够判别给
20、定偏序集或者代数系统是否构能够判别给定偏序集或者代数系统是否构成格成格n能够确定一个命题的对偶命题能够确定一个命题的对偶命题n能够证明格中的等式和不等式能够证明格中的等式和不等式n能判别格能判别格L的子集的子集S是否构成子格是否构成子格n能够判别给定的格是否为分配格、有补格能够判别给定的格是否为分配格、有补格n能够判别布尔代数并证明布尔代数中的等能够判别布尔代数并证明布尔代数中的等式式练习练习1o(1)证明格中的命题证明格中的命题,即即(ab)b=b(2)证明证明(ab)(cd)(ac)(bd)o证明：证明：(1)(ab)b是是ab与与b的最小上界的最小上界,根据最根据最小上界的定义有小上界的
21、定义有(ab)b b.b是是ab与与b的上界的上界,故有故有(ab)b b.由于偏序的反对由于偏序的反对称性称性,等式得证等式得证.练习练习1（续）（续）(2)ab a ac,ab b bd,所以所以(ab)(ac)(bd),同理同理(cd)(ac)(bd).从而得到从而得到(ab)(cd)(ac)(bd)练习练习2o求图中格的所有子格求图中格的所有子格.1元子格：元子格：a,b,c,d,e；2元子格：元子格：a,b,a,c,a,d,a,e,b,c,b,d,b,e,c,e,d,e；3元子格：元子格：a,b,c,a,b,d,a,b,e,a,c,e,a,d,e,b,c,e,b,d,e；4元子格：元
22、子格：a,b,c,e,a,b,d,e,b,c,d,e；5元子格：元子格：a,b,c,d,e eabcd练习练习3o判别上述格判别上述格L是否为分配格是否为分配格.L1不是分配格不是分配格,因为它含有与钻石格同构的子格因为它含有与钻石格同构的子格.L2和和L3不是分配格不是分配格,因为它们含有与五角格同构因为它们含有与五角格同构的子格的子格.L1L2 L3练习练习4o针对下图，求出每个格的补元并说明它们是针对下图，求出每个格的补元并说明它们是否为有补格否为有补格?L1L2 L3练习练习4解答解答oL1中中,a与与h互为补元互为补元,其他元素没补元其他元素没补元.oL2中中,a与与g互为补元互为补
23、元.b的补元为的补元为c,d,f；c的补的补元为元为b,d,e,f；d的补元为的补元为b,c,e；e的补元为的补元为c,d,f；f的补元为的补元为b,c,e.oL3中中,a与与h互为补元互为补元,b的补元为的补元为d；c的补元的补元为为d；d的补元为的补元为b,c,g；g的补元为的补元为d.L2与与L3是有补格是有补格.练习练习5o对于以下各题给定的集合和运算判断它们是对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）域、格、布尔代数）,并说明理由并说明理由.(1)S1=1,1/2,2,1/3,3,1/4,4,为
24、普通乘法为普通乘法.(2)S2=a1,a2,.,an,ai,ajS2,ai aj=ai,这里的这里的n 为给定正整数为给定正整数,n1.(3)S3=0,1,为普通乘法为普通乘法.(4)S4=1,2,3,6,x,yS4,x y与与x y分别分别表示表示x 与与y 的最小公倍数和最大公约数的最小公倍数和最大公约数.(5)S5=0,1,为模为模2加法加法,为模为模2乘法乘法.练习练习5解答解答o(1)不是代数系统不是代数系统,因为乘法不封闭因为乘法不封闭,例如例如4 4=16.o(2)是半群但不是独异点是半群但不是独异点,因为因为 运算满足结合律运算满足结合律,但是没有单位元但是没有单位元.o(3)
25、是独异点但不是群是独异点但不是群.因为因为 运算满足结合律运算满足结合律,单位元是单位元是1,可是可是0没有乘法逆元没有乘法逆元.o(4)是格是格,也是布尔代数也是布尔代数.因为这两个运算满足交因为这两个运算满足交换律和分配律；求最小公倍数运算的单位元是换律和分配律；求最小公倍数运算的单位元是1,求最大公约数运算的单位元是求最大公约数运算的单位元是6,满足同一律；满足同一律；两个运算满足补元律两个运算满足补元律.o(5)是域是域.对于模对于模n 的环的环Zn,当当n为素数时构成域为素数时构成域.练习练习6o设设是布尔代数是布尔代数,证明对于证明对于B中中任意元素任意元素a,b练习练习6（续）（
26、续）练习练习7o判断下述代数系统是否为格？是不是布尔代判断下述代数系统是否为格？是不是布尔代数？数？(1)S=1,3,4,12;任给任给x,yS,x y=lcm(x,y),x y=gcd(x,y),其中其中lcm是求最小公倍数是求最小公倍数,gcd是求最大公约数是求最大公约数.(2)S=0,1,2;是模是模3加法加法,是模是模3乘法乘法(3)S=0,.,n,其中其中n2;任给任给x,yS,x y=max(x,y),x y=min(x,y)练习练习7解答解答o(1)是布尔代数是布尔代数.o(2)不是格不是格.o(3)是格是格,但不是布尔代数但不是布尔代数.初始状态初始状态n6绕对边中点转绕对边中点转180度度(AF)(BE)(CD)6n3绕对顶点转绕对顶点转120度度(AFC)(BED)4n2绕对顶点转绕对顶点转240度度(ACF)(BDE)4n2绕对面中点转绕对面中点转90度度(ADBC)(E)(F)3n3绕对面中点转绕对面中点转180度度(AB)(CD)(E)(F)3n4绕对面中点转绕对面中点转270度度(ACBD)(E)(F)3n3对正方体顶点着色对正方体顶点着色o所以用所以用n种颜色对一个正方体的面着色的方种颜色对一个正方体的面着色的方案数为：案数为：