第8章-群和半群ppt课件.ppt

《第8章-群和半群ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章半群和群8.1半群和独异点半群和独异点的定义子半群和子独异点半群同态和独异点同态代数系统A=＜S，*＞，若*是满足结合律的二元运算，则A称为半群。若*同时满足交换律，则称为阿贝尔半群。存在幺元的半群称为独异点，也称(含)幺半群，单位半群。若*同时满足交换律，则称为阿贝尔独异点。8.1.1半群和独异点的定义例<∑+,·>是最典型的半群，只满足结合律<∑*,·,ε>是最典型的独异点，只满足结合律，有幺元是独异点，可交换独异点是独异点，不满足交换律，部分元素有逆元*abaabbabb)设S={a，b}，

2、*定义如右表：即a，b都是右零元∵x,y,zS①x*yS∴运算封闭②x*（y*z）=x*z=z（x*y）*z=z∴结合律成立∴〈S，*〉是一半群，该半群称为二元素右零半群半群的性质:1.独异点运算表中任何两行或两列均不相同证明：设独异点的幺元为e，a,bS，若ab∵a*eb*e,＜S,*＞运算表中a,b两行不同，由a,b任意性，运算表中任两行不同∵e*ae*b,＜S,*＞运算表中a,b两列不同，由a,b任意性，运算表中任两列不同．2.有限半群一定含有幂等元证明：设〈S，＊〉是半群,S是有限集，需证aS

3、，有a＊a=abS，因为运算封闭，b2=b＊bS,b3,b4…SS有限i，j∈N+，j>i有bi=bjbi=bj=bj-i＊bi令p=j－ibi=bj=bp*bi当q≥i,bq=bp·bq　　(1)又∵p≥1∴k∈N+有kp≥i由(1)bkp=bp＊bkp=bp＊(bp＊bkp)=bp＊(bp＊(bp＊bkp))=...=bp＊…bp＊bkp=bkp＊bkp∴令a=bkpS则a＊a=a∴a是幂等元.k个8.1.2子半群和子独异点设为半群，T为S的非空子集。若T关于*封闭，则称是的子半

4、群，记为T≤S。设为独异点，T为S的非空子集。若T关于*封闭，且e∈T,则称是的子独异点，记为T≤S。例半群有子半群，独异点有子独异点独异点<∑*,·,ε>,设A⊆∑，则是<∑*,·,ε>的子独异点；独异点<∑*,·,ε>，设T={s

5、

6、

7、s

8、

9、>10},是<∑*,·,ε>的子半群，但不是子独异点；独异点，设nN={nm

10、mN},是的子独异点；独异点

11、,1S>，其中S上的单射集合，满射集合和双射集合都是的子独异点。定理设为可交换独异点，T为S中所有幂等元的集合，则是的子独异点。证：(1)T对于*的封闭性∀a,b∈T,a*a=a,b*b=b,又由于*是可交换、可结合的，所以(a*b)*(a*b)=a*(b*a)*b=a*a*b*b=a*b∴(a*b)也是幂等元，a*b∈T.(2)e∈T.∵e*e∈T,∴e∈T.所以是的子独异点。8.1.3半群同态和独异点同态定义设和是半群，

12、函数h:S1→S2.若∀a,b∈S1,有h(a*b)=h(a)•h(b),则称h为从到的半群同态。设和是独异点，函数h:M1→M2.若∀a,b∈M1,有h(a*b)=h(a)•h(b),且h(e1)=e2,则称h为从到的独异点同态。例8.1.4设∑={a,b},<∑*,·,ε>上的函数h:∑*→∑*定义如下：i)h(ε)=ε;ii)h(a·s)=ab·h(s),h(b·s)=ba·h(s)则h是<∑*,·,ε>上的自同态。证：对s用归纳法证

13、明∀s,t∈∑*:h(s·t)=h(s)·h(t)i)s=ε时,h(ε·t)=h(t)=ε·h(t)=h(ε)·h(t),ii)假设s=x时成立，即h(x·t)=h(x)·h(t)则当s’=a·x时，h(s’·t)=h(a·x·t)=ab·h(x·t)=ab·h(x)·h(t)=h(a·x)·h(t)=h(s’)·h(t)当s’=b·x时同理可证。∴∀s,t∈∑*:h(s·t)=h(s)·h(t)又h(ε)=ε，所以h是∑*上的自同态。定理半群与同态证：定义h:S→SS为：∀a∈S,h(a)=fa,其中fa:S→

14、S,∀x∈S,fa(x)=a*x,则h是同态映射，因为：∀a,b∈S,∀c∈Sh(a*b)(c)=fa*b(c)=(a*b)*c=a*b*c(h(a)◦h(b))(c)=(fa◦fb)(c)=fa(fb(c))=a*(b