离散数学 (10)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,14.2.1,代数系统的定义与实例,14.2.2,代数系统的分类,14.2.3,子代数系统与积代数系统,14.2.4,代数系统的同态与同构,14.2,代数系统,1,代数系统定义与实例,定义,14.7,非空集合,S,和,S,上,k,个一元或二元运算,f,1,f,2,f,k,组成的系统称为一个,代数系统,简称,代数,，记作,.,实例：,是代数系统，,+,和,分别表示普通加法和乘法,.,是代数系统，,+,和,分别表示,n,阶,(,n,2),实矩阵的加法和乘法,.,是代数系统，,Z,n,0,1,n,1,，,和,分别表示模,n,的加法和乘法，对于,x,y,Z,n,，,x,y,=(,x,y,)mod,n,，,x,y,=(,xy,)mod,n,也是代数系统，,和为并和交，,为绝对补,2,代数系统的分类,定义,14.8,(1),如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是,同类型的,代数系统,.,(2),如果两个同类型的代数系统对应的运算所规定的运算性质也相同，则称为,同种的,代数系统,.,例,1,V,1,=,V,2,=,为,n,阶全,0,矩阵，,E,为,n,阶单位矩阵,V,3,=,3,V,1,V,2,V,3,+,可交换,可结合,可交换,可结合,+,满足消去律,满足消去律,对,+,可分配,+,对,不可分配,+,与,没有吸收律,+,可交换,可结合,可交换,可结合,+,满足消去律,满足消去律,对,+,可分配,+,对,不可分配,+,与,没有吸收律,可交换,可结合,可交换,可结合,不满足消去律,不满足消去律,对,可分配,对,可分配,与,满足吸收律,V,1,V,2,V,3,是同类型的代数系统,V,1,V,2,是同种的代数系统,V,1,V,2,与,V,3,不是同种的代数系统,实例,三个代数系统的比较,4,子代数,定义,14.9,设,V,=,是代数系统，,B,是,S,的非空子集，如果,B,对,f,1,f,2,f,k,都是封闭的，且,B,和,S,含有相同的代数常数，则称,是,V,的,子代数系统,，简称,子代数,.,有时将子代数系统简记为,B,.,实例,N,是,的子代数，,N,也是,的子代数,N,0,是,的子代数，但不是,的子代数,说明：,子代数和原代数是同种的代数系统,对于任何代数系统,V,，其子代数一定存在,.,5,关于子代数的术语,最大的子代数：就是,V,本身,最小的子代数：,V,中所有代数常数构成集合,B,，且,B,对,V,中所有运算封闭，则,B,就构成了,V,的最小的子代数,平凡的子代数,：最大和最小子代数称为,V,的平凡子代数,真子代数,：若,B,是,S,的真子集，则,B,构成的子代数称为,V,的真子代数,.,例,2,设,V,=,，令,n,Z,=,nz,|,z,Z,，,n,为自然数，则,n,Z,是,V,的子代数,当,n,=1,和,0,时，,n,Z,是,V,的平凡的子代数，其他的都是,V,的非平凡的真子代数,.,6,积代数,定义,14.10,设,V,1,=,和,V,2,=,是代数系统，,其中,和,是二元运算,.,V,1,与,V,2,的,积代数,V,=,S,1,S,2,=,例,3,V,1,=,V,2,=,积代数,Z,M,2,(R),=,7,积代数的性质,设,V,1,=,和,V,2,=,是代数系统，其中,和,是二元,运算,.,V,1,与,V,2,的,积代数,是,V,=,(1),若,和,运算是可交换的，那么,运算也是可交换的,(2),若,和,运算是可结合的，那么,运算也是可结合的,(3),若,和,运算是幂等的，那么,运算也是幂等的,(4),若,和,运算分别具有单位元,e,1,和,e,2,，那么,运算,也具有单位元,(5),若,和,运算分别具有零元,1,和,2,，那么,运算,也具有零元,(6),若,x,关于,的逆元为,x,1,y,关于,的逆元为,y,1,，那么,关于,运算也具有逆元,8,代数系统的同态与同构,同态映射的定义,同态映射的分类,单同态、满同态、同构,自同态,同态映射的实例,满同态映射的性质,9,定义,14.11,设,V,1,=,和,V,2,=,是代数系统，其中,和,是二元运算,.,f,:,S,1,S,2,且,x,y,S,1,f,(,x,y,)=,f,(,x,),f,(,y,),则称,f,为,V,1,到,V,2,的,同态映射,，简称,同态,.,同态映射的定义,10,同态映射的定义,(,续,),例,1,V,=,判断下面的哪些函数是,V,的同态？,(1),f,(,x,)=|,x,|(2),f,(,x,)=2,x,(3),f,(,x,)=,x,2,(4),f,(,x,)=1/,x,(5),f,(,x,)=,x,(6),f,(,x,)=,x,+1,解,(1),是同态,f,(,x,y,)=|,x,y,|=|,x,|,|,y,|=,f,(,x,),f,(,y,),(4),是同态,f,(,x,y,)=1/(,x,y,)=1/,x,1/,y,=,f,(,x,),f,(,y,),(3),是同态,f,(,x,y,)=(,x,y,),2,=,x,2,y,2,=,f,(,x,),f,(,y,),(2),不是同态，,f,(2,2)=,f,(4)=8,f,(2),f,(2)=4 4=16,(5),不是同态，,f,(1,1)=,f,(1)=,1,f,(1),f,(1)=(,1)(,1)=1,(6),不是同态，,f,(1,1)=,f,(1)=2,f,(1),f,(1)=22=4,11,特殊同态映射的分类,同态映射如果是单射，则称为,单同态,；,如果是满射，则称为,满同态,，这时称,V,2,是,V,1,的,同态像,，记作,V,1,V,2,；,如果是双射，则称为,同构,，也称代数系统,V,1,同构于,V,2,，记作,V,1,V,2,.,对于代数系统,V,，它到自身的同态称为,自同态,.,类似地可以定义,单自同态,、,满自同态,和,自同构,.,12,例,2,(1),设,V,=,，,a,Z,，令,f,a,:Z,Z,，,f,a,(,x,)=,ax,那么,f,a,是,V,的自同态,.,因为,x,y,Z,，有,f,a,(,x,+,y,)=,a,(,x,+,y,)=,ax,+,ay,=,f,a,(,x,)+,f,a,(,y,),当,a,=0,时称,f,0,为零同态；当,a,=,1,时，称,f,a,为自同构；除此之外其他的,f,a,都是单自同态,.,(2),设,V,1,=,V,2,=,，,其中,Q*=Q,0,，,令,f,:Q,Q*,f,(,x,)=,e,x,那么,f,是,V,1,到,V,2,的同态映射，因为,x,y,Q,有,f,(,x,+,y,)=,e,x,+,y,=,e,x,e,y,=,f,(,x,),f,(,y,).,不难看出,f,是单同态,.,同态映射的实例,13,(3),V,=,f,p,：,Z,n,Z,n,f,p,(,x,)=(,xp,)mod,n,，,p,=0,1,n,1.,x,y,Z,n,f,p,(,x,y,)=(,x,y,),p,)mod,n,=(,xp,)mod,n,(,yp,)mod,n,=,f,p,(,x,),f,p,(,y,),例如，,n,=6.,f,0,(,x,)=0,f,1,(,x,)=,x,f,2,(0)=,f,2,(3)=0,f,2,(1)=,f,2,(4)=2,f,2,(2)=,f,2,(5)=4,f,3,(0)=,f,3,(2)=,f,3,(4)=0,f,3,(1)=,f,3,(3)=,f,3,(5)=3,f,4,(0)=,f,4,(3)=0,f,4,(1)=,f,4,(4)=4,f,4,(2)=,f,4,(5)=2,f,5,(0)=0,f,5,(1)=5,f,5,(2)=4,f,5,(3)=3,f,5,(4)=2,f,5,(5)=1,同态映射的实例,(,续,),14,(4),V,1,=,V,2,=,f,:,Z,Z,n,f,(,x,)=(,x,)mod,n,x,y,Z,f,(,x+y,)=(,x+y,)mod,n,=(,x,)mod,n,(,y,)mod,n,=,f,(,x,),f,(,y,),例如，,n,=3.,f,(3,x,)=0,f,(3,x+,1)=1,f,(3,x,+2)=2,f,为满同态,.,同态映射的实例,(,续,),15,满同态映射的性质,设,V,1,和,V,2,是代数系统，,f,:,V,1,V,2,是满同态映射,则,若,V,1,中的运算是可交换,(,可结合,幂等,),的，那么,V,2,中,对应的,运算也是可交换,(,可结合、幂等的,),的,.,(2),若,V,1,中的对运算是可分配的，那么,V,2,中对应的,对,运算也是可分配的,.,(3),若,V,1,中的和运算是可吸收的，那么,V,2,中对应的,和,运算也是可吸收的,.,(4),若,V,1,中运算具有单位元,e,1,(,或零元,1,),，那么,f,(,e,1,)(,或,f,(,1,),是,V,2,中关于对应的运算的单位元,(,或零元,).,(5),若,x,关于,V,1,中 运算,的逆元为,x,1,那么,f,(,x,),在,V,2,中关于,对应的,运算的逆元为,f,(,x,1,).,16,