离散数学第九章代数系统课件

单击此处编辑母版标题样式,*,*,第三部分 代数结构,主要内容,代数系统-二元运算及其性质、代数系统和子代数,半群与群-半群、独异点、群,环与域-环、整环、域,格与布尔代数-格、布尔代数,1,第三部分 代数结构主要内容1,第九章 代数系统,主要内容,二元运算及其性质,一元和二元运算定义及其实例,二元运算的性质,代数系统,代数系统定义及其实例,子代数,积代数,代数系统的同态与同构,2,第九章 代数系统主要内容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,9.1 二元运算及其性质定义9.1 设S为集合，函数f：S,实例,(4),设,M,n,(R)表示所有,n,阶(,n,2)实矩阵的集合，即,则矩阵加法和乘法都是,M,n,(R)上的二元运算.,(5),S,为任意集合，则、,为,P,(,S,)上二元运算.,(6),S,S,为,S,上的所有函数的集合，则合成运算,为,S,S,上二元运算.,4,实例(4)设Mn(R)表示所有n 阶(n2)实矩阵的集合,一元运算的定义与实例,定义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,一元运算的定义与实例定义9.2 设S为集合，函数 f:SS,二元与一元运算的表示,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,二元与一元运算的表示1算符2表示二元或一元运算的方法:,运算表：表示有穷集上的一元和二元运算,运算表,二元运算的运算表,一元运算的运算表,7,运算表：表示有穷集上的一元和二元运算运算表 二元运算的运算,例3,设,S,=,P,(,a,b,)，,S,上的,和,运算,的运算表如下,运算表的实例,8,例3 设 S=P(a,b)，S上的,二元运算的性质,定义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,二元运算的性质定义9.3 设为S上的二元运算,定义9.4,实例,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分别为整数、有理数、实数集；Mn(R)为n,集合,运算,分配律,吸收律,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,集合 运算分配律吸收律Z,Q,R普通加法+与乘法,特异元素：单位元、零元,定义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,特异元素：单位元、零元定义9.5 设为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,可逆元素和逆元(3)设为S上的二元运算,令e为S中关于,实例,集合,运算,单位元,零元,逆元,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,实例集合运算单位元零元逆元Z,Q,R普通加法+0无x逆元x,惟一性定理,定理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.1 设为S上的二元运算，el和er分别为,定理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 设为S上可结合的二元运算,e为该运算的单位,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,9.2 代数系统定义9.6 非空集合S和S上k个一元或二元,代数系统的成分与表示,构成代数系统的成分：,集合（也叫载体，规定了参与运算的元素）,运算（这里只讨论有限个二元和一元运算）,代数常数（通常是与运算相关的特异元素：如单位元等）,研究代数系统时，如果把运算具有的特异元素也作为系统,的性质之一，那么这些特异元素可以作为系统的成分，叫做,代数常数,.,例如：代数系统：集合Z,运算+,代数常数0,代数系统：集合,P,(,S,),运算和，无代数常数,18,代数系统的成分与表示构成代数系统的成分：18,代数系统的表示,(1)列出所有的成分：集合、运算、代数常数（如果存在）,如,(2)列出集合和运算，在规定系统性质时不涉及具有单位元,的性质（无代数常数）,如,(3)用集合名称简单标记代数系统,在前面已经对代数系统作了说明的前提下使用,如代数系统,Z,P,(,B,),19,代数系统的表示(1)列出所有的成分：集合、运算、代数常数（,同类型与同种代数系统,定义9.7,(1)如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是,同类型的,代数系统.,(2)如果两个同类型的代数系统规定的运算性质也相同，则称为,同种的,代数系统.,例如,V,1,=,V,2,=,V,1,V,2,是同类型的代数系统，它们都含有2个二元运算,2个代数常数.,20,同类型与同种代数系统定义9.7 20,V,1,V,2,+可交换、可结合,可交换、可结合,+满足消去律,满足消去律,对+可分配,+对 不可分配,+与 没有吸收律,可交换、可结合,可交换、可结合,不满足消去律,不满足消去律,对可分配,对可分配,与满足吸收律,运算性质比较,V,1=,V,2=,所以,V1,V2是同类型的代数系统,但不是同种的代数系统.,21,V1V2+可交换、可结合可交换、可结合运算性质比较V1=,子代数系统,定义9.8,设,V,=是代数系统，,B,是,S,的非空子,集，如果,B,对,f,1,f,2,f,k,都是封闭的，且,B,和,S,含有相同的代,数常数，则称是,V,的,子代数系统,，简称子代,数.有时将子代数系统简记为,B,.,实例,N是的子代数，N也是的子代数,N,0是的子代数，但不是的子代数,说明：,子代数和原代数是同种的代数系统,对于任何代数系统,V,=，其子代数一定存在.,22,子代数系统定义9.8设V=S,f1,f2,f,关于子代数的术语,(1),最大的子代数,：就是,V,本身,(2),最小的子代数,