《离散数学》课程教学资源（教案讲义）第五章 代数结构

离散数学教案 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组

离散数学教案 1 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组

离散数学教案 代数结构 一、学习目的与要求 本章从一般代数系统的引入出发，研究一些特殊的代数系统中运算的性质。通过 本章的学习使学生了界代数系统的结构与性质。 二、知识点 1.代数系统的引入，运算的性质：封闭性、结合性、分配性、交换性： 2,主要的代数系统：广群、半群、独异点、群、子群：代数系统之间的关系： 3.交换群和循环群： 4.陪集、拉格朗日定理： 5.同态映射、同构映射： 6.环、同态象、域。 三、要求 1.识记 运算的封闭性、交换性、结合性，么元、零元、逆元、等幂元的识别。 2.领会 广群、半群、独异点、群、子群：代数系统之间的关系，主要的性质定理及其证 明。 四、主要内容 第5章代数结构概念及性质 5.1代数结构的定义与例 在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运 算这个概念是代数结构中不可缺少的基本概念。 定义5.1.1S是个非空集合且函数f∈S 或f:S”→S,则称f为一个n元运算。其中n是自然数，称为运算的元数或阶 当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等。 注意，元运算是个闭运算，因为经运算后产生的象仍在同一个集合中。封闭性 表明了元运算与一般函数的区别之处。此外，有些运算存在么元或零元，它在运算 中起着特殊的作用，称它为S中的特异元或常数。 运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和 2

离散数学教案 2 代数结构 一、学习目的与要求 本章从一般代数系统的引入出发，研究一些特殊的代数系统中运算的性质。通过 本章的学习使学生了界代数系统的结构与性质。 二、知识点 1．代数系统的引入，运算的性质：封闭性、结合性、分配性、交换性； 2．主要的代数系统：广群、半群、独异点、群、子群；代数系统之间的关系； 3．交换群和循环群； 4．陪集、拉格朗日定理； 5．同态映射、同构映射； 6．环、同态象、域。 三、要求 1．识记 运算的封闭性、交换性、结合性，幺元、零元、逆元、等幂元的识别。 2．领会 广群、半群、独异点、群、子群；代数系统之间的关系，主要的性质定理及其证 明。 四、主要内容 第 5 章 代数结构概念及性质 5.1 代数结构的定义与例 在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运 算这个概念是代数结构中不可缺少的基本概念。 定义 5.1.1 S 是个非空集合且函数 n s f S 或 f:Sn →S，则称 f 为一个 n 元运算。其中 n 是自然数，称为运算的元数或阶。 当 n=1 时，称 f 为一元运算，当 n=2 时，称 f 为二元运算，等等。 注意，n 元运算是个闭运算，因为经运算后产生的象仍在同一个集合中。封闭性 表明了 n 元运算与一般函数的区别之处。此外，有些运算存在幺元或零元，它在运算 中起着特殊的作用，称它为 S 中的特异元或常数。 运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和

离散数学教案 析取是谓词集合上的二元运算：在集合论中，并与交是集合上的二元运算：在整数算 术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。 在下面讲座的代数结构中，主要限于一元和二元运算，将用’、或一等符号表 示一元运算符：用⊕、⑧、⊙、O、A、∩、U等表示二元运算符，一元运算符常 常习惯于前置、顶置或肩置，如k、x':而二元运算符习惯于前置、中置或后置， 如：+xy,xy,Xy+。 有了集合上运算的概念后，便可定义代数结构了。 定义5.1.2设S是个非空集合且f是S上的ni元运算，其中i=1,2,.,m。 由S及f1,f2,.,fm组成的结构，称为代数结构，记作。 此外，集合S的基数即|S引定义代数结构的基数。如果S是有限集合，则说代数结构 是有限代数结构：否则便说是无穷代数结构。 有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义： 定义5.1.3设两个代数结构和,如果fi 和gi(1≤i≤m)具有相同的元数，则称这两个代数结构是同类型的： 可见，判定两个代数结构是否同类型，主要是对其运算进行考察。 此外，有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数 结构的概念。 定义5.1.4设是一代数结构且非空集TcS在运算f1,f2,., fm作用下是封闭的，且T含有与S中相同的特异元，则称为代 数结构的子代数。记为。 在结束本节时，声明记号即为一代数结构，除特别指明外， 运算符f1,f2,···,fm均为二元运算。根据需要对S及f1,f2,···,fm可置不同 的集合符和运算符。 5.2代数结构的基本性质 所谓代数结构的性质即是结构中任何运算所具有的性质。 1.结合律 给定S,⊙>，则运算“⊙”满足结合律或“⊙”是可结合的，即 (x)(付y)(付z)(x,y,z∈S一(x⊙y)⊙z=x⊙⊙z)

离散数学教案 3 析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算 术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。 在下面讲座的代数结构中，主要限于一元和二元运算，将用’、或ˉ等符号表 示一元运算符；用、、⊙、○、、、∩、∪等表示二元运算符，一元运算符常 常习惯于前置、顶置或肩置，如x、x’；而二元运算符习惯于前置、中置或后置， 如：+xy，x+y，xy+。 有了集合上运算的概念后，便可定义代数结构了。 定义 5.1.2 设 S 是个非空集合且 fi是 S 上的 ni 元运算，其中 i=1，2，.，m。 由 S 及 f1，f2，.，fm 组成的结构，称为代数结构，记作。 此外，集合 S 的基数即|S|定义代数结构的基数。如果 S 是有限集合，则说代数结构 是有限代数结构；否则便说是无穷代数结构。 有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义： 定义 5.1.3 设两个代数结构和，如果 fi 和 gi(1≤i≤m)具有相同的元数，则称这两个代数结构是同类型的。 可见，判定两个代数结构是否同类型，主要是对其运算进行考察。 此外，有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数 结构的概念。 定义 5.1.4 设是一代数结构且非空集 TS 在运算 f1，f2，.， fm 作用下是封闭的，且 T 含有与 S 中相同的特异元，则称为代 数结构的子代数。记为。 在结束本节时，声明记号即为一代数结构，除特别指明外， 运算符 f1,f2,···,fm 均为二元运算。根据需要对 S 及 f1,f2,···,fm 可置不同 的集合符和运算符。 5.2 代数结构的基本性质 所谓代数结构的性质即是结构中任何运算所具有的性质。 1.结合律 给 定 ，则运算 “ ⊙ ” 满足结合律或 “ ⊙ ” 是可结合的，即 (x)(y)(z)(x，y，z∈S→(x⊙y)⊙z=x⊙(y⊙z))

离散数学教案 2.交换律 给定，则运算“⊙”满足交换律或“⊙”是可交换的，即(x)(y)(x, y∈S→x⊙y=y⊙x)。 可见，如果一代数结构中的运算⊙是可结合和可交换的，那么，在计算l⊙a2 ⊙···⊙aO=am。称am为a的m次幂，m称a的指数。下面给出am的归纳定义： 设有且aeS,对于m∈I+,其中I+表示正整数集合，可有： (1)a'=a (2)a=a⊙a 由此利用归纳法不难证明指数定律： (1）a⊙a"=aa (2)(a)=a" 这里，m,neI+。 类似地定义某代数结构中的负幂和给出负指数定律 3.分配律 一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。 给定,则运算⊙对于O满足左分配律，或者⊙对于O是可左分配的，即 (x)(y)(z)(x,y,z∈S-→x⊙(yOz)=(y⊙x)O(x⊙z)。 运算⊙对于O满足右分配律或⊙对于O是可右分配的，即（付x)(y)(付2）(x,y, z∈S→(yOz)⊙x=(y⊙x)O(z⊙x) 类似地可定义O对于⊙是满足左或右分配律。 若⊙对于O既满足左分配律又满足右分配律，则称⊙对于O满足分配律或是可分 配的。同样可定义O对于⊙满足分配律。 由定义不难证明下面定理： 定理5.2.1给定且⊙是可交换的。如果⊙对于O满足左或右分配 律，则⊙对于O满足分配律。 例5.2.3给定,其中={0,1}。表5.2.1分别定义了运算⊙和O,问 运算⊙对于O是可分配的吗？O对于⊙呢？ 形如表5.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表 头元素及复合元素四部分组成。当集合S的基数很小，特别限于几个时，代数结构中 4

离散数学教案 4 2.交换律 给定，则运算“⊙”满足交换律或“⊙”是可交换的，即( x)( y)(x， y∈S→x⊙y=y⊙x)。 可见，如果一代数结构中的运算⊙是可结合和可交换的，那么，在计算 a1⊙a2 ⊙···⊙a0=am。称 am 为 a 的 m 次幂，m 称 a 的指数。下面给出 am 的归纳定义： 设有且 aS，对于 mI+，其中 I+表示正整数集合，可有： (1) a1 =a (2)am+1 =a m⊙a 由此利用归纳法不难证明指数定律： (1)am⊙a n =a m+n (2)(am ) n =a mn 这里，m,nI+。 类似地定义某代数结构中的负幂和给出负指数定律。 3.分配律 一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。 给定，则运算⊙对于○满足左分配律，或者⊙对于○是可左分配的，即 (x)(y)(z)(x，y，z∈S→x⊙(y○z))=(y⊙x)○(x⊙z))。 运算⊙对于○满足右分配律或⊙对于○是可右分配的，即(x)(y)(z)(x，y， z∈S→(y○z)⊙x=(y⊙x)○(z⊙x)) 类似地可定义○对于⊙是满足左或右分配律。 若⊙对于○既满足左分配律又满足右分配律，则称⊙对于○满足分配律或是可分 配的。同样可定义○对于⊙满足分配律。 由定义不难证明下面定理： 定理 5.2.1 给定且⊙是可交换的。如果⊙对于○满足左或右分配 律，则⊙对于○满足分配律。 例 5.2.3 给定，其中 B={0,1}。表 5.2.1 分别定义了运算⊙和○，问 运算⊙对于○是可分配的吗？○对于⊙呢？ 形如表 5.2.1 的表常常被称为运算表或复合表，它由运算符、行表头元素、列表 头元素及复合元素四部分组成。当集合 S 的基数很小，特别限于几个时，代数结构中

离散数学教案 运算常常用这种表给出。其优点简明直观，一目了然。 解可以验证⊙对于O是可分配的，但O对于⊙并非如此。因为 10(0⊙1)≠(1O0)⊙(101) 4.吸收律 给定,则 ⊙对于O满足左吸收律：=（付x)(付y)(x,y∈S一x⊙(xOy)=x) ⊙对于O满足右吸收律：=（付x)(y)(x,y∈S→(xOy)⊙x=x) 若⊙对于℃既满足左吸收律又满足右吸收律，则称⊙对于O满足吸收律或可吸收 的。 O对于⊙满足左、右吸收律和吸收律类似地定义。 若⊙对于O是可吸收的且O对于⊙也是可吸收的，则⊙和O是互为吸收的或⊙和 O同时满足吸收律。 5.等幂律与等幂元 给定，则 “⊙”是等幂的或“⊙”满足等幂律：=(x)(x∈S→x⊙x=x) 给定且x∈S,则 x是关于“⊙”的等幂元：=x⊙x=x 于是，不难证明下面定理： 定理5.2.2若x是中关于⊙的等幂元，对于任意正整数n,则x=x。 6.么元或单位元 给定且el,er,eeS,则 el为关于⊙的左么元：=(x)(x∈S→el⊙x=x) er为关于⊙的右么元：=(x)(x∈S→x⊙er=x) 若e既为⊙的左么元又为⊙的右么元，称e为关于⊙的么元。亦可定义如下： e为关于⊙的么元：=(x)(x∈S→e⊙x=x⊙e=x)。 定理5.2.3给定且el和er分别关于⊙的左、右么元，则el=er=e且 么元e唯一。 7.零元

离散数学教案 5 运算常常用这种表给出。其优点简明直观，一目了然。 解 可以验证⊙对于○是可分配的，但○对于⊙并非如此。因为 1○(0⊙1)(1○0)⊙(1○1) 4.吸收律 给定，则 ⊙对于○满足左吸收律:=(x)(y)(x，y∈S→x⊙(x○y)=x) ⊙对于○满足右吸收律:=(x)(y)(x，y∈S→(x○y)⊙x=x) 若⊙对于 c 既满足左吸收律又满足右吸收律，则称⊙对于○满足吸收律或可吸收 的。 ○对于⊙满足左、右吸收律和吸收律类似地定义。 若⊙对于○是可吸收的且○对于⊙也是可吸收的，则⊙和○是互为吸收的或⊙和 ○同时满足吸收律。 5.等幂律与等幂元 给定，则 “⊙”是等幂的或“⊙”满足等幂律:=( x)(x∈S→x⊙x=x) 给定且 x∈S，则 x 是关于“⊙”的等幂元:=x⊙x=x 于是，不难证明下面定理： 定理 5.2.2 若 x 是中关于⊙的等幂元，对于任意正整数 n，则 x n =x。 6.幺元或单位元 给定且 el，er，e∈S，则 el 为关于⊙的左幺元:=( x)(x∈S→el⊙x=x) er 为关于⊙的右幺元:=( x)(x∈S→x⊙er=x) 若 e 既为⊙的左幺元又为⊙的右幺元，称 e 为关于⊙的幺元。亦可定义如下： e 为关于⊙的幺元:=( x)(x∈S→e⊙x=x⊙e=x)。 定理 5.2.3 给定且 el 和 er 分别关于⊙的左、右幺元，则 el=er=e 且 幺元 e 唯一。 7.零元

离散数学教案 给定及01,0r,0∈S,则 01为关于O的左零元：=(x)(x∈S→01Ox=01) 0r为关于O的右零元：=(x)(x∈S→xO0r=0r) 0为关于O的零元：=(x)(x∈S一0Ox=xO0=0) 定理5.2.4给定且01和0r分别为关于⊙的左零元和右零元，则01= 0r=0且零元0是唯一的。 定理5.2.5给定且|S|>1。如果0，e∈S,其中0和e分别为关于⊙ 的零元和么元，则0≠e。 8.逆元 给定且么元e,x∈S,则 x为关于⊙的左逆元：=(3y)(y∈S∧x⊙y=e) x为关于⊙的右逆元：=(3y)(y∈S∧y⊙x=e) x为关于⊙可逆的：=（日y)(y∈S∧y⊙x=x⊙y=e) 给定及么元e:x,y∈S,则 y为x的左逆元：y⊙x=C y为x的右逆元：=x⊙y=e y为x的逆元：=y⊙x=x⊙y=e 显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的 逆元表为x。 一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可 以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是唯一的。 定理5.2.6给定及么元e∈S。如果⊙是可结合的并且一个元素x的左 逆元x和右逆元xr存在，则x1=xr。 定理5.2.7给定及么元e∈S。如果⊙是可结合的并且x的逆元x存在， 则x是唯一的。 9.可约律与可约元 给定且零元0∈S,则 ⊙满足左可约律或是左可约的： =(x)(y)(2)(x,y,z∈S∧x≠0八x⊙y=x⊙z)→y=z),并称x是关于⊙ 6

离散数学教案 6 给定及θl，θr，θ∈S，则 θl 为关于○的左零元:=( x)(x∈S→θl○x=θl) θr 为关于○的右零元:=( x)(x∈S→x○θr=θr) θ为关于○的零元:=( x)(x∈S→θ○x=x○θ=θ) 定理 5.2.4 给定且θl 和θr 分别为关于⊙的左零元和右零元，则θl= θr=θ且零元θ是唯一的。 定理 5.2.5 给定且|S|＞1。如果θ，e∈S，其中θ和 e 分别为关于⊙ 的零元和幺元，则θ≠e。 8．逆元 给定且幺元 e，x∈S，则 x 为关于⊙的左逆元:=(y)(y∈S∧x⊙y=e) x 为关于⊙的右逆元:=(y)(y∈S∧y⊙x=e) x 为关于⊙可逆的:=(y)(y∈S∧y⊙x=x⊙y=e) 给定及幺元 e；x，y∈S，则 y 为 x 的左逆元:=y⊙x=e y 为 x 的右逆元:=x⊙y=e y 为 x 的逆元:=y⊙x=x⊙y=e 显然，若 y 是 x 的逆元，则 x 也是 y 的逆元，因此称 x 与 y 互为逆元。通常 x 的 逆元表为 x -1。 一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可 以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是唯一的。 定理 5.2.6 给定及幺元 e∈S。如果⊙是可结合的并且一个元素 x 的左 逆元 xl-1 和右逆元 xr -1 存在，则 xl-1 =xr -1。 定理 5.2.7 给定及幺元 e∈S。如果⊙是可结合的并且 x 的逆元 x -1 存在， 则 x -1 是唯一的。 9.可约律与可约元 给定且零元θ∈S，则 ⊙满足左可约律或是左可约的: =( x)( y)( z)((x，y，z∈S∧x≠θ∧x⊙y=x⊙z)→y=z)，并称 x 是关于⊙

离散数学教案 的左可约元。 ⊙满足右可约律或是右可约的： =(x)(y)(z)(x,y,z∈Sx≠0Ay⊙x=z⊙x)→y=z),并称x是关于⊙ 的右可约元。 若⊙既满足左可约律又满足右可约律或⊙既是左可约又是右可约的，则称⊙满足 可约律或⊙是可约的。 若x既是关于⊙的左可约元又是关于⊙的右可约元，则称x是关于⊙的可约元。 可约律与可约元也可形式地定义如下： ⊙满足可约律： =(x)(y)(z)(x,y,z∈SAx≠0A(x⊙y=x⊙z∧y⊙x=z⊙x)→y=z) 给定且零元0，x∈S。 x是关于⊙的可约元： =(y)(z)(y,z∈S∧x≠0∧(x⊙y)=x⊙z∧y⊙x=z⊙x)→y=z)。 定理5.2.8给定且O是可结合的，如果x是关于O可逆的且x≠0，则 x也是关于O的可约元。 证明设任意y,z∈S且有xOy=xOz或yOx=zOx。因为O是可结合的及x是关 于O可逆的，则有 xO(xOy)=(xOx)Oy=eOy=y =xO(xOz)=(xOx)Oz =eOz=z 故得xOy=xOz→y=2,同样可证得yOx=zOx一y=2,故x是关于O的可约元。 最后，作一补充说明，用运算表定义一代数结构的运算，从表上很能反映出关于 运算的各种性质。为确定起见，假定及x,y,0,e∈S。 (1)运算O具有封闭性，当且仅当表中的每个元素都属于S。 (②)运算O满足交换律，当且仅当表关于主对角线是对称的。 (③)运算O是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元 素相同。 (④元素x是关于O的左零元，当且仅当x所对应的行中的每个元素都与x相同： 元素y是关于O的右零元，当且仅当y所对应的列中的每个元素都与y相同：元素0 7

离散数学教案 7 的左可约元。 ⊙满足右可约律或是右可约的: =( x)( y)( z)((x，y，z∈S∧x≠θ∧y⊙x=z⊙x)→y=z)，并称 x 是关于⊙ 的右可约元。 若⊙既满足左可约律又满足右可约律或⊙既是左可约又是右可约的，则称⊙满足 可约律或⊙是可约的。 若 x 既是关于⊙的左可约元又是关于⊙的右可约元，则称 x 是关于⊙的可约元。 可约律与可约元也可形式地定义如下： ⊙满足可约律: =( x)( y)( z)(x，y，z∈S∧x≠θ∧((x⊙y=x⊙z∧y⊙x=z⊙x)→y=z)) 给定且零元θ，x∈S。 x 是关于⊙的可约元: =( y)( z)(y，z∈S∧x≠θ∧((x⊙y)=x⊙z∧y⊙x=z⊙x)→y=z))。 定理 5.2.8 给定且○是可结合的，如果 x 是关于○可逆的且 x≠θ，则 x 也是关于○的可约元。 证明 设任意 y,zS 且有 x○y=x○z 或 y○x=z○x。因为○是可结合的及 x 是关 于○可逆的，则有 x -1○(x○y)=(x-1○x)○y=e○y=y =x -1○(x○z)=(x-1○x)○z =e○z=z 故得 x○y=x○zy=z，同样可证得 y○x=z○xy=z，故 x 是关于○的可约元。 最后，作一补充说明，用运算表定义一代数结构的运算，从表上很能反映出关于 运算的各种性质。为确定起见，假定及 x，y，θ，e∈S。 (1)运算○具有封闭性，当且仅当表中的每个元素都属于 S。 (2)运算○满足交换律，当且仅当表关于主对角线是对称的。 (3)运算○是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元 素相同。 (4)元素 x 是关于○的左零元，当且仅当 x 所对应的行中的每个元素都与 x 相同； 元素 y 是关于○的右零元，当且仅当 y 所对应的列中的每个元素都与 y 相同；元素θ

离散数学教案 是关于O的零元，当且仅当日所对应的行和列中的每个元素都与0相同。 (⑤)元素x为关于O的左么元，当且仅当x所对应的行中元素依次与行表头元素 相同：元素y为关于O的右么元，当且仅当y所对应的列中元素依次与列表头元素相 同：元素e是关于O的么元，当且仅当e所对应的行和列中元素分别依次地行表头元 素和列表头元素相同。 (6)x为关于O的左逆元，当且仅当位于x所在行的元素中至少存在一个么元，y 为关于O的右逆元，当且仅当位于y所在列的元素中至少存在一个么元：x与y互为 逆元，当且仅当位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是 么元。 5.3同态与同构 本节将阐明两个重要概念一一同态与同构。在以后各节中，它们会经常被使用到。 定义5.3.1设与是同类型的。称同态于或为的同态象，记为X,⊙>,其定义如下： :=(臼f)(f∈YX∧(x1) (付x2)(x1,x2∈X-→f(x1⊙x2)=f(x1)Of(x2) 同时，称f为从到的同态映射。 可以看出，同态映射「不必是唯一的。 两个同类型的代数结构间的同态定义不仅适用于具有一个二元运算的代数结构， 也可以推广到具有多个二元运算的任何两个同类型代数结构。例如，对于具有两个二 元运算的两个同类型代数结构和的同态定义如下： =：=(3f)(feYXA(x1) (x2)(x1,x2∈X→(f(x1⊙x2)=f(x1)⊕f(x2)Af(x1Ox2)=f(x1)⑧f(x2) 定理5.3.1如果且f为其同态映射，则cY,O>。 由于函数feX的不同性质，将给出不同种类的同态定义。 定义5.3.2设且f为其同态映射。 ()如果f为满射，则称f是从到的满同态映射。 (ii)如果f为单射（或一对一映射），则称f为从到的单一同态映 射

离散数学教案 8 是关于○的零元，当且仅当θ所对应的行和列中的每个元素都与θ相同。 (5)元素 x 为关于○的左幺元，当且仅当 x 所对应的行中元素依次与行表头元素 相同；元素 y 为关于○的右幺元，当且仅当 y 所对应的列中元素依次与列表头元素相 同；元素 e 是关于○的幺元，当且仅当 e 所对应的行和列中元素分别依次地行表头元 素和列表头元素相同。 (6)x 为关于○的左逆元，当且仅当位于 x 所在行的元素中至少存在一个幺元，y 为关于○的右逆元，当且仅当位于 y 所在列的元素中至少存在一个幺元；x 与 y 互为 逆元，当且仅当位于 x 所在行和 y 所在列的元素以及 y 所在行和 x 所在列的元素都是 幺元。 5.3 同态与同构 本节将阐明两个重要概念——同态与同构。在以后各节中，它们会经常被使用到。 定义 5.3.1 设与是同类型的。称同态于或为的同态象，记为，其定义如下： :=(f)(f∈YX∧(x1) (x2)(x1，x2∈X→f(x1⊙x2)=f(x1)○f(x2))) 同时，称 f 为从到的同态映射。 可以看出，同态映射 f 不必是唯一的。 两个同类型的代数结构间的同态定义不仅适用于具有一个二元运算的代数结构， 也可以推广到具有多个二元运算的任何两个同类型代数结构。例如，对于具有两个二 元运算的两个同类型代数结构和的同态定义如下： :=(f)(fYX(x1) (x2)(x1,x2X→(f(x1⊙x2)=f(x1)f(x2)f(x1○x2)=f(x1)f(x2))) 定理 5.3.1 如果且 f 为其同态映射，则。 由于函数 fYX 的不同性质，将给出不同种类的同态定义。 定义 5.3.2 设且 f 为其同态映射。 (i)如果 f 为满射，则称 f 是从到的满同态映射。 (ii)如果 f 为单射(或一对一映射)，则称 f 为从到的单一同态映 射

离散数学教案 (iii)如果f为双射（或一一对应），则称f为从到的同构映射。 记为。 显然，若f是从到的同构映射，则f为从X,⊙>到的满 同态映射及单一同态映射，反之亦然。 例5.3.4给定，其中I为整数集合，+为一般加法。 作函数feI:f(x)=kx,其中x,keI 则当k0时，f为到的单一同态映射。当k=-1或k=1时，f为从 到的同构映射。 综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说， 它能够保持运算的更多性质，为此，给出如下定理： 定理5.3.2给定且f为其满同态映射，则 (a)如果⊙和O满足结合律，则⊕和8也满足结合律。 (b)如果⊙和○满足交换律，则⊕和⑧也满足交换律。 (c)如果⊙对于O或O对于⊙满足分配律，则©对于⑧或⑧对于⊕也相应满足分配 律。 ()如果⊙对于O或O对于⊙满足吸收律，则⊕对于⑧或⑧对于⊕也满足吸收律。 ()如果⊙和O满足等幂律，则⊕和⑧也满足等幂律。 (f)如果e1和e2分别是关于⊙和O的么元，则f(el)和f(e2)分别为关于©和⑧ 的么元。 (g)如果01和62分别是关于⊙和O的零元，则f(01)和f(02)分别为关于⊕ 和⑧的零元。 ()如果对每个x∈X均存在关于⊙的逆元x-1,则对每个f(x)∈Y也均存在关于 ⊕的逆元f(x-1):如果对每个z∈X均存在关于O的逆元z-1,则对每个f(z)∈Y也 均存在关于⑧的逆元f(z-1)。 定理5.3.2告诉我们，对于满同态映射来说，代数系统的许多性质都能保持，如 结合律、交换律、分配律、等幂律、么元、零元、逆元等，但这种保持性质是单向的， 即如果满同态于,则所具有的性质，均具有。但反之 不然，即所具有的某些性质，X,⊙>不一定具有。不尽要问，在怎样条件下， 所具有的性质都完全具有呢？为了回答这个问题，需要引出两个代数 9

离散数学教案 9 (iii)如果 f 为双射(或一一对应)，则称 f 为从到的同构映射。 记为。 显然，若 f 是从到的同构映射，则 f 为从到的满 同态映射及单一同态映射，反之亦然。 例 5.3.4 给定，其中 I 为整数集合，+为一般加法。 作函数 fII:f(x)=kx，其中 x,kI 则当 k0 时，f 为到的单一同态映射。当 k=-1 或 k=1 时，f 为从 到的同构映射。 综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说， 它能够保持运算的更多性质，为此，给出如下定理： 定理 5.3.2 给定且 f 为其满同态映射，则 (a)如果⊙和○满足结合律，则和也满足结合律。 (b)如果⊙和○满足交换律，则和也满足交换律。 (c)如果⊙对于○或○对于⊙满足分配律，则对于或对于也相应满足分配 律。 (d)如果⊙对于○或○对于⊙满足吸收律，则对于或对于也满足吸收律。 (e)如果⊙和○满足等幂律，则和也满足等幂律。 (f)如果 e1 和 e2 分别是关于⊙和○的幺元，则 f(e1)和 f(e2)分别为关于和 的幺元。 (g)如果θ1 和θ2 分别是关于⊙和○的零元，则 f(θ1)和 f(θ2)分别为关于 和的零元。 (h)如果对每个 x∈X 均存在关于⊙的逆元 x-1，则对每个 f(x)∈Y 也均存在关于 的逆元 f(x-1)；如果对每个 z∈X 均存在关于○的逆元 z-1，则对每个 f(z)∈Y 也 均存在关于的逆元 f(z-1)。 定理 5.3.2 告诉我们，对于满同态映射来说，代数系统的许多性质都能保持，如 结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向的， 即如果满同态于，则所具有的性质，均具有。但反之 不然，即所具有的某些性质，不一定具有。不尽要问，在怎样条件下， 所具有的性质都完全具有呢?为了回答这个问题，需要引出两个代数

离散数学教案 结构同构的概念。 定义5.3.3设与是同类型的。称同构于,记为 =Y,O>,其定义如下 =:=(白)(f为从到的同构映射或更详细地定义为： :=(臼f)(f∈YX∧f为双射∧f为从到的同态映射) 由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同 态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单 向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结 构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它 们的所有发生“彼此相通”。 这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外 一个性质己知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的 两个代数系统来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是 相同的。因此，可以根据这些特征来识别同构的代数系统。 同构是一个关系，而且可以证明它是个等价关系，对此有如下定理： 定理5.3.3代数系统间的同构关系是等价关系。 证明显然，因为恒等映射是同构映射。又若 且f为其同构映射，则为从到的同构映射。因此，。再令及，则。这里因为若f 为到的同构映射，g为到的同构映射，则go为从到的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构 关系是等价关系。 由于同构关系是等价关系，故令所有的代数系统构成一个集合S,于是可按同构 关系将其分类，得到商集S/。因为同构的代数系统具有相同的性质，故实际上代 数系统所需要研究的总体并不是S而是S/。 在同态与同构中有一个特例，即具有相同集合的任两个代数系统的同态与同构， 这便是自同态与自同构。 定义5.3.4给定及f∈SS。 f为自同态映射：=f为从到的同态映射。 10

离散数学教案 10 结构同构的概念。 定义 5.3.3 设与是同类型的。称同构于，记为 ，其定义如下： :=(f)(f 为从到的同构映射或更详细地定义为： :=(f)(f∈YX∧f 为双射∧f 为从到的同态映射) 由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同 态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单 向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结 构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它 们的所有发生“彼此相通”。 这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外 一个性质已知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的 两个代数系统来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是 相同的。因此，可以根据这些特征来识别同构的代数系统。 同构是一个关系，而且可以证明它是个等价关系，对此有如下定理： 定理 5.3.3 代数系统间的同构关系是等价关系。 证明 显然，因为恒等映射是同构映射。又若 且 f 为其同构映射，则 f -1 为从到的同构映射。因此，。再令及，则。这里因为若 f 为到的同构映射，g 为到的同构映射，则 gof 为从到的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构 关系是等价关系。 由于同构关系是等价关系，故令所有的代数系统构成一个集合 S，于是可按同构 关系将其分类，得到商集 S/ 。因为同构的代数系统具有相同的性质，故实际上代 数系统所需要研究的总体并不是 S 而是 S/ 。 在同态与同构中有一个特例，即具有相同集合的任两个代数系统的同态与同构， 这便是自同态与自同构。 定义 5.3.4 给定及 f∈SS。 f 为自同态映射:=f 为从到的同态映射