代数系统本篇用代数方法来研究数学结构,故又叫代数结构,它将用抽象的方法来研究集合上的关系和运算。
代数的概念和方法已经渗透到计算机科学的许多分支中,
它对程序理论,数据结构,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。
本篇讨论一些典型的代数系统及其性质（包括格）。
代数系统第五章 代 数 结 构
§ 1 代数系统的引入
§ 2 运算及其性质
§ 3 半群
§ 4 群与子群
§ 5 阿贝尔群和循环群
§ 6* 陪集与拉格朗日定理
§ 7 同态与同构
§ 1代数系统的引入
,定义,,设 Z是一个集合,f是一个函数,f,Zn?Z,则称 f为
Z中的 n元运算,整数 n称为运算的阶（元,次）。
若 n=1,则称 f,Z?Z为一元运算；
若 n=2,则 f,Z2?Z为二元运算。
本章主要讨论一元运算和二元运算。
例：（ 1）在整数 I和实数 R中,+,-,× 均为二元运算,而对
÷ 而言就不是二元运算
（ 2）在集合 Z的幂集?(z)中,?,?均为二元运算,而
,~”是一元运算；
§ 1代数系统的引入
（ 3） {命题公式 }中,∨,∧ 均为二元运算,而,?”为一元运算
（ 4） {双射函数 }中,函数的合成运算是二元运算；
二元运算常用符号,+,?,?,?,?,?,?,?等等。
,定义,,一个非空集合 A连同若干个定义在该集合上的运算 f1,f2,?.,f k所组成的系统就称为一个代数系统，
记作 <A,f1,f2,?.,f k>。
§ 1代数系统的引入
,定义,,若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。
在 f,Z2?Z二元运算的定义中,本身要求满足运算是封闭的。
例：（ 1）在正整偶数的集合 E中,对 ×,+运算是封闭的；
在正整奇数的集合中,对 × 运算是封闭的,
而对 +运算不是封闭的。
（ 2）在前例中,R,I集合中 +,-,× 运算；?(z)的元素中?,?,~,运算等均为封闭的。
§ 2运算及其性质
,定义,,设 *是集合 S上的二元运算,对任一 x,y?S有
x?y∈ S则称?运算在 S上是封闭的。
,定义,,设 *是集合 S上的二元运算,对任一 x,y?S有
x?y=y? x,则称?运算在 S上是可交换的（或者说?在 S
上满足交换律）。
§ 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）,则称运算?对?是可分配的（或称?对?满足分配律）。
§ 2运算及其性质
,定义,,设?,?是定义在集合 S上的两个可交换二元运算，如果对于任意的 x,y?S，都有：
x?(x?y)=x； x?(x?y)=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和 xn=x成立。
§ 2运算及其性质例：（ 1）在实数集合 R中,+,× 是可交换,可结合的,× 对 +
是满足分配律的,“0”对 +是等幂元素,而其它不为等幂元素,对,-”法是不可交换,不可结合的；
（ 2）在?(z)中,?,?均是可交换,可结合的,?对?,?对
均是可分配的；
(z)中任一元素,对?,?均是等幂元素。 ∴ 满足等幂律；
而?(z)中,对称差分?是可交换,可结合的。
除?(s) ={?}以外不满足等幂律。 ∵ =?,而除?
以外的 A(z)有 A?A≠A。
§ 2运算及其性质
,定义,,设 *是 S上的二元运算,对任一 x?S,则：
x1=x,x2=x*x,…x n=xn-1*x
,定理,,设 *是 S上的二元运算,且 x?S,对任一 m,n?I+
有
（ 1） xm?xn=xm+n （ 2） (xm)n=xm?n
证明：
（ 1） xm?xn= (xm?x)? x?…?x = (xm+1?x)? x?…?x
n n-1
=….= x m+n
（ 2） (xm)n= xm?…? xm= xm+m? xm?… xm=…=x m?n
n n-1
§ 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是唯一的。
§ 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? =?（空集）；
§ 2运算及其性质
（ 3） {双射函数 }中,对,?”而言，
e? =Ix（恒等函数）；
（ 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中对于 *的右零元。
§ 2运算及其性质
,定理,,若 θl和 θr分别是 Z中对于 *的左零元和右零元，于是对所有的 x?Z,可有 θl = θr =θ，
能使 θ*x=x*θ=θ。在此情况下,θ?Z是唯一的，
并称 θ是 Z中对 *的零元。
证明：方法同幺元。
例：
（ 1）在实数集合 R中，对 × 而言,,θL = θr =0
（ 2）在?(E)中，对?而言,θ? =? ；
对?而言,θ? = E ；
（ 3） {命题逻辑 }中，对 ∨ 而言,θ ∨ =T ；
对 ∧ 而言,θ ∧ = F。
§ 2运算及其性质
,定义,,设 *是 Z中的二元运算，且 Z中含幺元 e，
令 x?Z，
（ 1）若存在一 xl?Z，能使 xl *x= e，则称 xL是 x的左逆元,并且称 x是左可逆的；
（ 2）若存在一 xr?Z，能使 x* xr = e，则称 xr是 x的右逆元，并且称 x是右可逆的；
（ 3）若元素 x既是左可逆的，又是右可逆的，则称 x
是可逆的，且 x的逆元用 x-1表示。
§ 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) = xl* e = xl
∴ xr = xl
§ 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中，对,+”运算，对任一 x?R有
x-1 =-x,∵ x+（ -x） =0，加法幺元
§ 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是可约的（或称可消去的）
§ 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是可约的。
§ 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 x?5y=（ x?y） mod 5
§ 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
§ 3 半群
,定义,,一个代数系统 < S,? >，
S为非空集合,?是 S上的二元运算，如果运算?是封闭的，则称代数系统 < S,? >为广群。
,定义,,设 < S,? >是一代数系统,S为非空集合,?
是 S上的二元运算，若
(1)?运算是封闭的。
(2)?运算满足结合律，则称 < S,? >为半群。
例,<N,+>,<N,? >,<IE,+ >,< IE,?>均为半群
,定义,,对于 *运算，拥有幺元的半群 < M,* >称为含幺半群。（拟群，幺半群，独异点）。
例,<N,+,0>,<N,?,1 >均为含幺半群，
而 < IE,?>就不为幺半群。
§ 3 半群例：设 S为非空集合,? (S)是 S的幂集，
则 <? (S),?,?>,<? (S),?,S>均为含幺半群。
而 <I,max>，其中 max(x1,x2)取二者之大值；
<I,min>，其中 min(x1,x2)取二者之小值，均不为幺半群（不存在幺元）。 <N,max>则为含幺半群，其中
e =0
,定义,,设 < S,* >是一半群,T?S，且 *在 T上是封闭的，那么 < T,* >也是半群，称 < T,* >是
< S,* >的子半群。
§ 3 半群讨论定义：
（ 1）因为 *在 S上是可结合的，而 T?S且 *在 T上是封闭的，所以 *在 T上也是可结合的。
（ 2）由定义可知,∵ S?S,∴ < S,* >也是 < S,* >
的子半群（子含幺半群）。为了和其它子半群相互区别，称 < S,* >是的“平凡子半群” ;
,定义,设 <S,*,e>是一个含幺半群,T?S，且 *在 T上是封闭的，则 <T,*,e>也是一个含幺半群，
称 <T,*,e>是 <S,*,e >的子含幺半群。
§ 3 半群讨论定义：
（ 1）在幺半群中，由于幺元 e的存在，
∴ 保证在运算表中一定没有相同的行和列。
设任一 x1,x2? Z，且 x1?x2,
则 e * x1 = x1? e * x2 = x2 ；
（ 2）在 < Z,*,e>中若存在零元的话，上述性质继续存在。
例：半群 <{0,1},*>是 <{?,0,1},*>的子半群，而不是子含幺半群。
*运算由运算表定义：
§ 3 半群
* 0 1
0 0 0
1 0 1
*? 0 1
0 1
0 0 0 0
1 1 0 1
由运算表可见,<{0,1},*>中幺元为 1，而在 <{?,0,1},*>
中幺元为?。
,定理,,如果半群 < S,* >的载体 S为有限集，则必有 a?S，使 a*a=a。
§ 3 半群证明：因 < S,* >是半群，对任意的 b?S，
由 *的封闭性,b*b?S,b3?S,b4?S,…
由于 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=….=b kp*bkp
令 a=bkp，则 a*a=a。
§ 3 半群
,定理,,设 < S,* >是独异点，对于任意 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
§ 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,?>只是含幺半群而不是群。
§ 4 群与子群例：设 M= {0o,60o,120o,240o,300o,180o}表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算 *，对 M中任一元素 a,b有 a*b=图形旋转 (a+b)的角度，并规定当旋转到 360o
时即为 0o，
试验证
<M,*>是一个群。
* 0o 60o 120o 180o 240o 300o
0o 0o 60o 120o 180o 240o 300o
60o 60o 120o 180o 240o 300o 0o
120o 120o 180o 240o 300o 0o 60o
180o 180o 240o 300o 0o 60o 120o
240o 240o 300o 0o 60o 120o 180o
300o 300o 0o 60o 120o 180o 240o
§ 4 群与子群
（ 1）运算是封闭的
（ 2） *是可结合的
（ 3）幺元为 0o；
（ 4）每一个元素均有逆元：
(0o)-1= 0o,(60o)-1=300o,
(120o)-1=240o,
(180o)-1= 180o,
(240o)-1=12 0o,(300o)-1= 60o ∴ <M,*>是一个群。
§ 4 群与子群
,定义,设 <G,*>是一个群，如果 G是有限集合，则称
<G,*>为有限群，并把 |G|称为群的阶数，如果 G为无限集合，则称 <G,*>为无限群。
例,<I,+>为无限群，上例中 <M,*>为有限群，群的阶为 |M|
=6。
至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。
2.群的性质由群的定义可知,
§ 4 群与子群
（ 1）群具有半群和含幺半群所具有的所有性质；
（ 2）由于群中存在幺元,∴ 在群的运算表中一定没有相同的行（和列）
（ 3）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。
下面以定理形式介绍群的性质
§ 4 群与子群
,定理 1,若 <G,*>是一个群，则对任一 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）的证明同上。
§ 4 群与子群
,定理 2,若 <G,* >是一个群，则对任一 a,b,c?G有：
（ 1） a * b = a * c? b = c（ a是左可消去的）；
（ 2） b * a = c * a? b = c（ a是右可消去的）。
结论：在代数系统中，二元运算是可结合的，且 a是可逆的，则 a是可约的。
此定理说明群满足消去律。
§ 4 群与子群
,定理 3,一个群 < G,*>中一定不存在零元。
∵ 零元不存在逆元。
,定义,,代数系统 < G,*>中，如果存在 a?G,有
a*a=a，则称 a为等幂元。
§ 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的一个置换。
§ 4 群与子群
,定理 5,,群 < G,*>的运算表中的每一行或每一列都是 G的元素的一个置换。
证明：首先，证明运算表中的任一行或任一列所含 G中的一个元素不可能多于一次。
（反证法）如果对应于元素 a?G的那一行中有两个元素都是 c，即有
a*b1=a*b2=c，且 b1?b2
由可约性，得,b1＝ b2，这与 b1?b2矛盾。
其次，证明 G中的每一个元素都在运算表的每一行和每一列中出现。
§ 4 群与子群考察对应于元素 a?G的那一行，
设 b是 G中的任一元素由于 b=a*(a-1*b)，所以 b必定出现在对应于 a的那一行。
再由运算表中没有两行（或两列）是相同的，
所以,< G,*>的运算表中的每一行都是 G的元素的一个置换，且每一行都是不相同的。
同样，对于每一列结论同样成立。
§ 4 群与子群
3.子群
,定义,设 <G,*>是一个群，且 S?G是一个非空集合。若
<S,* >满足下列三个条件，则称 <S,* >是 <G,*>的子群：
（ 1） e是 <G,*>的幺元，且 e?S； （保持幺元）
（ 2）对任一 a?S一定有 a-1?S ； （保持逆元）
（ 3）对任一 a,b?S一定有 a*b?S 。 （运算的封闭性）
讨论定义：
（ 1）任一群 <G,*>至少可找到二个子群，即 <{e},*>和
<G,*>,为了以示区别称此二子群为平凡子群；
（ 2）除了平凡子群以外的子群称为的真子群。
§ 4 群与子群
,定义,设 <S,*>是群 <G,*>的真子群，
若不再有一个真子群 <T,*> （其中 S?T），则称 <S,*>
是 <G,*>的极大子群。
例,<I,+>是一个群，设 S={x|x是 6的倍数 },T ={y|y是 3的倍数 }，则 <S,+>,<T,+>是 <I,+>的真子群。
∵ S?T，
∴ <S,+>不是 <I,+>的极大子群。
,定理,设 < G,*>是一个群,B是 G的非空子集，如果 B是一个有限集，那么，只要运算 *在 B上是封闭的，则 < B,* >
必定是 < G,*>的子群。
§ 4 群与子群证明：设 b?B，已知 *在 B上封闭，则 b*b?B，即
b2?B,b2 *b?B,即,b3?B，
于是 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-1?B；
§ 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，
X?Y=<x1?y1,x2?y2,x3?y3,x4?y4>，
其中?的运算表如图所示：
证明 <{<0,0,0,0>,<1,1,1,1>},?>是群
<G4,? >的子群。
0 1
0 0 1
1 1 0
§ 4 群与子群证明：
§ 4 群与子群
,定理,,设 < G,*>是一个群,S是 G的非空子集，如果对于 S中的任意元素 a和 b有 a*b-1?S，则 < S,* >是
< G,*>的子群。
证明：先证,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
§ 4 群与子群
a*b=a*(b-1)-1?S，而 (b-1)-1 ＝ b
∴ a*b?S
∴ < S,* >是 < G,*>的子群例：设 <H,*>和 <K,*>都是群 <G,*>的子群，试证明
<H?K,*>也是 <G,*>的子群。
§ 5 阿贝尔群和循环群
,定义,如果群 <G,*>中运算 *是可交换的，
则称该群为阿贝尔群（或称为交换群）。
例,<I,+> 为阿贝尔群。
例：离散函数代数系统 <F,° >是阿贝尔群。
Z={1,2,3,4},F={f0,f1,f2,f3 }
1 2 3 4
2 3 4 1,f2 =
1 2 3 4
3 4 1 2,f
3 = 1 2 3 44 1 2 3,f0 = 1 2 3 41 2 3 4f =
§ 5 阿贝尔群和循环群由运算表可见：
（ 1）运算是封闭的；
（ 2）,°,可结合；
（ 3）幺元 f0 ；
（ 4）每一个元素均可逆 ;
（ 5）以主对角线为对称。
∴ <F,° >为阿贝尔群。
° f0 f1 f2 f3
f0 f0 f1 f2 f3
f1 f1 f2 f3 f0
f2 f2 f3 f0 f1
f3 f3 f0 f1 f2
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是一个群，
< G,*>是阿贝尔群的充分必要条件是对任一 a,b?G有
(a*b)*(a*b) = (a*a)*(b*b)。
证明：
（ 1）充分性,(a*b)*(a*b) = (a*a)*(b*b)? < G,*>是阿贝尔群。
对任一 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，
∴ < G,*>是阿贝尔群。
§ 5 阿贝尔群和循环群
（ 2）必要性：
< G,*>是阿贝尔群? (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
§ 5 阿贝尔群和循环群
,定义,设 <G,* >是一个群,I 是整数集合，若存在一个元素 g?G，对于 G中每一个元素 a都能表示成 gn的形式
（ n? I），则称 <G,* >是一个循环群,g称为群 <G,* >
的生成元。
例,60o就是群 < {0o,60o,120o,240o,300o,180o},*>的生成元，所以该群为循环群。
,定义,设 <G,* >是由 g 生成的循环群，若存在一个正整数 m,使 gm=e成立，则整数中最小的 m 称为生成元
g 的周期，若不存在这样的 m,则称周期为无穷大。
§ 5 阿贝尔群和循环群例：（ 1） <N,+>是一个群，生成元 g=1，而 g的周期为无穷大；
（ 2） I为整数集合。“模
m同余”是一个等价关系。
设,m=4,N4表示“模 4同余”
所产生的等价类的集合，
N4={[0],[1],[2],[3]}，定义运 +4：
[i]+4[j]=[(i+j)(mod 4)]
(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]
运算表：
§ 5 阿贝尔群和循环群由运算表可见：
（ 1）由 [0]可生成 <{[0]},+4>
（ 2）由 [1]或 [3]可生成 <{[0],[1],[2],[3]},+4>
（ 3）由 [2]可生成 <{[0],[2]},+4>
讨论定义：
（ 1）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；
§ 5 阿贝尔群和循环群
（ 2）在循环群中，生成元的周期是指 gm=e中最小的 m
（这里 m?0且 m?I+）。
,定理,每一个循环群必然是阿贝尔群。
证明：设 <G,*>是一循环群,g为生成元，
对任一 p,q?G一定存在 i,j? I（整数）使得
p=gi,q=gj，
则 p*q = gi * gj = gi+j = gj * gi =q*p 。
∴ <G,*>循环群一定是阿贝尔群。
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是由元素 g?G生成的循环群，若
< G,*>是 n阶的（即 |G|=n），则 gn=e,以致 G={g1,
g2,… g n = e},而且 n是能使 gn = e的最小正整数。
证明：
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是由元素 g?G生成的循环群，若
< G,*>是 n阶的（即 |G|=n），则 gn=e,以致 G={g1,
g2,… g n = e},而且 n是能使 gn = e的最小正整数。
证明：
§ 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|的基数。
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是由元素 g?G生成的循环群，若
< G,*>是 n阶的（即 |G|=n），则 gn=e,以致 G={g1,
g2,… g n = e},而且 n是能使 gn = e的最小正整数。
证明：
§ 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|的基数。
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
期中复习
1）命题及其表示法命题 真值 原子命题 复合命题 命题标识符 命题常量命题变元 原子变元
2）联结词否定 合取 析取 条件 双条件
3）命题公式与翻译合式公式 翻译 优先级
4）真值表与等价公式真值表 逻辑等价 子公式 定理 1-4.1
期中复习
5）重言式与蕴含式重言式（永真式） 矛盾式（永假式） 蕴含式定理 1-5.1 定理 1-5.2 定理 1-5.3 定理 1-5.4
7）范式合取范式 析取范式 主合取范式 主析取范式定理 1-7.3 定理 1-7.4
8）推理理论有效结论 P规则 T规则 CP规则等价公式表 蕴含公式表期中复习第二章 谓词逻辑
1）谓词的概念与表示谓词 谓词填式 n元谓词
2）命题函数与量词命题函数 复合命题函数 个体域 全总个体域全称量词 存在量词 特性谓词
3）谓词公式与翻译合式公式
4）变元的约束辖域 约束变元 自由变元 换名 代入期中复习
5）谓词演算的等价式与蕴含式赋值 等价 有效的（永真的） 不可满足的（永假的）
可满足的 谓词演算的等价式与蕴含式
6）前束范式前束范式 定理 2-6.1
7）谓词演算的推理理论
US UG ES EG规则期中复习第一、二章作业选讲期中复习第三章 集合与关系
1）集合的概念和表示法集合 元素 子集 真子集 空集 全集 幂集外延性原理 定理 3-1.1 定理 3-1.2 定理 3-1.3
2）集合的运算交 并 补 绝对补 对称差集合运算的性质
4）序偶与笛卡尔积序偶 三元组 n元组 笛卡尔积
5）关系及其表示期中复习关系 前域 值域 恒等关系 全域关系 空关系关系矩阵 关系图
6）关系的性质自反 对称 传递 反自反 反对称
7）复合关系和逆关系复合关系 逆关系定理 3-7.2
8）关系的闭包运算闭包定理 3-8.1----定理 3-8.5
期中复习
9）集合的划分和覆盖划分 覆盖
10）等价关系与等价类等价关系 等价类 商集定理 3-10.1----定理 3-10.4
12）序关系偏序集 盖住关系 盖住集和哈斯图极大元 极小元 最大元 最小元上界 下界 最小上界 最大下界全序 良序 拟序期中复习第四章 函数
1）函数的概念函数 定义域 值域 函数相等 函数集合满射 入射 双射
2）逆函数和复合函数逆函数 左复合恒等函数 常函数 函数复合的结合性定理 4-2.1----定理 4-2.7
期中复习第三、四章作业选讲
§ 6 同态与同构
1.代数系统的概念,
,定义,由集合和集合上的一个或多个 n元运算所组成的系统称为代数系统，用符号 ∨ =<S,f1,f2…f m>表示，其中 S为非空集合,f1,f2…f m表示 n元运算。
讨论定义：
（ 1）构成一个代数系统必须具备三个条件：
一个非空集合 S，称为载体；
在 S上的运算 f1,f2…f m,；
在 S上的运算是封闭的。
（ 2）有些书上把特异元素（常数）放在代数系统之中，形成 <S,f1,f2…f m,k> ；
§ 6 同态与同构
2.同态和同构同态和同构是讨论二个代数系统之间的关系。
,定义,设 U =<A,?>和 V =<B,*>是二个代数系统，又设 U到
V存在一个映射 f,A?B，对任一 a1,a2?A，若有 f (a1?a2)
= f (a1) * f (a2)，则称 f 是从代数系统 U到 V的同态映射。
称 U同态于 V。把 <f(A),*>称为 <A,?>的一个同态象。其中：
f(A)={x|x=f(a),a?A}?B
讨论定义：
§ 6 同态与同构
（ 1） f,A?B为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；
（ 2）对同态讲，二个代数系统的基数可以不相等，
只要满足函数的条件就行；
（ 3）上述定义可以推广到多个 n元运算的同一类型的代数系统中去。
（ 4）一个代数系统到另一个代数系统可能存在多于一个同态。
§ 6 同态与同构例：
给定二代数系统 F ={I,+},I为整数，,+”为一般加；
G = {Nm,+m }，其中，
Nm = {0,1,2…m -1},“+m,为模 m加法并定义成
x1 +m x2 = (x1 + x2) mod m 。
对任一 i?I和 m?I +，
(i) mod m 定义了除以 m所得之非负余数且 0? (i) mod m < m。
§ 6 同态与同构定义 F?G的一个函数：
f,I? Nm且有 f (i) = i ( mod m)，
(其中 i?I,f (i)? Nm ),
f (i1+i2) = (i1+i2) mod m = (i1 mod m) +m (i2 mod m),其中
i1?I,i2?I ；
i1 mod m? Nm,i2 mod m? Nm 。
则 f 是一同态函数：自变量和象点的对应，并保持运算的对应。
§ 6 同态与同构
,定义,若 f,A?B 是从 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为自同构。
§ 6 同态与同构
<F,?> 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
<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]
例：离散函数代数系统和剩余类加代数系统是同构的。
§ 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]，
运算是一一对应的；
∴ <F,?>和 <N4,+4>是二个同构的代数系统。
在实际中，把对应的元素和运算进行交换，就能得到相同的运算表。
例：试考定下列二代数系统 U和 V是否同构：
U= <{?,A,~A,E},~,?,? >,V = <{1,2,5,10},ˉ,?,? >,
其运算表如下：
§ 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
§ 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
§ 6 同态与同构定义 V 中,?,求二数的最小公倍数；?,求二数的最大公约数；,ˉ,,10被 x除所得之商。
由运算表可见：
定义一函数 f,{1,2,5,10}? {?,A,~A,E}
f (1) =?,f (2) = A,,f (5) = ~A,,f (10) = E
元素一一对应；
x
§ 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 二个代数系统同构。
若二个代数系统同构，则此二个代数系统具有完全相同的性质,所以对于同构的代数系统,只要研究其中一个代数系统,其它的代数系统的问题也就解决了,给我们研究问题带来了方便。
§ 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同构。
所以，同构关系是等价关系。
§ 6 同态与同构
,定理,设 f是从代数系统 U = < A,? >到 V = <B,* >的同态映射，
（ 1）如果 U是半群，那么在 f作用下，同态象 <f(A),*>也是半群；
（ 2）如果 U是独异点，那么在 f作用下，同态象 <f(A),*>也是独异点；
（ 3）如果 U是群，那么在 f作用下，同态象 <f(A),*>也是群；
§ 6 同态与同构证明：
§ 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,….} 。
若对二个等价类中的元素进行 +,-,?运算，则运算结果必定属于同一等价类中。
§ 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中，
二个等价类的元素对 +,-,?运算均满足代换性质，即分数集合的相等关系，对 +,-,?运算满足代换性质。
§ 6 同态与同构
,定义,设代数系统 U =< Z,* >,* 是二元运算,R是 Z中的等价关系，当且仅当对任一 x1,x2?Z? y1,y2?Z有
x1R x2? y1Ry2? x1 *y1 R x2 * y2时，则对于运算 *，等价关系 R满足代换性质（置换性质）。
,定义,设 U =< Z,* >是一代数系统,R是 Z中的等价关系，
于是对于二元运算 *，若等价关系 R满足代换性质，则称 R
是代数系统 U中的同余关系，与此相对应,R的等价类称为同余类。
§ 6 同态与同构例：在整数 I集合中 是一个同余关系，
为一代数系统,对任一定义 *运算,*(i) =(i2) mod m,(m?I+)
定义 R关系：
设 R是 I中的一个关系，当 i1 mod m = i2 mod m时，
则有 i1R i2
下面证明 (i2) mod m是一个同余关系证明：
（ 1）前面已证明：在 I中,i(i?I)模 m 等价是一个等价关系。
（ 2）对于 *运算,R满足代换性质。
mi m o d)( 2
,I Ii?
§ 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) = *(i2),具有等价关系的元素 i1,i2经,*”运算后属于同一等价类,R对于 *满足代换性质。
∴ R是 <I,* >中的同余关系。
§ 6 同态与同构在同余关系的定义中，等价关系，对于某一运算满足代换性质，这二条均是必须的。只满足 R是等价关系，而不去证明对于运算满足代换性质不能说它就是同余关系，
可见下例。
§ 6 同态与同构例,< A,* >是一代数系统，其中
A = {a,b,c,d},*由运算表给出定义：
* a b c d
a a a d c
b b a d a
c c b a b
d c d b a
定义 A中一个等价关系 R，且 aRb,cRd,
R={<a,a><b,b><a,b><b,a><c,c><d,d
><c,d><d,c>}
但等价关系对 *运算不满足代换性质。
∵ c*a=c而 c*b=b但 cRb并不成立 。
∴ R不是 A中对于 *运算的同余关系。
§ 6 同态与同构
,定理,设 <A,?>是一个代数系统,R是 A上的一个同余关系,B＝ {A1,A2,….,A r}是由 R诱导的 A上的一个划分，
那么，必定存在新的代数系统 <B,*>，它是 <A,?>的同态象。
证明：由于 R是 A上的同余关系，我们设 B上的二元运算
*为：对于任意的 Ai,Aj?B,任取 a1?Ai,a2?Aj，
如果 a1?a2?Ak，则 Ai*Aj=Ak且是唯一的。
作映射 f(a)=Ai a?Ai
显然,f是从 A到 B的满射。
x,y?A,x,y必属于 B中的某两个同余类，不妨设
§ 6 同态与同构
x?Ai,y?Aj，则 x?y必属于 B中某个同余类，不妨设
x?y?Ak，于是有：
f(x?y )= Ak=Ai*Aj=f(x)*f(y)
因此,f是由 <A,?>到 <B,*>的满同态，即 <B,*>是 <A,?>的同态象。
形象地说，一个代数系统的同态象可以看作是抽去该系统中某些元素的次要特性的情况下，对该系统的一种粗糙描述。
§ 6 同态与同构
,定理,设 f是由 <A,?>到 <B,*> 的一个同态映射，如果在 A上定义二元关系 R为,<a,b>?R当且仅当
f(a)=f(b)
那么,R是 A上的一个同余关系。
证明,首先证明 R是 A上的等价关系。
(1)R是自反的，由 f(a)=f(a),∴?a?A,<a,a>?R。
(2)R是对称的，由 f(a)=f(b)可得 f(b)=f(a)，
∴?a,b?A，由 <a,b>?R可得 <b,a>?R。
(3)R是可传递的，当 <a,b>?R且 <b,c>?R时，有
f(a)=f(b),f(b)=f(c)则 f(a)=f(c)，即有 <a,c>?R。
其次证明 R对于?运算满足代换性质
§ 6 同态与同构
<a,b>?R,<c,d>?R时，有 f(a)=f(b),f(c)=f(d)
因为,f是由 <A,?>到 <B,*> 的一个同态映射。
∴ f(a?c)=f(a)*f(c),f(b?d)=f(b)*f(d)
∴ f(a?c)= f(b?d)，即 < a?c,b?d>?R。
综上所述,R是 A上的同余关系。
代数的概念和方法已经渗透到计算机科学的许多分支中,
它对程序理论,数据结构,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。
本篇讨论一些典型的代数系统及其性质（包括格）。
代数系统第五章 代 数 结 构
§ 1 代数系统的引入
§ 2 运算及其性质
§ 3 半群
§ 4 群与子群
§ 5 阿贝尔群和循环群
§ 6* 陪集与拉格朗日定理
§ 7 同态与同构
§ 1代数系统的引入
,定义,,设 Z是一个集合,f是一个函数,f,Zn?Z,则称 f为
Z中的 n元运算,整数 n称为运算的阶（元,次）。
若 n=1,则称 f,Z?Z为一元运算；
若 n=2,则 f,Z2?Z为二元运算。
本章主要讨论一元运算和二元运算。
例：（ 1）在整数 I和实数 R中,+,-,× 均为二元运算,而对
÷ 而言就不是二元运算
（ 2）在集合 Z的幂集?(z)中,?,?均为二元运算,而
,~”是一元运算；
§ 1代数系统的引入
（ 3） {命题公式 }中,∨,∧ 均为二元运算,而,?”为一元运算
（ 4） {双射函数 }中,函数的合成运算是二元运算；
二元运算常用符号,+,?,?,?,?,?,?,?等等。
,定义,,一个非空集合 A连同若干个定义在该集合上的运算 f1,f2,?.,f k所组成的系统就称为一个代数系统，
记作 <A,f1,f2,?.,f k>。
§ 1代数系统的引入
,定义,,若对给定集合中的元素进行运算,而产生的象点仍在该集合中,则称此集合在该运算的作用下是封闭的。
在 f,Z2?Z二元运算的定义中,本身要求满足运算是封闭的。
例：（ 1）在正整偶数的集合 E中,对 ×,+运算是封闭的；
在正整奇数的集合中,对 × 运算是封闭的,
而对 +运算不是封闭的。
（ 2）在前例中,R,I集合中 +,-,× 运算；?(z)的元素中?,?,~,运算等均为封闭的。
§ 2运算及其性质
,定义,,设 *是集合 S上的二元运算,对任一 x,y?S有
x?y∈ S则称?运算在 S上是封闭的。
,定义,,设 *是集合 S上的二元运算,对任一 x,y?S有
x?y=y? x,则称?运算在 S上是可交换的（或者说?在 S
上满足交换律）。
§ 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）,则称运算?对?是可分配的（或称?对?满足分配律）。
§ 2运算及其性质
,定义,,设?,?是定义在集合 S上的两个可交换二元运算，如果对于任意的 x,y?S，都有：
x?(x?y)=x； x?(x?y)=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和 xn=x成立。
§ 2运算及其性质例：（ 1）在实数集合 R中,+,× 是可交换,可结合的,× 对 +
是满足分配律的,“0”对 +是等幂元素,而其它不为等幂元素,对,-”法是不可交换,不可结合的；
（ 2）在?(z)中,?,?均是可交换,可结合的,?对?,?对
均是可分配的；
(z)中任一元素,对?,?均是等幂元素。 ∴ 满足等幂律；
而?(z)中,对称差分?是可交换,可结合的。
除?(s) ={?}以外不满足等幂律。 ∵ =?,而除?
以外的 A(z)有 A?A≠A。
§ 2运算及其性质
,定义,,设 *是 S上的二元运算,对任一 x?S,则：
x1=x,x2=x*x,…x n=xn-1*x
,定理,,设 *是 S上的二元运算,且 x?S,对任一 m,n?I+
有
（ 1） xm?xn=xm+n （ 2） (xm)n=xm?n
证明：
（ 1） xm?xn= (xm?x)? x?…?x = (xm+1?x)? x?…?x
n n-1
=….= x m+n
（ 2） (xm)n= xm?…? xm= xm+m? xm?… xm=…=x m?n
n n-1
§ 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是唯一的。
§ 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? =?（空集）；
§ 2运算及其性质
（ 3） {双射函数 }中,对,?”而言，
e? =Ix（恒等函数）；
（ 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中对于 *的右零元。
§ 2运算及其性质
,定理,,若 θl和 θr分别是 Z中对于 *的左零元和右零元，于是对所有的 x?Z,可有 θl = θr =θ，
能使 θ*x=x*θ=θ。在此情况下,θ?Z是唯一的，
并称 θ是 Z中对 *的零元。
证明：方法同幺元。
例：
（ 1）在实数集合 R中，对 × 而言,,θL = θr =0
（ 2）在?(E)中，对?而言,θ? =? ；
对?而言,θ? = E ；
（ 3） {命题逻辑 }中，对 ∨ 而言,θ ∨ =T ；
对 ∧ 而言,θ ∧ = F。
§ 2运算及其性质
,定义,,设 *是 Z中的二元运算，且 Z中含幺元 e，
令 x?Z，
（ 1）若存在一 xl?Z，能使 xl *x= e，则称 xL是 x的左逆元,并且称 x是左可逆的；
（ 2）若存在一 xr?Z，能使 x* xr = e，则称 xr是 x的右逆元，并且称 x是右可逆的；
（ 3）若元素 x既是左可逆的，又是右可逆的，则称 x
是可逆的，且 x的逆元用 x-1表示。
§ 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) = xl* e = xl
∴ xr = xl
§ 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中，对,+”运算，对任一 x?R有
x-1 =-x,∵ x+（ -x） =0，加法幺元
§ 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是可约的（或称可消去的）
§ 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是可约的。
§ 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 x?5y=（ x?y） mod 5
§ 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
§ 3 半群
,定义,,一个代数系统 < S,? >，
S为非空集合,?是 S上的二元运算，如果运算?是封闭的，则称代数系统 < S,? >为广群。
,定义,,设 < S,? >是一代数系统,S为非空集合,?
是 S上的二元运算，若
(1)?运算是封闭的。
(2)?运算满足结合律，则称 < S,? >为半群。
例,<N,+>,<N,? >,<IE,+ >,< IE,?>均为半群
,定义,,对于 *运算，拥有幺元的半群 < M,* >称为含幺半群。（拟群，幺半群，独异点）。
例,<N,+,0>,<N,?,1 >均为含幺半群，
而 < IE,?>就不为幺半群。
§ 3 半群例：设 S为非空集合,? (S)是 S的幂集，
则 <? (S),?,?>,<? (S),?,S>均为含幺半群。
而 <I,max>，其中 max(x1,x2)取二者之大值；
<I,min>，其中 min(x1,x2)取二者之小值，均不为幺半群（不存在幺元）。 <N,max>则为含幺半群，其中
e =0
,定义,,设 < S,* >是一半群,T?S，且 *在 T上是封闭的，那么 < T,* >也是半群，称 < T,* >是
< S,* >的子半群。
§ 3 半群讨论定义：
（ 1）因为 *在 S上是可结合的，而 T?S且 *在 T上是封闭的，所以 *在 T上也是可结合的。
（ 2）由定义可知,∵ S?S,∴ < S,* >也是 < S,* >
的子半群（子含幺半群）。为了和其它子半群相互区别，称 < S,* >是的“平凡子半群” ;
,定义,设 <S,*,e>是一个含幺半群,T?S，且 *在 T上是封闭的，则 <T,*,e>也是一个含幺半群，
称 <T,*,e>是 <S,*,e >的子含幺半群。
§ 3 半群讨论定义：
（ 1）在幺半群中，由于幺元 e的存在，
∴ 保证在运算表中一定没有相同的行和列。
设任一 x1,x2? Z，且 x1?x2,
则 e * x1 = x1? e * x2 = x2 ；
（ 2）在 < Z,*,e>中若存在零元的话，上述性质继续存在。
例：半群 <{0,1},*>是 <{?,0,1},*>的子半群，而不是子含幺半群。
*运算由运算表定义：
§ 3 半群
* 0 1
0 0 0
1 0 1
*? 0 1
0 1
0 0 0 0
1 1 0 1
由运算表可见,<{0,1},*>中幺元为 1，而在 <{?,0,1},*>
中幺元为?。
,定理,,如果半群 < S,* >的载体 S为有限集，则必有 a?S，使 a*a=a。
§ 3 半群证明：因 < S,* >是半群，对任意的 b?S，
由 *的封闭性,b*b?S,b3?S,b4?S,…
由于 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=….=b kp*bkp
令 a=bkp，则 a*a=a。
§ 3 半群
,定理,,设 < S,* >是独异点，对于任意 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
§ 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,?>只是含幺半群而不是群。
§ 4 群与子群例：设 M= {0o,60o,120o,240o,300o,180o}表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算 *，对 M中任一元素 a,b有 a*b=图形旋转 (a+b)的角度，并规定当旋转到 360o
时即为 0o，
试验证
<M,*>是一个群。
* 0o 60o 120o 180o 240o 300o
0o 0o 60o 120o 180o 240o 300o
60o 60o 120o 180o 240o 300o 0o
120o 120o 180o 240o 300o 0o 60o
180o 180o 240o 300o 0o 60o 120o
240o 240o 300o 0o 60o 120o 180o
300o 300o 0o 60o 120o 180o 240o
§ 4 群与子群
（ 1）运算是封闭的
（ 2） *是可结合的
（ 3）幺元为 0o；
（ 4）每一个元素均有逆元：
(0o)-1= 0o,(60o)-1=300o,
(120o)-1=240o,
(180o)-1= 180o,
(240o)-1=12 0o,(300o)-1= 60o ∴ <M,*>是一个群。
§ 4 群与子群
,定义,设 <G,*>是一个群，如果 G是有限集合，则称
<G,*>为有限群，并把 |G|称为群的阶数，如果 G为无限集合，则称 <G,*>为无限群。
例,<I,+>为无限群，上例中 <M,*>为有限群，群的阶为 |M|
=6。
至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。
2.群的性质由群的定义可知,
§ 4 群与子群
（ 1）群具有半群和含幺半群所具有的所有性质；
（ 2）由于群中存在幺元,∴ 在群的运算表中一定没有相同的行（和列）
（ 3）在群中，每一个元素均存在逆元，所以群相对半群和含幺半群来说有一些特殊的性质。
下面以定理形式介绍群的性质
§ 4 群与子群
,定理 1,若 <G,*>是一个群，则对任一 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）的证明同上。
§ 4 群与子群
,定理 2,若 <G,* >是一个群，则对任一 a,b,c?G有：
（ 1） a * b = a * c? b = c（ a是左可消去的）；
（ 2） b * a = c * a? b = c（ a是右可消去的）。
结论：在代数系统中，二元运算是可结合的，且 a是可逆的，则 a是可约的。
此定理说明群满足消去律。
§ 4 群与子群
,定理 3,一个群 < G,*>中一定不存在零元。
∵ 零元不存在逆元。
,定义,,代数系统 < G,*>中，如果存在 a?G,有
a*a=a，则称 a为等幂元。
§ 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的一个置换。
§ 4 群与子群
,定理 5,,群 < G,*>的运算表中的每一行或每一列都是 G的元素的一个置换。
证明：首先，证明运算表中的任一行或任一列所含 G中的一个元素不可能多于一次。
（反证法）如果对应于元素 a?G的那一行中有两个元素都是 c，即有
a*b1=a*b2=c，且 b1?b2
由可约性，得,b1＝ b2，这与 b1?b2矛盾。
其次，证明 G中的每一个元素都在运算表的每一行和每一列中出现。
§ 4 群与子群考察对应于元素 a?G的那一行，
设 b是 G中的任一元素由于 b=a*(a-1*b)，所以 b必定出现在对应于 a的那一行。
再由运算表中没有两行（或两列）是相同的，
所以,< G,*>的运算表中的每一行都是 G的元素的一个置换，且每一行都是不相同的。
同样，对于每一列结论同样成立。
§ 4 群与子群
3.子群
,定义,设 <G,*>是一个群，且 S?G是一个非空集合。若
<S,* >满足下列三个条件，则称 <S,* >是 <G,*>的子群：
（ 1） e是 <G,*>的幺元，且 e?S； （保持幺元）
（ 2）对任一 a?S一定有 a-1?S ； （保持逆元）
（ 3）对任一 a,b?S一定有 a*b?S 。 （运算的封闭性）
讨论定义：
（ 1）任一群 <G,*>至少可找到二个子群，即 <{e},*>和
<G,*>,为了以示区别称此二子群为平凡子群；
（ 2）除了平凡子群以外的子群称为的真子群。
§ 4 群与子群
,定义,设 <S,*>是群 <G,*>的真子群，
若不再有一个真子群 <T,*> （其中 S?T），则称 <S,*>
是 <G,*>的极大子群。
例,<I,+>是一个群，设 S={x|x是 6的倍数 },T ={y|y是 3的倍数 }，则 <S,+>,<T,+>是 <I,+>的真子群。
∵ S?T，
∴ <S,+>不是 <I,+>的极大子群。
,定理,设 < G,*>是一个群,B是 G的非空子集，如果 B是一个有限集，那么，只要运算 *在 B上是封闭的，则 < B,* >
必定是 < G,*>的子群。
§ 4 群与子群证明：设 b?B，已知 *在 B上封闭，则 b*b?B，即
b2?B,b2 *b?B,即,b3?B，
于是 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-1?B；
§ 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，
X?Y=<x1?y1,x2?y2,x3?y3,x4?y4>，
其中?的运算表如图所示：
证明 <{<0,0,0,0>,<1,1,1,1>},?>是群
<G4,? >的子群。
0 1
0 0 1
1 1 0
§ 4 群与子群证明：
§ 4 群与子群
,定理,,设 < G,*>是一个群,S是 G的非空子集，如果对于 S中的任意元素 a和 b有 a*b-1?S，则 < S,* >是
< G,*>的子群。
证明：先证,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
§ 4 群与子群
a*b=a*(b-1)-1?S，而 (b-1)-1 ＝ b
∴ a*b?S
∴ < S,* >是 < G,*>的子群例：设 <H,*>和 <K,*>都是群 <G,*>的子群，试证明
<H?K,*>也是 <G,*>的子群。
§ 5 阿贝尔群和循环群
,定义,如果群 <G,*>中运算 *是可交换的，
则称该群为阿贝尔群（或称为交换群）。
例,<I,+> 为阿贝尔群。
例：离散函数代数系统 <F,° >是阿贝尔群。
Z={1,2,3,4},F={f0,f1,f2,f3 }
1 2 3 4
2 3 4 1,f2 =
1 2 3 4
3 4 1 2,f
3 = 1 2 3 44 1 2 3,f0 = 1 2 3 41 2 3 4f =
§ 5 阿贝尔群和循环群由运算表可见：
（ 1）运算是封闭的；
（ 2）,°,可结合；
（ 3）幺元 f0 ；
（ 4）每一个元素均可逆 ;
（ 5）以主对角线为对称。
∴ <F,° >为阿贝尔群。
° f0 f1 f2 f3
f0 f0 f1 f2 f3
f1 f1 f2 f3 f0
f2 f2 f3 f0 f1
f3 f3 f0 f1 f2
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是一个群，
< G,*>是阿贝尔群的充分必要条件是对任一 a,b?G有
(a*b)*(a*b) = (a*a)*(b*b)。
证明：
（ 1）充分性,(a*b)*(a*b) = (a*a)*(b*b)? < G,*>是阿贝尔群。
对任一 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，
∴ < G,*>是阿贝尔群。
§ 5 阿贝尔群和循环群
（ 2）必要性：
< G,*>是阿贝尔群? (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
§ 5 阿贝尔群和循环群
,定义,设 <G,* >是一个群,I 是整数集合，若存在一个元素 g?G，对于 G中每一个元素 a都能表示成 gn的形式
（ n? I），则称 <G,* >是一个循环群,g称为群 <G,* >
的生成元。
例,60o就是群 < {0o,60o,120o,240o,300o,180o},*>的生成元，所以该群为循环群。
,定义,设 <G,* >是由 g 生成的循环群，若存在一个正整数 m,使 gm=e成立，则整数中最小的 m 称为生成元
g 的周期，若不存在这样的 m,则称周期为无穷大。
§ 5 阿贝尔群和循环群例：（ 1） <N,+>是一个群，生成元 g=1，而 g的周期为无穷大；
（ 2） I为整数集合。“模
m同余”是一个等价关系。
设,m=4,N4表示“模 4同余”
所产生的等价类的集合，
N4={[0],[1],[2],[3]}，定义运 +4：
[i]+4[j]=[(i+j)(mod 4)]
(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]
运算表：
§ 5 阿贝尔群和循环群由运算表可见：
（ 1）由 [0]可生成 <{[0]},+4>
（ 2）由 [1]或 [3]可生成 <{[0],[1],[2],[3]},+4>
（ 3）由 [2]可生成 <{[0],[2]},+4>
讨论定义：
（ 1）在循环群中，由生成元的周期分为有限循环群和无限循环群二类；
§ 5 阿贝尔群和循环群
（ 2）在循环群中，生成元的周期是指 gm=e中最小的 m
（这里 m?0且 m?I+）。
,定理,每一个循环群必然是阿贝尔群。
证明：设 <G,*>是一循环群,g为生成元，
对任一 p,q?G一定存在 i,j? I（整数）使得
p=gi,q=gj，
则 p*q = gi * gj = gi+j = gj * gi =q*p 。
∴ <G,*>循环群一定是阿贝尔群。
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是由元素 g?G生成的循环群，若
< G,*>是 n阶的（即 |G|=n），则 gn=e,以致 G={g1,
g2,… g n = e},而且 n是能使 gn = e的最小正整数。
证明：
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是由元素 g?G生成的循环群，若
< G,*>是 n阶的（即 |G|=n），则 gn=e,以致 G={g1,
g2,… g n = e},而且 n是能使 gn = e的最小正整数。
证明：
§ 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|的基数。
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
§ 5 阿贝尔群和循环群
,定理,设 < G,*>是由元素 g?G生成的循环群，若
< G,*>是 n阶的（即 |G|=n），则 gn=e,以致 G={g1,
g2,… g n = e},而且 n是能使 gn = e的最小正整数。
证明：
§ 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|的基数。
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
期中复习
1）命题及其表示法命题 真值 原子命题 复合命题 命题标识符 命题常量命题变元 原子变元
2）联结词否定 合取 析取 条件 双条件
3）命题公式与翻译合式公式 翻译 优先级
4）真值表与等价公式真值表 逻辑等价 子公式 定理 1-4.1
期中复习
5）重言式与蕴含式重言式（永真式） 矛盾式（永假式） 蕴含式定理 1-5.1 定理 1-5.2 定理 1-5.3 定理 1-5.4
7）范式合取范式 析取范式 主合取范式 主析取范式定理 1-7.3 定理 1-7.4
8）推理理论有效结论 P规则 T规则 CP规则等价公式表 蕴含公式表期中复习第二章 谓词逻辑
1）谓词的概念与表示谓词 谓词填式 n元谓词
2）命题函数与量词命题函数 复合命题函数 个体域 全总个体域全称量词 存在量词 特性谓词
3）谓词公式与翻译合式公式
4）变元的约束辖域 约束变元 自由变元 换名 代入期中复习
5）谓词演算的等价式与蕴含式赋值 等价 有效的（永真的） 不可满足的（永假的）
可满足的 谓词演算的等价式与蕴含式
6）前束范式前束范式 定理 2-6.1
7）谓词演算的推理理论
US UG ES EG规则期中复习第一、二章作业选讲期中复习第三章 集合与关系
1）集合的概念和表示法集合 元素 子集 真子集 空集 全集 幂集外延性原理 定理 3-1.1 定理 3-1.2 定理 3-1.3
2）集合的运算交 并 补 绝对补 对称差集合运算的性质
4）序偶与笛卡尔积序偶 三元组 n元组 笛卡尔积
5）关系及其表示期中复习关系 前域 值域 恒等关系 全域关系 空关系关系矩阵 关系图
6）关系的性质自反 对称 传递 反自反 反对称
7）复合关系和逆关系复合关系 逆关系定理 3-7.2
8）关系的闭包运算闭包定理 3-8.1----定理 3-8.5
期中复习
9）集合的划分和覆盖划分 覆盖
10）等价关系与等价类等价关系 等价类 商集定理 3-10.1----定理 3-10.4
12）序关系偏序集 盖住关系 盖住集和哈斯图极大元 极小元 最大元 最小元上界 下界 最小上界 最大下界全序 良序 拟序期中复习第四章 函数
1）函数的概念函数 定义域 值域 函数相等 函数集合满射 入射 双射
2）逆函数和复合函数逆函数 左复合恒等函数 常函数 函数复合的结合性定理 4-2.1----定理 4-2.7
期中复习第三、四章作业选讲
§ 6 同态与同构
1.代数系统的概念,
,定义,由集合和集合上的一个或多个 n元运算所组成的系统称为代数系统，用符号 ∨ =<S,f1,f2…f m>表示，其中 S为非空集合,f1,f2…f m表示 n元运算。
讨论定义：
（ 1）构成一个代数系统必须具备三个条件：
一个非空集合 S，称为载体；
在 S上的运算 f1,f2…f m,；
在 S上的运算是封闭的。
（ 2）有些书上把特异元素（常数）放在代数系统之中，形成 <S,f1,f2…f m,k> ；
§ 6 同态与同构
2.同态和同构同态和同构是讨论二个代数系统之间的关系。
,定义,设 U =<A,?>和 V =<B,*>是二个代数系统，又设 U到
V存在一个映射 f,A?B，对任一 a1,a2?A，若有 f (a1?a2)
= f (a1) * f (a2)，则称 f 是从代数系统 U到 V的同态映射。
称 U同态于 V。把 <f(A),*>称为 <A,?>的一个同态象。其中：
f(A)={x|x=f(a),a?A}?B
讨论定义：
§ 6 同态与同构
（ 1） f,A?B为同态函数，它不单是自变量和象点的对应，还有自变量的运算和象点运算之间的对应；
（ 2）对同态讲，二个代数系统的基数可以不相等，
只要满足函数的条件就行；
（ 3）上述定义可以推广到多个 n元运算的同一类型的代数系统中去。
（ 4）一个代数系统到另一个代数系统可能存在多于一个同态。
§ 6 同态与同构例：
给定二代数系统 F ={I,+},I为整数，,+”为一般加；
G = {Nm,+m }，其中，
Nm = {0,1,2…m -1},“+m,为模 m加法并定义成
x1 +m x2 = (x1 + x2) mod m 。
对任一 i?I和 m?I +，
(i) mod m 定义了除以 m所得之非负余数且 0? (i) mod m < m。
§ 6 同态与同构定义 F?G的一个函数：
f,I? Nm且有 f (i) = i ( mod m)，
(其中 i?I,f (i)? Nm ),
f (i1+i2) = (i1+i2) mod m = (i1 mod m) +m (i2 mod m),其中
i1?I,i2?I ；
i1 mod m? Nm,i2 mod m? Nm 。
则 f 是一同态函数：自变量和象点的对应，并保持运算的对应。
§ 6 同态与同构
,定义,若 f,A?B 是从 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为自同构。
§ 6 同态与同构
<F,?> 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
<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]
例：离散函数代数系统和剩余类加代数系统是同构的。
§ 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]，
运算是一一对应的；
∴ <F,?>和 <N4,+4>是二个同构的代数系统。
在实际中，把对应的元素和运算进行交换，就能得到相同的运算表。
例：试考定下列二代数系统 U和 V是否同构：
U= <{?,A,~A,E},~,?,? >,V = <{1,2,5,10},ˉ,?,? >,
其运算表如下：
§ 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
§ 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
§ 6 同态与同构定义 V 中,?,求二数的最小公倍数；?,求二数的最大公约数；,ˉ,,10被 x除所得之商。
由运算表可见：
定义一函数 f,{1,2,5,10}? {?,A,~A,E}
f (1) =?,f (2) = A,,f (5) = ~A,,f (10) = E
元素一一对应；
x
§ 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 二个代数系统同构。
若二个代数系统同构，则此二个代数系统具有完全相同的性质,所以对于同构的代数系统,只要研究其中一个代数系统,其它的代数系统的问题也就解决了,给我们研究问题带来了方便。
§ 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同构。
所以，同构关系是等价关系。
§ 6 同态与同构
,定理,设 f是从代数系统 U = < A,? >到 V = <B,* >的同态映射，
（ 1）如果 U是半群，那么在 f作用下，同态象 <f(A),*>也是半群；
（ 2）如果 U是独异点，那么在 f作用下，同态象 <f(A),*>也是独异点；
（ 3）如果 U是群，那么在 f作用下，同态象 <f(A),*>也是群；
§ 6 同态与同构证明：
§ 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,….} 。
若对二个等价类中的元素进行 +,-,?运算，则运算结果必定属于同一等价类中。
§ 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中，
二个等价类的元素对 +,-,?运算均满足代换性质，即分数集合的相等关系，对 +,-,?运算满足代换性质。
§ 6 同态与同构
,定义,设代数系统 U =< Z,* >,* 是二元运算,R是 Z中的等价关系，当且仅当对任一 x1,x2?Z? y1,y2?Z有
x1R x2? y1Ry2? x1 *y1 R x2 * y2时，则对于运算 *，等价关系 R满足代换性质（置换性质）。
,定义,设 U =< Z,* >是一代数系统,R是 Z中的等价关系，
于是对于二元运算 *，若等价关系 R满足代换性质，则称 R
是代数系统 U中的同余关系，与此相对应,R的等价类称为同余类。
§ 6 同态与同构例：在整数 I集合中 是一个同余关系，
为一代数系统,对任一定义 *运算,*(i) =(i2) mod m,(m?I+)
定义 R关系：
设 R是 I中的一个关系，当 i1 mod m = i2 mod m时，
则有 i1R i2
下面证明 (i2) mod m是一个同余关系证明：
（ 1）前面已证明：在 I中,i(i?I)模 m 等价是一个等价关系。
（ 2）对于 *运算,R满足代换性质。
mi m o d)( 2
,I Ii?
§ 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) = *(i2),具有等价关系的元素 i1,i2经,*”运算后属于同一等价类,R对于 *满足代换性质。
∴ R是 <I,* >中的同余关系。
§ 6 同态与同构在同余关系的定义中，等价关系，对于某一运算满足代换性质，这二条均是必须的。只满足 R是等价关系，而不去证明对于运算满足代换性质不能说它就是同余关系，
可见下例。
§ 6 同态与同构例,< A,* >是一代数系统，其中
A = {a,b,c,d},*由运算表给出定义：
* a b c d
a a a d c
b b a d a
c c b a b
d c d b a
定义 A中一个等价关系 R，且 aRb,cRd,
R={<a,a><b,b><a,b><b,a><c,c><d,d
><c,d><d,c>}
但等价关系对 *运算不满足代换性质。
∵ c*a=c而 c*b=b但 cRb并不成立 。
∴ R不是 A中对于 *运算的同余关系。
§ 6 同态与同构
,定理,设 <A,?>是一个代数系统,R是 A上的一个同余关系,B＝ {A1,A2,….,A r}是由 R诱导的 A上的一个划分，
那么，必定存在新的代数系统 <B,*>，它是 <A,?>的同态象。
证明：由于 R是 A上的同余关系，我们设 B上的二元运算
*为：对于任意的 Ai,Aj?B,任取 a1?Ai,a2?Aj，
如果 a1?a2?Ak，则 Ai*Aj=Ak且是唯一的。
作映射 f(a)=Ai a?Ai
显然,f是从 A到 B的满射。
x,y?A,x,y必属于 B中的某两个同余类，不妨设
§ 6 同态与同构
x?Ai,y?Aj，则 x?y必属于 B中某个同余类，不妨设
x?y?Ak，于是有：
f(x?y )= Ak=Ai*Aj=f(x)*f(y)
因此,f是由 <A,?>到 <B,*>的满同态，即 <B,*>是 <A,?>的同态象。
形象地说，一个代数系统的同态象可以看作是抽去该系统中某些元素的次要特性的情况下，对该系统的一种粗糙描述。
§ 6 同态与同构
,定理,设 f是由 <A,?>到 <B,*> 的一个同态映射，如果在 A上定义二元关系 R为,<a,b>?R当且仅当
f(a)=f(b)
那么,R是 A上的一个同余关系。
证明,首先证明 R是 A上的等价关系。
(1)R是自反的，由 f(a)=f(a),∴?a?A,<a,a>?R。
(2)R是对称的，由 f(a)=f(b)可得 f(b)=f(a)，
∴?a,b?A，由 <a,b>?R可得 <b,a>?R。
(3)R是可传递的，当 <a,b>?R且 <b,c>?R时，有
f(a)=f(b),f(b)=f(c)则 f(a)=f(c)，即有 <a,c>?R。
其次证明 R对于?运算满足代换性质
§ 6 同态与同构
<a,b>?R,<c,d>?R时，有 f(a)=f(b),f(c)=f(d)
因为,f是由 <A,?>到 <B,*> 的一个同态映射。
∴ f(a?c)=f(a)*f(c),f(b?d)=f(b)*f(d)
∴ f(a?c)= f(b?d)，即 < a?c,b?d>?R。
综上所述,R是 A上的同余关系。
