下载文档原格式
第9章半群和群semigroup and group§9.1 二元运算复习binary operation revisitedA上二元运算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,……,a n}时，二元运算可以用运算表给出。
二元运算的性质1可换commutativea*b=b*a2 结合associativea*(b*c)=(a*b)*c3 幂等idempotenta*a=a特殊元素单位元对任意a∈A，e*a=a*e＝a. 单位元也叫恒等元零元对任意a∈A，0*a=a*0＝0逆元对任意a，b∈A，a*b=b*a＝e a,b互为逆元代数结构(A,*)A上定义了二元运算满足1)封闭性2)结合律-----------半群3)有单位元---------独异点4)有逆元-----------群5)可交换-----------交换群例子：1)(Z n +), (Z n, )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), ∩），（M n，＋），（Mn，×），S上全体映射，对于复合，（L，∧），（L，∨），L是格（A*, ）,定理1.半群中，n个元素的乘积与乘法的次序无关。
幂power：设（S，*）是半群，a∈S，定义a的幂power：a1＝a， a n=a n-1*a.a0=？a-n=?a m*a n=a m+n(a m)n=a mn.子半群subsemigroup 子独异点submonoid设（S，*）是半群，T⊆S，T对*封闭，则（T，*）也是半群，称为（S，*）的子半群。
第一节 半群与群的基本概念定义1.1 设代数系统<S,*>，其中*为二元运算。
如果*是可结合的,则称<S,*>为一个半群（semigroup ），如果半群的二元运算有单位元，则称此半群为独异点（含幺半群）。
如果独异点的每个元素都是可逆的，则称它为群(group)。
根据定义，代数系统<G ,*>为成一个群当且仅当二元运算*满足下述条件： (1)适合结合律(*)**(*),,,a b c a b c a b c G =∀∈。
(2)有单位元e G ∈∀∈==，**a G a e e a a 。
(3)a G ∀∈,有逆元1a G −∈，使得11**a a a a e −−==群<G ,*>可简记作G ，a*b 可略去*，简记作ab 。
如果半群，独异点和群中的运算是可交换的，则分别称作为交换半群，交换独异点和交换群。
交换群又称作阿贝尔（Abel ）群。
如果群中的运算不是可交换的，则称它为非交换群。
习惯上，常将群中的二元运算叫作乘法，记做 。
定义1.2 若群G 所含元素个数有限，则称G 是有限群,否则称G 是无限群。
群G 中元素个数称作群的阶。
当G 是有限群时，用|G|表示它的阶。
例1.1，,Z +<+>是半群，但不是独异点，因为它没有单位元，,N <+>是独异点，但不是群,因为除0外其它元素无逆元。
而,Z +是一个群，并且是一个交换群，叫作整数加法群。
例1.2模n剩余类加法群<⊕>,n Z 是阿贝尔群,这里{[0],[1],,[1]}n Z n =−L ,[][][()mod ]x y x y n ⊕=+, [0]是它的单位元，对于每个x=0,1,2,…,n-1，[x]的逆元是[-x]=[n-x]。
例1.3 (),n M R <•>是独异点，这里•是矩阵乘法，n 阶单位矩阵是单位元，但它不是可交换的,而且不是每一个矩阵都是可逆的。
第九章半群与群（Semigroups and Groups）本章讨论含一个二元运算的特殊的代数系统――半群与群。
群论近世代数中发展最早、内容最丰富、应用最广泛的部分，也是建立其他代数系统的基础。
群论在自动机政论、形式语言，语法分析快速加法器设计、纠错码制定等方面均有卓有成效的应用。
2－1 半群与含幺半群定义2－1.1 满足结合律的代数系统U=<S,*>称为半群。
例2－1.1 <N,+>,<N,×>,<2I+,+>和<2I+,×>都是半群。
例2－1.2 <Nm ,+m>和<Nm,×m>都是半群。
例2－1.3 <M2(I),+>和<M2(I),·>都是半群。
定义2－1.2含幺元e的半群U=<S,*>称为含幺半群，常记作U=<S,*,e>。
在例2－1.1～例2－1.3中，除<2I+,+>和<2I+,×>外都是含幺半群。
例2－1.4 设S是任意非空集合，则<p(S),∪>和<p(S),∩>都是含幺半群。
例2－1.5在形式语言中，我们常称非空有限字符集合为字母表。
字母表中字符的n 重序元称为字符串，由m个字符所组成的字符串称为长度为m的字符串。
长度为0的字符串称为空串，用来表示。
如对V={a,b}, =aa和β=ab都是长度为2的字符串；γ=aab 和δ=bab都是长度为3的字符串。
我们用*来表示两个字符串的邻接运算，如,α*δ=aabab,α*γ=aaaab。
设用V*表示字母表V的所有有限长度字符串的集合，而用V+表示V*-{ }，则显然<V+,*>是半群，<V+,*, >是含幺半群。
定义2－1.3对运算满足交换律的半群（含幺半群）称为交换半群（交换含幺半群）。
第九章半群与群（Semigroups and Groups）本章讨论含一个二元运算的特殊的代数系统――半群与群。
群论近世代数中发展最早、内容最丰富、应用最广泛的部分，也是建立其他代数系统的基础。
群论在自动机政论、形式语言，语法分析快速加法器设计、纠错码制定等方面均有卓有成效的应用。
2－1 半群与含幺半群定义2－1.1 满足结合律的代数系统U=<S,*>称为半群。
例2－1.1 <N,+>,<N,×>,<2I+,+>和<2I+,×>都是半群。
例2－1.2 <Nm ,+m>和<Nm,×m>都是半群。
例2－1.3 <M2(I),+>和<M2(I),·>都是半群。
定义2－1.2含幺元e的半群U=<S,*>称为含幺半群，常记作U=<S,*,e>。
在例2－1.1～例2－1.3中，除<2I+,+>和<2I+,×>外都是含幺半群。
例2－1.4 设S是任意非空集合，则<p(S),∪>和<p(S),∩>都是含幺半群。
例2－1.5在形式语言中，我们常称非空有限字符集合为字母表。
字母表中字符的n重序元称为字符串，由m个字符所组成的字符串称为长度为m 的字符串。
长度为0的字符串称为空串，用来表示。
如对V={a,b}, =aa 和β=ab都是长度为2的字符串；γ=aab和δ=bab都是长度为3的字符串。
我们用*来表示两个字符串的邻接运算，如,α*δ=aabab,α*γ=aaaab。
设用V*表示字母表V的所有有限长度字符串的集合，而用V+表示V*-{ }，则显然<V+,*>是半群，<V+,*, >是含幺半群。
定义2－1.3对运算满足交换律的半群（含幺半群）称为交换半群（交换含幺半群）。
本章讨论几类重要的代数结构：半群、群、环、域、格与布尔代数等．我们先讨论最简单的半群．半群定义称代数结构<S，>为半群（semigroups），如果运算满足结合律．当半群<S，>含有关于运算的么元，则称它为独异点（monoid），或含么半群．例 <I+，＋>，<N，·>，< ，并置>都是半群，后两个又是独异点．半群及独异点的下列性质是明显的．定理设<S，>为一半群,那么（1）<S，>的任一子代数都是半群，称为<S，>的子半群．（2）若独异点<S,,e>的子代数含有么元e,那么它必为一独异点,称为<S， , e>的子独异点．证明简单，不赘述．定理设<S，>,<S’，’>是半群,h为S到S’的同态,这时称h为半群同态．对半群同态有（1）同态象<h(S)，’>为一半群．（2）当<S，>为独异点时，则<h(S)，’>为一独异点.定理设<S，>为一半群,那么（1）<S S，○ >为一半群，这里S S为S上所有一元函数的集合，○为函数的合成运算．（2）存在S到S S的半群同态．证（l）是显然的．为证（2）定义函数h:S→S S：对任意a Sh（a）= f af a：S→S 定义如下: 对任意x S，f a（x）= a x现证h为一同态．对任何元素a,b S．h(a b)＝f a b （l1－1）而对任何x S，f a b（x）= a b x = f a（f b（x））= f a○f b （x）故f a b = f a○f b ,由此及式（l1－1）即得h（a b）= f a b = f a○f b ＝h（a）○ h（b）本定理称半群表示定理。
它表明，任一半群都可以表示为（同态于）一个由其载体上的函数的集合及函数合成运算所构成的半群。
第九章半群与群（Semigroups and Groups）本章讨论含一个二元运算的特殊的代数系统――半群与群。
群论近世代数中发展最早、内容最丰富、应用最广泛的部分，也是建立其他代数系统的基础。
群论在自动机政论、形式语言，语法分析快速加法器设计、纠错码制定等方面均有卓有成效的应用。
2－1 半群与含幺半群定义2－1.1 满足结合律的代数系统U=<S,*>称为半群。
例2－1.1 <N,+>,<N,×>,<2I+,+>和<2I+,×>都是半群。
例2－1.2 <Nm ,+m>和<Nm,×m>都是半群。
例2－1.3 <M2(I),+>和<M2(I),·>都是半群。
定义2－1.2含幺元e的半群U=<S,*>称为含幺半群，常记作U=<S,*,e>。
在例2－1.1～例2－1.3中，除<2I+,+>和<2I+,×>外都是含幺半群。
例2－1.4 设S是任意非空集合，则<p(S),∪>和<p(S),∩>都是含幺半群。
例2－1.5在形式语言中，我们常称非空有限字符集合为字母表。
字母表中字符的n 重序元称为字符串，由m个字符所组成的字符串称为长度为m的字符串。
长度为0的字符串称为空串，用来表示。
如对V={a,b}, =aa和β=ab都是长度为2的字符串；γ=aab 和δ=bab都是长度为3的字符串。
我们用*来表示两个字符串的邻接运算，如,α*δ=aabab,α*γ=aaaab。
设用V*表示字母表V的所有有限长度字符串的集合，而用V+表示V*-{ }，则显然<V+,*>是半群，<V+,*, >是含幺半群。
定义2－1.3对运算满足交换律的半群（含幺半群）称为交换半群（交换含幺半群）。
在例2－1.1～例2－1.3中，除<M2(I),·>外都是交换半群，除<M2(I),·>，<2I+,+>和<2I+,×>外都是交换含幺半群。
例2－1.4的含幺半群也都是交换含幺半群。
定义2－1.4设<S,*>是半群（含幺半群），若S中存在一个元素g，可将S中任意元素a表示成a=g n n∈I+,(n∈N)，则称<S,*>是循环半群（循环含幺半群）,g就称为是它的生成元。
此时，常将<S,*>记作<g>。
注意在含幺半群中，我们规定任意元素的零次幂为幺元。
例2－1.6 <2I+,+>=<2>是循环半群。
例2－1.7<{i,-1,-i,1},×>=<i>=<-i>,<N4,+4>=<I>和<{1,2,3,4},×5>=<2>=<3>都是循环含幺半群。
可见循环半群（循环含幺半群）的生成元不一定是唯一的，但它们一定是可交换的。
定理2－1.1两个半群（含幺半群）的积代数是半群（含幺半群）。
证明设<S,*>和<T, >是两个半群，其积代数为<S×T, >。
对S×T中任意三个元素<s1,t1><s2,t2>和<s3,t3>，因为(<s1,t1> <s2,t2>) <s3,t3>=<(s1*s2)*s3,(t1t2) t3>=<s1*(s2*s3),t1(t2t3)>=<s1*t1> (<s2,t2> <s3,t3>)故<S×T, >是半群。
设<S,*>和<T, >是两个含幺半群，共中幺元分别为es 和eT，则显然<es,eT>是半群<S×T, >的幺元,故<S×T,*>是含幺半群。
★很明显，可交换半群（含幺半群）的积代数也是可交换的。
2－2 子半群与子含幺半群子含幺半群的概念是子代数系统概念在（含幺）半群这种代数系统中的具体体现。
定义2－2.1 设<S,*>是半群，T是S 的非空子集，若T对*封闭，则称<T,*>是半群<S,*>的子半群。
定义2－2.2 设<S,*,e>是含幺半群，T是S的非空子集，若T对*封闭，且e∈T，则称<T,*.e>是含幺半群<S,*,e>的子含幺半群。
易知子半群必是半群；子含幺半群必是含幺半群。
例2－2.1对任意正整数m，<mN,⨯>是半群<N,⨯>的子半群。
例2－2.2 设集合S={e,0,1}，若在S中规定二元运算*（见表2－2.1），* e 0 1e e 0 100 0 01 1 0 1表2－2.1则<S,*>是含幺半群，从运算表可看出<{0,1},*>不是<S,*>的子含幺半群。
定理2－2.1 设T是可交换含幺半群<S,*,e>的等幂元构成的集合，则<T,*>是<S,*,e>的子含幺半群。
证明因e2=e，故e∈T，即T非空。
又对T中任意元素a和b，因(a*b)2=(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b=(a*a)*(b*b)=a2*b2=a*b故a*b∈T。
这就证明了<T,*>是<S,*,e>的子含幺半群。
★2－3 半群与含幺半群的同态和同构本节中，将把代数系统运用的同态与同构的概念应用于半群（含幺半群），有关定义与性质，几乎是代数系统部分的平行照搬。
定义2-3.1 设U=<S,*>和V=<T, >是两个半群。
若存在映射（满射，单射，双射）f: S→T，对S中任意元素a和b，有f(a*b)=f(a) f(b)则称f是U到V的一个半群同态（满同态，单同态，同构）映射或简称同态（满同态，单同态，同构）。
特别U到U（上）的同态（同构）f称为U的自同态（自同构）。
定义2－3.2 若半群U=<S,*>到V=<T, >存在一个满同态（同构），则称U同态（同构）于V,记作U～V(U≅V)。
定义2－3.3设U=<S,*,e>和V=<T, ,eT>是两个含幺半群。
若存在映射（满射，单射，双射）f: S→T，对S中任意元素a和b，有f(a*b)=f(a) f(b)f(es )=eT则称f是U到V的一个含幺半群同态（满同态，单同态，同构）映射或简称同态（满同态，单同态，同构）。
特别U到U（上）的同态（同构）f称为U的自同态（自同构）。
定义2－3.4若含幺半群U=<S,*,es >到V=<T, ,eT>存在一个满同态（同构），则称U同态（同构）于V，记作U～V(U≅V)。
例2－3.1 我们已知例2－1.1中的U=<N,+>是半群（也是含幺半群）。
易知N到S的映射是半群U到V U到V的同态。
例2－3.2对半群（含幺半群）U＝<N,+>和V＝<M4,+4>,N到M4的映射f: a→〔a(mod 4)〕即是半群U到V的同态，也是含幺半群U到V的同态。
2－4 群对子群再附加一些性质就可成为群。
群是代数“系统中研究得比较完美的一类，目前已有许多群的专著。
在计算机科学中，群在快速加法器设计和纠错码理论等方面有广泛应用。
定义2－4.1每个元素都有逆元的含幺半群U＝<G,*>称为群。
若群还满足交换律，则称为交换群或阿贝尔群。
也就是说，设U=<G,*>是代数系统，若满足：1）对G中任意元素a,b和c，有(a*b)*c=a*(b*c)2）在G中存在元素e，对G中任意元素a，使c*a=a*e=a3）对G中任意元素a，在G中存在元素a-1，使a-1*a=a*a-1=e则称U=(G,*)为群。
若还满足4）对G中任意元素a和b，有a*b=b*a则称U=<G,*>为交换群或阿贝尔群。
由定义2－4.1，定理1－1.1和定理1－1.4知群中的幺元和每个元素的逆元都是唯一的。
且对群中任意元素a1,a2,…,am必有。
由定理1－不一定是唯一的，但群中的等幂元却一定是唯一的，即只有幺元一个。
例2－4.1 <I,+>,<Q,+>,<R,+>,<C,+>,<Q*,×>,<R*,×>和<C*,×>都是交换群。
例2－4.2 <Nm ,+m>和<R[x],+>都是交换群，其中R[x]表示所有实系数多项式的集合。
显然，由定义2－4.1知，给空集合G，和其上的二元运算A，<G,*>能构成群的判定过程如下：（1）验证*运算的封闭性（2）验证*运算的可结合性（3）验证题∃e∈G,∀x∈G有e*x=x*e=x（4）验证∀x∈G,∃x-1∈G使x*x-1=x-1*x=e上述四个步骤中至少一个步骤的验证不成立,<G,*>都不是群。
定理2－4.1 半群<G,*>是群的充要条件为存在左（右）幺元e1(er)，且每个元素对此左（右）幺元具有左（右）逆元。
证明必要性是很明显的。
a，设其左逆左“乘”的左逆元，可得即也是a即e1也是右幺元。
故由定理1-1.11可见<G,*>是群。
★这个定理说明群定义中的条件可以削弱。
定理2－4.2 代数系统<G,*>是群的充要条件为1)对G中任意元素a,b和c，有(a*b)*c=a*(b*c)2）对G中任意元素a和b，方程a*x=b和y*a=b都有解。
证明必要怀是很明显的。
实际上，x=a-1*b和y=b*a-1就是2）中方程的（唯一）解。
充分性：对G中任意元素a和b，设方程b*x=a的解为 d，方程y*b=b 的解为e，则有e*a=e*(b*d)=(e*b)*d=b*d=a，即e是左幺元。
又方程y*a=e的解是a的左逆元。
故由定理2－4.1知<G,*>是群。
★定理2－4.3 若<G,*>是群，则对*满足消去律。
证明 设a*b=a*c 或b*a=c*a ，则在等式两边左“乘”或右“乘” a -1即得b=c 。
★ 定理2－4.4 有限半群<G,*>是群的充要条件为对*满足消去律。
