离散数学(第14章)陈瑜.ppt

《离散数学(第14章)陈瑜.ppt》由会员分享，可在线阅读，更多相关《离散数学(第14章)陈瑜.ppt（64页珍藏版）》请在三一办公上搜索。

1、陈瑜,Email：yu2023/11/16,离散数学,计算机学院,2023/11/16,计算机科学与工程学院,2,第五部分：代数结构第14章 代数系统,2023/11/16,计算机科学与工程学院,3,引言,19世纪30年代，在寻找五次方程求解方法的过程中，法国青年数学家伽罗瓦提出了群的概念，证明了高于四次的一般代数方程的不可解性，而且还建立了具体数字系统的代数方程可用根号求解的判别准则，并举出了不能用根号求解的数字系数代数方程的实例。这样，伽罗瓦就彻底地解决了这个在长达200多年的时间使不少数学家伤透脑筋的问题。但是，当时他的思想不被人理解和接受，直到他去世38年后，他的超越时代的天才思想才逐

2、步被人们所承认。之所以说伽罗瓦是超越时代的天才，不仅仅是因为他在方程求解上的贡献，还因为他所发现的结果，他的奇特思想和巧妙方法，发展成为一门新学科-抽象代数学。因此，伽罗瓦作为抽象代数（即近代代数学）的创始人是当之无愧的。,2023/11/16,计算机科学与工程学院,4,主要内容,二元运算代数系统特异元半群与含幺半群,2023/11/16,计算机科学与工程学院,5,代数系统,代数系统又称为代数结构，群、环、域、格和布尔代数是典型的系统。代数系统理论对于可计算模型研究、抽象数据结构、形式语言理论、程序设计语言语义分析等许多方面产生的影响是深远的。代数系统理论提供了对各种表面上不同的实际问题高度抽

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

4、14-1.1：设S是一个非空集合，映射（或函数）f：SnS称为S上的n元代数运算，简称n元运算。当n1时，称为一元运算；当n2时，称为二元运算。为叙述统一起见，我们采用符号“”、“*”表示一般的二元运算符。其具体意义由上下文确定。在描述一个二元运算时，有时也采用一个表的形式表示。本章中除特别声明外所说的运算都指的是二元运算。,2023/11/16,计算机科学与工程学院,9,14.1 二元运算及其性质,定义14-1.1：设S是一个非空集合，映射（或函数）f：SnS称为S上的n元代数运算，简称n元运算。当n1时，称为一元运算；当n2时，称为二元运算。为叙述统一起见，我们采用符号“”、“*”表示一般

5、的二元运算符。其具体意义由上下文确定。在描述一个二元运算时，有时也采用一个表的形式表示。本章中除特别声明外所说的运算都指的是二元运算。,2023/11/16,计算机科学与工程学院,10,例1：设集合S=a，b，c，d。在S上定义一个二元运算“”如下表所示：称这种表为运算表。从运算表看出aa=a，ab=a，ba=a，ca=a，。当集合S所含元素较少时，用运算表的形式定义运算显得一目了然。,2023/11/16,计算机科学与工程学院,11,运算的性质,定义14-1.2：设“”是一个S上的二元代数运算，如果:对任意的a,bS，都有abS，则称“”在S上是封闭的；对任意的a,bS，都有abba,则称“

6、”在S上是可交换的，或称满足交换律。对任意的a,b，cS，都有(ab)ca(bc),则称“”在S上是可结合的，或称满足结合律。,2023/11/16,计算机科学与工程学院,12,运算的性质,定义14-1.2：设“”是一个S上的二元代数运算，如果:对任意的a,bS，都有abS，则称“”在S上是封闭的；对任意的a,bS，都有abba,则称“”在S上是可交换的，或称满足交换律。对任意的a,b，cS，都有(ab)ca(bc),则称“”在S上是可结合的，或称满足结合律。,2023/11/16,计算机科学与工程学院,13,运算的性质,定义14-1.2：设“”是一个S上的二元代数运算，如果:对任意的a,bS

7、，都有abS，则称“”在S上是封闭的；对任意的a,bS，都有abba,则称“”在S上是可交换的，或称满足交换律。对任意的a,b，cS，都有(ab)ca(bc),则称“”在S上是可结合的，或称满足结合律。对任意的aS，满足aaa，则称“”是幂等的。,2023/11/16,计算机科学与工程学院,14,运算的性质,定义14-1.2：设“”是一个S上的二元代数运算，如果:对任意的a,bS，都有abS，则称“”在S上是封闭的；对任意的a,bS，都有abba,则称“”在S上是可交换的，或称满足交换律。对任意的a,b，cS，都有(ab)ca(bc),则称“”在S上是可结合的，或称满足结合律。对任意的aS，满

8、足aaa，则称“”是幂等的。,2023/11/16,计算机科学与工程学院,15,例2：设A=xx=2n，nN，问运算封闭否，呢？解：2r、2sA，2r*2s=2r+sA（）运算封闭 2、4A，2+4A，运算不封闭 2、4A，2/4A，运算不封闭,2023/11/16,计算机科学与工程学院,16,例2：设A=xx=2n，nN，问运算封闭否，呢？解：2r、2sA，2r*2s=2r+sA（）运算封闭 2、4A，2+4A，运算不封闭 2、4A，2/4A，运算不封闭,2023/11/16,计算机科学与工程学院,17,定义14-1.3 设“*”、“”是集合S上的两个二元运算，对a,b,cS，若a(b*c)

9、=(ab)*(ac)且(b*c)a=(ba)*(ca)，则称“”关于“*”在S上是可分配的。“*”、“”是可换运算，若a(a*b)=a及 a*(ab)=a，则称运算“*”与“”满足吸收律。,2023/11/16,计算机科学与工程学院,18,定义14-1.3 设“*”、“”是集合S上的两个二元运算，对a,b,cS，若a(b*c)=(ab)*(ac)且(b*c)a=(ba)*(ca)，则称“”关于“*”在S上是可分配的。“*”、“”是可换运算，若a(a*b)=a及 a*(ab)=a，则称运算“*”与“”满足吸收律。,2023/11/16,计算机科学与工程学院,19,例3 设运算“”、“”分别是实数

10、集R上的最大值和最小值运算，即对任意的a,bR，有ab=max(a,b),ab=min(a,b)，试判断运算“”与“”是否满足分配律和吸收律。解：对任意的a,b,cR,显然有：a(bc)=(ab)(ac),a(bc)=(ab)(ac),又因为“”和“”满足交换律，由定义，“”与“”之间满足分配律。同理，a(ac)=a,a(ac)=a,因此“”与“”之间满足吸收律。所以，“”与“”满足分配律和吸收律。,2023/11/16,计算机科学与工程学院,20,例3 设运算“”、“”分别是实数集R上的最大值和最小值运算，即对任意的a,bR，有ab=max(a,b),ab=min(a,b)，试判断运算“”与

11、“”是否满足分配律和吸收律。解：对任意的a,b,cR,显然有：a(bc)=(ab)(ac),a(bc)=(ab)(ac),又因为“”和“”满足交换律，由定义，“”与“”之间满足分配律。同理，a(ac)=a,a(ac)=a,因此“”与“”之间满足吸收律。所以，“”与“”满足分配律和吸收律。,2023/11/16,计算机科学与工程学院,21,作业,习题14.1：P270：1（1）、2（1）（5）（8）,2023/11/16,计算机科学与工程学院,22,14.2 代数系统,2023/11/16,计算机科学与工程学院,23,定义14-2.1设S是一个非空集合，f1,f2,fm分别是定义在S上的运算，称

12、集合S和f1,f2,fm所组成的系统称为一个代数系统，简称代数，记为。判断集合S及其上的代数运算是否是代数系统，关键是判断两点：一是集合S非空，二是这些运算关于S是否满足封闭性。现实世界中有很多代数系统。对于具有相同性质的代数系统，我们没必要分散进行个别研究，而是进行集中研究，这就形成了特定的代数系统。本教材只介绍半群、群、环、域、格、布尔代数等典型的代数系统，其中重点是半群、群、格与布尔代数。,2023/11/16,计算机科学与工程学院,24,定义14-2.1设S是一个非空集合，f1,f2,fm分别是定义在S上的运算，称集合S和f1,f2,fm所组成的系统称为一个代数系统，简称代数，记为。判

13、断集合S及其上的代数运算是否是代数系统，关键是判断两点：一是集合S非空，二是这些运算关于S是否满足封闭性。现实世界中有很多代数系统。对于具有相同性质的代数系统，我们没必要分散进行个别研究，而是进行集中研究，这就形成了特定的代数系统。本教材只介绍半群、群、环、域、格、布尔代数等典型的代数系统，其中重点是半群、群、格与布尔代数。,2023/11/16,计算机科学与工程学院,25,定义14-2.1设S是一个非空集合，f1,f2,fm分别是定义在S上的运算，称集合S和f1,f2,fm所组成的系统称为一个代数系统，简称代数，记为。判断集合S及其上的代数运算是否是代数系统，关键是判断两点：一是集合S非空，

14、二是这些运算关于S是否满足封闭性。现实世界中有很多代数系统。对于具有相同性质的代数系统，我们没必要分散进行个别研究，而是进行集中研究，这就形成了特定的代数系统。本教材只介绍半群、群、环、域、格、布尔代数等典型的代数系统，其中重点是半群、群、格与布尔代数。,2023/11/16,计算机科学与工程学院,26,例：常见的代数系统如，等等。如果设Mn是全体n阶满秩阵构成的集合，那么，Mn与矩阵乘法“”构成代数系统。另外，同一个集合与不同的运算构成不同的代数系统。例如，在整数集上既可定义运算“+”，也可定义“”，还可以定义运算“max”(即求两个数中的最大值)，相应的代数系统可以表示为，。在同一个代数系

15、统中，有一些特殊元素与所定义的运算紧密相关，在系统结构中起着重要的作用，这些元素被称为特异元。,2023/11/16,计算机科学与工程学院,27,例：常见的代数系统如，等等。如果设Mn是全体n阶满秩阵构成的集合，那么，Mn与矩阵乘法“”构成代数系统。另外，同一个集合与不同的运算构成不同的代数系统。例如，在整数集上既可定义运算“+”，也可定义“”，还可以定义运算“max”(即求两个数中的最大值)，相应的代数系统可以表示为，。在同一个代数系统中，有一些特殊元素与所定义的运算紧密相关，在系统结构中起着重要的作用，这些元素被称为特异元。,2023/11/16,计算机科学与工程学院,28,例：常见的代数

16、系统如，等等。如果设Mn是全体n阶满秩阵构成的集合，那么，Mn与矩阵乘法“”构成代数系统。另外，同一个集合与不同的运算构成不同的代数系统。例如，在整数集上既可定义运算“+”，也可定义“”，还可以定义运算“max”(即求两个数中的最大值)，相应的代数系统可以表示为，。在同一个代数系统中，有一些特殊元素与所定义的运算紧密相关，在系统结构中起着重要的作用，这些元素被称为特异元。,2023/11/16,计算机科学与工程学院,29,特异元,定义14-2.2 设“*”是集合S上的二元运算，是一个代数系统，1)若eS，使得对aS，都有：a*e=e*a=a，则称e为(代数系统）的单位元或幺元；2)若S,使得对

17、aS，都有：a*=*a=，则称为(代数系统)的零元；3)若元素aS，满足a*aa，则称a是(代数系统）的一个幂等元。,2023/11/16,计算机科学与工程学院,30,特异元,定义14-2.2 设“*”是集合S上的二元运算，是一个代数系统，1)若eS，使得对aS，都有：a*e=e*a=a，则称e为(代数系统）的单位元或幺元；2)若S,使得对aS，都有：a*=*a=，则称为(代数系统)的零元；3)若元素aS，满足a*aa，则称a是(代数系统）的一个幂等元。,2023/11/16,计算机科学与工程学院,31,特异元,定义14-2.2 设“*”是集合S上的二元运算，是一个代数系统，1)若eS，使得对

18、aS，都有：a*e=e*a=a，则称e为(代数系统）的单位元或幺元；2)若S,使得对aS，都有：a*=*a=，则称为(代数系统)的零元；3)若元素aS，满足a*aa，则称a是(代数系统）的一个幂等元。,2023/11/16,计算机科学与工程学院,32,例：1）P（S），对运算，是单位元，S是零元，对运算，S是单位元，是零元。2）N，+有单位元0，无零元。,2023/11/16,计算机科学与工程学院,33,定义14-2.3设“*”是集合S上的二元运算,S,*是一个代数系统，e是S,*的幺元，若对aS，bS，使得：a*b=b*a=e，则称b是a的逆元，a也称为可逆的，记为b=a-1（同样，a也为b

19、的逆元，b也称为可逆的，记为b-1）；注意：在一个代数系统中，并不是每个元都是可逆的。,2023/11/16,计算机科学与工程学院,34,例：1）在代数系统中，每个元aZ的逆元是-a。2）在代数系统中，由于单位元是n阶单位阵，因此，元素aMn的逆是A-1。3）对于代数系统而言，除了幺元1以自身为逆元外，其它元素均无逆元。,2023/11/16,计算机科学与工程学院,35,特异元的性质,定理14-2.1 设S,*是一个代数系统：1）若S,*存在幺元，则该幺元唯一；2）若S,*存在零元，则该零元唯一；3）若“*”满足结合律且e是S,*的幺元(即幺元存在)，则对aS，若a存在逆元,则该逆元唯一。证明

20、：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。因此，逆元也是唯一的。,2023/11/16,计算机科学与工程学院,36,特异元的性质,定理14-2.1 设S,*是一个代数系统：1）若S,*存在幺元，则该幺元唯一；2）若S,*存在零元，则该零元唯一；3）若“*”满足结合律且e是S,*的幺元(即幺元存在)，则对aS，若a存在逆元,则该逆元唯一。证明：1）（反证法）设S,*含有幺元e1，e2，根据定义e1=e1*e2=e2，

21、因此，幺元是唯一的。3）设e是 S,*的幺元，元素a有两个逆元a1，a2，则a1=a1*e=a1*（a*a2）=(a1*a)*a2=e*a2=a2。因此，逆元也是唯一的。,2023/11/16,计算机科学与工程学院,37,特异元的性质,定理14-2.1 设S,*是一个代数系统：1）若S,*存在幺元，则该幺元唯一；2）若S,*存在零元，则该零元唯一；3）若“*”满足结合律且e是S,*的幺元(即幺元存在)，则对aS，若a存在逆元,则该逆元唯一。证明：1）（反证法）设S,*含有幺元e1，e2，根据定义e1=e1*e2=e2，因此，幺元是唯一的。3）设e是 S,*的幺元，元素a有两个逆元a1，a2，则

22、a1=a1*e=a1*（a*a2）=(a1*a)*a2=e*a2=a2。因此，逆元也是唯一的。,2023/11/16,计算机科学与工程学院,38,特异元的性质,定理14-2.1 设S,*是一个代数系统：1）若S,*存在幺元，则该幺元唯一；2）若S,*存在零元，则该零元唯一；3）若“*”满足结合律且e是S,*的幺元(即幺元存在)，则对aS，若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。因此

23、，逆元也是唯一的。,2023/11/16,计算机科学与工程学院,39,半群与含幺半群,半群与含么半群是最简单的代数系统之一，它在时序线路、形式语言理论、自动机理论中均有很广泛的应用。一般地，我们把只含一个二元运算的代数系统称为二元代数或广群。半群是二元代数中最简单的代数系统。,2023/11/16,计算机科学与工程学院,40,半群与含幺半群,半群与含么半群是最简单的代数系统之一，它在时序线路、形式语言理论、自动机理论中均有很广泛的应用。一般地，我们把只含一个二元运算的代数系统称为二元代数或广群。半群是二元代数中最简单的代数系统。,2023/11/16,计算机科学与工程学院,41,定义14-2.

24、4设是一个二元代数系统：当“*”是封闭的，称为广群；如果是广群，且“*”是可结合的运算，则称为半群；是半群，且存在幺元e，则称此半群是含幺半群，常记为；如果是含幺半群，且每个元素都有逆元，则称为群。（闭、结、逆、幺）群含幺半群半群广群,2023/11/16,计算机科学与工程学院,42,定义14-2.4设是一个二元代数系统：当“*”是封闭的，称为广群；如果是广群，且“*”是可结合的运算，则称为半群；是半群，且存在幺元e，则称此半群是含幺半群，常记为；如果是含幺半群，且每个元素都有逆元，则称为群。（闭、结、逆、幺）群含幺半群半群广群,2023/11/16,计算机科学与工程学院,43,定义14-2.

25、4设是一个二元代数系统：当“*”是封闭的，称为广群；如果是广群，且“*”是可结合的运算，则称为半群；是半群，且存在幺元e，则称此半群是含幺半群，常记为；如果是含幺半群，且每个元素都有逆元，则称为群。（闭、结、逆、幺）群含幺半群半群广群,2023/11/16,计算机科学与工程学院,44,定义14-2.4设是一个二元代数系统：当“*”是封闭的，称为广群；如果是广群，且“*”是可结合的运算，则称为半群；是半群，且存在幺元e，则称此半群是含幺半群，常记为；如果是含幺半群，且每个元素都有逆元，则称为群。（闭、结、逆、幺）群含幺半群半群广群,2023/11/16,计算机科学与工程学院,45,定义14-2.

26、4设是一个二元代数系统：当“*”是封闭的，称为广群；如果是广群，且“*”是可结合的运算，则称为半群；是半群，且存在幺元e，则称此半群是含幺半群，常记为；如果是含幺半群，且每个元素都有逆元，则称为群。（闭、结、逆、幺）群含幺半群半群广群,2023/11/16,计算机科学与工程学院,46,例：设n0,1,2,n-1，定义n上的运算+n如下：x,yn，x+nyxy(mod n)(即为xy除以n的余数)。证明是含么半群。证明：1）封闭性：x,yn，令kxy(mod n)，则0kn-1，即kn，所以封闭性成立；2）结合律：x,y,zn，有(xny)nzxy+z(mod n)xn(ynz)，所以结合律成立

27、。3）单位元：xn，显然有0+nxx+n0 x，所以0是单位元。故是含么半群。,2023/11/16,计算机科学与工程学院,47,例：设n0,1,2,n-1，定义n上的运算+n如下：x,yn，x+nyxy(mod n)(即为xy除以n的余数)。证明是含么半群。证明：1）封闭性：x,yn，令kxy(mod n)，则0kn-1，即kn，所以封闭性成立；2）结合律：x,y,zn，有(xny)nzxy+z(mod n)xn(ynz)，所以结合律成立。3）单位元：xn，显然有0+nxx+n0 x，所以0是单位元。故是含么半群。,2023/11/16,计算机科学与工程学院,48,例：设n0,1,2,n-1

28、，定义n上的运算+n如下：x,yn，x+nyxy(mod n)(即为xy除以n的余数)。证明是含么半群。证明：1）封闭性：x,yn，令kxy(mod n)，则0kn-1，即kn，所以封闭性成立；2）结合律：x,y,zn，有(xny)nzxy+z(mod n)xn(ynz)，所以结合律成立。3）单位元：xn，显然有0+nxx+n0 x，所以0是单位元。故是含么半群。,2023/11/16,计算机科学与工程学院,49,例：设n0,1,2,n-1，定义n上的运算+n如下：x,yn，x+nyxy(mod n)(即为xy除以n的余数)。证明是含么半群。证明：1）封闭性：x,yn，令kxy(mod n)，

29、则0kn-1，即kn，所以封闭性成立；2）结合律：x,y,zn，有(xny)nzxy+z(mod n)xn(ynz)，所以结合律成立。3）单位元（幺元）：xn，显然有0+nxx+n0 x，所以0是单位元。故是含么半群。,2023/11/16,计算机科学与工程学院,50,例：设kZ，令集合Sk=x|(xZ)(xk)，“+”是一个普通的加法运算，试判断是否是一个半群？解：1)显然二元运算“+”是可结合的；2)若k0，由于kSk，而(k+k)2kk，即(k+k)Sk，故运算“+”在Sk上不是封闭的；若k0，则对x，ySk，有(x+y)Sk，所以运算“+”在Sk上是封闭的。由1)、2)知：当k0时，不

30、是半群；当k0时，是一个半群。,2023/11/16,计算机科学与工程学院,51,例：设kZ，令集合Sk=x|(xZ)(xk)，“+”是一个普通的加法运算，试判断是否是一个半群？解：1)显然二元运算“+”是可结合的；2)若k0，由于kSk，而(k+k)2kk，即(k+k)Sk，故运算“+”在Sk上不是封闭的；若k0，则对x，ySk，有(x+y)Sk，所以运算“+”在Sk上是封闭的。由1)、2)知：当k0时，不是半群；当k0时，是一个半群。,2023/11/16,计算机科学与工程学院,52,例：设kZ，令集合Sk=x|(xZ)(xk)，“+”是一个普通的加法运算，试判断是否是一个半群？解：1)显

31、然二元运算“+”是可结合的；2)若k0，由于kSk，而(k+k)2kk，即(k+k)Sk，故运算“+”在Sk上不是封闭的；若k0，则对x，ySk，有(x+y)Sk，所以运算“+”在Sk上是封闭的。由1)、2)知：当k0时，不是半群；当k0时，是一个半群。,2023/11/16,计算机科学与工程学院,53,例：设kZ，令集合Sk=x|(xZ)(xk)，“+”是一个普通的加法运算，试判断是否是一个半群？解：1)显然二元运算“+”是可结合的；2)若k0，由于kSk，而(k+k)2kk，即(k+k)Sk，故运算“+”在Sk上不是封闭的；若k0，则对x，ySk，有(x+y)Sk，所以运算“+”在Sk上是

32、封闭的。由1)、2)知：当k0时，不是半群；当k0时，是一个半群。,2023/11/16,计算机科学与工程学院,54,例：,是一个可换的半群；0是单位元，也是唯一的幂等元，但没有零元。,是一个可换的半群；1是单位元，0是零元，1和0都是幂等元。是半群，但不是含么半群；无幂等元和零元。是含么半群，其幺元为1；而和对运算不封闭，不是代数系统，也就不是半群；,2023/11/16,计算机科学与工程学院,55,例：,是一个可换的半群；0是单位元，也是唯一的幂等元，但没有零元。,是一个可换的半群；1是单位元，0是零元，1和0都是幂等元。是半群，但不是含么半群；无幂等元和零元。是含么半群，其幺元为1；而和

33、对运算不封闭，不是代数系统，也就不是半群；,2023/11/16,计算机科学与工程学院,56,例：,是一个可换的半群；0是单位元，也是唯一的幂等元，但没有零元。,是一个可换的半群；1是单位元，0是零元，1和0都是幂等元。是半群，但不是含么半群；无幂等元和零元。是含么半群，其幺元为1；而和对运算不封闭，不是代数系统，也就不是半群；,2023/11/16,计算机科学与工程学院,57,例：,是一个可换的半群；0是单位元，也是唯一的幂等元，但没有零元。,是一个可换的半群；1是单位元，0是零元，1和0都是幂等元。是半群，但不是含么半群；无幂等元和零元。是含么半群，其幺元为1；而和对运算不封闭，不是代数系

34、统，也就不是半群；,2023/11/16,计算机科学与工程学院,58,例：,是一个可换的半群；0是单位元，也是唯一的幂等元，但没有零元。,是一个可换的半群；1是单位元，0是零元，1和0都是幂等元。是半群，但不是含么半群；无幂等元和零元。是含么半群，其幺元为1；而和对运算不封闭，不是代数系统，也就不是半群；,2023/11/16,计算机科学与工程学院,59,例：,设Mn(R)为全体nn实数矩阵集合，+和分别是矩阵的加法和乘法运算，则是可交换的含么半群，其幺元为零矩阵；也是唯一的幂等元；无零元；是含么半群，其幺元为单位矩阵，零矩阵是零元，单位矩阵和零矩阵都是幂等元。设A为任意集合，则和都是可交换的

35、含么半群，其的幺元为；零元为A，所有的元均为幂等元。其的幺元为A；零元为，所有的元均为幂等元。,2023/11/16,计算机科学与工程学院,60,例：,设Mn(R)为全体nn实数矩阵集合，+和分别是矩阵的加法和乘法运算，则是可交换的含么半群，其幺元为零矩阵；也是唯一的幂等元；无零元；是含么半群，其幺元为单位矩阵，零矩阵是零元，单位矩阵和零矩阵都是幂等元。设A为任意集合，则和都是可交换的含么半群，其的幺元为；零元为A，所有的元均为幂等元。其的幺元为A；零元为，所有的元均为幂等元。,2023/11/16,计算机科学与工程学院,61,例：,设Aa,b,c,z，A中的元素称为字符，由A中有限个字符组成

36、的序列称为A中的字符串，不包含任何字符的字符串称为空串，用表示，令A*xx是A中的字符串A+A*-为两个字符串的连接：即对任意两个字符串、，为将字符串写在字符串的左边而得到的字符串。显然，既是A*上的二元运算，又是A+上的二元运算，并且满足结合律，但不满足交换律；又对任意A*，有，所以 是A*中关于运算的幺元；也是唯一的幂等元；无零元。因此，是含么半群，而只是半群。,2023/11/16,计算机科学与工程学院,62,例：,设Aa,b,c,z，A中的元素称为字符，由A中有限个字符组成的序列称为A中的字符串，不包含任何字符的字符串称为空串，用表示，令A*xx是A中的字符串A+A*-为两个字符串的连

37、接：即对任意两个字符串、，为将字符串写在字符串的左边而得到的字符串。显然，既是A*上的二元运算，又是A+上的二元运算，并且满足结合律，但不满足交换律；又对任意A*，有，所以 是A*中关于运算的幺元；也是唯一的幂等元；无零元。因此，是含么半群，而只是半群。,2023/11/16,计算机科学与工程学院,63,例：,设Aa,b,c,z，A中的元素称为字符，由A中有限个字符组成的序列称为A中的字符串，不包含任何字符的字符串称为空串，用表示，令A*xx是A中的字符串A+A*-为两个字符串的连接：即对任意两个字符串、，为将字符串写在字符串的左边而得到的字符串。显然，既是A*上的二元运算，又是A+上的二元运算，并且满足结合律，但不满足交换律；又对任意A*，有，所以 是A*中关于运算的幺元；也是唯一的幂等元；无零元。因此，是含么半群，而只是半群。,2023/11/16,计算机科学与工程学院,64,作业,P273 2P274 4,