资源描述：
《离散数学课件 第9章 半群和群》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9章半群和群semigroupandgroup§9.1二元运算复习binaryoperationrevisitedA上二元运算f：A×A→Af处处有定义的函数。Dom（f）＝A×A，对任意a，b∈A，f(a，b)∈A，唯一确定。二元运算常记做＋，－，×，*，◦，等等对任意a，b∈A，a◦b∈A说成A对◦封闭。A＝{a1,a2,……,an}时，二元运算可以用运算表给出。二元运算的性质1可换commutativea*b=b*a2结合associativea*(b*c)=(a*b)*c3幂等idempotenta*a=a特殊元素单位元对任意a∈A，e*a=a*e＝a.单位元也叫恒等元零元
2、对任意a∈A，0*a=a*0＝0逆元对任意a，b∈A，a*b=b*a＝ea,b互为逆元代数结构(A,*)A上定义了二元运算满足1)封闭性2)结合律-----------半群3)有单位元---------独异点4)有逆元-----------群5)可交换-----------交换群例子：1)(Zn+),(Zn,´)2)(A*,*)字符串的连接HomeworkP323－32416，20，22，24，25，26§9.2半群semigroup半群定义：(S,*)*是S上乘法，满足结合律。半群的例(Z，＋），（Z，×），（N，×），（N，＋），（Q，＋），（R，×），（P(S),∪），（P(S
3、),∩），（Mn，＋），（Mn，×），S上全体映射，对于复合，（L，∧），（L，∨），L是格（A*,×）,定理1.半群中，n个元素的乘积与乘法的次序无关。幂power：设（S，*）是半群，a∈S，定义a的幂power：a1＝a，an=an-1*a.a0=？a-n=?am*an=am+n(am)n=amn.子半群subsemigroup子独异点submonoid设（S，*）是半群，TÍS，T对*封闭，则（T，*）也是半群，称为（S，*）的子半群。设（S，*）是独异点，TÍS，T对*封闭，且e∈T，则（T，*）也是独异点，称为（S，*）的子独异点。（N，＋），（Z，＋），（Q，＋），（R
4、，＋）前一个是后一个的子半群，也是子独异点。（N，×），（Z，×），（Q，×），（R，×）前一个是后一个的子半群，也是子独异点。设（S，*）是半群，（S，*）是（S，*）的子半群。设（S，*）是独异点，（S，*）是（S，*）的子独异点。设（S，*）是独异点，({e},*)是（S，*）的子独异点。同构isomorphism和同态homomorphism同构设（S，*）和（T，*’）是两个半群，函数f：S→T是一一对应，"a，b∈S，f(a*b)=f(a)*’f(b).称（S，*）和（T，*’）同构，记做（S，*）@（T，*’）.验证两个半群（S，*）和（T，*’）同构的方法：定义一个映
5、射f：S→T，证明(1)f单，f(a)=f(b)Þa=b.(2)f满，Ran(f)=T.(3)f保持运算f(a*b)=f(a)*’f(b).例.令T＝{2n
6、n∈Z}，则且（Z，＋）@（T，×）。证明.令f：Z→T，对任意n∈Z，f(n)=2n.（1）f处处有定义.（2）f单:f(m)=f(n),即2m=2nÞm=n。（1）f满.（2）f保持运算：f(m+n)=2m+n=2m×2n=f(m)×f(n)定理2.若S，T同构，则恒等元对应恒等元，零元对应零元，逆元对应逆元。同态Homomorphisim在同构的三个条件中，若仅满足(3)叫做同态。若仅满足(1)(3)称为同构嵌入。若仅满足
7、(2)(3)叫做满同态。例20．设A＝{0，1}，则自由半群（A*,×）与（A，＋）同态，（A，＋）的二元运算＋由乘法表给出：＋01001110例.(Z,+)»(Zn,+),(Z,×)»（Zn，×）.定理3.恒等元的满同态像是恒等元设（S，*），（T，*）是独异点，恒等元分别是e和e’，同态f:（S，*）»（T，*’）,则f(e)=e’.定理4.子半群的同态像是子半群。证明.设f：（S，*）»（T，*’）是半群同态，S’是（S，*）的子半群，则f(S’)是（T，*’）的子半群。只要证f(S’)对运算封闭。设t1,t2∈f(S’)，要证t1*’t2∈f(S’).存在s1，s2∈S’，f
8、(s1)＝t1，f(s2)＝t2，t1*’t2=f(s1)*’f(s2)=f(s1*’s2)∈f(S’).定理5.交换半群的同态像是交换半群。设f：（S，*）»（T，*’）是到上半群同态，（S，*）是交换半群，则（T，*’）的交换半群。证明.任意t1,t2∈T，要证t1*’t2＝t2*’t1.存在s1，s2∈S，f(s1)＝t1，f(s2)＝t2，t1*’t2=f(s1)*’f(s2)=f(s1*’s2)＝f(s2*’s1)＝f(s2)*’f(s1)＝t2
