半群与幺半群.ppt

《半群与幺半群.ppt》由会员分享，可在线阅读，更多相关《半群与幺半群.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、半群与幺半群半群与幺半群1现在学习的是第1页，共22页定义定义1 设设为为S上的二元运算上的二元运算,如果存在如果存在el(或或er)S，使得对任意，使得对任意 xS 都有都有 elx=x (或或 xer=x)，则称则称el(或或er)是是S中关于中关于运算的运算的左左(或或右右)单位元单位元.若若eS关于关于运算既是左单位元又是右单位元，则运算既是左单位元又是右单位元，则称称e为为S上关于上关于运算的运算的单位元单位元.单位元也叫做单位元也叫做幺元幺元.特异元素：单位元特异元素：单位元2现在学习的是第2页，共22页问题：问题：设设为为S上的二元运算上的二元运算,(1)如果如果S关于关于运算有

2、左单位元运算有左单位元el，则，则 S关于关于运算运算 一定有右单位元一定有右单位元er 吗？吗？例例：设：设R为实数集合，如下定义为实数集合，如下定义R上的二元运算上的二元运算：x,yR,x y=x 或或 x y=y.(2)若若S关于关于运算既有左单位元运算既有左单位元el又有右单位元又有右单位元er，则则el=er(=e)?(3)若若S关于关于运算有单位元，则单位元唯一吗？运算有单位元，则单位元唯一吗？特异元素：单位元特异元素：单位元3现在学习的是第3页，共22页定理定理1 设设为为S上的二元运算，上的二元运算，el和和er分别为分别为S中关于中关于运算的左和右单位元，则运算的左和右单位元

3、，则el=er=e为为S上关于上关于运算运算的惟一的单位元的惟一的单位元.单位元惟一性定理单位元惟一性定理4现在学习的是第4页，共22页定义定义2 设设为为S上的二元运算，上的二元运算，如果存在如果存在 l(或或 r)S，使得对任意，使得对任意 xS 都有都有 l x=l (或或 x r=r)，则称则称 l(或或 r)是是S 中关于中关于运算的运算的左左(或或右右)零元零元.若若 S 关于关于运算既是左零元又是右零元，则称运算既是左零元又是右零元，则称 为为S上关于运算上关于运算的的零元零元.特异元素：零元特异元素：零元5现在学习的是第5页，共22页问题：问题：设设为为S上的二元运算上的二元运

4、算,(1)如果如果S关于关于运算有左零元运算有左零元 l，则，则 S关于关于运算运算 一定有右零元一定有右零元 r 吗？吗？例例：设：设R为实数集合，如下定义为实数集合，如下定义R上的二元运算上的二元运算：x,yR,x y=x 或或 x y=y.(2)若若S关于关于运算既有左零元运算既有左零元 l又有右零元又有右零元 r，则则 l=r(=)?(3)若若S关于关于运算有零元，则零元唯一吗？运算有零元，则零元唯一吗？特异元素：零元特异元素：零元6现在学习的是第6页，共22页定理定理2 设设为为S上的二元运算，上的二元运算，l 和和 r分别为分别为S中关中关于运算的左和右零元，则于运算的左和右零元，

5、则 l=r=为为S上关于上关于运运算的惟一的零元算的惟一的零元.注意注意l当当|S|2，单位元与零元是不同的；，单位元与零元是不同的；l当当|S|=1时，这个元素既是单位元也是零元时，这个元素既是单位元也是零元.零元惟一性定理零元惟一性定理7现在学习的是第7页，共22页定义定义3 设设为为S上的二元运算上的二元运算,令令e为为S中关于运算中关于运算 的单的单位元位元.对于对于xS，如果存在，如果存在yl(或或yr)S使得使得 ylx=e（或（或xyr=e）则称则称yl(或或 yr)是是x的的左逆元左逆元（或（或右逆元右逆元）.关于关于运算，若运算，若yS 既是既是 x 的左逆元又是的左逆元又是

6、 x 的右逆的右逆元，则称元，则称y为为x的的逆元逆元.如果如果 x 的逆元存在，就称的逆元存在，就称 x 是是可逆的可逆的.可逆元素和逆元可逆元素和逆元8现在学习的是第8页，共22页问题：问题：设设为为S上的二元运算上的二元运算,令令e为为S中关于运算中关于运算 的的单位元单位元.对于对于xS，(1)如果如果x有左逆元有左逆元yl，则，则 x一定有右逆元一定有右逆元yr 吗？吗？例例：SS为为S上的所有映射的集合，则合成运算上的所有映射的集合，则合成运算 为为SS上二元运算上二元运算.单射左可逆，满射右可逆单射左可逆，满射右可逆.(2)若若x既有左逆元既有左逆元yl又有右逆元又有右逆元yr，

7、则，则yl=yr?(3)若若x有逆元，则逆元唯一吗？有逆元，则逆元唯一吗？可逆元素和逆元可逆元素和逆元9现在学习的是第9页，共22页定理定理3 设设为为S上上可结合可结合的二元运算的二元运算,e为该运算的为该运算的单位元单位元,对于对于xS 如果存在左逆元如果存在左逆元 yl 和右逆元和右逆元 yr,则有则有 yl=yr=y,且且 y是是 x 的惟一的逆元的惟一的逆元.说明说明 对于可结合的二元运算，可逆元素对于可结合的二元运算，可逆元素 x 只有惟只有惟一的逆元，记作一的逆元，记作 x 1.逆元惟一性定理逆元惟一性定理10现在学习的是第10页，共22页第第2节节 半群与幺半群半群与幺半群主要

8、内容主要内容:l半群与幺半群半群与幺半群l子半群、子幺半群、理想子半群、子幺半群、理想l循环半群与循环幺半群循环半群与循环幺半群11现在学习的是第11页，共22页定义定义1 (1)设设(S,)是一个代数系统，如果运算是一个代数系统，如果运算 满足结合律，满足结合律，则称则称(S,)为一个为一个半群半群.(2)设设(S,)是半群，若是半群，若eS是关于是关于 运算的单位元，运算的单位元，则称则称(S,)是一个是一个幺半群幺半群，也叫做，也叫做独异点独异点.有时也将独异点有时也将独异点(S,)记作记作(S,e).(3)如果如果(幺幺)半群半群S中的运算中的运算 满足交换律，则称满足交换律，则称(幺

9、幺)半半 群群S为为交换交换(幺幺)半群半群或或可换可换(幺幺)半群半群.(4)只含有有限个元素的只含有有限个元素的(幺幺)半群半群S称为称为有限有限(幺幺)半群半群，否则称为否则称为无限无限(幺幺)半群半群.通常把通常把S的基数称为的基数称为(幺幺)半群半群S的的阶阶.2.1 半群与幺半群半群与幺半群12现在学习的是第12页，共22页例例1(1)(N,+),(Z+,+),(Z,+),(Q,+),(R,+)都是半群，其中都是半群，其中+是普是普通加法通加法.这些半群中除这些半群中除(Z+,+)外都是幺半群外都是幺半群.(2)设设n是大于是大于1的正整数，的正整数，(Mn(R),+)和和(Mn(

10、R),)都是都是 半群，也都是幺半群，其中半群，也都是幺半群，其中+和和分别表示矩阵加分别表示矩阵加 法和矩阵乘法法和矩阵乘法.(3)(P(B),)为半群，也是幺半群，其中为半群，也是幺半群，其中 为集合对为集合对 称差运算称差运算.实实 例例13现在学习的是第13页，共22页(4)(Zn,)为半群，也是幺半群，其中为半群，也是幺半群，其中 Zn=0,1,n 1,x=y|yZ,yx(mod n)为模为模n加法加法:x y=xy 或者或者 x y=(xy)mod n (5)(AA,)为半群，也是幺半群，其中为半群，也是幺半群，其中为映射的合成为映射的合成 运算运算.(6)(R*,)为半群，其中为

11、半群，其中R*为非零实数集合，为非零实数集合，运算运算 定义如下：定义如下：x,y R*,xy=y.实实 例例14现在学习的是第14页，共22页注意注意 有单位元并不是半群的固有性质有单位元并不是半群的固有性质.在没有单位元的半群中可能有左单位元，在没有单位元的半群中可能有左单位元，或者或者有右单有右单位元，而且左位元，而且左(右右)单位元也可能不只一个，甚至可能单位元也可能不只一个，甚至可能有无穷多个有无穷多个.性性 质质(1)有单位元的半群、无单位元的半群；有单位元的半群、无单位元的半群；(2)在没有单位元的半群中可能有左单位元；在没有单位元的半群中可能有左单位元；(3)在没有单位元的半群

12、中可能有右单位元在没有单位元的半群中可能有右单位元.15现在学习的是第15页，共22页定理定理1 如果半群如果半群(S,)既有左单位元素又有右单位元既有左单位元素又有右单位元素，则左单位元素与右单位元素相等，从而半群素，则左单位元素与右单位元素相等，从而半群S有有单位元素单位元素(即半群即半群S成为幺半群成为幺半群)且单位元素是唯一的且单位元素是唯一的.定理定理2 有限半群有限半群(S,)为一个幺半群为一个幺半群存在存在x,y S使得使得xS=S，Sy=S.性性 质质注注(1)半群的正式研究始于半群的正式研究始于二十世纪二十世纪初初.(2)自从自从1950年代，有限半群的研究在年代，有限半群的

13、研究在理论计算机科理论计算机科 学学中变得特别重要，因为在中变得特别重要，因为在有限半群有限半群和和有限自动有限自动 机机之间有自然的联系之间有自然的联系.16现在学习的是第16页，共22页 在在幺半群幺半群(S,e)中可以定义非负整数次幂的运算中可以定义非负整数次幂的运算.a S，a0=e,an+1=an a,n0.定理定理3 设设(S,e)是一个幺半群，是一个幺半群，m,n是任意的非负整是任意的非负整数，则数，则(1)a S，am an=am+n ,(am)n=amn.(2)若若(S,e)是可交换的，则是可交换的，则 a,b S，(a b)n=an bn.幂运算幂运算17现在学习的是第17

14、页，共22页子半群子半群定义定义2 设设(S,)是半群，是半群，B是是S的一个非空子集的一个非空子集.如果如果 x,y B，有，有x y B，则称，则称(B,)是是(S,)的一的一个子半个子半群群，简称，简称B是是S的子半群的子半群.定理定理4 设设(S,)是半群，是半群，B是是S的一个非空子集的一个非空子集.B是是S的子半群的子半群 B B B.x,y B，有，有x y B.18现在学习的是第18页，共22页子幺半群子幺半群定义定义3 设设(S,e)是幺半群，是幺半群，P S.如果如果e P 且且P是是S的子半群，则称的子半群，则称P是是S的的子幺半群子幺半群.定理定理5 设设(S,e)是幺

15、半群，是幺半群，P S.P是是S的子幺半群的子幺半群 e P且且 P P P.e P且且 x,y P，有，有x y P.19现在学习的是第19页，共22页子子(幺幺)半群的实例半群的实例例例2(Z,)是半群，也是幺半群，是半群，也是幺半群，0,1 Z，则，则(0,1,)是是(Z,)是子半群，也是子幺半群是子半群，也是子幺半群.注意注意(1)幺半群的子半群如果有单位元，且和幺半群的单幺半群的子半群如果有单位元，且和幺半群的单位元相同，才能被称为子幺半群位元相同，才能被称为子幺半群.换句话说换句话说，也就是幺半群的一个子半群如果有单位，也就是幺半群的一个子半群如果有单位元，但和幺半群的单位元不同，

16、它也不能被称为子元，但和幺半群的单位元不同，它也不能被称为子幺半群幺半群.（会有这种情况吗？）（会有这种情况吗？）例：例：2阶矩阵乘法半群阶矩阵乘法半群a b;c d；子半群；子半群a 0;0 0(2)幺半群有无单位元幺半群有无单位元(不管此单位元是否和幺半群不管此单位元是否和幺半群的单位元相同的单位元相同)的子半群的子半群.20现在学习的是第20页，共22页子子(幺幺)半群的性质半群的性质性质性质1 一个幺半群一个幺半群S的任意多个子幺半群的交集还的任意多个子幺半群的交集还 是是S的子幺半群的子幺半群.问题：问题：“一个半群一个半群S的任意多个子半群的交集还是的任意多个子半群的交集还是S 的

17、子半群的子半群”成立吗？成立吗？例：例：(Z,)是半群，奇数半群？偶数半群？是半群，奇数半群？偶数半群？性质性质2 设设(S,)是半群，是半群，A是是S的一个非空子集，则的一个非空子集，则S的一切包含的一切包含A的子半群的交集也是的子半群的交集也是S的子半群的子半群.设设(S,e)是幺半群，是幺半群，A是是S的一个非空子集，则的一个非空子集，则S的的一切包含一切包含A的子幺半群的交集也是的子幺半群的交集也是S的子幺半群的子幺半群.21现在学习的是第21页，共22页生成子生成子(幺幺)半群半群定义定义4 设设(S,)是半群，是半群，A是是S的一个非空子集的一个非空子集.由由S的的包含包含A的所有子半群的交集所作成的子半群称为由的所有子半群的交集所作成的子半群称为由A生成的的子半群生成的的子半群，记为，记为(A).设设(S,e)是幺半群，是幺半群，A是是S的一个非空子集的一个非空子集.由由S的包的包含含A的所有子幺半群的交集所作成的子幺半群称为的所有子幺半群的交集所作成的子幺半群称为由由A生成的的子幺半群生成的的子幺半群，记为，记为(A).性质性质3 由由A生成的的子半群是半群生成的的子半群是半群S包含包含A的最小子的最小子(幺幺)半群半群.由由A生成的的子幺半群是幺半群生成的的子幺半群是幺半群S包含包含A的最小子幺的最小子幺半群半群.22现在学习的是第22页，共22页