离散数学左孝陵PPT参考课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,代数系统,本篇用代数方法来研究数学结构,故又叫代数结构,它将用抽象的方法来研究集合上的关系和运算。,代数的概念和方法已经渗透到计算机科学的许多分支中,它对程序理论,数据结构,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。,本篇讨论一些典型的代数系统及其性质（包括格）。,1,代数系统,第五章代 数 结 构,1,代数系统的引入,2,运算及其性质,3,半群,4,群与子群,5,阿贝尔群和循环群,6*,陪集与拉格朗日定理,7,同态与同构,2,1,代数系统的引入,定义,:,设,Z,是一个集合,f,是一个函数,f,：,Z,n,Z,则称,f,为,Z,中的,n,元运算,整数,n,称为运算的阶（元,次）。若,n=1,则称,f,：,Z,Z,为一元运算；,若,n=2,则,f,：,Z,2,Z,为二元运算。,本章主要讨论一元运算和二元运算。例：（,1,）在整数,I,和实数,R,中,+,-,均为二元运算,而对,而言就不是二元运算,（,2,）在集合,Z,的幂集,(z),中,均为二元运算,而“,”,是一元运算；,3,1,代数系统的引入,（,3,）,命题公式,中,均为二元运算,而,“,”,为一元运算,（,4,）,双射函数,中,函数的合成运算是二元运算；,二元运算常用符号：,+,等等。,定义,:,一个非空集合,A,连同若干个定义在该集合上的运算,f,1,f,2,.,f,k,所组成的系统就称为一个代数系统，,记作,。,4,1,代数系统的引入,定义,:,若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。在,f,：,Z,2,Z,二元运算的定义中,本身要求满足运算是封闭的。,例：（,1,）在正整偶数的集合,E,中,对,+,运算是封闭的；在正整奇数的集合中,对,运算是封闭的,而对,+,运算不是封闭的。（,2,）在前例中,R,I,集合中,+,-,运算；,(z),的元素中,运算等均为封闭的。,5,2,运算及其性质,定义,:,设*是集合,S,上的二元运算,对任一,x,y,S,有,x,y,S,则称,运算在,S,上是封闭的。,定义,:,设*是集合,S,上的二元运算,对任一,x,y,S,有,x,y=y,x,则称,运算在,S,上是可交换的（或者说,在,S,上满足交换律）。,6,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,）,则称运算,对,是可分配的（或称,对,满足分配律）。,7,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,成立。,8,2,运算及其性质,例：（,1,）在实数集合,R,中,+,是可交换,可结合的,对,+,是满足分配律的,“0”,对,+,是等幂元素,而其它不为等幂元素,对“,-”,法是不可交换,不可结合的；,（,2,）在,(z),中,均是可交换,可结合的,对,对,均是可分配的；,(z),中任一元素,对,均是等幂元素。满足等幂律；而,(z),中,对称差分,是可交换,可结合的。除,(s),=,以外不满足等幂律。,=,而除,以外的,A,(z),有,A,AA,。,9,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,10,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,是唯一的。,11,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,=,（空集）；,12,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,中对于*的右零元。,13,2,运算及其性质,定理,：,若,l,和,r,分别是,Z,中对于*的左零元和右零元，于是对所有的,x,Z,，,可有,l,=,r,=,，能使,*x=x*=,。在此情况下，,Z,是唯一的，并称,是,Z,中对*的零元。证明：方法同幺元。例：,（,1,）在实数集合,R,中，对,而言,，,L,=,r,=0,（,2,）在,(E),中，对,而言，,=,；,对,而言，,=E,；,（,3,）,命题逻辑,中，对而言，,=T,；,对而言，,=F,。,14,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,表示。,15,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,16,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,，加法幺元,17,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,是可约的（或称可消去的）,18,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,是可约的。,19,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,20,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,21,3,半群,定义,：,一个代数系统,，,S,为非空集合，,是,S,上的二元运算，如果运算,是封闭的，则称代数系统,为广群。,定义,：,设,是一代数系统，,S,为非空集合，,是,S,上的二元运算，若,(1),运算是封闭的。,(2),运算满足结合律，则称,为半群。例：,均为半群,定义,：,对于*运算，拥有幺元的半群,称为含幺半群。（拟群，幺半群，独异点）。例：,均为含幺半群，,而,就不为幺半群。,22,3,半群,例：设,S,为非空集合，,(S),是,S,的幂集，,则,均为含幺半群。而,，其中,max(x,1,x,2,),取二者之大值；,，其中,min(x,1,x,2,),取二者之小值，均不为幺半群（不存在幺元）。,则为含幺半群，其中,e=0,定义,：,设,是一半群，,T,S,，且*在,T,上是封闭的，那么,也是半群，称,是,的子半群。,23,3,半群,讨论定义：,（,1,）因为*在,S,上是可结合的，而,T,S,且*在,T,上是封闭的，所以*在,T,上也是可结合的。,（,2,）由定义可知，,S,S,，,也是,的子半群（子含幺半群）。为了和其它子半群相互区别，称,是的“平凡子半群”,;,定义,设,是一个含幺半群，,T,S,，且*在,T,上是封闭的，则,也是一个含幺半群，,称,是,的子含幺半群。,24,3,半群,讨论定义：（,1,）在幺半群中，由于幺元,e,的存在，,保证在运算表中一定没有相同的行和列。设任一,x,1,x,2,Z,，且,x,1,x,2,，,则,e*x,1,=x,1,e,*x,2,=x,2,；（,2,）在,中若存在零元的话，上述性质继续存在。,例：半群,是,的子半群，而不是子含幺半群。*运算由运算表定义：,25,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,。,26,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,。,27,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,28,4,群与子群,1.,群的定义,定义,设,是一代数系统，,S,是非空集合，*为,S,上的二元运算，它满足以下四个条件时，则称,为群（,1,）*运算是封闭的；（,2,）*运算是可结合的；,（,3,）存在幺元,e,；（,4,）,S,中每一个元素均有逆元。,例：,等均为群,（其中,Z,2,=0,1,Z,3,=0,1,2,），而,只是含幺半群而不是群。,29,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,30,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,是一个群。,31,4,群与子群,定义,设,是一个群，如果,G,是有限集合，则称,为有限群，并把,|G|,称为群的阶数，如果,G,为无限集合，则称,为无限群。,例：,为无限群，上例中,为有限群，群的阶为,|M|,=6,。,至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。,2.,群的性质,由群的定义可知,:,32,4,群与子群,（,1,）群具有半群和含幺半群所具有的所有性质；,（,2,）由于群中存在幺元，在群的运算表中一定没有相同的行（和列）,（,3,）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。,下面以定理形式介绍群的性质,33,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,）的证明同上。,34,4,群与子群,定理,2,若,是一个群，则对任一,a,b,c,G,有：,（,1,）,a*b=a*c,b=c,（,a,是左可消去的）；（,2,）,b*a=c*a,b=c,（,a,是右可消去的）。,结论：在代数系统中，二元运算是可结合的，且,a,是可逆的，则,a,是可约的。此定理说明群满足消去律。,35,4,群与子群,定理,3,一个群,中一定不存在零元。,零元不存在逆元。,定义,：,代数系统,中，如果存在,a,G,有,a*a=a,，则称,a,为等幂元。,36,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,的一个置换。,37,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,中的每一个元素都在运算表的每一行和每一列中出现。,38,4,群与子群,考察对应于元素,a,G,的那一行，,设,b,是,G,中的任一元素,由于,b=a*(a,-1,*b),，所以,b,必定出现在对应于,a,的那一行。,再由运算表中没有两行（或两列）是相同的，,所以，,的运算表中的每一行都是,G,的元素的一个置换，且每一行都是不相同的。,同样，对于每一列结论同样成立。,39,4,群与子群,3.,子群,定义,设,是一个群，且,S,G,是一个非空集合。若,满足下列三个条件，则称,是,的子群：（,1,）,e,是,的幺元，且,eS,；（保持幺元）（,2,）对任一,a,S,一定有,a,-1,S,；（保持逆元）（,3,）对任一,a,b,S,一定有,a*b,S,。（运算的封闭性）,讨论定义：（,1,）任一群,至少可找到二个子群，即,和,，为了以示区别称此二子群为平凡子群；（,2,）除了平凡子群以外的子群称为的真子群。,40,4,群与子群,定义,设,是群,的真子群，,若不再有一个真子群,（其中,S,T,），则称,是,的极大子群。,例：,是一个群，设,S=x,|x,是,6,的倍数,，,T=y,|y,是,3,的倍数,，则,是,的真子群。,S,T,，,不是,的极大子群。,定理,设,是一个群，,B,是,G,的非空子集，如果,B,是一个有限集，那么，只要运算*在,B,上是封闭的，则,必定是,的子群。,41,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,；,42,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,43,4,群与子群,证明：,44,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,45,4,群与子群,a,*,b=a,*,(,b,-1,),-1,S,，而,(,b,-1,),-1,b,a,*,b,S,是,的子群,例：设,和,都是群,的子群，试证明,也是,的子群。,46,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,=,47,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,48,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,，,是阿贝尔群。,49,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,50,5,阿贝尔群和循环群,定义,设,是一个群，,I,是整数集合，若存在一个元素,g,G,，对于,G,中每一个元素,a,都能表示成,g,n,的形式,（,n,I,），则称,是一个循环群，,g,称为群,的生成元。例：,60,就是群,的生成元，所以该群为循环群。,定义,设,是由,g,生成的循环群，若存在一个正整数,m,，使,g,m,=,e,成立，则整数中最小的,m,称为生成元,g,的周期，若不存在这样的,m,，则称周期为无穷大。,51,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,运算表：,52,5,阿贝尔群和循环群,由运算表可见：,（,1,）由,0,可生成,（,2,）由,1,或,3,可生成,（,3,）由,2,可生成,讨论定义：（,1,）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；,53,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,。,循环群一定是阿贝尔群。,54,5,阿贝尔群和循环群,定理,设,是由元素,g,G,生成的循环群，若,是,n,阶的（即,|G|=n,），则,g,n,=e,，以致,G=g,1,g,2,g,n,=e,，而且,n,是能使,g,n,=,e,的最小正整数。,证明：,55,5,阿贝尔群和循环群,定理,设,是由元素,g,G,生成的循环群，若,是,n,阶的（即,|G|=n,），则,g,n,=e,，以致,G=g,1,g,2,g,n,=e,，而且,n,是能使,g,n,=,e,的最小正整数。,证明：,56,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,57,5,阿贝尔群和循环群,定理,设,是由元素,g,G,生成的循环群，若,是,n,阶的（即,|G|=n,），则,g,n,=e,，以致,G=g,1,g,2,g,n,=e,，而且,n,是能使,g,n,=,e,的最小正整数。,证明：,58,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,59,期中复习,1,）命题及其表示法,命题 真值 原子命题 复合命题 命题标识符 命题常量,命题变元 原子变元,2,）联结词,否定 合取 析取 条件 双条件,3,）命题公式与翻译,合式公式 翻译 优先级,4,）真值表与等价公式,真值表 逻辑等价 子公式 定理,1-4.1,60,期中复习,5,）重言式与蕴含式,重言式（永真式）矛盾式（永假式）蕴含式,定理,1-5.1,定理,1-5.2,定理,1-5.3,定理,1-5.4,7,）范式,合取范式 析取范式 主合取范式 主析取范式,定理,1-7.3,定理,1-7.4,8,）推理理论,有效结论,P,规则,T,规则,CP,规则,等价公式表 蕴含公式表,61,期中复习,第二章谓词逻辑,1,）谓词的概念与表示,谓词 谓词填式,n,元谓词,2,）命题函数与量词,命题函数 复合命题函数 个体域 全总个体域,全称量词 存在量词 特性谓词,3,）谓词公式与翻译,合式公式,4,）变元的约束,辖域 约束变元 自由变元 换名 代入,62,期中复习,5,）谓词演算的等价式与蕴含式,赋值 等价 有效的（永真的）不可满足的（永假的）,可满足的 谓词演算的等价式与蕴含式,6,）前束范式,前束范式 定理,2-6.1,7,）谓词演算的推理理论,US UG ES EG,规则,63,期中复习,第一、二章作业选讲,64,期中复习,第三章集合与关系,1,）集合的概念和表示法,集合 元素 子集 真子集 空集 全集 幂集,外延性原理 定理,3-1.1,定理,3-1.2,定理,3-1.3,2,）集合的运算,交 并 补 绝对补 对称差,集合运算的性质,4,）序偶与笛卡尔积,序偶 三元组,n,元组 笛卡尔积,5,）关系及其表示,65,期中复习,关系 前域 值域 恒等关系 全域关系 空关系,关系矩阵 关系图,6,）关系的性质,自反 对称 传递 反自反 反对称,7,）复合关系和逆关系,复合关系 逆关系,定理,3-7.2,8,）关系的闭包运算,闭包,定理,3-8.1-,定理,3-8.5,66,期中复习,9,）集合的划分和覆盖,划分 覆盖,10,）等价关系与等价类,等价关系 等价类 商集,定理,3-10.1-,定理,3-10.4,12,）序关系,偏序集 盖住关系 盖住集和哈斯图,极大元 极小元 最大元 最小元,上界 下界 最小上界 最大下界,全序 良序 拟序,67,期中复习,第四章函数,1,）函数的概念,函数 定义域 值域 函数相等 函数集合,满射 入射 双射,2,）逆函数和复合函数,逆函数 左复合,恒等函数 常函数 函数复合的结合性,定理,4-2.1-,定理,4-2.7,68,期中复习,第三、四章作业选讲,69,6,同态与同构,1.,代数系统的概念,：,定义,由集合和集合上的一个或多个,n,元运算所组成的系统称为代数系统，用符号,=,表示，其中,S,为非空集合，,f,1,f,2,f,m,表示,n,元运算。讨论定义：,（,1,）构成一个代数系统必须具备三个条件：,一个非空集合,S,，称为载体；,在,S,上的运算,f,1,f,2,f,m,；,在,S,上的运算是封闭的。（,2,）有些书上把特异元素（常数）放在代数系统之中，形成,；,70,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,讨论定义：,71,6,同态与同构,（,1,）,f,:A,B,为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；,（,2,）对同态讲，二个代数系统的基数可以不相等，只要满足函数的条件就行；（,3,）上述定义可以推广到多个,n,元运算的同一类型的代数系统中去。,（,4,）一个代数系统到另一个代数系统可能存在多于一个同态。,72,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,。,73,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,是一同态函数：自变量和象点的对应，并保持运算的对应。,74,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,为自同构。,75,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,例：离散函数代数系统和剩余类加代数系统是同构的。,76,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=,其运算表如下：,77,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,78,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,10,1,1,1,1,1,2,1,2,1,2,5,1,1,5,5,10,1,2,5,10,79,6,同态与同构,定义,V,中：,：求二数的最小公倍数；,：求二数的最大公约数；“,”,：,10,被,x,除所得之商。,由运算表可见：,定义一函数,f:,1,2,5,10,A,A,E,f,(1)=,，,f,(2)=A,，,f,(5)=A,，,f,(10)=E,元素一一对应；,x,80,