離散數(shù)學(xué)半群

第五章代數(shù)結(jié)構(gòu)5-3半群授課人：李朔Email:chn.nj.1一、廣群與半群

半群是一種特殊的代數(shù)系統(tǒng)，在計(jì)算機(jī)科學(xué)領(lǐng)域中，如形式語言，自動機(jī)理論等方面，已得到了卓有成效的應(yīng)用。定義5-3.1<S,*>為一個代數(shù)系統(tǒng)，集合S

。*是S上的一個二元運(yùn)算，如果運(yùn)算*是封閉的，則稱代數(shù)系統(tǒng)<S,*>為廣群。定義5-3.2若<S,*>為廣群，且*在S上可結(jié)合，，則稱<S,*>為半群。例如：1）冪集P（A）上對稱差運(yùn)算構(gòu)成半群。2）設(shè)Z為整數(shù)集，+、-、*是數(shù)的加法、減法和乘法，則（Z，+）、（Z，*）都是半群；（Z，-）不是半群。3）Nk={0,1,2,

,k-1}上模k加法成半群。2一、廣群與半群

例題2設(shè)S={a,b,c},S上的一個二元運(yùn)算的定義如下表所示，驗(yàn)證＜S,△＞是半群?！鱝bcaabcbabccabc解：

由上表知運(yùn)算△在S上是封閉的而且對任意x1,x2∈S有x1△x2=x2，且a,b,c都是左幺元，從而對任意的x,y,z∈S都有:x△(y△z)=x△z=z,(x△y)△z=y△z=z因此x△(y△z)=(x△y)△z運(yùn)算△是可結(jié)合的，∴＜S,△＞是半群。

3一、廣群與半群

定理5-3.1設(shè)<S,*>是一個半群，B

S且*在B上封閉，則<B,*>也是一個半群，通常稱為<S,*>的子半群。證明：因*在S上可結(jié)合，而B

S，且*在B上封閉，故*在B上可結(jié)合，故<B,*>為半群。

例如：

為普通乘法，則<[0,1],

>,<0,1>都為<R,

>的子半群。定理5-3.2若<S,*>為半群，且S是有限集，則必有a

S,使a*a=a。

證明：對任b

S,由封閉性知b*b=b2

S,b3=b2*b

S,即是說序列b,b2,b3,…,bi…bj…都為S中元

4一、廣群與半群因S有限，故存在j>i使bi=bj設(shè)P=j-i則bj=bp*bi=bi故bp*bi*b=bi*b即bp*bi+1=bi+1對q>i有bp*bq=bq由于p

1，故存在k

1使kp

i即bp*bkp=bkp這是一個遞推關(guān)系，即bkp=bp*bkp=bp*(bp*bkp)=…=bkp*bkp令bkp=a，即有a*a=a。*本定理說明有限半群必有冪等元。5二、獨(dú)異點(diǎn)

定義5-3.3

含有幺元的半群稱為獨(dú)異點(diǎn)。有時獨(dú)異點(diǎn)也記<S,*,e>。例：（

是普通乘法，+是普通加法）<R,+,0>，<I,

>，<I+,

>，<R,

>都為獨(dú)異點(diǎn)。<N-{0},+>為半群，不含幺元0，故不是獨(dú)異點(diǎn)。代數(shù)系統(tǒng)＜{－1，1}，

＞，＜[－1，1]，

＞，和＜Z,

＞都是具有幺元1的半群。因此它們都是獨(dú)異點(diǎn)。定理5-3.3設(shè)<S,*>為獨(dú)異點(diǎn)，則關(guān)于*的運(yùn)算表中任何兩行或兩列都不同。

證明：設(shè)e為幺元。對任a,b

S,a

ba*e=a

b*e=b可見a,b所在行不同。同理e*a=a

e*b=b即a,b所在列也不同。

6二、獨(dú)異點(diǎn)

例：I為整數(shù)集，Zm為同余類構(gòu)成的集合，定義+m,

m如下：[i],[j]

Zm

[i]+m[j]=[(i+j)modm][i]

m[j]=[(i

j)modm]試證明這兩個運(yùn)算表中任兩行，兩列互異。證明：（這僅需證明<Zm,+m>,<Zm,

m>都為獨(dú)異點(diǎn)即可。）事實(shí)上：1）+m,

m在Zm上封閉。2）對任[i],[j],[k]

Zm

([i]+m[j])+m[k]=[i]+m([i]+m[j])=[(i+j+k)modm]([i]

m[j])

m[k]=[i]

m([i])

m[j])=[(i

j

k)modm]故+m,

m都可結(jié)合。7二、獨(dú)異點(diǎn)

3）[0]+m[i]=[i]+m[0]=[i][1]

m[i]=[i]

m[1]=[i]即[0]，[1]分別為+m,

m的幺元。因此<Zm,+m>,<Zm,

m>都為獨(dú)異點(diǎn)。由定理5-3.3可知，這兩個運(yùn)算的運(yùn)算表中任何兩行或兩列都不相同。

8二、獨(dú)異點(diǎn)由定理知其運(yùn)算表任兩行，兩列互異。在上例中，如果令m=5，則+5和

5的運(yùn)算表分別如下。（沒有兩行/列是相同的）9二、獨(dú)異點(diǎn)定理5-3.4<S,*>為獨(dú)異點(diǎn)，若對任a,b

S，且a,b有逆元a-1,b-1,則1）(a-1)-1=a2）a*b有逆且(a*b)-1=b-1*a-1。證明：1）因a有逆a-1，故a*a-1=a-1*a=e因此(a-1)-1=a2）因(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=a*a-1=a同理(b-1*a-1)*(a*b)=e故(a*