《离散数学》第五章3-4节

定义5-3.1：一个代数系统<S,*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，则称代数系统<S,*>为广群。

例如：？？

5-3半群1、广群、半群及其性质1整理ppt定义5-3.2：一个代数系统<S,*>，其中S是非空集合，*是S上的一个二元运算。如果：(1)运算*是封闭的。(2)运算*是可结合的，即对任意的x,y,z∈S，满足(x*y)*z=x*(y*z)则称代数系统<S,*>为半群。思考：（a）例如：？？(b)与广群的关系(1)<N,+>,

<Z,+>,

<Q,+>,

<R,+>。(2)<Mn(R),+>,<Mn(R),.>,其中Mn(R)为n阶实矩阵。2整理ppt例1：证明代数系统<R*,◦>是一个半群，其中R*是非零实数集合，◦运算定义为：x◦y=y。解：x,y∈R*，x◦y=y∈R*，封闭性；x,y,z∈R*，有(x◦y)◦z=y◦z=zx◦(y◦z)=x◦z=z，即(x◦y)◦z=x◦(y◦z)，结合律；所以代数系统<R*,◦>是一个半群。3整理ppt

例2设S={a,b,c}，在S上的一个二元运算△的运算表如下，验证<S,△>是一个半群。△abcabcabcabcabc观察特点？要验证3！个式子吗4整理ppt定理5-3.1：设<S,*>是一个半群，B

S且*在B上是封闭的，那么<B,*>也是一个半群。称<B,*>是半群<S,*>的子半群。问题：设<S,*>是一个半群，B

S，则<B,*>？？5整理ppt例3：设•表示普通的乘法运算，那么<[0,1],•>、<[0,1),•>和<I,•>都是<R,•>的子半群。验证<B,*>是半群<S,*>的子半群，满足：*在B上封闭；B是S的子集。6整理ppt定理5-3.2：设<S,*>是一个半群，如果S是一个有限集，则必有a∈S，使得a*a=a。证明：因为<S,*>是半群。对于

b∈S，由*的封闭性，有b∈S，b2=b*b∈S，…，bi∈S，…，bn∈S，因S是有限集，j>i，使得bi=bj，令p=j-i，所以有bi=bp*bi，显然对于q≥i，有bq=bp*bq，7整理ppt∵p≥1，∴总可以找到k≥1，使得kp≥i，对于S中的元素bkp，就有bkp=bp*bkp

=bp*(bp*bkp)=b2p*bkp=b2p*(bp*bkp)=…=bkp*bkp

证明了在S中存在元素a=bkp,使得a*a=a8整理ppt定义5-3.3：含有幺元的半群称为独异点。思考：举例？？与半群的关系例如，下列代数系统是不是独异点<R,+>，<I,•>、<I+,•>、<R,•>，2、独异点及其性质0是R中运算+的幺元；具有幺元1。9整理ppt定理5-3.3设<S,*>是一个独异点，则在关于运算*的运算表中任何两行或两列都是不相同的。证明：设S中关于运算*的幺元为e，

a,b∈S且a≠b时，总有e*a=a，e*b=b；a≠b,∴任何两列都是不相同的。a*e=a，b*e=b；a≠b,∴任何两行都是不相同的。所以*的运算表中不可能有两行或两列是相同的。10整理ppt例4：设I是整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集，在Zm上定义两个二元运算+m和×m分别如下：对于任意的[i],[j]∈Zm[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]试证明在这两个二元运算的运算表中任何两行或两列都不相同。咋证呢？11整理ppt证明：1)由运算+m和×m的定义，可知它们在Zm上都封闭的。2)对于任意[i],[j],[k]∈Zm

([i]+m[j])+m[k]=[(i+j+k)(modm)]=[i]+m([j]+m[k])

([i]×m[j])×m[k]=[(i×j×k)(modm)]=[i]×m([j]×m[k])12整理ppt

3)∵[0]+m[i]=[i]+m[0]=[i]，∴[0]是<Zm,+m>中的幺元。∵[1]×m[i]=[i]×m[1]=[i]，∴[1]是<Zm,×m>中的幺元。因此，代数系统<Zm,＋m>，<Zm,×m>都是独异点。由定理5-3.3可知这两个运算表中任何两行或两列都不相同。13整理ppt定理5-3.4：设<S,*>是独异点，对于任意a,b∈S，且a,b均有逆元，则1）(a-1)-1=a；2）a*b有逆元，且(a*b)-1=b-1*a-1。证明：a)因为a-1是a的逆元，即a*a-1=a-1*a=e(a-1)-1=ab)

因为(a*b)*(b-1*a-1)=a*(b*b-1)*a-1

=a*e*a-1

=a*a-1=e同理可证(b-1*a-1)*(a*b)=e所以(a*b)-1=b-1*a-114整理ppt1、群及其性质1)基本概念(群、有限群、无限群)定义5-4.1：设<G,*>是代数系统，其中G是非空集合，*是G上的二元运算，如果(1)运算*是封闭的；(2)运算*是可结合的；(3)存在幺元；(4)对于每一个元素x∈G，存在着它的逆元x-1∈G；则称<G,*>是一个群。5-4群与子群广群半群独异点15整理ppt广群，半群，独异点，群的关系（封闭）半群（结合律）独异点（有幺元）群（有逆元）广群16整理ppt例1：判断下列代数系统是否为群<R-{0},+>，<P(S),⊕>，<R-{0},×>群的分类：定义5-4.2设<G,*>是一个群。如果G是有限集，那么称<G,*>为有限群，G中元素的个数通常称为该有限群的阶数，记为|G|；如果G是无限集，则称<G,*>为无限群。约定无限群的阶数为∞17整理ppt例2：试验证代数系统<I,+>是一个群，I是整数集合，+是普通加法运算。解：二元运算+在I上是封闭的且是可结合的。幺元是0，任一元素a∈A，它的逆元是-a，所以<I,+>是一个群，且是一个无限群。又如：<I+,+>是吗？18整理ppt2）群的性质复习：定理5-2.3：设A是一个代数系统，且集合A中元素的个数大于1，如果该系统中存在幺元e和零元θ，则e≠θ。定理5-3.2：设<S,*>是一个半群，如果S是一个有限集，则必有a∈S，使得a*a=a（等幂元）。定理5-3.3设<S,*>是一个独异点，则在关于运算*的运算表中任何两行或两列都是不相同的。定理5-3.4：设<S,*>是独异点，对于任意a,b∈S，且a,b均有逆元，则1）(a-1)-1=a；2）a*b有逆元，且(a*b)-1=b-1*a-1。19整理ppt定理5-4.1：群中不可能有零元。证明：当群的阶为1时，它的唯一元素视为幺元。设|G|>1且群<G,*>有零元θ，任意x∈G，有x*θ=θ*x=θ≠e，定理5-2.3所以，零元θ就不存在逆元，与<G,*>是群相矛盾。20整理ppt定理5-4.2：设<G,*>是群，对于a,b∈G，必存在唯一的x∈G，使得a*x=b。证明：设a的逆元是a-1，令x=a-1*b（常用方法）则a*x=a*(a-1*b)=(a*a-1)*b=e*b=b若另有一解x1，满足a*x1=b，则a-1*(a*x1)=a-1*b即x1=a-1*b21整理ppt定理5-4.3：设<G,*>是群，对于a,b,c∈G，如果有a*b=a*c或b*a=c*a，则必有b=c（消去律）。证明：设a*b=a*c，且a的逆元是a-1，则有a-1*(a*b)=a-1*(a*c)(a-1*a)*b=(a-1*a)*ce*b=e*cb=c当b*a=c*a时，同理可证b=c。22整理ppt定义5-4.3：设S是一个非空集合，从集合S到S的一个双射称为S的一个置换。例如：S={a,b,c,d},一个置换为3）置换、等幂元23整理ppt定理5-4.4：群<G,*>的运算表中的每一行或每一列都是G的元素的一个置换。2)对每一行，G中每个元素出现最多一次：入射设对应于元素a∈G的那一行中若有两个元素都是c，即有a*b1=a*b2=c，且b1≠b2，由消去律可得b1=b2，矛盾所以<G,*>的运算表中每一行都是G的一个置换。同理<G,*>的运算表中每一列都是G的一个置换。证明：1)G中每个元素都在每一行中出现：满射设

b∈G的元素，考察对应于a∈G的那一行由于b=a*(a-1*b)，所以b必定出现在对应a的那一行中。24整理ppt定理5-4.5：在群<A,*>中，除幺元e外，不可能有任何别的等幂元。证明:(1)证幺元e是等幂元

(2)假设a

∈A，且a≠e，满足a*a=a，则a=e*a=(a-1*a)*a=a-1*(a*a)=a-1*a=e矛盾25整理ppt1）基本概念(子群、平凡子群)定义5-4.5：设<G,*>是一个群，S是G的一个非空子集，如果<S,*>也构成群，则称<S,*>是<G,*>的一个子群。2、子群及其性质定义5-4.6：设<G,*>是一个群，<S,*>是<G,*>的一个子群，如果S={e}或S=G，则称<S,*>为<G,*>的平凡子群。平凡子集26整理ppt例1：判断下列说法是否正确<Z,+>为<Q,+>的子群<R+,×>是<R-{0},×>的子群，也是<R,+>的子群27整理ppt例2：<I,+>是一个群，设IE={x|x=2n,n∈I}，证明<IE,+>是<I,+>的一个子群。证明：1）封闭性。

2）运算+在IE上保持可结合性。

3）<I,+>中的幺元0在IE中。

4）对于任意的x∈IE，-x=-2n，-n∈I，∴-x∈IE，x+(-x)=0。因此<IE，+>是一个群，又IE是I的子集，所以<IE，+>是<I,+>的一个子群。28整理ppt证明：设<S,*>中的幺元为e1，对于任一x∈S

G，必有e1*x=x=e*x，故e1=e（根据？？）。定理5-4.6：设<G,*>是一个群，<S,*>是<G,*>的一个子群，那么<G,*>中的幺元e必定也是<S,*>中的幺元。29整理ppt补充：定义：设<S,*>为一半群，a∈S，n为正整数，符号an表示n个a的计算结果，即an=a*a*……*a。在半群<S,*>中指数律成立，即对任意整数m，n和S中的元素a，有aman=am+n，(am)n=amn定义的扩充如果<S,*>是独异点，e是幺元，a∈S，令a0=e，如果<S,*>是群，a∈S，n为正整数，则令a-n=(a-1)n30整理ppt定理5-4.7：设<G,*>是一个群，B是G的非空子集，如果B是一个有限集，那么只要运算*在B上封闭，<B,*>必定是<G,*>的子群。证明：要证满足已知条件的<B,*>是一个子群，

1)封闭。2)结合。

3)存在幺元。b∈B，b2=b*b∈