第五 代数结构

第五代数结构第1页，课件共95页，创作于2023年2月代数系统

第五章 代数结构§1 代数系统的引入§2 运算及其性质§3

半群§4

群与子群§5

阿贝尔群和循环群§6*

陪集与拉格朗日定理§7

同态与同构第2页，课件共95页，创作于2023年2月§1 代数系统的引入《定义》:设Z是一个集合,f是一个函数,f：ZnZ,则称f为Z中的n元运算,整数n称为运算的阶（元,次）。

若n=1,则称f：ZZ为一元运算；若n=2,则f：Z2Z为二元运算。

本章主要讨论一元运算和二元运算。

例：（1）在整数I和实数R中,+,-,×均为二元运算,而对÷而言就不是二元运算（2）在集合Z的幂集(z)中,,均为二元运算,而“~”是一元运算；第3页，课件共95页，创作于2023年2月§1 代数系统的引入（3）{命题公式}中,∨,∧均为二元运算,而“”为一元运算（4）{双射函数}中,函数的合成运算是二元运算；二元运算常用符号：+,,,,,,,等等。《定义》:一个非空集合A连同若干个定义在该集合上的运算f1,f2,….,fk所组成的系统就称为一个代数系统，记作<A,f1,f2,….,fk>。第4页，课件共95页，创作于2023年2月§1 代数系统的引入《定义》:若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。

在f：Z2Z二元运算的定义中,本身要求满足运算是封闭的。例：（1）在正整偶数的集合E中,对×,+运算是封闭的；

在正整奇数的集合中,对×运算是封闭的,而对+运算不是封闭的。

（2）在前例中,R,I集合中+,-,×运算；(z)的元素中,,~,运算等均为封闭的。第5页，课件共95页，创作于2023年2月§2运算及其性质《定义》:设*是集合S上的二元运算,对任一x,yS有xy∈S则称运算在S上是封闭的。《定义》:设*是集合S上的二元运算,对任一x,yS有xy=yx,则称运算在S上是可交换的（或者说在S上满足交换律）。第6页，课件共95页，创作于2023年2月§2运算及其性质《定义》:设*是集合S上的二元运算,对任一x,y,zS都有（xy）

z=x

（yz）,则称运算在S上是可结合的（或者说*在S上满足结合律）。《定义》:设和是集合S上的二个二元运算,

对任一x,y,zS有

x

（yz）=（xy）（xz）；（yz）

x=（yx）（zx）,则称运算对是可分配的（或称对满足分配律）。第7页，课件共95页，创作于2023年2月§2运算及其性质《定义》:设，是定义在集合S上的两个可交换二元运算，如果对于任意的x,yS，都有：

x(xy)=x；x(xy)=x则称运算和运算满足吸收律。《定义》:设*是S上的二元运算,若对任一xS有xx=x,则称满足等幂律。讨论定义：1)S上每一个元素均满足xx=x,才称在S上满足幂等律；2)若在S上存在元素xS有xx=x,则称x为S上的幂等元素；3)由此定义,若x是幂等元素,则有xx=x和xn=x成立。第8页，课件共95页，创作于2023年2月§2运算及其性质例：（1）在实数集合R中,+,×是可交换,可结合的,×对+是满足分配律的,“0”对+是等幂元素,而其它不为等幂元素,对“-”法是不可交换,不可结合的；

（2）在(z)中,,均是可交换,可结合的,对,对均是可分配的；

(z)中任一元素,对,均是等幂元素。∴满足等幂律；

而(z)中,对称差分是可交换,可结合的。

除(s)={}以外不满足等幂律。∵

=,而除以外的A(z)有AA≠A。第9页，课件共95页，创作于2023年2月§2运算及其性质《定义》：设*是S上的二元运算,对任一xS,则：

x1=x,x2=x*x,…xn=xn-1*x《定理》：设*是S上的二元运算,且xS,对任一m,nI+有

（1）xmxn=xm+n

（2）(xm)n=xmn

证明：（1）xmxn=(xmx)x…x=(xm+1x)x…x

n

n-1

=….=xm+n

（2）(xm)n=xm…xm=xm+mxm…xm=…=xmn

nn-1第10页，课件共95页，创作于2023年2月§2运算及其性质下面定义特异元素幺元,零元和逆元。

《定义》：设*是集合Z中的二元运算,

(1)若有一元素elZ,对任一xZ有el*x=x；则称el为Z中对于*的左幺元(左单位元素)；

(2)若有一元素erZ,对任一xZ有x*er=x；则称er为Z中对于*的右幺元（右单元元素）。《定理》：若el和er分别是Z中对于*的左幺元和右幺元,则对于每一个xZ，可有el=er=e和e*x=x*e=x，则称e为Z中关于运算*的幺元，且eZ是唯一的。第11页，课件共95页，创作于2023年2月§2运算及其性质∵el和er分别是对*的左,右左元，则有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=（空集）；第12页，课件共95页，创作于2023年2月§2运算及其性质（3）{双射函数}中,对“”而言，

e=Ix（恒等函数）；（4）{命题逻辑}中，对∨而言，e∨

=F（永假式）；对∧而言，e∧

=T（永真式）。

《定义》：设*是对集合Z中的二元运算，（1）若有一元素θlZ，且对每一个xZ有θl*x=θl，则称θl为Z中对于*的左零元；

（2）若有一元素θr

Z，且对每一个xZ有x*θr=θr

，则称θr为Z中对于*的右零元。第13页，课件共95页，创作于2023年2月§2运算及其性质《定理》：若θl和θr分别是Z中对于*的左零元和右零元，于是对所有的xZ，可有θl=θr=θ，能使θ*x=x*θ=θ。在此情况下，θZ是唯一的，并称θ是Z中对*的零元。

证明：方法同幺元。

例：（1）在实数集合R中，对×而言,，θL=θr=0（2）在(E)中，对而言，θ

=

；对而言，θ=E；（3）{命题逻辑}中，对∨而言，θ∨=T；对∧而言，θ∧

=F。第14页，课件共95页，创作于2023年2月§2运算及其性质《定义》：设*是Z中的二元运算，且Z中含幺元e，令xZ，

（1）若存在一xlZ，能使xl*x=e，则称xL是x的左逆元,并且称x是左可逆的；

（2）若存在一xr

Z，能使x*xr=e，则称xr是x的右逆元，并且称x是右可逆的；

（3）若元素x既是左可逆的，又是右可逆的，则称x是可逆的，且x的逆元用x-1表示。第15页，课件共95页，创作于2023年2月§2运算及其性质《定理》：设Z是集合，并含有幺元e

。*是定义在Z上的一个二元运算，并且是可结合的。若xZ是可逆的，则它的左逆元等于右逆元，且逆元是唯一的。

证明：（1）先证左逆元=右逆元：设xL和xr分别是xZ的左逆元和右逆元，∵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第16页，课件共95页，创作于2023年2月§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，加法幺元第17页，课件共95页，创作于2023年2月§2运算及其性质对“×”运算，对任一xR有x-1=1x（x0）∵x×1x=1，乘法幺元；（2）在函数的合成运算中,每一个双射函数都是可逆的，

f-1（f的逆关系）；（3）在所有的二元运算中,零元一定不存在逆元，∵θ*x=x*θ=θ。

《定义》设*是Z集合中的二元运算，且aZ和x,yZ，若对每一x，y有

（a*x=a*y）（x*a=y*a）（x=y），则称a是可约的（或称可消去的）第18页，课件共95页，创作于2023年2月§2运算及其性质《定理》设*是Z集合中的二元运算,且*是可结合的,若元素aZ,且对于*是可逆的,则a也是可约的。（反之不一定,即可约的不一定是可逆的。）

证明：设任一x，yZ,且有a*x=a*y，下面证明，在*可结合和a对*是可逆的条件下，a是可约的。∵*是可结合的和aZ对*是可逆的（条件给出）∴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页，课件共95页，创作于2023年2月§2运算及其性质下面举例证明，若元素是可约的，但不一定是可逆的。

例：I为整数集合，对“”运算，运算是可结合的。任何非零元素均是可约的，但除1和（-1）以外其他元素均没有逆元。1-1=1，(-1)-1=(-1)。

例：Z={0,1,2,3,4},定义Z中二个运算为，对任一x，yZ有

x+5y=（x+y）mod5x5y=（xy）mod5

第20页，课件共95页，创作于2023年2月§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没有逆元。

以上二元运算的性质均可运用到代数系统进行讨论。+501234012340123412340234013401240123*501234012340000001234024130314204321第21页，课件共95页，创作于2023年2月§3半群《定义》：一个代数系统<S,>，S为非空集合，是S上的二元运算，如果运算是封闭的，则称代数系统<S,>为广群。《定义》：设<S,>是一代数系统，S为非空集合，是S上的二元运算，若

(1)运算是封闭的。

(2)运算满足结合律，则称<S,>为半群。

例：<N,+>,<N,>,<IE,+>,<IE,>均为半群《定义》：对于*运算，拥有幺元的半群<M,*>称为含幺半群。（拟群，幺半群，独异点）。

例：<N,+,0>,<N,,1>均为含幺半群，而<IE,>就不为幺半群。第22页，课件共95页，创作于2023年2月§3半群例：设S为非空集合，

(S)是S的幂集，则<(S),,>,<(S),,S>均为含幺半群。而<I,max>，其中max(x1,x2)取二者之大值；<I,min>，其中min(x1,x2)取二者之小值，均不为幺半群（不存在幺元）。<N,max>则为含幺半群，其中e=0《定义》：设<S,*>是一半群，TS，且*在T上是封闭的，那么<T,*>也是半群，称<T,*>是

<S,*>的子半群。第23页，课件共95页，创作于2023年2月§3半群讨论定义：

（1）因为*在S上是可结合的，而TS且*在T上是封闭的，所以*在T上也是可结合的。（2）由定义可知，∵SS

，∴<S,*>也是<S,*>的子半群（子含幺半群）。为了和其它子半群相互区别，称<S,*>是的“平凡子半群”;《定义》设<S,*,e>是一个含幺半群，TS，且*在T上是封闭的，则<T,*,e>也是一个含幺半群，称<T,*,e>是<S,*,e

>的子含幺半群。第24页，课件共95页，创作于2023年2月§3半群讨论定义：

（1）在幺半群中，由于幺元e的存在，∴保证在运算表中一定没有相同的行和列。

设任一x1,x2

Z，且x1x2

，则e*x1=x1e*x2=x2

；

（2）在<Z,*,e>中若存在零元的话，上述性质继续存在。

例：半群<{0,1},*>是<{,0,1},*>的子半群，而不是子含幺半群。

*运算由运算表定义：第25页，课件共95页，创作于2023年2月§3半群

*01000101*010100001101由运算表可见：<{0,1},*>中幺元为1，而在<{,0,1},*>中幺元为。

《定理》：如果半群<S,*>的载体S为有限集，则必有aS，使a*a=a。第26页，课件共95页，创作于2023年2月§3半群证明：因<S,*>是半群，对任意的bS， 由*的封闭性，b*bS，b3S，b4S，…

由于S是有限集，必有i<j，使bi=bj

设：p=j－i，则bj=bp*bi，即：bi=bp*bi

当q≥i时，bq=bp*bq， 又因p≥1，总可以找到k≥1，使kp≥i，对S中的

bkp有bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=b3p*bkp=….=bkp*bkp

令a=bkp，则a*a=a。第27页，课件共95页，创作于2023年2月§3半群《定理》：设<S,*>是独异点，对于任意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第28页，课件共95页，创作于2023年2月§4群与子群1.群的定义《定义》设<S,*>是一代数系统，S是非空集合，*为S上的二元运算，它满足以下四个条件时，则称<S,*>为群

（1）*运算是封闭的；

（2）*运算是可结合的； （3）存在幺元e；

（4）S中每一个元素均有逆元。例：<I,+>,<Z2,+2>,<Z3,+3>等均为群（其中Z2={0,1},Z3={0,1,2}），而<N,+>,<I,>只是含幺半群而不是群。第29页，课件共95页，创作于2023年2月§4群与子群例：设M={0º,60º,120º,240º,300º,180º}表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对M中任一元素a,b有a*b=图形旋转(a+b)的角度，并规定当旋转到360º时即为0º，试验证<M,*>是一个群。*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页，课件共95页，创作于2023年2月§4群与子群（1）运算是封闭的（2）*是可结合的（3）幺元为0º

；（4）每一个元素均有逆元：(0º)-1=0º,(60º)-1=300º,(120º)-1=240º,(180º)-1=180º,(240º)-1=120º,(300º)-1=60º

∴<M,*>是一个群。第31页，课件共95页，创作于2023年2月§4群与子群《定义》设<G,*>是一个群，如果G是有限集合，则称<G,*>为有限群，并把|G|称为群的阶数，如果G为无限集合，则称<G,*>为无限群。

例：<I,+>为无限群，上例中<M,*>为有限群，群的阶为|M|=6。

至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。2.群的性质

由群的定义可知:第32页，课件共95页，创作于2023年2月§4群与子群（1）群具有半群和含幺半群所具有的所有性质；（2）由于群中存在幺元，∴在群的运算表中一定没有相同的行（和列）（3）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。

下面以定理形式介绍群的性质第33页，课件共95页，创作于2023年2月§4群与子群《定理1》若<G,*>是一个群，则对任一a,bG有：

（1）存在唯一的元素xG

，使a*x=b；（2）存在唯一的元素yG

，使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页，课件共95页，创作于2023年2月§4群与子群《定理2》若<G,*>是一个群，则对任一a,b,cG有：（1）a*b=a*cb=c（a是左可消去的）；

（2）b*a=c*ab=c（a是右可消去的）。结论：在代数系统中，二元运算是可结合的，且a是可逆的，则a是可约的。

此定理说明群满足消去律。第35页，课件共95页，创作于2023年2月§4群与子群《定理3》一个群<G,*>中一定不存在零元。∵零元不存在逆元。

《定义》：代数系统<G,*>中，如果存在aG,有a*a=a，则称a为等幂元。第36页，课件共95页，创作于2023年2月§4群与子群《定理4》一个群中，除了幺元e之外，不存在其它等幂元素。

证明：若任一aG

，有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页，课件共95页，创作于2023年2月§4群与子群《定理5》：群<G,*>的运算表中的每一行或每一列都是G的元素的一个置换。证明：首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。（反证法）如果对应于元素aG的那一行中有两个元素都是c，即有 a*b1=a*b2=c，且b1b2

由可约性，得：b1＝b2，这与b1b2矛盾。其次，证明G中的每一个元素都在运算表的每一行和每一列中出现。第38页，课件共95页，创作于2023年2月§4群与子群考察对应于元素aG的那一行，设b是G中的任一元素由于b=a*(a-1*b)，所以b必定出现在对应于a的那一行。再由运算表中没有两行（或两列）是相同的，所以，<G,*>的运算表中的每一行都是G的元素的一个置换，且每一行都是不相同的。同样，对于每一列结论同样成立。第39页，课件共95页，创作于2023年2月§4群与子群3.子群《定义》设<G,*>是一个群，且SG是一个非空集合。若<S,*>满足下列三个条件，则称<S,*>是<G,*>的子群：

（1）e是<G,*>的幺元，且eS；（保持幺元）

（2）对任一aS一定有a-1S

；（保持逆元）

（3）对任一a,bS一定有a*bS

。（运算的封闭性）讨论定义：

（1）任一群<G,*>至少可找到二个子群，即<{e},*>和<G,*>，为了以示区别称此二子群为平凡子群；

（2）除了平凡子群以外的子群称为的真子群。第40页，课件共95页，创作于2023年2月§4群与子群《定义》设<S,*>是群<G,*>的真子群，若不再有一个真子群<T,*>（其中ST），则称<S,*>是<G,*>的极大子群。例：<I,+>是一个群，设S={x|x是6的倍数}，T={y|y是3的倍数}，则<S,+>,<T,+>是<I,+>的真子群。∵ST，∴<S,+>不是<I,+>的极大子群。《定理》设<G,*>是一个群，B是G的非空子集，如果B是一个有限集，那么，只要运算*在B上是封闭的，则<B,*>必定是<G,*>的子群。第41页，课件共95页，创作于2023年2月§4群与子群证明：设bB，已知*在B上封闭，则b*bB，即

b2B，b2

*bB，即：b3B， 于是b，b2，b3……均在B中。 由于B是有限集，∴必存在正整数i和j，i<j,

使得：bi=bj

即：bi=bi*bj-i

由此可说明bj-i是<G,*>中的幺元，且这个幺元也在子集B中。如果j-i>1，那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，且bj-i-1B；第42页，课件共95页，创作于2023年2月§4群与子群如果j-i=1，那么由bi=bi*b可知b就是幺元，且以自身为逆元。因此，<B,*>是<G,*>的一个子群。例：设G4={p=<p1,p2,p3,p4>|pi{0,1}}，是上的二元运算，定义为，对任意X=<x1,x2,x3,x4>，Y=<y1,y2,y3,y4>G4，XY=<x1y1,x2y2,x3y3,x4y4>，其中的运算表如图所示：证明<{<0,0,0,0>,<1,1,1,1>},>是群<G4,>的子群。01001110第43页，课件共95页，创作于2023年2月§4群与子群证明：第44页，课件共95页，创作于2023年2月§4群与子群《定理》:设<G,*>是一个群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1S，则<S,*>是

<G,*>的子群。证明：先证，G中的幺元e也是S中的幺元。 任取aS，a*a-1S，而a*a-1＝e，∴eS

再证，每个元素都有逆元。又e*a-1S，即a-1S。 最后说明，*对S是封闭的。 a,bS，因b-1S，∴(b-1)-1S第45页，课件共95页，创作于2023年2月§4群与子群

a*b=a*(b-1)-1S，而(b-1)-1＝b∴a*bS

∴<S,*>是<G,*>的子群例：设<H,*>和<K,*>都是群<G,*>的子群，试证明

<HK,*>也是<G,*>的子群。第46页，课件共95页，创作于2023年2月§5阿贝尔群和循环群《定义》如果群<G,*>中运算*是可交换的，则称该群为阿贝尔群（或称为交换群）。例：<I,+>为阿贝尔群。

例：离散函数代数系统<F,°>是阿贝尔群。Z={1,2,3,4}，F={f0,f1,f2,f3

}12342341,f2=12343412,f3=12344123,f0=12341234

f

=第47页，课件共95页，创作于2023年2月§5阿贝尔群和循环群由运算表可见：（1）运算是封闭的；（2）“°”可结合；（3）幺元f0

；（4）每一个元素均可逆;（5）以主对角线为对称。∴<F,°>为阿贝尔群。

°f0f1

f2f3f0f0f1

f2f3f1f1

f2f3f0f2

f2f3f0f1f3f3f0f1f2第48页，课件共95页，创作于2023年2月§5阿贝尔群和循环群《定理》设<G,*>是一个群，

<G,*>是阿贝尔群的充分必要条件是对任一a,bG有(a*b)*(a*b)=(a*a)*(b*b)。证明：（1）充分性：(a*b)*(a*b)=(a*a)*(b*b)<G,*>是阿贝尔群。

对任一a,bG有(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，∴<G,*>是阿贝尔群。第49页，课件共95页，创作于2023年2月§5阿贝尔群和循环群（2）必要性：

<G,*>是阿贝尔群

(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第50页，课件共95页，创作于2023年2月§5阿贝尔群和循环群《定义》设<G,*>是一个群，I是整数集合，若存在一个元素gG，对于G中每一个元素a都能表示成gn的形式（nI），则称<G,*>是一个循环群，g称为群<G,*>的生成元。

例：60º就是群<{0º,60º,120º,240º,300º,180º},*>的生成元，所以该群为循环群。

《定义》设<G,*>是由g生成的循环群，若存在一个正整数m，使gm=e成立，则整数中最小的m称为生成元g的周期，若不存在这样的m，则称周期为无穷大。第51页，课件共95页，创作于2023年2月§5阿贝尔群和循环群例：（1）<N,+>是一个群，生成元g=1，而g的周期为无穷大；

（2）I为整数集合。“模m同余”是一个等价关系。设：m=4，N4表示“模4同余”所产生的等价类的集合，N4={[0],[1],[2],[3]}，定义运+4：[i]+4[j]=[(i+j)(mod4)](i,j=0,1,2,3)则：<N4,+4>是群+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页，课件共95页，创作于2023年2月§5阿贝尔群和循环群由运算表可见：（1）由[0]可生成<{[0]},+4>（2）由[1]或[3]可生成<{[0],[1],[2],[3]},+4>（3）由[2]可生成<{[0],[2]},+4>讨论定义：

（1）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；第53页，课件共95页，创作于2023年2月§5阿贝尔群和循环群（2）在循环群中，生成元的周期是指gm=e中最小的m

（这里m0且mI+）。《定理》每一个循环群必然是阿贝尔群。

证明：设<G,*>是一循环群，g为生成元，对任一p,qG一定存在i,jI（整数）使得p=gi,q=gj，则p*q=gi*gj=gi+j=gj*gi=q*p。

∴<G,*>循环群一定是阿贝尔群。第54页，课件共95页，创作于2023年2月§5阿贝尔群和循环群《定理》设<G,*>是由元素gG生成的循环群，若

<G,*>是n阶的（即|G|=n），则gn=e，以致G={g1,g2,…gn=e}

，而且n是能使gn=e的最小正整数。证明：

第55页，课件共95页，创作于2023年2月§5阿贝尔群和循环群《定理》设<G,*>是由元素gG生成的循环群，若

<G,*>是n阶的（即|G|=n），则gn=e，以致G={g1,g2,…gn=e}

，而且n是能使gn=e的最小正整数。证明：

第56页，课件共95页，创作于2023年2月§5阿贝尔群和循环群例：<G,*>为一群,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,*>的阶，即|G|的基数。*abcdaabcdbbadcccdbaddcab第57页，课件共95页，创作于2023年2月§5阿贝尔群和循环群《定理》设<G,*>是由元素gG生成的循环群，若

<G,*>是n阶的（即|G|=n），则gn=e，以致G={g1,g2,…gn=e}

，而且n是能使gn=e的最小正整数。证明：

第58页，课件共95页，创作于2023年2月§5阿贝尔群和循环群例：<G,*>为一群,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,*>的阶，即|G|的基数。*abcdaabcdbbadcccdbaddcab第59页，课件共95页，创作于2023年2月期中复习1）命题及其表示法命题真值原子命题复合命题命题标识符命题常量命题变元原子变元2）联结词否定合取析取条件双条件3）命题公式与翻译合式公式翻译优先级4）真值表与等价公式真值表逻辑等价子公式定理1-4.1第60页，课件共95页，创作于2023年2月期中复习5）重言式与蕴含式重言式（永真式）矛盾式（永假式）蕴含式定理1-5.1定理1-5.2定理1-5.3定理1-5.47）范式合取范式析取范式主合取范式主析取范式定理1-7.3定理1-7.48）推理理论有效结论P规则T规则CP规则等价公式表蕴含公式表第61页，课件共95页，创作于2023年2月期中复习第二章 谓词逻辑1）谓词的概念与表示谓词谓词填式n元谓词2）命题函数与量词命题函数复合命题函数个体域全总个体域全称量词存在量词特性谓词3）谓词公式与翻译合式公式4）变元的约束辖域约束变元自由变元换名代入第62页，课件共95页，创作于2023年2月期中复习5）谓词演算的等价式与蕴含式赋值等价有效的（永真的）不可满足的（永假的）可满足的谓词演算的等价式与蕴含式6）前束范式前束范式定理2-6.17）谓词演算的推理理论USUGESEG规则第63页，课件共95页，创作于2023年2月期中复习第一、二章作业选讲第64页，课件共95页，创作于2023年2月期中复习第三章 集合与关系1）集合的概念和表示法集合元素子集真子集空集全集幂集外延性原理定理3-1.1定理3-1.2定理3-1.32）集合的运算交并补绝对补对称差集合运算的性质4）序偶与笛卡尔积序偶三元组n元组笛卡尔积5）关系及其表示第65页，课件共95页，创作于2023年2月期中复习关系前域值域恒等关系全域关系空关系关系矩阵关系图6）关系的性质自反对称传递反自反反对称7）复合关系和逆关系复合关系逆关系定理3-7.28）关系的闭包运算闭包定理3-8.1----定理3-8.5第66页，课件共95页，创作于2023年2月期中复习9）集合的划分和覆盖划分覆盖10）等价关系与等价类等价关系等价类商集定理3-10.1----定理3-10.412）序关系偏序集盖住关系盖住集和哈斯图极大元极小元最大元最小元上界下界最小上界最大下界全序良序拟序第67页，课件共95页，创作于2023年2月期中复习第四章 函数1）函数的概念函数定义域值域函数相等函数集合满射入射双射2）逆函数和复合函数逆函数左复合恒等函数常函数函数复合的结合性定理4-2.1----定理4-2.7第68页，课件共95页，创作于2023年2月期中复习第三、四章作业选讲第69页，课件共95页，创作于2023年2月§6同态与同构1.代数系统的概念：《定义》由集合和集合上的一个或多个n元运算所组成的系统称为代数系统，用符号∨=<S,f1,f2…fm>表示，其中S为非空集合，f1,f2…fm表示n元运算。

讨论定义：（1）构成一个代数系统必须具备三个条件：

•一个非空集合S，称为载体；

•在S上的运算f1,f2…fm,；

•在S上的运算是封闭的。

（2）有些书上把特异元素（常数）放在代数系统之中，形成<S,f1,f2…fm,k>；

第70页，课件共95页，创作于2023年2月§6同态与同构2.同态和同构

同态和同构是讨论二个代数系统之间的关系。《定义》设U=<A,>和V=<B,*>是二个代数系统，又设U到V存在一个映射f:AB，对任一a1,a2A，若有f(a1a2)=f(a1)*f(a2)，则称f是从代数系统U到V的同态映射。称U同态于V。把<f(A),*>称为<A,>的一个同态象。其中：

f(A)={x|x=f(a)，aA}B

讨论定义：第71页，课件共95页，创作于2023年2月§6同态与同构

（1）f:AB为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；

（2）对同态讲，二个代数系统的基数可以不相等，只要满足函数的条件就行；

（3）上述定义可以推广到多个n元运算的同一类型的代数系统中去。（4）一个代数系统到另一个代数系统可能存在多于一个同态。第72页，课件共95页，创作于2023年2月§6同态与同构例：给定二代数系统F={I,+}，I为整数，“+”为一般加；

G={Nm,+m}，其中，Nm={0,1,2…m-1},“+m”为模m加法并定义成

x1+mx2=(x1+x2)modm。对任一iI和mI

+，

(i)modm定义了除以m所得之非负余数且0(i)modm<m。第73页，课件共95页，创作于2023年2月§6同态与同构定义FG的一个函数：f:INm且有f(i)=i(modm)，

(其中iI，f(i)

Nm),f(i1+i2)=(i1+i2)modm=(i1modm)+m(i2modm)，其中i1I,i2I；

i1modmNm,i2modmNm

。则f是一同态函数：自变量和象点的对应，并保持运算的对应。第74页，课件共95页，创作于2023年2月§6同态与同构《定义》若f:AB是从U=<A,>

到V=<B,*>的同态，于是有：

（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页，课件共95页，创作于2023年2月§6同态与同构

<F,>f=1234

2341

f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f2<N4,+4>+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页，课件共95页，创作于2023年2月§6同态与同构定义一函数h:FN4，h(fi)=[i]，其中i{0,1,2,3}，元素一一对应；

h(fi

fj)=h(fi)+4h(fj)=[i]+4[j]，运算是一一对应的；∴<F,>和<N4,+4>是二个同构的代数系统。在实际中，把对应的元素和运算进行交换，就能得到相同的运算表。例：试考定下列二代数系统U和V是否同构：U=<{,A,~A,E},~,,>，V=<{1,2,5,10},¯,,>,其运算表如下：

第77页，课件共95页，创作于2023年2月§6同态与同构S~SEA~A~AAEA~AEA~AEAAAEE~A~AE~AEEEEEEA~AEAAA~A~A~AEA~AE第78页，课件共95页，创作于2023年2月§6同态与同构X¯1102552101X12510112510222101055105101010101010125101111121212511551012510第79页，课件共95页，创作于2023年2月§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页，课件共95页，创作于2023年2月§6同态与同构对任一

a,b{1,2,5,10}有f(¯)=~f(a)af(ab)=f(a)f(b)

f(ab)=f(a)f(b)运算一一对应。

∴f是一双射函数，U和V二个代数系统同构。

若二个代数系统同构，则此二个代数系统具有完全相同的性质,所以对于同构的代数系统,只要研究其中一个代数系统,其它的代数系统的问题也就解决了,给我们研究问题带来了方便。

第81页，课件共95页，创作于2023年2月§6同态与同构《定理》代数系统中的同构关系是一个等价关系。证：（1）自反性：因为任何一个代数系统可以通过恒等映射与它自身同构； （2）对称性：设U和V同构且有对应的同构映射f，f是双射函数，f的逆是V到U的同构映射，即V和U同构； （3）传递性：设f是U到V的同构映射，g是V到W的同构映射，因为f和g是双射函数，fg是U到W的同构映射。即U和W同构。所以，同构关系是等价关系。第82页，课件共95页，创作于2023年2月§6同态与同构《定理》设f是从代数系统U=<A,>到V=<B,*>的同态映射，（1）如果U是半群，那么在f作用下，同态象<f(A),*>也是半群；（2）如果U是独异点，那么在f作用下，同态象<f(A),*>也是独异点；（3）如果U是群，那么在f作用下，同态象<f(A),*>也是群；第83页，课件共95页，创作于2023年2月§6同态与同构证明：第84页，课件共95页，创作于2023年2月§6同态与同构3.同余关系：

这是讨论同一代数系统中的关系。

同余关系是代数系统的集合中的等价关系，在运算的作用下，能保持运算的等价类，同余关系是相等关系的推广。

在介绍同余关系之前先看一个例子。例：设<F,+,-,>是一代数系统,其中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页，课件共95页，创作于2023年2月§6同态与同构如：1/2+1/3=(1/2+2/6)=(2/4+1/3)[5/6];1/21/3=(1/22/6)=(2/41/3)[1/6];1/2–1/3=(1/2–2/6)=(2/4–1/3)[1/6]。∴在F中，二个等价类的元素对+,-,运算均满足代换性质，即分数集合的相等关系，对+,-,运算满足代换性质。第86页，课件共95页，创作于2023年2月§6同态与同构《定义》设代数系统U=<Z,*>,*是二元运算，R是Z中的等价关系，当且仅当对任一x1,x2Zy1,y2Z有

x1Rx2y1Ry2x1*y1R

x2*

y2时，则对于运算*，等价关系R满足代换性质（置换性质）。

《定义》设U=<Z,*>是一代数系统，R是