离散数学左孝陵第五章名师优质课获奖市赛课一等奖课件.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,，,令xZ,，（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,ba,*,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页,6 同态与同构,对任,一,a,b,1,2,5,10有,f,(,)=,f,(,a,),a,f,(a,b)=,f,(,a,),f,(,b,),f,(a,b)=,f,(,a,),f,(,b,),运算一一对应。,f,是一双射函数，U和V 二个代数系统同构。,若二个代数系统同构，则此二个代数系统含有完全相同性质,所以对于同构代数系统,只要研究其中一个代数系统,其它代数系统问题也就处理了,给我们研究问题带来了方便。,第81页,6 同态与同构,定理,代数系统中同构关系是一个等价关系。,证：（1）自反性：因为任何一个代数系统能够经过恒等映射与它本身同构；,（2）对称性：设U和V同构且有对应同构映射f，f是双射函数，f逆是V到U同构映射，即V和U同构；,（3）传递性：设f是U到V同构映射，g是V到W同构映射，因为f和g是双射函数，f,g是U到W同构映射。即U和W同构。,所以，同构关系是等价关系。,第82页,6 同态与同构,定理,设f是从代数系统U=,到 V=同态映射，,（1）假如U是半群，那么在f作用下，同态象也是半群；,（2）假如U是独异点，那么在f作用下，同态象也是独异点；,（3）假如U是群，那么在f作用下，同态象也是群；,第83页,6 同态与同构,证实：,第84页,6 同态与同构,3.同余关系：,这是讨论同一代数系统中关系。同余关系是代数系统集合中等价关系，在运算作用下，能保持运算等价类，同余关系是相等关系推广。在介绍同余关系之前先看一个例子。,例：设是一代数系统,其中F是全部分数集合,+,-,为普通加,减,乘法。则在F中,可把相等分数作为元素集合是F子集:,1/2=,-2/-4,-1/-2,1/2,2/4,3/6,1/3=,-2/-6,-1/-3,1/3,2/6,.。,若对二个等价类中元素进行+,运算，则运算结果必定属于同一等价类中。,第85页,6 同态与同构,如：,1/2+1/3=(1/2+2/6)=(2/4+1/3),5/6;,1/2 1/3=(1/2 2/6)=(2/4 1/3)1/6;,1/2,1/3=(1/2 2/6)=(2/4 1/3),1/6 。,在F中，,二个等价类元素对,+,-,运算均满足代换性质，即分数集合相等关系，对,+,-,运算满足代换性质。,第86页,6 同态与同构,定义,设代数系统 U=,*是二元运算，R是Z中等价关系，当且仅当对任一x,1,x,2,Z y,1,y,2,Z有,x,1,R x,2,y,1,Ry,2,x,1,*y,1,R,x,2,*,y,2,时，则对于运算*，等价关系R满足代换性质（置换性质）。,定义,设,U=,是一代数系统，,R,是Z中等价关系，于是对于二元运算*，若等价关系,R,满足代换性质，则称,R,是代数系统U中同余关系，与此相对应，,R,等价类称为同余类。,第87页,6 同态与同构,例：在整数I集合中 是一个同余关系，,为一代数系统，对任一,定义,*,运算：,*,(i)=(i,2,)mod m,(m,I,+,),定义R关系：,设R是I中一个关系，当i,1,mod m=i,2,mod m时，,则有i,1,R i,2,下面证实(i,2,)mod m是一个同余关系证实：,（1）前面已证实：在I中，i(i,I),模 m 等价是一