離散數(shù)學第5章

1、1,第3篇 代數(shù)系統(tǒng)（Algebraic System）,2,第5章 代數(shù)結構（algebraic structure ）,§1代數(shù)系統(tǒng)的引入§2運算及其性質§3半群§4群與子群§5阿貝爾群和循環(huán)群§6陪集與拉格朗日定理§7同態(tài)與同構§8 環(huán)和域,,3,§1代數(shù)系統(tǒng)的引入,定義：如果 ? 為An到B的一個函數(shù)

2、，則稱 ? 為集合A上的n元運算（operater）。 如果 B?A，則稱該n元運算在A上封閉。,4,§1代數(shù)系統(tǒng)的引入,本章主要討論一元運算和二元運算。例：（1）在整數(shù)I和實數(shù)R中,+,-,×均為二元運算。 （2）在集合Z的冪集?(z)中,?,?均為二元運算,而“~”是一元運算；,5,§1代數(shù)系統(tǒng)的引入,（3）{命題公式}中,∨,∧均為二元運算,而“?”為一元運算（4）{雙射函數(shù)}中,函數(shù)

3、的合成運算是二元運算； 二元運算常用符號：+,?,?,?,?,?,?,?等等。,6,§1代數(shù)系統(tǒng)的引入,定義:一個非空集合A連同若干個定義在該集合上的運算f1,f2,….,fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)， 記作。,7,§2運算及其性質,定義:設*是集合S上的二元運算,對任一x,y?S有x?y∈S則稱?運算在S上是封閉的。,8,§1代數(shù)系統(tǒng)的引入,例：（1）在正整偶數(shù)的集合E中,對×,

4、+運算是封閉的；在正整奇數(shù)的集合中,對×運算是封閉的,而對+運算不是封閉的。,（2）在前例中,R,I集合中+,-,×運算； ?(z) 的元素中?,? ,~,運算等均為封閉的。,9,§2運算及其性質,例題: 設A={x|x=2n,n?N},問乘法運算是否封閉？對加法運算呢？,解 對于任意的2r,2s?A，r，s?N，因為2r·2s=2r+s?A,所以乘法運算是封閉。對于加法運算是不封閉的，因為

5、至少有2+22=6?A,10,§2運算及其性質,定義:設*是集合S上的二元運算,對任一x,y?S有x?y=y?x,則稱?運算在S上是可交換的（commutative ）或者說?在S上滿足交換律。,11,§2運算及其性質,例題:設Q是有理數(shù)集合，Δ是Q上的二元運算，對任意的a,b?R， aΔb=a+b-a·b，問運算Δ是否可交換。,解 因為 aΔb=a+b-a·b=b+a-b

6、3;a=bΔa所以運算Δ 是可交換的。,12,§2運算及其性質,定義:設*是集合S上的二元運算,對任一x,y,z ?S都有 （x ? y）? z=x ?（y ? z）,則稱?運算在S上是可結合的（associative ）或者說*在S上滿足結合律。,13,§2運算及其性質,例題:設A是一個非空集合， ★是A上的二元運算，對于任意a,b?A,有a★b=b，證明★是可結合運算。,證明 因為對于任意的a,b,c ?

7、A (a★b)★c=b★c=c而 a★(b★c)=a★c=c所以(a★b)★c=a★(b★c),14,§2運算及其性質,定義:設?和?是集合S上的二個二元運算,對任一x,y,z ?S有 x ?（y ? z）=（x ? y）?（x ? z）； （y ? z）? x=（y ? x）?（z ? x）, 則稱運算?對?是可分配的（distributive ）或稱?對?滿足分配律。,15,&#

8、167;2運算及其性質,例題：設集合A＝｛α，β｝ ，定義A上的二元運算?，?，運算表如下：問： ?對?可分配嗎？,16,從*和△的運算表中可以看出*和△兩種運算都是可交換的。故只須驗證 α△(α*α)=(α△α)*(α△α) α△(α*β)=(α△α)*(α△β) α△(β*β)=(α△β)*(α△β)

9、 β△(α*α)=(β△α)*(β△α) β△(α*β)=(β△α)*(β△β) β△(β*β)=(β△β)*(β△β),α△(α*α)=α△α=α (α△α)*(α△α)=α*α=α α△(α*β)=α△β=α (α△α)*(α△β)=α*α=αα△(β*β)=α△α=α (α△β)*

10、(α△β)=α*α=αβ△(α*α)=β△α=α (β△α)*(β△α)=α*α=αβ△(α*β)=β△β=β (β△α)*(β△β)=α*β=ββ△(β*β)=β△α=α (β△β)*(β△β)=β*β=α,驗證運算△對于運算*是可分配的。,17,β* (α△ β)≠(β*α) △(β*β) β* (α△ β)＝ β (β*α) △

11、(β*β)＝ α,運算* 對于運算△是不可分配的。,18,§2運算及其性質,定義:設?，?是定義在集合S上的兩個可交換二元運算，如果對于任意的x,y?S，都有：x ?(x ?y)=x；x ?(x?y)=x 則稱運算?和運算?滿足吸收律（assimilate）。,19,§2運算及其性質,例題：設集合N為自然數(shù)全體，在N上定義兩個二元運算*和★，對于任意x,y?N，有 x*

12、y=max(x,y) x★y=min(x,y)驗證運算*和★的吸收律。,20,§2運算及其性質,解 對于任意a,b?N a*(a★b)=max(a,min(a,b))=a a★(a*b)=min(a,max(a,b))=a因此，*和★滿足吸收律。,21,§2運算及其性質,定義:設*是S上的二元運算,若對任一x?S有x ? x=x,則稱?滿足等冪律（idempot

13、ent ）。,22,§2運算及其性質,例題：設?(S)是集合S的冪集，在?(S)上定義的兩個二元運算，集合的“并”運算∪和集合的“交”運算∩ ，驗證是∪、∩等冪的。,23,§2運算及其性質,討論定義：1)S上每一個元素均滿足x?x=x,才稱?在S上滿足冪等律；2)若在S上存在元素x?S有x ? x=x,則稱x為S上的等冪元；3)由此定義,若x是冪等元素,則有x?x=x和xn=x成立。,24,§2運算及

14、其性質,例：（1）在實數(shù)集合R中,+,×是可交換,可結合的,×對+是滿足分配律的,“0”對+是等冪元素,而其它不為等冪元素,對“-”法是不可交換,不可結合的；,25,§2運算及其性質,（2）在?(z)中, ?,?均是可交換,可結合的, ?對?, ?對?均是可分配的； ?(z)中任一元素,對?,?均是等冪元素?！酀M足等冪律；而?(z)中,對稱差分?是可交換,可結合的。,26,§2運算及其性質,除

15、?(s) ={?}以外不滿足等冪律。 ∵ ? ? ? = ?,而除?以外的A? ?(z)有A ? A≠A。,27,§2運算及其性質,下面定義特異元素幺元,零元和逆元。定義：設*是集合Z中的二元運算,(1)若有一元素el ?Z,對任一x ?Z有el*x=x；則稱el為Z中對于*的左幺元(左單位元素)；,28,§2運算及其性質,(2)若有一元素er ?Z,對任一x ?Z有x* er=x；則稱er為Z中對于*的右幺

16、元（右單元元素）。,29,§2運算及其性質,定理：若el和er分別是Z中對于*的左幺元和右幺元,則對于每一個x ?Z，可有el= er = e和e*x=x* e=x，則稱e為Z中關于運算* 的幺元，且e ?Z是唯一的。,30,§2運算及其性質,∵ el和er分別是對*的左,右左元， 則有el * er = er = el∴有el = er = e成立。,31,§2運算及其性質,（2）幺元e是唯一的

17、。 用反證法：假設有二個不同的幺元e1和e2,則有e1* e2= e2= e1,這和假設相矛盾?！嗳舸嬖阽墼脑捯欢ㄊ俏ㄒ坏?。,32,§2運算及其性質,例：（1）在實數(shù)集合R中,對+而言, e+=0；對×而言, e*=1 ；（2）在?(E)中,對?而言, e ? =E（全集合）；對?而言, e ? =?（空集）；,33,§2運算及其性質,（3）{雙射函數(shù)}中,對“?”而言， e ? =

18、Ix（恒等函數(shù)）；（4）{命題邏輯}中， 對∨而言，e ∨ =F（永假式）； 對∧而言， e ∧ =T（永真式）。,34,§2運算及其性質,例:設集合S={α,β,γ,δ}，在S上定義的兩個二元運算*和★ 如表所示。試指出左幺元或右幺元。,35,§2運算及其性質,定義：設*是對集合Z中的二元運算， （1）若有一元素θl ?Z，且對每一個x ?Z有θl *x=

19、θl ，則稱θl 為Z中對于*的左零元；（2）若有一元素θr ?Z，且對每一個x ?Z有 x* θr= θr ，則稱θr為Z中對于*的右零元。,36,§2運算及其性質,定理：若θl和θr分別是Z中對于*的左零元和右零元，于是對所有的x ?Z，可有θl = θr =θ，能使θ*x=x*θ=θ。在此情況下，θ ?Z是唯一的，并稱θ是Z中對*的零元。,37,§2運算及其性質,例：（1）在實數(shù)集合R中，對×而言

20、,， θL = θr =0 （2）在?(E)中，對?而言，θ ? = ? ； 對?而言，θ ? = E ；（3）{命題邏輯}中， 對∨而言，θ ∨ =T ； 對∧而言，θ ∧ = F。,38,§2運算及其性質,例題8 設集合S={淺色，深色}，定義在S上的一個二元運算*如表所示。試指出零元和幺元。,39,§2運算及其性質,1）運算?具有封閉性，當且僅當運算表中的每個元素都屬于A。

21、 2）運算?具有可交換性，當且僅當運算表關于主對角線是對稱的。 3）運算?具有等冪性，當且僅當運算表的主對角線上的每一元素與它所在行（列）的表頭元素相同。,40,§2運算及其性質,定義:設代數(shù)結構中? 為二元運算，e為么元，a,b 為A中元素,若b?a＝e，那么稱b為a的左逆元，a為b的右逆元。若a?b＝b?a＝e，那么稱a(b)為b(a)的逆元。 x的逆元通常記為x-1;但當運算被稱為“加法運算

22、”（記為+）時，x的逆元可記為-x 。,41,§2運算及其性質,1） A中關于運算?具有幺元，當且僅當該元素所對應的行和列依次與運算表的行和列相一致。 2） A中關于運算?具有零元，當且僅當該元素所對應的行和列中的元素都與該元素相同。 3） 設A中關于運算?具有幺元，a和b互逆，當且僅當位于a所在行和b所在列的元素及b所在行和a 所在列的元素都是幺元。,42,§2運算及其性質,例: 設集合S={α

23、,β,γ,δ,ζ },定義在S上的一個二元運算*如表所示。試指出代數(shù)系統(tǒng)中各個元素的左、右逆元情況。,43,§2運算及其性質,44,§2運算及其性質,一般地，一個元素的左逆元不一定等于它的右逆元。一個元素可以有左逆元不一定有右逆元。甚至一個元素的左（右）逆元不一定是唯一的。,45,§2運算及其性質,定理：設是代數(shù)系統(tǒng)， *是定義在Z上的一個二元運算，Z中含有幺元e。且每一個元素都有左逆元。如果*是可結合的運

24、算。那么，這個代數(shù)系統(tǒng)中的任何一個元素的左逆元必定是該元素的右逆元，且每個元素的逆元是唯一的。,46,§2運算及其性質,證明：（1）先證左逆元=右逆元：設a,b,c，且b是a的左逆元， c是b的左逆元。因為： （b?a）?b =e ?b = b所以： e=c?b = c ? (（b?a）?b ) = (c ?（b?a） ) ?b

25、 = (（c ?b ）?a ) ?b = (（e ）?a ) ?b =a?b (即b也是a的右逆元),47,§2運算及其性質,（2）證明逆元是唯一的。設a有兩個逆元b1和b2，則有 b1 = b1 ? e = b1 ? （ a ? b2 ） = （ b1 ? a

26、 ） ? b2 = e ? b2 = b2,48,§2運算及其性質,例：試構造一個代數(shù)系統(tǒng)，使得其中只有一個元素具有逆元。,解 ：設m,n?I,T={x|x?I,m≤x≤n},那么，代數(shù)系統(tǒng)中有一個幺元是m,且只有m有逆元，因為m=max(m,m)。,49,§2運算及其性質,例： 對于代數(shù)系統(tǒng)，這里R是實數(shù)的全體，是普通的乘法運算，是否每個元素都有逆元。

27、,解 ：該代數(shù)系統(tǒng)中的幺元是1，除了零元素0外，所有的元素都有逆元。,50,§2運算及其性質,例： 對于代數(shù)系統(tǒng)，這里Nk={0,1,2,…,k-1}, +k是定義在Nk上的模k加法運算，定義如下： 對于任意x,y?Nk x+y 若x+y<k x +ky= x+y-k 若x+y≥ k試問是否每個元素都有逆元。,,51,§2運算及其

28、性質,解: 可以驗證，+k是一個可結合的二元運算，Nk中關于運算+k的幺元是0， Nk中的每一個元素都有唯一的逆元，即0的逆元是0，每個非零元素x的逆元是k-x。,52,§2運算及其性質,推論：(x-1)-1 =x , e-1= e證明：∵ x-1 *x= (x-1)-1 *（ x-1 ）=x* x-1 = e ∴有(x-1)-1 =x∵ e-1 * e= e= e* e ∴有e-1= e,53,&

29、#167;2運算及其性質,例：（1）在實數(shù)集合R中，對“+”運算，任一x?R有 x-1 =-x，∵x+（-x）=0，加法幺元 對“×”運算，對任一x ?R有x-1 =1?x（x?0） ∵x× 1?x =1，乘法幺元；,54,§2運算及其性質,（2）在函數(shù)的合成運算中,每一個雙射函數(shù)都是可逆的， f-1（f的逆關系）；（3）在所有的二元運算中,零元一定不存在逆元，∵θ*x=x*θ=θ。,5

30、5,§3 半群（semigroup ）,半群是一種特殊的代數(shù)系統(tǒng)，它在形式語言、自動機等領域中，都有具體的應用。,學習本節(jié)要掌握如下概念：廣群、半群、子半群、獨異點,56,§3 半群,定義：一個代數(shù)系統(tǒng)，其中S是非空集合，*是S上的一個二元運算，如果運算?是封閉的，則稱代數(shù)系統(tǒng)為廣群。,57,§3 半群,定義： 一個代數(shù)系統(tǒng)，其中S是非空集合，*是S上的一個二元運算，如果：（1）運算?是封閉的；

31、（2）運算*是可結合的，即對任意的x,y,z?S，滿足 (x*y)*z=x*(y*z)則稱代數(shù)系統(tǒng)為半群。,58,§3 半群,例：對于正整數(shù)k，Nk={0,1,2,…,k-1}，設*k是Nk上的一個二元運算，使得a*kb=用k除a·b所得的余數(shù)，這里a，b∈Nk。a)當k=4時，試造出*k的運算表。b)對于任意正整數(shù)k，證明是一個半群。,59,§3 半群,60,§3 半群,b)對于任意

32、的a，b∈Nk ，a*kb= a·b-nk= r，0≤r≤k-1，所以運算*k在Nk上是封閉的。對于任意的a，b，c∈Nk ，有 (a*kb) *kc=(a·b-n1k) ·c- n2k=r1 0≤r1≤k-1 = a·b ·c-k(n1c+n2) a*k ( b *kc)=

33、a·(b ·c -n3k) - n4k=r2 0≤r2≤k-1 = a·b ·c-k(n3a+n4)可見r1和r2都是a·b ·c用k除所得的余數(shù)，所以r1 = r2 。所以(a*kb) *kc= a*k ( b *kc)，即*k滿足結合律。因此，是半群。,61,§3 半群,例題：設S={a,b,c

34、}，在S上的一個二元運算Δ 定義如表所示。驗證是一個半群。,62,§3 半群,解 從運算表中可知運算Δ是封閉的，同時a,b和c都是左幺元。所以，對于任意的x,y,z?S，都有 xΔ(yΔz)=xΔz=z=yΔz=(xΔy)Δz因此，是半群。,63,§3 半群,例：設*是實數(shù)集R上的運算，其定義如下： a*b=a+b+2ab1)求2*3，3*（-5）和7*1/2。2)是

35、半群嗎？*可交換嗎？3)求R中關于*的幺元（單位元）。4)R中哪些元素有逆元，逆元素是什么？,64,§3 半群,解：1) 2*3=17，3*（-5）=-32，7*1/2=14.5,65,§3 半群,2)運算*在R上是封閉的。對任意a，b，c∈R，(a*b)*c=(a+b+2ab)*c=a+b+2ab+c+2(a+b+2ab )c=a+b+c+2ab+2ac+2bc+4abca*(b*c)=a*(b+c+2

36、bc)=a+b+c+2bc+2a(b+c+2bc)=a+b+c+2ab+2ac+2bc+4abc所以(a*b)*c= a*(b*c)。因此是半群。*可交換。,66,§3 半群,3)R中關于*的幺元是0。,4)R中除-1/2外所有元素都有逆元，a的逆元素是-a/（1+2a）。,67,§3 半群,定義：設為一半群, B?S且?在B上封閉，那么也是一個半群，稱為的子半群。,例：設· 表示普通的乘法運算，那么

37、、和都是的子半群。,68,§3 半群,討論定義：（1）因為*在S上是可結合的，而T?S且*在T上是封閉的，所以*在T上也是可結合的。 （2）由定義可知，∵ S?S ，∴ 也是的子半群。為了和其它子半群相互區(qū)別，稱是的“平凡子半群”;,69,§3 半群,練習：若是半群，a∈S， M={an|n ∈ N}，證明是的子半群。,70,§3 半群,證明 只須證明運算*在M上是封閉的。任取an

38、 ， am ∈ M， an * am =（ an * a）* am -1 = an +1 * am -1 =（ an+1 * a）* am -2 = an +2 * am -2 =…… = an +m ∈ M所以是的子半群。,71,

39、67;3 半群,,定理： 設代數(shù)結構為一個半群，如果S是一個有限集合，則必有a?S ，使得a?a=a,72,§3 半群,證明: 因是半群,對于任意b?S，由于?的封閉性可知 b ? b?S 記b2 =b ? b b2 ? b =b ? b2 ?S 記b3 = b2 ? b =b ? b2 ……… b, b2, b3, …, bi, … , bq, … ,

40、bj(最多有|S|個不同元素),73,§3 半群,因S是一個有限集合，所以必存在 j>i，使得 bi = bj 令 p=j-i 即 j =p+i 代入上式： bi = bp ? bi 所以， bq = bp ? bq i≤q 因為p≥1所以總可以找到k≥1，使得 kp≥i

41、 對于bkp ?S，就有 bkp = bp ? bkp = bp ? (bp ? bkp ) = b2p ? bkp = b2p ? (bp ? bkp ) =...= bkp ?bkp,74,§3 半群,定義：設代數(shù)結構為半群，若含有關于 ? 運算的么元,則稱它為獨異點(monoid)，或含么半群。,75,§3 半

42、群,例如：代數(shù)系統(tǒng)是一個獨異點，因為是一個半群，且0是R中關于運算+的幺元。 另外，代數(shù)系統(tǒng),,都是具有幺元1的半群，因此它們都是獨異點。,76,§3 半群,例：設S為非空集合，? (S)是S的冪集， 則 ,均為含幺半群。而，其中max(x1,x2)取二者之大值；，其中min(x1,x2)取二者之小值，均不為幺半群（不存在幺元）。則為含幺半群，其中 e =0,77,§3 半群,代數(shù)系統(tǒng)雖是一個半群，但關于

43、運算+不存在幺元，所以，這個代數(shù)系統(tǒng)不是獨異點。,78,§3 半群,有代數(shù)系統(tǒng)，其中S={a，0，1}，運算*由下表定義，證明是獨異點。,79,§3 半群,證明： 1）運算*是封閉的。,2）對于任意x，y∈S，(x*y)*a=x*y x*(y*a)=x*y(x*y)*0=0 x*(y*0)=x*0=0(x*y)*1=1 x*(y*1)=x*1=1所以運算*是可結

44、合的。,80,§3 半群,證明： 3）a是S中關于運算*的幺元。,因此是獨異點。,81,§3 半群,定理：設是一個獨異點,則在關于運算 ?的運算表中任何兩行或兩列都是不相同的。,82,§3 半群,證明: 因S 中關于?運算的幺元是e，因為對于任意的元素a,b?S，且a≠b時，總有 e ? a = a ≠ b= e ? b 和 a ? e = a ≠ b= b

45、 ? e 所以：在的運算表中不可能有兩行或兩列是相同的。,83,§3 半群,例題：設I是整數(shù)集合，m是任意正整數(shù)，Zm是由模m的同余類組成的同余類集，在Zm上定義兩個二元運算+m和×m分別如下：對于任意的[i]，[j]?Zm [i] +m[j]=[(i+j)(mod m)] [i]×m[j]=[(i×j)(mod m)]試證明在這兩個二元運算的運算表中任何兩行或兩

46、列都是不相同的。,84,§3 半群,證明：考察代數(shù)結構和 ，只須證明和都是獨異點。先分三步證明是獨異點， 1）根據(jù)運算定義，證明兩個運算在Zm上封閉； 2）根據(jù)運算定義，證明兩個運算滿足結合律； 3）根據(jù)運算定義，證明[0]是的幺元，[1]是的幺元。,85,§3 半群,(1)由運算+m和×m的定義，可知它們在Zm上都是封閉的。,(2)對于任意[i]，[j]，[k]?Zm

47、([i]+m[j])+m[k]=[i]+m([j]+m[k]) =[(i+j+k)(mod m)]([i]×m[j])×m[k]=[i]×m([j]×m[k]) =[(i×j×k)(mod m)]即運算+m和×m都是可結合的。,86,§3 半群,(3)因為[0]+m[i]=[i]+m[0]=[i

48、]，所以，[0]是中的幺元。因為[1]×m[i]=[i]×m[1]=[i]，所以[1]是中的幺元。 因此，代數(shù)系統(tǒng)， 都是獨異點。由定理可知，這兩個運算的運算表中任何兩行或兩列都不相同。,87,§3 半群,定理：設是獨異點，對于任意a，b?S，且a， b均有逆元，則 a)(a-1)-1=a b)a*b有逆元，且(a*b)-1=b-1*a-1,88,§3 半群,證明：a

49、)因為a-1是a的逆元，即a* a-1= a-1*a=e 所以 (a-1)-1=a b)因為(a*b)*(b-1*a-1) = a*(b*b-1)*a-1=a*e*a-1=e 同理可證： (b-1*a-1) * (a*b)=e 所以 (a*b)-1=b-1*a-1,89,§4 群與子群,定義：設是一代數(shù)系統(tǒng)，S是非空集合，*為S上的二

50、元運算，它滿足以下四個條件時，則稱為群。（1）*運算是封閉的；（2） *運算是可結合的；（3）存在幺元e；（4）S中每一個元素均有逆元。,90,§4 群與子群,例：, , （其中Z2 ={0,1}, Z3 ={0,1,2} ）， 等均為群 , 只是含幺半群而不是群。,91,§4 群與子群,例：設M= {0º,60º,120º,240º,300&#

51、186;,180º}表示平面上幾何圖形順時針旋轉的六種位置，定義一個二元運算*，對M中任一元素a,b有a*b=圖形旋轉(a+b)的角度，并規(guī)定當旋轉到360º時即為0º， 試驗證是一個群。,92,§4 群與子群,93,§4 群與子群,（1）運算是封閉的（2）*是可結合的（3）幺元為0º ；（4）每一個元素均有逆元：(0º )-1= 0º , (

52、60º )-1=300º ,(120º )-1=240º , (180º )-1= 180º , (240º )-1=12 0º ,(300º )-1= 60º,∴ 是一個群。,94,§4 群與子群,定義：設是一個群，如果G是有限集合，則稱為有限群，并把|G|稱為群的階數(shù)，如果G為無限集合，則稱為無限群。

53、 例：為無限群，上例中為有限群，群的階為|M| =6。,95,§4 群與子群,至此，可以概括地說：廣群僅僅是具有一個封閉的二元運算的非空集合；半群是一個具有結合運算的廣群；獨異點是具有幺元的半群；群是每個元素都有逆元的獨異點。,96,§4 群與子群,（1）群具有半群和含幺半群所具有的所有性質；（2）由于群中存在幺元，所以在群的運算表中一定沒有相同的行（和列）（3）在群中，每一個元素均存在逆元，所以群相對半群和含幺

54、半群來說有一些特殊的性質。,97,§4 群與子群,定理1：一個群中一定不存在零元。,98,§4 群與子群,證明: 因當群的階為1時，它的唯一元素是視作幺元e 。 設|G|>1 且群有零元。那么群中任何元素x ?G，都有 x ? ? = ? ? x = ? ≠ e，所以，零元?就不存在，與是群的假設矛盾。,99,§4 群與子群,定理2：若是一個群，則對任一a,b?G必存在唯一的元素x ?G

55、， 使a * x= b。,100,§4 群與子群,證明: 1）先證解存在性 設a的逆元a-1，令 x = a-1 ? b （構造一個解） a?x＝ a? （ a-1 ? b ） ＝（ a ? a-1 ） ? b ＝ e ? b ＝ b

56、 2）再證解唯一性 若另有解x1滿足a? x1 ＝ b ，則 a-1 ? （a? x1）＝ a-1 ? b x1 ＝ a-1 ? b,101,§4 群與子群,定理3：若是一個群，則對任一a,b,c?G，如果有 a * b = a * c 或b * a = c * a ， 則必 有 b = c。,1

57、02,§4 群與子群,定理4：群的運算表中的每一行或每一列都是G的元素的一個置換。,定義：設S是一個非空集合，從集合S到S的一個雙射稱為S的一個置換。,103,§4 群與子群,如：對于集合S={a,b,c,d}，一個置換如下： a b c d b d a c a b c

58、 d c a d b,,,104,§4 群與子群,證明: 先證G中每一個元素只出現(xiàn)一次 用反證法：設a對應行有兩個元素b1、 b2對應的都是c, 即a?b1＝a?b2＝c,且b1≠b2 由可約性得b1＝b2 與假設矛盾。,105,§4 群與子群,再證G中每一個元素必出現(xiàn)一次 對于元素a?G的那一行，設b是G中的任意一個元

59、素，由于b=a?（a-1?b），所以b必定出現(xiàn)在對應于a的那一行。 再由運算表中任何兩行或兩列都是不相同的。 得出要證的結論。,106,§4 群與子群,定理5：群中，除幺元e外，不可能有別的等冪元。,定義：代數(shù)系統(tǒng)中，如果存在a?G,有a*a=a，則稱a為等冪元。,107,§4 群與子群,證明: 因為e ? e = e ，所以e是等冪元?，F(xiàn)設 a?G， a≠e 且 a ? a= a 則有,a=e?a

60、=(a-1?a)?a =a-1?(a?a)=a-1?a=e,與假設 a≠e 矛盾。,108,§4 群與子群,定義：設為群。S是G的非空子集 ，如果也構成群，則稱 為G的子群(subgroups)。,109,§4 群與子群,定理：設為群，為G的子群，那么， 中的幺元e必定也是中的幺元。,110,§4 群與子群,證明: 設中的幺元為e1 ，對于任意一個元素 x?S?G, 必有 e1 ? x

61、 = x = e ? x 則有 e1 = e,111,§4 群與子群,定義：設為群，為G的子群，如果，S ={e}或S =G，那么稱為 的平凡子群。,112,§4 群與子群,例： 是一個群，設IE={x|x=2n,n?I}，證明是的一個子群。,113,§4 群與子群,證明： (1)對于任意的x,y ?IE，不妨設x=2n1,y=2n2,n1,n2?I,則 x+y=2n1+2n2

62、=2(n1+n2) n1+n2?I 所以 x+y?I 即+在IE上封閉。,114,§4 群與子群,(2)運算+在IE上保持可結合性。,(3)中的幺元0也在IE中。,(4)對于任意的x?IE，必有n使得x=2n，而 -x=-2n=2(-n)，n?I所以-x?IE，而x+(-x)=0，因此，是的一個子群。,115,§4 群與子群,定理：設是一個群，B是G的非空

63、子集，如果B是一個有限集，那么，只要運算*在B上是封閉的，則必定是的子群。,116,§4 群與子群,證明：設b?B，已知*在B上封閉， 則b*b ?B，即 b2 ?B， b2 *b ?B， 即： b3 ?B， 于是b ， b2 ， b3……均在B中。由于B是有限集，∴必存在正整數(shù)i和j，i<j,使得：bi=bj即： bi=bi*bj-i,117,

64、§4 群與子群,由此可說明bj-i是中的幺元，且這個幺元也在子集B中。 如果j-i>1，那么由bj-i=b*bj-i-1 可知bj-i-1是b的逆元， 且bj-i-1 ?B；如果j-i=1，則由bi=bi?b可知b是幺元， 而幺元是以自身為逆元的。因此， 是的一個子群。,118,§4 群與子群,定理:設是一個群，S是G的非空子集，如果對于S中的任意元素a和b有a*b-1?S，則是的

65、子群。,119,§4 群與子群,證明：先證，G中的幺元e也是S中的幺元。任取 a?S， a*a-1?S，而a*a-1＝e，∴e?S 再證，每個元素都有逆元。 又e*a-1?S，即a-1?S。 最后說明，*對S是封閉的。?a,b ?S，因b-1?S， ∴ (b-1)-1 ?S,120,§4 群與子群,a*b=a*(b-1)-1 ?S，而(b-1)-1 ＝b ∴a*b ?S ∴是

66、的子群。,結合律是保持的，證畢。,121,§4 群與子群,例：設G4={p=|pi?{0,1}}，?是上的二元運算，定義為，對任意X=，Y= ?G4， X?Y=， 其中?的運算表如圖所示： 證明,}, ?>是群 的子群。,122,§4 群與子群,例： 設和都是群的子群，試證明也是的子群。,證明：設任意的a,b?H∩K，因為和都是子群，所以b-1?H∩K，由于*在H和K中的封閉性，所以a

67、*b-1?H∩K，由定理即得也是的子群。,123,§5 阿貝爾群（ Abel group ）和循環(huán)群（cyclic group ）,定義：如果群中運算*是可交換的，則稱該群為阿貝爾群（或稱為交換群）。 例： 為阿貝爾群。,124,§5 阿貝爾群（ Abel group ）和循環(huán)群（cyclic group ）,例：離散函數(shù)代數(shù)系統(tǒng)是阿貝爾群。Z={1,2,3,4}，

68、 F={f0 , f1 , f2 , f3 },,1 2 3 4,2 3 4 1,f2 =,,1 2 3 4,3 4 1 2,f3 =,,1 2 3 4,4 1 2 3,f0 =,,1 2 3 4,1 2 3 4,f =,125,§5 阿貝爾群和循環(huán)群,由運算表可見：（1）運算是封閉的；（2）“ ° ”可結合； （

69、3）幺元f0 ；（4）每一個元素均可逆; （5）以主對角線為對稱。 ∴ 為阿貝爾群。,126,§5 阿貝爾群和循環(huán)群,定理：設是一個群， 是阿貝爾群的充分必要條件是對任一a ,b?G有 ： (a*b)*(a*b) = (a*a)*(b*b)。,127,§5 阿貝爾群和循環(huán)群,定義：設是一個群，I 是整數(shù)集合，若存在一個元素a?G，對于G中每一個元素x都能表示成an的形式 （n ? I），

70、 則稱是一個循環(huán)群，a稱為群的生成元（ generater ）。,128,§5 阿貝爾群和循環(huán)群,例： 60º就是群 的生成元，所以該群為循環(huán)群。,129,§5 阿貝爾群和循環(huán)群,例：是一個循環(huán)群， 生成元a=1,生成元不唯一。,130,§5 阿貝爾群和循環(huán)群,定理:每一個循環(huán)群必是阿貝爾群。,131,§5 阿貝爾群和循環(huán)群,證明: 設 是一個循環(huán)群， a是該群的生成元，

71、則對于任意的x,y?G ，必有r,s?I，使得 x= ar 和 y = as 而且 x?y=ar?as=ar+s =as+r =as?ar =y?x 因此，運算?可交換，是阿貝爾群。,132,§5 阿貝爾群和循環(huán)群,例：I為整數(shù)集合?！澳同余”是一個等價關系。設：m=4，N4表示“模4同余”所產(chǎn)生的等價類的集合，N4={[0],[1],[2],[3]}，定義運+4：[i]+4[j]

72、=[(i+j)(mod 4)](i,j=0,1,2,3)則：是群,133,§5 阿貝爾群和循環(huán)群,運算表：,134,§5 阿貝爾群和循環(huán)群,由運算表可見： [0]的階：1 [1]的階：4 [2]的階：2 [3]的階：4,135,§5 阿貝爾群和循環(huán)群,定理：設為循環(huán)群，a?G是該群的生成元，如果G的階數(shù)是n ，即| G |= n ，則an = e,且 G={a, a2,

73、 a3,..., an-2, an-1, an=e} 其中， e是群的幺元。 n是a的階。,,,136,§5 阿貝爾群和循環(huán)群,先證a的階為n 設對于某個正整數(shù)m,m是一個循環(huán)群，所以對于G中任意的元素都能寫為ak (k? I),而且k=mq+r,其中q是某個整數(shù),0≤r<m,則有,,,137,§5 阿貝爾群和循環(huán)群,ak=amq+r =(am)q?ar =(e)q?ar =ar 因此，G中