第五章 代数结构优秀PPT.ppt

《第五章 代数结构优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第五章 代数结构优秀PPT.ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 代数结构第一页，本课件共有95页代数系统代数系统第五章第五章代代 数数 结结 构构1代数系统的引入2运算及其性质3半群4群与子群5阿贝尔群和循环群6*陪集与拉格朗日定理7同态与同构第二页，本课件共有95页1 代数系统的引入定义定义:设Z是一个集合,f是一个函数,f：ZnZ,则称f为Z中的n元运算,整数n称为运算的阶（元,次）。若n=1,则称f：ZZ为一元运算；若n=2,则f：Z2Z为二元运算。本章主要讨论一元运算和二元运算。例：（1）在整数I和实数R中,+,-,均为二元运算,而对而言就不是二元运算 （2）在集合Z的幂集(z)中,均为二元运算,而“”是一元运算；第三页，本课件共有95页1

2、 代数系统的引入（3）命题公式中,均为二元运算,而“”为一元运算（4）双射函数中,函数的合成运算是二元运算；二元运算常用符号：+,等等。定义定义:一个非空集合A连同若干个定义在该集合上的运算f1,f2,.,fk所组成的系统就称为一个代数系统，记作。第四页，本课件共有95页1 代数系统的引入定义定义:若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。在f：Z2Z二元运算的定义中,本身要求满足运算是封闭的。例：（1）在正整偶数的集合E中,对,+运算是封闭的；在正整奇数的集合中,对运算是封闭的,而对+运算不是封闭的。（2）在前例中,R,I集合中+,-,运算；

3、(z)的元素中,运算等均为封闭的。第五页，本课件共有95页2运算及其性质定义定义:设*是集合S上的二元运算,对任一x,yS有xyS则称运算在S上是封闭的。定义定义:设*是集合S上的二元运算,对任一x,yS有xy=y x,则称运算在S上是可交换的（或者说在S上满足交换律）。第六页，本课件共有95页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）,则称运

4、算对是可分配的（或称对满足分配律）。第七页，本课件共有95页2运算及其性质定义定义:设，是定义在集合S上的两个可交换二元运算，如果对于任意的x,yS，都有：x(x y)=x；x(xy)=x则称运算和运算满足吸收律。定义定义:设*是S上的二元运算,若对任一x S有x x=x,则称满足等幂律。讨论定义：1)S上每一个元素均满足xx=x,才称在S上满足幂等律；2)若在S上存在元素xS有x x=x,则称x为S上的幂等元素；3)由此定义,若x是幂等元素,则有x x=x和xn=x成立。第八页，本课件共有95页2运算及其性质例：（1）在实数集合R中,+,是可交换,可结合的,对+是满足分配律的,“0”对+是等

5、幂元素,而其它不为等幂元素,对“-”法是不可交换,不可结合的；（2）在(z)中,均是可交换,可结合的,对,对均是可分配的；(z)中任一元素,对,均是等幂元素。满足等幂律；而(z)中,对称差分是可交换,可结合的。除(s)=以外不满足等幂律。=,而除以外的A(z)有A AA。第九页，本课件共有95页2运算及其性质定义：设*是S上的二元运算,对任一xS,则：x1=x,x2=x*x,xn=xn-1*x定理：设*是S上的二元运算,且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（

6、2）(xm)n=xm xm=xm+m xm xm=xmn n n-1第十页，本课件共有95页2运算及其性质下面定义特异元素幺元,零元和逆元。定义定义：设*是集合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运算及其性质 el和er分别是对*的

7、左,右左元，则有el*er=er=el 有el=er=e成立。（2）幺元e是唯一的。用反证法：假设有二个不同的幺元e1和e2,则有e1*e2=e2=e1,这和假设相矛盾。若存在幺元的话一定是唯一的。例：（1）在实数集合R中,对+而言,e+=0；对而言,e*=1；（2）在(E)中,对而言,e =E（全集合）；对而言,e =（空集）；第十二页，本课件共有95页2运算及其性质（3）双射函数中,对“”而言，e =Ix（恒等函数）；（4）命题逻辑中，对而言，e =F（永假式）；对而言，e =T（永真式）。定义：定义：设*是对集合Z中的二元运算，（1）若有一元素l Z，且对每一个x Z有 l*x=l，则称

8、l 为Z中对于*的左零元；（2）若有一元素r Z，且对每一个x Z有 x*r=r，则称r为Z中对于*的右零元。第十三页，本课件共有95页2运算及其性质定理定理：若l和r分别是Z中对于*的左零元和右零元，于是对所有的x Z，可有l=r=，能使*x=x*=。在此情况下，Z是唯一的，并称是Z中对*的零元。证明：方法同幺元。例：（1）在实数集合R中，对而言,，L=r=0（2）在(E)中，对而言，=；对而言，=E；（3）命题逻辑中，对而言，=T；对而言，=F。第十四页，本课件共有95页2运算及其性质定义定义：设*是Z中的二元运算，且Z中含幺元e，令x Z，（1）若存在一xlZ，能使xl*x=e，则称xL

9、是x的左逆元,并且称x是左可逆的；（2）若存在一xr Z，能使x*xr=e，则称xr是x的右逆元，并且称x是右可逆的；（3）若元素x既是左可逆的，又是右可逆的，则称x是可逆的，且x的逆元用x-1表示。第十五页，本课件共有95页2运算及其性质定理定理：设Z是集合，并含有幺元e。*是定义在Z上的一个二元运算，并且是可结合的。若x Z是可逆的，则它的左逆元等于右逆元，且逆元是唯一的。证明：（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)

10、=xl*e=xl xr=xl第十六页，本课件共有95页2运算及其性质（2）证明逆元是唯一的（若有的话）：假设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证明：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运算及其性质对“

11、”运算，对任一x R有x-1=1x（x0）x 1x=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是可约的（或称可消去的）第十八页，本课件共有95页2运算及其性质定理定理设*是Z集合中的二元运算,且*是可结合的,若元素a Z,且对于*是可逆的,则a也是可约的。（反之不一定,即可约的不一定是可逆的。）证明：设任一x，y Z,且有a*x=a*y，下面证明，在*可结合和a对*

12、是可逆的条件下，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运算及其性质下面举例证明，若元素是可约的，但不一定是可逆的。例：I为整数集合，对“”运算，运算是可结合的。任何非零元素均是可约的，但除1和（-1）以外其他元素均没有逆元。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

13、运算及其性质 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没有逆元。以上二元运算的性质均可运用到代数系统进行讨论。+50 1 2 3 4012340 1 2 3 41 2 3 4 02 3 4 0 13 4 0 1 24 0 1 2 3*50 1 2 3 4012340 0 0 0 00 1 2 3 40 2 4 1 30 3 1 4 20 4 3 2 1第二十一页，本课件共有95页3 半群半群定义定义：一个代数系统，S为非空集合，是S上的二元运算，如果运算是封闭的，则称代数系统为广群。定义定义

14、：设是一代数系统，S为非空集合，是S上的二元运算，若(1)运算是封闭的。(2)运算满足结合律，则称为半群。例：,均为半群定义定义：对于*运算，拥有幺元的半群称为含幺半群。（拟群，幺半群，独异点）。例：,均为含幺半群，而就不为幺半群。第二十二页，本课件共有95页3 半群半群例：设S为非空集合，(S)是S的幂集，则,均为含幺半群。而，其中max(x1,x2)取二者之大值；，其中min(x1,x2)取二者之小值，均不为幺半群（不存在幺元）。则为含幺半群，其中 e=0定义定义：设是一半群，TS，且*在T上是封闭的，那么也是半群，称是 的子半群。第二十三页，本课件共有95页3 半群半群讨论定义：（1）因

15、为*在S上是可结合的，而TS且*在T上是封闭的，所以*在T上也是可结合的。（2）由定义可知，SS，也是的子半群（子含幺半群）。为了和其它子半群相互区别，称是的“平凡子半群”;定义定义设是一个含幺半群，TS，且*在T上是封闭的，则也是一个含幺半群，称是的子含幺半群。第二十四页，本课件共有95页3 半群半群讨论定义：（1）在幺半群中，由于幺元e的存在，保证在运算表中一定没有相同的行和列。设任一x1,x2 Z，且x1x2，则e*x1=x1 e*x2=x2；（2）在中若存在零元的话，上述性质继续存在。例：半群是的子半群，而不是子含幺半群。*运算由运算表定义：第二十五页，本课件共有95页3 半群半群*0

16、1000101*010100001101由运算表可见：中幺元为1，而在中幺元为。定理定理：如果半群的载体S为有限集，则必有aS，使a*a=a。第二十六页，本课件共有95页3 半群半群证明：因是半群，对任意的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。第二十七页，本课件共有

17、95页3 半群半群定理定理：设是独异点，对于任意a，bS，且a，b均有逆元，则a)(a-1)-1=ab)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第二十八页，本课件共有95页4 群与子群群与子群1.群的定义群的定义定义定义设是一代数系统，S是非空集合，*为S上的二元运算，它满足以下四个条件时，则称为群（1）*运算是封闭的；（2）*运算是

18、可结合的；（3）存在幺元e；（4）S中每一个元素均有逆元。例：,等均为群（其中Z2 =0,1,Z3=0,1,2），而,只是含幺半群而不是群。第二十九页，本课件共有95页4 群与子群群与子群例：设M=0,60,120,240,300,180表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对M中任一元素a,b有a*b=图形旋转(a+b)的角度，并规定当旋转到360时即为0，试验证是一个群。*060120180240300006012018024030060601201802403000120120180240300060180180240300060120240240300060120

19、180300300060120180240第三十页，本课件共有95页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 是一个群。第三十一页，本课件共有95页4 群与子群群与子群定义定义设是一个群，如果G是有限集合，则称为有限群，并把|G|称为群的阶数，如果G为无限集合，则称为无限群。例：为无限群，上例中为有限群，群的阶为|M|=6。至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有

20、结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。2.群的性质群的性质由群的定义可知:第三十二页，本课件共有95页4 群与子群群与子群（1）群具有半群和含幺半群所具有的所有性质；（2）由于群中存在幺元，在群的运算表中一定没有相同的行（和列）（3）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。下面以定理形式介绍群的性质 第三十三页，本课件共有95页4 群与子群群与子群定理定理1 若是一个群，则对任一a,bG有：（1）存在唯一的元素x G，使a*x=b；（2）存在唯一的元素y G，使y*a=b。证明：（1）（a）在G中存在x，使a*x=b成立。a*

21、(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）的证明同上。第三十四页，本课件共有95页4 群与子群群与子群定理定理2 2若是一个群，则对任一a,b,cG有：（1）a*b=a*c b=c（a是左可消去的）；（2）b*a=c*a b=c（a是右可消去的）。结论：在代数系统中，二元运算是可结合的，且a是可逆的，则a是可约的。此定理说明群满足消去律。

22、第三十五页，本课件共有95页4 群与子群群与子群定理定理3 3一个群中一定不存在零元。零元不存在逆元。定义定义：代数系统中，如果存在aG,有a*a=a，则称a为等幂元。第三十六页，本课件共有95页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的一个置换。第三十七页，本课件共有95页4 群与子群群与子群定理定理5：群的运算表中的每一行或每一列都是G的元素的一个置换。证明：首先，证明运算表中的

23、任一行或任一列所含G中的一个元素不可能多于一次。（反证法）如果对应于元素aG的那一行中有两个元素都是c，即有a*b1=a*b2=c，且b1b2 由可约性，得：b1b2，这与b1b2矛盾。其次，证明G中的每一个元素都在运算表的每一行和每一列中出现。第三十八页，本课件共有95页4 群与子群群与子群 考察对应于元素aG的那一行，设b是G中的任一元素由于b=a*(a-1*b)，所以b必定出现在对应于a的那一行。再由运算表中没有两行（或两列）是相同的，所以，的运算表中的每一行都是G的元素的一个置换，且每一行都是不相同的。同样，对于每一列结论同样成立。第三十九页，本课件共有95页4 群与子群群与子群3.子

24、群子群定义定义设是一个群，且SG是一个非空集合。若满足下列三个条件，则称是的子群：（1）e是的幺元，且eS；（保持幺元）（2）对任一 aS一定有a-1 S；（保持逆元）（3）对任一a,bS一定有a*bS。（运算的封闭性）讨论定义：（1）任一群至少可找到二个子群，即和，为了以示区别称此二子群为平凡子群；（2）除了平凡子群以外的子群称为的真子群。第四十页，本课件共有95页4 群与子群群与子群定义定义设是群的真子群，若不再有一个真子群（其中ST），则称 是的极大子群。例：是一个群，设S=x|x是6的倍数，T=y|y是3的倍数，则,是的真子群。ST，不是的极大子群。定理定理设是一个群，B是G的非空子集

25、，如果B是一个有限集，那么，只要运算*在B上是封闭的，则必定是的子群。第四十一页，本课件共有95页4 群与子群群与子群证明：设bB，已知*在B上封闭，则b*b B，即b2 B，b2*b B，即：b3 B，于是b，b2，b3均在B中。由于B是有限集，必存在正整数i和j，ij,使得：bi=bj即：bi=bi*bj-i由此可说明bj-i是中的幺元，且这个幺元也 在子集B中。如果j-i1，那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，且bj-i-1 B；第四十二页，本课件共有95页4 群与子群群与子群如果j-i=1，那么由bi=bi*b可知b就是幺元，且以自身为逆元。因此，是的一个子群。

26、例：设G4=p=|pi0,1，是上的二元运算，定义为，对任意X=，Y=G4，X Y=，其中的运算表如图所示：证明,是群的子群。01001110第四十三页，本课件共有95页4 群与子群群与子群证明：第四十四页，本课件共有95页4 群与子群群与子群定理定理:设是一个群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1S，则是 的子群。证明：先证，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 群与子群群与子群a

27、*b=a*(b-1)-1 S，而(b-1)-1 b a*b S 是的子群例：设和都是群的子群，试证明也是的子群。第四十六页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群定义定义如果群中运算*是可交换的，则称该群为阿贝尔群（或称为交换群）。例：为阿贝尔群。例：离散函数代数系统是阿贝尔群。Z=1,2,3,4，F=f0 ,f1 ,f2 ,f3 1 2 3 42 3 4 1,f2 =1 2 3 43 4 1 2,f3 =1 2 3 44 1 2 3,f0=1 2 3 41 2 3 4 f =第四十七页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群由运算表可见：（1）运算是封闭的；（2）

28、“”可结合；（3）幺元f0；（4）每一个元素均可逆;（5）以主对角线为对称。为阿贝尔群。f0f1 f2 f3f0f0f1 f2 f3f1f1 f2 f3f0f2 f2 f3f0f1f3f3f0f1f2 第四十八页，本课件共有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)成立，*是可结合的，且是可消去的，a*(a*b)*b=(a*a)*(b*b)=(a

29、*b)*(a*b)=a*(b*a)*b 得a*b=b*a，是阿贝尔群。第四十九页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群（2）必要性：是阿贝尔群(a*b)*(a*b)=(a*a)*(b*b)。阿贝尔群满足交换律，对任一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 阿贝尔群和循环群阿贝尔群和循环群定义定义设是一个群，I 是整数集合，若存在一个元素gG，对于G中每一个元素a都能表示成gn的形式 （n I

30、），则称是一个循环群，g称为群的生成元。例：60就是群的生成元，所以该群为循环群。定义定义设是由g 生成的循环群，若存在一个正整数m，使gm=e成立，则整数中最小的m 称为生成元g 的周期，若不存在这样的m，则称周期为无穷大。第五十一页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群例：（1）是一个群，生成元g=1，而g的周期为无穷大；（2）I为整数集合。“模m同余”是一个等价关系。设：m=4，N4表示“模4同余”所产生的等价类的集合，N4=0,1,2,3，定义运+4：i+4j=(i+j)(mod 4)(i,j=0,1,2,3)则：是群+4012300123112302230133012

31、运算表：第五十二页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群由运算表可见：（1）由0可生成（2）由1或3可生成（3）由2可生成讨论定义：（1）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；第五十三页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群（2）在循环群中，生成元的周期是指gm=e中最小的m （这里m0且mI+）。定理定理每一个循环群必然是阿贝尔群。证明：设是一循环群，g为生成元，对任一p,q G一定存在 i,j I（整数）使得p=gi,q=gj，则p*q=gi *gj=gi+j =gj *gi=q*p。循环群一定是阿贝尔群。第五十四页，本课件共有95页5

32、阿贝尔群和循环群阿贝尔群和循环群定理定理设是由元素gG生成的循环群，若 是n阶的（即|G|=n），则gn=e，以致G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。证明：第五十五页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群定理定理设是由元素gG生成的循环群，若 是n阶的（即|G|=n），则gn=e，以致G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。证明：第五十六页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群例：为一群,G中元素和*运算见运算表：c1=c,c2=b,c3=d,c4=a(幺元);d1=d,d2=b,d3=c,d4=a(幺元);而

33、a1=a,a2=a,a3=a,a4=a;b1=b,b2=a,b3=b,b4=a,由上可见：生成元c,d的阶为4，等于群的阶，即|G|的基数。*abcdaabcdbbadcccdbaddcab第五十七页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群定理定理设是由元素gG生成的循环群，若 是n阶的（即|G|=n），则gn=e，以致G=g1,g2,gn =e，而且n是能使gn =e的最小正整数。证明：第五十八页，本课件共有95页5 阿贝尔群和循环群阿贝尔群和循环群例：为一群,G中元素和*运算见运算表：c1=c,c2=b,c3=d,c4=a(幺元);d1=d,d2=b,d3=c,d4=a(幺元

34、);而a1=a,a2=a,a3=a,a4=a;b1=b,b2=a,b3=b,b4=a,由上可见：生成元c,d的阶为4，等于群的阶，即|G|的基数。*abcdaabcdbbadcccdbaddcab第五十九页，本课件共有95页期中复习1）命题及其表示法）命题及其表示法命题 真值 原子命题 复合命题 命题标识符 命题常量 命题变元 原子变元2）联结词）联结词否定 合取 析取 条件 双条件3）命题公式与翻译）命题公式与翻译合式公式 翻译 优先级4）真值表与等价公式）真值表与等价公式真值表 逻辑等价 子公式 定理1-4.1第六十页，本课件共有95页期中复习5）重言式与蕴含式）重言式与蕴含式重言式（永真

35、式）矛盾式（永假式）蕴含式定理1-5.1 定理1-5.2 定理1-5.3 定理1-5.47）范式）范式合取范式 析取范式 主合取范式 主析取范式定理1-7.3 定理1-7.48）推理理论）推理理论有效结论 P规则 T规则 CP规则 等价公式表 蕴含公式表第六十一页，本课件共有95页期中复习第二章第二章 谓词逻辑谓词逻辑1）谓词的概念与表示）谓词的概念与表示谓词 谓词填式 n元谓词2）命题函数与量词）命题函数与量词命题函数 复合命题函数 个体域 全总个体域 全称量词 存在量词 特性谓词3）谓词公式与翻译）谓词公式与翻译合式公式4）变元的约束）变元的约束辖域 约束变元 自由变元 换名 代入第六十二

36、页，本课件共有95页期中复习5）谓词演算的等价式与蕴含式）谓词演算的等价式与蕴含式赋值 等价 有效的（永真的）不可满足的（永假的）可满足的 谓词演算的等价式与蕴含式6）前束范式）前束范式前束范式 定理2-6.17）谓词演算的推理理论）谓词演算的推理理论US UG ES EG规则第六十三页，本课件共有95页期中复习第一、二章作业选讲第六十四页，本课件共有95页期中复习第三章第三章集合与关系集合与关系1）集合的概念和表示法）集合的概念和表示法集合 元素 子集 真子集 空集 全集 幂集 外延性原理 定理3-1.1 定理3-1.2 定理3-1.32）集合的运算）集合的运算交 并 补 绝对补 对称差集合

37、运算的性质4）序偶与笛卡尔积）序偶与笛卡尔积序偶 三元组 n元组 笛卡尔积5）关系及其表示）关系及其表示第六十五页，本课件共有95页期中复习关系 前域 值域 恒等关系 全域关系 空关系 关系矩阵 关系图6）关系的性质）关系的性质自反 对称 传递 反自反 反对称7）复合关系和逆关系）复合关系和逆关系复合关系 逆关系定理3-7.28）关系的闭包运算）关系的闭包运算闭包定理3-8.1-定理3-8.5第六十六页，本课件共有95页期中复习9）集合的划分和覆盖）集合的划分和覆盖划分 覆盖10）等价关系与等价类）等价关系与等价类等价关系 等价类 商集定理3-10.1-定理3-10.412）序关系）序关系偏序

38、集 盖住关系 盖住集和哈斯图极大元 极小元 最大元 最小元 上界 下界 最小上界 最大下界 全序 良序 拟序第六十七页，本课件共有95页期中复习第四章第四章函数函数1）函数的概念）函数的概念函数 定义域 值域 函数相等 函数集合满射 入射 双射2）逆函数和复合函数）逆函数和复合函数逆函数 左复合恒等函数 常函数 函数复合的结合性定理4-2.1-定理4-2.7第六十八页，本课件共有95页期中复习第三、四章作业选讲第六十九页，本课件共有95页6 同态与同构同态与同构1.代数系统的概念代数系统的概念：定义定义由集合和集合上的一个或多个n元运算所组成的系统称为代数系统，用符号=表示，其中S为非空集合，

39、f1,f2fm表示n元运算。讨论定义：（1）构成一个代数系统必须具备三个条件：一个非空集合S，称为载体；在S上的运算f1,f2fm,；在S上的运算是封闭的。（2）有些书上把特异元素（常数）放在代数系统之中，形成 ；第七十页，本课件共有95页6 同态与同构同态与同构2.同态和同构同态和同构 同态和同构是讨论二个代数系统之间的关系。定义定义设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 讨论定义：第七十一页

40、，本课件共有95页6 同态与同构同态与同构 （1）f:AB为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；（2）对同态讲，二个代数系统的基数可以不相等，只要满足函数的条件就行；（3）上述定义可以推广到多个n元运算的同一类型的代数系统中去。（4）一个代数系统到另一个代数系统可能存在多于一个同态。第七十二页，本课件共有95页6 同态与同构同态与同构例：给定二代数系统 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 定义了除以

41、m所得之非负余数 且0 (i)mod m m。第七十三页，本课件共有95页6 同态与同构同态与同构定义FG的一个函数：f :I Nm且有 f(i)=i(mod m)，(其中iI，f(i)Nm),f(i1+i2)=(i1+i2)mod m=(i1 mod m)+m(i2 mod m)，其中 i1I,i2I；i1 mod m Nm,i2 mod m Nm。则 f 是一同态函数：自变量和象点的对应，并保持运算的对应。第七十四页，本课件共有95页6 同态与同构同态与同构定义定义若 f:AB 是从U=到 V=的同态，于是有：（1）若 f 是满射函数，则称 f 是从U到V的满同态；（2）若 f 是入射函数

42、，则称 f 是从U到V的单一同态；（3）若 f 是双射函数，则称 f 是从U到V的同构。定义定义设V是一个代数系统，如果f是由V到V的同态，则称f为自同态。如果g是V到V的同构，则称g为自同构。第七十五页，本课件共有95页6 同态与同构同态与同构 f =1 2 3 4 2 3 4 1 f 0f 1f 2f 3f 0f 0f 1f 2f 3f 1f 1f 2f 3f 0f 2f 2f 3f 0f 1f 3f 3f 0f 1f 2+4012300123112302230133012例：离散函数代数系统和剩余类加代数系统是同构的。第七十六页，本课件共有95页6 同态与同构同态与同构定义一函数 h:F

43、 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，运算是一一对应的；和是二个同构的代数系统。在实际中，把对应的元素和运算进行交换，就能得到相同的运算表。例：试考定下列二代数系统U和V是否同构：U=，V=,其运算表如下：第七十七页，本课件共有95页6 同态与同构同态与同构SSEAAAAEAAEAAEAAAEEAAEAEEEEEEAAEAAAAAAEAAE第七十八页，本课件共有95页6 同态与同构同态与同构X110255210 1X1251011251022210 105510 51010 10 10 10 10125

44、101111121212511551012510第七十九页，本课件共有95页6 同态与同构同态与同构定义V 中：求二数的最小公倍数；：求二数的最大公约数；“”：10被x除所得之商。由运算表可见：定义一函数 f:1,2,5,10 ,A,A,Ef(1)=，f(2)=A,，f(5)=A,，f(10)=E 元素一一对应；x第八十页，本课件共有95页6 同态与同构同态与同构对任一 a,b 1,2,5,10有 f()=f(a)af(a b)=f(a)f(b)f(a b)=f(a)f(b)运算一一对应。f 是一双射函数，U和V 二个代数系统同构。若二个代数系统同构，则此二个代数系统具有完全相同的性质,所以对

45、于同构的代数系统,只要研究其中一个代数系统,其它的代数系统的问题也就解决了,给我们研究问题带来了方便。第八十一页，本课件共有95页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同构。所以，同构关系是等价关系。第八十二页，本课件共有95页6 同态与同构同态与同构定理定理设f是从代数系统U=到

46、V=的同态映射，（1）如果U是半群，那么在f作用下，同态象也是半群；（2）如果U是独异点，那么在f作用下，同态象也是独异点；（3）如果U是群，那么在f作用下，同态象也是群；第八十三页，本课件共有95页6 同态与同构同态与同构证明：第八十四页，本课件共有95页6 同态与同构同态与同构3.同余关系：同余关系：这是讨论同一代数系统中的关系。同余关系是代数系统的集合中的等价关系，在运算的作用下，能保持运算的等价类，同余关系是相等关系的推广。在介绍同余关系之前先看一个例子。例：设是一代数系统,其中F是所有分数的集合,+,-,为一般的加,减,乘法。则在F中,可把相等的分数作为元素的集合是F的子集:1/2=

47、,-2/-4,-1/-2,1/2,2/4,3/6,1/3=,-2/-6,-1/-3,1/3,2/6,.。若对二个等价类中的元素进行+,-,运算，则运算结果必定属于同一等价类中。第八十五页，本课件共有95页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中，二个等价类的元素对+,-,运算均满足代换性质，即分数集合的相等关系，对+,-,运算满足代换性质。第八十六页，本课件共有95页6 同态与同构同态与同构定义定义设代数系统 U=

48、,*是二元运算，R是Z中的等价关系，当且仅当对任一x1,x2 Z y1,y2 Z有 x1R x2 y1Ry2 x1*y1 R x2*y2时，则对于运算*，等价关系R满足代换性质（置换性质）。定义定义设U=是一代数系统，R是Z中的等价关系，于是对于二元运算*，若等价关系R满足代换性质，则称R是代数系统U中的同余关系，与此相对应，R的等价类称为同余类。第八十七页，本课件共有95页6 同态与同构同态与同构例：在整数I集合中 是一个同余关系，为一代数系统，对任一定义*运算：*(i)=(i2)mod m,(m I+)定义R关系：设R是I中的一个关系，当i1 mod m=i2 mod m时，则有i1R i

49、2下面证明(i2)mod m是一个同余关系证明：（1）前面已证明：在I中，i(i I)模 m 等价是一个等价关系。（2）对于*运算，R满足代换性质。第八十八页，本课件共有95页6 同态与同构同态与同构设i1,i2 I，且i1 R i2（即i1 mod m=i2 mod m），又设i1=a1m+r，i2=a2m+r,由定义有：*(i1)=(i12)mod m=(a1m+r)2 mod m =(a12m2+2 a1mr+r2)mod m=r2 mod m*(i2)=(i22)mod m=(a2m+r)2 mod m =(a22m2+2 a2mr+r2)mod m=r2 mod m *(i1)=*(

50、i2),具有等价关系的元素i1,i2经“*”运算后属于同一等价类,R对于*满足代换性质。R是 中的同余关系。第八十九页，本课件共有95页6 同态与同构同态与同构在同余关系的定义中，等价关系，对于某一运算满足代换性质，这二条均是必须的。只满足R是等价关系，而不去证明对于运算满足代换性质不能说它就是同余关系，可见下例。第九十页，本课件共有95页6 同态与同构同态与同构例：是一代数系统，其中 A=a,b,c,d，*由运算表给出定义：*abcdaaadcbbadaccbabdcdba定义A中一个等价关系R，且aRb,cRd,R=但等价关系对*运算不满足代换性质。c*a=c而c*b=b但cRb并不成立。