[数学]离散数学第11章.ppt

《[数学]离散数学第11章.ppt》由会员分享，可在线阅读，更多相关《[数学]离散数学第11章.ppt（222页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数学数学离散数学第离散数学第11章章代数数学发展到现在，已经成为科学世界中拥有数学发展到现在，已经成为科学世界中拥有100多个主要多个主要分支学科的庞大的分支学科的庞大的“共和国共和国”。大体说来，数学中研究数。大体说来，数学中研究数的部分属于的部分属于代数学代数学的范畴；研究形的部分，属于的范畴；研究形的部分，属于几何学几何学的的范筹；沟通形与数且涉及极限运算的部分，属于范筹；沟通形与数且涉及极限运算的部分，属于分析学分析学的的范围。这三大类数学构成了整个数学的本体与核心。在这范围。这三大类数学构成了整个数学的本体与核心。在这一核心的周围，由于数学通过数与形这两个概念，与其它一核心的周围，由

2、于数学通过数与形这两个概念，与其它科学互相渗透，而出现了许多边缘学科和交叉学科。科学互相渗透，而出现了许多边缘学科和交叉学科。代数发展至今，它包含算术、初等代数、高等代数、数论、代数发展至今，它包含算术、初等代数、高等代数、数论、抽象代数五个部分。抽象代数五个部分。 抽象代数系统代数学的研究历史悠久。代数学的研究历史悠久。 但是，从上世纪初以来，代数但是，从上世纪初以来，代数学的研究对象和研究方法发生了重大变革，形成了抽象学的研究对象和研究方法发生了重大变革，形成了抽象代数学，这一变化可以追溯到上上个世纪伽罗瓦代数学，这一变化可以追溯到上上个世纪伽罗瓦（Galois）提出群的概念。）提出群的概

3、念。 抽象代数学不同于以代数方抽象代数学不同于以代数方程求根和根的分布情况为研究中心的古典代数学，它研程求根和根的分布情况为研究中心的古典代数学，它研究所谓抽象代数系统。被处理的对象和其上的运算（操究所谓抽象代数系统。被处理的对象和其上的运算（操作）称为一个代数系统。人们发现许多不同对象上的运作）称为一个代数系统。人们发现许多不同对象上的运算可以有共同的性质，这些发现将代数学研究引导到更算可以有共同的性质，这些发现将代数学研究引导到更高的层次高的层次抽象代数系统研究。抽象代数系统研究。伽罗瓦伽罗瓦Galois, Evariste,1811-1832 法国数学家。法国数学家。1811年年10月月

4、25日生于巴黎附近的小镇。日生于巴黎附近的小镇。15岁岁后开始显示数学的天分，但两次报考巴黎理工后开始显示数学的天分，但两次报考巴黎理工(Ecole Polytechnique)被拒。被拒。1827年开始自学勒让德、拉格朗日、年开始自学勒让德、拉格朗日、高斯和柯西等人的论著。高斯和柯西等人的论著。1828-1830年，得到许多后来称年，得到许多后来称为伽罗瓦理论的重要结果。为伽罗瓦理论的重要结果。1830年进入高等师范学校年进入高等师范学校(Ecole Normale)学习，由于参加政治斗争被学学习，由于参加政治斗争被学校除名，并两次入狱。校除名，并两次入狱。 1832年年5月月31日，日，由

5、于政治和爱情的纠葛在一次决斗中被由于政治和爱情的纠葛在一次决斗中被打死。伽罗瓦生前并未获得应有的荣誉。打死。伽罗瓦生前并未获得应有的荣誉。他三次投到巴黎科学院的论文均被遗失他三次投到巴黎科学院的论文均被遗失或退回。直到或退回。直到1846年，伽罗瓦的手稿才年，伽罗瓦的手稿才公开发表。公开发表。1870年，伽罗瓦的工作才被年，伽罗瓦的工作才被完全理解。完全理解。 A drawing done in 1848 from memory by Evaristes brother 被誉为天才数学家的伽罗瓦被誉为天才数学家的伽罗瓦他深入研究了一个方程能用根式求解所必须满足的本他深入研究了一个方程能用根式求

6、解所必须满足的本质条件，他提出的质条件，他提出的“伽罗瓦域伽罗瓦域”、“伽罗瓦群伽罗瓦群”和和“伽罗瓦理论伽罗瓦理论”都是近世代数所研究的最重要的课题。都是近世代数所研究的最重要的课题。伽罗瓦群理论被公认为十九世纪最杰出的数学成就之伽罗瓦群理论被公认为十九世纪最杰出的数学成就之一。一。他给方程可解性问题提供了全面而透彻的解答，解决他给方程可解性问题提供了全面而透彻的解答，解决了困扰数学家们长达数百年之久的问题。了困扰数学家们长达数百年之久的问题。伽罗瓦群论还给出了判断几何图形能否用直尺和圆规伽罗瓦群论还给出了判断几何图形能否用直尺和圆规作图的一般判别法，圆满解决了三等分任意角或倍立作图的一般判

7、别法，圆满解决了三等分任意角或倍立方体的问题都是不可解的。方体的问题都是不可解的。最重要的是，群论开辟了全新的研究领域，以结构研最重要的是，群论开辟了全新的研究领域，以结构研究代替计算，把从偏重计算研究的思维方式转变为用究代替计算，把从偏重计算研究的思维方式转变为用结构观念研究的思维方式，并把数学运算归类，使群结构观念研究的思维方式，并把数学运算归类，使群论迅速发展成为一门崭新的数学分支，对近世代数的论迅速发展成为一门崭新的数学分支，对近世代数的形成和发展产生了巨大影响。同时这种理论对于物理形成和发展产生了巨大影响。同时这种理论对于物理学、化学的发展，甚至对于二十世纪结构主义哲学的学、化学的发

8、展，甚至对于二十世纪结构主义哲学的产生和发展都发生了巨大的影响。产生和发展都发生了巨大的影响。 抽象代数系统在抽象代数系统中，对象是抽象的而不是具体的，对象上在抽象代数系统中，对象是抽象的而不是具体的，对象上的运算也是抽象的，其含义由一组给定公理规定。由于抽的运算也是抽象的，其含义由一组给定公理规定。由于抽象代数学研究一般的数学结构，它对现代数学研究具有基象代数学研究一般的数学结构，它对现代数学研究具有基本的重要性，它的方法和结果已经渗透到许多不同的数学、本的重要性，它的方法和结果已经渗透到许多不同的数学、物理学以及化学等领域，显著地影响了现代科学的发展。物理学以及化学等领域，显著地影响了现代

9、科学的发展。抽象代数系统的一些基本内容已经成为科学工作者必备的抽象代数系统的一些基本内容已经成为科学工作者必备的理论知识。理论知识。 特别应该指出，抽象代数系统在计算机科学研究中始终占特别应该指出，抽象代数系统在计算机科学研究中始终占有重要的地位和作用，对计算机科学的产生和发展具有决有重要的地位和作用，对计算机科学的产生和发展具有决定性的影响。定性的影响。抽象代数系统毫无疑问，没有抽象代数结构研究和数理逻辑研究的先行发展，图灵就不可能在1936年提出图灵机这样的代数结构作为计算的模型，从而第一次精确地定义了计算的概念和证明了计算机在理论上的存在性。在上世纪4050年代，格和布尔代数成为电子计算

10、机硬件设计以及通信系统设计中的重要工具，而半群理论在自动机和形式语言研究中发挥了重要作用。70年代在数据库研究中人们发现关系代数理论能够作为数据库的理论模型；泛代数和多类代数是程序设计方法学研究中的有力工具；抽象数据类型代数规范理论和技术广泛应用于计算机软件形式说明和开发以及硬件体系结构设计。抽象代数系统在计算机算法设计与分析中，代数算法研究占有主导地位，在计算机算法设计与分析中，代数算法研究占有主导地位，因为它们便于形式描述、正确性和终止性证明以及复杂性因为它们便于形式描述、正确性和终止性证明以及复杂性分析。尤其值得注意的是，基于代数理论的符号计算技术分析。尤其值得注意的是，基于代数理论的符

11、号计算技术和计算机代数系统自和计算机代数系统自80年代以来在自动推理和智能教学年代以来在自动推理和智能教学系统研究中获得了广泛的应用，由此形成的自动定理证明系统研究中获得了广泛的应用，由此形成的自动定理证明的代数式方法与传统方法比较具有明显的优越性，使计算的代数式方法与传统方法比较具有明显的优越性，使计算机实际证明数学定理和发现新的数学结果成为可能。机实际证明数学定理和发现新的数学结果成为可能。代数系统是离散数学的重要组成部分。我们将介绍抽象代代数系统是离散数学的重要组成部分。我们将介绍抽象代数系统的基本概念和基本理论，介绍几类基本的抽象代数数系统的基本概念和基本理论，介绍几类基本的抽象代数系

12、统：系统： 半群、群、环和域等。半群、群、环和域等。第十一章第十一章 群和环群和环 111 代数运算的基本概念代数运算的基本概念 定义：设定义：设 A、B、D是三个任意的非空集。一个是三个任意的非空集。一个A B到到D 的函数的函数 * ，叫做一个，叫做一个A B到到D的的代数运算代数运算。按照我们的定义，一个代数运算只是一种特殊的函数，给按照我们的定义，一个代数运算只是一种特殊的函数，给了了A中的任意一个元素中的任意一个元素a和和B中任意一个元素中任意一个元素b，我们可以，我们可以通过这个运算，得到唯一的一个结果，即存在唯一的通过这个运算，得到唯一的一个结果，即存在唯一的d D，使得，使得

13、* (a，b)=d。由于代数运算是一种特殊的函。由于代数运算是一种特殊的函数，描写它的符号，也可以特殊一点。我们记数，描写它的符号，也可以特殊一点。我们记 * (a，b)=d 为为 a*b =d。从定义不难知道，一个代数运算是可以任意规定的。例例1 N是自然数集是自然数集。 普通加法普通加法“+”是一个是一个NN到到N的运算。的运算。 普遍除法普遍除法“”是一个是一个 NZ+到到Q的运算的运算, 其中其中Z+=x Z x0, Z为整数集合为整数集合, Q为有为有理数集。理数集。例例2 N是自然数集，定义是自然数集，定义 NN到到N 上的一个函数上的一个函数 * ： 对于任意的对于任意的m，n

14、N， *(m，n)=mn “*”即是一个即是一个NN到到N的运算的运算, 对于任意的对于任意的m，n N， m*n=mn00=？例3 异或函数异或函数设设 A=奇，偶奇，偶。我们定义一个。我们定义一个AA 到到A的函数的函数 * ： （奇，奇）（奇，奇） 偶，偶， （奇，偶）（奇，偶） 奇，奇， （偶，奇）（偶，奇） 奇，奇， （偶，偶）（偶，偶） 偶。偶。“ * ”是一个是一个AA到到 A的运算。的运算。这个运算的集合这个运算的集合 是有限集。我们可以用一个表，叫运算表是有限集。我们可以用一个表，叫运算表来给予说明。来给予说明。*奇奇偶偶奇奇偶偶奇奇偶偶奇奇偶偶定义 A，B是两个非空集合。设

15、是两个非空集合。设 * 是是AA到到B的一个运算，我的一个运算，我们称们称 * 是是集合集合A上上的一个代数运算或二元运算。的一个代数运算或二元运算。若若BA，我们说，我们说*是集合是集合A上的上的闭运算闭运算。也说集合。也说集合A对运对运算算 * 是封闭的。是封闭的。 闭运算的例子： 例1中的加法运算 例2 例3交换律定义：定义： 设设A，B是两个非空集合，一个是两个非空集合，一个AA 到到B的一个的一个代数运算代数运算 * 适合交换律，若对于适合交换律，若对于A中任意的两个中任意的两个元素元素a和和b来说，都有来说，都有 a*b=b*a。显然，数的运算中，加法是适合交换律的，而减法则不适显

16、然，数的运算中，加法是适合交换律的，而减法则不适合交换律。合交换律。结合律定义：设定义：设A是一个非空集，一个是一个非空集，一个A上的闭运算上的闭运算 * 适合结合适合结合律，假如对于律，假如对于A中任意的三个元素中任意的三个元素a，b和和c来说，来说，都有都有 (a*b)*c =a*(b*c)。注意：注意： 有时，若有时，若 * 是一个是一个AA 到到B 的一个代数运算，而的一个代数运算，而且象集且象集*(AA )A，这时候也可以讨论，这时候也可以讨论 * 是否满是否满足结合律。足结合律。?例4Z是整数集，是整数集，* 是是Z上一个二元运算，对于任意的上一个二元运算，对于任意的m，n Z，m

17、*n=m+n-5。 问：问：* 是可交换的二元运算吗？是可交换的二元运算吗？ * 是可是可结合的二元运算吗？结合的二元运算吗？解：对于任意的解：对于任意的m，n Z， m*n=m+n-5，n*m=n+m-5, 又又m+n-5=n+m-5， m*n=n*m，故，故 * 是可交换的。是可交换的。 对于任意的对于任意的m，n，l Z， （m*n）*l =（m+n-5）*l=m+n+l-10, 又又m*（n*l）=m+n+l-10, （m*n）*l=m*（n*l），故），故 * 是可结合的。是可结合的。例5设设A是一个非空集合。记是一个非空集合。记 AA=fAA|f: AA，即对于任意即对于任意f A

18、A，f是是A到到A的一个映射。的一个映射。在在AA上，我们定义一个运算上，我们定义一个运算“ ”, 即映射的复合运算：即映射的复合运算：对于任意的对于任意的f1，f2 AA，f1 f2为为f1 f2: AAxf1(f2(x)由定义知由定义知“ ”是封闭的，是封闭的，容易验证，容易验证，“ ”是可结合的。是可结合的。例5 (续)在在A是多于是多于1个元素的集合时，个元素的集合时，“ ”不是不是AA上的可交换上的可交换的二元运算。的二元运算。 下面是一个反例。下面是一个反例。若若|A|1, 设设a1,a2 A, a1a2, 我们定义我们定义f1,f2如下：如下：f1: AA xx, xa1, xa

19、2 a1a1 a2a1f2: AA xx, xa1, xa2 a1a2 a2a2则容易说明：则容易说明： f1 f2(a1)=a1， f2 f1(a1)=a2，即即 f1 f2(a1) f2 f1(a1)例6N是自然数集合，在是自然数集合，在N上定义运算上定义运算 * ：对于任意的对于任意的m，n N，m*n=m+2n。* 是可交换的吗？是可交换的吗？* 适合结合律吗？适合结合律吗？解：解：取取m=1，n=2, m*n=1 * 2=1+22=5,而而n*m=2 * 1=2+21=4m *n * 是不可交换的。是不可交换的。 取取m=1, n=2, l=3，（m *n ）* l=(m+2n)+2

20、l=1+4+6=11,而而m*(n*l)=m+2(n+2l)=1+4+12=17 （m*n）*lm*（n*l）所以所以 * 不适合结合律。不适合结合律。例7A=a,b,c, 右表给出了集合右表给出了集合A上的一个上的一个*运算表。问运算表。问: * 是否是否适合结合律？是否适合交换律？适合结合律？是否适合交换律？ 解：由于上表的运算表是对称的，所以可以断定解：由于上表的运算表是对称的，所以可以断定 *适合交适合交换律，是否符合结合律，须对式子：换律，是否符合结合律，须对式子：(x*y)*z与与x*(y*z)讨讨论在论在x为为a，b或或c；y为为a，b或或c；和；和z为为a，b或或c即总共即总共

21、27种情况下，是否分别相等。只有种情况下，是否分别相等。只有27种情况全相等，才有种情况全相等，才有 * 适合结合律。当然在具体验算时，可以采取适当的方式以适合结合律。当然在具体验算时，可以采取适当的方式以减少验算的次数。例如，表中的减少验算的次数。例如，表中的a元素有性质，对任意的元素有性质，对任意的x属于，属于，a*x=x。则我们无须讨论。则我们无须讨论x，y，z中任何一个为中任何一个为a的情况。的情况。同时，同时，* 适合交换律适合交换律，又可以减少一些情况。经，又可以减少一些情况。经验证验证 * 运算适合结合律。运算适合结合律。* a b ca a b cb b c ac c a b

22、例A=a,b,c, 右表给出了集合右表给出了集合A上的一个上的一个*运算表。问运算表。问: * 是否是否适合结合律？是否适合交换律？适合结合律？是否适合交换律？ 解：显然，解：显然， b*c=cb=c*b即即 *不满足交换率。不满足交换率。 显然，显然，(a*b)*c=b*c=c而而 a*(b*c)=a*c=bc=(a*b)*c,即有： *不满足结合率。* a b ca a b bb a b cc a b a 例对于实数集合对于实数集合R,下表所列的二元运算是否具有左边一列下表所列的二元运算是否具有左边一列中的那些性质中的那些性质. + maxmin|x-y|满足交换率满足结合率可交换,但不可

23、结合n元运算（元运算（n1）设设A，B是两个非空集合，是两个非空集合， n1是正整数，我们称一个是正整数，我们称一个An到到B的映射的映射 “*” 为为A上一个上一个n元运算。元运算。一元运算例子：一元运算例子：nR是实数集，是实数集，R上绝对值运算，可以称为上绝对值运算，可以称为R上一个一上一个一元运算。元运算。nA是一个集合，是一个集合，2A是是A的幂集合，集合的补运算是的幂集合，集合的补运算是2A上的一个一元运算。上的一个一元运算。注意：注意： 一般地，通常讨论一般地，通常讨论B=A的情况。的情况。n元运算（元运算（n1）的其它定义）的其它定义设设A是非空集合，是非空集合， n1是正整数

24、，称一个是正整数，称一个An到到A的映射的映射 “*” 为为A上一个上一个n元运算。元运算。n元运算例子：元运算例子：nR是实数集，下面是实数集，下面R上一个上一个n元运算：元运算： *(x1,x2,xn)=x1+x2+xn112 代数系统和半群代数系统和半群设设A是一个集合，是一个集合，*1，*2，*n是是A上的上的n个代数运个代数运算，而算，而（A，*1，*2，*n）表示集合表示集合A，以及，以及A上上的的n个代数运算个代数运算*1，*2，*n组成的一个组成的一个代数系统代数系统。 主要研究内容：主要研究内容：只有一个代数运算的代数系统只有一个代数运算的代数系统 （A，*）。 例 代数系统

25、（N，+）表示自然数集带着数的加法。）表示自然数集带着数的加法。 代数系统（N， ）表示自然数集带着数的乘法。）表示自然数集带着数的乘法。 代数系统（N，）表示自然数集和数的减法运算。，）表示自然数集和数的减法运算。注意注意: 对于代数系统对于代数系统(A,*)来说来说, *是是A上的代数运算上的代数运算. 按定按定义义, *是是AA到集合到集合B的函数的函数,那自然会问那自然会问 B=? 一般一般地地, 我们可把我们可把B理解为理解为A或象集或象集*(AA).同态函数同态函数定义定义1：设（设（A，*），（），（A1，）是两个代数系统，）是两个代数系统，*是是A上的一个二元运算，上的一个二元

26、运算，是是A1上一个二元运算。一个上一个二元运算。一个函数（映射）函数（映射）f：AA1是是A到到A1的的同态函数同态函数（映（映射）射） ，若对于，若对于A中的任意两个元素中的任意两个元素a1，a2，有，有 f（a1*a2）=f（a1）f（a2）。）。并且，并且， 若若f是单射，说是单射，说f是是单一同态函数单一同态函数； 若若f是满射，说是满射，说f是是满同态函数满同态函数； 若若f是双射，说是双射，说f是是同构函数同构函数（映射）。（映射）。单同态、满同态、同构两个代数系统之间若存在单一同态函数，说这两个代数两个代数系统之间若存在单一同态函数，说这两个代数系统是系统是单同态单同态的；的；

27、两个代数系统之间若存在满同态函数，说这两个代数系两个代数系统之间若存在满同态函数，说这两个代数系统是统是满同态满同态的；的；两个代数系统之间若存在同构函数，说这两个代数系统两个代数系统之间若存在同构函数，说这两个代数系统是是同构同构的。的。例Z是整数集，是整数集，Z上的二元运算是数的加法，即（上的二元运算是数的加法，即（Z，）。，）。A=1，-1，A上的二元运算是数的乘法，即（上的二元运算是数的乘法，即（A， ）。）。分别定义三个分别定义三个Z到到A的函数如下的函数如下11： ZA ZA，对于每一个，对于每一个n n Z Z，1(n)=11(n)=1。22： ZA ZA，对于每一个，对于每一个

28、n n Z Z，若，若n n是偶数，是偶数，2(n)=12(n)=1；若；若n n是奇数，是奇数，2(n)=-12(n)=-1。33： ZA ZA，对于每一个，对于每一个n n Z Z，3(n)=-13(n)=-1。则则 1 1是同态函数是同态函数 （见第（见第139139页的例页的例1 1），）， 2 2是满同态函数（见第是满同态函数（见第140140页的例页的例2 2） ， 3 3不是同态函数不是同态函数（见第（见第140140页的例页的例3 3）。例1显然，对于显然，对于Z中的任意二个数中的任意二个数n1和和n2，有，有 1(n1)=1，1(n2)=1，1(n1+n2)=1， 1(n1+

29、n2)=1(n1) 1(n2)故故1是同态函数。是同态函数。例2显然显然22是是Z Z到到A A的满射。对于的满射。对于Z Z中的任意的二个数中的任意的二个数n1n1和和n2n2来说：来说：若若n1n1和和n2n2均是偶数，那末均是偶数，那末2(n1)=2(n2)=12(n1)=2(n2)=1，而，而2(n1+n2)=12(n1+n2)=1，所以，所以 2(n1+n2)=2(n1)2(n2) 2(n1+n2)=2(n1)2(n2)。若若n1n1和和n2n2均是奇数，那末均是奇数，那末2(n1)=2(n2)=-12(n1)=2(n2)=-1，而，而2(n1+n2)=12(n1+n2)=1，所以，

30、所以2(n1+n2)=2(n1)2(n2) 2(n1+n2)=2(n1)2(n2) 。若若n1n1和和n2n2一个奇数，一个偶数，不失一般性设一个奇数，一个偶数，不失一般性设n1n1是奇数，是奇数，n2n2是偶数，那末是偶数，那末2(n1)=-1, 2(n2)=12(n1)=-1, 2(n2)=1，而，而 2(n1+n2)=-1 2(n1+n2)=-1，所以所以2(n1+n2)=2(n1)2(n2)2(n1+n2)=2(n1)2(n2)。所以所以22是是满同态满同态映射。映射。即（即（Z，+）与（）与（A，）是两个）是两个满同态满同态代数系统。代数系统。例3取n1=2，n2=3时， 3(n1+

31、n2)= 3(5)=-1,3(n1+n2)= 3(5)=-1,而3(n1)= 3(n2)=-1，即有3(n1+n2) 3(n1) 3(n2)。所以33不是同态映射。以上例子说明两个代数系统之间可以建立多个同态映射，以上例子说明两个代数系统之间可以建立多个同态映射，而两个代数系统同态，并不表示两个集合之间的任何一个而两个代数系统同态，并不表示两个集合之间的任何一个映射都是同态映射。映射都是同态映射。例设（设（R， ）和（）和（R+，）是两个代数系统，其中）是两个代数系统，其中R与与R+分别为实数集合、正实数集合，分别为实数集合、正实数集合， 与与分别为算术减分别为算术减法、除法。证明：法、除法。

32、证明： （R， ）和（）和（R+，）同构。）同构。提示提示: 作映射作映射 f: R R+x R, f(x)=ex 可以说明可以说明, f是同态的双射。是同态的双射。定理1 （A1，*1）和（）和（A2，*2）是两个代数系统，且）是两个代数系统，且（A1，*1）与（）与（A2，*2）满同态满同态。若若“*1”适合交换律，则适合交换律，则“*2”也适合交换律；也适合交换律；若若“*1”适合结合律，则适合结合律，则“*2”也适合结合律。也适合结合律。定理1的证明 因为（因为（A1，*1）与（）与（A2，*2）满同态满同态，所以存在，所以存在f：A1A2，是满同态映射。对于是满同态映射。对于A2中的

33、任意二个元素中的任意二个元素a2和和b2，存在，存在a1和和b1属于属于A1，有，有f(a1)=a2，f(b1)=b2，所以，所以a2*2b2=f(a1)*2f(a2)=f(a1*1b1)=f(b1*1a1)=f(b1)*2f(a1)=b2*2a2。即。即*2适合交换律。适合交换律。对于对于A2中的任意三个元素中的任意三个元素a2，b2和和c2，有，有a1，b1，c1 A1，使得使得f(a1)=a2，f(b1)=b2，f(c1)=c2。所以。所以,利用利用*1的结合的结合律有律有(a2*2b2)*2c2=(f(a1)*2f(b1)*2f(c1) =f(a1*1b1)*2f(c1)=f(a1*1

34、b1)*1c1)=f(a1*1(b1*1c1)=f(a1)*2f(b1*1c1)=a2*2(b2*2c2)即即*2也适合结合律。也适合结合律。半群定义定义2：设（：设（A，*）是一个代数系统，）是一个代数系统，A是一个非空集，是一个非空集，*是是A上的一个二元运算。若上的一个二元运算。若*是是A上的闭运算，上的闭运算，且且*适合结合律，我们说（适合结合律，我们说（A，*）是一个半群。）是一个半群。例例 n （N，+）表示自然数集带着数的加法）表示自然数集带着数的加法, 构成半群。构成半群。n （N， ）表示自然数集带着数的乘法）表示自然数集带着数的乘法, 构成半群。构成半群。n （N，）即自然

35、数集和数的减法运算，就不是半群了。，）即自然数集和数的减法运算，就不是半群了。因为减法既不封闭，又不适合结合律。因为减法既不封闭，又不适合结合律。n 我们在自然数集上还可以定义许多的二元运算，使它们我们在自然数集上还可以定义许多的二元运算，使它们构成半群。例如，对于任意二个自然数构成半群。例如，对于任意二个自然数m和和n，我们定义，我们定义“ * ”运算：运算：m*n=m+n+mn。不难验证。不难验证“*”是是N上的闭上的闭运算且适合结合律，（运算且适合结合律，（N，*）也是一个半群。）也是一个半群。例题设设f1,f2是代数系统是代数系统(A, )到代数系统到代数系统(B,*)的同态，的同态，

36、设设g为为A到到B的映射，使得的映射，使得 a A就有就有g(a)=f1(a)*f2(a)，证明若证明若(B,*)是一个可交换的半群是一个可交换的半群,那么那么g为为A到到B的同态。的同态。证明：证明： a,b A, g(a b)=f1(a b)* f2(a b)f1,f2为同态映射，为同态映射，g(a b)=f1(a b)*f2(a b) =(f1(a)*f1(b)* (f2(a)*f2(b) (B,*)可交换的半群，可交换的半群，g(a b)= f1(a)*(f1(b)*f2(a)*f2(b) =(f1(a)*f2(a)*(f1(b)*f2(b) =g(a)*g(b)g为为A到到B的同态的

37、同态左幺元、右幺元、幺元设（设（A，*）是一个代数系统，）是一个代数系统，若存在若存在e右右 A，使得对于任意的，使得对于任意的a A，有，有 a*e右右=a，说说e右右是是右幺元右幺元。若存在若存在e左左 A，使得对于任意的，使得对于任意的a A，有，有e左左*a=a，说说e左左是是左幺元左幺元。一个元素一个元素e A ，它既是左幺元，又是右幺元，称，它既是左幺元，又是右幺元，称e是是幺元幺元（又称（又称单位元单位元）。）。例A=a,b,c, 下面给出了集合下面给出了集合A上的两个上的两个*运算表。运算表。* a b ca a b cb b c ac c a b * a b ca a b b

38、b a b cc a b a a是左幺元 a是右幺元 a是幺元 b是左幺元 无右幺元 无幺元运算表运算表二元运算满足二元运算满足可交换性可交换性的充分必要条件是运算表关于的充分必要条件是运算表关于主对角线对称。主对角线对称。 二元运算有二元运算有左幺元左幺元的充分必要条件是该元素对应的行的充分必要条件是该元素对应的行与该表表头的行相一致。与该表表头的行相一致。二元运算有二元运算有右幺元右幺元的充分必要条件是该元素对应的列的充分必要条件是该元素对应的列与该表表头的列相一致。与该表表头的列相一致。二元运算有二元运算有幺元幺元的充分必要条件是该元素对应的行和的充分必要条件是该元素对应的行和列依次与该

39、表表头的行、列相一致。列依次与该表表头的行、列相一致。当当S是有穷集合时，其上的二元运算常可用运算表给出，是有穷集合时，其上的二元运算常可用运算表给出，运算的一些性质可直接由运算表看出。运算的一些性质可直接由运算表看出。定理2设（设（A，*）是一个代数系统，若它既有左幺元，又有右）是一个代数系统，若它既有左幺元，又有右幺元，则左幺元等于右幺元。若有幺元，则幺元唯一。幺元，则左幺元等于右幺元。若有幺元，则幺元唯一。证明：证明：设设e左左，e右右 A分别是左、右幺元，则有：分别是左、右幺元，则有：e左左=e左左*e右右=e右右。 若有若有e1，e2 A ，且均是么元，则也有：，且均是么元，则也有：

40、e1=e1*e2=e2。注意：注意： 我们往往用我们往往用e 表示么元。表示么元。含幺半群我们称含有幺元的半群为我们称含有幺元的半群为含幺半群含幺半群。例例 0是半群（是半群（N，+）的么元，）的么元， （N，+）是含幺半群。）是含幺半群。 1是半群（是半群（N，）的么元，（）的么元，（N，）是含幺半群。）是含幺半群。 设设A是一个任意的集合，是一个任意的集合，2A是是A的幂集合，集合的并运的幂集合，集合的并运算算是是2A上的一个二元运算，由第六章集合运算的性上的一个二元运算，由第六章集合运算的性质知，并运算是质知，并运算是2A上的闭运算，且满足结合律，所以上的闭运算，且满足结合律，所以（2A

41、，）是一个半群。显然，）是一个半群。显然， 2A是幺元，即是幺元，即（2A，）也是含幺半群。）也是含幺半群。子半群定义：（定义：（A，*）是一个半群，）是一个半群，BA，若（，若（B，*）本）本身是一个半群，我们说（身是一个半群，我们说（B，*）是（）是（A，*）的）的子半群。子半群。考察半群（考察半群（A，*）的一个非空子集）的一个非空子集BA是否是是否是A的子半群，的子半群，按定义需考察二条，即按定义需考察二条，即 “*”是否是是否是B上封闭的二元运算；上封闭的二元运算； “*”是否是是否是B上可结合的二元运算。上可结合的二元运算。由于由于BA，而，而“*”是是A上可结合的二元运算，所以显

42、然也上可结合的二元运算，所以显然也是是A的子集的子集B上的可结合的二元运算。所以我们仅需考察上的可结合的二元运算。所以我们仅需考察“*”是否是是否是B上的闭运算。上的闭运算。性质性质（A，*）是一个半群，）是一个半群，BA。设设b B，若，若B是是A的子半群，则的子半群，则 b2,b3,bn,均属于均属于B，也即对于任意正整数也即对于任意正整数n，bn B，这里这里b2=b*b, 其它类推。其它类推。因为 * 是在B上的闭运算子含幺半群子含幺半群（A，*）是一个含幺半群，）是一个含幺半群，e A是幺元，是幺元，我们说（我们说（B，*）是（）是（A，*）的子含幺半群，若）的子含幺半群，若BA，（

43、B，*）本身是一个半群，且）本身是一个半群，且e B。注意注意 B一定是含幺半群，而且其幺元就是一定是含幺半群，而且其幺元就是A的幺元。的幺元。 如果仅要求如果仅要求“（B，*）是一个含幺半群）是一个含幺半群”，其幺元未必，其幺元未必就一定是就一定是A的幺元。的幺元。例设设A=（aij）nn|aij R是是实数集上实数集上n阶方阶的集合，阶方阶的集合，A关于矩阵的乘法运算构成一关于矩阵的乘法运算构成一个含幺半群，幺元是：个含幺半群，幺元是：令令B=（aij）nn|aij R，ain=ani=0，1in按我们的定义按我们的定义B不是不是A的子含幺半群。的子含幺半群。不难证明不难证明BA，且，且B

44、关于矩阵的关于矩阵的乘法运算本身构成一个含幺半群，乘法运算本身构成一个含幺半群，幺元是：幺元是：1 0 0 0 00 1 0 0 00 0 1 0 0 0 0 0 1 00 0 0 0 11 0 0 0 00 1 0 0 00 0 1 0 0 0 0 0 1 00 0 0 0 0113 群的基本概念群的基本概念定义1 ： (A，*)是一个代数系统，是一个代数系统，e A是幺元，是幺元，a A，若存在若存在b A，使得，使得a*b=e，说，说b是是a的的右逆元右逆元；若存在若存在d A，使得，使得d*a=e，说，说d是是a的的左逆元左逆元。若存在若存在a A，使得，使得a既是既是a的左逆元，又是

45、的左逆元，又是a的右逆元，说的右逆元，说a是是a的的逆元逆元。注意: 关于左、右逆元，我们在定义一个函数的左逆函数，右逆函数中已经接触了。 例 （AA， ）设设 f：AA，参考第，参考第94页的定义页的定义2与定理与定理4，我们有：，我们有： 若存在函数若存在函数g：AA，使得，使得 f g=A，说，说 f是右可逆函数，是右可逆函数，并称并称g是是f的的右逆函数右逆函数。 若存在函数若存在函数g：AA，使得，使得 g f =A，说，说 f是左可逆函数，是左可逆函数，并称并称 g是是f的的左逆函数左逆函数。 若若f既是左可逆函数又是右可逆函数，则说既是左可逆函数又是右可逆函数，则说 f是是可逆函

46、数可逆函数。 若若 f是右可逆函数当且仅当是右可逆函数当且仅当 f是满射。是满射。 若若 f是左可逆函数当且仅当是左可逆函数当且仅当 f是单射。是单射。 若若 f是可逆函数当且仅当是可逆函数当且仅当 f是双射。是双射。 恒等关系为幺元 单射函数有左逆元 满射函数有右逆元 双射函数有逆元例A=a,b,c, 右表给出了集合右表给出了集合A上的一个上的一个*运算表。运算表。考察如下考察如下: w b是幺元是幺元w a的右逆元是的右逆元是c， a没有左逆元。没有左逆元。w b的右逆元是的右逆元是b, b的左逆元是的左逆元是b。w c没有右逆元没有右逆元, c的左逆元是的左逆元是a.* a b ca a

47、 a bb a b cc a c c 定理4（A，*）是一个代数系统，）是一个代数系统，e A是幺元，若是幺元，若 * 适合结适合结合律，则对于任意的合律，则对于任意的a A，若，若a既有左逆元，又有右逆既有左逆元，又有右逆元，则元，则a的左逆元等于的左逆元等于a右逆元，即是右逆元，即是a的逆元。的逆元。a的逆元的逆元若存在，则唯一。若存在，则唯一。证明：证明： 设设a A，d，b分别是分别是a的左、右逆元。则有的左、右逆元。则有 d=d*e =d *(a*b)=(d*a)*b=e*b=b。同法可有的逆元存在一定唯一。同法可有的逆元存在一定唯一。逆元（A，*）是一个代数系统，对于）是一个代数系

48、统，对于A中的任意元素中的任意元素a，若，若a有逆元，则记有逆元，则记a-1为为a的逆元。的逆元。群定义定义2：设：设A是一个非空集，（是一个非空集，（A，*）是一个代数系统，）是一个代数系统， * 是是A上的一个二元运算，若（上的一个二元运算，若（A，*）满足以下）满足以下四条，说（四条，说（A，*）是一个）是一个群群。 *是是A上的闭运算；上的闭运算； *适合结合律；适合结合律； 存在存在e A，是幺元（又称单位元）；，是幺元（又称单位元）； 对于对于A中的任意元素中的任意元素a，存在，存在a-1 A，使得，使得a*a-1=a-1*a=e。Klein四元群设设G=e,a,b,c,*为为G上

49、的二元运算，上的二元运算，它由运算表给出。它由运算表给出。 不难证明不难证明:u e是是G中的幺元；中的幺元；u G中任何元素的逆元就是它自己中任何元素的逆元就是它自己;u G是一个群。是一个群。 u 在在a,b,c三个元素中，任何两个元素运算的结果都等于三个元素中，任何两个元素运算的结果都等于另一个元素。另一个元素。*eabceeabcaaecbbbceaccbae例（N，+）不是群，是含幺半群，幺元是）不是群，是含幺半群，幺元是0。因为。因为1 N，但不存在但不存在x N，使得，使得x+1=0。（Z，+）是群。）是群。（Q，+）是群。）是群。（R，+）是群。）是群。（C，+）是群。）是群。

50、（Z，）不是群，也是含幺半群，幺元是）不是群，也是含幺半群，幺元是1。因为。因为2 N，不存在不存在x Z，使得，使得x2=1。（Q，）也不是群，因为）也不是群，因为0 Q，但，但0没有逆元。没有逆元。（Q*，）是群，这里）是群，这里Q*=Q-0.（R*， ）也是群，这里）也是群，这里R*=R-0。例1 模模n的剩余类加群的剩余类加群(p142)设设A=0, 1, 2, 3, .,n-1, n是一个正整数。是一个正整数。在在A上定义运算：对于任意的上定义运算：对于任意的i，j A，这个群叫模这个群叫模n的剩余类加群，一般记的剩余类加群，一般记A=Zn。i j =i+j (i+j) n-1 i+