数字电路课件

《数字电路课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三篇代数系统信息科学与工程学院王新红5-3半群和独异点半群是一种特殊的代数系统，它在形式语言、自动机等领域都有具体的应用。广群、半群与独异点的定义*半群和独异点的性质18371123@qq.com5-3半群和独异点广群、半群与独异点的定义定义5-3.1一个代数系统，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，则称代数系统为广群。定义5-3.2一个代数系统，其中S是非空集合，*是S上的一个二元运算，如果：（1）运算*是封闭的（2）运算*是可结合的，即对任意的x,y,zS，满足(x*y)*z=x*(y*z)则称代数系统为半群。定义5

2、-3.3含有幺元的半群称为独异点（含幺半群，单位半群）18371123@qq.com5-3半群和独异点半群和独异点的性质定理5-3.1设是一个半群，BS且*在B上是封闭的，那么也是一个半群。通常称是的子半群。定理5-3.2设是一个半群，如果S是一个有限集,则必有aS，使得a*a=a.即有限半群必有等幂元。18371123@qq.com5-3半群和独异点半群和独异点的性质定理5-3.3设是一个独异点，则关于运算*的运算表中任何两行或两列都是不相同的。定理5-3.4设是一个独异点，对于任意的a,bS，且a,b均有逆元，

3、则a）(a-1)-1=ab)a*b有逆元，且(a*b)-1=b-1*a-118371123@qq.com5-4群和子群群有限群、无限群、置换群、等幂元群的性质子群子群的性质子群的判别18371123@qq.com5-4群和子群群的定义定义5-4.1设是一个代数系统，其中G是非空集合，*是G上的一个二元运算，如果(1)运算*是封闭的.(2)运算*是可结合的(3)存在幺元e。对于每一个元素xG，存在着它的逆元。则称代数系统是一个群。18371123@qq.com5-4群和子群至此，我们可以概括地说：广群仅仅是一个具有封闭二元运算的非空集合；半群是一个具有结合运算的广群；独

4、异点是具有幺元的的半群；群是每个元素都有逆元的独异点。即有{群}{独异点}{半群}{广群}具有一个二元运算的代数系统广群半群独异点群18371123@qq.com5-4群和子群群的性质定理5-4.1群中不可能有零元。定理5-4.2(群方程存在唯一解)设是一个群，对于a,bG,必存在唯一的xG，使得a*x=b；存在唯一的yG，使得y*a=b。定理5-4.3（消去律）设是一个群，对于a,b,cG,如果有a*b=a*c或者b*a=c*a，则必有b=c。定理5-4.4群的运算表中的每一行或每一列都是G的元素的一个置换。定理5-4.5在群中，除幺

5、元e外，不可能任何有别的等幂元。18371123@qq.com5-5阿贝尔群和循环群阿贝尔群定义5-5.1如果群中的运算*是可交换的，则称该群为阿贝尔群，或称交换群。循环群定义5-5.2设为群，若在G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称该群为循环群，元素a称为循环群G的生成元。循环群的性质定理5-5.2任何一个循环群必定是阿贝尔群。定理5-5.3设是一个由元素aG生成的有限循环群。如果G的阶数是n，即

6、G

7、=n，则an=e，且G={a,a2,a3,…,an-1,an=e}其中，n是使an=e的最小正整数。（称n为元素a的阶）1837112

8、3@qq.com函数函数，定义域和值域入射、满射和双射18371123@qq.com函数：特殊的二元关系定义4-1.1设X和Y是任何两个集合，而f是X到Y的二元关系，如果对于每个xX，有唯一的yY，使得f，称关系f为函数。f记作：f：XY,或XY假如f，则称x为自变元，y称为在f作用下x的象f也记做y=f(x)记f(X)={f(x)

9、xX}Xf(X)18371123@qq.com函数：特殊的二元关系函数与关系有两点区别domf=X定义域ranfY值域共域(1)函数的定义域是X，而不能是X的某个真子集18371123@qq.com函数：特殊的二

10、元关系函数与关系有两点区别xyz非单值单值(2)函数必须是单值的二元关系：单值即一个xX只能对应于唯一的y.xdomf,y,zranf,xfyxfzy=z18371123@qq.com入射、满射和双射入射，1－1映射(injection):从X到Y的映射中，X中没有两个元素有相同的象。设f:XY是入射，即是对任意的x1，x2X，如果x1x2f(x1)f(x2)或者f(x1)=f(x2)x1=x2