Email：fws365@scu.edu.cn 2019年5月1日星期三 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2019年5月1日星期三

主要内容 二元运算 代数系统 特异元 半群与含幺半群 2019/5/1 计算机学院

代数系统 代数系统又称为代数结构，群、环、域、格和布尔代数是典型的代数系统。代数系统理论对于可计算模型研究、抽象数据结构、形式语言理论、程序设计语言语义分析等许多方面产生的影响是深远的。 代数系统理论提供了对各种表面上不同的实际问题高度抽象的途径，使人们更能把握住事物的本质，进行形式化的研究，又反过来指导实践的深入。 2019/5/1 计算机学院

二元运算 定义14.1：设S是一个非空集合，映射（或函数）f ：Sn→S称为S上的n元代数运算，简称n元运算(n-ary Operation)。当n＝1时，称为一元运算；当n＝2时，称为二元运算。 一般采用符号“·”表示二元运算符。 2019/5/1 计算机学院

运算的性质 定义14.2：设“·”是一个S上的二元代数运算，如果 对任意的a, b∈S，都有a·b∈S，则称“·”在S上是封闭的； 对任意的a, b∈S，都有a·b＝b·a 则称“·”在S上是可交换的，或称满足交换律； 对任意的a, b，c∈S，都有 (a·b)·c＝a·(b·c) 则称“·”在S上是可结合的，或称满足结合律； 对任意的a∈S，满足a·a＝a，则称“·”是幂等的。 2019/5/1 计算机学院

问题:在我们已经 学过的知识里面， 这样的集合和运算 存不存在呢? 〈2A，∪，∩〉，〈，，〉 定义14.3 设“*”、“·”是集合S上的两个二元运算，对a,b,cS， 若 a·(b*c)=(a·b)*(a·c)且 (b*c)·a=(b·a)*(c·a)，则称“·”对“*”在S上满足分配律。 设“*”、“·”是可换运算，若a·(a*b)=a及 a*(a·b)=a，则称运算“*”与“·” 满足吸收律。 问题:在我们已经 学过的知识里面， 这样的集合和运算 存不存在呢? 〈2A，∪，∩〉，〈，，〉 2019/5/1 计算机学院

同一个集合与不同的运算构成不同的代数系统 定义14.4 设S是一个非空集合，f1,f2,…, fm分别是定义在S上的运算，称集合S和f1,f2,…, fm所组成的系统称为一个代数系统，简称代数，记为<S，f1,f2,…,fm >。 常见的代数系统有 同一个集合与不同的运算构成不同的代数系统 2019/5/1 计算机学院

特异元 定义14.5 设“*”是集合S上的二元运算，〈S,*〉是一个代数系统， 1）若eS，使得对aS，都有：a*e=e*a=a， （注意：在任意一个代数系统中，并不是都有零元存在）。 3）若元素a∈S，满足a*a＝a，则称a是(代数系统）的一个幂等元。 2019/5/1 计算机学院

注意：在一个代数系统中，并不是每个元都是可 逆的。 定义14.6 设“*”是集合S上的二元运算,〈S,*〉是一个代数系统，e是〈S,*〉的幺元，若对aS，bS，使得：a*b=b*a=e，则称b是a的逆元，a也称为可逆的，记为b=a-1（同样，a也为b的逆元，b也称为可逆的，记为b-1 ）； 注意：在一个代数系统中，并不是每个元都是可 逆的。 2019/5/1 计算机学院

特异元的性质 定理14.1 设〈S,*〉是一个代数系统： 1）若〈S,*〉存在幺元，则该幺元唯一； 2）若〈S,*〉存在零元，则该零元唯一； 3）若“*”满足结合律且e是〈S,*〉的幺元(即幺元存在)，则对aS，若a存在逆元,则该逆元唯一。 证明：1）（反证法）设〈S,*〉含有幺元e1，e2，根据定义e1=e1*e2=e2，因此，幺元是唯一的。 3）设e是〈 S,*〉的幺元，元素a有两个逆元a1，a2，则 a1=a1*e= a1*（a*a2）= (a1*a)*a2=e*a2=a2 因此，逆元也是唯一的。 2019/5/1 计算机学院

半群与含幺半群 广群、半群与含么半群是最简单的代数系统之一，它在时序线路、形式语言理论、自动机理论中均有很广泛的应用。 一般地，我们把只含一个二元运算的代数系统<S,*>称为二元代数。 2019/5/1 计算机学院

定义14.7 设<S，*>是一个二元代数系统： 当“*”是封闭的，称<S，*>为广群； <S，*>是半群，且存在幺元e，则称此半群<S，*>是含幺半群，常记为<S，*，e>； 如果<S，*>是含幺半群，且每个元素都有逆元，则称<S，*>为群。（闭、结、逆、幺） 群含幺半群半群广群 2019/5/1 计算机学院

(x+ny)+nz＝x+y+z(mod n)＝x+n(y+nz) 例14.1 设n＝｛0,1,2,…,n-1｝，定义n上的运算+n如下：x,y∈n，x+ny＝x+y(mod n)(即为x＋y除以n的余数)。证明<n，+n>是含么半群。 证明：封闭性：x,y∈n，令k＝x+y(mod n)， 则0≤k≤n-1，即k∈n，所以封闭性成立； 结合律：x,y,z∈n，有 (x+ny)+nz＝x+y+z(mod n)＝x+n(y+nz) 所以结合律成立。 单位元：x∈n，显然有0+nx＝x+n0＝x 所以0是单位元。故<n，+n>是含么半群。 2019/5/1 计算机学院

例14.2 设kZ，令集合Sk={x|(xZ)∧(xk)}，“+”是一个普通的加法运算，试判断<Sk，+>是否是一个半群？ 解：1)　显然二元运算“+”是可结合的； 2)　① 若k0，由于kSk，而(k+k)＝2k＜k，即(k+k)Sk，故运算“+”在Sk上不是封闭的； ② 若k0，则对x，ySk，有(x+y)Sk，所以运算“+”在Sk上是封闭的。 由1)、2)知：当k0时，<Sk，+>不是半群；当k0时，<Sk，+>是一个半群。 2019/5/1 计算机学院

例14.3 <Z,+>,<N,+>,<R,+>是一个可换的半群； 0是单位元，也是唯一的幂等元，但没有零元。 <Z,×>,<N,×>,<R,×>是一个可换的半群； 1是单位元，0是零元，1和0都是幂等元。 <Q+,+>是半群，但不是含么半群； 无幂等元和零元。 <Q+,×>是含么半群，其幺元为1；而<Q+,->对运算不封闭，因而不是广群，也就不是半群； 2019/5/1 计算机学院

设Mn(R)为全体n×n实数矩阵集合，+和·分别是矩阵的加法和乘法运算，则<Mn(R),+>可交换的含么半群， 其幺元为零矩阵；也是唯一的幂等元；无零元； <Mn(R), ×>是含么半群， 其幺元为单位矩阵，零矩阵是零元，单位矩阵和零矩阵都是幂等元。 设A为任意集合，则<2A,∩>和<2A,∪>都是可交换的含么半群， 其<2A,∩>的幺元为A；零元为，所有的元均为幂等元。 其<2A,∪>的幺元为；零元为A，所有的元均为幂等元。 2019/5/1 计算机学院

A*＝{x｜x是A中的字符串} A+＝A*- 设A＝{a,b,c,…,z}，A中的元素称为字符，由A中有限个字符组成的序列称为A中的字符串，不包含任何字符的字符串称为空串，用表示，令 A*＝{x｜x是A中的字符串} A+＝A*- ·为两个字符串的连接：即对任意两个字符串、， ·为将字符串写在字符串的左边而得到的字符串。 显然， ·既是A*上的二元运算，又是A+上的二元运算，并且满足结合律，但不满足交换律；又对任意∈A*，有·＝·＝，所以 是A*中关于运算的幺元；也是唯一的幂等元；无零元。 因此，<A*, ·>是含么半群，而<A+, ·>只是半群。 2019/5/1 计算机学院

幂 设<S,*>是一个半群,由于*满足结合律，可定义幂运算，即对xS，可定义： x¹=x， x²=x*x， x³=x*x²=x²*x=x*x*x， …… xn=xn-1*x=x*xn-1=x*x*x*……*x。 ……  如果<S,*>有单位元e，可以定义：x0=e 幂运算有如下的公式： 2019/5/1 计算机学院

定理15.1 设<S，*>是半群，aS，m和n是正整数，则 am*an=am+n (am)n=amn 设结论对n=k时成立，则 2019/5/1 计算机学院

am*ak+1 = am*(ak*a) (由幂的定义) = (am*ak)*a (可结合性） = (am+k)*a （归纳假设） 由归纳法可知，结论成立。 ②的证明方法同① 注意：当运算为加法“+”时，上述定理应写成： ma+na=(m+n)a n(ma)=(mn)a 2019/5/1 计算机学院

注意：如果S不是有限集，则不一定有幂等元。 定理15.2 设<S，*>是半群，如果S是有限集，则必有aS，使得 a2=a。 证明：因为<S，*>是半群，S是有限集， 对bS，则元素b1，b2，b3，‥‥中必有重复 的，设bi=bj ，其中j＞i，由 bi=bj-i*bi， 则 对 t≥i 都得到 bt=bj-i*bt， 注意：如果S不是有限集，则不一定有幂等元。 利用上式反复迭代，则对任何正整数k≥1，有 bt=bk（j-i）*bt，（t≥i） 特别，取k使得k(j-i)≥i，同时令t=k(j-i)，则 得到幂等元。 这也是一种构造性的证明方法 2019/5/1 计算机学院

子半群 定义15.1 如果<S,*>是半群，T是S的非空子集，且T对运算*是封闭的，则称<T,*>是半群<S,*>的子半群； 如果<S,*,e>是含幺半群，TS，e∈T，且T对运算*是封闭的，则称<T,*,e>是含幺半群<S,*,e>的含幺子半群。 例：半群<R，×>的子代数<[0，1]，×>，<Z，×>，<R+，×>都是<R，×>的子半群。 2019/5/1 计算机学院

这是在代数系统中一种典型的按定义证明方法 例15.1 设<S，*>是一个可换的含幺半群，M是它的所有的幂等元构成的集合，则<M，*>是<S，*>的一个含幺子半群。 证明：(1)、显然，MS； (2)、<S，*>是含幺半群，所以幺元e存在，又e*e＝e，则e是一个幂等元，即有e∈M，所以M是非空的； (3)、e∈M； (4)对任意a，b∈M，有 (a*b)*(a*b)＝a*(b*a)*b＝a*(a*b)*b ＝(a*a)*(b*b)＝a*b， 即运算“*”关于集合M是封闭的运算。 由(1)、(2)、(3)、(4)知：<M，*>是<S，*>的一个含幺子半群。 这是在代数系统中一种典型的按定义证明方法 2019/5/1 计算机学院

习题十四 2、3、4、5、7 习题十五 2、3、4 2019/5/1 计算机学院