离散数学 章节练习KEY

1、离散数学 章节练习 4范围：代数系统一、单项选择题1. <G,*>是群，则对* ( A )A、有单位元，可结合 B、满足结合律、交换律 C、有单位元、可交换 D、有逆元、可交换2. 设N和Z分别表示自然数和整数集合，则对减法运算封闭的是 ( B )A、N B、x÷2|xÎZ C、x|xÎN且x是素数 D、2x+1| xÎZ 3. 设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，为集合的交运算，下列系统中是群的代数系统的有 ( B )A.Z，+，÷ B.Z，÷C.Z，÷ D.P(A)，&

2、#199;4. 设S=0，1，*为普通乘法，则< S , * >是 ( B )A、半群，但不是独异点；B、只是独异点，但不是群；C、群； D、环，但不是群。5. 设f是由群<G,>到群<,*>的同态映射，则ker (f)是 ( B )A、的子群 B、G的子群C、包含 D、包含G 6. 在整数集Z上,下列哪种运算不是封闭的 ( C ) A + B - C ÷ D X7. 设S=0，1，*为普通乘法，则< S , * >是 ( B )A、半群，但不是独异点； B、只是独异点，但不是群；C、群； D、环，但不是群。8. 设R是实数集合，“”为

3、普通乘法，则代数系统<R ，×> 是（ A ）。A群； B环； C半群 .都不是9. 设°是集合S上的二元运算，如果集合S中的某元素eL,对"xÎS都有 eL°x=x ,则称eL为 ( C )A、右单位元 B、右零元 C、左单位元 D、左零元10. <Z,+> 整数集上的加法系统中0是 ( A ) A 单位元 B逆元 C 零元 D陪集11. 若V=<S,°>是半群，则它具有下列那些性质 ( A )A、封闭性、结合性 B、封闭性、交换性 C、有单位元 D、有零元二、判断题1若半群<S,*>

4、含有零元，则称为独异点。 ( )2、代数系统<Z，×>的零元是0 ( )3、<e,*>是<G,*>的子群。 ( )4、小于6阶群都是可交换群。 ( )5、设*是S上的二元运算，若存在零元和单位元e，则|S| >1 ( )6、代数系统<Z, ×>的单位元是1。 ( )7若群<G,*>中的运算可交换，则称为交换群。 ( )8、在代数系统<A,*>中如果元素的左逆元存在，则它一定唯一且。( )9、设<S,*>是群<G,*>的子群，则<G,*>中幺元e是<S,*&

5、gt;中幺元。( )10、设， +,·为普通加法和乘法，则代数系统<A，+，·>是域。( )11、设*是S上的二元运算，若存在零元和单位元e，则|S| >1 ( )12、设<A,>为偏序集, BÍA, yB ，若"x(xByx)成立, 则称 y 为A的最小元 ( )13、若V=<S,° >是封闭、可结合,则称V为半群。 ( )14、<Z,+> 整数集上的加法独异点 ( )15、设G为群<G, °>且|G|>1，则G中没有零元。 ( )16、设为群<G, *

6、>，对于a, bÎG， 必存在唯一的 xÎG，使得a*x=b。 ( )17、设<G, *>是群,若G存在一个元素a，使得G中任意元素都由a的幂组成，则称该群为循环群。 ( )18、设°与*是集合S上的二种可交换的二元运算，若"x,yÎS都有 x*(x°y)=x , x°(x*y)=x 则称*与°是满足吸收律 ( )19、设°是集合S上的二元运算，若"xÎS 都有x°x=x,则称°在S上是幂等的,或者说运算° 在S上满足幂等律。 ( )20

7、、设°是集合S上的二元运算，若"x,yÎS都有x°y=y°x,则称°在S上是可交换的,或者说运算° 在S上满足交换律。( )21、设<G,*>是群,若G存在一个元素a，使得G中任意元素都由a的幂组成，则称该群为交换群。 ( )22、设<S, ©>是半群,集合BÍS,且运算©在B上封闭,则<B, ©>是半群。 ( )23、设G为群<G, °>且|G|>1，则G中没有单位零元 ( )【参考答案】1-10 ××

8、; × 11-20 ×× 21-23 ××三、填空题1代数系统<N，+>的单位元是 0 。2代数系统<G，*>的单位元e的逆元是 e 。3对代数系统<S，*>，其中*是S上的二元运算，若存在aS，且对任意的xÎS，都有a*x=x*a=x，则称a 为运算“*”的 单位 元。4自然数乘法代数系统<N，X>的单位元是 1 。5集合A和A上的偏序关系一起叫做 偏序集 。6设°是集合S上的二元运算，如果集合S中的某元素eL对"xÎS都有eL°x=x ,则称e

9、L为 左单位元 。7某xÎS若有yLÎS,使得 yL°x=e，则称yL为 左逆元 。8H是G的子群，aÎG,H的右陪集Ha = x | x=h°a, hÎH，其中a称为Ha的 代表元或特征元 。9设°是S上的二元运算,若存在零元q与单位元e,且集合S中至少有2个元素，则q与e的关系为 qe 。10设<A,R>是偏序集,BÍA, y0ÎB, 若"xÎB,均有<x,y0> ÎR，则y0是B的 最大元 。11设有代数系统<A,©>,在A

10、上定义了等价关系RÍA´A。如果<a1,a2>，<b1,b2>ÎR时均有<a1©b1, a2©b2>ÎR,称R为A上关于©的 同余关系 。12设<G, *>是群,若G存在一个元素a，使得G中任意元素都由 a的幂 组成，则称该群为循环群。记成G=<a>，a称为该群的生成元。13设°与*是集合S上的二种可交换的二元运算，若"x,yÎS都有 x*(x°y)=x , x°(x*y)=x, 则称*与°是满足 吸收律

11、。四、计算题1 .判断自然数中的加法<N,+>是否是半群。【参考答案】2判断整数中的加法<Z,+>是否是群，并证明。【参考答案】3. 判断自然数中的乘法<N,x>是否是半群。【参考答案】4. 证明：设<S, ©>是半群，集合BÍS，且运算©在B上封闭，则<B, ©>是半群。【参考答案】5. 设 * 为上的二元运算，X * Y = min ( x，y ),即x和y之中较小的数.求4 * 6，7 * 3，9 * 1，15 * 2的结果。【参考答案】4 3 1 26. 设 * 为上的二元运算，X *

12、Y = min ( x，y ),即x和y之中较小的数，求*运算的单位元，零元及中所有可逆元素的逆元。【参考答案】单位元 无，零元 1, 所有元素无逆元7. 设S=0，1，2，3，为模4乘法，即 "x,yS, xy=(xy)mod 4 。问S，是否构成群？为什么？【参考答案】解：(1) x,yS, xy=(xy)mod 4,是S上的代数运算。(2) x,y,zS,设xy=4k+r (xy)z =(xy)mod 4)z=rz=(rz)mod 4=(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4同理x(yz) =(xyz)mod 4所以，(xy)z = x(y

13、z)，结合律成立。(3) xS, (x1)=(1x)=x,，所以1是单位元。(4) 0和2没有逆元所以，S，不构成群8. 设Z为整数集合，在Z上定义二元运算为x,yZ,xoy= x+y-2，问Z关于o运算能否构成群？为什么？【参考答案】解：(1) x,yZ, xoy= x+y-2,o是Z上的代数运算。(2) x,y,zZ, (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz= xo(yoz)，结合律成立。(3)设是单位元，xZ, xo= ox=x,即x+-2= +x-2=x, e=2(4) xZ , 设x的逆元是y, xoy= yox=, 即x+y

14、-2=y+x-2=2, 所以，所以Z，o构成群9. 令S=a，b，S上有三个运算°，和分别如下表确定。 (a) (b) (c) 这三个运算中哪些运算满足交换律，结合律，幂等律？【参考答案】(a)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 (b)满足交换律,不满足幂等律,不满足结合律 没有单位元, 没有零元(c) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元10 .设集合A = 1 , 2 , 3 , 4 , * 是A 上的二元运算, 其定义为: a * b = a+ ab , 请写出*的运算表。【参考答案】其运算表如表所示。*12341234524681036

15、912154812162011.写出( N5 , 5 ) 的运算表, 其中N5 = 0 , 1 , 2 , 3 , 4 , 5 是模5 加法运算。【参考答案】代数系统( N5 , 5 ) 的运算表如表所示。50123400123411234022340133401244012312 .设A = 1 , 2 , 3 , 4 , * 是A 上的二元运算, 其定义为: a * b = min( a, b) , 请写出*的运算表。【参考答案】其运算表如表所示。*12341111121222312334123413.设( A, * ) 是代数系统, A 是有限集, 那么(1 ) 当运算* 对于A 是封闭

16、运算时, 其运算表有何特征?(2 ) 当运算* 是可交换运算时, 其运算表有何特征?【参考答案】(1 )当运算表中的元素都属于 A 时, * 对于 A 是封闭的。(2 )当运算表中的元素关于运算表的对角线对称时, * 为可交换运算。13.设( A, * ) 是代数系统, A 是有限集, 那么(1) 当运算* 对于A 是封闭运算时, 其运算表有何特征?(2) 当运算* 是可交换运算时, 其运算表有何特征?【参考答案】其运算表如表所示。*12341234524681036912154812162014 .设( Z, * ) 是代数系统, * 的定义分别为:(1 ) a * b = | a + b

17、|(2 ) a * b = ab(3 ) a * b = a + b - 1(4 ) a * b = a + 2 b(5 ) a * b = 2 ab问:哪些运算对于Z 是封闭的?哪些运算是可交换运算?哪些运算是可结合运算?【参考答案】 (1) a * b = | a + b | ,易见 * 对于 Z是封闭的, 是可交换运算,但 * 不是可结合运算,因为( a * b) * c = | a + b | * c=| a + b |+ c |a * ( b* c) = a*| b + c |=|a +| b + c |当取 a = 1, b = - 1 , c = - 1 时, 就有( a * b

18、) * c =| a + b |+c|= 1 a * ( b* c) =|a +| b + c |= 3所以( a * b) * c a * ( b* c)由此说明 * 不是可结合运算。(2) a* b = ab , 易见 * 对于 Z不是封闭的, 若取 a = 2 , b = - 1, 则 a * b = 2 - 1 = 1/ 2, 它不是整数。*也不是可交换运算, 若取 a = 2 , b = 3 ,则 a * b = 23 = 8, b * a = 32 = 9, 所以 a * b b* a。*也不是可结合运算, 因为( a* b) * c = ab * c = ( ab )c = ab

19、c a* (b * c) = a* bc = abc所以( a * b) * c a * ( b* c)由此说明 * 不是可结合运算。(3) a * b = a + b - 1 ,易见 * 对于 Z 是封闭的,且是可交换运算, 也是可结合运算。(4) a * b = a + 2b, * 对于 Z 是封闭的, 但不是可交换运算,因为a * b = a + 2b b* a = b + 2a所以 a* b b* a。* 也不是可结合运算, 因为( a * b) * c = ( a + 2b) * c= a + 2b + 2c a * ( b* c) = a * ( b + 2c)= a + 2(b

20、+ 2c) = a + 2b + 4c所以( a * b) * c a * ( b* c)。(5) a * b = 2 ab, 易见 * 对于 Z 是封闭的, 且是可交换运算和可结合运算。15.设A = 2 , 4 , 6 , 8 , 10 , * 是A 上的二元运算, 其定义分别为:(1 ) a * b = min( a, b)(2 ) a * b = a(3 ) a * b = ab + a(4 ) a * b = gcd( a, b) , 其中gcd( a, b) 表示a 和b 的最大公约数(5 ) a * b = lcm( a, b) , 其中lcm( a, b) 表示a 和b 的最小

21、公倍数问:哪些运算是等幂运算?【参考答案】 (1) , (2) , (4) , (5) 都是等幂运算。16 .在代数系统( Z, * ) 中, 二元运算* 的定义分别为:(1 ) a * b = a + b - 1(2 ) a * b = ( a + b)2(3 ) a * b = a2 + b2(4 ) a * b = b(5 ) a * b = 3 ab问:哪些运算* 可使( Z, * ) 为半群或独异点?【参考答案】.(1) 易见, a* b = a + b - 1, 运算 * 对于 Z 是封闭的, 且满足结合律,幺元为 1。所以( Z, * ) 是独异点。17 .A = 1 , 2 ,

22、 3 , 4 , 5 , 6 , A 上二元运算* 的定义分别为:(1 ) a * b = | a + b |(2 ) a * b = min( a, b)(3 ) * 为模7 乘法(4 ) * 为模7 加法(5 ) a * b = a2 + b问:哪些运算* 可使( A, * ) 为独异点?【参考答案】运算 a * b = ( a + b)2 对于 Z 是封闭的, 但不是可结合运算。因为( a* b) * c = ( a + b)2 * c= ( ( a + b)2 + c)2 a * ( b* c) = a * ( b + c)2= ( a + ( b + c)2 )2所以( a * b)

23、 * c a * ( b* c)由此可知, * 不是可结合运算, ( Z, * ) 不是半群。18.在代数系统( R, * ) 中, 二元运算* 定义为: a * b = ( a - 3) ( b - 3) + 3 , 证明( R, * )是独异点。【参考答案】运算 a * b = b,易见它对于 Z 是封闭的, 且满足结合律。因为( a * b) * c = ca* (b * c) = c 所以( a * b) * c = a * ( b* c)由此可知, ( Z, * ) 是半群, 但没有幺元,所以( Z, * ) 不是独异点。19.设A = 1 , 2 , 3 , 4 , 对于下列运算*

24、 :(1 ) a * b = a + b(2 ) * 是模5 乘法(3 ) * 是模5 加法(4 ) a * b = max( a, b)说明哪些运算使得( A, * ) 为群。【参考答案】(1) 由于 * 对于 A 是不封闭的, 所以( A, * ) 不是群。20 .设A = x | x = 2n ·3 m , n 和m 是整数 , 对于普通乘法×, 证明( A, ×) 是群。【参考答案】( A, * ) 不是群。因为模 5 加法对于 A 不是封闭的。( A, * ) 不是群。因为在 A 中除元素 1 有逆元外,其他元素都没有逆元。由于这两个运算表中,有些行中有

25、相同元素, 所以这两个运算表构成的代数系统都不是群。首先证明乘法运算对于 A 是封闭的。设 a = 2n1 × 3m1 , b = 2n2 × 3m2 , a× b = 2n1 ×3m1 ×2n2 × 3m2 = 2n1+ n2 ×3m1 + m2 , 由于 n1 , n2 , m1 , m2 都是整数,所以 n1 + n2 和 m1 + m2 也是整数,由此可知乘法运算对于 A 是封闭的。普通乘法是可结合运算。20 × 30 = 1 是其幺元。A 中任意元素 2n × 3m 的逆元为 2 - n 

26、15; 3 - m 。综上所述, ( A, * ) 是群。21 .设A = a, b , 试构造代数系统(P ( A) , ) 的运算表, 并说明(P ( A) , ) 是否是群?说明理由。【参考答案】 A = a, b, P ( A) = , a, b, a, b。(P ( A) , ) 的运算表如表所示。由表可知, 第 2, 3, 4 行都有相同元素,所以(P ( A) , ) 不是群。 ab a, b ab a, b a a a a, b a, b b b a, bb a, b a, b a, b a, b a, b a, b22 .设( G, * ) 是3 阶群, 其中G = e, a

27、, b , e 是幺元, 证明a2 = b, a3 = e。【参考答案】证明 先写出群 G的运算表, 由群的性质可知,运算表中各行、各列都没有相同元素,且 e 是幺元,所以 3 阶群 G 的运算表是惟一的,见表。*eabeeabaabebbea由运算表可知, a2 = b, a3 = e。另一种证明方法是:由于 3 是素数,3 阶群一定是循环群, 且每一个非幺元都是生成元 (3 阶元素 ) ,所以 a3 = e。由于 e是群中惟一的等幂元, 所以 a2 a;又由于 a 是 3 阶元素, 所以 a2 e; 由此可知, a2 = b。23 .设( G, * ) 是可交换群, a 和b 是G 中任意元素, 证明( a * b) n = an * bn ( n 是任意正整数)。【参考答案】由于 * 是可交换运算, 所以( a* b) n = a * b* a