离散数学近世代数代数结构.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,离散数学近世代数代数结构,（优选）离散数学近世代数代数结构,由集合以及集合上的运算组成的数学结构,称为代数结构（也称为代数系统）,.,代数结构是抽象代数的一个主要内容,.,研究的中心问题：,集合上的抽象运算及运算的性质和结构。,什么是代数结构,研究意义：研究抽象代数结构的基本特征和基本结构，不仅能深化代数结构的理论研究，也能扩展其应用领域。,应用：,现代数学，如拓扑学、泛函分析，等,计算机科学：如,半群,自动机、形式语言,群,纠错码的设计,格和布尔代数,计算机硬件设计、通讯系统设计,其他,：代数方程求解、物理、化学,关于代数结构,主要内容,第12,章 代数结构的概念,第,13,章 半群与群,第,14,章 环和域,第,15,章 格与布尔代数,第,12,章 代数结构的概念,第,1,节 代数运算及其性质,第,2,节 代数结构的同态和同构,重点：,代数结构的判定与构造，代数结构关系：同态、同构,难点：,同态基本定理,代数运算、代数结构,S,是非空集合，映射,f:S,n,S,称为,S,上的,n,元运算。,写法,:f(a,b)=c,可改写为,:a f b=c,例如，在集合,R,上，对任意两个数所进行的普通加法和乘法，都是在集合,R,上的二元运算。,由集合,S,及,S,上的封闭运算,f,1,，,f,2,，,，,f,k,所组成的系统就称为一个代数系统，记作,或,（,S,，,f,1,，,f,2,，,f,k,）,.,x1-1 x x2-1 =x1-1(x x2-1)=x1-1 e=x1-1,由集合S及S上的封闭运算f1，f2，fk所组成的系统就称为一个代数系统，记作,或（S，f1，f2,，fk）.,例1Z;+,Z;-,N,-,T,F;,P(A);,作双射 f：A1A2，f(1)=b,f(2)=d,f(3)=c,f(4)=a,注意：单位元是跟运算有关系的，不同的运算可能单位元是不一样的。,设代数系统 和,综上，同构于,由集合以及集合上的运算组成的数学结构,(2)如果*是可结合的，则*也是可结合的；,写法:f(a,b)=c可改写为:a f b=c,设有代数系统(S，*)，对a,b,cS，如果有,设集合S=，定义在S上的一个二元运算如下表所示，试指出代数系统(S，)中各个元素的左、右逆元情况。,代数结构R+;*,R;+同构吗？,元素x为右单位元x对应的列与表头的列完全相同。,当幺元存在时，才考虑逆元。,例,1,Z;+,Z;-,N,-,T,F;,P(A);,是否代数系统？,需要满足的条件？,对于集合,A,，称运算,f:A,B,是封闭的,如果,B,A,。,一个代数系统需要满足以下三个条件：,有一个非空集合,S,；,有一些建立在集合,S,上的运算；,这些运算在,S,上是封闭的。,代数系统的基本概念,例,在整数集合,I,上定义,如下：,对任何,其中的,+,，分别是通常数的加法和乘法。,那么 是一个从,I,2,到,I,的函数，,易知 在集合,I,上是封闭的，,是,一个代数系统。,如果两个代数系统有相同个数的运算符，每个相对应的运算符的元数是相同的，则称这两个代数系统是同类型的。,定义：两个代数系统,(U,，,),与,(U,，*,),，如果满足下列条件：,U,U,；,若,a,U,，,b,U,，则,a*b=a,b,；则称,(U,，*,),是,(U,，,),的子系统或子代数。,代数系统的基本概念,设有代数系统,(S,，,*,),，对,a,，,b,，,c,S,，如果有,(a*b)*c=a*(b*c),则称此代数系统的运算满足结合律。,例设,A,是一个非空集合，是,A,上的二元运算，对于任意,a,，,b,A,，有,ab=b,，证明：是满足结合律的。,证：对于任意的,a,，,b,，,c,A,，,(a b)c=b c=c,而,a(bc)=a c=c,，,(ab)c=a(bc),是满足结合律的,.,代数运算及其性质,交换律,设有代数系统,(S,，*,),，如果对于,a,，,b,S,，有,a*b=b*a,，则称此代数系统的运算“*”满足交换律。,例：在整合集合,I,上定义运算,：,对任何,其中的,+,，分别是通常数的加法和乘法。,可以满足交换律吗？,分配律,(,左分配，右分配,),设有代数系统,(S,，,，*,),，对,a,b,cS,，如果有,a,(,b*c)=(a,b)*(a,c),，则称 “,”运算对“*”运算满足左分配律。,若“*”对“,”满足,a*(b,c)=(a*b),(a*c),，则称“*”对“,”满足左分配律,若有,(a*b),c=(a*c),(b*c),，则称“,”对“*”满足右分配律。,若,(a,b)*c=(a*c),(b*c),，则称“*”运算对“,”运算满足右分配律。,例：代数系统,(N,，,+,，,),。其中,+,，,分别代表通常数的加法和乘法。,是否满足交换律？,一个代数系统。,在所有n阶方阵集合M上的代数系统(M，)，零元是什么？,x1-1 x x2-1 =x1-1(x x2-1)=x1-1 e=x1-1,一个存在幺元 e 的代数系统(U，)，如果对 U 中的,aR，a 0，a 的逆元是什么?,对称:f是U到V的同构映射，则f-1是V到U的同构映射。,其中+，分别代表通常数的加法和乘法。,其中+，分别代表通常数的加法和乘法。,同理 x1-1 x x2-1=(x1-1 x)x2-1=e x2-1=x2-1,定理 一个代数系统，其零元若存在，则唯一。,解：作映射 f：IA，,集合上的抽象运算及运算的性质和结构。,(4)若e是*的单位元，则(e)是*的单位元;,称具有这些性质的代数是同一类(代数结构的类),若存在一个元素erS，使得对xS，有：x er=x，则称 er为对于运算“”的右幺元。,单位元,(,幺元,),一个代数系统,(S,，,*,),，若存在一个元素,e,U,，使得对,x,S,，有：,e,*,x=x,*,e=x,，则称,e,为对于运算“,*,”的单位元,也称幺元。,注意：单位元是跟运算有关系的，不同的运算可能单位元是不一样的。,左单位元或右单位元,(,左幺元或右幺元,),一个代数系统,(S,，,),，若存在一个元素,e,l,S,，使得对,x,S,，有：,e,l,x=x,，则称,e,l,为对于运算“,”的左幺元。,若存在一个元素,e,r,S,，使得对,x,S,，有：,x,e,r,=x,，则称,e,r,为对于运算“,”的右幺元。,例 设代数系统,(N,，*,),，的定义为：,对,那么，,(N,，*,),有没有单位元？左幺元？右幺元？,解：对任何,因此,1,是右幺元。,但,1,不是左幺元，因为,所以,(N,，*,),没有左幺元，当然也就没有幺元。,定理,代数系统,(U,),的单位元若存在，则唯一。,证：设,e,为运算“,”的幺元，另有一单位元,e,，,e,是幺元，对,x,U,，有,e,x=x,，取,x=e,，则,e,e,=e,又,e,是幺元，对,x,U,，有,x,e,=x,，取,x=e,，则,e,e,=e ,由 式可得：,e,=e,，即幺元唯一。,零元,代数系统,(S,，,),，如果存在一个元素,S,，使得对,x,S,有：,x=x,=,，则称,为对于运算“,”的零元。,若只满足,x=,，则,称为左零元。,若只满足,x,=,，则,称为右零元。,例,:,代数系统,(I,，,),的零元是什么？,在所有,n,阶方阵集合,M,上的代数系统,(M,，,),，零元是什么？,在,I,+,上定义一个二元运算取极小“,Min”,，,(I,+,，,Min),的零元是什么？,性质、定理,定理 一个代数系统，其零元若存在，则唯一。,定理 一个代数系统,(S,，,),，若集合,A,中元素的个数大于,1,，且该代数系统存在幺元,e,和零元,，则,e,。,证明：用反证法，设,=e,，则对于任意的,x,A,，必有,x=e,x=,x=e,，,即对于,A,中所有元素都是相同的，这与,A,中含有多个元素相矛盾。,逆元,一个存在幺元,e,的代数系统,(U,，,),，如果对,U,中的,元素,x,存在,x,-1,，使得,x,-1,x=x,x,-1,=e,，,则称,x,-1,为,x,的逆元。,若,x,x,-1,=e,，则称,x,-1,为,x,的右逆元。,若,x,-1,x=e,，则称,x,-1,为,x,的左逆元。,既是左逆元，又是右逆元，则称,x,-1,为,x,的一个逆元。,例子,对代数系统,(R,，*,),，*为二元运算，定义为通常数的乘法。,R,为实数集合。,a,R,，,a 0,，,a,的逆元是什么,?,对代数系统,(I,，*,),，*为二元运算，定义为通常数的乘法。,I,为整数集合。,哪些元素有逆元？,(R1,，*,),，,*为二元运算，定义为通常数的乘法。,R1,为除了,1,之外的实数集合。,哪些元素有逆元？,注意,因此，关于逆元，下述结论是正确的：,当幺元存在时，才考虑逆元。,逆元是针对具体元素而定的，有些元素可能有逆元，有些元素则可能没有逆元。如果,a,和,b,都有逆元且,a,b,，则,a,-1,和,b,-1,也不相同。,一个元素的逆元必须是代数系统内的元素。,设,e,幺元，只有当,a,b=e,和,b,a=e,同时成立时，,b,才能是,a,的逆元，如果只有一个成立，,b,也不是,a,的逆元。,定理：设代数系统,(U,，,),，运算“,”满足结合律，且,存在幺元,e,，那么对任意固定的,x,U,，若,x,有逆元，则,逆元是唯一的。,证明：,设,x,有两个逆元,x,1,-1,和,x,2,-1,，则,x,1,-1,x,x,2,-1,=x,1,-1,(x,x,2,-1,)=x,1,-1,e=x,1,-1,同理,x,1,-1,x,x,2,-1,=(x,1,-1,x),x,2,-1,=e,x,2,-1,=x,2,-1,所以：,x,1,-1,=x,2,-1,设*是定义在集合A上的一个二元运算，如果对于任意的x,A，都有x*x=x，则称*运算是等幂的。,例:S=1,2,4，在集合,p,(S)定义两个二元运算，分别表示集合的“并”运算和集合的“交”运算，是等幂的？,解：对于任意的A,p,(S)，有AA=A；AA=A 因此运算，都满足等幂律。,等幂律,设集合,S=,，,，,，,，,，定义在,S,上的一个二元运算如下表所示，试指出代数系统,(S,，,),中各个元素的左、右逆元情况。,解：是幺元，是 的左逆元，是 的右逆元；是、的左逆元，、是 右逆元；是 的左逆元,是 的右逆元；是 的左逆元,是 的右逆元。,例题,有限集合上运算的性质,*,是封闭的,表上每个元素都属于,S,。,*,满足交换律,表中元素关于主对角线对称。,元素,x,为左零元,x,对应的行中每个元素都是,x,。,元素,x,为右零元,x,对应的列中每个元素都是,x,。,元素,x,为零元,x,对应的行中每个元素都是,x,且,x,对应的列中每个元素都是,x,。,元素,x,为左单位元,x,对应的行与表头的行完全相同。,元素,x,为右单位元,x,对应的列与表头的列完全相同。,元素,x,为单位元,x,对应的行与表头的行完全相同且,x,对应的列与表头的列完全相同。,元素,x,为左逆元,x,对应的行中至少有一个单位元。,元素,x,为右逆元,x,对应的列中至少有一个单位元。,元素,x,与元素,y,互为逆元,x,所在行与,y,所在列交叉位置元素为单位元且,x,所在列与,y,所在行交叉位置元素为单位元,。,*,代数结构之间的关系,为什么需要研究代数结构之间的关系？,在研究代数结构的过程中，所关心的常常是代数结过中运算所满足的性质，不关心具体的运算，而对于遵循相同运算规律的系统只需要研究其中一个就可以了解其它的系统,.,考察下列代数,:,I,;Q,+;R,+,min;P(S),;P(S),此,5,个代数都有相同的构成成分,:,同样个数的运算,且对应运算元数相,(1,个二元运算,);,满足同样的,Y,运算律,(,交换律,结合律,);,存在单位元。,称具有这些性质的代数是同一类,(,代数结构的类,),设,(U,，,),和,(V,，*,),是两个同类型的代数系统,与*都是二元运算,如果存在映射,f,：,U,V,，使得对,x,1,，,x,2,U,有,f(x,1,x,2,)=f(x,1,)*f(x,2),，称,f,是一个从,(U,，,),到,(V,，*,),的同态映射，或说,(U,，,),与,(V,，*,),是同态的。,若,f,是满射，则称,f,是,(U,，,),到,(V,，*,),的满同态映射，,(U,，,),与,(V,，*,),是满同态。,若,f,是单射，则称,f,是,(U,，,),到,(V,，*,),的单同态映射，,(U,，,),与,(V,，*,),是单同态。,若,f,是双射，则称,f,是,(U,，,),到,(V,，*,),的同构映射，,(U,，,),与,(V,，*,),是同构的。,同态与同构,例,解：作映射,f,：,I,A,，,a,b,c,a,a,b,c,b,b,a,b,c,a,c,b,是偶数,是奇数,1.,设集合,A=a,，,b,，,c,，在,A,上定义运算。如下表，那么，,V,1,=(I,，,+),，,V,1,=(A,，,),，其中,I,是正整数集合，,+,运算是普通的加法。,V,1,和,V,1,是否同态？,2.,构造,与,之间的同态映射,.(,课堂练习,),例,解：,作双射,f,：,A,1,A,2,，,f,(1)=b,f,(2)=d,f,(3)=c,f,(4)=a,a,b,c,d,a,b,b,b,d,b,a,a,d,b,c,c,b,c,a,d,a,a,c,d,*,1,2,3,4,1,4,1,2,4,2,4,2,3,4,3,1,4,3,3,4,1,2,1,1,设代数系统,V,1,=(A,1,，*,),，,V,2,=(A,2,，,),，,其中,A,1,=1,，,2,，,3,，,4,，,A,2,=a,，,b,，,c,，,d,，,*和,的运算分别如下表，,V,1,和,V,2,是否同构？,例,代数结构,R,+,;*,R,;+,同构吗？,证明：,与,同构,下面证明二者之间存在双射关系且满足同态方程。,i),建立双射关系：,令,f:R,+,R,f(x),=,lnx,显然，,f,是单射,y,R,x=e,y,使,y=lne,y,=lnx=f(x),f,是满射,f,是从,R,+,到,R,的双射,ii),f,满足同态方程：,f(a,*,b)=ln,（,a*b,）,=lnalnb=f(a)+f(b),综上，,同构于,定理,设代数系统 和,其中*,*,都是二元运算，,是,V,1,到,V,2,的满同态映射，则,(1),如果*是可交换的，则*,也是可交换的；,(2),如果*是可结合的，则*,也是可结合的；,(3),如果*对,是可分配的,则*,对,也是可分配的；,(4),若,e,是*的单位元，则,(e),是*,的单位元,;,(5),若,是*的零元，则,(),是*,的零元,;,(6),若,a,关于运算*可逆，且逆元为,b,则,(a),关于运算*,也可逆，逆元为,(b),。,性质保持,1.,对于同构：,保持结合律、交换律、分配律；单位元、逆元、零元相应存在,.,2.,对于同态,单向保持性质,称具有这些性质的代数是同一类(代数结构的类),元素x为右零元x对应的列中每个元素都是x。,若“*”对“”满足a*(bc)=(a*b)(a*c)，则称“*”对“”满足左分配律,在所有n阶方阵集合M上的代数系统(M，)，零元是什么？,代数系统(S，)，如果存在一个元素S，使得对xS有：x=x=，则称为对于运算“”的零元。,单位元、逆元、零元相应存在.,设集合S=，定义在S上的一个二元运算如下表所示，试指出代数系统(S，)中各个元素的左、右逆元情况。,构造与之间的同态映射.,(1)如果*是可交换的，则*也是可交换的；,(5)若是*的零元，则()是*的零元;,离散数学近世代数代数结构,综上，同构于,定理 一个代数系统，其零元若存在，则唯一。,f 是满射,其中*,*,都是二元运算，是V1到V2的满同态映射，则,可以证明,代数系统间的同构关系是等价关系。,自反：构造映射,f,：,U,U,满足,f(x)=x,对称,:f,是,U,到,V,的同构映射，则,f,-1,是,V,到,U,的同构映射。,(U,，,),，,(V,，*,),，,(W,，,),，如果,f,是,U,到,V,同构映射，,g,是,V,到,W,的同构映射，则可证,g,o,f,是,U,到,W,的 同构映射。,代数系统间同构关系是等价关系,同态核,f,是一个从,(U,，,),到,(V,，*,),的同态映射,e,是,(V,，*,),的单位元。,定义集合,K(f)=x,x,S,且,f,(x),e,为同态核，记为,K(f),。,定理 设,f,为代数结构,到,的同态，如果,K(f),，那么,为,的子代数。,