离散数学-代数系统

1、1 第三部分第三部分 代数结构代数结构 代数结构又名近世代数或抽象代数学，是数学代数结构又名近世代数或抽象代数学，是数学 中最重要的、基础的分支之一，是在初等代数学的中最重要的、基础的分支之一，是在初等代数学的 基础上产生和发展起来的。基础上产生和发展起来的。 它起始于十九世纪初，形成于它起始于十九世纪初，形成于20世纪世纪30年代。年代。 在这期间，挪威数学家阿贝尔在这期间，挪威数学家阿贝尔(N.H. Abel)、法国数、法国数 学家伽罗瓦学家伽罗瓦(E. Galois)、英国数学家德、英国数学家德摩根摩根(A. De Morgan)和布尔和布尔(G. Boole)等人都做出了杰出贡献，等人

2、都做出了杰出贡献， 荷兰数学家范德瓦尔登荷兰数学家范德瓦尔登(B.L. Van Der Waerden)根据根据 德国数学家诺特德国数学家诺特(A.E. Noether)和奥地利数学家阿廷和奥地利数学家阿廷 (E. Artin)的讲稿，于的讲稿，于1930年和年和1931年分别出版了年分别出版了 近世代数学近世代数学一卷和二卷，标志着抽象代数的成一卷和二卷，标志着抽象代数的成 熟。熟。 2 第三部分第三部分 代数结构代数结构 代数结构是以研究数字、文字和更一般元素的运代数结构是以研究数字、文字和更一般元素的运 算的规律和由这些运算适合的公理而定义的各种数算的规律和由这些运算适合的公理而定义的各

3、种数 学结构的性质为中心问题。它对现代数学如扑拓学、学结构的性质为中心问题。它对现代数学如扑拓学、 泛函分析等以及一些其他科学领域，如计算机科学、泛函分析等以及一些其他科学领域，如计算机科学、 编码理论等，都有重要影响和广泛地应用。编码理论等，都有重要影响和广泛地应用。 3 第三部分第三部分 代数结构代数结构 主要内容主要内容: l 代数系统代数系统-二元运算及其性质、代数系统和子代二元运算及其性质、代数系统和子代 数数 l 半群与群半群与群-半群、独异点、群半群、独异点、群 l 环与域环与域-环、整环、域环、整环、域 l 格与布尔代数格与布尔代数-格、布尔代数格、布尔代数 4 第九章第九章

4、代数系统代数系统 主要内容主要内容: (1)二元运算及其性质二元运算及其性质 l 一元和二元运算定义及其实例一元和二元运算定义及其实例 l 二元运算的性质二元运算的性质 (2)代数系统代数系统 l 代数系统定义及其实例代数系统定义及其实例 l 子代数子代数 l 积代数积代数 (3)代数系统的同态与同构代数系统的同态与同构 5 9.1 二元运算及其性质二元运算及其性质 定义定义9.1 设设S为集合，函数为集合，函数f：S SS 称为称为S上的上的二元二元 运算运算，简称为二元运算，简称为二元运算 l S中任何两个元素都可以进行运算，且运算的结果中任何两个元素都可以进行运算，且运算的结果 惟一惟一

5、 l S中任何两个元素的运算结果都属于中任何两个元素的运算结果都属于S，即，即S对该运对该运 算封闭算封闭 例例1 (1) 自然数集合自然数集合N上的加法和乘法是上的加法和乘法是N上的二元运上的二元运 算，但减法和除法不是算，但减法和除法不是 (2) 整数集合整数集合Z上的加法、减法和乘法都是上的加法、减法和乘法都是Z上的二元上的二元 运算，而除法不是运算，而除法不是 (3) 非零实数集非零实数集R*上的乘法和除法都是上的乘法和除法都是R*上的二元运上的二元运 算，而加法和减法不是算，而加法和减法不是 6 实例实例 (4) 设设Mn(R)表示所有表示所有n 阶阶(n2)实矩阵的集合，即实矩阵的

6、集合，即 则矩阵加法和乘法都是则矩阵加法和乘法都是Mn(R)上的二元运算上的二元运算. (5) S为任意集合，则为任意集合，则、 为为P(S)上二元上二元 运算运算. (6) SS为为S上的所有函数的集合，则合成运算上的所有函数的集合，则合成运算 为为SS上上 二元运算二元运算. njiRa aaa aaa aaa RM ij nnnn n n n ,.,2 , 1,)( 21 22221 11211 7 一元运算的定义与实例一元运算的定义与实例 定义定义9.2 设设S为集合，函数为集合，函数 f:SS 称为称为S上的上的一元运一元运 算算，简称一元运算，简称一元运算. 例例2 (1) 求相反

7、数是整数集合求相反数是整数集合Z,有理数集合有理数集合Q和实数和实数 集集 合合R上的一元运算上的一元运算. (2) 在幂集在幂集P(S)上规定全集为上规定全集为S，则求绝对补运算，则求绝对补运算是是 P(S)上的一元运算上的一元运算. (3) 设设S为集合，令为集合，令A为为S上所有双射函数的集合，上所有双射函数的集合， A SS，求一个双射函数的反函数为，求一个双射函数的反函数为A上的一元运算上的一元运算. (4) 在在n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)上，求转置矩阵上，求转置矩阵 是是Mn(R)上的一元运算上的一元运算. 8 二元与一元运算的表示二元与一元运算的表示 1算符

8、算符 可以用可以用 , , , , , 等符号表示二元或一元运算，等符号表示二元或一元运算， 称为算符称为算符. 对二元运算对二元运算 ，如果，如果 x 与与 y 运算得到运算得到 z，记做，记做 x y = z 对一元运算对一元运算 , x的运算结果记作的运算结果记作 x. 2表示二元或一元运算的方法表示二元或一元运算的方法: 解析公式和运算解析公式和运算 表公式表示表公式表示 例例 设设R为实数集合，如下定义为实数集合，如下定义R上的二元运算上的二元运算 ： x, yR, x y = x. 那么那么 3 4 = 3， 0.5 ( 3) = 0.5 9 运算表：表示有穷集上的一元和二元运算运

9、算表：表示有穷集上的一元和二元运算 运算表运算表 二元运算的运算表二元运算的运算表 一元运算的运算一元运算的运算 表表 10 例例3 设设 S=P(a,b)，S上的上的 和和 运算运算的运算的运算 表如下表如下: 运算表的实例运算表的实例 11 二元运算的性质二元运算的性质 定义定义9.3 设设 为为S上的二元运算上的二元运算, (1) 若对任意若对任意x,yS 有有 x y=y x, 则称运算在则称运算在S上满上满 足足 交换律交换律. (2) 若对任意若对任意x,y,zS有有 (x y) z=x (y z), 则称运则称运 算在算在S 上满足上满足结合律结合律. (3) 若对任意若对任意x

10、S 有有 x x=x, 则称运算在则称运算在S上满足上满足幂幂 等等 律律. 12 二元运算的性质二元运算的性质 定义定义9.4 设设 和和 为为S上两个不同的二元运算上两个不同的二元运算, (1) 若对任意若对任意x,y,zS有有 (x y) z=(x z) (y z)， z (x y)=(z x) (z y), 则称则称 运算对运算对 运算满足运算满足 分配律分配律. (2) 若若 和和 都可交换都可交换,且对任意且对任意x,yS有有 x (x y)=x， x (x y)=x, 则称则称 和和 运算满足运算满足吸收律吸收律. 13 实例实例 Z, Q, R分别为整数、有理数、实数集；分别为

11、整数、有理数、实数集；Mn(R)为为n阶阶 实矩阵集合实矩阵集合, n 2；P(B)为幂集；为幂集；AA为从为从A到到A的函数的函数 集，集，|A| 2. 集合集合运算运算交换律交换律结合律结合律幂等律幂等律 Z,Q,R普通加法普通加法+ 普通乘法普通乘法 有有 有有 有有 有有 无无 无无 Mn(R)矩阵加法矩阵加法+ 矩阵乘法矩阵乘法 有有 无无 有有 有有 无无 无无 P(B)并并 交交 相对补相对补 对称差对称差 有有 有有 无无 有有 有有 有有 无无 有有 有有 有有 无无 无无 AA函数复合函数复合 无无有有无无 14 集合集合 运算运算分配律分配律吸收律吸收律 Z,Q,R普通加

12、法普通加法+与乘法与乘法 对对+可分配可分配 +对对 不分配不分配 无无 Mn(R)矩阵加法矩阵加法+与乘法与乘法 对对+可分配可分配 +对对 不分配不分配 无无 P(B)并并 与交与交 对对 可分配可分配 对对 可分配可分配 有有 交交 与对称差与对称差 对对 可分配可分配无无 实例实例 Z, Q, R分别为整数、有理数、实数集；分别为整数、有理数、实数集；Mn(R)为为n阶阶 实矩阵集合实矩阵集合, n 2；P(B)为幂集；为幂集；AA为从为从A到到A的函数的函数 集，集，|A| 2. 15 特异元素：单位元特异元素：单位元 定义定义9.5 设设 为为S上的二元运算上的二元运算, (1)

13、如果存在如果存在el (或或er) S，使得对任意，使得对任意 xS 都有都有 el x = x (或或 x er = x)， 则称则称el (或或er)是是S中关于中关于 运算的运算的左左(或或右右)单位元单位元. 若若eS关于关于 运算既是左单位元又是右单位元，则运算既是左单位元又是右单位元，则 称称 e为为S上关于上关于 运算的运算的单位元单位元. 单位元也叫做单位元也叫做幺元幺元. 16 特异元素：零元特异元素：零元 定义定义9.5 设设 为为S上的二元运算上的二元运算, (2) 如果存在如果存在 l (或或 r)S，使得对任意，使得对任意 xS 都有都有 l x = l (或或 x

14、r = r)， 则称则称 l (或或 r)是是S 中关于中关于 运算的运算的左左(或或右右)零元零元. 若若 S 关于关于 运算既是左零元又是右零元，则称运算既是左零元又是右零元，则称 为为S上关于运算上关于运算 的的零元零元. 17 特异元素：可逆元素和逆元特异元素：可逆元素和逆元 (3) 设设 为为S上的二元运算上的二元运算, 令令e为为S中关于运算中关于运算 的单的单 位位 元元. 对于对于xS，如果存在，如果存在yl (或或yr)S使得使得 yl x=e（或（或x yr=e） 则称则称yl (或或 yr)是是x的的左逆元左逆元（或（或右逆元右逆元）. 关于关于 运算，若运算，若yS 既

15、是既是 x 的左逆元又是的左逆元又是 x 的右逆的右逆 元，则称元，则称y为为x的的逆元逆元. 如果如果 x 的逆元存在，就称的逆元存在，就称 x 是是可逆的可逆的. 18 实例实例 集合集合运算运算单位元单位元零元零元逆元逆元 Z,Q, R 普通加法普通加法 + 普通乘法普通乘法 0 1 无无 0 x逆元逆元 x x逆元逆元x 1 (x 1 给定集合给定集合) Mn(R) 矩阵加法矩阵加法 + 矩阵乘法矩阵乘法 n阶全阶全0矩阵矩阵 n阶单位矩阶单位矩 阵阵 无无 n阶全阶全0 矩阵矩阵 X逆元逆元 X X的逆元的逆元X 1 （X可逆）可逆） P(B)并并 交交 对称差对称差 B B 无无

16、的逆元为的逆元为 B的逆元为的逆元为B X的逆元为的逆元为X 19 惟一性定理惟一性定理 定理定理9.1 设设 为为S上的二元运算，上的二元运算，el和和er分别为分别为S中关中关 于于 运算的左和右单位元，则运算的左和右单位元，则el = er = e为为S上关于上关于 运算运算 的惟一的单位元的惟一的单位元. 注意：注意： (1) 当当 |S| 2，单位元与零元是不同的；，单位元与零元是不同的； (2) 当当 |S| = 1时，这个元素既是单位元也是零元时，这个元素既是单位元也是零元. 20 定理定理9.2 设设 为为S上可结合的二元运算上可结合的二元运算, e为该运算的为该运算的 单位元

17、单位元, 对于对于xS 如果存在左逆元如果存在左逆元 yl 和右逆元和右逆元 yr, 则有则有 yl = yr= y, 且且 y是是 x 的惟一的逆元的惟一的逆元. 说明：说明： 对于可结合的二元运算，可逆元素对于可结合的二元运算，可逆元素 x 只有惟一的逆只有惟一的逆 元，记作元，记作 x 1 . 惟一性定理惟一性定理 21 9.2 代数系统代数系统 定义定义9.6 非空集合非空集合S和和S上上k个一元或二元运算个一元或二元运算f1,f2, fk组成的系统称为组成的系统称为代数系统代数系统, 简称代数，记做简称代数，记做. 实例：实例：(1) ,是代数系统，是代数系统，+ 和和分别表示普通加

18、法和乘法分别表示普通加法和乘法. (2) 是代数系统，和是代数系统，和分别表示分别表示 n 阶阶 (n2)实矩阵的加法和乘法实矩阵的加法和乘法. (3) 是代数系统，是代数系统，Zn0,1,n-1， 和和 分别表示模分别表示模n的加法和乘法，对于的加法和乘法，对于x,yZn， x y=(xy)modn，x y=(xy)modn (4) 是代数系统，是代数系统， 和和 为并和交，为并和交，为为 绝对补绝对补. 22 代数系统的成分与表示代数系统的成分与表示 构成代数系统的成分：构成代数系统的成分： l 集合（也叫载体，规定了参与运算的元素）集合（也叫载体，规定了参与运算的元素） l 运算（这里只

19、讨论有限个二元和一元运算）运算（这里只讨论有限个二元和一元运算） l 代数常数（通常是与运算相关的特异元素：如单代数常数（通常是与运算相关的特异元素：如单 位元等）位元等） 研究代数系统时，如果把运算具有它的特异元素也研究代数系统时，如果把运算具有它的特异元素也 作为系统的性质之一，那么这些特异元素可以作为作为系统的性质之一，那么这些特异元素可以作为 系统的成分，叫做代数常数系统的成分，叫做代数常数. 例如：代数系统例如：代数系统：集合：集合Z, 运算运算+, 代数常数代数常数0 代数系统代数系统：集合：集合P(S), 运算运算和和，无，无 代数常数代数常数. 23 代数系统的表示代数系统的表

20、示 (1) 列出所有的成分：集合、运算、代数常数（如果列出所有的成分：集合、运算、代数常数（如果 存在）存在） 如如, (2) 列出集合和运算，在规定系统性质时不涉及具有列出集合和运算，在规定系统性质时不涉及具有 单位元的性质（无代数常数）单位元的性质（无代数常数） 如如, (3) 用集合名称简单标记代数系统用集合名称简单标记代数系统 在前面已经对代数系统作了说明的前提下使用在前面已经对代数系统作了说明的前提下使用 如代数系统如代数系统Z, P(B) 24 同类型与同种代数系统同类型与同种代数系统 定义定义9.7 (1) 如果两个代数系统中运算的个数相同，如果两个代数系统中运算的个数相同， 对

21、应运算的元数相同，且代数常数的个数也相同，对应运算的元数相同，且代数常数的个数也相同， 则称它们是则称它们是同类型的同类型的代数系统代数系统. (2) 如果两个同类型的代数系统规定的运算性质也相如果两个同类型的代数系统规定的运算性质也相 同，则称为同，则称为同种的同种的代数系统代数系统. 25 同类型与同种代数系统同类型与同种代数系统 例如例如 V1=, V2=, 为为 n 阶全阶全0矩阵，矩阵，E为为 n 阶单位矩阵阶单位矩阵 V3=. l V1, V2, V3是同类型的代数系统，它们都含有是同类型的代数系统，它们都含有2个二个二 元运算元运算, 2个代数常数个代数常数. l V1, V2是

22、同种的代数系统，是同种的代数系统，V1, V2与与V3不是同种的不是同种的 代数系统代数系统. 26 V1V2V3 + 可交换、可结合可交换、可结合 可交换、可结合可交换、可结合 + 满足消去律满足消去律 满足消去律满足消去律 对对 + 可分配可分配 + 对对 不可分配不可分配 + 与与 没有吸收律没有吸收律 + 可交换、可结合可交换、可结合 可交换、可结合可交换、可结合 + 满足消去律满足消去律 不满足消去律不满足消去律 对对 + 可分配可分配 + 对对 不可分配不可分配 + 与与 没有吸收律没有吸收律 可交换、可结合可交换、可结合 可交换、可结合可交换、可结合 不满足消去律不满足消去律 不

23、满足消去律不满足消去律 对对可分配可分配 对对可分配可分配 与与满足吸收律满足吸收律 运算性质比较运算性质比较 27 子代数系统子代数系统 定义定义9.8设设V=是代数系统，是代数系统，B是是S的的 非空子集，如果非空子集，如果B对对f1, f2, , fk 都是封闭的，且都是封闭的，且B和和 S含有相同的代数常数，则称含有相同的代数常数，则称是是V的的 子代数系统子代数系统，简称子代数，简称子代数. 有时将子代数系统简记为有时将子代数系统简记为B. 28 子代数系统子代数系统 实例实例: N是是的子代数，的子代数，N也是也是的子代数的子代数; N 0是是的子代数，但不是的子代数，但不是的子的

24、子 代数代数. 说明：说明： (1) 子代数和原代数是同种的代数系统子代数和原代数是同种的代数系统. (2) 对于任何代数系统对于任何代数系统V=，其子代数，其子代数 一定存在一定存在. 29 关于子代数的术语关于子代数的术语 (1) 最大的子代数最大的子代数：就是：就是V本身本身 (2) 最小的子代数最小的子代数：如果令：如果令V中所有代数常数构成的中所有代数常数构成的 集合是集合是B，且，且B对对V中所有的运算都是封闭的，则中所有的运算都是封闭的，则 B就构成了就构成了V的最小的子代数的最小的子代数 (3) 最大和最小的子代数称为最大和最小的子代数称为V 的的平凡的子代数平凡的子代数 (4

25、) 若若B是是S的真子集，则的真子集，则B构成的子代数称为构成的子代数称为V的的真真 子代数子代数. 例例 设设V=,令令 nZ=nz | z Z,n为自然数，则为自然数，则 nZ是是V的子代数的子代数 当当n=1和和0时，时，nZ是是V的平凡的子代数，其他的都的平凡的子代数，其他的都 是是V的非平凡的真子代数的非平凡的真子代数. 30 积代数积代数 定义定义9.9 设设V1=和和V2=是同类型的代数是同类型的代数 系系 统，统， 和和 为二元运算，在集合为二元运算，在集合A B上如下定义二上如下定义二 元元 运算运算 ， , A B，有，有 = 称称V=为为V1与与V2的的积代数积代数，记作

26、，记作V1 V2. 这时也称这时也称V1和和V2为为V的的因子代数因子代数. 实例实例 Z2=0,1，V=， V1 V2= Z2 Z2=, , , = 注意：注意：积代数的定义可以推广到具有多个运算的同类积代数的定义可以推广到具有多个运算的同类 型的代数系统型的代数系统. 31 积代数的性质积代数的性质 定理定理9.3 设设V1=和和V2=是同类型的代数系是同类型的代数系 统，统，V1 V2=是它们的积代数是它们的积代数. (1) 如果如果 和和 运算是可交换（可结合、幂等）的，运算是可交换（可结合、幂等）的， 那么那么 运算也是可交换（可结合、幂等）的运算也是可交换（可结合、幂等）的. (2

27、) 如果如果 e1 和和 e2（ 1和和 2）分别为）分别为 和和 运算的单位运算的单位 元（零元），那么元（零元），那么（）也是）也是 运算运算 的单位元（零元）的单位元（零元）. (3) 如果如果 x 和和 y 分别为分别为 和和 运算的可逆元素，那么运算的可逆元素，那么 也是也是 运算的可逆元素，其逆元就是运算的可逆元素，其逆元就是 . 32 9.3 代数系统的同态与同构代数系统的同态与同构 定义定义9.10 设设V1=和和V2=是同类型的代数系是同类型的代数系 统，统，f:AB，且，且 x, y A 有有 f(x y) = f(x) f(y), 则称则称 f 是是V1到到V2的的同态同

28、态映射，简称同态映射，简称同态. 同态分类：同态分类： (1) f 如果是单射，则称为如果是单射，则称为单同态单同态 (2) 如果是满射，则称为如果是满射，则称为满同态满同态，这时称，这时称V2是是V1的的同同 态像态像， 记作记作V1 V2 (3) 如果是双射，则称为同构，也称代数系统如果是双射，则称为同构，也称代数系统V1同构同构 于于V2，记作，记作V1 V2 (4) 如果如果V1=V2，则称作，则称作自同态自同态 33 实例实例 (1) 设设V1=, V2=其中其中Z为整数集，为整数集，+为为 普通加法；普通加法；Zn=0,1,n 1， 为模为模n加加. 令令 f : ZZn，f (x

29、)=(x)mod n 那么那么 f 是是V1到到V2的满同态的满同态 (2) 设设V1=, V2=，其中，其中R和和R*分别为实分别为实 数集与非零实数集，数集与非零实数集，+ 和和 分别表示普通加法与分别表示普通加法与 乘法令乘法令 f : RR*，f (x)= ex 则则 f 是是V1到到V2的单同态的单同态. 34 实例实例 (3) 设设V=，其中，其中Z为整数集，为整数集，+为普通加法为普通加法. a Z，令，令 fa : ZZ，fa(x)=ax， 那么那么 fa 是是V的自同态的自同态. 当当a=0时称时称 f0 为零同态；为零同态； 当当a= 1时，称时，称 fa 为自同构；为自同

30、构； 除此之外其他的除此之外其他的 fa 都是单自同态都是单自同态. 35 练习练习1 1设设 运算为运算为Q上的二元运算，上的二元运算， x, y Q, x y = x+y+2xy, (1) 判断判断 运算是否满足交换律和结合律，并说明运算是否满足交换律和结合律，并说明 理由理由. (2) 求出求出 运算的单位元、零元和所有可逆元素的运算的单位元、零元和所有可逆元素的 逆元逆元. 36 (1) 运算可交换，可结合运算可交换，可结合. 任取任取 x, y Q, x y = x+y+2xy = y+x+2yx = y x, 任取任取 x, y, z Q, (x y) z = (x+y+2xy)+

31、z+2(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x+(y+z+2yz)+2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz 解答解答 37 (2) 设设 运算的单位元和零元分别为运算的单位元和零元分别为 e 和和 ，则，则对对 于任意于任意 x 有有 x e = x 成立，即成立，即 x+e+2xe = x e = 0 由于由于 运算可交换，所以运算可交换，所以 0 是幺元是幺元. 对于任意对于任意 x 有有x = 成立，即成立，即 x+ +2x = x+2x = 0 = 1/2 给定给定 x，设，设 x 的逆元为的逆元为

32、y, 则有则有 x y = 0 成立，即成立，即 x+y+2xy = 0 (x 1/2 ) 因此当因此当x 1/2时时， 是是x的逆元的逆元. x x y 21 x x 21 解答解答 38 2下面是三个运算表下面是三个运算表 (1) 说明那些运算是可交换的、可结合的、幂等的说明那些运算是可交换的、可结合的、幂等的. (2) 求出每个运算的单位元、零元、所有可逆元素求出每个运算的单位元、零元、所有可逆元素 的逆元。的逆元。 练习练习2 39 解 解答解答 (1) * 满足交换律，满足结合律，不满足幂等律满足交换律，满足结合律，不满足幂等律. 不满足交换律，满足结合律，满足幂等律不满足交换律，满

33、足结合律，满足幂等律. 满足交换律，满足结合律，不满足幂等律满足交换律，满足结合律，不满足幂等律. (2) * 的单位元为的单位元为b，没有零元，没有零元， a 1=c, b 1=b,c 1=a 的单位元和零元都不存在，没有可逆元素的单位元和零元都不存在，没有可逆元素. 的单位元为的单位元为 a，零元为，零元为c，a 1=a，b, c不是可逆不是可逆 元素元素. 40 解 解答解答 说明：关于结合律的判断说明：关于结合律的判断 (1)需要针对运算元素的每种选择进行验证，若需要针对运算元素的每种选择进行验证，若|A|=n， 一般需要验证一般需要验证n3个等式个等式. (2)单位元和零元不必参与验证单位元和零元不必参与验证. (3)通过对具体运算性质的分析也可能简化验证的复通过对具体运算性质的分析也可能简化验证的复 杂性杂性. 41 练习练习3 3.