离散数学第九章代数系统

单击此处编辑母版标题样式,*,*,第三部分 代数结构,主要内容,代数系统,-,二元运算及其性质、代数系统和子代数,半群与群,-,半群、独异点、群,环与域,-,环、整环、域,格与布尔代数,-,格、布尔代数,1,第九章 代数系统,主要内容,二元运算及其性质,一元和二元运算定义及其实例,二元运算的性质,代数系统,代数系统定义及其实例,子代数,积代数,代数系统的同态与同构,2,9.1,二元运算及其性质,定义9.1,设,S,为集合，函数,f,：,S,S,S,称为,S,上的,二元运算,，简,称为二元运算,S,中任何两个元素都可以进行运算，且运算的结果惟一,S,中任何两个元素的运算结果都属于,S,，即,S,对该运算封闭,例1,(1)自然数集合N上的加法和乘法是N上的二元运算，但,减法和除法不是,(2)整数集合Z上的加法、减法和乘法都是Z上的二元运算，,而除法不是,(3)非零实数集R*上的乘法和除法都是R*上的二元运算，而,加法和减法不是,3,实例,(4),设,M,n,(R)表示所有,n,阶(,n,2)实矩阵的集合，即,则矩阵加法和乘法都是,M,n,(R)上的二元运算.,(5),S,为任意集合，则、,为,P,(,S,)上二元运算.,(6),S,S,为,S,上的所有函数的集合，则合成运算,为,S,S,上二元运算.,4,一元运算的定义与实例,定义9.2,设,S,为集合，函数,f,:,S,S,称为,S,上的,一元运算,，简,称一元运算.,例2,(1)求相反数是整数集合Z,有理数集合Q和实数集合R上,的一元运算,(2)求倒数是非零有理数集合Q*,非零实数集合R*上一元运算,(3)求共轭复数是复数集合,C,上的一元运算,(4)在幂集,P,(,S,)上规定全集为,S,，则求绝对补运算是,P,(,S,)上的一元运算.,(5)设,S,为集合，令,A,为,S,上所有双射函数的集合，,A,S,S,，求一个双射函数的反函数为,A,上的一元运算.,(6)在,n,(,n,2)阶实矩阵的集合,M,n,(R)上，求转置矩阵是,M,n,(,R,)上的一元运算.,5,二元与一元运算的表示,1算符,可以用,等符号表示二元或一元运算，称为算符.,对二元运算,，如果,x,与,y,运算得到,z,，记做,x,y,=,z,对一元运算,x,的运算结果记作,x,.,2表示二元或一元运算的方法:解析公式和运算表,公式表示,例 设R为实数集合，如下定义R上的二元运算：,x,y,R,x,y,=,x,.,那么 34=3，0.5(,3)=0.5,6,运算表：表示有穷集上的一元和二元运算,运算表,二元运算的运算表,一元运算的运算表,7,例3,设,S,=,P,(,a,b,)，,S,上的,和,运算,的运算表如下,运算表的实例,8,二元运算的性质,定义9.3,设,为,S,上的二元运算,(1)若对任意,x,y,S,有,x,y,=,y,x,则称运算在,S,上满足,交换律,.,(2)若对任意,x,y,z,S,有(,x,y,),z,=,x,(,y,z,),则称运算在,S,上满足,结,合律,.,(3)若对任意,x,S,有,x,x,=,x,则称运算在,S,上满足,幂等律,.,定义9.4,设,和为,S,上两个不同的二元运算,(1)若对任意,x,y,z,S,有(,x,y,),z,=(,x,z,)(,y,z,)，,z,(,x,y,)=(,z,x,)(,z,y,),则称,运算对运算满足,分配律,.,(2)若,和都可交换,且对任意,x,y,S,有,x,(,x,y,)=,x,，,x,(,x,y,)=,x,则称,和运算满足,吸收律,.,9,实例,Z,Q,R分别为整数、有理数、实数集；,M,n,(,R,)为,n,阶实,矩阵集合,n,2；,P,(,B,)为幂集；,A,A,为从,A,到,A,的函数集，|,A,|,2,集合,运算,交换律,结合律,幂等律,Z,Q,R,普通加法+,普通乘法,有,有,有,有,无,无,M,n,(,R,),矩阵加法+,矩阵乘法,有,无,有,有,无,无,P,(,B,),并,交,相对补,对称差,有,有,无,有,有,有,无,有,有,有,无,无,A,A,函数复合,无,有,无,10,集合,运算,分配律,吸收律,Z,Q,R,普通加法+与乘法,对,+可分配,+对,不分配,无,M,n,(,R,),矩阵加法+与乘法,对,+可分配,+对,不分配,无,P,(,B,),并,与交,对,可分配,对,可分配,有,交,与对称差,对,可分配,无,实例,Z,Q,R分别为整数、有理数、实数集；,M,n,(,R,)为,n,阶实,矩阵集合,n,2；,P,(,B,)为幂集；,A,A,为从,A,到,A,的函数集，|,A,|,2,11,特异元素：单位元、零元,定义9.5,设,为,S,上的二元运算,(1)如果存在,e,l,(或,e,r,),S,，使得对任意,x,S,都有,e,l,x,=,x,(或,x,e,r,=,x,)，,则称,e,l,(或,e,r,)是,S,中关于,运算的,左,(或,右,),单位元,.,若,e,S,关于,运算既是左单位元又是右单位元，则称,e,为,S,上,关于,运算的,单位元,.单位元也叫做,幺元,.,(2)如果存在,l,(或,r,),S,，使得对任意,x,S,都有,l,x,=,l,(或,x,r,=,r,)，,则称,l,(或,r,)是,S,中关于,运算的,左,(或,右,),零元,.,若,S,关于,运算既是左零元又是右零元，则称,为,S,上关,于运算,的,零元,.,12,可逆元素和逆元,(3)设,为,S,上的二元运算,令,e,为,S,中关于运算,的单位元.,对于,x,S,，如果存在,y,l,(或,y,r,),S,使得,y,l,x,=,e,（或,x,y,r,=,e,）,则称,y,l,(或,y,r,)是,x,的,左逆元,（或,右逆元,）.,关于,运算，若,y,S,既是,x,的左逆元又是,x,的右逆元，则称,y,为,x,的,逆元,.如果,x,的逆元存在，就称,x,是,可逆的,.,13,实例,集合,运算,单位元,零元,逆元,Z,Q,R,普通加法+,普通乘法,0,1,无,0,x,逆元,x,x,逆元,x,1,(,x,1,给定集合),M,n,(,R,),矩阵加法+,矩阵乘法,n,阶全0矩阵,n,阶单位矩阵,无,n,阶全0矩阵,X,逆元,X,X,的逆元,X,1,（,X,可逆）,P,(,B,),并,交,对称差,B,B,无,的逆元为,B,的逆元为,B,X,的逆元为,X,14,惟一性定理,定理9.1,设,为,S,上的二元运算，,e,l,和,e,r,分别为,S,中关于运算的,左和右单位元，则,e,l,=,e,r,=,e,为,S,上关于,运算的惟一的单位元.,证：,e,l,=,e,l,e,r,(,e,r,为右单位元),e,l,e,r,=,e,r,(,e,l,为左单位元),所以,e,l,=,e,r,将这个单位元记作,e,.,假设,e,也是,S,中的单位元，则有,e,=,e,e,=,e,.惟一性得证.,类似地可以证明关于零元的惟一性定理.,注意：,当,|S|,2,，单位元与零元是不同的；,当,|S|=1,时，这个元素既是单位元也是零元,.,15,定理9.2,设,为,S,上可结合的二元运算,e,为该运算的单位元,对于,x,S,如果存在左逆元,y,l,和右逆元,y,r,则有,y,l,=,y,r,=,y,且,y,是,x,的惟一的逆元.,证：由,y,l,x,=,e,和,x,y,r,=,e,得,y,l,=,y,l,e,=,y,l,(,x,y,r,)=(,y,l,x,),y,r,=,e,y,r,=,y,r,令,y,l,=,y,r,=,y,则,y,是,x,的逆元.,假若,y,S,也是,x,的逆元,则,y,=,y,e,=,y,(,x,y,)=(,y,x,),y,=,e,y,=,y,所以,y,是,x,惟一的逆元.,说明：对于可结合的二元运算，可逆元素,x,只有惟一的逆,元，记作,x,1,惟一性定理,16,9.2,代数系统,定义9.6,非空集合,S,和,S,上,k,个一元或二元运算,f,1,f,2,f,k,组成,的系统称为,代数系统,简称代数，记做.,实例：,(1),是代数系统，+和分别表示普通加法和乘法.,(2)是代数系统，和分别表示,n,阶(,n,2)实矩阵的加法和乘法.,(3)是代数系统，Z,n,0,1,n,-1，,和,分别表示模,n,的加法和乘法，对于,x,y,Z,n,，,x,y,=(,x,y,)mod,n,，,x,y,=(,xy,)mod,n,(4)是代数系统，,和,为并和交，为绝对补,17,代数系统的成分与表示,构成代数系统的成分：,集合（也叫载体，规定了参与运算的元素）,运算（这里只讨论有限个二元和一元运算）,代数常数（通常是与运算相关的特异元素：如单位元等）,研究代数系统时，如果把运算具有的特异元素也作为系统,的性质之一，那么这些特异元素可以作为系统的成分，叫做,代数常数,.,例如：代数系统,：集合,Z,运算,+,代数常数,0,代数系统,：集合,P,(,S,),运算和，无代数常数,18,代数系统的表示,(1)列出所有的成分：集合、运算、代数常数（如果存在）,如,(2)列出集合和运算，在规定系统性质时不涉及具有单位元,的性质（无代数常数）,如,(3)用集合名称简单标记代数系统,在前面已经对代数系统作了说明的前提下使用,如代数系统,Z,P,(,B,),19,同类型与同种代数系统,定义9.7,(1)如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是,同类型的,代数系统.,(2)如果两个同类型的代数系统规定的运算性质也相同，则称为,同种的,代数系统.,例如,V,1,=,V,2,=,V,1,V,2,是同类型的代数系统，它们都含有,2,个二元运算,2,个代数常数,.,20,V,1,V,2,+可交换、可结合,可交换、可结合,+满足消去律,满足消去律,对+可分配,+对 不可分配,+与 没有吸收律,可交换、可结合,可交换、可结合,不满足消去律,不满足消去律,对可分配,对可分配,与满足吸收律,运算性质比较,V,1=,V,2=,所以,V1,V2是同类型的代数系统,但不是同种的代数系统.,21,子代数系统,定义9.8,设,V,=是代数系统，,B,是,S,的非空子,集，如果,B,对,f,1,f,2,f,k,都是封闭的，且,B,和,S,含有相同的代,数常数，则称是,V,的,子代数系统,，简称子代,数.有时将子代数系统简记为,B,.,实例,N是的子代数，N也是的子代数,N,0是的子代数，但不是的子代数,说明：,子代数和原代数是同种的代数系统,对于任何代数系统,V,=,，其子代数一定存在,.,22,关于子代数的术语,(1),最大的子代数,：就是,V,本身,(2),最小的子代数,：如果令,V,中所有代数常数构成的集合是,B,，且,B,对,V,中所有的运算都是封闭的，则,B,就构成了,V,的,最小的子代数,(3)最大和最小的子代数称为,V,的,平凡的子代数,(4)若,B,是,S,的真子集，则,B,构成的子代数称为,V,的,真子代数,.,例 设,V,=,令,n,Z=,nz,|,z,Z,n,为自然数，则,n,Z是,V,的子,代数,当,n,=1和0时，,n,Z是,V,的平凡的子代数，其他的都是,V,的非,平凡的真子代数.,23,积代数,定义9.9,设,V,1,=和,V,2,=是同类型的代数系统，,和,为二元运算，在集合,A,B,上如下定义二元运算，,A,B,，有,=,称,V,=为,V,1,与,V,2,的,积代数,，记作,V,1,V,2,.这时也称,V,1,和,V,2,为,V,的,因子代数,.,实例 Z,2,=0,1，V=，,V,1,V,2,=,Z,2,Z,2,=,=,注意：,积代数的定义可以推广到具有多个运算的同类型的代,数系统,模2的加法:,x,y,Z,2,x,y=(x+y)mod 2,24,积代数,实例 已知Z,2,=0,1，V=，其中,为,模2的加法:,x,y,Z,2,有x,y=(x+y)mod 2.,求,V,1,V,2,=,注意：,积代数的定义可以推广到具有多个运