《数据结构与算法设计》第十、十一章习题.ppt

1 第十、十一章 习题课 北京理工大学 计算机学院 刘琼昕 2 第十章 习题课 o 主要内容 n 半群、独异点与群的定义 n 群的基本性质 n 子群的判别定理 n 陪集的定义及其性质 n 拉格朗日定理及其应用 n 循环群的生成元和子群 n 置换群与Polya定理 n 环的定义与性质 n 特殊的环 3 基本要求 o 判断或证明给定集合和运算是否构成半群、独 异点和群 o 熟悉群的基本性质 o 能够证明G的子集构成G的子群 o 熟悉陪集的定义和性质 o 熟悉拉格朗日定理及其推论，能够简单应用 o 会用Polya定理进行计数 o 熟悉循环群的生成元及其子群性质 o 熟悉n元置换的表示方法、乘法以及n元置换群 o 能判断给定代数系统是否为环和域 4 练习1 o 判断下列集合和运算是否构成半群、独异点 和群. (1) a 是正整数，G = an | nZ, 运算是普通 乘法. (2) Q+是正有理数集，运算为普通加法. (3) 一元实系数多项式的集合关于多项式加 法. 5 练习1解答 (1) 是半群、独异点和群 (2) 是半群但不是独异点和群 (3) 是半群、独异点和群 o 方法：根据定义验证，注意运算的封闭性 6 练习2 o 设V1= , V2 = ,其中Z为整数集合, + 和 分别代表普通加法和乘法. 显然V1和V2 是半群和独异点. 判断下述集合S是否构成V1和V2的子半群和 子独异点. (1) S= 2k | kZ (2) S= 2k+1 | kZ (3) S= 1, 0, 1 7 练习2解答 o (1) S关于V1构成子半群和子独异点，但是关 于V2仅构成子半群。 o (2) S关于V1不构成子半群也不构成子独异点 ，S关于V2构成子半群和子独异点。 o (3) S关于V1不构成子半群和子独异点，关于 V2构成子半群和子独异点。 8 练习3 o 判断下列集合和给定运算是否构成环、整环 和域, 如果不构成, 说明理由. (1) A = a+bi | a,bQ , 其中i2= 1, 运算为复 数加法和乘法. (2) A= 2z+1 | zZ, 运算为实数加法和乘法 (3) A= 2z | zZ, 运算为实数加法和乘法 (4) A= x | x0xZ, 运算为实数加法和乘法. (5) 9 练习3解答 o 解： (1) 是环, 是整环, 也是域. (2) 不是环, 因为关于加法不封闭. (3) 是环, 不是整环和域, 因为乘法没有么元. (4) 不是环, 因为正整数关于加法的负元不存在 . (5) 不是环, 因为关于乘法不封闭. 10 练习4 o 设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| =18 11 说明 o 群中元素的阶可能存在，也可能不存在. o 对于有限群，每个元素的阶都存在，而且是 群的阶的因子. o 对于无限群，单位元的阶存在，是1；而其 它元素的阶可能存在，也可能不存在.（可能 所有元素的阶都存在，但是群还是无限群）. 12 练习5 (1) 设G为模12加群, 求 在G中所有的左陪集 (2) 设 X= x | xR, x 0,1, 在X上如下定义6个 函数： f1(x) = x， f2(x) =1/x, f3(x) = 1x, f4(x) = 1/(1x), f5(x) = (x1)/x, f6(x) = x/(x1), 则G = f1, f2, f3, f4, f5, f6关于函数合成运算构 成群. 求子群H=f1, f2 的所有的右陪集. 13 练习5解答 解：(1) = 0, 3, 6, 9, 的不同左陪集有3 个，即 0 = , 1 = 1, 4, 7, 10 =4 = 7 = 10 2= 2, 5, 8, 11 = 5 = 8 = 11 (2) f1, f2有3个不同的陪集，它们是： H，Hf3 = f3, f5, Hf4 = f4, f6. 14 练习6 o 设 i 为虚数单位，即 i2 = 1, 令 则G关于矩阵乘法构成群. 找出G的所有子群 . 15 练习6解答 o 解 令A, B, C, D分别为 则运算表为 G的子群有6个，即 平凡子群： = A, G 2 阶子群： = A, -A, 4 阶子群： = A,B,-A,-B, = A,C,-A,-C, = A,D,-A,-D, 17 练习7 o 设群G的运算表如表所示，问G是否为循环 群？如果是，求出它所有的生成元和子群。 解：G=是循环群 |b|=|f|=6, b和f 是生成元. |c|=|e|=3, |d|=2,c,d,e不是生 成元. 子群：阶数1,2,3,6 1阶：=a 2阶：=d, a 3阶：=c, e, a 6阶：G * 练习8 o 试证：任何一个四阶群只可能是四阶循环群 或者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, 因此这个群是Klein四元群。 20 练习9 o 证明偶数阶群必含2阶元. o 证：由 x2 = e |x| = 1 或2. 换句话说, 对于G中元素x，如果 |x| 2, 必有 x1 x. 由于 |x| = |x1|，阶大于2的元素成对出现， 共有偶数个. 那么剩下的 1 阶和 2 阶元总共应该是偶数个. 1 阶元只有 1 个，就是单位元，从而证明了 G中必有 2 阶元. 21 练习10 o 设G为群，a是G中的2 阶元，证明G中与a可 交换的元素构成G的子群. o 证明：令H= x | xG xa = ax, 下面证明H 是G的子群. 因为a是2阶元，所以a=a-1. 首先e属于H，H是G的非空子集. 任取x, y H，有 (xy1) a = x(y1a ) = x(a1y)1 = x(ay)1 = x(ya)1 = xa1y1 = xay1 = axy1 = a(xy1) 因此 xy1属于H. 由判定定理二命题得证. 22 说明 o 证明子群可以用定义和判定定理，特别是判 定定理二. o 判定定理二： n 验证 H 非空 n 任取 x, yH，证明xy1H o 判定定理三： n 验证 H 非空，有限 n 任取 x, yH，证明xyH 23 练习11 o 设 H1,H2分别是群G 的 r, s 阶子群，若(r,s) = 1 ，证明H1H2 = e. o 证： H1,H2分别是群G 的子群， 所以eH1H2，且a,bH1H2 ,ab-1H1H2, 所以H1H2H1，H1H2 H2. 由Lagrange定理，|H1H2| 整除r，也整除s. 从而 |H1H2| 整除 r与s 的最大公因子. 因为(r,s) = 1, 从而 |H1H2 | = 1. 即 H1H2 = e. 24 练习12 o 设G=是循环群,阶为n.试证明： 对任何自然数 r ( r是循环群，试证G的子群仍是循环群. o 证明： n 设H是G=的子群，若H=e，显然H是循 环群，否则取H中的最小正方幂元am，下面 证明H=. 易见 H. n 下面证明H. 任取alH，由除法可知 存在整数 q 和 r，使 l = qm+r， 其中 0rm1 ar = alqm = al(am)q 由al, amH 且 H 是G 的子群可知arH. 因为am是H中最小正方幂元，必有r = 0. 推出 al = (am)q 26 练习14 o 证明Fermat小定理：设 p为素数，则 p|(npn) o 证：考虑一个圆环上等距离穿有 p个珠子，用 n 种颜色对珠子着色. 考虑围绕中心旋转，则 群是： G= 1, 2, , p 因为p是素数，所以除了恒等置换外，其他p-1 个置换都由1个p阶轮换构成： 1=()()() 2=( ) p=( ) 27 练习14（续） o 根据Polya定理，不同的着色方案数是 o于是 p|(npn) 28 练习15 o 在整数环中定义和两个运算, a,bZ 有 ab = a+b1, ab = a+bab. 证明构成环 o 证 a,bZ有ab, abZ, 两个运算封闭. 任取a,b,cZ (ab)c = (a+b1)c = (a+b1)+c1 = a+b+c2 a(bc) = a(b+c1) = a+(b+c1)1 = a+b+c2 29 练习15（续） (ab)c = (a+bab)c = a+b+c (ab+ac+bc)+abc a(bc) = a(b+cbc) = a+b+c (ab+ac+bc)+abc 与可结合. 1为的单位元, 2a为a关于的逆元, *可交换. Z关于构成交换群, 关于构成半群. 关于 满足分配律. a(bc) = a(b+c1) = 2a+b+cabac1 (ab)(ac) = 2a+b+cabac1 构成环 30 练习16 o 设 p为素数，证明Zp是域. o 证 p为素数，所以 |Zp|2. 易见Zp可交换，单位元是1. 对于任意的 i, jZp, 设i 0有 i j = 0 p 整除 ij p| j j = 0 所以 Zp 中无零因子，Zp为整环. 31 练习16（续） 下面证明每个非零元素都有逆元. 因为Zp 是有限半群, 且Zp-0关于适合消去律 任取 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 的逆元. 练习17 o 在域Z5中解方程：3x=2 o 解： x = 3-1 2= 22=4 第十一章 习题课 o 主要内容 n 格的两个等价定义 n 格的性质 n 子格 n 特殊格：分配格、有界格、有补格、布尔 代数 第十一章 习题课 o 基本要求 n 能够判别给定偏序集或者代数系统是否构 成格 n 能够确定一个命题的对偶命题 n 能够证明格中的等式和不等式 n 能判别格L的子集S是否构成子格 n 能够判别给定的格是否为分配格、有补格 n 能够判别布尔代数并证明布尔代数中的等 式 练习1 o (1) 证明格中的命题, 即 (ab)b = b (2) 证明 (ab)(cd)(ac)(bd) o 证明： (1) (ab)b是ab与b的最小上界, 根据最 小上界的定义有(ab)bb . b是ab与b的 上界, 故有(ab)bb. 由于偏序的反对称 性, 等式得证. 练习1（续） (2) abaac, abbbd, 所以 (ab)(ac)(bd), 同理 (cd)(ac)(bd). 从而得到 (ab)(cd)(ac)(bd) 练习2 o 求图中格的所有子格. 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元子格： a, b, c, e , a, b, d, e , b, c, d, e ； 5元子格： a, b, c, d, e e a b cd 练习3 o 判别上述格L是否为分配格. L1不是分配格, 因为它含有与钻石格同构的子格. L2和L3不是分配格, 因为它们含有与五角格同构 的子格. L1 L2 L3 练习4 o 针对下图，求出每个格的补元并说明它们是 否为有补格? L1 L2 L3 练习4解答 oL1中, a与h互为补元, 其他元素没补元. oL2中, a与g互为补元. 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 是有补格. 练习5 o 对于以下各题给定的集合和运算判断它们是 哪一类代数系统（半群、独异点、群、环、 域、格、布尔代数）, 并说明理由. (1) S1 = 1, 1/2, 2, 1/3, 3, 1/4, 4, 为普通乘法. (2) S2 = a1, a2, ., an, ai, ajS2, aiaj = ai, 这里的 n 为给定正整数, n1. (3) S3 = 0, 1,为普通乘法. (4) S4 = 1, 2, 3, 6, x,yS4, xy与xy分别 表示 x 与 y 的最小公倍数和最大公约数. (5) S5 = 0, 1, 为模2加法, 为模2乘法. 练习5解答 o (1) 不是代数系统, 因为乘法不封闭, 例如 44=16. o (2) 是半群但不是独异点, 因为运算满足结合律 , 但是没有单位元. o (3) 是独异点但不是群. 因为运算满足结合律, 单位元是1, 可是0没有乘