离散数学 第六章 代数.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,6.1,代数结构,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,代 数,主讲：王书振,西安电子科技大学计算机学院,陕西省物联网实验研究中心,E-mail,:,shuzhenwang,Tel,:029-88203699,2026/1/31 周六,第六章 代 数,6.1,代数结构,6.2,子代数,6.3,同态,6.4,同余关系,6.5,商代数,6.6,半群和独异点,6.7,群,6.8,环和域,yuliang,2,2026/1/31 周六,6.1,代数结构,代数系统,一个非空集合,A,，连同若干个定义在该集合上的运算,f,1,f,2,f,n,，,所组成的系统称为一个代数系统，简称代数，记为,。,2026/1/31 周六,6.1,代数结构,代数系统的组成,载体（一个非空集合,A,）,定义在载体上的运算,(,f,1,f,2,f,n,),代数常元,2026/1/31 周六,6.1,代数结构,【,例题,1】,(a),正整数集合,I,+,，以及定义在该集合上的普通加法运算“,+”,组成一个代数系统,。,(b),一个有限集合,S,，由,S,的幂集,(,S,),，及定义在,(,S,),上的交、并、补运算组成一个代数系统,。,2026/1/31 周六,6.1,代数结构,代数运算,设,A1,A2,An,A,是非空集合，,f,是从,A1A2An,到,A,的一个映射，则称,f,为从集合,A1A2An,到,A,的一个,n,元代数运算，简称运算，,n,称为代数运算的阶。,x,n,x,3,f,x,2,x,1,y,yuliang,6,2026/1/31 周六,6.1,代数结构,运算的封闭性,设,f,是从,A1A2An,到,A,的一个,n,元运算，若,A=A1=A2=An,，则称该,n,元运算在集合,A,上是封闭的，亦称,f,是,A,上的,n,元运算。,特别地，设,f,是从,A,到,A,的映射，则称,f,是一个在,A,上封闭的,一元运算,。设,f,是从,A,2,到,A,的映射，则称,f,是一个在,A,上的封闭的,二元运算,。,2026/1/31 周六,6.1,代数结构,【,例题,2】,一台自动售货机能接受五角和一元的硬币。当人们投入任意两枚上述硬币时，自动售货机将供应出相应的饮料，如下表,5,角,1,元,5,角,雪碧,可乐,1,元,可乐,酷儿,2026/1/31 周六,6.1,代数结构,设集合,A,5,角，,1,元,，集合,B,雪碧，可乐，酷儿,，则上表其实是一个从,AA,到,B,的一个映射，也即一个从,A,2,到,B,的一个二元运算。问运算在,A,上是否封闭？,2026/1/31 周六,6.1,代数结构,【,例题,3】,设有正整数集,I,+,，“,+”,是,I,+,上的普通加法运算。在,I,+,上定义二元运算*为：任取,x,y,I,+,x*y=,x+y,。令,S=,2k|,k,I,+,=,2,4,6,8,T=,n|n,I,+,n,能整除,30,=,1,2,3,5,6,10,15,30,问运算*在,S,和,T,上是否封闭,?,2026/1/31 周六,6.1,代数结构,运算表,当集合,A,是有限集时，例如,A=,a,1,a,2,a,n,，则,A,上一元代数运算和二元代数运算分别用如表,(,a,),和,(b),所示的运算表来表示。,a,1,a,2,a,n,a,1,a,2,a,n,a,1,a,1,a,1,a,2,a,1,a,n,a,2,a,1,a,2,a,2,a,2,a,n,a,n,a,1,a,n,a,2,a,n,a,n,(,a,i,),a,1,a,2,a,n,(a,1,),(a,2,),(a,n,),(a),(b),运算符,集合,A,运算结果,yuliang,11,2026/1/31 周六,6.1,代数结构,代数运算的性质一,交换律,设*是定义在集合,A,上的一个二元运算，如果任取,x,yA,，都有,x*y=y*x,，则称该二元运算是可交换的。,【,例题,4】,设,Q,是有理数集合，是,Q,上的二元运算，对任意,a,bQ,ab,=,a+b-a,b,其中,+,和,是普通的加法、乘法运算，问是否是可交换的？,2026/1/31 周六,6.1,代数结构,代数运算的性质二,结合律,设*是定义在集合,A,上的一个二元运算，如果对于任意,x,y,zA,，都有,x*(y*z)=(x*y)*z,则称该二元运算是可结合的。,【,例题,5】,设,A,是一个非空集合，*是,A,上的一个二元运算，对于任意,a,b,A,有,a*b=b,证明运算*是可结合的。,yuliang,13,2026/1/31 周六,6.1,代数结构,代数运算的性质三,分配律,设*和 是定义在集合,A,上的二元运算，如果对任意的,a,b,cA,，都有,*对 左可分配,*对 右可分配,则称*对 是可分配的。,yuliang,14,2026/1/31 周六,6.1,代数结构,代数运算的性质三,【,例题,6】,设集合,A=,在,A,上定义两个二元运算*和,，如下表,(a),和,(,b),所示。,运算,对运算*可分配吗？运算*对运算,呢？,*,(a),(b),yuliang,15,2026/1/31 周六,6.1,代数结构,代数运算的性质四,吸收律,设*和 是定义在集合,A,上的两个可交换的二元运算，如果对于任意的,x,yA,都有,则称运算*和 满足吸收律。,yuliang,16,2026/1/31 周六,6.1,代数结构,代数运算的性质五,等幂律,设*是定义在集合,A,上的一个二元运算，如果对于任意,xA,都有,x*x=x,则称运算*满足等幂律。,yuliang,17,2026/1/31 周六,6.1,代数结构,【,例题,7】,设,(S),是集合,S,上的幂集，在,(S),上定义两个二元运算：集合的并运算,和集合的交运算,，验证,和,满足吸收律和等幂律。,解答：,和,运算是可交换的。,A,B,(S),有,A,(A,B)=A A,(A,B)=A,所以,和,满足吸收律。又有,A,A=A A,A=A,所以,和,满足等幂律。,2026/1/31 周六,6.1,代数结构,代数运算的性质六,消去律,设*是定义在集合上的一个二元运算，元素,aA,如果对于任意,x,y,A,都有,a*x=a*y x=y,a,是左可消去的,x*a=y*a x=y,a,是右可消去的,则称,a,关于运算*是可消去的。若,A,中的所有元素都是可消去的，则称运算*满足消去律。,yuliang,19,2026/1/31 周六,6.1,代数结构,代数常元,代数系统中，针对某一代数运算表现出具有某些特殊性质的元素称为代数常元，常见的有：,幺元、零元、逆元、等幂元,等。,幺元,左幺元,：设*是定义在集合,A,上的一个二元运算，若存在元素,e,l,，对于,A,中的每一个元素,x,，都有,e,l,*x,=,x,则称,e,l,为,A,中关于运算*的左幺元。,yuliang,20,2026/1/31 周六,6.1,代数结构,幺元,右幺元,：设*是定义在集合,A,上的一个二元运算，若存在元素,e,r,，对于,A,中每一个元素,x,都有,x*,e,r,=x,则称,e,r,为,A,中关于运算*的右幺元。,yuliang,21,2026/1/31 周六,6.1,代数结构,幺元,幺元,：设*是定义在集合,A,上一个二元运算，若,A,中有一个运算,e,它既是左幺元，又是右幺元，则称,e,为,A,中关于运算*的幺元，亦称作单位元。,e*x=x*e=x,yuliang,22,2026/1/31 周六,6.1,代数结构,【,例题,8】,设集合,S=,a,b,c,d,S,上定义的两个二元运算*和的运算表如下表所示，试求出其中的左幺元和右幺元。,*,a b c d,a,b,c,d,d a b c,a b c d,a b c c,a b c d,a b c d,a,b,c,d,a b d c,b a c d,c d a b,d d b c,(a),(b),yuliang,23,2026/1/31 周六,6.1,代数结构,定理,设*是定义在集合,A,上的一个二元运算，且在,A,中有关于运算*的左幺元,e,l,和右幺元,e,r,则,e,l,=,e,r,=e,且,A,中的幺元是唯一的。,证明：,设,e,l,和,e,r,分别是,A,中关于运算*的左幺元和右幺元，则有,e,l,=,e,l,*,e,r,=,e,r,=e,假设另有幺元,e,A,则有,e=e*e=e,结论得证。,yuliang,24,2026/1/31 周六,6.1,代数结构,代数常元,零元,左零元,：设*是定义在集合,A,上的一个二元运算，如果有一个元素,l,A,对于任意的元素,x,A,都有,l,*x=,l,，则称,l,为,A,中关于运算*的左零元。,右零元,：如果有一个元素,r,A,对于任意的元素,x,A,都有,x,*,r,=,r,，则称,r,为,A,中关于运算*的右零元。,yuliang,25,2026/1/31 周六,6.1,代数结构,零元,零元,：如果,A,中的一个元素,，它既是左零元，又是右零元，则称,为,A,中关于运算*的零元。,*x=x*,=,yuliang,26,2026/1/31 周六,6.1,代数结构,【,例题,9】,设“浅”表示不易褪色的浅色衣服，“深”表示易褪色的深色衣服，集合,S,=,浅，深,，定义,S,的一个二元运算“混洗”，记为“”，则 的运算表如下表所示。求,S,中关于 运算的幺元和零元。,浅 深,浅,深,浅 深,深 深,yuliang,27,2026/1/31 周六,6.1,代数结构,定理,设*是定义在集合,A,上一个二元运算，且在,A,中有关于运算*的左零元,l,和右零元,r,那么,l,=,r,=,，且,A,中的零元是唯一的。,yuliang,28,2026/1/31 周六,6.1,代数结构,逆元,逆元,：设,是一个代数系统，*是定义在集合,A,上的一个二元运算，,e,是,A,中关于运算*的幺元。,x,yA,如果,x*y=e,那么关于运算*,x,是,y,的左逆元，,y,是,x,的右逆元。如果,x*y=y*x=e,那么关于运算*,x,与,y,互为逆元。运算,x,的逆元记为,x,-1,。,yuliang,29,2026/1/31 周六,6.1,代数结构,定理,设,是一个代数系统，*是定义在集合,A,上的一个二元运算，,e,是,A,中关于运算*的幺元。若运算*是可结合的，且元素,x,有左逆元,l,和右逆元,r,，则,l,=,r,。,证明：因为,e,是,A,中关于运算*的幺元且,x,有左逆元,l,和右逆元,r,则有,l*x=x*r=e,又运算是可结合的，所以,l=l*e=l*(x*r)=(l*x)*r=e*r=r,yuliang,30,2026/1/31 周六,6.1,本节小结,代数系统组成,：,载体、定义在载体上的运算、代数常元。,设,为代数系统，*是定义在,A,上的二元运算，则运算*的某些性质以及代数常元可以直接从运算表中得到,：,运算*是封闭的，当且仅当运算表中的每个元素都属于,A,；,运算*满足交换律，当且仅当运算表关于主对角线对称；,yuliang,31,2026/1/31 周六,6.1,本节小结,运算满足等幂律，当且仅当运算表中主对角线上的每一元素与它所对应的行,(,列,),表头元素相同,;,运算满足消去律，当且仅当运算表中任意行、任意列没有相同的两个元素；,若,A,中有关于运算*的零元，则该元素所在的行和列中的所有元素都等于该元素；,若,A,中有关于运算*的幺元，则该元素所在的行,(,列,),中的所有元素都依次与列,(,行,),表头元素相同,;,yuliang,32,2026/1/31 周六,6.1,本节小结,设,A,中有关于运算*的幺元,e,，元素,a,与,b,互逆，当且仅当运算表中,a,行、,b,列对应的元素与,a,列、,b,行对应的元素都是,e,。,代数常元,：,幺元、零元。,yuliang,33,2026/1/31 周六,6.1,习题,习题一,设,为代数系统，其中,A=1,2,3,4,“*”,定义如下表所示：,(a),运算*是可交换的吗？为什么？,(b),运算*是可结合的吗？为什么？,(c),求,A,中关于运算*的幺元，,并给出每个元素的逆元。,(,d)A,中有关于运算*的零元吗？,*,1 2 3 4,1,2,3,4,1 2 3 4,2 3 4 1,3 4 1 2,4 1 2 3,yuliang,34,2026/1/31 周六,6.1,习题,习题二,设,I,是整数集合，函数,g:III,，定义为：,g,(,x,y,),=x*y=x,y,xy,，其中,+,和,是普通的加法和乘法运算。,(a),试证明二元运算*是可交换的和可结合的。,(b),求运算*的幺元，并指出每个元素的逆元。,yuliang,35,2026/1/31 周六,6.2,子代数,子代数定义,设,是一个代数系统，*和分别是载体,A,上的二元运算和一元运算，,k,是代数常元，如果满足,(1),A A,(2)*,和运算在,A,上封闭，,(3),k,A,那么称,是,的子代数。,yuliang,36,2026/1/31 周六,6.2,子代数,平凡子代数定义,设,是一代数系统，,T,是由,A,中的代数常元构成的集合，且运算*和在,T,上封闭。称,和,是,的平凡子代数，非平凡子代数亦称为,真子代数,。,yuliang,37,2026/1/31 周六,6.2,习题,习题一,I,是整数集合，,I,e,和,I,o,分别是偶数集合和奇数集合，,+,是,I,上的普通加法运算，则,是一代数系统。,和,是,的子代数吗？,解答：,是,的子代数。而,不是,的子代数，因为,I,o,在,+,上不封闭。,yuliang,38,2026/1/31 周六,6.2,习题,习题二,I,是整数集合，,I,+,是正整数集合，,+,是,I,上的普通加法运算，则,是一代数系统。,是,的子代数吗？,解答：,不是,的子代数，因为,0,I,+,。,yuliang,39,2026/1/31 周六,6.3,同态,同态的定义,设,A=,和,A=,是两个具有相同构成的代数系统，,f,是从,S,到,S,的一个映射，且对任意,a,bS,满足：,f(a,*b)=,f(a,)*,f(b,),f(a,)=,f(a,),f(k,)=k,则称,f,为由,A,到,A,的一个同态映射，简称同态。,A,同态于,A,记作,AA,。,yuliang,40,2026/1/31 周六,6.3,同态,同态象,设,f,是从,A=,到,A=,的一个同态映射，称,为,A,在映射,f,下的同态象。其中,下图反映了两个代数系统间的同态关系。,yuliang,41,2026/1/31 周六,6.3,同态,k,S,S,f,k,a,f(a,),b,f(b,),c,f(c,),a*b,f(a,)*,f(b,),(c),f(c,),*,*,同态象,yuliang,42,2026/1/31 周六,6.3,同态,【,例题,1】,设代数系统,I,是整数集,是普通乘法运算。如果我们只对运算结果是正数、负数还是零关心,那么代数系统,中的运算结果的特征就可以用另一个代数系统,的运算结果来表示,其中,B,+,-,0,是,B,上的二元运算，运算表如下所示，构造从,到,的同态映射。,yuliang,43,2026/1/31 周六,6.3,同态,解答：,构造函数,f:IB,f(x,),显然，任取,a,bI,f(a,b,)=,f(a,),f(b,),。,所以，,f,是由,到,的一个同态。,+-0,+,-,0,+-0,-+0,0 0 0,+x0,-x0,0 x=0,yuliang,44,2026/1/31 周六,6.3,同态,同态的分类,设,f,是由,A=S,*,k,到,A=S,*,k,的一个同态。,满同态,:,若,f,是满射的，则称,f,为由,A,到,A,的一个满同态。,A,就是,A,在满同态,f,下一个同态象。,单一同态,：若,f,是单射的，则称,f,为由,A,到,A,的一个单一同态。显然，,A,在单一同态,f,下的同态象,与,A,同构。,yuliang,45,2026/1/31 周六,6.3,同态,同态的分类,同构,：若,f,是双射的，则称,f,为由,A,到,A,的一个同构映射，简称同构。,A,同构于,A,，记作,A A,。,自同态,：若,A=A,，则称,f,为,A,上的自同态。,自同构,：若,A=A,且,f,是双射的，则称,f,为,A,上的自同构。,yuliang,46,2026/1/31 周六,6.3,同态,【,例题,2】,N,是自然数集合，,+,是,N,上的普通加法运算，设,N,k,=0,1,2,k-1,+,k,是定义在,N,上的模,k,加法运算。设函数,f:,NN,k,定义为,f(x,)=x(mod k),证明：,f,是从,到,N,k,+,k,0),的一个满同态 映射。,yuliang,47,2026/1/31 周六,6.3,同态,证明：,(a),显然，,f,是从,N,到,N,k,的满射。,(b),任取,x,yN,有,f(x+y,)=(,x+y)(mod,k)=(,x(mod,k)+,y(mod,k)(mod k)=(,x(mod,k)+,k,(,y(mod,k)=,f(x)+,k,f(y,),(c),f(0)=0,。,所以，,f,是从,到,的一个满同态。,yuliang,48,2026/1/31 周六,6.3,同态,【,例题,3】,设,A=,a,b,c,d,在,A,上定义一个二元运算如表,a,所示，又设,B=0,1,2,3,在,B,上定义一个二元运算*如表,b,所示。构造从代数系统,到,的一个同构映射。,a b c d,a,b,c,d,a a a a,a b c d,a c a c,a d c b,*,0 1 2 3,0,1,2,3,2 0 2 0,0 1 2 3,2 2 2 2,0 3 2 1,(a),(b),yuliang,49,2026/1/31 周六,6.3,同态,解答：,设函数,h:AB,h(a,)=2,h(b)=1,h(c)=0,h(d)=3,。,容易验证：,(a),h,是双射的；,(b),任取,x,yA,h(xy,)=,h(x,)*,h(y,);,(c),中的幺元,b,h(b,)=1,也是,中的幺元；,中的零元,a,h(a,)=2,也是,的零元。,所以,h,是从代数系统,到,的一个同构映射。,yuliang,50,2026/1/31 周六,6.3,同态的性质,定理,设,f,是从,A=,到,A=,的一个同态映射，那么,A,的同态象,是,A,的子代数。,证明：,(i),因为,f,是从,S,到,S,的一个映射,所以,f(S,)S,。,(ii),因为,kS,f(k,)=k,所以,kf(S,).,(iii),任取,a,bf(S,),，存在,x,yS,使得,f(x,)=,a,f(y,)=b,。,因为,x*y=,zS,所以,a*b=,f(x,)*,f(y,)=,f(x,*y)=,f(z,),f(S,),故,f(S,),在运算*下是封闭的。,yuliang,51,2026/1/31 周六,6.3,同态的性质,(iv),任取,af(S,),存在,xS,使得,f(x,)=a,。,因为,xS,所以,a=,f(x,)=,f(x,),f(S,),故,f(S,),在运算,下是封闭的。,由,(,i)(ii)(iii)(iv,),可知，,是,A,的子代数。,f,A=,同态象,A=,yuliang,52,2026/1/31 周六,6.3,同态的性质,定理,设,f,是从,A=,到,A=,的一个同态映射，,A=,是,A,在同态映射,f,下的同态象，则有,(1),若*在,A,中可交换,则*在,A,中也是可交换的,;,(2),若*在,A,中可结合,则*在,A,中也是可结合的,;,(3),若在,A,中*对,可分配,则在,A,中*对,也可分配,;,yuliang,53,2026/1/31 周六,6.3,同态的性质,(4),若,e,是,A,中关于运算*的幺元，则,f(e,),是,A,中关于运算*的幺元；,(5),若,是,A,中关于运算*的零元，则,f(,),是,A,中关于运算*的零元；,(6),任取,x,S,x,对运算*有逆元,x,-1,在,f(S,),中，,f(x,),也有关于运算*的逆元,f(x,-1,),。,yuliang,54,2026/1/31 周六,6.3,小结,子代数概念：,一个代数系统载体,A,的一个子集,A,，如果在该代数系统的所有运算下都封闭，则称以,A,为载体的代数系统是原代数系统的子代数。,同态概念：,同态映射不仅建立了两个代数系统载体间的映射关系，更重要的是同时还建立了两个代数系统对应运算间的映射关系。,yuliang,55,2026/1/31 周六,6.3,小结,同态象概念：,一个代数系统与其同态象之间有许多相似的地方。,同态的分类：,根据同态映射的性质可以将同态分为：满同态、单一同态和同构。,同态性质：,在同态映射下，同态象的运算能够保持原代数系统中对应运算的交换性、结合性和分配性，并且幺元、零元和逆元也满足映射对应关系。,yuliang,56,2026/1/31 周六,6.3,本节习题,习题一,设,h,是从,A=,到,A=,的同态，证明如果,是,A,的子代数，那么,是,A,的子代数。,h,-1,(T),T,h,h,-1,h,A=,A=,yuliang,57,2026/1/31 周六,6.3,本节习题,证明：,(i),因为,是,的子代数，所以,T S,。故有,h,-1,(T)h,-1,(S)S,。,(ii),任取,x,yh,-1,(T),存在,x,yT,使得,h(x,)=,x,h(y,)=y,因为,x,yS,且,h,是从,A,到,A,的同态，所以有,h(x,*y)=,h(x,)*,h(y,)=x*y T,故,x*yh,-1,(T),即,h,-1,(T),对*运算是封闭的。,(iii),因为,h(k,)=k T,所以,k h,-1,(T),。,由,(,i)(ii)(iii,),可知，,是,的子代数。,yuliang,58,2026/1/31 周六,6.4,同余关系,同余的定义,运算上的同余关系：,设,A=,是一个代数系统，,是载体,S,上的等价关系，任取,a,b,cS,。,(1),当,ab,时，若,ab,则等价关系,在一元运算下是可保持的，称,是关于运算同余关系。,(2),当,ab,和,cd,时，若有,a*,cb,*d,，则等价关系,在二元运算*下是可保持的，称,是关于运算*同余关系。,yuliang,59,2026/1/31 周六,6.4,同余关系,a,b,a,b,c,d,c,d,a=,a,c=,c,a,b,a*c,b*d,c,d,a*c=a*c,yuliang,60,2026/1/31 周六,6.4,同余关系,【,例题,1】,设,+,是整数集合,I,上的普通加法运算，,是,I,上的模,k(,kI,+,),相等关系，问,在运算,+,上是否是,I,上的同余关系？,分析：任意,a,b,和,c,d,有：,ab(mod,k),其实就是,a-b=n*k,cd(mod,k),其实就是,c-d,=m*k,那么,(,a+c)-(b+d,)=(,m+n,)*k,，即,(,a+c,)(,b+d)(mod,k),yuliang,61,2026/1/31 周六,6.4,同余关系,【,例题,2】,设是集合,I,上的一元运算，任取,aI,a=a,2,是,I,上的模,k(,kI,),相等关系，问,在运算是否是,I,上的同余关系？,是否是代数系统,A,上,A,的同余关系？,分析：,ab(mod,k),就相当于,(a-b)=n*k,a-b=(,a+b)(a-b,)=,(,a+b,)*n,*k,，,即,a,b,整数,m,yuliang,62,2026/1/31 周六,6.4,同余关系,代数系统上的同余关系：,设,A=,是一个代数系统，,是载体,S,上的等价关系，若,在,A,上的所有运算下都是可保持的，则称,为代数系统,A,上的同余关系。,yuliang,63,2026/1/31 周六,6.4,同余关系,定理,设,g,是从代数系统,A=,到,A=,的一个同态映射，那么由,g,诱导的,S,上的等价关系,是代数系统,A,上同余关系。,证明：由函数,g,诱导的,S,上的等价关系,为：任取,a,bS,ab,当且仅当,g(a,)=,g(b,),。,(i),若,ab,则,g(a,)=,g(b,),g(a,)=,g(b,),。,yuliang,64,2026/1/31 周六,6.4,同余关系,又,g,是从,A,到,A,的同态映射，所以有,g(a,)=,g(a,)=,g(b,)=,g(b,),故,a b,，这说明,在运算下是可保持的。,(ii),若,ab,且,cd,且有,g(a,)=,g(b),g(c,)=,g(d,),所以,g(a,)*,g(c,)=,g(b,)*,g(d,),又因,g,是从,A,到,A,的同态映射，所以有,g(a,)*,g(c,)=,g(a,*c)=,g(b,)*,g(d,)=,g(b,*d),故,a*,cb,*d,这说明等价关系,在运算*下是可保持的。,由,(,i)(ii,),可得，,是代数系统,A,上的同余关系。,yuliang,65,2026/1/31 周六,6.4,同余关系,运算上的同余关系：,等价关系在运算下的可保持性是指参与运算的对应元素，如果在同一个等价类中，则运算后所得的结果也必在同一个等价类中。,代数系统上的同余关系：,等价关系,R,如果在一个代数系统中的所有运算下都是可保持的，则,R,是,A,上的同余关系。同余关系使得元素所在的等价类在运算上可以作为一个整体来看待。,yuliang,66,2026/1/31 周六,6.5,商代数,商代数定义,:,设,A=,是一个代数系统，,是,A,上的同余关系，,A,关于,的商代数,A/=,。其中,a=a a*b=a*b,注意：,S/,是集合的集合，即等价类的集合，,形如：,a,b,*,是集合之间的运算,k,是代数常元的集合,yuliang,67,2026/1/31 周六,6.5,商代数,【,例题,】,代数系统,A=,，其中,S=a,1,a,2,a,3,a,4,a,5,一元运算和,由下表所示的运算表定义。又,S,上的等价关系,R,产生的,S,上的划分,=a,1,a,3,a,2,a,5,a,4,(a),证明：,R,是,A,上的同余关系。,(b),给出,A/R,。,a,1,a,2,a,3,a,4,a,5,a,4,a,3,a,4,a,2,a,1,a,3,a,2,a,1,a,3,a,5,yuliang,68,2026/1/31 周六,6.5,小结,商代数：,由等价关系,R,可以得到代数系统,A,的载体的一个划分，以这个划分为新的载体，按照原运算的规则建立等价类之间新的运算，这样得到的代数系统是原代数系统的商代数。,yuliang,69,2026/1/31 周六,6.6,半群和独异点,半群：,一个代数系统,，其中,S,是非空集合，*是,S,上一个二元运算，如果满足：,运算*是封闭的；,运算*是可结合的，即任取,x,y,zS,有,(x*y)*z=x*(y*z),则称,为半群。,yuliang,70,2026/1/31 周六,6.6,半群与独异点,【,例题,1】,设集合,S,k,=x|,xI,xk,其中,I,是整数集合，,kI,且,k 1,+,是普通加法运算。证明,是一个半群。,证明：因为,+,运算在,S,k,上封闭的和可结合的，所以,是半群。,考虑：如果,k 0,呢？如果,k -1,呢？,yuliang,71,2026/1/31 周六,6.6,半群与独异点,【,例题,2】,设,I,+,是正整数集合，,R,是实数集合，,R,+,和,R,-,分别表示正实数和负实数集合。问,、,、,和,都是半群吗？为什么？,解答：,满足半群的定义，它是半群。,、,、,的运算不封闭，因此均不是半群。,yuliang,72,2026/1/31 周六,6.6,半群与独异点,定理,设,是一个半群，,T S,且*在,T,上是封闭的，那么,是,的子代数，,也是一个半群，称为,的子半群。,独异点：,含有,幺元,的,半群,。,由于结合律在子代数上是可继承的，因此半群的子代数也是半群。,yuliang,73,2026/1/31 周六,6.6,半群与独异点,【,例题,3】,判断以下代数系统是否是独异点。,(a);,(b),。,解答：,(a),是半群，但不是独异点，因为不含有幺元,0,。,(b),是半群，因为含有幺元,0,，所以它也是独异点。,yuliang,74,2026/1/31 周六,6.6,半群与独异点,【,例题,4】,设,A=,0,1,2,3,+,4,和,4,分别是模,4,加法和模,4,乘法，其运算表分别如下页,(,a,),、,(,b,),所示，即任意,a,bA,有,a+,4,b=(a+b)(mod 4),a,4,b=(,ab,)(mod 4),(a),和,是独异点吗,?,为什么,?,(b),A,中的元素在运算,+,4,和,4,上有逆元吗,?,yuliang,75,2026/1/31 周六,6.6,半群与独异点,+,4,0 1 2 3,0,1,2,3,0 1 2 3,1 2 3 0,2 3 0 1,3 0 1 2,4,0 1 2 3,0,1,2,3,0 0 0 0,0 1 2 3,0 2 0 2,0 3 2 1,(a),(b),yuliang,76,2026/1/31 周六,6.6,半群与独异点,子独异点,：设,是一个独异点，,T S,且*在,T,上是封闭的，那么,是,的子代数,也是一个独异点，称为,的子独异点。,原代数系统的子代数,本身是独异点,在相同运算下，幺元相同,yuliang,77,2026/1/31 周六,6.6,半群与独异点,【,例题,5】,设,N,10,=0,1,2,3,9,10,是模,10,乘法运算，则,是一个独异点，,(a),写出,10,的运算表；,(b),取,N,10,的一个子集,A=0,2,4,6,8,证明,是一个独异点，但不是,的子独异点；,(c),构造,的一个含有,5,个元素的子独异点。,yuliang,78,2026/1/31 周六,6.6,半群与独异点,交换半群（独异点）,：在半群（独异点）中，若二元运算是可交换的，则称该半群（独异点）为交换半群（独异点）。,注：概念只作了解。,yuliang,79,2026/1/31 周六,6.6,半群和独异点的性质,定理,设,是一个半群，如果,S,是一个有限集，则必存在,aS,使得,a*a=a,。,证明：设,|S|=n,因为,是半群，任取,bS,由运算*的封闭性以及,S,为有限集知,b,b*b=b,2,b*b*b=b,3,b,n,b,n+1,S,根据抽屉原理，必有两个元素相等,不妨设为,b,i,=,b,j,(,其中,ji),。,n+1,yuliang,80,2026/1/31 周六,6.6,半群与独异点的性质,令,p=,j-i,显然有,p1,。由此可得,b,i,=,b,j,=,b,p+i,=,b,p,*b,i,。,b,i,=,b,p,*b,i,b,i+1,=,b,p,*b,i+1 ,b,kp,=,b,p,*,b,kp,又由,b,kp,=,b,p,*,b,kp,知,b,kp,=b,(k+1)p,b,(k+1)p,=,b,(k+2)p .,b,(2k-1)p,=b,2kp,因此有,b,kp,b,2kp,b,kp,*,b,kp,令,a=,b,kp,，则有,a=a*a,，证毕。,yuliang,81,2026/1/31 周六,6.6,半群与独异点,【,思考题,】,设,是一个独异点，*的运算表中可能出现两行或两列完全相同吗？,解答：不可能。设,S,中关于运算*的幺元是,e,。,任取,a,bS,若,ab,则有,e*a e*b,(,任何两列不同,),a*e b*e,(,任何两行不同,),所以运算*的运算表中任何两行和两列都是不同的。,yuliang,82,2026/1/31 周六,6.6,半群与独异点,循环独异点：,设,是一个独异点，若存在一个元素,gS,对于,S,中的每一个元素,a,都有一个对应的,kN,使得,a=,g,k,，则称此独异点为循环独异点。,g,称为此循环独异点的生成元。,yuliang,83,2026/1/31 周六,6.6,半群与独异点,【,例题,6】,判断以下代数系统是否是循环独异点，若是，指出生成元。,(a),;,(b),*,的运算表如下表所示。,*,a b c d,a,b,c,d,a b c d,b a d c,c d b a,d c a b,yuliang,84,2026/1/31 周六,6.6,本节小结,半群,半群定义：封闭、可结合,子半群：子集、封闭，子代数，子半群,半群性质：有限半群中必有等幂元,交换半群：可交换,yuliang,85,2026/1/31 周六,6.6,本节小结,独异点,独异点定义：含幺元半群,子独异点：子集、封闭、含有幺元,e,，子代数,交换独异点：可交换,循环独异点：有一个生成元,g,每个元素都可以用,g,k,表示,yuliang,86,2026/1/31 周六,6.7,群,群,：设,是一个代数系统，其中,G,是非空集合，*是,G,上一个二元运算。如果满足,运算*是封闭的，,运算*是可结合的，,存在幺元,e,，,对于每一个元素,xG,都存在逆元,x,-1,G,，,则称,是一个群。,半群,独异点,群,半群,独异点,群,yuliang,87,2026/1/31 周六,6.7,群,【,例题,1】,判断以下代数系统是否是群？,(a),I,是整数集合，,+,是普通加法运算。,(b),Q,是有理数集合，,是普通乘法运算。,(c),，,I,是整数集合，,是普通乘法运算。,(d),运算*如下表所示。,*,a b c,a,b,c,a b c,b c a,c a b,yuliang,88,2026/1/31 周六,6.7,群,【,例题,2】,设有代数系统,，其中,I,是整数集合，运算,的定义为，对任意,a,bI,有,a b=a+b-2,试问,是否是群？,解答：,(i),对任意,a,b,I,a b I,所以运算,在,I,上是封闭的。,yuliang,89,2026/1/31 周六,6.7,群,(ii),对任意的,a,b,c,I,有,(a b)c=(a+b-2)c=(a+b-2)+c-2=a+b+c-4,a(b c)=,a+(b,c)-2=a+(b+c-2)-2=a+b+c-4,所以,运算满足结合律。,(iii),任取,aI,ae,=a+e-2=a,得到,e=2,所以,2,是幺元。,(iv),任取,aI,aa,-1,=a+a,-1,-2=2,得到,a,-1,=4-aI,因此,I,中每个元素都有逆元。,由以上可知,是一个群。,yuliang,90,2026/1/31 周六,6.7,群,有限群：,设,是一个群，如果,G,是有限集，则称,为有限群。,无限群：,设,是一个群，如果,G,是无限集，则称,为无限群。,群的阶数：,有限群,的载体,G,的基数,|G|,，称为群的阶。,yuliang,91,2026/1/31 周六,6.7,群的性质,性质一：,群中无零元。,说明：当群中只有一个元素的时候，一般的把它看作幺元，如果它是零元的话，它就不符合群的定义了。因为零元没有逆元，零元与任何元素进行操作结果都是零元。如果群中有零元，则不符合群的定义了,(,任何一个元素都有逆元,),。,yuliang,92,2026/1/31 周六,6.7,群的性质,性质二：,群中每个元素的逆元都是唯一的。,说明：前面我们学过一个定理,6.1-3,，对于可结合运算，如果一个元素,x,有左逆元,l,和右逆元,r,那么,l=r,（即逆元是唯一的）。,假设群中的元素,a,有两个逆元,c,d,，,c=c*e=c*(a*d)=(c*a)*d=e*d=d,yuliang,93,2026/1/31 周六,6.7,群的性质,性质三：,设,是一个群，