离散数学半群

离散数学半群离散数学半群第一页，共13页一、广群与半群半群是一种特殊的代数系统，在计算机科学领域中，如形式语言，自动机理论等方面，已得到了卓有成效的应用。定义5-3.1为一个代数系统，集合S。*是S上的一个二元运算，如果运算*是封闭的，则称代数系统为广群。定义5-3.2若为广群，且*在S上可结合，，则称为半群。例如：1）幂集P（A）上对称差运算构成半群。2）设Z为整数集，+、-、*是数的加法、减法和乘法，则（Z，+）、（Z，*）都是半群；（Z，-）不是半群。3）Nk={0,1,2,,k-1}上模k加法成半群。第二页，共1...

离散数学半群第一页，共13页一、广群与半群半群是一种特殊的代数系统，在计算机科学领域中，如形式语言，自动机理论等方面，已得到了卓有成效的应用。定义5-3.1为一个代数系统，集合S。*是S上的一个二元运算，如果运算*是封闭的，则称代数系统为广群。定义5-3.2若为广群，且*在S上可结合，，则称为半群。例如：1）幂集P（A）上对称差运算构成半群。2）设Z为整数集，+、-、*是数的加法、减法和乘法，则（Z，+）、（Z，*）都是半群；（Z，-）不是半群。3）Nk={0,1,2,,k-1}上模k加法成半群。第二页，共13页一、广群与半群例题2设S={a,b,c},S上的一个二元运算的定义如下表所示，验证＜S,△＞是半群。△abcaabcbabccabc解：由上表知运算△在S上是封闭的而且对任意x1,x2∈S有x1△x2=x2，且a,b,c都是左幺元，从而对任意的x,y,z∈S都有:x△(y△z)=x△z=z,(x△y)△z=y△z=z因此x△(y△z)=(x△y)△z运算△是可结合的，∴＜S,△＞是半群。第三页，共13页一、广群与半群定理5-3.1设是一个半群，BS且*在B上封闭，则也是一个半群，通常称为的子半群。证明：因*在S上可结合，而BS，且*在B上封闭，故*在B上可结合，故为半群。例如：为普通乘法，则<[0,1],>,<0,1>都为的子半群。定理5-3.2若为半群，且S是有限集，则必有aS,使a*a=a。证明：对任bS,由封闭性知b*b=b2S,b3=b2*bS,即是说序列b,b2,b3,…,bi…bj…都为S中元第四页，共13页一、广群与半群因S有限，故存在j>i使bi=bj设P=j-i则bj=bp*bi=bi故bp*bi*b=bi*b即bp*bi+1=bi+1对q>i有bp*bq=bq由于p1，故存在k1使kpi即bp*bkp=bkp这是一个递推关系，即bkp=bp*bkp=bp*(bp*bkp)=…=bkp*bkp令bkp=a，即有a*a=a。*本定理说明有限半群必有幂等元。第五页，共13页二、独异点定义5-3.3含有幺元的半群称为独异点。有时独异点也记。例：（是普通乘法，+是普通加法），，，都为独异点。为半群，不含幺元0，故不是独异点。代数系统＜{－1，1}，＞，＜[－1，1]，＞，和＜Z,＞都是具有幺元1的半群。因此它们都是独异点。定理5-3.3设为独异点，则关于*的运算表中任何两行或两列都不同。证明：设e为幺元。对任a,bS,aba*e=ab*e=b可见a,b所在行不同。同理e*a=ae*b=b即a,b所在列也不同。第六页，共13页二、独异点例：I为整数集，Zm为同余类构成的集合，定义+m,m如下：[i],[j]Zm[i]+m[j]=[(i+j)modm][i]m[j]=[(ij)modm]试证明这两个运算表中任两行，两列互异。证明：（这仅需证明,都为独异点即可。）事实上：1）+m,m在Zm上封闭。2）对任[i],[j],[k]Zm([i]+m[j])+m[k]=[i]+m([i]+m[j])=[(i+j+k)modm]([i]m[j])m[k]=[i]m([i])m[j])=[(ijk)modm]故+m,m都可结合。第七页，共13页二、独异点3）[0]+m[i]=[i]+m[0]=[i][1]m[i]=[i]m[1]=[i]即[0]，[1]分别为+m,m的幺元。因此,都为独异点。由定理5-3.3可知，这两个运算的运算表中任何两行或两列都不相同。第八页，共13页二、独异点由定理知其运算表任两行，两列互异。在上例中，如果令m=5，则+5和5的运算表分别如下。（没有两行/列是相同的）第九页，共13页二、独异点定理5-3.4为独异点，若对任a,bS，且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=a2）因(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第十页，共13页二、独异点例：n阶方阵的集合，对矩阵乘法，若A，B可逆，则(A-1)-1=A(AB)-1=B-1A-1第十一页，共13页本课小结广群半群独异点第十二页，共13页作业作业：5-3(2)(3)第十三页，共13页

                    本文档为【离散数学半群】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

离散数学半群

你可能还喜欢