第五代数结构.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五代数结构,1,代数系统的引入,（,3,）,命题公式,中,均为二元运算,而“,”为一元运算,（,4,）,双射函数,中,函数的合成运算是二元运算；,二元运算常用符号：,+,等等。,定义,:,一个非空集合,A,连同若干个定义在该集合上的运算,f,1,f,2,.,f,k,所组成的系统就称为一个代数系统，,记作,。,1,代数系统的引入,定义,:,若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。在,f,：,Z,2,Z,二元运算的定义中,本身要求满足运算是封闭的。,例：（,1,）在正整偶数的集合,E,中,对,+,运算是封闭的；在正整奇数的集合中,对,运算是封闭的,而对,+,运算不是封闭的。（,2,）在前例中,R,I,集合中,+,-,运算；,(z),的元素中,运算等均为封闭的。,2,运算及其性质,定义,:,设*是集合,S,上的二元运算,对任一,x,y,S,有,x,y,S,则称,运算在,S,上是封闭的。,定义,:,设*是集合,S,上的二元运算,对任一,x,y,S,有,x,y=y,x,则称,运算在,S,上是可交换的（或者说,在,S,上满足交换律）。,2,运算及其性质,定义,:,设*是集合,S,上的二元运算,对任一,x,y,z,S,都有,（,x,y,）,z=x,（,y,z,）,则称,运算在,S,上是可结合的（或者说*在,S,上满足结合律）。,定义,:,设,和,是集合,S,上的二个二元运算,对任一,x,y,z,S,有,x,（,y,z,）,=,（,x,y,）,（,x,z,）；,（,y,z,）,x=,（,y,x,）,（,z,x,）,则称运算,对,是可分配的（或称,对,满足分配律）。,2,运算及其性质,定义,:,设,，是定义在集合,S,上的两个可交换二元运算，如果对于任意的,x,y,S,，都有：,x(x y)=x,；,x(xy)=x,则称运算,和运算满足吸收律。,定义,:,设*是,S,上的二元运算,若对任一,x,S,有,x,x=x,则称,满足等幂律。,讨论定义：,1)S,上每一个元素均满足,x,x=x,才称,在,S,上满足幂等律；,2),若在,S,上存在元素,x,S,有,x,x=x,则称,x,为,S,上的幂等元素；,3),由此定义,若,x,是幂等元素,则有,x,x=x,和,x,n,=x,成立。,2,运算及其性质,例：（,1,）在实数集合,R,中,+,是可交换,可结合的,对,+,是满足分配律的,“0”,对,+,是等幂元素,而其它不为等幂元素,对“,-”,法是不可交换,不可结合的；,（,2,）在,(z),中,均是可交换,可结合的,对,对,均是可分配的；,(z),中任一元素,对,均是等幂元素。满足等幂律；而,(z),中,对称差分,是可交换,可结合的。除,(s),=,以外不满足等幂律。,=,而除,以外的,A,(z),有,A,AA,。,2,运算及其性质,定义,：设*是,S,上的二元运算,对任一,x,S,则：,x,1,=x,x,2,=x*x,x,n,=x,n-1,*x,定理,：设*是,S,上的二元运算,且,x,S,对任一,m,n,I,+,有 （,1,）,x,m,x,n,=x,m+n,（,2,）,(x,m,),n,=x,m,n,证明：,（,1,）,x,m,x,n,=(x,m,x)x x,=(x,m+1,x)x x,n,n-1,=.=x,m+n,（,2,）,(x,m,),n,=x,m,x,m,=x,m+m,x,m,x,m,=x,m,n,n n-1,2,运算及其性质,下面定义特异元素幺元,零元和逆元。,定义,：设*是集合,Z,中的二元运算,(1),若有一元素,e,l,Z,对任一,x,Z,有,e,l,*x=x,；则称,e,l,为,Z,中对于*的左幺元,(,左单位元素,),；,(2),若有一元素,e,r,Z,对任一,x,Z,有,x*,e,r,=x,；,则称,e,r,为,Z,中对于*的右幺元（右单元元素）。,定理,：若,e,l,和,e,r,分别是,Z,中对于*的左幺元和右幺元,则对于每一个,x,Z,，可有,e,l,=,e,r,=,e,和,e*x=x*e=x,，则称,e,为,Z,中关于运算*的幺元，且,e Z,是唯一的。,2,运算及其性质,e,l,和,e,r,分别是对*的左,右左元，,则有,e,l,*,e,r,=,e,r,=,e,l,有,e,l,=,e,r,=e,成立。（,2,）幺元,e,是唯一的。用反证法：假设有二个不同的幺元,e,1,和,e,2,则有,e,1,*e,2,=e,2,=e,1,这和假设相矛盾。,若存在幺元的话一定是唯一的。,例：,（,1,）在实数集合,R,中,对,+,而言,e,+,=0,；对,而言,e,*,=1,；,（,2,）在,(E),中,对,而言,e,=E,（全集合）；,对,而言,e,=,（空集）；,2,运算及其性质,（3）双射函数中,对“,”而言，,e,=I,x,（恒等函数）；,（4）命题逻辑中，对而言，,e,=F（永假式）；,对而言，,e,=T（永真式）。,定义：,设*是对集合Z中的二元运算，,（1）若有一元素,l,Z，,且对每一个x,Z,有,l,*x=,l,，则称,l,为Z中对于*的左零元；（2）若有一元素,r,Z，,且对每一个x,Z,有,x*,r,=,r,，,则称,r,为Z中对于*的右零元。,2,运算及其性质,定理,：,若,l,和,r,分别是,Z,中对于*的左零元和右零元，于是对所有的,x,Z,，,可有,l,=,r,=,，能使,*x=x*=,。在此情况下，,Z,是唯一的，并称,是,Z,中对*的零元。证明：方法同幺元。例：,（,1,）在实数集合,R,中，对,而言,，,L,=,r,=0,（,2,）在,(E),中，对,而言，,=,；,对,而言，,=E,；,（,3,）,命题逻辑,中，对而言，,=T,；,对而言，,=F,。,2,运算及其性质,定义,：,设*是,Z,中的二元运算，且,Z,中含幺元,e,，,令,x,Z,，（,1,）若存在一,x,l,Z,，能使,x,l,*x=,e,，则称,x,L,是,x,的左逆元,并且称,x,是左可逆的；（,2,）若存在一,x,r,Z,，能使,x*x,r,=,e,，则称,x,r,是,x,的右逆元，并且称,x,是右可逆的；（,3,）若元素,x,既是左可逆的，又是右可逆的，则称,x,是可逆的，且,x,的逆元用,x,-1,表示。,2,运算及其性质,定理,：,设,Z,是集合，并含有幺元,e,。*是定义在,Z,上的一个二元运算，并且是可结合的。若,x,Z,是可逆的，则它的左逆元等于右逆元，且逆元是唯一的。证明：,（,1,）先证左逆元,=,右逆元：,设,x,L,和,x,r,分别是,x,Z,的左逆元和右逆元，,x,是可逆的和*是可结合的（条件给出）,x,l,*x=x*x,r,=,e,x,l,*x*x,r,=,（,x,l,*x,）*,x,r,=,e,*x,r,=x,r,；,x,l,*x*x,r,=x,l,*(x*x,r,)=x,l,*,e,=x,l,x,r,=x,l,2,运算及其性质,（,2,）证明逆元是唯一的（若有的话）：,假设,x,1,-1,和,x,2,-1,均是,x,的二个不同的逆元，则,x,1,-1,=x,1,-1,*,e,=,x,1,-1,*,（,x*x,2,-1,）,=,（,x,1,-1,*x,）*,x,2,-1,=,e,*x,2,-1,=x,2,-1,，,这和假设相矛盾。,x,若存在逆元的话一定是唯一的。,推论,(x,-1,),-1,=x,e,-1,=,e,证明：,x,-1,*x=(x,-1,),-1,*,（,x,-1,）,=x*x,-1,=,e,有,(x,-1,),-1,=x,e,-1,*,e,=,e,=,e,*,e,有,e,-1,=,e,例：（,1,）在实数集合,R,中，对“,+”,运算，对任一,x,R,有,x,-1,=-x,，,x+,（,-x,）,=0,，加法幺元,2,运算及其性质,对“,”,运算，对任一,x,R,有,x,-1,=1,x,（,x,0,）,x 1,x,=1,，乘法幺元；,（,2,）在函数的合成运算中,每一个双射函数都是可逆的，,f,-1,（,f,的逆关系）；,（,3,）在所有的二元运算中,零元一定不存在逆元，,*x=x*=,。,定义,设*是,Z,集合中的二元运算，且,a,Z,和,x,y,Z,，,若对每一,x,，,y,有（,a*x=a*y,）,（,x*a=y*a,）,（,x=y,），则称,a,是可约的（或称可消去的）,2,运算及其性质,定理,设*是,Z,集合中的二元运算,且*是可结合的,若元素,a,Z,且对于*是可逆的,则,a,也是可约的。（反之不一定,即可约的不一定是可逆的。）,证明：设任一,x,，,y,Z,且有,a*x=a*y,，下面证明，在*可结合和,a,对*是可逆的条件下，,a,是可约的。,*是可结合的和,a,Z,对*是可逆的（条件给出）,a,-1,*,（,a*x,）,=,（,a,-1,*a,）*,x=e*x=x,而,a,-1,*,（,a*y,）,=,（,a,-1,*a,）*,y=e*y=y,即,x=y,。,由定义可知,a,是可约的。,2,运算及其性质,下面举例证明，若元素是可约的，但不一定是可逆的。例：,I,为整数集合，对“,”运算，运算是可结合的。任何非零元素均是可约的，但除,1,和（,-1,）以外其他元素均没有逆元。,1,-1,=1,，,(-1),-1,=(-1),。例：,Z=0,1,2,3,4,定义,Z,中二个运算为，,对任一,x,，,y,Z,有,x+,5,y=,（,x+y,）,mod 5 x,5,y=,（,x,y,）,mod 5,2,运算及其性质,e,+5,=0,0,-1,=0,1,-1,=4,2,-1,=3,3,-1,=2,4,-1,=1。,e,*5,=,1,*5,=1,1,-1,=1,2,-1,=3,3,-1,=2,4,-1,=4,0没有逆元。,以上二元运算的性质均可运用到代数系统进行讨论。,+5,0 1 2 3 4,0,1,2,3,4,0 1 2 3 4,1 2 3 4 0,2 3 4 0 1,3 4 0 1 2,4 0 1 2 3,*,5,0 1 2 3 4,0,1,2,3,4,0 0 0 0 0,0 1 2 3 4,0 2 4 1 3,0 3 1 4 2,0 4 3 2 1,3,半群,定义,：,一个代数系统,，,S,为非空集合，,是,S,上的二元运算，如果运算,是封闭的，则称代数系统,为广群。,定义,：,设,是一代数系统，,S,为非空集合，,是,S,上的二元运算，若,(1),运算是封闭的。,(2),运算满足结合律，则称,为半群。例：,均为半群,定义,：,对于*运算，拥有幺元的半群,称为含幺半群。（拟群，幺半群，独异点）。例：,均为含幺半群，,而,就不为幺半群。,3,半群,例：设,S,为非空集合，,(S),是,S,的幂集，,则,均为含幺半群。而,，其中,max(x,1,x,2,),取二者之大值；,，其中,min(x,1,x,2,),取二者之小值，均不为幺半群（不存在幺元）。,则为含幺半群，其中,e=0,定义,：,设,是一半群，,T,S,，且*在,T,上是封闭的，那么,也是半群，称,是,的子半群。,3,半群,讨论定义：,（,1,）因为*在,S,上是可结合的，而,T,S,且*在,T,上是封闭的，所以*在,T,上也是可结合的。,（,2,）由定义可知，,S,S,，,也是,的子半群（子含幺半群）。为了和其它子半群相互区别，称,是的“平凡子半群”,;,定义,设,是一个含幺半群，,T,S,，且*在,T,上是封闭的，则,也是一个含幺半群，,称,是,的子含幺半群。,3,半群,讨论定义：（,1,）在幺半群中，由于幺元,e,的存在，,保证在运算表中一定没有相同的行和列。设任一,x,1,x,2,Z,，且,x,1,x,2,，,则,e*x,1,=x,1,e,*x,2,=x,2,；（,2,）在,中若存在零元的话，上述性质继续存在。,例：半群,是,的子半群，而不是子含幺半群。*运算由运算表定义：,3,半群,*,0,1,0,0,0,1,0,1,*,0,1,0,1,0,0,0,0,1,1,0,1,由运算表可见：,中幺元为,1,，而在,中幺元为,。,定理,：,如果半群,的载体,S,为有限集，则必有,a,S,，使,a*a=a,。,3,半群,证明：因,是半群，对任意的,b,S,，,由*的封闭性，,b,*,bS,，,b,3,S,，,b,4,S,，,由于,S,是有限集，必有,ij,，使,b,i,=b,j,设：,p=j,i,，则,b,j,=b,p,*,b,i,，即：,b,i,=b,p,*,b,i,当,q,i,时，,b,q,=b,p,*,b,q,，,又因,p,1,，总可以找到,k1,，使,kpi,，对,S,中的,b,kp,有,b,kp,=b,p,*,b,kp,=b,p,*,(b,p,*,b,kp,)=b,2p,*,b,kp,=b,2p,*,(b,p,*,b,kp,)=b,3p,*,b,kp,=.=b,kp,*,b,kp,令,a=b,kp,，则,a,*,a=a,。,3,半群,定理,：,设,是独异点，对于任意,a,，,b,S,，且,a,，,b,均有逆元，则,a)(a,-1,),-1,=a,b)a,*,b,有逆元，且,(a,*,b),-1,=b,-1,*,a,-1,证明：,a),因为,a,-1,是,a,的逆元，即,a,*,a,-1,=a,-1,*,a=e,所以,(a,-1,),-1,=a,b),因为,(a,*,b),*,(b,-1,*,a,-1,)=a,*,(b,*,b,-1,),*,a,-1,=a,*,e,*,a,-1,=e,同理可证：,(b,-1,*,a,-1,),*,(a,*,b)=e,所以,(a,*,b),-1,=b,-1,*,a,-1,4,群与子群,1.,群的定义,定义,设,是一代数系统，,S,是非空集合，*为,S,上的二元运算，它满足以下四个条件时，则称,为群（,1,）*运算是封闭的；（,2,）*运算是可结合的；,（,3,）存在幺元,e,；（,4,）,S,中每一个元素均有逆元。,例：,等均为群,（其中,Z,2,=0,1,Z,3,=0,1,2,），而,只是含幺半群而不是群。,4,群与子群,例：设,M=0,60,120,240,300,180,表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对,M,中任一元素,a,b,有,a*b=,图形旋转,(a+b),的角度，并规定当旋转到,360,时即为,0,，,试验证,是一个群。,*,0,60,120,180,240,300,0,0,60,120,180,240,300,60,60,120,180,240,300,0,120,120,180,240,300,0,60,180,180,240,300,0,60,120,240,240,300,0,60,120,180,300,300,0,60,120,180,240,4,群与子群,（,1,）运算是封闭的,（,2,）*是可结合的,（,3,）幺元为,0,；,（,4,）每一个元素均有逆元：,(0,),-1,=0,(60,),-1,=300,(120,),-1,=240,(180,),-1,=180,(240,),-1,=12 0,(300,),-1,=60,是一个群。,4,群与子群,定义,设,是一个群，如果,G,是有限集合，则称,为有限群，并把,|G|,称为群的阶数，如果,G,为无限集合，则称,为无限群。,例：,为无限群，上例中,为有限群，群的阶为,|M|,=6,。,至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。,2.,群的性质,由群的定义可知,:,4,群与子群,（,1,）群具有半群和含幺半群所具有的所有性质；,（,2,）由于群中存在幺元，在群的运算表中一定没有相同的行（和列）,（,3,）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。,下面以定理形式介绍群的性质,4,群与子群,定理,1,若,是一个群，则对任一,a,b,G,有：（,1,）存在唯一的元素,x,G,，使,a*x=b,；,（,2,）存在唯一的元素,y,G,，使,y*a=b,。证明：,（,1,）（,a,）在,G,中存在,x,，使,a*x=b,成立。,a*(a,-1,*b)=(a*a,-1,)*b=e*b=b,，,至少有一,x=(a,-1,*b),满足,a*x=b,成立。（,b,）下面证明这样的,x,是唯一的。,若,x,是,G,中任一元素，且能使,a*x=b,成立，,则有,x=e,*x=,(a,-1,*a)*x=a,-1,*(a*x)=a,-1,*b,，,x=(a,-1,*b),是满足,a*x=b,的唯一元素，即,x,是唯一的。（,2,）的证明同上。,4,群与子群,定理,2,若,是一个群，则对任一,a,b,c,G,有：,（,1,）,a*b=a*c,b=c,（,a,是左可消去的）；（,2,）,b*a=c*a,b=c,（,a,是右可消去的）。,结论：在代数系统中，二元运算是可结合的，且,a,是可逆的，则,a,是可约的。此定理说明群满足消去律。,4,群与子群,定理,3,一个群,中一定不存在零元。,零元不存在逆元。,定义,：,代数系统,中，如果存在,a,G,有,a*a=a,，则称,a,为等幂元。,定义由集合和集合上的一个或多个n元运算所组成的系统称为代数系统，用符号=表示，其中S为非空集合，f1,f2fm表示n元运算。,定理设f是从代数系统U=到 V=的同态映射，,n n-1,在S上的运算是封闭的。,G=Nm,+m，其中，,当qi时，bq=bp*bq，,可满足的 谓词演算的等价式与蕴含式,定义设是由g 生成的循环群，若存在一个正整数m，使gm=e成立，则整数中最小的m 称为生成元g 的周期，若不存在这样的m，则称周期为无穷大。,3 4 1 2,证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。,c1=c,c2=b,c3=d,c4=a(幺元);,(2)R是对称的，由f(a)=f(b)可得f(b)=f(a)，,任何非零元素均是可约的，但除1和（-1）以外其他元素均没有逆元。,命题函数 复合命题函数 个体域 全总个体域,（2）对称性：设U和V同构且有对应的同构映射f，f是双射函数，f的逆是V到U的同构映射，即V和U同构；,4,群与子群,定理,4,一个群中，除了幺元,e,之外，不存在其它等幂元素。证明：若任一,a,G,，有,a*a=a,的话，,则,a=,e,。,e,=a*a,-1,=(a*a,）*,a,-1,=a*(a*a,-1,)=a*,e,=a,定义,：,设,S,是一个非空集合，从集合,S,到,S,的一个双射称为,S,的一个置换。,4,群与子群,定理5：,群的运算表中的每一行或每一列都是G的元素的一个置换。,证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。,（反证法）如果对应于元素a,G的那一行中有两个元素都是c，即有,a*b,1,=a*b,2,=c，且b,1,b,2,由可约性，得：b,1,b,2,，这与b,1,b,2,矛盾。,其次，证明G中的每一个元素都在运算表的每一行和每一列中出现。,4,群与子群,考察对应于元素,a,G,的那一行，,设,b,是,G,中的任一元素,由于,b=a*(a,-1,*b),，所以,b,必定出现在对应于,a,的那一行。,再由运算表中没有两行（或两列）是相同的，,所以，,的运算表中的每一行都是,G,的元素的一个置换，且每一行都是不相同的。,同样，对于每一列结论同样成立。,4,群与子群,3.,子群,定义,设,是一个群，且,S,G,是一个非空集合。若,满足下列三个条件，则称,是,的子群：（,1,）,e,是,的幺元，且,eS,；（保持幺元）（,2,）对任一,a,S,一定有,a,-1,S,；（保持逆元）（,3,）对任一,a,b,S,一定有,a*b,S,。（运算的封闭性）,讨论定义：（,1,）任一群,至少可找到二个子群，即,和,，为了以示区别称此二子群为平凡子群；（,2,）除了平凡子群以外的子群称为的真子群。,4,群与子群,定义,设,是群,的真子群，,若不再有一个真子群,（其中,S,T,），则称,是,的极大子群。,例：,是一个群，设,S=x,|x,是,6,的倍数,，,T=y,|y,是,3,的倍数,，则,是,的真子群。,S,T,，,不是,的极大子群。,定理,设,是一个群，,B,是,G,的非空子集，如果,B,是一个有限集，那么，只要运算*在,B,上是封闭的，则,必定是,的子群。,4,群与子群,证明：设,b,B,，已知*在,B,上封闭，则,b*b B,，即,b,2,B,，,b,2,*,b B,，即：,b,3,B,，,于是,b,，,b,2,，,b,3,均在,B,中。,由于,B,是有限集，必存在正整数,i,和,j,，,i1,，那么由,b,j-i,=b,*,b,j-i-1,可知,b,j-i-1,是,b,的逆元，,且,b,j-i-1,B,；,4,群与子群,如果,j-i=1,，那么由,b,i,=b,i,*,b,可知,b,就是幺元，且以自身为逆元。,因此，,是,的一个子群。,例：设,G,4,=p=|p,i,0,1,，是上的二元运算，定义为，对任意,X=,，,Y=G,4,，,X Y=,，,其中的运算表如图所示：,证明,是群,的子群。,0,1,0,0,1,1,1,0,4,群与子群,证明：,4,群与子群,定理,:,设,是一个群，,S,是,G,的非空子集，如果对于,S,中的任意元素,a,和,b,有,a,*,b,-1,S,，则,是,的子群。,证明：先证，,G,中的幺元,e,也是,S,中的幺元。,任取,a,S,，,a,*,a,-1,S,，而,a,*,a,-1,e,，,e,S,再证，每个元素都有逆元。,又,e,*,a,-1,S,，即,a,-1,S,。,最后说明，*对,S,是封闭的。,a,b S,，因,b,-1,S,，,(,b,-1,),-1,S,4,群与子群,a,*,b=a,*,(,b,-1,),-1,S,，而,(,b,-1,),-1,b,a,*,b,S,是,的子群,例：设,和,都是群,的子群，试证明,也是,的子群。,5,阿贝尔群和循环群,定义,如果群,中运算*是可交换的，,则称该群为阿贝尔群（或称为交换群）。,例：,为阿贝尔群。,例：离散函数代数系统,是阿贝尔群。,Z=1,2,3,4,，,F=,f,0,f,1,f,2,f,3,1 2 3 4,2 3 4 1,f,2,=,1 2 3 4,3 4 1 2,f,3,=,1 2 3 4,4 1 2 3,f,0,=,1 2 3 4,1 2 3 4,f,=,5,阿贝尔群和循环群,由运算表可见：,（,1,）运算是封闭的；,（,2,）“,”,可结合；,（,3,）幺元,f,0,；,（,4,）每一个元素均可逆,;,（,5,）以主对角线为对称。,为阿贝尔群。,f,0,f,1,f,2,f,3,f,0,f,0,f,1,f,2,f,3,f,1,f,1,f,2,f,3,f,0,f,2,f,2,f,3,f,0,f,1,f,3,f,3,f,0,f,1,f,2,5,阿贝尔群和循环群,定理,设,是一个群，,是阿贝尔群的充分必要条件是对任一,a,b,G,有,(a*b)*(a*b)=(a*a)*(b*b),。,证明：,（,1,）充分性：,(a*b)*(a*b)=(a*a)*(b*b),是阿贝尔群。对任一,a,b,G,有,(a*b)*(a*b)=(a*a)*(b*b),成立，,*是可结合的，且是可消去的，,a*(a*b)*b=(a*a)*(b*b)=(a*b)*(a*b)=a*(b*a)*b,得,a*b=b*a,，,是阿贝尔群。,5,阿贝尔群和循环群,（,2,）必要性：,是阿贝尔群,(a,*,b),*,(a,*,b)=(a,*,a),*,(b,*,b),。阿贝尔群满足交换律，对任一,a,b,G,有,a*b=b*a,，,(a,*,a),*,(b,*,b)=a,*,(a,*,b),*,b=a,*,(b,*,a),*,b=(a,*,b),*,(a,*,b),。,推论,在阿贝尔群中，对任一,a,b,G,有,(a,*,b),1,=b,-1,*,a,-1,=a,-1,*,b,-1,5,阿贝尔群和循环群,定义,设,是一个群，,I,是整数集合，若存在一个元素,g,G,，对于,G,中每一个元素,a,都能表示成,g,n,的形式,（,n,I,），则称,是一个循环群，,g,称为群,的生成元。例：,60,就是群,的生成元，所以该群为循环群。,定义,设,是由,g,生成的循环群，若存在一个正整数,m,，使,g,m,=,e,成立，则整数中最小的,m,称为生成元,g,的周期，若不存在这样的,m,，则称周期为无穷大。,5,阿贝尔群和循环群,例：（,1,）,是一个群，生成元,g=1,，而,g,的周期为无穷大；（,2,）,I,为整数集合。“模,m,同余”是一个等价关系。,设：,m=4,，,N,4,表示“模,4,同余”所产生的等价类的集合，,N,4,=0,1,2,3,，定义运,+,4,：,i+,4,j=(i+j)(mod 4),(i,j=0,1,2,3),则：,是群,+,4,0,1,2,3,0,0,1,2,3,1,1,2,3,0,2,2,3,0,1,3,3,0,1,2,运算表：,5,阿贝尔群和循环群,由运算表可见：,（,1,）由,0,可生成,（,2,）由,1,或,3,可生成,（,3,）由,2,可生成,讨论定义：（,1,）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；,5,阿贝尔群和循环群,（,2,）在循环群中，生成元的周期是指,g,m,=,e,中最小的,m,（这里,m,0,且,m,I,+,）。,定理,每一个循环群必然是阿贝尔群。证明：设,是一循环群，,g,为生成元，,对任一,p,q,G,一定存在,i,j,I,（整数）使得,p=g,i,q=g,j,，,则,p*q=g,i,*g,j,=g,i+j,=g,j,*g,i,=q*p,。,循环群一定是阿贝尔群。,5,阿贝尔群和循环群,定理,设,是由元素,g,G,生成的循环群，若,是,n,阶的（即,|G|=n,），则,g,n,=e,，以致,G=g,1,g,2,g,n,=e,，而且,n,是能使,g,n,=,e,的最小正整数。,证明：,5,阿贝尔群和循环群,定理,设,是由元素,g,G,生成的循环群，若,是,n,阶的（即,|G|=n,），则,g,n,=e,，以致,G=g,1,g,2,g,n,=e,，而且,n,是能使,g,n,=,e,的最小正整数。,证明：,5,阿贝尔群和循环群,例：,为一群,G,中元素和*运算见运算表：,c,1,=c,c,2,=b,c,3,=d,c,4,=a(,幺元,);,d,1,=d,d,2,=b,d,3,=c,d,4,=a(,幺元,);,而,a,1,=a,a,2,=a,a,3,=a,a,4,=a;,b,1,=b,b,2,=a,b,3,=b,b,4,=a,由上可见：生成元,c,d,的阶为,4,，等于群,的阶，即,|G|,的基数。,*,a,b,c,d,a,a,b,c,d,b,b,a,d,c,c,c,d,b,a,d,d,c,a,b,5,阿贝尔群和循环群,定理,设,是由元素,g,G,生成的循环群，若,是,n,阶的（即,|G|=n,），则,g,n,=e,，以致,G=g,1,g,2,g,n,=e,，而且,n,是能使,g,n,=,e,的最小正整数。,证明：,5,阿贝尔群和循环群,例：,为一群,G,中元素和*运算见运算表：,c,1,=c,c,2,=b,c,3,=d,c,4,=a(,幺元,);,d,1,=d,d,2,=b,d,3,=c,d,4,=a(,幺元,);,而,a,1,=a,a,2,=a,a,3,=a,a,4,=a;,b,1,=b,b,2,=a,b,3,=b,b,4,=a,由上可见：生成元,c,d,的阶为,4,，等于群,的阶，即,|G|,的基数。,*,a,b,c,d,a,a,b,c,d,b,b,a,d,c,c,c,d,b,a,d,d,c,a,b,期中复习,1,）命题及其表示法,命题 真值 原子命题 复合命题 命题标识符 命题常量,命题变元 原子变元,2,）联结词,否定 合取 析取 条件 双条件,3,）命题公式与翻译,合式公式 翻译 优先级,4,）真值表与等价公式,真值表 逻辑等价 子公式 定理,期中复习,5,）重言式与蕴含式,重言式（永真式）矛盾式（永假式）蕴含式,定理,1-5.1,定理,1-5.2,定理,1-5.3,定理,7,）范式,合取范式 析取范式 主合取范式 主析取范式,定理,1-7.3,定理,8,）推理理论,有效结论,P,规则,T,规则,CP,规则,等价公式表 蕴含公式表,期中复习,第二章谓词逻辑,1,）谓词的概念与表示,谓词 谓词填式,n,元谓词,2,）命题函数与量词,命题函数 复合命题函数 个体域 全总个体域,全称量词 存在量词 特性谓词,3,）谓词公式与翻译,合式公式,4,）变元的约束,辖域 约束变元 自由变元 换名 代入,期中复习,5,）谓词演算的等价式与蕴含式,赋值 等价 有效的（永真的）不可满足的（永假的）,可满足的 谓词演算的等价式与蕴含式,6,）前束范式,前束范式 定理,7,）谓词演算的推理理论,US UG ES EG,规则,期中复习,第一、二章作业选讲,期中复习,第三章集合与关系,1,）集合的概念和表示法,集合 元素 子集 真子集 空集 全集 幂集,外延性原理 定理,3-1.1,定理,3-1.2,定理,2,）集合的运算,交 并 补 绝对补 对称差,集合运算的性质,4,）序偶与笛卡尔积,序偶 三元组,n,元组 笛卡尔积,5,）关系及其表示,期中复习,关系 前域 值域 恒等关系 全域关系 空关系,关系矩阵 关系图,6,）关系的性质,自反 对称 传递 反自反 反对称,7,）复合关系和逆关系,复合关系 逆关系,定理,8,）关系的闭包运算,闭包,定理定理,期中复习,9,）集合的划分和覆盖,划分 覆盖,10,）等价关系与等价类,等价关系 等价类 商集,定理定理,12,）序关系,偏序集 盖住关系 盖住集和哈斯图,极大元 极小元 最大元 最小元,上界 下界 最小上界 最大下界,全序 良序 拟序,期中复习,第四章函数,1,）函数的概念,函数 定义域 值域 函数相等 函数集合,满射 入射 双射,2,）逆函数和复合函数,逆函数 左复合,恒等函数 常函数 函数复合的结合性,定理定理,期中复习,第三、四章作业选讲,G=Nm,+m，其中，,G=Nm,+m，其中，,1-1=1，(-1)-1=(-1)。,（1）由0可生成,由运算表可见：中幺元为1，而在中幺元为。,循环群一定是阿贝尔群。,只满足R是等价关系，而不去证明对于运算满足代换性质不能说它就是同余关系，,对而言，e =T（永真式）。,讨论定义：（1）因为*在S上是可结合的，而TS且*在T上是封闭的，所以*在T上也是可结合的。,（4）一个代数系统到另一个代数系统可能存在多于一个同态。,为阿贝尔群。,和是二个同构的代数系统。,则a=e。,为了和其它子半群相互区别，称是的“平凡子半群”;,令x Z，（1）若存在一xlZ，能使xl*x=e，则称xL是x的左逆元,并且称x是左可逆的；,6,同态与同构,1.,代数系统的概念,：,定义,由集合和集合上的一个或多个,n,元运算所组成的系统称为代数系统，用符号,=,表示，其中,S,为非空集合，,f,1,f,2,f,m,表示,n,元运算。讨论定义：,（,1,）构成一个代数系统必须具备三个条件：,一个非空集合,S,，称为载体；,在,S,上的运算,f,1,f,2,f,m,；,在,S,上的运算是封闭的。（,2,）有些书上把特异元素（常数）放在代数系统之中，形成,；,6,同态与同构,2.,同态和同构,同态和同构是讨论二个代数系统之间的关系。,定义,设,U=,和,V=,是二个代数系统，又设,U,到,V,存在一个映射,f,:A,B,，对任一,a,1,a,2,A,，若有,f,(a,1,a,2,)=,f,(a,1,)*,f,(a,2,),，则称,f,是从代数系统,U,到,V,的同态映射。称,U,同态于,V,。把,称为,的一个同态象。其中：,f(A)=x|x=f(a),，,aAB,讨论定义：,6,同态与同构,（,1,）,f,:A,B,为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；,（,2,）对同态讲，二个代数系统的基数可以不相等，只要满足函数的条件就行；（,3,）上述定义可以推广到多个,n,元运算的同一类型的代数系统中去。,（,4,）一个代数系统到另一个代数系统可能存在多于一个同态。,6,同态与同构,例：,给定二代数系统,F=I,+,，,I,为整数，“,+”,为一般加；,G=N,m,+,m,，其中，,N,m,=0,1,2m-1,“+,m,”,为模,m,加法并定义成,x,1,+,m,x,2,=(x,1,+x,2,)mod m,。,对任一,i,I,和,m,I,+,，,(i)mod m,定义了除以,m,所得之非负余数,且,0,(i)mod m m,。,6,同态与同构,定义,F,G,的一个函数：,f :I,N,m,且有,f(i)=i(mod m),，,(,其中,i,I,，,f(i),N,m,),f(i,1,+i,2,)=(i,1,+i,2,),mod m=(i,1,mod m)+,m,(i,2,mod m),，其中,i,1,I,i,2,I,；,i,1,mod m,N,m,i,2,mod m,N,m,。,则,f,是一同态函数：自变量和象点的对应，并保持运算的对应。,6,同态与同构,定义,若,f,:A,B,是从,U=,到,V=,的同态，于是有：（,1,）若,f,是满射函数，则称,f,是从,U,到,V,的满同态；（,2,）若,f,是入射函数，则称,f,是从,U,到,V,的单一同态；（,3,）若,f,是双射函数，则称,f,是从,U,到,V,的同构。,定义,设,V,是一个代数系统，如果,f,是由,V,到,V,的同态，则称,f,为自同态。如果,g,是,V,到,V,的同构，则称,g,为自同构。,6,同态与同构,f =,1 2 3 4,2 3 4 1,f,0,f,1,f,2,f,3,f,0,f,0,f,1,f,2,f,3,f,1,f,1,f,2,f,3,f,0,f,2,f,2,f,3,f,0,f,1,f,3,f,3,f,0,f,1,f,2,+,4,0,1,2,3,0,0,1,2,3,1,1,2,3,0,2,2,3,0,1,3,3,0,1,2,例：离散函数代数系统和剩余类加代数系统是同构的。,6,同态与同构,定义一函数,h:F,N,4,，,h(,f,i,)=i,，其中,i,0,1,2,3,，,元素一一对应；,h(,f,i,f,j,)=h(,f,i,)+,4,h(,f,j,)=i+,4,j,，,运算是一一对应的；,和,是二个同构的代数系统。,在实际中，把对应的元素和运算进行交换，就能得到相同的运算表。,例：试考定下列二代数系统,U,和,V,是否同构：,U=,，,V=,其运算表如下：,6,同态与同构,S,S,E,A,A,A,A,E,A,A,E,A,A,E,A,A,A,E,E,A,A,E,A,E,E,E,E,E,E,A,A,E,A,A,A,A,A,A,E,A,A,E,6,同态与同构,X,1,10,2,5,5,2,10,1,X,1,2,5,10,1,1,2,5,10,2,2,2,10,10,5,5,10,5,10,10,10,10,10,10,1,2,5,