离散数学半群和独异点、群与子群课件.ppt

1、第二讲第二讲 半群、群和子群半群、群和子群定义定义 一个代数系统一个代数系统，其中其中S是非空集合，是非空集合，*是是S上的上的 一个二元运算，如果运算一个二元运算，如果运算*是封闭的是封闭的，则称代数系统，则称代数系统 为为广群广群。一一.广群广群二二.半群半群定义定义 一个代数系统一个代数系统，其中其中S是非空集合，是非空集合，*是是S上的上的 一个二元运算，如果一个二元运算，如果 1）运算）运算*是封闭的是封闭的。2）运算）运算*是是可结合的可结合的，即对任意的，即对任意的x,y,zS，满足满足 (x*y)*z=x*(y*z)则称代数系统则称代数系统 为为半群半群。例例设集合设集合Sk=

2、x|x I xk，k0，那么那么是一个是一个半群吗？（其中半群吗？（其中+是普通加法运算）是普通加法运算）分析分析 因为加法运算在因为加法运算在Sk上是封闭的，并且该运算可结合，上是封闭的，并且该运算可结合，所以所以是一个半群。是一个半群。注意注意 若若k0，则运算则运算+在在Sk上是不封闭的。上是不封闭的。？代数系统代数系统是半群吗？是半群吗？呢？呢？定理定理设设是一个半群，是一个半群，B S且且*在在B上是封闭的上是封闭的，那，那末末也是一个半群。通常称也是一个半群。通常称是半群是半群的的子半群子半群。证明证明 因为因为*在在S上是可结合的，而上是可结合的，而B S 所以所以*在在B上也是

3、可上也是可结合的，又结合的，又*在在B上是封闭的，因此，上是封闭的，因此，也是一个半群。也是一个半群。例例 代数系统代数系统，都是都是的的 子半群。子半群。定理定理设设是一个是一个半群半群，如果，如果S是一个是一个有限集有限集，则必有，则必有aS，使得使得a*a=a。证明证明 因为因为是一个半群。对于是一个半群。对于 b S，由，由*的封闭性可知的封闭性可知 b*b S，记记b2=b*b b2*b=b*b2 S，记记b3=b2*b=b*b2 由于由于S是有限集，所以必存在是有限集，所以必存在 ji，使得使得bi=bj 令令p=ji，有有bi=bp*bi，所以对所以对qi，有有bq=bp*bq

4、因为因为p1，所以总可以找到所以总可以找到k1，使得使得kpi 就有就有bkp=bp*bkp =bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=bkp*bkp 这就证明了在这就证明了在S中存在元素中存在元素a=bkp，使得使得a*a=a.3独异点独异点定义定义 含有幺元的半群称为独异点。含有幺元的半群称为独异点。例例 代数系统代数系统是一个独异点。因为是一个独异点。因为是半群，且是半群，且0是是 R中关于运算中关于运算+的幺元。的幺元。代数系统代数系统 都是独异点，幺元为都是独异点，幺元为1。定理定理 设设是一个独异点，则在关于运算是一个独异点，则在关于运算*的运算表中的运

5、算表中任何任何 两行或两列两行或两列都是都是不相同不相同的。的。证明证明 设设S中关于运算中关于运算*的幺元是的幺元是e。因为因为 a,b S且且ab，总有总有 e*a=ab=e*b 和和 a*e=ab=b*e 所以，在所以，在*的运算表中任何两行或两列都是不相同的。的运算表中任何两行或两列都是不相同的。定理定理设设是独异点，对于任意是独异点，对于任意a,bS,且且a,b均有逆元，则均有逆元，则1)(a-1)-1=a2)a*b有逆元，且有逆元，且(a*b)-1=b-1*a-1证明证明 1)因为因为a-1是是a 的逆元，即的逆元，即 a*a-1=a-1*a=e 所以，所以，(a-1)-1=a 2

6、)因为因为(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-14群群定义定义 设设一个代数系统一个代数系统，其中其中G是非空集合，是非空集合，*是是G上上 的一个二元运算，如果的一个二元运算，如果 1）运算）运算*是封闭的是封闭的。2）运算）运算*是是可结合的可结合的。3）存在）存在幺元幺元e。4）对于每一个元素对于每一个元素x G，存在着它的存在着它的逆元逆元x-1。则称代数系统则称代数系统 为为群群。群 独异点 半群 广群5有限群有限群定义定义 设设是一个

7、群。如果是一个群。如果G是有限集，那末称是有限集，那末称为为 有限群，有限群，G中元素的个数通常称为该有限群的阶数，记中元素的个数通常称为该有限群的阶数，记 为为|G|；如果如果G是无限集，则称是无限集，则称为无限群。为无限群。例例 ，都是群。都是群。考察如下代数系统是否构成群考察如下代数系统是否构成群，？定理定理群中群中不可能不可能有零元。有零元。证明证明 当群的阶为当群的阶为1时，它的唯一元素视为幺元。时，它的唯一元素视为幺元。设设|G|1且群且群有零元有零元。那么群中任何元素。那么群中任何元素xG，都有都有x*=*x=e，所以，零元所以，零元就不存在逆元，这与就不存在逆元，这与 是群相矛

8、盾。是群相矛盾。定理定理 设设是一个群，对于是一个群，对于a,bG,必存在唯一的必存在唯一的xG,使得使得a*x=b.证明证明 1）存在）存在 2）唯一）唯一设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*b定理定理设设是一个群，对于任意的是一个群，对于任意的a,b,cG，如果有如果有a*b=a*c或者或者b*a=c*a,则必有则必有b=c。（。（消去律消去律）证明证明 设设a*b=a*c，且且a的逆元是的逆元是a-1，则有则有 a-1*(a*b)=a-1*(

9、a*c)(a-1*a)*b=(a-1*a)*c e*b=e*c b=c 当当b*a=c*a时，可同样证得时，可同样证得b=c。定义定义设设S是一个非空集合，从集合是一个非空集合，从集合S到到S的一个双射称为的一个双射称为S的一个的一个置换置换。定理定理群群的运算表中的每一行或每一列都是的运算表中的每一行或每一列都是G的元的元素的一个置换。素的一个置换。证明见书证明见书193等幂元等幂元证明证明 因为因为e*e=e，所以所以e是等幂元。是等幂元。假设存在假设存在aA,ae且且a*a=a 则有则有 a=e*a=(a-1*a)*a=a-1*(a*a)=a-1*a=e 与假设与假设a e相矛盾。相矛盾

10、。定义定义 代数系统代数系统中，如果存在中，如果存在aG，有有a*a=a，则称则称a为为等幂元等幂元。定理定理 在群在群中，除幺元中，除幺元e外，不可能有任何别的等幂元。外，不可能有任何别的等幂元。6子群子群定义定义 设设是一个群是一个群，S是是G的的非空子集非空子集，如果，如果也也 构成群，则称构成群，则称 是是的一个的一个子群子群。定理定理 设设是一个群，是一个群，是是的一个子群，那末，的一个子群，那末，中的幺元中的幺元 e 必定也是必定也是中的幺元。中的幺元。证明证明 设设中的幺元为中的幺元为e1，对于任一对于任一xS G，必有必有 e1*x=x=e*x 故，故，e1=e。(为群，满足消

11、去律为群，满足消去律)7平凡子群平凡子群 定义定义 设设是一个群是一个群，是是的的子群子群，如果，如果 S=e，或者或者S=G，则称则称是是的的平凡子群平凡子群。例例 是一个群，设是一个群，设IE=x|x=2n,nI，证明证明是是 的一个子群。的一个子群。分析分析 1）+在在IE上封闭。上封闭。2）+在在IE上可结合。上可结合。3）有幺元。有幺元。4）IE中的每个元素都有逆元。中的每个元素都有逆元。定理定理设设是一个群，是一个群，B是是G的非空子集，如果的非空子集，如果B是一是一个有限集个有限集，那末只要运算，那末只要运算*在在B上封闭，上封闭，必定必定是是的子群。的子群。证明证明 设设e是是

12、 中么元，中么元，b是是B中的任一个元素。若中的任一个元素。若*在在B上上 封闭，则元素封闭，则元素b2=b*b,b3=b2*b,都在都在B中。中。由于由于B是有限集，所以必存在正整数是有限集，所以必存在正整数i和和j，不妨假设不妨假设 ij，使得使得bi=bj，即即bi=bi*bj-i。这就说明这就说明bj-i是是 中的幺元中的幺元(bi=bi*bj-i=bi*e)，且这个幺元也在子集，且这个幺元也在子集B中。中。如果如果j-i1，那末由那末由bj-i=b*bj-i-1可知可知bj-i-1是是b的逆元，的逆元，且且bj-i-1 B；如果如果j-i=1，那末由那末由bi=bi*b可知可知b就是

13、就是 幺元，而幺元是以自身为逆元的。幺元，而幺元是以自身为逆元的。因此，因此，是是的一个子群。的一个子群。当当B不是有限集不是有限集则结论不成立：则结论不成立：为群，而为群，而 不为群，不为群，虽然在自然数上是封闭的。虽然在自然数上是封闭的。定理定理设设是群，是群，S是是G的非空子集，如果对于的非空子集，如果对于S中的中的任意元素任意元素a和和b有有a*b-1S，则则是是的子群。的子群。证明证明 1）证明证明G中的幺元中的幺元e也是也是S中的幺元。中的幺元。任取任取S中的元素中的元素aS G，所以所以a*a-1=e S且且a*e=e*a =a,即即e也是也是S中的幺元。中的幺元。2）证明证明S中的每一个元素都有逆元。中的每一个元素都有逆元。对任一对任一aS，因为因为eS，所以所以e*a-1S即即a-1S。3）证明证明*在在S上是封闭的。上是封闭的。对任意的对任意的a,b S，由上可知，由上可知b-1S而而b=(b-1)-1 所以所以 a*b=a*(b-1)-1 S 4）*在在S上的结合性是可继承的。上的结合性是可继承的。因此，因此，是是的子群。的子群。作业作业P190(2)197(2)(3)