离散数学半群.ppt
离散数学半群现在学习的是第1页，共13页一、广群与半群一、广群与半群 半群是一种特殊的代数系统，在计算机科学领域中，如形式语言，自动机理论等方面，已得到了卓有成效的应用。定义定义5-3.15-3.1 为一个代数系统，集合S 。*是S上的一个二元运算，如果运算运算*是封闭的是封闭的，则称代数系统 为广群广群。定义定义5-3.25-3.2 若为广群，且*在S上可结合，可结合，则称为半群半群。例如：1）幂集P（A）上对称差运算构成半群。2）设Z为整数集，+、-、*是数的加法、减法和乘法，则（Z，+）、（Z，*）都是半群；（Z，-）不是半群。3）Nk=0,1,2,k-1上模k加法成半群。现在学习的是第2页，共13页一、广群与半群一、广群与半群 例题2 设S=a,b,c,S上的一个二元运算的定义如下表所示，验证S,是半群。abcaabcbabccabc解：解：由上表知运算在S上是封闭的而且对任意x1,x2S有x1x2=x2，且a,b,c都 是 左 幺 元，从 而 对 任 意 的x,y,zS都 有:x(yz)=xz=z,(xy)z=yz=z因此x(yz)=(xy)z运算是可结合的，S,是半群。现在学习的是第3页，共13页一、广群与半群一、广群与半群 定理定理5-3.15-3.1 设是一个半群，B B S S且且*在在B B上封闭上封闭，则也是一个半群，通常称为的子半群子半群。证明：因*在S上可结合，而BS，且*在B上封闭，故*在B上可结合，故为半群。例如：为普通乘法，则,都为的子半群。定理定理5-3.25-3.2 若为半群，且S是有限集，则必有aS,使a*a=a。证明：对任bS,由封闭性知 b*b=b2 S,b3=b2*b S,即是说序列 b,b2,b3,bi bj 都为S中元 现在学习的是第4页，共13页一、广群与半群一、广群与半群因S有限，故存在ji使bi=bj设 P=j-i则 bj=bp*bi=bi故 bp*bi*b=bi*b即 bp*bi+1=bi+1对 qi有 bp*bq=bq由于 p1，故存在k1使kp i即 bp*bkp=bkp这是一个递推关系，即bkp =bp*bkp=bp*(bp*bkp)=bkp*bkp令 bkp=a，即有a*a=a。*本定理说明有限半群必有幂等元。本定理说明有限半群必有幂等元。现在学习的是第5页，共13页二、独异点二、独异点 定义定义5-3.35-3.3 含有幺元含有幺元的半群称为独异点独异点。有时独异点也记。例：（是普通乘法，+是普通加法）n，都为独异点。n 为半群，不含幺元0，故不是独异点。n代数系统1，1，1，1，和Z,都是具有幺元1的半群。因此它们都是独异点。定理定理5-3.35-3.3 设 为独异点，则关于*的运算表中任何两行或两列都不同。证明：设e为幺元。对任a,bS,aba*e=a b*e=b可见a,b所在行不同。同理 e*a=a e*b=b 即a,b所在列也不同。现在学习的是第6页，共13页二、独异点二、独异点 例：I为整数集，Zm为同余类构成的集合，定义+m,m如下：i,j Zm i+mj=(i+j)mod m imj=(i j)mod m 试证明这两个运算表中任两行，两列互异。证明：（这仅需证明这仅需证明 Z,都为独异点即可。都为独异点即可。）事实上：1）+m,m在Zm上封闭。2）对任 i,j,k Zm(i+m j)+m k=i+m(i+m j)=(i+j+k)mod m (i m j)m k=i m(i)m j)=(i j k)mod m 故+m,m都可结合。现在学习的是第7页，共13页二、独异点二、独异点 3）0+m i=i+m 0=i 1 m i=i m 1=i 即 0，1 分别为+m,m的幺元。因此,都为独异点。由定理5-3.3可知，这两个运算的运算表中任何两行或两列都不相同。现在学习的是第8页，共13页二、独异点二、独异点 由定理知其运算表任两行，两列互异。在上例中，如果令m=5，则+5和5的运算表分别如下。（没有两行/列是相同的）现在学习的是第9页，共13页二、独异点二、独异点 定理定理5-3.45-3.4 为独异点，若对任a,bS，且a,b有逆元a-1,b-1,则1）(a-1)-1=a2）a*b有逆且(a*b)-1=b-1*a-1。证明：1）因a有逆a-1，故a*a-1=a-1*a=e 因此(a-1)-1=a 2）因(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=a*a-1=a 同理 (b-1*a-1)*(a*b)=e故 (a*b)-1=b-1*a-1现在学习的是第10页，共13页二、独异点二、独异点例：n阶方阵的集合，对矩阵乘法，若A，B可逆，则(A-1)-1=A(AB)-1=B-1A-1现在学习的是第11页，共13页本课小结 广群广群 半群半群 独异点独异点 现在学习的是第12页，共13页作业 作业：作业：5-3(2)(3)现在学习的是第13页，共13页
