null
《离散数学》课件
第五章 代数结构
《离散数学》课件
第五章 代数结构
夏 侯 士 戟
电子科技大学自动化工程学院 主楼C2-508
xiahousj@uestc.edu.cn 028-61830313
null 在一个集合上定义一个或多个运算,就形成了一个代数运算系统,或称代数系统。
代数结构是研究代数系统的一般性质及各种特殊代数系统的学科，其理论和方法不仅对其它数学学科产生着深远的影响，在计算机科学领域也有着广泛的应用。第五章 代数结构null 一个代数系统需要满足下面三个条件：
（1）有一个非空集合S；
（2）有一些建立在集合S上的运算；
（3）这些运算在集合S上是封闭的。
上述三个条件说明如下：
集合S上的元素一般讲是一些经过抽象的元素, 如自然数、实数、字母、字符串等。集合S给出了代数系统所研究的客体的范围。
运算的概念具有一定的广泛性和抽象性, 不仅包括常见的算术运算(+,-,×,÷), 还包括抽象的运算, 如两个字符串的“并置”等, 也包括任意定义的运算。“运算”是代数系统对其研究客体加工的工具。
集合S中的元素经某一运算后它的结果仍在S中, 则称此运算在集合S上是封闭的。二元运算及其性质null例:① 一个在整数集Z上且带有加法运算的系统
构成了一个代数系统< Z, + >
∵Z={…-3,-2,-1,0,1,2,3, …}且有集合Z上
的运算“+”, 这个加法运算对Z是封闭的
②一个在实数集R上且带有两个二元运算“+”
与“×”的系统构成一个代数系统< R, +,×>
∵ R是一个集合, 在R上的两个运算它们均
是封闭的。
定义：
设S为集合，函数 f : S×S →S 称为S上的二元运算，简称为二元运算。
例如： f :N × N →N，f (
)= x + y 为自然数集合N上的二元运算，即普通的加法运算。null考虑： f: N × N → N，f ()=x-y 呢？
验证一个运算是否为集合S上的二元运算需考虑两点：
(1) S中任两个元素都能进行这种运算，且运算
结果唯一。
(2) S中任意两个元素的运算结果都属于S，即S
对该运算是封闭的。
考虑:除法运算是否是实数
集R上的二元运算呢?不是
∵0不能做除法运算。
集合R-{0}可以定义除法运算。 二元运算及其性质null例： 考察下列运算是否是指定集合上二元运算?
(1) 自然数集合N上的加、减、乘、除。
(2) 整数集合Z上的加、减、乘、除。
(3) 非零实数集 R*上的加、减、乘、除。
(4) n 阶实矩阵上的加、乘。
(5) 集合S的幂集上的∪、∩ 、-、 。
(6) 集合S上的所有函数的集 SS上的复合运算。
SS = f f: S S
注意:通常用 , *,·,…等符号表示二元运算,称为算符
如：设f: S×S → S 称为S上的二元运算，对于任意的x,y∈S，如果x与y的运算结果是 z，即 f()=z, 可利用算符 简记为
x y=znull例： 正整数集合Z+上的加法运算是一个二元运算, 下列运算均是Z+的子集，下列加法运算在这些子集上是二元运算吗? 说明理由。
(1) S1 = n n 是 15 的因子
(2) S2 = n n 是 15 的倍数
(3) S3 = n 6 整除 n，而 24 整除 n2
解: (1) 加法运算在S1 上不封闭。因为3∈ S1 , 5∈ S1 ,
但 3 + 5 = 8 S1 , ∴不是二元运算
(2) 加法运算在S2 上是封闭的。其证明如下：
对于任意n1 , n2∈ S2 ,设n1 =15 k1, n2 =15 k2
(k1, k2∈ Z+ )则
n1 + n2=15 k1+15 k2 =15(k1+ k2 ) (k1+ k2 ∈ Z+ )
∴ n1 + n2 ∈ S2 ∴ 是二元运算null例： 正整数集合Z+上的加法运算是一个二元运算, 下列运算均是Z+的子集，加法运算在这些子集上是二元运算吗? 说明理由。
(3) S3 = n 6 整除 n，而 24 整除 n2
解: (3) 加法运算在S3 上是封闭的。其证明如下：
对于任意n1 , n2∈ S3 ,设n1 =6 k1, n2 =6 k2
(k1, k2∈ Z+ )则
n1 + n2=6 k1+6 k2 =6(k1+ k2 ) (k1+ k2 ∈ Z+ )
∴ n1 + n2 能被6整除
又(n1 + n2)2 = n12 + 2n1 n2 +n22 ,根据
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
意, n12 能被24整除,n22能被24整除,而 2n1n2= 26k16k2 =24 (3k1k2)
也能被24整除,因此(n1 + n2)2能被24整除
由此知 n1 + n2 ∈ S3 ∴ 是二元运算 null定义： 设S为集合，n为正整数，则函数
f : S×S ×… ×S →S
称为S上的一个n元运算，简称为n元运算。
（当n=1时，则为一元运算）
例如： (1) 求一个数的相反数是Z、Q、R上一元运算。
(2) 求一个数的倒数是Q、R上一元运算。
(3) 求一个数的共轭复数C上一元运算。
(4) 集合上的绝对补运算～。～A= x xA
(5) 求一个双射函数的反函数运算。 同二元运算一样，一元运算也可以用算符 ，*，·，
…来表示。例： 定义实数集R上二元运算 ：x,y∈R,x y= x
计算 5 1, 4.9 | -1nnull运算表——
一元、二元运算的另一种表示法ai 。ai
a1 。a1
a2 。a2
… …
an 。an一元运算表
的一般形式。 a1 a2 … an
a1 a1。a1 a1 。a2 … a1 。an
a2 a2。a1 a2 。a2 … a2 。an
… …
an an。a1 an 。a2 … an 。an二元运算表
的一般形式null例： 设S={1，2}，给出S上的运算~和的
运算表。其中全集为Sai ~ ai
Φ {1，2}
{1} {2}
{2} {1}
{1，2} φ~A=S-A={xx∈S∧x∈A } null例： 设S={ 1, 2 }, 给出S上的运算 ~ 和 的
运算表。其中全集为S Φ {1} {2} {1，2}
Φ Φ {1} {2} {1,2}
{1} {1} Φ {1,2} {2}
{2} {2} {1,2} Φ {1}
{1,2} {1,2} {2} {1} Φ A B=（A∪B）-（A∩B）null例： 设S ={1, 2, 3, 4},定义 S 上的二元运算, 如下:
x y = ( x y ) mod 5 , x , y ∈ S
求 的运算表。
解: (x y) mod 5 是 x y 除以5的余数, 其运算如下表 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1 null定义： 设 为S上的二元运算，如果对于任
意的x,y∈ S都有
x y = y x
则称运算 在S上是可交换的，
或说 运算在S上符合交换律。
考察下列运算在指定集合上是否符合交换律?
(1) 实数集合上的加、减、乘、除。
(2) n阶实矩阵上的加、乘。
(3) 集合S的幂集上的∪、∩ 、-、 。
A=1,2,3 B=1,4
A-B=2,3 B-A=4 null定义：
设 为S上的二元运算，如果对于任意的x,y,z∈ S都有
(x y) z =x (y z)
则称运算 在S上是可结合的，或说 运算在S上符合结合律。
考察下列运算在指定集合上是否符合结合律?
(1) N、Z、Q、R 集合上的加、乘。
(2) n阶实矩阵上的加、乘。
(3) 集合S的幂集上的∪、∩ 、 。
null例： 设R为实数集, 定义 R 上的二元运算, 如下:
x y = x1+y1-x1 y1
则 满足交换律和结合律。
证:
∵ x y = x1+y1-x1 y1 = y1 + x1- y1 x1= y x
∴ 满足交换律
∵( x y) z = (x1+y1-x1 y1 ) z
= (x1+y1-x1 y1 ) + z1- (x1+y1-x1 y1 ) z1
= x1+y1 + z1 -x1 y1 - x1 z1 -y1 z1 +x1 y1 z1 x (y z) = x (y1+z1-y1 z1 )
= x1 + (y1+z1-y1 z1 ) - x1 (y1+z1-y1 z1 )
= x1+y1 + z1 -x1 y1 - x1 z1 -y1 z1 +x1 y1 z1
∴ 满足结合律 证毕null定义： 设 为S上的二元运算，如果对于任意的
x∈ S都有 x x = x
则称该运算适合幂等律,x为运算 的幂等元
考察下列运算在指定集合上是否符合幂等律?
(1) N、Z、Q、R集合上的加、乘。
普通加法、乘法不适合幂等律，但0是加法的幂等元，1是乘法的幂等元。
(2) n阶实矩阵上的加、乘。
同理，n阶零矩阵是矩阵加法的幂等元，n阶单位矩阵是矩阵乘法的幂等元。
(3) 集合S的幂集上的∪、∩ 、 、-。
后两个运算一般不适合幂等律，但φ是它们的幂等元。null定义： 设 和 * 是S上的两个二元运算，如果对
于任意的x,y,z∈ S有
x *( y z) =(x * y) (x * z) （左分配律）
( y z) * x =(x * y) (x * z) （右分配律）
则称运算*对 是可分配的,也称*对 适合分配律。
如：
(1) N、Z、Q、R 集合上的乘法对加法。
(2) n阶实矩阵上的乘法对加法。
(3) 集合上的∪、∩互相可分配。
推而广之,如果*对 分配律成立，则
x*(y1 y2 … yn)=(x *y1) (x * y2) … (x * yn)
(y1 y2 … yn)*x=(y1* x) (y2* x) … (yn* x )a(b+c)=ab+acnull定义：
设 和 * 是S上的两个可交换的二元运算，如果对于任意的x,y∈ S都有
x *( x y) =x
x (x * y)=x
则称*和 满足吸收律。
如：
集合上的∪和∩满足吸收律。
即，任意集合A，B满足
A ∪(A ∩ B) =A
A ∩(A ∪ B) =Anull定义： 设 是S上的二元运算，如果存在
el( 或 er )∈ S使得 x ∈S 都有
el x =x (或 x er =x )
则称el(或er)是S中关于 运算的一个左幺元（或右幺元），若e∈S关于 运算既是左幺元又是右幺元，
则称e为S上关于 运算的幺元（单位元）。
如：(1) 在N、Z、Q、R上，0是加法的幺元，1是乘法的
幺元。
(2) n阶0矩阵是矩阵加法的幺元，n阶单位矩阵是
矩阵乘法的幺元。
(3) 在集合上,φ是∪、运算的幺元,全集是∩运
算的幺元 。
(4) 恒等关系是函数复合运算的幺元。∵对任意函数 f : R R, 有 IA f = f IA = f
∴恒等关系是函数复合运算的幺元
例: f(x)= x g(x)=x3
则 f g = f( g (x)) = f(x3 ) = x3 = g(x)
g f = g( f (x) ) = g(x ) = x3 = g(x) null例： 设 S = {α,β}, 是S上的二元运算。试指出下表的左幺元、右幺元及幺元。 表 1 表 2 表 3
解: 如表 1 所定义， 是 的幺元
（单位元）
如表 2 所定义， 和 是 的右幺元
如表 3 所定义， 和 是 的左幺元 =
=
=
= =
=
=
= =
=
=
= null∵ er是右单位元∵ el是左单位元∵ e是单位元定理： 设 是S上的二元运算，el、er分别
为 运算的左、右幺元,(单位元)则有
el = er = e
且e为S上关于运算 的唯一幺元。
证明：
el er = er
el er = el
∴ el = er
把el = er 记作e，则e是S中的幺元。假设
e`也是S中的幺元，则
e`=e e`=e
∴ e是S中关于 运算的唯一的幺元。null定义： 设 是S上的二元运算，如果存在
θl(或θr)∈ S使得x∈S都有
θl x = θl (或 x θr = θr )
则称θl(或θr)是S中关于。运算的一个左零元（右零元）。
若θ∈S关于 运算既是左零元又是右零元，则称θ为S上关于 运算的零元。
如：(1) 在N、Z、Q、R上，0是乘法的零元，加法
没有零元。
(2) n阶0矩阵是矩阵乘法的零元，n阶矩阵的加法
无零元。
(3) 在集合上， ∪运算的零元是全集，∩运算的
零元是φ ，无零元。null例： 设 A = {3, 4, 6, 9, 17, 22 }, 定义A上的二元 运算 为min, 即a b= min(a,b)为a与b中的最小者。
试证 3 是运算 min 的零元，
22 是运算 min 的幺元(单位元)。
证: ∵ 对于任意的 a A, 都有
3 a = min( 3,a )= a 3 = min(a,3 )=3
∴ 3 是运算 min 的零元
∵ 对于任意的 a A, 都有
22 a = min(22,a)= a 22= min(a,22)=a
∴ 22 是运算 min 的幺元(单位元)null∵ θr是右零元∵ θl是左零元∵ θ是零元定理： 设 是S上的二元运算， θl 、θr
分别为 运算的左、右零元，则有
θl = θr = θ
且 θ为S上关于运算 的唯一零元。
证明：
θl θr = θl
θl θr = θr
∴ θl = θr
把θl = θr 记作θ，则θ是S中的零元。
假设θ`也是S中的零元，则
θ`= θ θ`= θ
∴ θ是S中关于 运算的唯一的零元。null定义： 设 是S上的二元运算，e∈ S为 运
算的幺元，对于x∈S，
如果yl ∈ S(或yr ∈ S)使得
yl x =e (或 x yr = e )
则称yl(或yr)是x的左逆元(或右逆元) 。
换句话说,如果对S内的元素a,存在al-1∈S,
使得 al-1 a =e
则称al-1 是a的左逆元素
如果对S内的元素a,存在ar-1∈S, 使得
a ar-1 = e
则称ar-1 是a的右逆元素null 若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元。 如果x的逆元存在，则称x是可逆的。
考虑：
(1) 整数集合Z上，加法逆元?
∵x+(-x)= 0,(-x)+x = 0 ∴存在加法逆元
(2) n阶0矩阵是乘法逆元、加法逆元?
对于矩阵乘法只有可逆矩阵存在逆元M-1，
使得 MM-1= E
(3) 在集合上，∪运算、∩运算的逆元?
只有有逆元，其它元素都没有逆元null∵ yl 。x =e ∵ x 。yr = e定理： 设 是S上的二元运算， e 为该运算
的幺元(单位元).对于x∈S，如果存
在左逆元yl和右逆元yr ，则有
yl = yr =y
且y是x的唯一逆元。
证明：
yl= yl e= yl (x yr) = (yl x) yr
= e 。yr= yr
令yl= yr= y，则y是x的逆元。假若y`∈S也是x的逆元，则
y`=y` e= y` (x y) = (y` x) y
= e y = y
所以y是x的唯一逆元。
通常，将x的逆元记作x-1。null定义： 设 是S上的二元运算，如果
x,y,z∈S满足以下条件
(1) 若 x y=x z 且 x ≠θ,则y=z.
(2) 若 y x=z x 且 x ≠θ,则y=z.
则称 运算满足消去律。(1)、(2) 分别
称作左、右消去律。
考虑：
(1) N、Z、Q、R上的乘法、加法。
对任意的x,y,z x+y=x+z y=z
xy=xz y=z ( x≠0 )
(2) 在集合上 ∪、∩、。
例 A=1,2 B=1 C=2
A∪B=A ∪C= 1,2 B ≠ Cnull综上所述，
二元运算的主要性质：
交换律，结合律，幂等律，消去律
分配律，吸收律
特殊元素：
幺元（单位元） ，零元，逆元的区别
θ 使得对x∈A， 满足
xθ=θ x=x 则θ叫幺元（单位元）
xθ=θ x 则θ叫零元
e为单位元, y使得
y-1 y=e yy-1=e 则y-1叫y的逆元满足吸收率满足交换率null例： 对于下列给定的集合和该集合上的二元运算，指出该运算的性质，并求出它的幺元，零元和所有可逆元素的逆元。
① Z+,x,y∈ Z+,x*y=Lcm(x,y),即求x,y的最小公倍数
② Q, x,y∈ Q, x * y= x + y – xy.
解：① 此运算符合交换律、结合律、幂等律。
1为单位元。
不存在零元。
只有1有逆元，是它自身，其它元素无逆元。
② ∵ x,y∈ Q 都有 x*y = x+y-xy = y+x-yx=y*x
∴ *满足交换律
∵ x,y,z∈ Q 有
(x*y)*z=(x+y-xy)*z= x+y+z-xy-xz-yz+xyz
x*(y*z)=x*(y+z-yz)= x+y+z-xy-xz-yz+xyz
∴ *满足结合律x x= x xe=ex=xxθ=θx=θnull ∵ 3∈ Q 有 3*3=3+3-3×3=-3≠3
∴ *不满足幂等律
∵ x,y,z∈ Q (x≠1) 有
x*y=x*z =>x+y-xy=x+z-xz
=>y-z=x(y-z)=> y=z
同理由于*是可交换的，故右消去律也成立。
∴ *满足消去律
∵ x∈Q 有
x*0=x+0-x×0= x =0+x-0×x=0*x
∴ 0是*运算的幺元（单位元）
∵ x∈Q 有
x*1=x+1-x×1= 1 =1+x-1×x=1*x
∴ 1是*运算的零元 null 单位元的求法：
∵ * 是可交换的，因此若*有左单位元，则它也是右
单位元， ∴ 它有单位元
设 rl 是左单位元，则对任意的 r ∈ Q ,应有
rl * r = rl + r – rlr =r
于是 rl – rlr = 0 => rl (1 – r )=0
由于r的任意性，要使上式成立，只有rl =0
∴ 0 是运算 * 的单位元
由于 * 可交换,若元素 x 有左逆元 y,则 y 必是
x 的右逆元和逆元
设 y 是 x 的左逆元, 则应有 y * x = y+x-yx=0
于是 yx-y = x , 即 y(x-1) = x,
x x
y= x-1 (x≠1) ∴ x-1= x-1 (x≠1) null代数系统及其子系统和积代数
定义： 非空集合S和S上k个一元或二元运算f1, f2, …, fk组成的系统称为一个代数系统, 简称代数，记作< S, f1, f2,…, fk >。
例如
< N , + > ,< Z, + , >, < R , + , > ,
< Mn(R) , +, >
等都是代数系统。 null 在某些代数系统中存在着一些特定的元素，如幺元、零元等，它们对该系统的运算起着重要的作用，称这些元素为该代数系统的特异元素或代数常数。
有时，为了强调这些元素的重要性，经常把它们列到代数系统表达式中。例如：
< N , + > 的幺元(单位元)是 0，
也可记为< N , + , 0 > 。
< P(S), ∪, ∩, ~ > 中∪和∩的幺元(单位元)是 φ和 S, 同样可记为 < P(S), ∪, ∩, ~ , φ, S >等。null定义：
设 V= < S, f1 ,f2, …, fk > 是代数系统, B S, 且B≠Φ, 如果B对f1, f2, …, fk都是封闭的, 且B和S含有相同的代数常数, 则称< B, f1, f2, …, fk > 是V的子代数系统，简称子代数。
如：
① < N, + > 是 < Z, + >的子代数, 因为N对+是封闭
的，且它们都没有代数常数。( 幺元或零元 )
②< N,+,0 > 是 < Z,+,0 >的子代数，因为N对+是封
闭的，且它们都具有代数常数 0。
③ < N,－｛0｝,+ > 是 < Z, + >的子代数，但不是
< Z,+,0 >的子代数，因为代数常数0不出现在
N－｛0｝中null 由子代数的定义不难看出，V的子代数与V本身不仅具有相同的代数运算，并且这些运算也具有相同的性质，只是子系统比原来的代数系统小一些。
对任何代数系统 V= < S, f1, f2, …, fk >, 其子系统一定存在, 最大的子系统就是V本身, 如果令V中所有的代数常数(单位元或零元)构成的集合是 B, 且 B 对V中所有的运算都是封闭的, 那么, B 就构成了 V 的最小的子系统, 这种最大与最小的子代数称为 V 的平凡的子代数, 如果V 的子代数 V‘= < B, f1, f2, …, fk > 满足 B S , 则称 V’是 V 的真子代数。null例：设有代数系统V= < Z+, + , >, 其中Z+为正整数集合, + 和 表示通常数的加法和乘法。令
① A={ 6z | zZ+ }= { 6, 12, 18, … }
② B={ z2 | zZ+ }= { 12, 22 , 32 , … }
试问: < A, + , > 和 < B, + , >
是< Z+, + , > 的子代数吗？
解: 显然，A，B 均是Z+ 的非空子集
① 对于任意的6z1, 6z2A, 6z1+6z2= 6 (z1,+z2) A
6z1 6z2= 6 (6z1 z2) A, + 和 均在A上封闭
∴ < A, + , > 是< Z+, + , > 的子代数
② z21, z22B, z21 z22=(z1 z2)2 B 但
z21 + z22不一定在 B 中, 22 + 32=13B
∴ < B, + , >不是 < Z+, + , > 的子代数。 null例： 设V= < Z, + ,0 >,令
nZ={ nz | zZ } n为自然数
那么，nZ是V的子系统
证:任取nZ中的两个元素nz1和nz２, z1,z２Z,则有
nz1+nz２=n(z1+z２) nZ
即nZ对＋运算是封闭的, 并且0=n•0 nZ。所以，
nZ是< Z,+,0 >的子代数
当n=1时, nZ就是V本身，当n=0时，0Z= { 0 }
是V的最小的子代数，而其它的子代数都是V的
非平凡的真子代数。代数系统及其子系统和积代数null例： 设V= < Z, + ,• >, 其中Z表示整数集, +和• 分别表示通常的加法和乘法运算。对下面Z的每个子集, 确定它是否构成V的子代数？
① H1={ 2n+1 | nZ }
② H2={ -1, 0, 1 }
③ H3={ 2n | nZ }
解: ① H1不能构成V的子代数
∵ 2n1+1, 2n２+1 H1, 有
(2n1+1)+( 2n２+1)= 2n1+2n２+2 H1
∴加法运算在H1上不封闭。
② H2不能构成V的子代数
∵加法运算在H2上不封闭, 如1+1=2 H2null例： 设V= < Z, + ,• >, 其中Z表示整数集, +和• 分别表示通常的加法和乘法运算。对下面Z的每个子集, 确定它是否构成V的子代数？
① H1={ 2n+1 | nZ }
② H2={ -1, 0, 1 }
③ H3={ 2n | nZ }
解: ③ H3能构成V的子代数
∵ 2n1, 2n２ H3, 有
2n1+ 2n２= 2(n1+n２) H3 且
2n1• 2n２= 2(2n1• n２) H3
∴ 加法和乘法运算在H3上是封闭的。
∴ < H3, + ,• > 是 < Z, + ,• >的子代数null例： 设V= < R , * >, 其中R表示实数集
运算 * 定义为 x * y = [ x , y ]
符号[ x, y ] 表示不小于 x 和 y 的最小整数, 又设
① H1 = { x | 0 ≤x≤10 x R }
② H2 = { x | 0 ≤x＜10 x R }
试问 H1, H2 能否构成V的子代数吗？
解: ① ∵ x, y H1, 有 x*y = [ x, y ] H1
∴ 运算 * 在 H1 上是封闭的。
< H1, * > 是 < R, * > 的子代数。
② < H1, * > 不是 < R, * > 的子代数
∵运算 * 在 H2 上是不封闭的
如 9.8 * 2 = [ 9.8 , 2 ] = 10 但 10 H2null定义：
设 V1= < S1, >, V2 = < S2, * > 是代数系统,
和* 为二元运算, V1和V2的积代数V1V2 是含有一个二元运算 的代数系统, 即V1V2 = < S, >, 其中S = S1S2, 对任意的, S1 S2 有
< x1, y1 > < x2, y2 >= < x1 x2，y1 y2 >
设V1= < Z, + >, V2= < M3(R), >,其中+和分别表示整数加法和矩阵乘法。那么V1V2 是
V1V2 = < Z M3(R) , >
对任意的< z1, M1 >, < z2, M2 > Z M3(R) 都有
< z1 , M1 > < z2 , M2 > = < z1+ z2 , M1 M2 > null例： 通常数的乘法运算是否可以看作下列集合上的二元运算，说明理由.
① A = { 1, 2 }
② B = { x | x是素数 }
③ C = { x | x是偶数 }
④ D = { 2n | nN }
解 ① 乘法运算不是A上的二元运算,因为2×2=4A
② 乘法运算不是B上的二元运算，因为素数
乘素数不一定是素数，如2×3＝6B.
③ 乘法运算是C上的二元运算，因为偶数
乘偶数仍然是偶数.
④ 乘法运算是D上的二元运算,因为对任意的
m, nN, 2n, 2m D 有2n×2m = 2n+m Dnull 代数系统的同构与同态 世界上存在着很多的代数系统,但有些代数系统, 尽
管表面上似乎不相同, 但实际上是相同的,比如两个代数
系统 ( {0,1},∨)与( {a,b}, ), 其运算分别由表1和表2定义
表1 代数系统({0,1},∨) 表2 代数系统({a,b}, )
∨ 0 1 。 a b
0 0 1 a a b
1 1 1 b b b
如果将第二个代数系统中的元素a , b分别换以第一个代
数系统中的元素0 , 1, 那么得到的运算组合表与第一个代
数系统的运算组合表完全一样,只是表现形式不同,其实
质是一样的。这种表面上不同而实质上相同的代数系统
我们称它们是同构的null 如何来识别同构的代数系统呢？从上面的例子我们可以看出：两个系统同构必须满足下
面几个条件：
① 它们必须是同一类型的
② 两个集合间的元素是一一对应的
③ 它们的运算定义法则是相同的
我们用上面的例子来说明这三点
① ( {0,1},∨)与( {a,b}, )是同类型的
② 它们的元素间是一一对应的 a 0 b 1
③ 它们有相同的运算定义法则，就是说将表1中的0, 1
分 别换以表2中的a, b后即成为表2，反之亦然。
故这两个代数系统同构null 将这一概念进一步抽象而得到同构定义
定义：
设V1= < S1 , >, V2= < S2 , > 是代数系统,
和 是二元运算，如果存在一个一一对应的映射
： S1 S2 满足对任意的 x,yS1 ，有
(x y)= (x) (y)
则称 是一个从V1到V2的同构映射或称代数系统
V1与V2同构，可记作 V1 V2
我们用下图来表示同构的含义ΦV1=V2= xyx y (x) (y) (x) (y)null如果我们将同构的条件放宽一点，则可得到比同
构范围更广的一些关系，放宽后的关系，使两个
代数系统不一定要有相同的基数，但是能在一定
意义上保持其性质，为此，我们引入同态和满同
态的概念。
定义： 设V1=< S1 , >, V2=< S2 , > 是代数系
统, 和 是二元运算, 如果存在映射 ：S1 S2
满足对任意的 x,yS1 ，有
(x y)= (x) (y)
则称 是一个从V1到V2的同态映射或称代数
系统V1与V2同态，null 从定义可以看出，同态的条件比同构弱，关键是同
构映射是一一对应的，而同态映射则不一定要一一对应
因此对同态而言，有如下的特点：
① 映射可以允许有多对一对应，一对一对应以及一一对应；
② 映射的象可以允许有 (S1 ) S2 , 及 (S1 )=S2 即 (S1 ) S2 对于同态可用下图说明之。V1=V2=< S2 , >xyxys2= (x) (S1 ) (x) (y)null 如果 (S1 ) = S2, 亦即是说 是一个S1到 S2的
满射，此时有下面的定义：
定义5.17
设 是V1=< S1 , >到V2=< S2 , > 的同态, 如果
是满射的，则称 为V1到V2的满同态，记作
V1~V2,如果 是单射的,则称 为V1到V2的单同态
同样一个代数系统与自身的同态称为自同态。
由定义可知，满同态的条件比同态略微强一些。null例：设V1= < Z , + >和V2= < Z n , >,
其中Zn= { 0, 1, …, n-1 }, +为普通加法, 为模n加法。即x, y Zn ,有
x y = (x+y)mod n
令 : Z Zn , (x)= (x)mod n
则 是V1到V2的同态。
解:∵ 对 x, y Z ,有
(x+y)= (x+y)mod n= (x)mod n(y)mod n
= (x) (y)
∴ 是V1到V2的同态。null例：设V = < Z , + > 给定a Z ,令
a : Z Z , a (x)= ax , x Z
则 a 是V到自身的同态（自同态）。
解:∵ 对 x, y Z ,有
a (x+y)= a (x+y) = ax + ay = a(x) + a (y)
∴ a 是V到自身的同态（自同态）
当a =0 时, 有x Z , 0 (x) = 0
称0 为零同态, 其同态象为< { 0 }, + > .
当a = 1时, 有x Z , 1 (x)= x , 称1 为Z的恒等映射, 显然是双射,其同态象就是< Z, + >。这时1 是V的自同构。同理可证-1 也是V的自同构当a≠±1
且a≠0 时, x Z有a (x)=ax , 易证a是 单射的, 这时a 为V的单自同态。同态象是null例： 证明: f : R+R, f(x)=log2x为代数系统V1 = < R+, • > 到V2 = < R, + >的同态( 这里R+为正实数集， R为实数集， • 和+为通常数的乘法和加法运算）。 V1 和V2 是否同态或同构？
分析: 欲证同态必须满足两点
①存在映射 f : R+R（同构是双射)
② x, y R+, 有f(x • y)=f(x) + f(y)
证: f : R+R, f(x)=log2x ,
∵对x R+, 有唯一 f(x) =log2x R,
∴f 为R+到R的函数。
又∵对x, y R+,
f(x • y) = log2(x • y)= log2x + log2y=f(x)+f(y)
∴ f 为V1 = < R+, • > 到V2 = < R, + >的同态。null例： 证明: f : R+R, f(x)=log2x为代数系统V1 = < R+, • > 到V2 = < R, + >的同态( 这里R+为正实数集， R为实数集， • 和+为通常数的乘法和加法运算）。 V1 和V2 是否同态或同构？
分析: 欲证同构必须满足两点
①双射 f : R+R
② x1, x2 R+, 有f(x1 • x2 )=f(x1) + f(x2)
证: f : R+R, f(x)=log2x ,
∵对x R+, 有唯一 f(x) =log2x R,
∴f 为R+到R的函数。
又∵对 x1, x2 R+, x1≠ x2, log2 x1≠log2x2
即f(x1) ≠f(x2), 故 f 为单射, 又对 y R
取x=2y R+, 使 f(x)=log22y= y, 故 f 为满射
f(x • y) = log2x • y = log2x + log2y=f(x)+f(y) ∴是
同构null例：设V1=< R , • >和V2=< R+ , • >, 其中R和R+ 分别表示实数集和正实数集, • 表示通常的乘法。
定义函数 ① f1: R R+ , f(x)=|x|
② f2: R+ R+ , g(x)=x
③ f3: R+ R+ , f3(x)=2x
试问, 以上这些函数是否是V1到V2的同态或同构？
解: ① 对任意的x , yR
f(x • y)= |x • y|= f(x)•f(y)
所以f1是V1到V2 的同态。
但f1 不是单射, 因为f(x)=f(-x)= |x|
如f(2.5)=f(-2.5)=2.5。
故 f1不是V1到V2的同构。 null例： 设V1=< R , • >和V2=< R+ , • >, 其中R和R+ 分别表示实数集和正实数集, • 表示通常的乘法。
定义函数 ② f2: R+ R+ , g(x)=x
③ f3: R+ R+ , f3(x)=2x
试问, 以上这些函数是否是V1到V2的同态或同构？
解: ②对任意的x , y R+
g(x • y)= x • y=g(x)•g(y)
∴ f2是V1到V2 的同态。且因为对于任意x R+
g(x)=x , 即f2 是R+ 上的恒等函数, 它是双射
的, 因此 f2是V2到V2的同构。
③对x , y R+ , f3(x • y)=2xy,
f3(x) • f3(y)=2x•2y=4xy, 因此f(x • y) f3(x) • f3(y)
故f2不是V2到V2的同态和同构。null例： 设V=< R* , • >, 其中R* 表示非零实数集,
• 表示通常的乘法。
定义函数 f: R* R* , f(x)= 1/x
求证：f 是V到V的满同态
证: 对x R* ,因为x≠0，所以有1/x R* , 因此
f 是由 R* 到 R* 的函数
又对于x, y R* 有 ∴ f是V到V 的同态null例： 设< A , > 是一个代数系统，二元运算
对任意的 a , b A , 有
① (a b) a = a
② (a b) b = (b a) a
试证明: 对任意的 a , b A , 有
① a (a b) = a b
② a a = (a b) (a b)
证: ① a (a b) = ((a b) a ) (a b)
= ((a b) a ) (a b)
= a b
② (a b) (a b) = (a (a b) ) (a b)
= ((a b) a) a
= a a bab=a*(a*b) (ab)a=anull 我们知道,若 是V1=< S1 , >到V2=< S2 , > 的同态, 如果 是满射的，则称 为V1到V2的满同态，记作 V1~V2,如果 是单射的,则称 为V1到V2的单同态同样一个代数系统与自身的同态称为自同态。
由定义可知，满同态的条件比同态略微强一些。
若V1 =< R, • > 到 V2 = < R, + >的影射( R为实数集， • 和+为通常数的乘法和加法运算）。
V1 和V2 是否同态或同构？
分析: 欲证同态（同构)必须满足两点
①存在映射 f : RR（同构是双射)
② x, y R, 有f(x • y)=f(x) + f(y)null作业：设V= < Z , + >其中+为普通加法, x Z , 有 1 (x)= x , 2 (x)= 0, 3 (x)= x+5,
4(x)=2x, 5(x) =x2, 6(x)= - x
解: 一个代数系统与自身的同态称为自同态(4)
1(x)= x , 2(x)= 0, 4 (x)=2x, 6(x)= - x
(同构是双射 ZZ)其中2个不是V的自同构
2(x)= 0, 4 (x)=2x,
如果 是单射的,则称 为V到V的单自同态
4(x)=2x, 不是满自同态
如果 是满射的，则称 为V到V的满自同态
浙公网安备 33021202002483