离散数学课件第9章半群和群.doc

第9章 半群和群semigroup and group§9.1 二元运算复习binary operation revisitedA上二元运算 f：A×A→A f处处有定义的函数 Dom〔f〕＝A×A， 对任意a，b∈A，f(a，b)∈A，唯一确定二元运算常记做＋，－，×，*，◦，等等对任意a，b∈A，a◦b∈A 说成A对◦封闭A＝{a1,a2,……,an}时，二元运算可以用运算表给出二元运算的性质 1可换mutative a*b=b*a 2 结合associative a*(b*c)=(a*b)*c 3 幂等idempotent a*a=a特殊元素单位元对任意a∈A，e*a=a*e＝a. 单位元也叫恒等元零元对任意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*, *) 字符串的连接Homework P323－32416，20，22，24，25，26§9.2 半群semigroup半群定义：(S,*) *是S上乘法，满足结合律。

半群的例 (Z，＋〕，〔Z，×〕， 〔N，×〕，〔N，＋〕， 〔Q，＋〕，〔R，×〕， 〔P(S),∪〕，〔P(S), ∩〕， 〔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，＋〕前一个是后一个的子半群，也是子独异点〔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，*’〕同构的方法：定义一个映射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 | n∈Z}，则且〔Z，＋〕@〔T，×〕证明. 令f：Z→T， 对任意n∈Z，f(n)= 2n.（1） f处处有定义.（2） f单:f(m)=f(n), 即 2m=2nÞm=n3） f满.（4） f保持运算： f(m+n)= 2m+n=2m×2n =f(m)×f(n)定理2. 假设S，T同构，则恒等元对应恒等元，零元对应零元，逆元对应逆元同态Homomorphisim在同构的三个条件中，假设仅满足(3)叫做同态假设仅满足(1)(3)称为同构嵌入假设仅满足(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(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*’t1.Homework P330－33113，16，18，19，23，26，28，31§9.3 乘积半群和商半群Products and Quotiens Semigroup定理1. 乘积半群设〔S，*〕和〔T，*’〕是两个半群，则〔S×T，*〞〕也是半群。

(s1, t1)*〞 (s2, t2)=( s1*s2, t1*’t2 ).设〔S，*〕和〔T，*’〕是两个独异点，则〔S×T，*〞〕也是独异点，恒等元是〔e，e’〕同余关系〔合同关系〕congruence relation设〔S，*〕是半群，R是S上等价关系R称为S上同余关系：aRa’, bRb’Þ(a*b)R(a’*b’).例1. Z上剩余关系是(Z,＋)上同余关系：aºb〔mod 2〕Û 2 | a－b证明. aºb〔mod 2〕是等价关系aºb〔mod 2〕, 2 | a-b, a-b=2k.cºd〔mod 2〕, 2 | c-d, c-d=2t.(a+c)－(b+d)=(a-b)+(c-d)=2(k+t)a+c º b+d〔mod 2〕aºb〔mod 2〕是(Z,＋)上同余关系Z上剩余关系是(Z,×)上同余关系. 例2．令A＝{0,1},自由半群〔A*,×〕上关系R：αRβÛα，β含有同样多个1则R是〔A*,×〕上同余关系例3．设f(*)=*2-*-2, 令〔Z，＋〕上关系R：aRb Û f(a)=f(b).R是Z上等价关系，但不是同余关系 －1R2，f(－1)=f(2)=0 －2R3，f(-2)=f(3)=4-1+-2=-3, 2+3=5 f(-3)=10, f(5)=18 -1+-2 与 2＋3 不满足R。

定理2. 设R是半群〔S，*〕上同余关系定义商集S/R上二元运算*：[a]*[b]=[a*b]则〔S/R,*〕是半群证明. 设[a]=[a’], [b]=[b’],要证[a*b]=[ a’*b’]aRa’, bRb’,由*是同余关系a*bRa’*b’,因此[a*b]=[ a’*b’]，*是映射，二元运算还要证*满足结合律：[a]*([b]*[c])=[a]*[b*c]=[a*(b*c)]=[(a*b)*c]=[a*b]*[c]=([a]*[b])*[c]因此〔S/R,*〕是半群称S/R为商半群推论1. 设R是独异点〔S，*〕上同余关系，则〔S/R,*〕是独异点证明.恒等元e∈S,只要证明[e]是S/R,的恒等元任何a∈S，[a]*[e]=[a*e]=[a][e]*[a]=[e*a]=[a].例5．〔Zn,+〕,(Zn，×)都是半群，独异点Zn＝{[0],[1],[2],……,[n-1]}[m]+[n]=[m+n]定理3.令R是半群〔S，*〕上同余关系,〔S/R,*〕是商半群f：S→S/R, f(a)=[a],则f是满同态，称f为自然同态定理4.同态根本定理设f:〔S，*〕→〔T，*’〕是两个半群间的满同态映射，令R是S上二元关系：a,b∈S，aRbÛf(a)=f(b).则(a) R是〔S，*〕上同余关系。

b) (T，*’)@(S/R,*).Homework P337-3384,10,14,16,22,24§9.4 群Group群的定义群〔G，*〕是一个代数系统，1) 封闭2〕 结合律,2〕有单位元e， a*e=e*a=a,3) 对每个a∈G，存在a’∈G，a*a’=a’*a=e, 称a’为a的逆元群〔G，*〕是一个有单位元的独异点，对每个a∈G，存在逆元a’∈G，使a*a’=a’*a=e.群〔G，*〕常简记为G，a*b常简记为ab可换群叫Abel群 Abelian Group群的例 (Z，＋〕， 〔Q，＋〕，〔Q\{0}，×〕， 〔R，＋〕，〔R\{0}，×〕， 〔Zn，＋〕， 〔Mn，＋〕， S上全体一一对应，对于复合，最后一个不是Abel群例〔R，*〕：a*b=ab/2是Abel群群的性质定理1. 群的逆元唯一：设G是群，任意a∈G，a只有一个逆元，记做a-1证明.设a’，a〞都是a的逆，a’=a’aa〞=a〞.定理2. 群有消去律：设G是群，a,b,c∈G,则（a） ab＝acÞb＝c，（b） ba＝caÞb＝c设G={a1,a2,……,an} 任意a∈G，aG=G.定理3. 逆律设G是群，a,b∈G, 则(a) (a-1)-1=a,(b) (ab)-1=b-1a-1.〔c〕(an)-1＝(a-1)n定理4. 方程有唯一解设G是群，a,b∈G,则(a) 方程a*＝b在G中有唯一解。

b) 方程ya＝b在G中有唯一解群G的阶: |G|.|G|有限时称G为有限群元素的阶a∈G，a的阶：使ak＝e的最小的k如无这样的k，称a为无限阶a无限阶，任意n∈Z+，an≠e.子群subgroup HÍG，H对于G的运算*构成群H是G的子群当且仅当（1） e∈H（2） a，b∈HÞab∈H（3） a∈HÞa-1∈HH是G的子群当且仅当 a，b∈HÞab-1∈H.子群的例设G是群，H＝{e}是子群G是群，a∈G，H＝{ak | k∈Z}是子群，叫做a生成的子群命题. 一个群的任意两个子群的交仍是子群循环群cycle group存在a∈G ，任意*∈G，*＝ak，k∈Za的阶是n，G＝{e,a,a2,……,an-1} ak的逆是an-ka无限阶，G＝{……,a-2,a-1,e,a,a。