2009-7-29 离散数学 1
第五章 代数系统的一般性质
§ 5.1 二元运算及其性质
§ 5.2 代数系统及其子代数
§ 5.3 代数系统的同态与同构
2009-7-29 离散数学 2
如：集合 Z对加、减、乘法封闭，但对除法不封闭。验证运算是否为集合 S上的二元运算，首先需要验证集合 S对该运算的封闭性。
一、二元运算的概念二元运算,设 S为集合，函数 f,S? S? S称为 S上的一个二元运算，简称为二元运算。
§ 5.1 二元运算及其性质集合对运算的封闭性,给定集合 S,如果对集合上的所有元素进行某种运算后，运算结果仍在 S中，则称集合 S对该运算封闭。
2009-7-29 离散数学 3
一、二元运算的概念（续）
常见二元运算：
(1) 设 f,N? N? N,f (<x,y>) = x + y，则 f 是集合
N上的二元运算。即自然数集合 N上的加法运算是 N上的二元运算，但减法不是。
(2) 整数集合 Z上的加、减、乘法运算是 Z上的二元运算，但除法不是。
(3) 设 Mn(R)表示所有 n阶实矩阵的集合，则矩阵的加法和乘法都是 Mn(R)上的二元运算。
2009-7-29 离散数学 4
一、二元运算的概念（续）
(4) S为任意集合,P(S)为其幂集，则 ∪,∩,?,? 都是 P(S)上的二元运算。
(5) S为集合,SS是 S上的所有函数的集合，则合成运算?是 SS上的二元运算。
n元运算,设 S为集合,n为正整数，则函数
f,S? S?…? S? S称为 S上的一个 n元运算，
简称为 n元运算。
n个
2009-7-29 离散数学 5
一、二元运算的概念（续）
n元运算通常用符号?,?,?,? … 来表示。
如,f,N? N? N，对? x,y?N,
f (<x,y>) = x + y 可简记为? (x,y) = x + y
或 x? y = x + y。
g,N? N,f (x) = y 可简记为? (x) = y。
2009-7-29 离散数学 6
一、二元运算的概念（续）
有限集上的一元、二元运算也可用运算表给出。
a1 a1? a1 a1? a2 … a1? an
a1 a2 … an
a2 a2? a1 a2? a2 … a2? an
an an? a1 an? a2 … an? an
… … … …
an?(an)
(ai )
a1? (a1)
a2? (a2)
… …
2009-7-29 离散数学 7
一、二元运算的概念（续）
例 1：设 S ={1,2,3,4}，定义 S上的二元运算如下：
x? y = (xy) mod 5,? x,y?S。
求? 的运算表。
1 2 3 4
1
2
3
4
1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1
2009-7-29 离散数学 8
如,Z上的减法不满足结合律。幂集 P(S)上的 ∪,∩,?
满足结合律。
二、二元运算的性质
1,交换律,设?是 S上的二元运算，若对? x,y?S都有 x? y = y? x，则称运算?在 S上是可交换的。
2,结合律,设?是 S上的二元运算，若对? x,y,z?S
都有 (x? y)? z = x? (y? z)，则称运算?在 S上是可结合的。
如,Z上的加法满足交换律，但减法不满足交换律。
幂集 P(S)上的 ∪,∩,? 满足交换律。
2009-7-29 离散数学 9
二、二元运算的性质（续）
3,幂等律,设?是 S上的二元运算，若对? x?S都有 x? x = x，则称运算?适合幂等律。
也即是 S中的所有元素都是幂等元。
如：幂集 P(S)上的 ∪,∩运算适合幂等律，但?运算不适合幂等律。
2009-7-29 离散数学 10
4,分配律,设?和? 是 S上的两个二元运算，若对
x,y,z?S都有 x? (y? z) = (x? y)? (x? z)
和 (y? z)? x = (y? x)? (z? x)，则称运算?
对? 适合分配律。
二、二元运算的性质（续）
如,R上的乘法对加法满足分配律，加法对乘法不满足分配律。幂集 P(S)上的 ∪ 和 ∩是相互可分配的。
2009-7-29 离散数学 11
6,消去律,设?是 S上的二元运算，若对? x,y,z?S，
满足,(1) 若 x? y = x? z且 x不是零元，则 y = z。
(2) 若 y? x = z? x且 x不是零元，则 y = z。
则称运算?满足消去律。
5,吸收律,设?和?是 S上的两个可交换的二元运算，
若对?x,y?S，都有 x? (x? y) = x 和
x? (x? y) = x,则称运算?和? 满足吸收律。
二、二元运算的性质（续）
如：幂集 P(S)上的 ∪ 和 ∩运算满足吸收律。
2009-7-29 离散数学 12
三、集合 S的特殊元
1,左幺元（右幺元）,设?是 S上的二元运算，
若存在元素 el (或 er)?S，使得对?x?S都有
el? x = x (或 x? er = x)，则称 el (或 er)是 S中关于运算?的一个左幺元（或右幺元）。
如：自然数集上的加法运算的幺元是 0，乘法运算的幺元是 1，幂集 P(S)上的 ∪ 运算和?运算的幺元是?,∩运算的幺元是 S。
若 e?S关于运算?既是左幺元又是右幺元，
则称 e为 S上关于运算?的幺元。
2009-7-29 离散数学 13
三、集合 S的特殊元（续）
设 el,er 分别是 S上关于二元运算?的左幺元和右幺元，则有 el = er = e，且 e是 S上关于二元运算?的唯一幺元。
定理 1
证明,由 el 是左幺元有,el? er = er,
由 er 是右幺元有,el? er = el,
于是有,er = el,记 er = el = e
又设 S上有幺元 e'，则有,e' = e'? e = e，
于是 e是 S上关于二元运算? 的唯一幺元。
2009-7-29 离散数学 14
如：自然数集上的加法运算无零元，乘法运算的零元是 0，幂集 P(S)上的 ∪ 运算的零元是 S,∩运算的零元是?。
三、集合 S的特殊元（续）
2,左零元（右零元）,设?是 S上的二元运算，
若存在元素?l (或?r)?S，使得对?x?S都有
l? x =?l (或 xr =?r)，则称?l (或?r)是 S
中关于运算? 的一个左零元（或右零元）。
若S关于运算?既是左零元又是右零元，
则称?为 S上关于运算?的零元。
2009-7-29 离散数学 15
三、集合 S的特殊元（续）
设?l,?r 分别是 S上关于二元运算?的左零元和右零元，则有? l =? r =?,且?是 S上关于二元运算?的唯一零元。
定理 2
证明,?lr=?l,
lr=?r,故?l =?r,令?l =?r=?，
设 S上有零元?′，则有,? ′=? ′=?，
故?是 S上关于二元运算?的唯一零元。
2009-7-29 离散数学 16
如：整数集中元素 x 的加法逆元是 - x，只有 1和 -1分别有乘法逆元 1和 -1，其他元素无乘法逆元。
三、集合 S的特殊元（续）
3,左逆元（右逆元）,设?是 S上的二元运算，
e?S是运算?的幺元，对于 x?S，若存在元素 yl (或 yr)?S，使得 yl? x = e (或 x? yr = e)，
则称 yl (或 yr)是 x 的左逆元（或右逆元）。
若 y?S 既是 x 的左逆元又是 x 的右逆元，
则称 y是 x 的逆元，并记为 x–1。
2009-7-29 离散数学 17
于是 yl = yr = y是 S上 x关于运算? 的唯一逆元。
三、集合 S的特殊元（续）
设运算?为 S上可结合的二元运算,e是? 的幺元，对于?x?S，若存在左逆元 yl 和右逆元 yr,则有 yl = yr = y，且 y是 x 的唯一逆元。
定理 3
证明,由 yl 是 x 的左逆元有,yl? x = e，
由 yr 是 x 的右逆元有,x?yr = e，
则,yl = yl? e = yl? (x? yr) = (yl? x)? yr = e? yr = yr,
又设 x有逆元 y'，则有：
y' = y'? e = y'? (x? y ) = (y'? x)? y = e? y = y，
2009-7-29 离散数学 18
1的逆元是 1，
2的逆元是 3,3的逆元是 2。
例 2：设 S ={1,2,3},S上定义的二元运算?和?如表所示，试指出 S中关于?和?存在的特殊元。
三、集合 S的特殊元（续）
1 2 3
1 1 2 3
2 2 3 1
3 3 1 2
1 2 3
1 1 1 1
2 1 2 3
3 1 3 2
解：关于?的幺元是 1,无零元，
2009-7-29 离散数学 19
1无逆元，
2的逆元是 2,3的逆元是 3。
例 2：设 S ={1,2,3},S上定义的二元运算?和?如表所示，试指出 S中关于?和?存在的特殊元。
三、集合 S的特殊元（续）
1 2 3
1 1 2 3
2 2 3 1
3 3 1 2
1 2 3
1 1 1 1
2 1 2 3
3 1 3 2
零元是 1，解：关于?的幺元是 2，
2009-7-29 离散数学 20
例 3：设?是实数集 R上的二元运算，对?x,y?R有
x? y = x + y – 2xy,说明?运算是否为可交换的、
可结合的、幂等的，然后确定关于?运算的幺元、
零元和所有可逆元素的逆元。
三、集合 S的特殊元（续）
解：
由 (x? y)? z = x + y + z – 2xy – 2xz – 2yz + 4xyz
和 x? (y? z) = x + y + z – 2xy – 2xz – 2yz + 4xyz
得,?运算是可交换的；
得,?运算是可结合的；
由 x? y = x + y – 2xy 和 y? x = y + x – 2yx
2009-7-29 离散数学 21
例 3：设?是实数集 R上的二元运算，对?x,y?R有
x? y = x + y – 2xy,说明?运算是否为可交换的、
可结合的、幂等的，然后确定关于?运算的幺元、
零元和所有可逆元素的逆元。
三、集合 S的特殊元（续）
由 x? x = x + x – 2x2 = 2x – 2x2，
不满足 对?x?R都有 x? x = x，
于是,? 运算不是幂等的；
要使 x? x = x，只有 x = 0或 1/2，
解：
2009-7-29 离散数学 22
即对?x?R，有 x + e – 2xe = x 和 x +?– 2x? =?，
例 3：设?是实数集 R上的二元运算，对?x,y?R有
x? y = x + y – 2xy,说明?运算是否为可交换的、
可结合的、幂等的，然后确定关于?运算的幺元、
零元和所有可逆元素的逆元。
三、集合 S的特殊元（续）
设 e 和?分别是幺元和零元，
对?x?R，设 y是 x的逆元，
解得 e = 0 和? = 1/2，
则 x + y – 2xy = 0
解得 y = x/(2x –1)，其中 x? 1/2。
解：
2009-7-29 离散数学 23
一、代数系统的概念
§ 5.2 代数系统及其子代数代数系统,非空集合 S和 S上的 k个运算 f1,f2,…,fk
组成的系统称为一个代数系统。
记作 < S,f1,f2,…,fk > 。
如,<N,+>,<R,+,?>,<Mn(R),+,?>,<P(S),∪,∩,~ >。
有时也在代数系统表达式中加入系统的 代数常数
(即幺元或零元 )。 如,<N,+,0>,<R,+,?,0,1>，
< Mn(R),+,?,?,E >,< P(S),∪,∩,~,?,S>。
2009-7-29 离散数学 24
注意：当代数系统 V的表达式中带有代数常数时，
子代数 V '应含有和 V 相同的代数常数。
二、子代数系统的概念子代数系统,设 V = < S,f1,f2,…,fk >是代数系统，
B? S且 B，如果 B对 f1,f2,…,fk都是封闭的，则称 V ' = < B,f1,f2,…,fk >是 V的子代数系统，简称子代数。
若 B? S，则称 V '是 V的真子代数。
2009-7-29 离散数学 25
二、子代数系统的概念（续）
又如：设,则 < A,?>是 < M2(R),?>
的真子代数。 M2(R)中关于?运算的幺元是,
A中关于?运算的幺元是,因此 < A,?,>
不是 <M2(R),?,>的子代数。
RaaA
00
0
10 01
00 01 00 01
10 01
如,< N,+ >和 < N -{0},+ >都是 < Z,+ >的子代数，
但 < N -{0},+ >不是 < Z,+,0 >的子代数。
2009-7-29 离散数学 26
因此，任何代数系统，其子代数一定存在。
二、子代数系统的概念（续）
平凡子代数,设 V = < S,f1,f2,…,fk >是代数系统，
令 B是 V中所有的代数常数构成的集合，
若 B对 f1,f2,…,fk都是封闭的，
则 < B,f1,f2,…,fk >是 V的子代数，
称这个子代数及 V本身是 V的平凡子代数。
2009-7-29 离散数学 27
因为，对?nk1,nk2?nZ，有 nk1 +nk2 = n(k1 + k2)?nZ，
并且 0 = n? 0?nZ，所以 nZ对 V的运算都是封闭的。
即 < nZ,+,0> 是 < Z,+,0>的子代数。
二、子代数系统的概念（续）
例 4：设 V = < Z,+,0>，令 nZ = { nz| z?Z },n为自然数，则 < nZ,+,0> 是 V的子代数 。
当 n = 0时,nZ = {0},<{0},+,0>是 V的平凡真子代数；
当 n = 1时,nZ = Z,< Z,+,0>是 V的平凡子代数；
当 n? 0或 1时,< nZ,+,0> 是 V的非平凡真子代数。
2009-7-29 离散数学 28
一、同态的概念
§ 5.3 代数系统的同态与同构同态,设 V1 = < S1,? >,V2 = < S2,? >是代数系统，
和?是二元运算，如果存在映射?,S1? S2
满足对?x,y?S1有?(x? y) =? (x) (y)，
则称?是 V1到 V2的同态映射，简称同态。
同态象,设?是 V1= < S1,? >到 V2= < S2,? >的同态，
则称 <? (S1),? >是 V1在?下的同态象。
2009-7-29 离散数学 29
一、同态的概念（续）
设映射?,{1,2}? {a,b,c}，
其中? (1) = a,? (2) = b，
1 2
1 1 2
2 2 2
a b c
a a b c
b b b c
c c c c
V1 = <{1,2},? > V2 = <{a,b,c},? >
则?(1? 1) =? (1) = a = a? a
=? (1) (1),同理? (1? 2) =? (1) (2)，
(2? 1) =? (2) (1),? (2? 2) =? (2) (2)。
因此,?是 V1到 V2的同态，且 V1在?下的同态象是 < {a,b},? > 。
2009-7-29 离散数学 30
二、与同态相关的概念（续）
例：设 V1 = <R,+>,V2 = <R,?>，令?,R? R，
(x) = 2x，验证?是 V1到 V2的同态映射。
(x + y) = 2(x + y) = 2x? 2y =? (x) (y)，
则?是 V1到 V2的同态，
解：对?x,y?R,有
2009-7-29 离散数学 31
一、同态的概念（续）
如,V1 = <Z,+>,V2 = <Zn,?>，其中 +为普通加法，
Zn = { 0,1,…,n –1 },?为模 n加法。
即对? x,y?Zn,有 x? y = (x + y) mod n。
令映射?,Z? Zn,? (x) = x mod n，
于是对?x,y?Z，有?(x + y) = (x + y) mod n
= (x mod n + y mod n) mod n = x mod n? y mod n
=? (x) (y),因此?是 V1到 V2的同态 。
2009-7-29 离散数学 32
二、与同态相关的概念设?是 V1= < S1,? >到 V2= < S2,? >的同态,
(2) 若?是单射的，则称?为 V1到 V2的 单同态 。
(1) 若?是满射的，则称?为 V1到 V2的 满同态 。
记为 V1 V2。~?
(3) 若?是双射的，则称?为 V1到 V2的 同构 。
记为 V1 V2。?
(4) 若 V1 = V2，则称?为 V1的 自同态 。
若?又是双射的，则称?为 V1的 自同构 。
2009-7-29 离散数学 33
当 a 1,0时,?a 是单射的,称?a 为 V的 单自同态 。
解：因为对?x,y?Z，有二、与同态相关的概念（续）
例 5：设 V = <Z,+>，给定 a?Z，令?a,Z? Z，
a (x) = ax，验证?a 是 V的自同态。
当 a = 1(或 -1)时,对? x?Z,有? 1(x) = x (或?-1(x) = -x),
而? 1和?-1都是双射的,则? 1(或?-1)为 V的自同构。
a (x + y) = a(x + y) = ax + ay =?a (x) +?a (y)，
则?a 是 V 到 V的同态，即是 V的自同态。
当 a = 0时,对? x?Z,? 0(x) = 0,称? 0为 V的 零同态 。
2009-7-29 离散数学 34
二、与同态相关的概念（续）
例 6：设 V1 = <R,+>,V2 = <R,?>，令?,R? R，
(x) = 2x，验证?是 V1到 V2的单同态。
(x + y) = 2(x + y) = 2x? 2y =? (x) (y)，
则?是 V1到 V2的同态，
其次，对于?x,y?R，当 x? y时,2x? 2y，
即? (x) (y)，
解：对?x,y?R,有从而,?是 V1到 V2的单同态。
则?为单射的，
2009-7-29 离散数学 35
三、同态概念之推广具有两个二元运算的代数系统之间的同态：
设代数系统 V1 = <S1,?,?>,V2 = <S2,?',?' >，
其中?,?,?',?'是二元运算，若 映射?,S1? S2
满足对任意的 x,y?S1,有,
(1)? (x? y) =? (x)?'? (y)，
(2)? (x? y) =? (x)?'? (y)，
则称?是 V1到 V2的同态。
2009-7-29 离散数学 36
三、同态概念之推广（续）
具有一元运算的代数系统之间的同态：
设代数系统 V1 = <S1,?,?>,V2 = <S2,?',?' >，
其中?,?'是二元运算,?,?'是一元运算，
若 映射?,S1? S2满足对任意的 x,y?S1,有,
(1)? (x? y) =? (x)?'? (y)，
(2)? (?(x)) =?' (? (x)),
则称?是 V1到 V2的同态。
例,P128
2009-7-29 离散数学 37
三、同态概念之推广（续）
具有代数常数的代数系统之间的同态：
设代数系统 V1 = <S1,?,k1>,V2 = <S2,?,k2>，
其中?,?是二元运算,k1?S1,k2?S2是代数常数。
若 映射?,S1? S2满足下列条件：
(1)? x,y?S1，有?(x? y) =? (x) (y)，
(2)? (k1) = k2，
则称?是 V1到 V2的同态。
2009-7-29 离散数学 38
三、同态概念之推广（续）
例 7：设 V1 = <R,+,0>,V2 = <R,?,1>，令?,R? R，
(x) = 2x，验证?是 V1到 V2的同态。
(x + y) = 2(x + y) = 2x? 2y =? (x) (y)，
则?是 V1到 V2的同态。
且? (0) = 1，
解：对?x,y?R,有
2009-7-29 离散数学 39
(1) 若? (?)是可交换的 (可结合的或幂等的 )，则?' (?')
在? (S1)中也是可交换的 (可结合的或幂等的 )。
四、同态的意义设 V1 = <S1,?,?>和 V2 = <S2,?',?' >是具有两个二元运算的代数系统,? 是 V1到 V2的同态，则：
(2) 若? 对?是可分配的 (可吸收的 ),则?'对?'在
(S1)中也是可分配的 (可吸收的 ) 。
(3) 若 e是 S1中关于? 的幺元,?是 S1中关于? 的零元，
则? (e)和? (?)分别是?(S1)中关于?'的幺元和零元。
若 x –1是 x关于?的逆元，则?(x –1)是? (x) 关于?'的逆元。
2009-7-29 离散数学 40
(1) 若? (?)是可交换的 (可结合的或幂等的 )，则?' (?')
在? (S1)中也是可交换的 (可结合的或幂等的 )。
四、同态的意义（续）
仅对可结合进行证明。
因为?是可结合的，所以对? x,y,z?S1，
有 (x? y)? z = x? (y? z)，则
(? (x)?'? (y))?'? (z) =? (x? y)?'? (z) =? ((x? y)? z)
于是?'在? (S1)中是可结合的。
=? (x)?'? (y? z)=? (x? (y? z)) =? (x)?' (? (y)?'? (z))
2009-7-29 离散数学 41
四、同态的意义（续）
(3) 若 e是 S1中关于? 的幺元,?是 S1中关于? 的零元，
则? (e)和? (?)分别是?(S1)中关于?'的幺元和零元。
若 x–1是 x关于? 的逆元，则?(x –1)是? (x) 关于?'的逆元。
因为对?x?S1，有 x? e = e? x = x,则?(e)?'? (x)
=? (e? x) =? (x)，
于是? (e)是?(S1)中关于?'的幺元；
且?(x)?'? (e) =? (x? e) =? (x)，
因为 x? x –1 = x –1? x = e,则?(x –1)?'? (x) =? (x –1? x)
=? (e),且?(x)?'? (x –1) =? (x? x –1) =? (e)，
于是? (x –1)是? (x) 关于?'的逆元。
第五章 代数系统的一般性质
§ 5.1 二元运算及其性质
§ 5.2 代数系统及其子代数
§ 5.3 代数系统的同态与同构
2009-7-29 离散数学 2
如：集合 Z对加、减、乘法封闭，但对除法不封闭。验证运算是否为集合 S上的二元运算，首先需要验证集合 S对该运算的封闭性。
一、二元运算的概念二元运算,设 S为集合，函数 f,S? S? S称为 S上的一个二元运算，简称为二元运算。
§ 5.1 二元运算及其性质集合对运算的封闭性,给定集合 S,如果对集合上的所有元素进行某种运算后，运算结果仍在 S中，则称集合 S对该运算封闭。
2009-7-29 离散数学 3
一、二元运算的概念（续）
常见二元运算：
(1) 设 f,N? N? N,f (<x,y>) = x + y，则 f 是集合
N上的二元运算。即自然数集合 N上的加法运算是 N上的二元运算，但减法不是。
(2) 整数集合 Z上的加、减、乘法运算是 Z上的二元运算，但除法不是。
(3) 设 Mn(R)表示所有 n阶实矩阵的集合，则矩阵的加法和乘法都是 Mn(R)上的二元运算。
2009-7-29 离散数学 4
一、二元运算的概念（续）
(4) S为任意集合,P(S)为其幂集，则 ∪,∩,?,? 都是 P(S)上的二元运算。
(5) S为集合,SS是 S上的所有函数的集合，则合成运算?是 SS上的二元运算。
n元运算,设 S为集合,n为正整数，则函数
f,S? S?…? S? S称为 S上的一个 n元运算，
简称为 n元运算。
n个
2009-7-29 离散数学 5
一、二元运算的概念（续）
n元运算通常用符号?,?,?,? … 来表示。
如,f,N? N? N，对? x,y?N,
f (<x,y>) = x + y 可简记为? (x,y) = x + y
或 x? y = x + y。
g,N? N,f (x) = y 可简记为? (x) = y。
2009-7-29 离散数学 6
一、二元运算的概念（续）
有限集上的一元、二元运算也可用运算表给出。
a1 a1? a1 a1? a2 … a1? an
a1 a2 … an
a2 a2? a1 a2? a2 … a2? an
an an? a1 an? a2 … an? an
… … … …
an?(an)
(ai )
a1? (a1)
a2? (a2)
… …
2009-7-29 离散数学 7
一、二元运算的概念（续）
例 1：设 S ={1,2,3,4}，定义 S上的二元运算如下：
x? y = (xy) mod 5,? x,y?S。
求? 的运算表。
1 2 3 4
1
2
3
4
1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1
2009-7-29 离散数学 8
如,Z上的减法不满足结合律。幂集 P(S)上的 ∪,∩,?
满足结合律。
二、二元运算的性质
1,交换律,设?是 S上的二元运算，若对? x,y?S都有 x? y = y? x，则称运算?在 S上是可交换的。
2,结合律,设?是 S上的二元运算，若对? x,y,z?S
都有 (x? y)? z = x? (y? z)，则称运算?在 S上是可结合的。
如,Z上的加法满足交换律，但减法不满足交换律。
幂集 P(S)上的 ∪,∩,? 满足交换律。
2009-7-29 离散数学 9
二、二元运算的性质（续）
3,幂等律,设?是 S上的二元运算，若对? x?S都有 x? x = x，则称运算?适合幂等律。
也即是 S中的所有元素都是幂等元。
如：幂集 P(S)上的 ∪,∩运算适合幂等律，但?运算不适合幂等律。
2009-7-29 离散数学 10
4,分配律,设?和? 是 S上的两个二元运算，若对
x,y,z?S都有 x? (y? z) = (x? y)? (x? z)
和 (y? z)? x = (y? x)? (z? x)，则称运算?
对? 适合分配律。
二、二元运算的性质（续）
如,R上的乘法对加法满足分配律，加法对乘法不满足分配律。幂集 P(S)上的 ∪ 和 ∩是相互可分配的。
2009-7-29 离散数学 11
6,消去律,设?是 S上的二元运算，若对? x,y,z?S，
满足,(1) 若 x? y = x? z且 x不是零元，则 y = z。
(2) 若 y? x = z? x且 x不是零元，则 y = z。
则称运算?满足消去律。
5,吸收律,设?和?是 S上的两个可交换的二元运算，
若对?x,y?S，都有 x? (x? y) = x 和
x? (x? y) = x,则称运算?和? 满足吸收律。
二、二元运算的性质（续）
如：幂集 P(S)上的 ∪ 和 ∩运算满足吸收律。
2009-7-29 离散数学 12
三、集合 S的特殊元
1,左幺元（右幺元）,设?是 S上的二元运算，
若存在元素 el (或 er)?S，使得对?x?S都有
el? x = x (或 x? er = x)，则称 el (或 er)是 S中关于运算?的一个左幺元（或右幺元）。
如：自然数集上的加法运算的幺元是 0，乘法运算的幺元是 1，幂集 P(S)上的 ∪ 运算和?运算的幺元是?,∩运算的幺元是 S。
若 e?S关于运算?既是左幺元又是右幺元，
则称 e为 S上关于运算?的幺元。
2009-7-29 离散数学 13
三、集合 S的特殊元（续）
设 el,er 分别是 S上关于二元运算?的左幺元和右幺元，则有 el = er = e，且 e是 S上关于二元运算?的唯一幺元。
定理 1
证明,由 el 是左幺元有,el? er = er,
由 er 是右幺元有,el? er = el,
于是有,er = el,记 er = el = e
又设 S上有幺元 e'，则有,e' = e'? e = e，
于是 e是 S上关于二元运算? 的唯一幺元。
2009-7-29 离散数学 14
如：自然数集上的加法运算无零元，乘法运算的零元是 0，幂集 P(S)上的 ∪ 运算的零元是 S,∩运算的零元是?。
三、集合 S的特殊元（续）
2,左零元（右零元）,设?是 S上的二元运算，
若存在元素?l (或?r)?S，使得对?x?S都有
l? x =?l (或 xr =?r)，则称?l (或?r)是 S
中关于运算? 的一个左零元（或右零元）。
若S关于运算?既是左零元又是右零元，
则称?为 S上关于运算?的零元。
2009-7-29 离散数学 15
三、集合 S的特殊元（续）
设?l,?r 分别是 S上关于二元运算?的左零元和右零元，则有? l =? r =?,且?是 S上关于二元运算?的唯一零元。
定理 2
证明,?lr=?l,
lr=?r,故?l =?r,令?l =?r=?，
设 S上有零元?′，则有,? ′=? ′=?，
故?是 S上关于二元运算?的唯一零元。
2009-7-29 离散数学 16
如：整数集中元素 x 的加法逆元是 - x，只有 1和 -1分别有乘法逆元 1和 -1，其他元素无乘法逆元。
三、集合 S的特殊元（续）
3,左逆元（右逆元）,设?是 S上的二元运算，
e?S是运算?的幺元，对于 x?S，若存在元素 yl (或 yr)?S，使得 yl? x = e (或 x? yr = e)，
则称 yl (或 yr)是 x 的左逆元（或右逆元）。
若 y?S 既是 x 的左逆元又是 x 的右逆元，
则称 y是 x 的逆元，并记为 x–1。
2009-7-29 离散数学 17
于是 yl = yr = y是 S上 x关于运算? 的唯一逆元。
三、集合 S的特殊元（续）
设运算?为 S上可结合的二元运算,e是? 的幺元，对于?x?S，若存在左逆元 yl 和右逆元 yr,则有 yl = yr = y，且 y是 x 的唯一逆元。
定理 3
证明,由 yl 是 x 的左逆元有,yl? x = e，
由 yr 是 x 的右逆元有,x?yr = e，
则,yl = yl? e = yl? (x? yr) = (yl? x)? yr = e? yr = yr,
又设 x有逆元 y'，则有：
y' = y'? e = y'? (x? y ) = (y'? x)? y = e? y = y，
2009-7-29 离散数学 18
1的逆元是 1，
2的逆元是 3,3的逆元是 2。
例 2：设 S ={1,2,3},S上定义的二元运算?和?如表所示，试指出 S中关于?和?存在的特殊元。
三、集合 S的特殊元（续）
1 2 3
1 1 2 3
2 2 3 1
3 3 1 2
1 2 3
1 1 1 1
2 1 2 3
3 1 3 2
解：关于?的幺元是 1,无零元，
2009-7-29 离散数学 19
1无逆元，
2的逆元是 2,3的逆元是 3。
例 2：设 S ={1,2,3},S上定义的二元运算?和?如表所示，试指出 S中关于?和?存在的特殊元。
三、集合 S的特殊元（续）
1 2 3
1 1 2 3
2 2 3 1
3 3 1 2
1 2 3
1 1 1 1
2 1 2 3
3 1 3 2
零元是 1，解：关于?的幺元是 2，
2009-7-29 离散数学 20
例 3：设?是实数集 R上的二元运算，对?x,y?R有
x? y = x + y – 2xy,说明?运算是否为可交换的、
可结合的、幂等的，然后确定关于?运算的幺元、
零元和所有可逆元素的逆元。
三、集合 S的特殊元（续）
解：
由 (x? y)? z = x + y + z – 2xy – 2xz – 2yz + 4xyz
和 x? (y? z) = x + y + z – 2xy – 2xz – 2yz + 4xyz
得,?运算是可交换的；
得,?运算是可结合的；
由 x? y = x + y – 2xy 和 y? x = y + x – 2yx
2009-7-29 离散数学 21
例 3：设?是实数集 R上的二元运算，对?x,y?R有
x? y = x + y – 2xy,说明?运算是否为可交换的、
可结合的、幂等的，然后确定关于?运算的幺元、
零元和所有可逆元素的逆元。
三、集合 S的特殊元（续）
由 x? x = x + x – 2x2 = 2x – 2x2，
不满足 对?x?R都有 x? x = x，
于是,? 运算不是幂等的；
要使 x? x = x，只有 x = 0或 1/2，
解：
2009-7-29 离散数学 22
即对?x?R，有 x + e – 2xe = x 和 x +?– 2x? =?，
例 3：设?是实数集 R上的二元运算，对?x,y?R有
x? y = x + y – 2xy,说明?运算是否为可交换的、
可结合的、幂等的，然后确定关于?运算的幺元、
零元和所有可逆元素的逆元。
三、集合 S的特殊元（续）
设 e 和?分别是幺元和零元，
对?x?R，设 y是 x的逆元，
解得 e = 0 和? = 1/2，
则 x + y – 2xy = 0
解得 y = x/(2x –1)，其中 x? 1/2。
解：
2009-7-29 离散数学 23
一、代数系统的概念
§ 5.2 代数系统及其子代数代数系统,非空集合 S和 S上的 k个运算 f1,f2,…,fk
组成的系统称为一个代数系统。
记作 < S,f1,f2,…,fk > 。
如,<N,+>,<R,+,?>,<Mn(R),+,?>,<P(S),∪,∩,~ >。
有时也在代数系统表达式中加入系统的 代数常数
(即幺元或零元 )。 如,<N,+,0>,<R,+,?,0,1>，
< Mn(R),+,?,?,E >,< P(S),∪,∩,~,?,S>。
2009-7-29 离散数学 24
注意：当代数系统 V的表达式中带有代数常数时，
子代数 V '应含有和 V 相同的代数常数。
二、子代数系统的概念子代数系统,设 V = < S,f1,f2,…,fk >是代数系统，
B? S且 B，如果 B对 f1,f2,…,fk都是封闭的，则称 V ' = < B,f1,f2,…,fk >是 V的子代数系统，简称子代数。
若 B? S，则称 V '是 V的真子代数。
2009-7-29 离散数学 25
二、子代数系统的概念（续）
又如：设,则 < A,?>是 < M2(R),?>
的真子代数。 M2(R)中关于?运算的幺元是,
A中关于?运算的幺元是,因此 < A,?,>
不是 <M2(R),?,>的子代数。
RaaA
00
0
10 01
00 01 00 01
10 01
如,< N,+ >和 < N -{0},+ >都是 < Z,+ >的子代数，
但 < N -{0},+ >不是 < Z,+,0 >的子代数。
2009-7-29 离散数学 26
因此，任何代数系统，其子代数一定存在。
二、子代数系统的概念（续）
平凡子代数,设 V = < S,f1,f2,…,fk >是代数系统，
令 B是 V中所有的代数常数构成的集合，
若 B对 f1,f2,…,fk都是封闭的，
则 < B,f1,f2,…,fk >是 V的子代数，
称这个子代数及 V本身是 V的平凡子代数。
2009-7-29 离散数学 27
因为，对?nk1,nk2?nZ，有 nk1 +nk2 = n(k1 + k2)?nZ，
并且 0 = n? 0?nZ，所以 nZ对 V的运算都是封闭的。
即 < nZ,+,0> 是 < Z,+,0>的子代数。
二、子代数系统的概念（续）
例 4：设 V = < Z,+,0>，令 nZ = { nz| z?Z },n为自然数，则 < nZ,+,0> 是 V的子代数 。
当 n = 0时,nZ = {0},<{0},+,0>是 V的平凡真子代数；
当 n = 1时,nZ = Z,< Z,+,0>是 V的平凡子代数；
当 n? 0或 1时,< nZ,+,0> 是 V的非平凡真子代数。
2009-7-29 离散数学 28
一、同态的概念
§ 5.3 代数系统的同态与同构同态,设 V1 = < S1,? >,V2 = < S2,? >是代数系统，
和?是二元运算，如果存在映射?,S1? S2
满足对?x,y?S1有?(x? y) =? (x) (y)，
则称?是 V1到 V2的同态映射，简称同态。
同态象,设?是 V1= < S1,? >到 V2= < S2,? >的同态，
则称 <? (S1),? >是 V1在?下的同态象。
2009-7-29 离散数学 29
一、同态的概念（续）
设映射?,{1,2}? {a,b,c}，
其中? (1) = a,? (2) = b，
1 2
1 1 2
2 2 2
a b c
a a b c
b b b c
c c c c
V1 = <{1,2},? > V2 = <{a,b,c},? >
则?(1? 1) =? (1) = a = a? a
=? (1) (1),同理? (1? 2) =? (1) (2)，
(2? 1) =? (2) (1),? (2? 2) =? (2) (2)。
因此,?是 V1到 V2的同态，且 V1在?下的同态象是 < {a,b},? > 。
2009-7-29 离散数学 30
二、与同态相关的概念（续）
例：设 V1 = <R,+>,V2 = <R,?>，令?,R? R，
(x) = 2x，验证?是 V1到 V2的同态映射。
(x + y) = 2(x + y) = 2x? 2y =? (x) (y)，
则?是 V1到 V2的同态，
解：对?x,y?R,有
2009-7-29 离散数学 31
一、同态的概念（续）
如,V1 = <Z,+>,V2 = <Zn,?>，其中 +为普通加法，
Zn = { 0,1,…,n –1 },?为模 n加法。
即对? x,y?Zn,有 x? y = (x + y) mod n。
令映射?,Z? Zn,? (x) = x mod n，
于是对?x,y?Z，有?(x + y) = (x + y) mod n
= (x mod n + y mod n) mod n = x mod n? y mod n
=? (x) (y),因此?是 V1到 V2的同态 。
2009-7-29 离散数学 32
二、与同态相关的概念设?是 V1= < S1,? >到 V2= < S2,? >的同态,
(2) 若?是单射的，则称?为 V1到 V2的 单同态 。
(1) 若?是满射的，则称?为 V1到 V2的 满同态 。
记为 V1 V2。~?
(3) 若?是双射的，则称?为 V1到 V2的 同构 。
记为 V1 V2。?
(4) 若 V1 = V2，则称?为 V1的 自同态 。
若?又是双射的，则称?为 V1的 自同构 。
2009-7-29 离散数学 33
当 a 1,0时,?a 是单射的,称?a 为 V的 单自同态 。
解：因为对?x,y?Z，有二、与同态相关的概念（续）
例 5：设 V = <Z,+>，给定 a?Z，令?a,Z? Z，
a (x) = ax，验证?a 是 V的自同态。
当 a = 1(或 -1)时,对? x?Z,有? 1(x) = x (或?-1(x) = -x),
而? 1和?-1都是双射的,则? 1(或?-1)为 V的自同构。
a (x + y) = a(x + y) = ax + ay =?a (x) +?a (y)，
则?a 是 V 到 V的同态，即是 V的自同态。
当 a = 0时,对? x?Z,? 0(x) = 0,称? 0为 V的 零同态 。
2009-7-29 离散数学 34
二、与同态相关的概念（续）
例 6：设 V1 = <R,+>,V2 = <R,?>，令?,R? R，
(x) = 2x，验证?是 V1到 V2的单同态。
(x + y) = 2(x + y) = 2x? 2y =? (x) (y)，
则?是 V1到 V2的同态，
其次，对于?x,y?R，当 x? y时,2x? 2y，
即? (x) (y)，
解：对?x,y?R,有从而,?是 V1到 V2的单同态。
则?为单射的，
2009-7-29 离散数学 35
三、同态概念之推广具有两个二元运算的代数系统之间的同态：
设代数系统 V1 = <S1,?,?>,V2 = <S2,?',?' >，
其中?,?,?',?'是二元运算，若 映射?,S1? S2
满足对任意的 x,y?S1,有,
(1)? (x? y) =? (x)?'? (y)，
(2)? (x? y) =? (x)?'? (y)，
则称?是 V1到 V2的同态。
2009-7-29 离散数学 36
三、同态概念之推广（续）
具有一元运算的代数系统之间的同态：
设代数系统 V1 = <S1,?,?>,V2 = <S2,?',?' >，
其中?,?'是二元运算,?,?'是一元运算，
若 映射?,S1? S2满足对任意的 x,y?S1,有,
(1)? (x? y) =? (x)?'? (y)，
(2)? (?(x)) =?' (? (x)),
则称?是 V1到 V2的同态。
例,P128
2009-7-29 离散数学 37
三、同态概念之推广（续）
具有代数常数的代数系统之间的同态：
设代数系统 V1 = <S1,?,k1>,V2 = <S2,?,k2>，
其中?,?是二元运算,k1?S1,k2?S2是代数常数。
若 映射?,S1? S2满足下列条件：
(1)? x,y?S1，有?(x? y) =? (x) (y)，
(2)? (k1) = k2，
则称?是 V1到 V2的同态。
2009-7-29 离散数学 38
三、同态概念之推广（续）
例 7：设 V1 = <R,+,0>,V2 = <R,?,1>，令?,R? R，
(x) = 2x，验证?是 V1到 V2的同态。
(x + y) = 2(x + y) = 2x? 2y =? (x) (y)，
则?是 V1到 V2的同态。
且? (0) = 1，
解：对?x,y?R,有
2009-7-29 离散数学 39
(1) 若? (?)是可交换的 (可结合的或幂等的 )，则?' (?')
在? (S1)中也是可交换的 (可结合的或幂等的 )。
四、同态的意义设 V1 = <S1,?,?>和 V2 = <S2,?',?' >是具有两个二元运算的代数系统,? 是 V1到 V2的同态，则：
(2) 若? 对?是可分配的 (可吸收的 ),则?'对?'在
(S1)中也是可分配的 (可吸收的 ) 。
(3) 若 e是 S1中关于? 的幺元,?是 S1中关于? 的零元，
则? (e)和? (?)分别是?(S1)中关于?'的幺元和零元。
若 x –1是 x关于?的逆元，则?(x –1)是? (x) 关于?'的逆元。
2009-7-29 离散数学 40
(1) 若? (?)是可交换的 (可结合的或幂等的 )，则?' (?')
在? (S1)中也是可交换的 (可结合的或幂等的 )。
四、同态的意义（续）
仅对可结合进行证明。
因为?是可结合的，所以对? x,y,z?S1，
有 (x? y)? z = x? (y? z)，则
(? (x)?'? (y))?'? (z) =? (x? y)?'? (z) =? ((x? y)? z)
于是?'在? (S1)中是可结合的。
=? (x)?'? (y? z)=? (x? (y? z)) =? (x)?' (? (y)?'? (z))
2009-7-29 离散数学 41
四、同态的意义（续）
(3) 若 e是 S1中关于? 的幺元,?是 S1中关于? 的零元，
则? (e)和? (?)分别是?(S1)中关于?'的幺元和零元。
若 x–1是 x关于? 的逆元，则?(x –1)是? (x) 关于?'的逆元。
因为对?x?S1，有 x? e = e? x = x,则?(e)?'? (x)
=? (e? x) =? (x)，
于是? (e)是?(S1)中关于?'的幺元；
且?(x)?'? (e) =? (x? e) =? (x)，
因为 x? x –1 = x –1? x = e,则?(x –1)?'? (x) =? (x –1? x)
=? (e),且?(x)?'? (x –1) =? (x? x –1) =? (e)，
于是? (x –1)是? (x) 关于?'的逆元。
