离散数学第五章代数系统.ppt

《离散数学第五章代数系统.ppt》由会员分享，可在线阅读，更多相关《离散数学第五章代数系统.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学第五章代数系统现在学习的是第1页，共97页 代数学的历史悠久，早期代数学的研究对象是具体的，它以方程根的求解与分布为研究中心。但自从20世纪初以来，代数学的研究对象和研究方法都发生了重大的变化，形成了抽象代数学。这一变化可以追溯到19世纪30年代法国数学家伽罗瓦（Galois）提出的群的概念，证明了高于四次的一般代数方程的不可解性，并且建立了具体数字系统的代数方程可用根号求解的判别准则以及不能用根号求解的数字系统代数方程的实例。现在学习的是第2页，共97页 抽象代数学不同于以代数方程求根和根的分布情况为研究中心的古典代数学，它研究所谓的抽象代数系统。被处理的对象连同其上定义的运算（操作

2、）称为一个代数系统。由于其研究对象的抽象性，即它不以某一具体对象为研究对象，而是以一大类具有某种共同性质的对象为研究对象，因此其研究成果适用于这一类对象中的每个对象，从而达到事半功倍的效果。它在较高的观点上，把一些形式上很不相同的代数系统，撇开个性，抽出共性，用统一的方法描述、研究和推理，从而得到一些反映事物本质的结论，再把它们应用到那些系统中去，高度的抽象产生了广泛的应用。现在学习的是第3页，共97页 代数系统这个具有运算的集合，是抽象代数研究的主要对象，是离散数学的重要组成部分。它广泛应用于自动机、形式语言、逻辑电路设计、编码理论等研究中，成为计算机科学中重要的数学工具。由于抽象代数的内容

3、较多，作为离散数学的内容之一，本篇主要介绍代数系统的基本概念和几类典型的代数系统，包括半群、群、环、域、格和布尔代数。现在学习的是第4页，共97页第第5章章 代数系统代数系统现在学习的是第5页，共97页5.1 代数系统的基本概念 代数系统，也称为代数结构，是一个具有运算的集合。因此在介绍它之前，先引进一个集合上的运算的概念。例如，将实数集合R上的每一个数a0映射成它的倒数 ，或者将R上的每一个数y映射成 ，就可以将这些映射称为在集合R上的一元运算；而在集合R上，对任意两个数所进行的普通加法和乘法，都是集合R上的二元运算，也可以看作是将R上的每二个数映射成R中的一个数；至于对集合R上的任意三个数

4、x，y，z，ALGOL算法语言中的条件算术表达式if x=0 then y else z，就是集合R上的三元运算。a1 y现在学习的是第6页，共97页5.1 代数系统的基本概念 上述一些例子，有一个共同的特征，就是其运算结果都是在原来的集合R中，我们称那些具有这种特征的运算是封闭的，简称闭运算。相反地，没有这种特征的运算就不是封闭的。很容易举出不封闭运算的例子：一架自动售货机，能接受五角硬币和壹圆硬币，而所对应的商品是矿泉水（瓶）、可口可乐（瓶）和冰淇淋（杯）。当人们投入上述硬币的任何两枚时，自动售货机将按表5-1所示的供应相应的商品。现在学习的是第7页，共97页5.1 代数系统的基本概念*五

5、角硬币五角硬币 壹圆硬币壹圆硬币五角硬币五角硬币壹圆硬币壹圆硬币矿泉水矿泉水 可口可乐可口可乐可口可乐可口可乐 冰淇淋冰淇淋表 5-1表格左上角的记号*可以理解为一个二元运算的运算符。这个例子中的二元运算*就是集合五角硬币，壹圆硬币上的不封闭运算。定义定义5.1 设A，B是两个集合，若f是从An到B的函数，则称f为A上的一个n元运算。其中n是自然数，称为运算的元数或阶。如果BA，则称该n元运算是封闭的。现在学习的是第8页，共97页5.1 代数系统的基本概念 当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等。运算的例子很多。例如，在数理逻辑中，否定是命题集合上的一元运算，合取和析取是

6、命题集合上的二元运算；在集合论中，集合的补是集合上的一元运算，并与交是集合上的二元运算；在实数算术中，加、减、乘、除运算都是二元运算。有了集合上运算的概念后，便可以定义代数系统了。现在学习的是第9页，共97页5.1 代数系统的基本概念 定义定义5.2 设A是个非空集合且fi是A上的ni元运算，其中i=1，2，m。由A及f1，f2，fm组成的结构，称为代数结构或代数系统，记作 。此外，集合A的基数即|A|，定义为代数系统的基数。如果A是有限集合，则说代数系统是有限代数系统；否则便说是无穷代数系统。有时，要考察两个或多个代数系统，这里就有是否为同类型之说，请看下面定义：现在学习的是第10页，共97

7、页5.1 代数系统的基本概念 定义定义5.3 设两个代数系统和，如果fi和gi(1im)具有相同的元数，则称这两个代数系统是同类型的。可见，判定两个代数系统是否同类型，主要是对其运算进行考察。下面举例说明上述各个概念。现在学习的是第11页，共97页5.1 代数系统的基本概念 例例5.1 设S是非空集合，P(S)是它的幂集。对任意集合A，BP(S)上的运算和定义如下:AB=(A-B)(B-A)AB=AB 则是一个代数系统，并且是一个封闭的代数系统。现在学习的是第12页，共97页5.1 代数系统的基本概念 例例5.2 设是由有限个字母组成的集合，称为字母表。由中的字母组成的有序集合，称为上的串。串

8、中的字母个数m称为该串的长度。m=0时，叫做空串，用表示之。用*表示上的串集合。在*上定义一个并置或者连接运算，用表示之。如、*，则=。那么，是一代数系统。如果令+=*-，则也是一个代数系统。现在学习的是第13页，共97页5.1 代数系统的基本概念 例例5.3 设有一台字长为8位的计算机，它以定点加、减、乘、除以及逻辑加和逻辑乘为运算指令，并分别用01，02，06表示之。则在计算机中由28个不同数字所组成集合S同该机中运算指令构成一代数系统。现在学习的是第14页，共97页5.1 代数系统的基本概念 例例5.4 设Z是整数集合，+是普通的加法运算，则是一个代数系统。显然，在这个代数系统中，关于“

9、+”运算，具有以下三个运算规律，即对于任意的x，y，zZ，有（1）x+yZ，（封闭性）（2）x+y=y+x（交换律）（3）(x+y)+z=x+(y+z)（结合律）容易找到与具有相同运算规律的一些代数系统，如表5-2所示。现在学习的是第15页，共97页5.1 代数系统的基本概念集合集合运算运算封闭性封闭性交换律交换律结合律结合律Z为整数集合为整数集合为普通乘法为普通乘法xyZxy=yx(xy)z=x(yz)R为实数集合为实数集合+为普通加法为普通加法x+yRx+y=y+x(x+y)+z=x+(y+z)P(S)是是S的幂集的幂集是集合的是集合的“并并”ABP(S)AB=BA(AB)C=A(BC)P

10、(S)是是S的幂集的幂集是集合的是集合的“交交”ABP(S)AB=BA(AB)C=A(BC)表 5-2在结束本节时，声明记号即为一代数系统，除特别指明外，运算符f1，f2，fm均为二元运算。根据需要对A及f1，f2，fm可置不同的集合和运算符。现在学习的是第16页，共97页5.2 运算及其性质 在前面讨论几个具体的代数系统时，已经涉及到我们所熟知的运算的某些性质。下面，着重讨论一般二元运算的一些性质。对于代数系统的性质的考察方法不是一个一个研究各个结构，而是列举一组性质，并且对于具有这些性质的任何代数系统推导可能的结论。把那些被选出的性质看成是公理并且由这些公理推导出的任何有效结论，对于满足这

11、些公理的任何代数系统也都必定成立。现在学习的是第17页，共97页5.2 运算及其性质 因此，为了做出这样的讨论，将不考虑任何特定的集合，也不给所涉及到的运算赋予任何特定的含义。这种系统的集合及集合上的诸运算仅仅看成是一些符号，或更确切地说，它们都是些抽象对象。因此，与此相应的代数系统，通常称为抽象代数。对于那些特定的代数系统只能是具有这些基本性质中的某些性质。现在学习的是第18页，共97页5.2 运算及其性质 性质性质1：封闭性：封闭性 设*是定义在集合A上的二元运算，如果对于任意的x，yA，都有x*yA，即(x)(y)(x，yAx*yA)，则称二元运算*在A上是封闭的。例例5.5 设A=x|

12、x=2n,nN，问乘法运算是否封闭？加法运算是否封闭？解：对于任意的2r，2sA，r，sN，因为2r2s=2r+sA所以乘法运算是封闭的。而对于加法运算是不封闭的，因为至少有2+22=6A。现在学习的是第19页，共97页5.2 运算及其性质 性质性质2：交换律：交换律 设*是定义在集合A上的二元运算，如果对于任意的x，yA，都有x*y=y*x，即(x)(y)(x，yAx*y=y*x)，则称二元运算*满足交换律，或称*是可交换的。例例5.6 给定，其中Q为有理数集合，并且对任意a，bQ有ab=a+b-ab，问运算 是否可交换?解：因为a b=a+b-ab=b+a-ba=ba所以运算是可交换的。现

13、在学习的是第20页，共97页5.2 运算及其性质 性质性质3：结合律：结合律 设*是定义在集合A上的二元运算，如果对于任意的x，y，zA，都有(x*y)*z=x*(y*z)，即(x)(y)(z)(x，y，zA(x*y)*z=x*(y*z)，则称二元运算*满足结合律，或称*是可结合的。例例5.7 给定，对任意a，bA有ab=b。证明运算“”是可结合的。证明：因为对于任意的a，b，c有(a b)c=bc=c，而a(bc)=ac=c所以(ab)c=a(bc)现在学习的是第21页，共97页5.2 运算及其性质 可见，如果一个代数系统中的运算是可结合和可交换的，那么，在计算a1 a2 am时可按任意次序

14、计算其值。特别当a1=a2=am=a时，则a1a2 am=am。称am为a的m次幂，m称a的指数。下面给出am的归纳定义：设有且aA。对于mN+，其中N+表示正整数集合，可有 (1)a1=a (2)am+1=am a现在学习的是第22页，共97页5.2 运算及其性质 由此利用归纳法不难证明指数定律：(1)am an=am+n (2)(am)n=amn这里，m，n N+。类似地可定义某代数系统中的负幂和给出负指数定律。现在学习的是第23页，共97页5.2 运算及其性质 性质性质4：分配律：分配律 设*，是定义在集合A上的两个二元运算，如果对于任意的x，y，zA，都有x*(yz)=(x*y)(x*

15、z)和(yz)*x=(y*x)(z*x)即(x)(y)(z)(x，y，zAx*(yz)=(x*y)(x*z)(y z)*x=(y*x)(z*x)，则称运算*对于满足分配律，或者*对于 是可分配的。一个代数系统若具有两个运算时，则分配律可建立这两个运算之间的某种联系。现在学习的是第24页，共97页5.2 运算及其性质 例例5.8 给定，其中B=0，1。表5-3分别定义了运算*和，问运算*对于是可分配的吗?对于*呢?解：容易验证运算对于运算*是可分配的。但是运算*对于运算是不可分配的，因为 1*(0 1)=1*0=1，而(1*0)(1*1)=1 0=0*0 10 100 100 011 010 1

16、表5-3现在学习的是第25页，共97页5.2 运算及其性质 形如表5-3的表常常称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成。对于集合的基数很小，特别是2或3时，代数系统中运算常常用这种表给出。优点是简明直观，一目了然。性质性质5：吸收律：吸收律 设*，是定义在集合A上的两个可交换的二元运算，如果对于任意的x，yA，都有x*(x y)=x 和x(x*y)=x 即(x)(y)(x，yAx*(xy)=xx(x*y)=x),则称运算*和运算 满足吸收律，或称*对于以及对于*是可吸收的。现在学习的是第26页，共97页5.2 运算及其性质 例例5.9 给定，其中N是自然数集

17、合，*和定义如下：对任意a，bN有a*b=max(a，b)，ab=min(a，b)，试证，*和互为吸收的。证明：对于任意a，bNa*(a b)=max(a，min(a，b)=aa(a*b)=min(a，max(a，b)=a因此，*和满足吸收律。现在学习的是第27页，共97页5.2 运算及其性质 性质性质6：等幂律：等幂律 设*是定义在集合A上的一个二元运算，如果对于任意的xA，都有x*x=x，即(x)(xAxx=x)，则称运算*是等幂的，或*满足等幂律，并称x是关于*的等幂元。例例5.10 给定，其中P(S)是集合S的幂集，和分别为集合的并和交运算。证明：和是等幂的。证明：对于任意的AP(S)

18、，有AA=A和AA=A，因此运算和都满足等幂律。关于等幂律，不难证明下面的定理：现在学习的是第28页，共97页5.2 运算及其性质 定理定理5.1 若x是中关于的等幂元，对于任意正整数n，则xn=x。证明留做练习。性质性质7：幺元：幺元 设*是定义在集合A上的一个二元运算，如果存在一个元素elA，对于任意的xA，都有el*x=x，即(x)(xAel*x=x)，则称el为A中关于运算*的左幺元；如果存在一个元素erA，对于任意的xA，都有x*er=x，即(x)(xAx*er=x)，则称er为A中关于运算*的右幺元；如果A中一个元素e，它既是*的左幺元又是*的右幺元，则称e为A中关于*的幺元，即(

19、x)(xAe*x=x*e=x)。现在学习的是第29页，共97页5.2 运算及其性质 例例5.11 给定，表5-4，表5-5和表5-6分别给出*的不同定义的运算表，试指出左幺元、右幺元及幺元。解：在运算表5-4中，既是左幺元，又是右幺元。即为幺元。运算表5-5中，不存在左幺元，和都是右幺元。运算表5-6中，是左幺元，不存在右幺元。表表5-4表表5-5表表5-6*现在学习的是第30页，共97页5.2 运算及其性质 定理定理5.2 给定且el和er分别关于的左、右幺元，则el=er=e且幺元e是惟一的。证明：因为el和er分别是S中关于的左、右幺元，所以el=el er=er=e 设另有一个幺元e1

20、S，则 e1=e1e=e现在学习的是第31页，共97页5.2 运算及其性质 性质性质8：零元：零元 设*是定义在集合A上的一个二元运算，如果存在一个元素lA，对于任意的xA，都有l*x=l，即(x)(xAl*x=l)，则称l为A中关于运算*的左零元；如果存在一个元素rA，对于任意的xA，都有x*r=r，即(x)(xAx*r=r)，则称r为A中关于运算*的右零元；如果A中一个元素，它既是*的左零元又是*的右零元，则称为A中关于*的零元，即(x)(xA*x=x*=)。现在学习的是第32页，共97页5.2 运算及其性质 例例5.12 在例5.11中，*如表5-4所定义，是*的零元；*如表5-5所定义

21、，和都是*的左零元；*如表5-6所定义，是*的右零元。定理定理5.3 给定且l和r分别为关于的左零元和右零元，则l=r=且零元是惟一的。本定理的证明可仿照定理5.2，请读者自己完成。现在学习的是第33页，共97页5.2 运算及其性质 定理定理5.4 给定且|S|1。如果，eS，其中和e分别为关于的零元和幺元，则 e。证明：用反证法。设=e，那么对于任意的xS，必有x=ex=x=e于是，S中的所有元素都是相同的，这与S中含有多个元素相矛盾。现在学习的是第34页，共97页5.2 运算及其性质 性质性质9：逆元：逆元 给定代数系统，是定义在A上的一个二元运算，且e是A中关于运算的幺元。如果对于A中的

22、一个元素x存在A中的某个元素y，使得y x=e，那么称y为的x的左逆元，即(y)(yAy x=e)；如果xy=e成立，那么称y为的x的右逆元，即(y)(yAxy=e)；如果一个元素y，它既是x的左逆元，又是x的右逆元，那么就称y是x的一个逆元。显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的逆元表为x-1。现在学习的是第35页，共97页5.2 运算及其性质 一般地说，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是惟一的。例例5.13 给定，其中S=，且*的定义如表5-7所示。试指出该代数系统中

23、各元素的左、右逆元情况。解：是幺元；的左逆元和右逆元都是；即和互为逆元；的左逆元是而右逆元是；有两个左逆元和；的右逆元是，但没有左逆元。现在学习的是第36页，共97页5.2 运算及其性质*表5-7 定理定理5.5 给定及幺元eS。如果是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1。证明：xl-1=xl-1e=xl-1(x xr-1)=(xl-1x)xr-1=exr-1=xr-1现在学习的是第37页，共97页5.2 运算及其性质 定理定理5.6 给定及幺元eS。如果是可结合的并且x的逆元x-1存在，则x-1是惟一的。证明：假设x有两个逆元x-1和x1-1，那么

24、 x-1=x-1 e=x-1(xx1-1)=(x-1x)x1-1=ex1-1=x1-1因此，x的逆元是惟一的。现在学习的是第38页，共97页5.2 运算及其性质 性质性质10：可约律：可约律 给定代数系统，是定义在A上的一个可交换的二元运算，且是A中关于运算的零元。如果对于A中的任意元素x 和任意的y，z，若x y=xz，都有y=z，即(x)(y)(z)(x，y，zSx xy=xz)y=z)，则称x是关于的可约元，并且称满足可约律或是可约的。例例5.14 给定，其Z是整数集合，是一般乘法运算。显然，每个非零整数都是可约元，而且运算满足可约律。现在学习的是第39页，共97页5.2 运算及其性质

25、定理定理5.7 给定且是可结合的，如果x是关于可逆的且x ，则x也是关于的可约元。证明：对于S中的任意元素y，z，若x y=xz，设x的逆元为x-1，则x-1(xy)=x-1(xz)(x-1x)y=(x-1 x)z ey=ez y=z因此，x是关于的可约元。现在学习的是第40页，共97页5.2 运算及其性质 例例5.15 对于代数系统，其中Nk=0，1，2，k-1，+k是定义在Nk上的模k加法运算，定义如下：对于任意x，yNk 试问是否每个元素都有逆元。解：可以验证，+k是一个可结合的二元运算，Nk中关于运算+k的幺元是0，Nk中的每一个元素都有惟一的逆元，即0的逆元是0，每个非零元素x的逆元

26、是k-x。kyxkyxkyxyxyxk若若现在学习的是第41页，共97页5.2 运算及其性质 定义定义5.4 设是一代数系统，且非空集TS在运算f1，f2，fm作用下是封闭的，且T含有与S中相同的特异元（幺元或零元），则称为代数系统的子代数，记为 。最后，作一补充说明，用运算表定义一代数系统的运算，从表上能很好地反映出关于运算的各种性质。为确定起见，假定及x，y，eS。现在学习的是第42页，共97页5.2 运算及其性质(1)运算*具有封闭性，当且仅当运算表中的每个元素都属于S。(2)运算*满足交换律，当且仅当运算表关于主对角线是对称的。(3)运算*满足等幂律，当且仅当运算表的主对角线上的每个元

27、素与所在行或列表头元素相同。(4)元素x是关于*的左零元，当且仅当x所对应的行中的每个元素都与x相同；元素y是关于*的右零元，当且仅当y所对应的列中的每个元素都与y相同；元素是关于*的零元，当且仅当所对应的行和列中的每个元素都与相同。现在学习的是第43页，共97页5.2 运算及其性质(5)元素x为关于*的左幺元，当且仅当x所对应的行中元素依次与行表头元素相同；元素y为关于*的右幺元，当且仅当y所对应的列中元素依次与列表头元素相同；元素e是关于*的幺元，当且仅当e所对应的行和列中元素分别依次地与行表头元素和列表头元素相同。(6)x为关于*的左逆元，当且仅当位于x所在行的元素中至少存在一个幺元，y

28、为关于*的右逆元，当且仅当位于y所在列的元素中至少存在一个幺元；x与y互为逆元，当且仅当位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是幺元。现在学习的是第44页，共97页5.3 同态与同构 本节我们讨论两个代数系统之间的联系。着重研究两个代数系统之间的同态关系和同构关系，在以后各节中，它们会经常被使用。定义定义5.5 设与是同类型的两个代数系统，若(f)(f YX(x1)(x2)(x1，x2Xf(x1x2)=f(x1)*f(x2)，则称同态于或为的同态象，记为 ，同时，称f为从到的同态映射。现在学习的是第45页，共97页5.3 同态与同构 两个代数系统在同态意义下的相互联系可以由

29、图5.1来描述。abca cf(c)f(a)*f(c)=f(b)*f(c)ABb cf(a)=f(b)图5.1现在学习的是第46页，共97页5.3 同态与同构 例例5.16 考察代数系统，这里Z是整数集合，*是普通乘法运算。如果我们对计算结果只感兴趣于正、负、零之间的特征区别，那么，代数系统中运算结果的特征就可以用另一个代数系统的运算结果来描述，其中B=正，负，零，是定义在B上的二元运算，如表5-8所示。作映射f：ZB如下：正若n0 f(n)=负若n0 零若n=0现在学习的是第47页，共97页5.3 同态与同构表 5-8 很明显，对于任意的a，bZ，有f(a*b)=f(a)f(b)因此，映射f

30、是到的一个同态映射。例5.16告诉我们，在中研究运算结果的正、负、零的特征就等于在中研究这些运算特征，可以说，代数系统描述了中运算结果的这些基本特征。而这正是研究两个代数系统之间是否存在同态的重要意义。正正 负负 零零正正负负零零正正 负负 零零负负 正正 零零零零 零零 零零现在学习的是第48页，共97页5.3 同态与同构 应该指出，两个代数系统之间的同态映射f不必是惟一的，即一个代数系统到另一个代数系统可能存在多个同态映射。例例5.17 给定和，其中R是实数集合，+和分别是加法和乘法运算，试证 。证明：构造函数fRR如下：f(x)=ax，其中a0，xR则f为所求的同态映射，这是因为对任意y

31、，zR有f(y+z)=ay+z=ayaz=f(y)f(z)因此，现在学习的是第49页，共97页5.3 同态与同构 两个同类型的代数系统间的同态定义不仅适用于具有一个二元运算的代数系统，也可以推广到具有多个二元运算的任何两个同类型代数系统。例如，对于具有两个二元运算的两个同类型代数系统和同态当且仅当(f)(fYX(x1)(x2)(x1，x2X(f(x1x2)=f(x1)f(x2)f(x1*x2)=f(x1)f(x2)，并且称f为从到的同态映射。现在学习的是第50页，共97页5.3 同态与同构 例例5.18 给定，其中Z为整数集合，+和是一般的加法和乘法运算。又有，这里Zm=0，1，2，m-1，+

32、m和m分别是模m加法和模m乘法，它们详细定义如下：a+m b=(a+b)(mod m)a m b=(ab)(mod m)其中a，b Zm现在定义函数fZmZ:f(i)=(i)(mod m)，其中iZ Z 试证 。现在学习的是第51页，共97页5.3 同态与同构 证明：因为对任意i1，i2Z，有 f(i1+i2)=(i1+i2)(mod m)=(i1)(mod m)+m(i2)(mod m)=f(i1)+m f(i2)f(i1 i2)=(i1 i2)(mod m)=(i1)(mod m)m(i2)(mod m)=f(i1)m f(i2)故f为所求的同态映射，于是 。现在学习的是第52页，共97页

33、5.3 同态与同构 定理定理5.8 如果 且f为其同态映射，则。证明：因为fYX，R(f)Y，故若y1，y2R(f)，则应有x1，x2X，使得f(x1)=y1和f(x2)=y2，而且存在x3X，使x1x2=x3，所以y1*y2=f(x1)*f(x2)=f(x1x2)=f(x3)R(f)可见，集合R(f)在*作用下是封闭的，因此则。由于函数fYX的不同性质，将给出不同种类的同态定义。现在学习的是第53页，共97页5.3 同态与同构 定义定义5.6 设 且f为其同态映射。(1)如果f为满射，则称f是从到的满同态映射。(2)如果f为单射(或一对一映射)，则称f为从到的单一同态映射。(3)如果f为双射

34、(或一一对应)，则称f为从到的同构映射。记为。显然，若f是从到的同构映射，则f为从到的满同态映射及单一同态映射，反之亦然。现在学习的是第54页，共97页5.3 同态与同构 例例5.19 给定，其中Z为整数集合，+为一般加法。作函数fZ Z:f(x)=kx 其中x，kZ则当k 0时，f为到的单一同态映射。当k=-1或k=1时，f为从到的同构映射。可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说，它能够保持运算的更多性质。为此，给出如下定理：现在学习的是第55页，共97页5.3 同态与同构 定理定理5.9 给定且f为其满同态映射，则(1)如果和*满足结合律，则和也满足结合律。(2

35、)如果和*满足交换律，则和也满足交换律。(3)如果 对于*或*对于满足分配律，则对于或对于也相应满足分配律。(4)如果对于*或*对于满足吸收律，则对于或对于也满足吸收律。(5)如果和*满足等幂律，则和也满足等幂律。现在学习的是第56页，共97页5.3 同态与同构(6)如果e1和e2分别是关于和*的幺元，则f(e1)和f(e2)分别为关于和的幺元。(7)如果1和2分别是关于和*的零元，则f(1)和f(2)分别为关于和的零元。(8)如果对每个xX均存在关于的逆元x-1，则对每个f(x)Y也均存在关于的逆元f(x-1)；如果对每个zX均存在关于*的逆元z-1，则对每个f(z)Y也均存在关于的逆元f(

36、z-1)。现在学习的是第57页，共97页5.3 同态与同构 证明：(1)因为f是从到的满同态映射，故对任意y1，y2，y3Y，必存在x1，x2，x3 X，使得f(x1)=y1，f(x2)=y2，f(x3)=y3，而且有f(x1(x2x3)=f(x1)f(x2 x3)=f(x1)(f(x2)f(x3)=y1(y2y3)f(x1x2)x3)=f(x1x2)f(x3)=(f(x1)f(x2)f(x3)=(y1y2)y3现在学习的是第58页，共97页5.3 同态与同构因为x1(x2x3)=(x1x2)x3于是f(x1(x2x3)=f(x1x2)x3)因此y1(y2y3)=(y1y2)y3 可见，由于满

37、足结合律证明也满足结合律；同理由*满足结合律，可证也满足结合律。现在学习的是第59页，共97页5.3 同态与同构(2)因为f是从到的满同态映射，故对任意y1，y2Y，必存在x1，x2X，使得f(x1)=y1，f(x2)=y2，而且有f(x1x2)=f(x1)f(x2)=y1y2f(x2x1)=f(x2)f(x1)=y2y1又因为满足交换律，故x1x2=x2x1于是f(x1x2)=f(x2x1)，因此y1y2=y2y1 可见，满足交换律；同理由*满足交换律，可证也满足交换律。现在学习的是第60页，共97页5.3 同态与同构(3)因为f是从到的满同态映射，故对任意y1，y2，y3Y，必存在x1，x

38、2，x3 X，使得f(x1)=y1，f(x2)=y2，f(x3)=y3，而且有f(x1(x2*x3)=f(x1)f(x2*x3)=f(x1)(f(x2)f(x3)=y1(y2y3)f(x1x2)*(x1x3)=f(x1x2)f(x1x3)=(f(x1)f(x2)(f(x1)f(x3)=(y1y2)(y1y3)现在学习的是第61页，共97页5.3 同态与同构又因为 对于*满足分配律，故x1(x2*x3)=(x1x2)*(x1x3)于是f(x1(x2*x3)=f(x1x2)*(x1x3)因此y1(y2y3)=(y1y2)(y1y3)同理可得(y2y3)y1=(y2y1)(y3y1)所以，对于满足分

39、配律，类似可以证明对于也满足分配律。现在学习的是第62页，共97页5.3 同态与同构(4)因为f是从到的满同态映射，故对任意y1，y2Y，必存在x1，x2X，使得f(x1)=y1，f(x2)=y2，而且有f(x1(x1*x2)=f(x1)f(x1*x2)=f(x1)(f(x1)f(x2)=y1(y1y2)f(x1*x2)x1)=f(x1*x2)f(x1)=(f(x1)f(x2)f(x1)=(y1y2)y1现在学习的是第63页，共97页5.3 同态与同构又因为对于*满足吸收律，故x1(x1*x2)=x1(x1*x2)x1=x1于是f(x1(x1*x2)=f(x1)f(x1*x2)x1)=f(x1

40、)因此y1(y1y2)=y1(y1y2)y1=y1 可见，对于满足吸收律；同理可证对于也满足吸收律。现在学习的是第64页，共97页5.3 同态与同构(5)因为f是从到的满同态映射，故对任意yY，必存在xX，使得f(x)=y，而且有f(x x)=f(x)f(x)=yy又因为满足等幂律，故xx=x于是f(xx)=f(x)因此yy=y 可见，满足等幂律；同理可证也满足等幂律。不难证明，若x分别是和*的等幂元，则f(x)是分别关于和的等幂元。现在学习的是第65页，共97页5.3 同态与同构(6)因为f是从到的满同态映射，故对任意yY，必存在xX，使得f(x)=y，又因为e1是关于的幺元，所以有f(x)

41、=f(xe1)=f(x)f(e1)=yf(e1)f(x)=f(e1x)=f(e1)f(x)=f(e1)y即f(e1)y=y f(e1)=y因此f(e1)是关于的幺元；同理可证f(e2)是关于的幺元。现在学习的是第66页，共97页5.3 同态与同构(7)因为f是从到的满同态映射，故对任意yY，必存在xX，使得f(x)=y，又因为1是关于的零元，所以有f(1)=f(x1)=f(x)f(1)=yf(1)f(1)=f(1x)=f(1)f(x)=f(1)y即f(1)y=yf(1)=f(1)因此f(1)是关于的零元；同理可证f(2)是关于的零元。现在学习的是第67页，共97页5.3 同态与同构(8)因为f

42、是从到的满同态映射，故对任意yY，必存在xX，使得f(x)=y，并且有f(e1)=f(x-1x)=f(x-1)f(x)=f(x-1)yf(e1)=f(xx-1)=f(x)f(x-1)=yf(x-1)即f(x-1)y=yf(x-1)=f(e1)由(6)可知，f(e1)是关于的幺元，若取f(x-1)=y-1，便有f(x-1)f(x)=f(x)f(x-1)即y-1y=yy-1=f(e1)现在学习的是第68页，共97页5.3 同态与同构 因此f(x-1)是f(x)关于的逆元；同理可证，若对每个zX均存在关于*的逆元z-1，则对每个f(z)Y也均存在关于的逆元f(z-1)。现在学习的是第69页，共97页

43、5.3 同态与同构 定理5.9 说明，对于满同态映射，代数系统的许多性质都能保持，如结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向的，即如果满同态于，则所具有的性质，均具有。但反之不然，即所具有的某些性质，不一定具有。那么，在什么样的条件下，所具有的性质也完全具有呢？只有当两个代数系统之间的映射是双射，即两个代数系统是同构的情况下才完全具有这些性质。现在学习的是第70页，共97页5.3 同态与同构 同构映射是双射，而同态映射不一定要求是双射。因此，同构不仅仅象满同态那样保持运算的单向，而保持运算的双向。两个同构的代数，表面上似乎很不相同，但在结构上实际没有差别，只不过

44、是集合中的元素名称和运算的标识不同而已。这样，当探索新的代数系统的性质时，若发现或可证明该结构同构于另外一个性质已知的代数系统，便能直接知道新的代数系统的各种性质了。对于同构的两个代数系统来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是相同的。因此，可以根据这些特征来识别同构的代数系统。现在学习的是第71页，共97页5.3 同态与同构 例例5.20 令与是同类型的，其中F=f 0，f 1，f 2，f 3，“”定义如表5-9所示；Z4=0，1，2，3，+4定义如表5-10，试证明。表5-9 表5-10 f 0 f 1 f 2 f 3+40 1 2 3f 0f 1f 2f 3f 0

45、f 1 f 2 f 3f 1 f 2 f 3 f 0f 2 f 3 f 0 f 1f 3 f 0 f 1 f 201230 1 2 31 2 3 02 3 0 13 0 1 2现在学习的是第72页，共97页5.3 同态与同构 解：令 且对任意j=0，1，2，3有则显然 为双射。根据表5-9和表5-10，对于所有i，j=0，1，2，3有 故 为从到的同态映射。因此，。+)(+)()(44jifffjiji现在学习的是第73页，共97页5.3 同态与同构 例例5.21 给定，其中S=，A，B，C，和是一般的集合运算；又有，这里T=1，2，5，10，且对于a，bT有ab=lcma，b，ab=gcda

46、，b，表5-11至表5-14给出四个运算表。试说明。解：令fTS:f()=1，f(A)=2，f(B)=5，f(C)=10，可以证明f是从到的同构映射，故：现在学习的是第74页，共97页5.3 同态与同构表5-11 表5-12表5-13 表5-14 A B C A B CABC A B CA A C CB C B CC C C CABC A A B B A B C1 2 5 101 2 5 10125101 2 5 102 2 10 105 10 5 1010 10 10 10125101 1 1 11 2 1 21 1 5 51 2 5 10现在学习的是第75页，共97页5.3 同态与同构 同

47、构是一个关系，而且可以证明它是等价关系。定理定理5.10 代数系统间的同构关系是等价关系。证明：代数系统可以通过恒等映射与它自身同构，即自反性成立。若且对应的同构映射为f，因为f的逆是由到的同构映射，即，即对称性成立。若f是由到的同构映射，g是从到的同构映射，那么g和f的复合gf就是从到的同构映射，即传递性成立。因此，代数系统间的同构关系是等价关系。现在学习的是第76页，共97页5.3 同态与同构 由于同构关系是等价关系，故令所有的代数系统构成一个集合S，于是可按同构关系将其分类，得到商集S/。因为同构的代数系统具有相同的性质，故实际上代数系统所需要研究的总体并不是S而是S/。在同态与同构中有

48、一个特例，即具有相同集合的任两个代数系统的同态与同构，这便是自同态与自同构。现在学习的是第77页，共97页5.3 同态与同构 定义定义5.7 给定及fSS，若f为从到的同态映射，则称f是自同态映射；若f为从到的同构映射，则称f为自同构映射。例例5.22 在例5.19中，当k 0时，f=kx是从到的自同态映射；当k=1或k=-1时，f=kx是从到的自同构映射。现在学习的是第78页，共97页5.4 同余关系 本节我们讨论同态与同余关系的对应，为此先给出同余关系的概念。定义定义5.8 给定代数系统，且E为S中的等价关系。定义E有代换性质(x1，x2，y1，y2Sx1Ex2y1Ey2(x1y1)E(x

49、2y2)。若E有代换性质，则称E为中的同余关系。并且，称同余关系E的等价类为同余类。现在学习的是第79页，共97页5.4 同余关系 由定义可知，同余关系是代数系统的集合中的等价关系，并且在运算的作用下，能够保持关系的等价类。即在x1y1中，如果用集合S中的与x1等价的任何其它元素x2代换x1，并且用与y1等价的任何其它元素y2代换y1，则所求的结果x2y2与x1y1位于同一等价类之中。亦即若x1E=x2E并且y1E=y2E，则x1y1E=x2y2E。此外，同余关系与运算密切相关。如果一个代数系统中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质。如果有，则说该代数系统存在同余关系

50、；否则，同余关系不存在。现在学习的是第80页，共97页5.4 同余关系 例例5.23 给定，其中Z是整数集合，+和是一般加、乘法。假设Z中的关系R定义如下：i1Ri2：=|i1|=|i2|其中i1、i2Z试问，R为该结构的同余关系吗？解：显然，R为Z中的等价关系，接下来考察R对于+运算的代换性质：若取i1，-i1，i2Z，则有|i1|=|-i1|和|i2|=|i2|，于是，下式(i1R(-i1)(i2Ri2)(i1+i2)R(-i1+i2)不真。这是因为前件为真，后件为假。故R对于+运算不具有代换性质。现在学习的是第81页，共97页5.4 同余关系 至此可以说，R不是该结构上的同余关系。但为了