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

离散数学DiscreteMathematics,SchoolofMathematicsandComputingScience,第四篇代数系统,由集合以及集合上的运算组成的数学结构称为代数结构（也称为代数系统）.代数结构是抽象代数的一个主要内容.研究的中心问题：集合上的抽象运算及运算的性质和结构。,什么是代数结构,研究意义：研究抽象代数结构的基本特征和基本结构，不仅能深化代数结构的理论研究，也能扩展其应用领域。应用：现代数学，如拓扑学、泛函分析，等计算机科学：如半群自动机、形式语言群纠错码的设计格和布尔代数计算机硬件设计、通讯系统设计其他：代数方程求解、物理、化学,关于代数结构,主要内容,第12章代数结构的概念第13章半群与群第14章环和域第15章格与布尔代数,第12章代数结构的概念第1节代数运算及其性质第2节代数结构的同态和同构重点：代数结构的判定与构造，代数结构关系：同态、同构难点：同态基本定理,代数运算、代数结构,S是非空集合，映射f:SnS称为S上的n元运算。写法:f(a,b)=c可改写为:afb=c例如，在集合R上，对任意两个数所进行的普通加法和乘法，都是在集合R上的二元运算。,由集合S及S上的封闭运算f1，f2，fk所组成的系统就称为一个代数系统，记作,或（S，f1，f2,，fk）.,例1Z;+,Z;-,N,-,T,F;,P(A);,是否代数系统？需要满足的条件？,对于集合A，称运算f:AB是封闭的,如果BA。,一个代数系统需要满足以下三个条件：有一个非空集合S；有一些建立在集合S上的运算；这些运算在S上是封闭的。,代数系统的基本概念,例,在整数集合I上定义如下：对任何其中的+，分别是通常数的加法和乘法。那么是一个从I2到I的函数，易知在集合I上是封闭的，是一个代数系统。,如果两个代数系统有相同个数的运算符，每个相对应的运算符的元数是相同的，则称这两个代数系统是同类型的。定义：两个代数系统(U，)与(U，*)，如果满足下列条件：UU；若aU，bU，则a*b=ab；则称(U，*)是(U，)的子系统或子代数。,代数系统的基本概念,设有代数系统(S，*)，对a，b，cS，如果有(a*b)*c=a*(b*c),则称此代数系统的运算满足结合律。例：设A是一个非空集合，是A上的二元运算，对于任意a，bA，有ab=b，证明：是满足结合律的。证：对于任意的a，b，cA，(ab)c=bc=c而a(bc)=ac=c，(ab)c=a(bc)是满足结合律的.,代数运算及其性质,交换律设有代数系统(S，*)，如果对于a，bS，有a*b=b*a，则称此代数系统的运算“*”满足交换律。例：在整合集合I上定义运算：对任何其中的+，分别是通常数的加法和乘法。可以满足交换律吗？,分配律(左分配，右分配)设有代数系统(S，*)，对a,b,cS，如果有a(b*c)=(ab)*(ac)，则称“”运算对“*”运算满足左分配律。若“*”对“”满足a*(bc)=(a*b)(a*c)，则称“*”对“”满足左分配律若有(a*b)c=(a*c)(b*c)，则称“”对“*”满足右分配律。若(ab)*c=(a*c)(b*c)，则称“*”运算对“”运算满足右分配律。例：代数系统(N，+，)。其中+，分别代表通常数的加法和乘法。是否满足交换律？,单位元(幺元),一个代数系统(S，*)，若存在一个元素eU，使得对xS，有：e*x=x*e=x，则称e为对于运算“*”的单位元,也称幺元。注意：单位元是跟运算有关系的，不同的运算可能单位元是不一样的。,左单位元或右单位元(左幺元或右幺元)一个代数系统(S，)，若存在一个元素elS，使得对xS，有：elx=x，则称el为对于运算“”的左幺元。若存在一个元素erS，使得对xS，有：xer=x，则称er为对于运算“”的右幺元。,例设代数系统(N，*)，*的定义为：对那么，(N，*)有没有单位元？左幺元？右幺元？解：对任何因此1是右幺元。但1不是左幺元，因为所以(N，*)没有左幺元，当然也就没有幺元。,定理,代数系统(U,)的单位元若存在，则唯一。证：设e为运算“”的幺元，另有一单位元e，e是幺元，对xU，有ex=x，取x=e，则ee=e又e是幺元，对xU，有xe=x，取x=e，则ee=e由式可得：e=e，即幺元唯一。,零元,代数系统(S，)，如果存在一个元素S，使得对xS有：x=x=，则称为对于运算“”的零元。若只满足x=，则称为左零元。若只满足x=，则称为右零元。例:代数系统(I，)的零元是什么？在所有n阶方阵集合M上的代数系统(M，)，零元是什么？在I+上定义一个二元运算取极小“Min”，(I+，Min)的零元是什么？,性质、定理,定理一个代数系统，其零元若存在，则唯一。定理一个代数系统(S，)，若集合A中元素的个数大于1，且该代数系统存在幺元e和零元，则e。证明：用反证法，设=e，则对于任意的xA，必有x=ex=x=e，即对于A中所有元素都是相同的，这与A中含有多个元素相矛盾。,逆元,一个存在幺元e的代数系统(U，)，如果对U中的元素x存在x-1，使得x-1x=xx-1=e，则称x-1为x的逆元。若xx-1=e，则称x-1为x的右逆元。若x-1x=e，则称x-1为x的左逆元。既是左逆元，又是右逆元，则称x-1为x的一个逆元。,例子,对代数系统(R，*)，*为二元运算，定义为通常数的乘法。R为实数集合。aR，a0，a的逆元是什么?对代数系统(I，*)，*为二元运算，定义为通常数的乘法。I为整数集合。哪些元素有逆元？(R1，*)，*为二元运算，定义为通常数的乘法。R1为除了1之外的实数集合。哪些元素有逆元？,注意,因此，关于逆元，下述结论是正确的：当幺元存在时，才考虑逆元。逆元是针对具体元素而定的，有些元素可能有逆元，有些元素则可能没有逆元。如果a和b都有逆元且ab，则a-1和b-1也不相同。一个元素的逆元必须是代数系统内的元素。设e幺元，只有当ab=e和ba=e同时成立时，b才能是a的逆元，如果只有一个成立，b也不是a的逆元。,定理：设代数系统(U，)，运算“”满足结合律，且存在幺元e，那么对任意固定的xU，若x有逆元，则逆元是唯一的。证明：设x有两个逆元x1-1和x2-1，则x1-1xx2-1=x1-1(xx2-1)=x1-1e=x1-1同理x1-1xx2-1=(x1-1x)x2-1=ex2-1=x2-1所以：x1-1=x2-1,设*是定义在集合A上的一个二元运算，如果对于任意的xA，都有x*x=x，则称*运算是等幂的。例:S=1,2,4，在集合p(S)定义两个二元运算，分别表示集合的“并”运算和集合的“交”运算，是等幂的？解：对于任意的Ap(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：UV，使得对x1，x2U,有f(x1x2)=f(x1)*f(x2)，称f是一个从(U，)到(V，*)的同态映射，或说(U，)与(V，*)是同态的。若f是满射，则称f是(U，)到(V，*)的满同态映射，(U，)与(V，*)是满同态。若f是单射，则称f是(U，)到(V，*)的单同态映射，(U，)与(V，*)是单同态。若f是双射，则称f是(U，)到(V，*)的同构映射，(U，)与(V，*)是同构的。,同态与同构,例,解：作映射f：IA，,1.设集合A=a，b，c，在A上定义运算。如下表，那么，V1=(I，+)，V1=(A，)，其中I是正整数集合，+运算是普通的加法。V1和V1是否同态？,2.构造与之间的同态映射.(课堂练习),例,解：作双射f：A1A2，f(1)=b,f(2)=d,f(3)=c,f(4)=a,设代数系统V1=(A1，*)，V2=(A2，)，其中A1=1，2，3，4，A2=a，b，c，d，*和的运算分别如下表，V1和V2是否同构？,例,代数结构R+;*,R;+同构吗？,证明：与同构,下面证明二者之间存在双射关系且满足同态方程。i)建立双射关系：令f:R+R,f(x)=lnx显然，f是单射yR,x=ey使y=lney=lnx=f(x)f是满射f是从R+到R的双射ii)f满足同态方程：f(a*b)=ln（a*b）=lna+lnb=f(a)+f(b)综上，同构于,定理,设代数系统和其中*,*,都是二元运算，是V1到V2的满同态映射，则(1)如果*是可交换的，则*也是可交换的；(2)如果*是可结合的，则*也是可结合的；(3)如果*对是可分配的,则*对也是可分配的；(4)若e是*的单位元，则(e)是*的单位元;(5)若是*的零元，则()是*的零元;(6)若a关于运算*可逆，且逆元为b,则(a)关于运算*也可逆，逆元为(b)。,性质保持1.对于同构：保持结合律、交换律、分配律；单位元、逆元、零元相应存在.2.对于同态单向保持性质,可以证明,代数系统间的同构关系是等价关系。自反：构造映射f：UU,满足f(x)=x对称:f是U到V的同构映射，则f-1是V到U的同构映射。(U，)，(V，*)，(W，)，如果f是U到V同构映射，g是V到W的同构映射，则可证gof是U到W的同构映射。,代数系统间同构关系是等价关系,同态核,f是一个从(U，)到(V，*)的同态映射,e是(V，*)的单位元。定义集合K(f)=xxS且f(x)e为同态核，记为K(f)。定理设f为代数结构到的