代数结构.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 代数(dish)结构,第一页，共95页。,代数(dish)系统,第五章代 数 结 构,1代数(dish)系统的引入,2运算及其性质,3半群,4群与子群,5阿贝尔群和循环群,6*陪集与拉格朗日定理(dngl),7同态与同构,第二页，共95页。,1代数(dish)系统的引入,定义:设Z是一个集合(jh),f是一个函数,f：ZnZ,则称f为Z中的n元运算,整数n称为运算的阶（元,次）。若n=1,则称f：ZZ为一元运算；,若n=2,则f：Z2Z为二元运算。,本章主要讨论一元运算和二元运算。例：（1）在整数I和实数R中,+,-,均为二元运算,而对而言就不是二元运算,（2）在集合(jh)Z的幂集(z)中,均为二元运算,而“”是一元运算；,第三页，共95页。,1代数(dish)系统的引入,（3）命题公式中,均为二元运算,而“”为一元运算,（4）双射函数中,函数的合成运算是二元运算；,二元运算常用符号：+,等等。,定义(dngy):一个非空集合A连同若干个定义(dngy)在该集合上的运算f1,f2,.,fk所组成的系统就称为一个代数系统，,记作。,第四页，共95页。,1代数(dish)系统的引入,定义:若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。在f：Z2Z二元运算的定义中,本身(bnshn)要求满足运算是封闭的。,例：（1）在正整偶数的集合E中,对,+运算是封闭的；在正整奇数的集合中,对运算是封闭的,而对+运算不是封闭的。（2）在前例中,R,I集合中+,-,运算；(z)的元素中,运算等均为封闭的。,第五页，共95页。,2运算(yn sun)及其性质,定义:设*是集合S上的二元运算,对任一x,yS有xyS则称运算在S上是封闭的。,定义:设*是集合S上的二元运算,对任一x,yS有xy=y x,则称运算在S上是可交换(jiohun)的（或者说在S上满足交换(jiohun)律）。,第六页，共95页。,2运算(yn sun)及其性质,定义:设*是集合S上的二元运算(yn sun),对任一x,y,z S都有,（x y）z=x （y z）,则称运算(yn sun)在S上是可结合的（或者说*在S上满足结合律）。,定义:设和是集合S上的二个二元运算(yn sun),对任一x,y,z S有,x （y z）=（x y）（x z）；,（y z）x=（y x）（z x）,则称运算(yn sun)对是可分配的（或称对满足分配律）。,第七页，共95页。,2运算(yn sun)及其性质,定义:设，是定义在集合S上的两个可交换二元运算，如果对于任意的x,yS，都有：,x(x y)=x；x(xy)=x,则称运算和运算满足吸收律。,定义:设*是S上的二元运算,若对任一,x S有x x=x,则称满足等幂律。,讨论(toln)定义：,1)S上每一个元素均满足xx=x,才称在S上满足幂等律；,2)若在S上存在元素xS有x x=x,则称x为S上的幂等元素；,3)由此定义,若x是幂等元素,则有x x=x和xn=x成立。,第八页，共95页。,2运算(yn sun)及其性质,例：（1）在实数集合R中,+,是可交换,可结合的,对+是满足分配律的,“0”对+是等幂元素,而其它(qt)不为等幂元素,对“-”法是不可交换,不可结合的；,（2）在(z)中,均是可交换,可结合的,对,对均是可分配的；(z)中任一元素,对,均是等幂元素。满足等幂律；而(z)中,对称差分是可交换,可结合的。除(s)=以外不满足等幂律。=,而除以外的A(z)有A AA。,第九页，共95页。,2运算(yn sun)及其性质,定义：设*是S上的二元运算(yn sun),对任一xS,则：x1=x,x2=x*x,xn=xn-1*x,定理：设*是S上的二元运算(yn sun),且x S,对任一m,n I+有 （1）xmxn=xm+n （2）(xm)n=xmn证明：,（1）xmxn=(xm x)x x=(xm+1 x)x x n n-1,=.=xm+n,（2）(xm)n=xm xm=xm+m xm xm=xmn,n n-1,第十页，共95页。,2运算(yn sun)及其性质,下面定义特异(ty)元素幺元,零元和逆元。,定义：设*是集合Z中的二元运算,(1)若有一元素el Z,对任一x Z有el*x=x；则称el为Z中对于*的左幺元(左单位元素)；(2)若有一元素er Z,对任一x Z有x*er=x；则称er为Z中对于*的右幺元（右单元元素）。,定理：若el和er分别是Z中对于*的左幺元和右幺元,则对于每一个x Z，可有el=er=e和e*x=x*e=x，则称e为Z中关于运算*的幺元，且e Z是唯一的。,第十一页，共95页。,2运算(yn sun)及其性质,el和er分别是对*的左,右左元，,则有el*er=er=el,有el=er=e成立。（2）幺元e是唯一的。用反证法：假设(jish)有二个不同的幺元e1和e2,则有e1*e2=e2=e1,这和假设(jish)相矛盾。,若存在幺元的话一定是唯一的。,例：,（1）在实数集合R中,对+而言,e+=0；对而言,e*=1；,（2）在(E)中,对而言,e =E（全集合）；,对而言,e =（空集）；,第十二页，共95页。,2运算(yn sun)及其性质,（3）双射函数(hnsh)中,对“”而言，,e =Ix（恒等函数(hnsh)）；,（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中对于*的右零元。,第十三页，共95页。,2运算(yn sun)及其性质,定理：若l和r分别是Z中对于*的左零元和右零元，于是对所有的x Z，可有l=r=，能使*x=x*=。在此情况下，Z是唯一的，并称是Z中对*的零元。证明(zhngmng)：方法同幺元。例：,（1）在实数集合R中，对而言,，L=r=0,（2）在(E)中，对而言，=；,对而言，=E；,（3）命题逻辑中，对而言，=T；,对而言，=F。,第十四页，共95页。,2运算(yn sun)及其性质,定义：设*是Z中的二元运算(yn sun)，且Z中含幺元e，,令x Z，（1）若存在一xlZ，能使xl*x=e，则称xL是x的左逆元,并且称x是左可逆的；（2）若存在一xr Z，能使x*xr=e，则称xr是x的右逆元，并且称x是右可逆的；（3）若元素x既是左可逆的，又是右可逆的，则称x是可逆的，且x的逆元用x-1表示。,第十五页，共95页。,2运算(yn sun)及其性质,定理：设Z是集合，并含有幺元e。*是定义在Z上的一个二元运算，并且是可结合的。若x Z是可逆的，则它的左逆元等于(dngy)右逆元，且逆元是唯一的。证明：,（1）先证左逆元=右逆元：,设xL和xr分别是x Z的左逆元和右逆元，,x是可逆的和*是可结合的（条件给出）,xl*x=x*xr=e xl*x*xr=（xl*x）*xr=e*xr=xr；,xl*x*xr=xl*(x*xr)=xl*e=xl xr=xl,第十六页，共95页。,2运算(yn sun)及其性质,（2）证明(zhngmng)逆元是唯一的（若有的话）：,假设x1-1和x2-1均是x的二个不同的逆元，则x1-1=x1-1*e=x1-1*（x*x2-1）=（x1-1*x）*x2-1=e*x2-1=x2-1，,这和假设相矛盾。x若存在逆元的话一定是唯一的。,推论(x-1)-1=x,e-1=e证明(zhngmng)：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中，对“+”运算，对任一xR有,x-1=-x，x+（-x）=0，加法幺元,第十七页，共95页。,2运算(yn sun)及其性质,对“”运算，对任一x R有x-1=1x（x0）,x 1x=1，乘法幺元；,（2）在函数的合成(hchng)运算中,每一个双射函数都是可逆的，,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是可约的（或称可消去的）,第十八页，共95页。,2运算(yn sun)及其性质,定理设*是Z集合中的二元运算,且*是可结合的,若元素a Z,且对于*是可逆的,则a也是可约的。（反之(fnzh)不一定,即可约的不一定是可逆的。）证明：设任一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是可约的。,第十九页，共95页。,2运算(yn sun)及其性质,下面举例证明，若元素是可约的，但不一定是可逆的。例：I为整数集合，对“”运算，运算是可结合的。任何非零元素均是可约的，但除1和（-1）以外其他(qt)元素均没有逆元。1-1=1，(-1)-1=(-1)。例：Z=0,1,2,3,4,定义Z中二个运算为，,对任一x，y Z有,x+5y=（x+y）mod 5 x5y=（xy）mod 5,第二十页，共95页。,2运算(yn sun)及其性质,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没有逆元。,以上二元运算的性质(xngzh)均可运用到代数系统进行讨论。,+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,第二十一页，共95页。,3,半群,定义：一个代数系统，,S为非空集合，是S上的二元运算(yn sun)，如果运算(yn sun)是封闭的，则称代数系统为广群。,定义：设是一代数系统，S为非空集合，是S上的二元运算(yn sun)，若,(1)运算(yn sun)是封闭的。,(2)运算(yn sun)满足结合律，则称为半群。例：,均为半群,定义：对于*运算(yn sun)，拥有幺元的半群称为含幺半群。（拟群，幺半群，独异点）。例：,均为含幺半群，,而就不为幺半群。,第二十二页，共95页。,3,半群,例：设S为非空集合，(S)是S的幂集，,则,均为含幺半群。而，其中max(x1,x2)取二者之大值；，其中min(x1,x2)取二者之小值，均不为幺半群（不存在幺元）。则为含幺半群，其中 e=0,定义：设是一半群，TS，且*在T上是封闭(fngb)的，那么也是半群，称是,的子半群。,第二十三页，共95页。,n n-1,是n阶的（即|G|=n），则gn=e，以致(yzh)G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。,x （y z）=（x y）（x z）；,1-1=1，(-1)-1=(-1)。,其次证明R对于 运算(yn sun)满足代换性质,因为：f是由到 的一个同态映射(yngsh)。,第四十五页，共95页。,*是可结合的，且是可消去的，,把称为的一个同态象。,在此情况下，Z是唯一的，并称是Z中对*的零元。,第三章集合与关系(gun x),(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)。,（4）S中每一个元素均有逆元。,xl*x*xr=xl*(x*xr)=xl*e=xl xr=xl,4 群与子群(z qn),0 1 2 3 4,第七十九页，共95页。,3,半群,讨论定义：（1）因为*在S上是可结合的，而TS且*在T上是封闭(fngb)的，所以*在T上也是可结合的。,（2）由定义可知，SS，也是的子半群（子含幺半群）。为了和其它子半群相互区别，称是的“平凡子半群”;,定义设是一个含幺半群，TS，且*在T上是封闭(fngb)的，则也是一个含幺半群，,称是的子含幺半群。,第二十四页，共95页。,3,半群,讨论定义：（1）在幺半群中，由于幺元e的存在，,保证在运算表中一定没有相同的行和列。设任一x1,x2 Z，且x1x2，,则e*x1=x1 e*x2=x2；（2）在中若存在零元的话(dehu)，上述性质继续存在。,例：半群是的子半群，而不是子含幺半群。*运算由运算表定义：,第二十五页，共95页。,3,半群,*,0,1,0,0,0,1,0,1,*,0,1,0,1,0,0,0,0,1,1,0,1,由运算表可见(kjin)：中幺元为1，而在中幺元为。,定理：如果半群的载体S为有限集，则必有aS，使a*a=a。,第二十六页，共95页。,3,半群,证明(zhngmng)：因是半群，对任意的bS，,由*的封闭性，b*bS，b3S，b4S，,由于S是有限集，必有ij，使bi=bj,设：p=j i，则bj=bp*bi，即：bi=bp*bi,当qi时，bq=bp*bq，,又因p1，总可以找到k1，使kpi，对S中的,bkp有bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp,=b2p*(bp*bkp)=b3p*bkp=.=bkp*bkp,令a=bkp，则a*a=a。,第二十七页，共95页。,3,半群,定理：设是独异点，对于任意a，bS，且a，b均有逆元，则,a)(a-1)-1=a,b)a*b有逆元，且(a*b)-1=b-1*a-1,证明：a)因为(yn wi)a-1是a的逆元，即,a*a-1=a-1*a=e,所以 (a-1)-1=a,b)因为(yn wi)(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,第二十八页，共95页。,4 群与子群(z qn),1.群的定义,定义设是一代数系统，S是非空集合，*为S上的二元运算，它满足以下四个条件时，则称为群（1）*运算是封闭(fngb)的；（2）*运算是可结合的；,（3）存在幺元e；（4）S中每一个元素均有逆元。,例：,等均为群,（其中Z2 =0,1,Z3=0,1,2），而,只是含幺半群而不是群。,第二十九页，共95页。,4 群与子群(z qn),例：设M=0,60,120,240,300,180表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对M中任一元素a,b有a*b=图形旋转(a+b)的角度，并规定当旋转到360时即为0，,试验(shyn)证,是一个群。,*,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,第三十页，共95页。,4 群与子群(z qn),（1）运算是封闭(fngb)的,（2）*是可结合的,（3）幺元为0；,（4）每一个元素均有逆元：,(0)-1=0,(60)-1=300,(120)-1=240 ,(180)-1=180 ,(240)-1=12 0 ,(300)-1=60,是一个(y)群。,第三十一页，共95页。,4 群与子群(z qn),定义设是一个群，如果G是有限集合，则称为有限群，并把|G|称为群的阶数，如果G为无限集合，则称为无限群。,例：为无限群，上例中为有限群，群的阶为|M|=6。,至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合(jih)运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。,2.群的性质由群的定义可知:,第三十二页，共95页。,4 群与子群(z qn),（1）群具有半群和含幺半群所具有的所有性质；,（2）由于(yuy)群中存在幺元，在群的运算表中一定没有相同的行（和列）,（3）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。,下面以定理形式介绍群的性质,第三十三页，共95页。,4 群与子群(z qn),定理1 若是一个群，则对任一a,bG有：（1）存在唯一(wi y)的元素x G，使a*x=b；,（2）存在唯一(wi y)的元素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是唯一(wi y)的。,若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的唯一(wi y)元素，即x是唯一(wi y)的。（2）的证明同上。,第三十四页，共95页。,4 群与子群(z qn),定理2若是一个群，则对任一a,b,cG有：,（1）a*b=a*c b=c（a是左可消去的）；（2）b*a=c*a b=c（a是右可消去的）。,结论：在代数系统中，二元运算是可结合的，且a是可逆的，则a是可约的。此定理说明(shumng)群满足消去律。,第三十五页，共95页。,4 群与子群(z qn),定理(dngl)3一个群中一定不存在零元。,零元不存在逆元。,定义：代数系统中，如果存在aG,有a*a=a，则称a为等幂元。,第三十六页，共95页。,4 群与子群(z qn),定理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的一个双射称为(chn wi)S的一个置换。,第三十七页，共95页。,4 群与子群(z qn),定理5：群的运算表中的每一行或每一列都是G的元素的一个置换。,证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。,（反证法）如果对应于元素aG的那一行中有两个元素都是c，即有,a*b1=a*b2=c，且b1b2,由可约性，得：b1b2，这与b1b2矛盾。,其次(qc)，证明G中的每一个元素都在运算表的每一行和每一列中出现。,第三十八页，共95页。,4 群与子群(z qn),考察对应于元素aG的那一行，,设b是G中的任一元素,由于(yuy)b=a*(a-1*b)，所以b必定出现在对应于a的那一行。,再由运算表中没有两行（或两列）是相同的，,所以，的运算表中的每一行都是G的元素的一个置换，且每一行都是不相同的。,同样，对于每一列结论同样成立。,第三十九页，共95页。,4 群与子群(z qn),3.子群,定义设是一个群，且SG是一个非空集合。若满足下列三个条件，则称是的子群：（1）e是的幺元，且eS；（保持幺元）（2）对任一 aS一定有a-1 S；（保持逆元）（3）对任一a,bS一定有a*bS。（运算的封闭性）,讨论定义：（1）任一群至少可找到二个子群，即和，为了(wi le)以示区别称此二子群为平凡子群；（2）除了平凡子群以外的子群称为的真子群。,第四十页，共95页。,4 群与子群(z qn),定义设是群的真子群，,若不再(b zi)有一个真子群（其中ST），则称 是的极大子群。,例：是一个群，设S=x|x是6的倍数，T=y|y是3的倍数，则,是的真子群。,ST，,不是的极大子群。,定理设是一个群，B是G的非空子集，如果B是一个有限集，那么，只要运算*在B上是封闭的，则必定是的子群。,第四十一页，共95页。,4 群与子群(z qn),证明：设bB，已知*在B上封闭(fngb)，则b*b B，即,b2 B，b2*b B，即：b3 B，,于是b，b2，b3均在B中。,由于B是有限集，必存在正整数i和j，i1，那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，,且bj-i-1 B；,第四十二页，共95页。,4 群与子群(z qn),如果j-i=1，那么由bi=bi*b可知(k zh)b就是幺元，且以自身为逆元。,因此，是的一个子群。,例：设G4=p=|pi0,1，是上的二元运算，定义为，对任意X=，Y=G4，,X Y=，,其中的运算表如图所示：,证明,是群,的子群。,0,1,0,0,1,1,1,0,第四十三页，共95页。,4 群与子群(z qn),证明(zhngmng)：,第四十四页，共95页。,4 群与子群(z qn),定理:设是一个群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1S，则是,的子群。,证明(zhngmng)：先证，G中的幺元e也是S中的幺元。,任取 aS，a*a-1S，而a*a-1e，eS,再证，每个元素都有逆元。,又e*a-1S，即a-1S。,最后说明，*对S是封闭的。,a,b S，因b-1S，(b-1)-1 S,第四十五页，共95页。,4 群与子群(z qn),a*b=a*(b-1)-1 S，而(b-1)-1 b,a*b S,是的子群(z qn),例：设和都是群的子群(z qn)，试证明,也是的子群(z qn)。,第四十六页，共95页。,5,阿贝尔群和循环群,定义如果群中运算*是可交换的，,则称该群为阿贝尔群（或称为交换群）。,例：为阿贝尔群。,例：离散(lsn)函数代数系统是阿贝尔群。,Z=1,2,3,4，F=f0 ,f1 ,f2 ,f3 ,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,=,第四十七页，共95页。,5,阿贝尔群和循环群,由运算表可见：,（1）运算是封闭的；,（2）“”可结合；,（3）幺元f0；,（4）每一个元素(yun s)均可逆;,（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,第四十八页，共95页。,5,阿贝尔群和循环群,定理设是一个群，,是阿贝尔群的充分必要条件是对任一a,bG有 (a*b)*(a*b)=(a*a)*(b*b)。,证明：,（1）充分性：(a*b)*(a*b)=(a*a)*(b*b)是阿贝尔群。对任一a,bG有(a*b)*(a*b)=(a*a)*(b*b)成立(chngl)，,*是可结合的，且是可消去的，,a*(a*b)*b=(a*a)*(b*b)=(a*b)*(a*b)=a*(b*a)*b,得a*b=b*a，,是阿贝尔群。,第四十九页，共95页。,5,阿贝尔群和循环群,（2）必要性：,是阿贝尔群(a*b)*(a*b)=(a*a)*(b*b)。阿贝尔群满足(mnz)交换律，对任一a,bG有a*b=b*a，,(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)。,推论在阿贝尔群中，对任一a,bG有,(a*b)1 =b-1*a-1=a-1*b-1,第五十页，共95页。,5,阿贝尔群和循环群,定义设是一个(y)群，I 是整数集合，若存在一个(y)元素gG，对于G中每一个(y)元素a都能表示成gn的形式,（n I），则称是一个(y)循环群，g称为群的生成元。例：60就是群的生成元，所以该群为循环群。,定义设是由g 生成的循环群，若存在一个(y)正整数m，使gm=e成立，则整数中最小的m 称为生成元g 的周期，若不存在这样的m，则称周期为无穷大。,第五十一页，共95页。,5,阿贝尔群和循环群,例：（1）是一个群，生成元g=1，而g的周期为无穷大；（2）I为整数集合。“模m同余”是一个等价关系。,设：m=4，N4表示(biosh)“模4同余”所产生的等价类的集合，,N4=0,1,2,3，定义运+4：,i+4j=(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,运算表：,第五十二页，共95页。,5,阿贝尔群和循环群,由运算表可见：,（1）由0可生成,（2）由1或3可生成,（3）由2可生成,讨论定义：（1）在循环群中，由生成元的周期(zhuq)分为有限循环群和无限循环群二类；,第五十三页，共95页。,5,阿贝尔群和循环群,（2）在循环群中，生成元的周期是指gm=e中最小的m,（这里m0且mI+）。,定理每一个循环群必然是阿贝尔群。证明：设是一循环群，g为生成元，,对任一p,q G一定存在 i,j I（整数(zhngsh)）使得p=gi,q=gj，,则p*q=gi *gj=gi+j =gj *gi=q*p。循环群一定是阿贝尔群。,第五十四页，共95页。,5,阿贝尔群和循环群,定理设是由元素gG生成的循环群，若,是n阶的（即|G|=n），则gn=e，以致(yzh)G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。,证明：,第五十五页，共95页。,5,阿贝尔群和循环群,定理(dngl)设是由元素gG生成的循环群，若,是n阶的（即|G|=n），则gn=e，以致G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。,证明：,第五十六页，共95页。,5,阿贝尔群和循环群,例：为一群(y qn),G中元素和*运算见运算表：,c1=c,c2=b,c3=d,c4=a(幺元);,d1=d,d2=b,d3=c,d4=a(幺元);,而a1=a,a2=a,a3=a,a4=a;,b1=b,b2=a,b3=b,b4=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,第五十七页，共95页。,5,阿贝尔群和循环群,定理设是由元素gG生成(shn chn)的循环群，若,是n阶的（即|G|=n），则gn=e，以致G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。,证明：,第五十八页，共95页。,5,阿贝尔群和循环群,例：为一群(y qn),G中元素和*运算见运算表：,c1=c,c2=b,c3=d,c4=a(幺元);,d1=d,d2=b,d3=c,d4=a(幺元);,而a1=a,a2=a,a3=a,a4=a;,b1=b,b2=a,b3=b,b4=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,第五十九页，共95页。,(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)。,（4）每一个元素(yun s)均可逆;,但等价关系对*运算(yn sun)不满足代换性质。,第七十二页，共95页。,证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。,证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。,定义：对于*运算(yn sun)，拥有幺元的半群称为含幺半群。,（2）在中若存在零元的话(dehu)，上述性质继续存在。,期中(q zhn)复习,0 4 3 2 1,任何非零元素均是可约的，但除1和（-1）以外其他(qt)元素均没有逆元。,第二十二页，共95页。,x1+m x2=(x1 +x2)mod m。,定义:若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。,x是可逆的和*是可结合的（条件给出）,期中(q zhn)复习,1）命题及其表示法,命题 真值 原子命题 复合命题 命题标识符 命题常量(chngling),命题变元 原子变元,2）联结词,否定 合取 析取 条件 双条件,3）命题公式与翻译,合式公式 翻译 优先级,4）真值表与等价公式,真值表 逻辑等价 子公式 定理,第六十页，共95页。,期中(q zhn)复习,5）重言式与蕴含式,重言式（永真式）矛盾式（永假式）蕴含式,定理1-5.1 定理1-5.2 定理1-5.3 定理,7）范式,合取范式 析取范式 主合取范式 主析取范式,定理1-7.3 定理,8）推理理论,有效结论 P规则 T规则 CP规则,等价(dngji)公式表 蕴含公式表,第六十一页，共95页。,期中(q zhn)复习,第二章谓词逻辑,1）谓词的概念与表示,谓词 谓词填式 n元谓词,2）命题(mng t)函数与量词,命题(mng t)函数 复合命题(mng t)函数 个体域 全总个体域,全称量词 存在量词 特性谓词,3）谓词公式与翻译,合式公式,4）变元的约束,辖域 约束变元 自由变元 换名 代入,第六十二页，共95页。,期中(q zhn)复习,5）谓词演算的等价式与蕴含式,赋值 等价 有效的（永真的）不可满足的（永假的）,可满足的 谓词演算的等价式与蕴含式,6）前束范式,前束范式 定理(dngl),7）谓词演算的推理理论,US UG ES EG规则,第六十三页，共95页。,期中(q zhn)复习,第一(dy)、二章作业选讲,第六十四页，共95页。,期中(q zhn)复习,第三章集合与关系(gun x),1）集合的概念和表示法,集合 元素 子集 真子集 空集 全集 幂集,外延性原理 定理3-1.1 定理3-1.2 定理,2）集合的运算,交 并 补 绝对补 对称差,集合运算的性质,4）序偶与笛卡尔积,序偶 三元组 n元组 笛卡尔积,5）关系(gun x)及其表示,第六十五页，共95页。,期中(q zhn)复习,关系 前域 值域 恒等关系 全域关系 空关系,关系矩阵 关系图,6）关系的性质,自反 对称 传递 反自反 反对称,7）复合(fh)关系和逆关系,复合(fh)关系 逆关系,定理,8）关系的闭包运算,闭包,定理定理,第六十六页，共95页。,期中(q zhn)复习,9）集合的划分(hu fn)和覆盖,划分(hu fn)覆盖,10）等价关系与等价类,等价关系 等价类 商集,定理定理,12）序关系,偏序集 盖住关系 盖住集和哈斯图,极大元 极小元 最大元 最小元,上界 下界 最小上界 最大下界,全序 良序 拟序,第六十七页，共95页。,期中(q zhn)复习,第四章函数,1）函数的概念,函数 定义域 值域 函数相等 函数集合(jh),满射 入射 双射,2）逆函数和复合函数,逆函数 左复合,恒等函数 常函数 函数复合的结合性,定理定理,第六十八页，共95页。,期中(q zhn)复习,第三(d sn)、四章作业选讲,第六十九页，共95页。,6,同态与同构,1.代数系统的概念：,定义由集合和集合上的一个或多个n元运算所组成的系统称为代数系统，用符号=表示，其中S为非空集合，f1,f2fm表示n元运算。讨论定义：,（1）构成一个代数系统必须具备三个条件(tiojin)：一个非空集合S，称为载体；在S上的运算f1,f2fm,；在S上的运算是封闭的。（2）有些书上把特异元素（常数）放在代数系统之中，形成 ；,第七十页，共95页。,6,同态与同构,2.同态和同构,同态和同构是讨论二个代数系统之间的关系(gun x)。,定义设U=和V=是二个代数系统，又设U到V存在一个映射 f:AB，对任一a1,a2A，若有f(a1a2)=f(a1)*f(a2)，则称 f 是从代数系统U到V的同态映射。称U同态于V。把称为的一个同态象。其中：,f(A)=x|x=f(a)，aAB,讨论定义：,第七十一页，共95页。,6,同态与同构,（1）f:AB为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；,（2）对同态讲，二个代数系统的基数可以不相等，只要满足(mnz)函数的条件就行；（3）上述定义可以推广到多个n元运算的同一类型的代数系统中去。,（4）一个代数系统到另一个代数系统可能存在多于一个同态。,第七十二页，共95页。,6,同态与同构,例：,给定二代数(dish)系统 F=I,+，I为整数，“+”为一般加；,G=Nm,+m，其中，,Nm=0,1,2m-1,“+m”为模m加法并定义成,x1+m x2=(x1 +x2)mod m。,对任一iI和mI+，,(i)mod m 定义了除以m所得之非负余数,且0 (i)mod m m。,第七十三页，共95页。,6,同态与同构,定义FG的一个函数：,f :I Nm且有 f(i)=i(mod m)，,(其中(qzhng)iI，f(i)Nm),f(i1+i2)=(i1+i2)mod m=(i1 mod m)+m(i2 mod m)，其中(qzhng)i1I,i2I；,i1 mod m Nm,i2 mod m Nm。,则 f 是一同态函数：自变量和象点的对应，并保持运算的对应。,第七十四页，共95页。,6,同态与同构,定义若 f:AB 是从U=,到 V=的同态，于是有：（1）若 f 是满射函数，则称 f 是从U到V的满同态；（2）若 f 是入射函数，则称 f 是从U到V的单一同态；（3）若 f 是双射函数，则称 f 是从U到V的同构。,定义设V是一个代数(dish)系统，如果f是由V到V的同态，则称f为自同态。如果g是V到V的同构，则称g为自同构。,第七十五页，共95页。,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,例：离散函数代数(dish)系统和剩余类加代数(dish)系统是同构的。,第七十六页，共95页。,6,同态与同构,定义一函数 h:F N4，h(f i)=i，其中i 0,1,2,3，,元素一一对应；,h(f i f j)=h(f i)+4 h(f j)=i+4 j，,运算是一一对应的；,和是二个同构的代数系统。,在实际中，把对应的元素和运算进行交换(jiohun)，就能得到相同的运算表。,例：试考定下列二代数系统U和V是否同构：,U=，V=,其运算表如下：,第七十七页，共95页。,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,第七十八页，共95页。,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,第七十九页，共95页。,6,同态与同构,定义V 中：求二数的最小公倍数；：求二数的最大公约数；“”：10被x除所得(su d)之商。,由运算表可见：,定义一函数 f:1,2,5,10 ,A,A,E,f(1)=，f(2)=A,，f(5)=A,，f(