離散數學 章節(jié)練習KEY

1、離散數學 章節(jié)練習 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、環(huán)，但不是群。5. 設f是由群<G,>到群<,*>的同態(tài)映射，則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、環(huán)，但不是群。8. 設R是實數集合，“”為

3、普通乘法，則代數系統<R ，×> 是（ A ）。A群； B環(huán)； 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的冪組成，則稱該群為循環(huán)群。 ( )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的冪 組成，則稱該群為循環(huán)群。記成G=<a>，a稱為該群的生成元。13設°與*是集合S上的二種可交換的二元運算，若"x,yÎS都有 x*(x°y)=x , x°(x*y)=x, 則稱*與°是滿足 吸收律

11、。四、計算題1 .判斷自然數中的加法<N,+>是否是半群。【參考答案】2判斷整數中的加法<Z,+>是否是群，并證明?！緟⒖即鸢浮?. 判斷自然數中的乘法<N,x>是否是半群?！緟⒖即鸢浮?. 證明：設<S, ©>是半群，集合BÍS，且運算©在B上封閉，則<B, ©>是半群?！緟⒖即鸢浮?. 設 * 為上的二元運算，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) , 其中l(wèi)cm( 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?！緟⒖即鸢浮孔C明 先寫出群 G的運算表, 由群的性質可知,運算表中各行、各列都沒有相同元素,且 e 是幺元,所以 3 階群 G 的運算表是惟一的,見表。*eabeeabaabebbea由運算表可知, a2 = b, a3 = e。另一種證明方法是:由于 3 是素數,3 階群一定是循環(huán)群, 且每一個非幺元都是生成元 (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