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

1、-第9章 半群和群semigroup and group9.1 二元运算复习binary operation revisitedA上二元运算 f：AAA f处处有定义的函数。 DomfAA， 对任意a，bA，f(a，b)A，唯一确定。二元运算常记做，*，等等对任意a，bA，abA 说成A对封闭。Aa1,a2,an时，二元运算可以用运算表给出。二元运算的性质 1可换mutative a*b=b*a 2 结合associative a*(b*c)=(a*b)*c 3 幂等idempotent a*a=a特殊元素单位元对任意aA，e*a=a*ea. 单位元也叫恒等元零元对任意aA，0*a=a*00 逆元对任意a，bA，a*b=b*aea,b互为逆元代数构造(A,*)A上定义了二元运算满足1)封闭性2)结合律-半群3)有单位元-独异点4)有逆元-群5)可交换-交换群例子：1) (Zn +), (Zn,)2) (A*, *) 字符串的连接Homework P32332416，20，22，24，25，269.2 半群semigroup半群定义：(S,*) *是S上乘法，满足结合律。半群的例 (Z，

2、Z， N，N， Q，R， P(S),，P(S), ， Mn，Mn， S上全体映射，对于复合， L，L，L是格 A*, , 定理1. 半群中，n个元素的乘积与乘法的次序无关。幂power：设S，*是半群，aS，定义a的幂power： a1a， an=an-1*a.a0=.a-n=?am*an=am+n(am)n=amn.子半群subsemigroup 子独异点submonoid设S，*是半群，TS，T对*封闭，则T，*也是半群，称为S，*的子半群。设S，*是独异点，TS，T对*封闭，且eT，则T，*也是独异点，称为S，*的子独异点。N，Z，Q，R，前一个是后一个的子半群，也是子独异点。N，Z，Q，R，前一个是后一个的子半群，也是子独异点。设S，*是半群，S，*是S，*的子半群。设S，*是独异点，S，*是S，*的子独异点。设S，*是独异点， (e,*)是S，*的子独异点。同构isomorphism和同态 homomorphism同构设S，*和T，*是两个半群，函数f：ST是一一对应，a，bS， f(a*b)=f(a)*f(b).称S，*和T，*同构，记做S，*T，*.验证两个半群S，*和T

3、，*同构的方法：定义一个映射f：ST，证明(1) f 单，f(a)=f(b)a=b.(2) f 满，Ran(f)=T.(3) f保持运算f(a*b)=f(a)*f(b).例. 令T2n | nZ，则且Z，T，。证明. 令f：ZT， 对任意nZ，f(n)= 2n.（1） f处处有定义.（2） f单:f(m)=f(n), 即 2m=2nm=n。（3） f满.（4） f保持运算： f(m+n)= 2m+n=2m2n =f(m)f(n)定理2. 假设S，T同构，则恒等元对应恒等元，零元对应零元，逆元对应逆元。同态Homomorphisim在同构的三个条件中，假设仅满足(3)叫做同态。假设仅满足(1)(3)称为同构嵌入。假设仅满足(2)(3)叫做满同态。例20 设A0，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，*的

4、子半群，则f(S)是T，*的子半群。只要证f(S)对运算封闭。设t1,t2f(S)，要证t1*t2f(S).存在s1，s2S， f(s1)t1，f(s2)t2， t1*t2= f(s1)*f(s2) = f(s1*s2)f(S).定理5.交换半群的同态像是交换半群。设f：S，* T，*是到上半群同态，S，*是交换半群，则T，*的交换半群。证明. 任意t1,t2T， 要证t1*t2t2*t1. 存在s1，s2S， 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 P33033113，16，18，19，23，26，28，319.3 乘积半群和商半群Products and Quotiens Semigroup定理1. 乘积半群设S，*和T，*是两个半群，则ST，*也是半群。 (s1, t1)* (s2, t2)=( s1*s2, t1*t2 ).设S，*和T，*是两个独异点，则ST，*也是独异点，恒等元是e，e。同余关系合同关系congruence relation设S，*是半群，

5、R是S上等价关系。R称为S上同余关系：aRa, bRb(a*b)R(a*b).例1. Z上剩余关系是(Z,)上同余关系：abmod 2 2 | ab。证明. abmod 2是等价关系。abmod 2, 2 | a-b, a-b=2k.cdmod 2, 2 | c-d, c-d=2t.(a+c)(b+d)=(a-b)+(c-d)=2(k+t)a+c b+dmod 2abmod 2是(Z,)上同余关系。Z上剩余关系是(Z,)上同余关系. 例2令A0,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 与 23 不满足R。定理2. 设R是半群S，*上同余关系。定义商集S/R上二元运算*：a*b=a*b。则S/R,*是半群。证明. 设a=a, b=b,要证a*b= a*baRa, bRb,由*是同余关系a*bRa*b,因此

6、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,*是独异点。证明.恒等元eS,只要证明e是S/R,的恒等元。任何aS，a*e=a*e=ae*a=e*a=a.例5Zn,+,(Zn，)都是半群，独异点。Zn0,1,2,n-1m+n=m+n定理3.令R是半群S，*上同余关系,S/R,*是商半群。f：SS/R, f(a)=a,则f是满同态，称f为自然同态。定理4.同态根本定理设f:S，*T，*是两个半群间的满同态映射，令R是S上二元关系：a,bS，aRbf(a)=f(b).则(a) R是S，*上同余关系。(b) (T，*)(S/R,*).Homework P337-3384,10,14,16,22,249.4 群Group群的定义群G，*是一个代数系统，1) 封闭2 结合律,2有单位元e， a*e=e*a=a,3) 对每个aG，存在aG，a*a=a*a=e, 称a为a的逆元。群G，*是一个有单位元的独异点，对每

7、个aG，存在逆元aG，使a*a=a*a=e.群G，*常简记为G，a*b常简记为ab。可换群叫Abel群 Abelian Group群的例 (Z， Q，Q0， R，R0， Zn， Mn， S上全体一一对应，对于复合，最后一个不是Abel群。例R，*：a*b=ab/2是Abel群。群的性质定理1. 群的逆元唯一：设G是群，任意aG，a只有一个逆元，记做a-1。证明.设a，a都是a的逆，a=aaa=a.定理2. 群有消去律：设G是群，a,b,cG,则（a） abacbc，（b） bacabc。设G=a1,a2,an 任意aG，aG=G.定理3. 逆律设G是群，a,bG, 则(a) (a-1)-1=a,(b) (ab)-1=b-1a-1.c(an)-1(a-1)n定理4. 方程有唯一解设G是群，a,bG,则(a) 方程a*b在G中有唯一解。(b) 方程yab在G中有唯一解。群G的阶: |G|.|G|有限时称G为有限群。元素的阶aG，a的阶：使ake的最小的k。如无这样的k，称a为无限阶。a无限阶，任意nZ+，ane.子群subgroup HG，H对于G的运算*构成群。H是G的子群当且仅当（1） eH（2） a，bHabH（3） aHa-1HH是G的子群当且仅当 a，bHab-1H.子群的例设G是群，He是子群。G是群，aG，Hak | kZ是子群，叫做a生成的子群。命题. 一个群的任意两个子群的交仍是子群。循环群cycle group存在aG ，任意*G，*ak，kZ。a的阶是n，Ge,a,a2,an-1 ak的逆是an-k。a无限阶，G,a-2,a-1,e,a,a

《离散数学课件第9章半群和群》由会员cn****1分享，可在线阅读，更多相关《离散数学课件第9章半群和群》请在金锄头文库上搜索。