




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
離散數(shù)學半群第一頁,共十三頁,2022年,8月28日一、廣群與半群
半群是一種特殊的代數(shù)系統(tǒng),在計算機科學領(lǐ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)設Z為整數(shù)集,+、-、*是數(shù)的加法、減法和乘法,則(Z,+)、(Z,*)都是半群;(Z,-)不是半群。
3)Nk={0,1,2,,k-1}上模k加法成半群。第二頁,共十三頁,2022年,8月28日一、廣群與半群
例題2設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,△>是半群。
第三頁,共十三頁,2022年,8月28日一、廣群與半群
定理5-3.1
設<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中元
第四頁,共十三頁,2022年,8月28日一、廣群與半群因S有限,故存在j>i使bi=bj設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。*本定理說明有限半群必有冪等元。第五頁,共十三頁,2022年,8月28日二、獨異點
定義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設<S,*>為獨異點,則關(guān)于*的運算表中任何兩行或兩列都不同。
證明:設e為幺元。對任a,bS,aba*e=ab*e=b可見a,b所在行不同。同理e*a=ae*b=b
即a,b所在列也不同。
第六頁,共十三頁,2022年,8月28日二、獨異點
例: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é)合。第七頁,共十三頁,2022年,8月28日二、獨異點
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可知,這兩個運算的運算表中任何兩行或兩列都不相同。
第八頁,共十三頁,2022年,8月28日二、獨異點由定理知其運算表任兩行,兩列互異。在上例中,如果令m=5,則+5和5的運算表分別如下。(沒有兩行/列是相同的)第九頁,共十三頁,2022年,8月28日二、獨異點定理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第十頁,共十三頁,2022年,8月28日二、獨異點例:n階方陣的集
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 下水道合同范例
- 會務公司簡易合同范例
- 樂器買賣合同范例
- 公路工程拆遷合同范例
- 入股投資協(xié)議合同范例
- 關(guān)于長期合同范例
- 農(nóng)地菜園租賃合同范例
- 買期房定金合同范例
- 公墓石材安裝合同范例
- 關(guān)于餐飲加盟合同范例
- 新版基本公共衛(wèi)生服務健康教育培訓課件
- 六年級上冊音樂課件 《校園小戲迷》人音版
- 2023版北京協(xié)和醫(yī)院重癥醫(yī)學科診療常規(guī)
- 千里江山圖解析課件
- 《現(xiàn)代漢語常用字表》3500個漢字
- 道路通行能力計算題
- 經(jīng)濟學基礎(chǔ)完整版ppt-全體教學教程課件最新
- JJF(湘) 09-2018 純水-超純水系統(tǒng)監(jiān)測儀表(電導率)計量校準規(guī)范-(高清現(xiàn)行)
- SJG 82-2020 政府投資學校建筑室內(nèi)裝修材料空氣污染控制標準-高清現(xiàn)行
- 智慧園區(qū)平臺用戶操作手冊
- 精品市政道路施工測量方法及測量方案
評論
0/150
提交評論