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

離散數(shù)學(xué)半群第1頁，共13頁，2023年，2月20日，星期一一、廣群與半群

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

。*是S上的一個二元運算，如果運算*是封閉的，則稱代數(shù)系統(tǒng)<S,*>為廣群。定義5-3.2

若<S,*>為廣群，且*在S上可結(jié)合，，則稱<S,*>為半群。例如：

1）冪集P（A）上對稱差運算構(gòu)成半群。

2）設(shè)Z為整數(shù)集，+、-、*是數(shù)的加法、減法和乘法，則（Z，+）、（Z，*）都是半群；（Z，-）不是半群。

3）Nk={0,1,2,,k-1}上模k加法成半群。第2頁，共13頁，2023年，2月20日，星期一一、廣群與半群

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

由上表知運算△在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運算△是可結(jié)合的，∴＜S,△＞是半群。

第3頁，共13頁，2023年，2月20日，星期一一、廣群與半群

定理5-3.1

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

例如：為普通乘法，則<[0,1],>,<0,1>都為<R,>的子半群。定理5-3.2

若<S,*>為半群，且S是有限集，則必有aS,使a*a=a。

證明：對任bS,由封閉性知

b*b=b2S,b3=b2*bS,即是說序列b,b2,b3,…,bi

…bj

…都為S中元

第4頁，共13頁，2023年，2月20日，星期一一、廣群與半群因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由于p1，故存在k1使kpi即bp*bkp=bkp這是一個遞推關(guān)系，即bkp=bp*bkp=bp*(bp*bkp)=…=bkp*bkp令bkp=a，即有a*a=a。*本定理說明有限半群必有冪等元。第5頁，共13頁，2023年，2月20日，星期一二、獨異點

定義5-3.3

含有幺元的半群稱為獨異點。有時獨異點也記<S,*,e>。例：（是普通乘法，+是普通加法）<R,+,0>，<I,>，<I+,>，<R,>都為獨異點。<N-{0},+>為半群，不含幺元0，故不是獨異點。代數(shù)系統(tǒng)＜{－1，1}，＞，＜[－1，1]，＞，和＜Z,＞都是具有幺元1的半群。因此它們都是獨異點。定理5-3.3設(shè)<S,*>為獨異點，則關(guān)于*的運算表中任何兩行或兩列都不同。

證明：設(shè)e為幺元。對任a,bS,aba*e=ab*e=b可見a,b所在行不同。同理e*a=ae*b=b

即a,b所在列也不同。

第6頁，共13頁，2023年，2月20日，星期一二、獨異點

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

[i]+m[j]=[(i+j)modm][i]m[j]=[(ij)modm]試證明這兩個運算表中任兩行，兩列互異。證明：（這僅需證明<Zm,+m>,<Zm,m>都為獨異點即可。）事實上：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])=[(ijk)modm]故+m,m都可結(jié)合。第7頁，共13頁，2023年，2月20日，星期一二、獨異點

3）[0]+m[i]=[i]+m[0]=[i][1]m[i]=[i]m[1]=[i]即[0]，[1]分別為+m,m的幺元。因此<Zm,+m>,<Zm,m>都為獨異點。由定理5-3.3可知，這兩個運算的運算表中任何兩行或兩列都不相同。

第8頁，共13頁，2023年，2月20日，星期一二、獨異點由定理知其運算表任兩行，兩列互異。在上例中，如果令m=5，則+5和5的運算表分別如下。（沒有兩行/列是相同的）第9頁，共13頁，2023年，2月20日，星期一二、獨異點定理5-3.4<S,*>為獨異點，若對任a,bS，且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*b)-1=b-1*a-1第10頁，共13頁，2023年，2月20日，星期一二、獨異點例：n階方陣的集合，對矩陣乘法，若