北大离散数学chap5.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,代数系统,简介,这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。我们将介绍代数系统的最基本概念和最基本理论，以及几类常用的代数系统，它们是：半群，幺半群，群，环，域，格和布尔代数。本课程在第五，六章中介绍代数系统的内容。,第五章,代数系统的一般性质,第一节,二元运算及性质,内容：,二元运算，运算律，特殊元素。,重点：,(1),一元和二元运算的概念，,(2),二元运算律,(,结合律，交换律，,分配律,),，,(3),二元运算的特殊元素,(,幺元，,零元，逆元,),。,一般：,吸收律，消去律，幂等律。,一、二元运算。,1,、,定义：,设,上的,二元运算,(,即,运算封闭,),为集合，函数,称为,，,，,元运算，,掌握,，,，即一元，二元运算。,一、二元运算。,2,、记号：用,等符号表示二元运算，,称为,算符,。,例如：,记为,(,二元运算,),记为,(,一元运算,),但减法，除法不是。,但除法不是。,例,1,、,(1),上的加法，乘法都是二元运算，,(2),上的加法，乘法，减法都是二元运算，,上求相反数的运算是一元运算。,(3),非零实数集,上的乘法和除法都是二元运算。,但加法，减法不是，,而求倒数是一元运算。,(4),表示所有,阶实矩阵的集合,则矩阵的加法和乘法都是二元运算。,，,都是二元运算，,(5),集合,的幂集,上的,而绝对补集,(,为全集,),是一元运算。,(6),所有命题公式的集合上的,都是二元运算，,而否定,为一元运算。,(7),表示集合,上的所有函数的集合，,函数的合成运算,是,上的二元运算。,3,、一元，二元运算表。,当,为有穷集时，,都可以用运算表给出。,上的一元和二元运算,例,2,、,(1),设,，给出,上的运算绝对,和对称差,的运算表。,补集,解：,，“,”为一元运算，,“,”为二元运算，其运算表如下：,例,2,、,(2),设,，定义,二元运算如下：,上的两个,求运算,和,的运算表。,解：,分别是,，,的和,与积除以,5,的余数，运算表如下：,二、有关运算律。,设,是,上的二元运算，,1,、若,，则称,在,(,或称满足,交换律,),上,可交换,。,2,、若,，则称,在,(,或称满足,结合律,),上,可结合,。,二、有关运算律。,设,是,上的二元运算，,3,、若,则称运算,对,是,可分配,的。,(,或称,对,满足,分配律,),(2),矩阵的加法和乘法在,上是可结合的，,加法可交换，但乘法不可交换，乘法对加法,是可分配的。,例,3,、,(1),普通的加法和乘法在,上都是,可结合的，且是可交换的，乘法对加,法是可分配的。,(3),在幂集,上可结合，可交换，,但是相对补不可结合，不可交换，,和,是互相可分配的。,(4),在全体命题公式集合上可结合，可交换，,和,是相互可分配的。,三、一些特殊元素。,设,为,上的二元运算，,1,、,幺元,：,若,，对,则称,，,为运算,的,幺元,。,注：,(1),若幺元存在必唯一。,(2),若只有,或只有,，,则,，,称为左幺元或右幺元。,在,上，矩阵加法的幺元是,阶,0,矩阵，,矩阵乘法的幺元是,阶单位矩阵。,在幂集,上，运算,的幺元是,，运算,的幺元是全集,。,例如：在,上，加法的幺元是,0,，,乘法的幺元是,1,。在,算没有幺元，只有右幺元,0,上的减法运,例,4,、,在,(,非零实数集,),上定义运算如下：,则,中的任何元素都是右幺元，,但没有左幺元,，使,，,从而没有幺元。,2,、,零元,：,若,，对,，,，则称,为运算,的,零元,。,注：,(1),若零元存在必唯一。,(2),若只有,，或只有,，,则,分别称为左零元或右零元。,如例,4,的任何元素都是左零元，,从而也没有零元。,但没有右零元,，,例如：在,上加法没有零元，,乘法的零元是,0,。,在,上矩阵加法没有零元，矩阵乘法的零元,是,阶,0,矩阵。,在幂集,上，运算,的零元是,，运算,的,零元是,。,3,、,逆元,：,设,为,上的二元运算，,为运算,的幺元，若对,，存在,，使,，则称,为,的,逆元,。,注：,(1),逆元是针对某个元素,而言的,(,可能有些元素有逆元，有些没有,),(2),若二元运算,满足结合律且,存在则必唯一。,的逆元,3,、,逆元,：,设,为,上的二元运算，,为运算,的幺元，若对,，存在,，使,，则称,为,的,逆元,。,注：,(3),若只有,或只有,，,则,称为左逆元或右逆元。,例如：普通加法运算在,上有幺元,0,，,仅在,上任意元素,有逆元,，满足,在,上只有,0,有逆元,0,，而其它的自然数就,没有逆元。,在,上矩阵的乘法只有可逆矩阵存在逆元。,幂集,上关于运算,有幺元,，但除了,外，,其余元素都没有逆元。,例,5,、,判断普通的加法和乘法运算在下列集合中,是否二元运算。,(1),解：,加法，乘法都不是二元运算。,(2),解：,加法不是二元运算，,乘法是二元运算。,例,5,、,判断普通的加法和乘法运算在下列集合中,是否二元运算。,(3),解：,加法，乘法都是二元运算。,(4),解：,加法不是二元运算，,乘法是二元运算。,例,5,、,判断普通的加法和乘法运算在下列集合中,是否二元运算。,(5),解：,加法不是二元运算，,乘法是二元运算。,例,6,、,在实数集,上定义运算,如下：,(1),是,上的二元运算吗？,解：,因,，是二元运算。,(2),在,上满足交换律，结合律吗？,解：,因,，满足交换律，,，满足结合律。,例,6,、,在实数集,上定义运算,如下：,(3),关于,有幺元，零元吗？,解：,因对,，,，,故,0,为幺元，,因,，,故,为零元。,例,6,、,在实数集,上定义运算,如下：,(4),关于,每个元素有逆元吗？,解：,，有,且,时，无逆元。,故,时，,，,例,7,、,设,，二元运算,和,定义，问运算,如下表,和,是否可交换的；是否有零元；,是否有幺元；如果有幺元，指出哪些元素有逆元；,逆元是什么？,(1),没有零元，,可交换，,解：,运算,是幺元，,都有逆元，且,，,互为逆元。,(2),不可交换，,解：,运算,是左零元，,是幺元，,只有,有逆元，,，,由于,，故,是,的左逆元，,的右逆元，,是,(2),解：,但它们的逆元都不存在。,四、其它一些运算律和特殊元素。,(,了解,),1,、设,和,都是,上的可交换的二元运算，,若,，,则称,和,满足,吸收律,。,四、其它一些运算律和特殊元素。,(,了解,),2,、设,是,上的二元关系，,若,(,不是零元,),满足：,(1),若,，则,(2),若,，则,就称运算,满足,消去律,。,四、其它一些运算律和特殊元素。,(,了解,),3,、幂等元。,是,上的二元运算，对,设,，,若,，则称,为,幂等元,。,若,上所有元素都是幂等元，,则称运算,满足,幂等律,。,例如：,上的运算,和,，全体命题公式集合,上的运算,和,都满足吸收律，又分别满足幂等律，,但都不满足消去律,(,如,，不一定有,),。,上的加法运算都不满足幂等律，,但它们都有幂等元，幺元就是幂等元。,第二节代数系统及其子代数和积代数,内容：,代数系统，子代数，积代数。,重点：,掌握代数系统，,子代数的有关概念。,了解：,积代数的概念。,一、代数系统。,1,、,定义：,非空集合,和,上的,个运算,(,其中,为,元运算，,),组成的系统称为一个,代数系统,，简称,代数,，,记作,。,例如：,，,，,，,，,都是代数系统。,2,、代数常数,(,特异元素,),。,在某些代数系统中对于给定的二元运算存在,幺元或零元，它们对该系统的性质起着重要作,用，称为,代数常数,(,特异元素,),。,例如：,的幺元,0,，也可记为,，,中,和,的幺元分别为,和,，,同样可记为,。,二、子代数系统。,1,、,定义：,设,是代数系统，,且,，若,对运算,都,是封闭的，且,和,含有相同的代数常数，则,称,为,的,子代数系统,，简称,子代数,。,例如：,是,的子代数，,是,的子代数，,但,是,的子代数，,却不是,的子代数，,因代数常数,。,2,、平凡子代数，真子代数。,设,是代数系统,的子代数，当,和,时，称为,平凡子代数,(,分别是最大和最小的子代数,),，,当,时，称,为,的,真子代数,。,例,1,、,设,，令,为自然数，,，,那么,是,的子代数。,，,证明：,，则,即,对,+,封闭，,又,，所以,是,的子代数。,证明：,当,时，,，,当,时，,，,它们是,的平凡子代数，而其它的子代数都是,的非平凡的真子代数。,例,1,、,设,，令,为自然数，,，,那么,是,的子代数。,例,1,、,设,，令,为自然数，,，,那么,是,的子代数。,当,时，,，,当,时，,，,它们是,的平凡子代数，而其它的子代数都是,的非平凡的真子代数。,三、积代数。,设,是代数系统，,，,其中,和,是二元运算，,令,，对,则,为代数系统，称为,的,积代数,，,记,。,例如：,和,的积代数为,其中运算,为二元运算，,对,，,，,，,例如：,和,的积代数为,，,，,，,有代数常数,0,，,有代数常数,，,有代数常数,。,第三节,代数系统的同态与同构,内容：,代数系统的同态映射，同构映射。,一般：,掌握同态，单同态，满同态，同构的,定义及判定。,一、同态映射，同构映射的概念。,代数系统的同态和同构是研究两个代数系统,之间的关系。,1,、,定义,：,设,是代数系统，,，,其中,和,都是二元运算，若存在映射,(,即函数,),，满足对任意的,，有,则称,是,到,的,同态映射,，简称,同态,。,满同态，记,单同态,同构，记,注：,若存在从,到,的满同态,，则称,为,在,下的同态象。,例,1,、,(1),，,，,其中,为,普通加法，,为模,加法，即,，有,，这里,令,，,则对,，,例,1,、,(1),，,，,其中,为,普通加法，,为模,加法，即,，有,，这里,令,，,所以,是,到,的同态。,显然,是满射，所以,，即满同态，,但不是单同态,例,1,、,(2),，,，,则对,令,，,，,所以,是,到,的同态。,由于,是双射，所以是同构，,思考：,，,是同构映射吗？,2,、自同态，自同构。,自同态,从一个代数系统,到自己的同态称为自同态。,自同构,从一个代数系统,到自己的同构称为自同构。,则对,例,2,、,，给定,，令,，,所以,是,到,的同态，即自同态。,当,时，有,，,，,称,为零同态。,则对,例,2,、,，给定,，令,，,所以,是,到,的同态，即自同态。,当,时，有,，,，即恒等映射，,它是双射的，这时,是,的自同构，同理可证,也是,的自同构。,则对,例,2,、,，给定,，令,，,所以,是,到,的同态，即自同态。,当,且,时，易证,是单射的，,这时,是,的单自同态。,3,、同态，同构概念的推广。,(1),，,例,3,、,，,，其中,为普通的加法，乘法，,为模,加法，乘法,令,，,，,则对,，,例,3,、,，,，其中,为普通的加法，乘法，,为模,加法，乘法,令,，,，,所以,是,到,的同态，且是满同态。,(2),，,(3),，,例,4,、,(1),，,，其中,为普通加法和乘法，,表示求,的相反数，,表示,的倒数。,令,，,，则对,，,所以,是,到,的同态。,例,4,、,(2),，,，其中,0,是,加法幺元，,1,是乘法幺元，都是代数常数，,，,同,(1),，即,则有,，,所以,是,到,的同态。,二、性质。,设,是从,到,的满同态，则,1,、若,可结合，则,也是可结合。,2,、若,可交换，则,也是可交换。,3,、若,是关于,的幺元，则,是关于,的幺元。,4,、若,是关于,的零元，则,是关于,的零元。,二、性质。,设,是从,到,的满同态，则,5,、若,是关于,的幂等元，则,是关于,的幂等元。,6,、若,是,中元素,关于,的逆元，则,是,中元素,关于,的逆元。,注：,若,分别有两个二元运算，且,中分配律,成立，则,中分配律也成立。,第五章,小结与例题,一、二元运算及其性质。,1,、基本概念。,一元运算和二元运算；二元运算的结合律，交换律，分配律，幂等律，吸收律，消去律；二元运算的特殊元素：幺元，零元，逆元；一元运算和二元运算的运算表。,一、二元运算及其性质。,2,、运用。,(1),判断给定的二元运算是否满足结合律，交换律，,分配律，幂等律，吸收律，消去律等。,(2),求幺元，零元，逆元。,(3),列出一元运算和二元运算的运算表。,二、代数系统及其子代数和积代数。,1,、基本概念。,代数系统；子代数；积代数。,2,、运用。,判断代数系统的子集能否构成子代数系统。,三、代数系统的同态与同构。,1,、基本概念。,同态，单同态，满同态；同构。,2,、运用。,判断两个代数系统是否同态，单同态，,满同态，同构。,例,1,、,数的加，减，乘，除是否为下述集合上,的二元运算。,(1),实数集,解：,加、减、乘是二元运算，,除不是二元运算。,(2),非零实数集,解：,加、减不是二元运算，,乘、除是二元运算。,例,1,、,数的加，减，乘，除是否为下述集合上,的二元运算。,(3),正整数集,解：,加、乘是二元运算，,减、除不是二元运算。,(4),解：,乘是二元运算，,加、减、除都不是二元运算。,例,1,、,数的加，减，乘，除是否为下述集合上,的二元运算。,(5),解：,乘、除是二元运算，,加、减不是二元运算。,例,2,、,正整数集,上的二元运算,表示两个数,的最小公倍数。,(1),求,解：,(2),问,在,上满足交换律，结合律，,幂等律吗？,解：,因对任意的正整数,有,，,，,故,满足交换律，结合律，幂等律。,例,2,、,正整数集,上的二元运算,表示两个数,的最小公倍数。,(3),求幺元，零元。,(4),中任意元都有逆元吗？,解：,因,，故,1,是幺元，,不存在零元。,解：,中只有,1,有逆元，其它元素都没有逆元。,例,3,、,在有理数集,上定义二元运算,，,有,(1),求,，,解：,例,3,、,在有理数集,上定义二元运算,，,有,(2),在,上满足结合律吗？,解：,对任意的,故,满足结合律。,例,3,、,在有理数集,上定义二元运算,，,有,(3),求幺元。,解：,对任意的,故,0,是幺元。,例,3,、,在有理数集,上定义二元运算,，,有,(4),中哪些元素存在逆元？,解：,对任意的,，设,是,的逆元，则,解得：,即,时，有逆元,例,4,、,如下定义实数集,上的二元运算,，判断,是否可交换，可结合？是否有幺元？若有幺元，,指出,中哪些元素有逆元？,(1),解：,可交换；,但不可结合，,如：,，,而,，,即,；,无幺元。,例,4,、,如下定义实数集,上的二元运算,，判断,是否可交换，可结合？是否有幺元？若有幺元，,指出,中哪些元素有逆元？,(2),解：,可交换，,可结合，,无幺元。,例,4,、,如下定义实数集,上的二元运算,，判断,是否可交换，可结合？是否有幺元？若有幺元，,指出,中哪些元素有逆元？,(3),解：,不可交换，,如,，,即,。,例,4,、,如下定义实数集,上的二元运算,，判断,是否可交换，可结合？是否有幺元？若有幺元，,指出,中哪些元素有逆元？,(3),解：,不可结合，,如,，,即,，,无幺元。,例,4,、,如下定义实数集,上的二元运算,，判断,是否可交换，可结合？是否有幺元？若有幺元，,指出,中哪些元素有逆元？,(4),解：,可交换，,如,，,即,，,无幺元。,不可结合，,例,5,、,设,，,，其中,和,，,，,如下：,(1),满足交换律吗,?,解：,由于运算表关于主对角线对称，,所以,是可交换的。,例,5,、,设,，,，其中,和,，,，,如下：,(2),有幺元、零元吗？,解：,有幺元,，,零元,。,例,5,、,设,，,，其中,和,，,，,如下：,(3),设,，,，,，问,，,，,是否为代数,系统,的子代数？,解：,由于,的非空子集，,都是,其中,对运算,是封闭的，故,，,是,的子代数。,例,5,、,设,，,，其中,和,，,，,如下：,(3),设,，,，,，问,，,，,是否为代数,系统,的子代数？,解：,但,不封闭，,对运算,如,，,故,不是,的子代数。,例,5,、,设,，,，其中,和,，,，,如下：,定义同态,，且,，,，,，,，,(4),是单同态吗？是满同态吗？,例,5,、,设,，,，其中,和,，,，,如下：,定义同态,，且,，,，,，,，,(5),在,下的同态象是什么？,