離散數(shù)學(xué)第5章

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

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

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

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

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

6、3;a=bΔa所以運(yùn)算Δ 是可交換的。,12,§2運(yùn)算及其性質(zhì),定義:設(shè)*是集合S上的二元運(yùn)算,對(duì)任一x,y,z ?S都有 （x ? y）? z=x ?（y ? z）,則稱?運(yùn)算在S上是可結(jié)合的（associative ）或者說*在S上滿足結(jié)合律。,13,§2運(yùn)算及其性質(zhì),例題:設(shè)A是一個(gè)非空集合， ★是A上的二元運(yùn)算，對(duì)于任意a,b?A,有a★b=b，證明★是可結(jié)合運(yùn)算。,證明 因?yàn)閷?duì)于任意的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運(yùn)算及其性質(zhì),定義:設(shè)?和?是集合S上的二個(gè)二元運(yùn)算,對(duì)任一x,y,z ?S有 x ?（y ? z）=（x ? y）?（x ? z）； （y ? z）? x=（y ? x）?（z ? x）, 則稱運(yùn)算?對(duì)?是可分配的（distributive ）或稱?對(duì)?滿足分配律。,15,&#

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、算。那么，這個(gè)代數(shù)系統(tǒng)中的任何一個(gè)元素的左逆元必定是該元素的右逆元，且每個(gè)元素的逆元是唯一的。,46,§2運(yùn)算及其性質(zhì),證明：（1）先證左逆元=右逆元：設(shè)a,b,c，且b是a的左逆元， c是b的左逆元。因?yàn)椋?（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運(yùn)算及其性質(zhì),（2）證明逆元是唯一的。設(shè)a有兩個(gè)逆元b1和b2，則有 b1 = b1 ? e = b1 ? （ a ? b2 ） = （ b1 ? a

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

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

28、性質(zhì),解: 可以驗(yàn)證，+k是一個(gè)可結(jié)合的二元運(yùn)算，Nk中關(guān)于運(yùn)算+k的幺元是0， Nk中的每一個(gè)元素都有唯一的逆元，即0的逆元是0，每個(gè)非零元素x的逆元是k-x。,52,§2運(yùn)算及其性質(zhì),推論：(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運(yùn)算及其性質(zhì),例：（1）在實(shí)數(shù)集合R中，對(duì)“+”運(yùn)算，任一x?R有 x-1 =-x，∵x+（-x）=0，加法幺元 對(duì)“×”運(yùn)算，對(duì)任一x ?R有x-1 =1?x（x?0） ∵x× 1?x =1，乘法幺元；,54,§2運(yùn)算及其性質(zhì),（2）在函數(shù)的合成運(yùn)算中,每一個(gè)雙射函數(shù)都是可逆的， f-1（f的逆關(guān)系）；（3）在所有的二元運(yùn)算中,零元一定不存在逆元，∵θ*x=x*θ=θ。,5

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

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

32、的a，b∈Nk ，a*kb= a·b-nk= r，0≤r≤k-1，所以運(yùn)算*k在Nk上是封閉的。對(duì)于任意的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滿足結(jié)合律。因此，是半群。,61,§3 半群,例題：設(shè)S={a,b,c

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

35、半群?jiǎn)幔?可交換嗎？3)求R中關(guān)于*的幺元（單位元）。4)R中哪些元素有逆元，逆元素是什么？,64,§3 半群,解：1) 2*3=17，3*（-5）=-32，7*1/2=14.5,65,§3 半群,2)運(yùn)算*在R上是封閉的。對(duì)任意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中關(guān)于*的幺元是0。,4)R中除-1/2外所有元素都有逆元，a的逆元素是-a/（1+2a）。,67,§3 半群,定義：設(shè)為一半群, B?S且?在B上封閉，那么也是一個(gè)半群，稱為的子半群。,例：設(shè)· 表示普通的乘法運(yùn)算，那么

37、、和都是的子半群。,68,§3 半群,討論定義：（1）因?yàn)?在S上是可結(jié)合的，而T?S且*在T上是封閉的，所以*在T上也是可結(jié)合的。 （2）由定義可知，∵ S?S ，∴ 也是的子半群。為了和其它子半群相互區(qū)別，稱是的“平凡子半群”;,69,§3 半群,練習(xí)：若是半群，a∈S， M={an|n ∈ N}，證明是的子半群。,70,§3 半群,證明 只須證明運(yùn)算*在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è)代數(shù)結(jié)構(gòu)為一個(gè)半群，如果S是一個(gè)有限集合，則必有a?S ，使得a?a=a,72,§3 半群,證明: 因是半群,對(duì)于任意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|個(gè)不同元素),73,§3 半群,因S是一個(gè)有限集合，所以必存在 j>i，使得 bi = bj 令 p=j-i 即 j =p+i 代入上式： bi = bp ? bi 所以， bq = bp ? bq i≤q 因?yàn)閜≥1所以總可以找到k≥1，使得 kp≥i

41、 對(duì)于bkp ?S，就有 bkp = bp ? bkp = bp ? (bp ? bkp ) = b2p ? bkp = b2p ? (bp ? bkp ) =...= bkp ?bkp,74,§3 半群,定義：設(shè)代數(shù)結(jié)構(gòu)為半群，若含有關(guān)于 ? 運(yùn)算的么元,則稱它為獨(dú)異點(diǎn)(monoid)，或含么半群。,75,§3 半

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

43、運(yùn)算+不存在幺元，所以，這個(gè)代數(shù)系統(tǒng)不是獨(dú)異點(diǎn)。,78,§3 半群,有代數(shù)系統(tǒng)，其中S={a，0，1}，運(yùn)算*由下表定義，證明是獨(dú)異點(diǎn)。,79,§3 半群,證明： 1）運(yùn)算*是封閉的。,2）對(duì)于任意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所以運(yùn)算*是可結(jié)

44、合的。,80,§3 半群,證明： 3）a是S中關(guān)于運(yùn)算*的幺元。,因此是獨(dú)異點(diǎn)。,81,§3 半群,定理：設(shè)是一個(gè)獨(dú)異點(diǎn),則在關(guān)于運(yùn)算 ?的運(yùn)算表中任何兩行或兩列都是不相同的。,82,§3 半群,證明: 因S 中關(guān)于?運(yùn)算的幺元是e，因?yàn)閷?duì)于任意的元素a,b?S，且a≠b時(shí)，總有 e ? a = a ≠ b= e ? b 和 a ? e = a ≠ b= b

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

46、列都是不相同的。,84,§3 半群,證明：考察代數(shù)結(jié)構(gòu)和 ，只須證明和都是獨(dú)異點(diǎn)。先分三步證明是獨(dú)異點(diǎn)， 1）根據(jù)運(yùn)算定義，證明兩個(gè)運(yùn)算在Zm上封閉； 2）根據(jù)運(yùn)算定義，證明兩個(gè)運(yùn)算滿足結(jié)合律； 3）根據(jù)運(yùn)算定義，證明[0]是的幺元，[1]是的幺元。,85,§3 半群,(1)由運(yùn)算+m和×m的定義，可知它們?cè)赯m上都是封閉的。,(2)對(duì)于任意[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)]即運(yùn)算+m和×m都是可結(jié)合的。,86,§3 半群,(3)因?yàn)閇0]+m[i]=[i]+m[0]=[i

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

49、)因?yàn)閍-1是a的逆元，即a* a-1= a-1*a=e 所以 (a-1)-1=a b)因?yàn)?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è)是一代數(shù)系統(tǒng)，S是非空集合，*為S上的二

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

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

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

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

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

55、， 使a * x= b。,100,§4 群與子群,證明: 1）先證解存在性 設(shè)a的逆元a-1，令 x = a-1 ? b （構(gòu)造一個(gè)解） 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：若是一個(gè)群，則對(duì)任一a,b,c?G，如果有 a * b = a * c 或b * a = c * a ， 則必 有 b = c。,1

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

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

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

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

61、 = x = e ? x 則有 e1 = e,111,§4 群與子群,定義：設(shè)為群，為G的子群，如果，S ={e}或S =G，那么稱為 的平凡子群。,112,§4 群與子群,例： 是一個(gè)群，設(shè)IE={x|x=2n,n?I}，證明是的一個(gè)子群。,113,§4 群與子群,證明： (1)對(duì)于任意的x,y ?IE，不妨設(shè)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)運(yùn)算+在IE上保持可結(jié)合性。,(3)中的幺元0也在IE中。,(4)對(duì)于任意的x?IE，必有n使得x=2n，而 -x=-2n=2(-n)，n?I所以-x?IE，而x+(-x)=0，因此，是的一個(gè)子群。,115,§4 群與子群,定理：設(shè)是一個(gè)群，B是G的非空

63、子集，如果B是一個(gè)有限集，那么，只要運(yùn)算*在B上是封閉的，則必定是的子群。,116,§4 群與子群,證明：設(shè)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是中的幺元，且這個(gè)幺元也在子集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是幺元， 而幺元是以自身為逆元的。因此， 是的一個(gè)子群。,118,§4 群與子群,定理:設(shè)是一個(gè)群，S是G的非空子集，如果對(duì)于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 再證，每個(gè)元素都有逆元。 又e*a-1?S，即a-1?S。 最后說明，*對(duì)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、的子群。,結(jié)合律是保持的，證畢。,121,§4 群與子群,例：設(shè)G4={p=|pi?{0,1}}，?是上的二元運(yùn)算，定義為，對(duì)任意X=，Y= ?G4， X?Y=， 其中?的運(yùn)算表如圖所示： 證明,}, ?>是群 的子群。,122,§4 群與子群,例： 設(shè)和都是群的子群，試證明也是的子群。,證明：設(shè)任意的a,b?H∩K，因?yàn)楹投际亲尤?，所以b-1?H∩K，由于*在H和K中的封閉性，所以a

67、*b-1?H∩K，由定理即得也是的子群。,123,§5 阿貝爾群（ Abel group ）和循環(huán)群（cyclic group ）,定義：如果群中運(yùn)算*是可交換的，則稱該群為阿貝爾群（或稱為交換群）。 例： 為阿貝爾群。,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)群,由運(yùn)算表可見：（1）運(yùn)算是封閉的；（2）“ ° ”可結(jié)合； （

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

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

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

72、=[(i+j)(mod 4)](i,j=0,1,2,3)則：是群,133,§5 阿貝爾群和循環(huán)群,運(yùn)算表：,134,§5 阿貝爾群和循環(huán)群,由運(yùn)算表可見： [0]的階：1 [1]的階：4 [2]的階：2 [3]的階：4,135,§5 阿貝爾群和循環(huán)群,定理：設(shè)為循環(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è)對(duì)于某個(gè)正整數(shù)m,m是一個(gè)循環(huán)群，所以對(duì)于G中任意的元素都能寫為ak (k? I),而且k=mq+r,其中q是某個(gè)整數(shù),0≤r<m,則有,,,137,§5 阿貝爾群和循環(huán)群,ak=amq+r =(am)q?ar =(e)q?ar =ar 因此，G中