离散数学第七章代数系统

1、离散数学第七章代数系统1第1页，共50页，2022年，5月20日，11点11分，星期五 本章在集合、关系和函数等概念基础上，研究更为复杂的对象代数系统，研究代数系统的性质和特殊的元素，代数系统与代数系统之间的关系（如代数系统的同态和同构），这些概念较为复杂也较为抽象，是本课程中的难点。它们将集合、集合上的运算以及集合间的函数关系结合在一起进行研究。第七章 代数系统2第2页，共50页，2022年，5月20日，11点11分，星期五第七章 代数系统7.1 二元运算及其性质 二元运算定义及其实例 一元运算定义及其实例 运算的表示 二元运算的性质交换律、结合律、幂等律、消去律分配律、吸收律 二元运算的特

2、异元素单位元零元可逆元素及其逆元3第3页，共50页，2022年，5月20日，11点11分，星期五二元运算的定义及其实例定义：设 S 为集合,函数 f：SSS 称为S上的二元运算, 简称为二元运算. 也称 S 对 f 封闭. 例1 (1) N 上的二元运算：加法、乘法. (2) Z 上的二元运算：加法、减法、乘法. (3) 非零实数集 R* 上的二元运算: 乘法、除法. (4) 设 S = a1, a2, , an, ai aj = ai ， 为 S 上二 元运算. 4第4页，共50页，2022年，5月20日，11点11分，星期五二元运算的实例（续） (5) 设 Mn(R) 表示所有 n 阶 (

3、n2) 实矩阵的集 合，即 矩阵加法和乘法都是 Mn(R) 上的二元运算. (6) 幂集 P(S) 上的二元运算：, . (7) SS 为 S 上的所有函数的集合：合成运算. 5第5页，共50页，2022年，5月20日，11点11分，星期五二元运算的定义及其实例从二元运算的定义可知它有三点涵义:(1)S中任意两个元素都有运算结果;(2)运算是封闭的,即运算结果仍在S中;(3)结果是唯一的。6第6页，共50页，2022年，5月20日，11点11分，星期五一元运算的定义与实例定义：设 S 为集合，函数 f：SS 称为 S 上的一元运算，简称为一元运算. 例2 (1) Z, Q 和 R 上的一元运算

4、: 求相反数 (2) 非零有理数集 Q*，非零实数集 R*上的 一元运算: 求倒数 (3) 幂集 P(S) 上, 全集为 S: 求绝对补运算 (4) A 为 S 上所有双射函数的集合，ASS: 求 反函数 (5) 在 Mn(R) ( n2 )上，求转置矩阵 7第7页，共50页，2022年，5月20日，11点11分，星期五二元与一元运算的表示运算符：, , , , 等符号表示二元或一元运算。 对二元运算 ，如果 x 与 y 运算得到 z，记做 xy = z； 对一元运算 , x 的运算结果记作 x。表示二元或一元运算的方法：公式、 运算表。注意：在同一问题中不同的运算使用不同的运算符8第8页，共

5、50页，2022年，5月20日，11点11分，星期五公式表示 例3 设 R 为实数集合，如下定义 R 上的二元运算 ： x, yR, x y = x. 那么 3 4 = 3 0.5 (-3) = 0.5运算表（表示有穷集上的一元和二元运算） 二元与一元运算的表示（续）9第9页，共50页，2022年，5月20日，11点11分，星期五运算表的形式 a1 a2 an ai a1 a2 . . . ana1a1 a1a2 a1ana2a1 a2a2 a2an . . . . . . . . .ana1 ana2 anan a1 a2 . . . ana1a2 . . .an10第10页，共50页，20

6、22年，5月20日，11点11分，星期五运算表的实例例4 A = P(a, b), , 分别为对称差和绝对补运算 （a,b为全集） 的运算表 的运算表 a b a,b X Xaba,b a b a,b a a.b b b a,b aa,b b a a ba,ba,bab11第11页，共50页，2022年，5月20日，11点11分，星期五运算表的实例（续）例5 Z5 = 0, 1, 2, 3, 4 , , 分别为模 5 加法与乘法 的运算表 的运算表 0 1 2 3 4 0 1 2 3 401234 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2

7、3 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 12第12页，共50页，2022年，5月20日，11点11分，星期五二元运算的性质 定义：设 为 S 上的二元运算, (1) 如果对于任意的 x, y S 有 x y = y x, 则称运算在 S 上满足交换律. (2) 如果对于任意的 x, y, z S 有 (x y) z = x (y z), 则称运算在 S 上满足结合律. (3) 如果对于任意的 x S 有 x x = x, 则称运算在 S 上满足幂等律.13第13页，共50页，2022年，5月20日，11点11分

8、，星期五实例分析Z, Q, R分别为整数、有理数、实数集；Mn(R)为 n 阶实矩阵集合, n2；P(B)为幂集；AA 为 A上A，|A|2.集合运算交换律结合律幂等律Z, Q, R普通加法+普通乘法Mn(R)矩阵加法+矩阵乘法P(B)并交相对补对称差AA函数符合14第14页，共50页，2022年，5月20日，11点11分，星期五实例分析Z, Q, R分别为整数、有理数、实数集；Mn(R)为 n 阶实矩阵集合, n2；P(B)为幂集；AA 为 A上A，|A|2.集合运算交换律结合律幂等律Z, Q, R普通加法+有有无普通乘法有有无Mn(R)矩阵加法+有有无矩阵乘法无有无P(B)并有有有交有有有

9、相对补无无无对称差有有无AA函数符合无有无15第15页，共50页，2022年，5月20日，11点11分，星期五二元运算的性质（续） 定义 设 和 为 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 则称 和 运算满足吸收律. 16第16页，共50页，2022年，5月20日，11点11分，星期五实例分析 集合 运算分配律吸收律 Z,Q,R普通加法 + 与乘法 Mn

10、(R)矩阵加法 + 与乘法 P(B)并 与交 交 与对称差 Z, Q, R分别为整数、有理数、实数集；Mn(R) 为 n 阶实矩阵集合, n2；P(B)为幂集；AA为 A上A，|A|2.17第17页，共50页，2022年，5月20日，11点11分，星期五实例分析 集合 运算分配律吸收律 Z,Q,R普通加法 + 与乘法 对 + 可分配无+ 对 不分配 Mn(R)矩阵加法 + 与乘法 对 + 可分配无+ 对 不分配 P(B)并 与交 对 可分配有 对 可分配交 与对称差 对 可分配无 对 不分配Z, Q, R分别为整数、有理数、实数集；Mn(R) 为 n 阶实矩阵集合, n2；P(B)为幂集；AA

11、为 A上A，|A|2.18第18页，共50页，2022年，5月20日，11点11分，星期五二元运算的特异元素单位元定义 设为S上的二元运算, 如果存在el（或er）S，使得对任意 xS 都有 el x = x ( 或 x er = x )，则称 el ( 或 er )是 S 中关于 运算的 左 ( 或右 ) 单位元. 若 eS 关于 运算既是左单位元又是右单位元，则称 e 为 S 上关于 运算的 单位元. 单位元也叫做 幺元.19第19页，共50页，2022年，5月20日，11点11分，星期五二元运算的特异元素（续）零元设 为 S 上的二元运算, 如果存在l（或r）S，使得对任意 xS 都有

12、l x =l ( 或 x r =r )，则称l ( 或r )是 S 中关于 运算的 左 ( 或右) 零元. 若S关于运算既是左零元又是右零元，则称为 S 上关于运算 的 零元.20第20页，共50页，2022年，5月20日，11点11分，星期五二元运算的特异元素（续）可逆元素及其逆元 令 e 为 S 中关于运算的单位元. 对于 xS，如果存在yl（或 yr）S 使得 yl x = e（或 x yr = e），则称 yl ( 或 yr )是 x 的 左逆元 ( 或右逆元 ). 关于 运算，若 yS 既是 x 的左逆元又是 x 的右逆元，则称 y 为 x 的逆元. 如果 x 的逆元存在，就称 x

13、是可逆的.21第21页，共50页，2022年，5月20日，11点11分，星期五实例分析集合运算单位元零元逆元Z,Q,R普通加法+普通乘法Mn(R)矩阵加法+矩阵乘法P(B)并交对称差22第22页，共50页，2022年，5月20日，11点11分，星期五实例分析集合运算单位元零元逆元Z,Q,R普通加法+0无X 的逆元 x普通乘法10X 的逆元 x1(x-1属于给定集合)Mn(R)矩阵加法+n阶全0矩阵无X逆元X矩阵乘法 n阶单位 矩阵n阶全0矩阵X的逆元 X1（X是可逆矩阵）P(B)并B 的逆元为 交BB 的逆元为 B对称差无X 的逆元为 X23第23页，共50页，2022年，5月20日，11点1

14、1分，星期五唯一性定理定理 设 为S上的二元运算，el 和 er 分别为 S 中关于运算的左和右单位元，则 el = er = e 为 S 上关于 运算的唯一的单位元.证：el = el er = el er = er 所以 el = er , 将这个单位元记作 e. 假设 e 也是 S 中的单位元，则有 e = e e = e. 唯一性得证.类似地可以证明关于零元的唯一性定理.注意：当 |S| 2，单位元与零元是不同的； 当 |S| = 1 时，这个元素既是单位元也是零元. 24第24页，共50页，2022年，5月20日，11点11分，星期五唯一性定理（续）定理 设 为 S 上可结合的二元运

15、算, e 为该运算的单位元, 对于 xS 如果存在左逆元 yl 和右逆元 yr , 则有 yl = yr= y, 且 y 是 x 的唯一的逆元.证：由 yl x = e 和 x yr = e 得 yl = yl e = yl (x yr) = (yl x) yr = e yr = yr令 yl = yr = y, 则 y 是 x 的逆元. 假若 yS 也是 x 的逆元, 则 y= y e = y (x y) = (y x) y = e y = y所以 y 是 x 唯一的逆元.说明：对于可结合的二元运算，可逆元素 x 只有唯一的逆元，记作 x1. 25第25页，共50页，2022年，5月20日，

16、11点11分，星期五消去律定义：设为V上二元运算，如果 x, y, zV， 若 x y = x z，且 x不是零元，则 y = z 若 y x = z x, 且 x 不是零元，则 y = z 那么称 运算满足消去律. 26第26页，共50页，2022年，5月20日，11点11分，星期五消去律实例: （1）Z, Q, R 关于普通加法和乘法满足消去律.（2）Mn(R) 关于矩阵加法满足消去律，但是关于矩阵乘法不满足消去律. （3）Zn关于模 n 加法满足消去律，当 n 为素数时关于模 n乘法满足消去律. 当 n 为合数时关于模 n 乘法不满足消去律. 27第27页，共50页，2022年，5月20

17、日，11点11分，星期五例题分析解 (1) 运算可交换，可结合. 任取x, yQ, x y = x+y+2xy = y+x+2yx = y x, 任取x, y, zQ, (x y) z= (x+y+2xy) + 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例6 设 运算为 Q 上的二元运算， x, yQ, xy = x+y+2xy, (1) 运算是否满足交换和结合律? 说明理由. (2) 求 运算的单位元、零元和所有可逆元.28第28

18、页，共50页，2022年，5月20日，11点11分，星期五给定 x，设 x 的逆元为 y, 则有 x y = 0 成立，即 x+y+2xy = 0 (x = 1/2) 因此当 x 1/2时， 是 x 的逆元. 例题分析（续）(2) 设运算的单位元和零元分别为 e 和 ，则对于任意 x 有 xe = x 成立，即 x+e+2xe = x e = 0 由于 运算可交换，所以 0 是幺元.对于任意 x 有 x = 成立，即 x+2 x = x + 2 x = 0 = 1/2 29第29页，共50页，2022年，5月20日，11点11分，星期五例题分析（续）例7 (1) 说明那些运算是交换的、可结合的

19、、幂等的. (2) 求出运算的单位元、零元、所有可逆元素的逆元. a b c a b c a b c a b c c a b a b c b c a a b c a a a b b b c c c a b c a b c b c c c c c解 (1) 满足交换、结合律； 满足结合、幂等律； 满足交换、结合律. (2) 的单位元为 b, 没零元， a1 = c, b1 = b, c1 = a 的单位元和零元都不存在，没有可逆元素. 的单位元为 a，零元为c, a1=a. b, c不可逆. 30第30页，共50页，2022年，5月20日，11点11分，星期五由运算表判别算律的一般方法交换律：运

20、算表关于主对角线对称幂等律：主对角线元素排列与表头顺序一致消去律：所在的行与列中没有重复元素单位元: 所在的行与列的元素排列都与表头一致零元：元素的行与列都由该元素自身构成A 的可逆元：a 所在的行中某列 (比如第 j 列) 元素为 e，且第 j 行 i 列的元素也是 e，那么 a 与第 j 个元素互逆结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示结合律的等式是否成立31第31页，共50页，2022年，5月20日，11点11分，星期五代数系统定义与实例同类型与同种的代数系统子代数第七章 代数系统7.2 代数系统及其子代数32第32页，共50页，2022年，5月20日，11点11分

21、，星期五代数系统定义与实例定义 非空集合 S 和 S 上 k 个一元或二元运算 f1, f2, , fk 组成的系统称为一个代数系统, 简称代数，记做 V=. S 称为代数系统的载体， S 和运算叫做代数系统的成分. 有的代数系统定义指定了S中的特殊元素，称为代数常数, 例如二元运算的单位元.有时也将代数常数作为系统的成分. 33第33页，共50页，2022年，5月20日，11点11分，星期五实例, , 是代数系统， + 和 分别表示普通加法和乘法. 是代数系统， + 和 分别表示n 阶 (n2) 实矩阵的加法和乘法. 是代数系统，Zn0, 1, , n-1， 和 分别表示模 n 的加法和乘法

22、，x,yZn， xy = (xy) mod n，xy = (xy) mod n 也是代数系统， 和为并和交，为绝对补34第34页，共50页，2022年，5月20日，11点11分，星期五同类型与同种代数系统定义 (1) 如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是 同类型的 代数系统. (2) 如果两个同类型的代数系统规定的运算性质也相同，则称为 同种的 代数系统. 例1 V1 = , V2 = , 为 n 阶全 0 矩阵，E 为 n 阶单位矩阵 V3 = 35第35页，共50页，2022年，5月20日，11点11分，星期五V1V2V3+ 可交换, 可

23、结合 可交换, 可结合+ 满足消去律 满足消去律 对+可分配+ 对 不可分配+与 没有吸收律+ 可交换, 可结合 可交换, 可结合+ 满足消去律 满足消去律 对+可分配+ 对 不可分配+与 没有吸收律可交换, 可结合可交换, 可结合不满足消去律 不满足消去律对可分配对可分配与满足吸收律V1, V2, V3是同类型的代数系统V1, V2是同种的代数系统V1, V2与V3不是同种的代数系统同类型与同种代数系统（续）36第36页，共50页，2022年，5月20日，11点11分，星期五子代数定义 设V= 是代数系统，B 是 S 的非空子集 ，如果 B 对 f1, f2, , fk 都是封闭的，且 B

24、和 S 含有相同的代数常数，则称 是 V 的子代数系统，简称 子代数. 有时将子代数系统简记为 B.实例 N是 和的子代数. N0是的子代数，但不是的子代数说明： 子代数和原代数是同种的代数系统 对于任何代数系统 V ，其子代数一定存在. 37第37页，共50页，2022年，5月20日，11点11分，星期五同态映射的定义同态映射的分类单同态、满同态、同构自同态同态映射的性质第七章 代数系统7.3 代数系统的同态与同构38第38页，共50页，2022年，5月20日，11点11分，星期五同态映射的定义定义 设 V1=和 V2=是代数系统，其中 和 是二元运算. f: S1S2, 且x,yS1, f

25、 (xy) = f(x) f( y), 则称 f 为V1到 V2 的同态映射，简称同态. 39第39页，共50页，2022年，5月20日，11点11分，星期五更广泛的同态映射定义定义 设 V1=和 V2=是代数系统，其中 和 是二元运算. f: S1S2, 且x,yS1 f (x y) = f(x) f(y) , f (x y) = f(x) f(y)则称 f 为V1到 V2 的同态映射，简称同态. 设 V1=和 V2=是代数系统，其中 和 是二元运算. 和 是一元运算， f: S1S2, 且x,yS1 f (xy)=f(x)f(y), f (xy)=f(x)f(y), f ( x)=f(x)

26、 则称 f 为V1到 V2 的同态映射，简称同态.40第40页，共50页，2022年，5月20日，11点11分，星期五例题例1 V=, 判断下面的哪些函数是V 的自同态？ (1) f(x)=|x| (2) f(x)=2x (3) f(x)=x2 (4) f(x)=1/x (5) f(x)= x (6) f(x)=x+1解 (2) , (5), (6) 不是自同态. (1) 是同态， f(xy) = |xy| = |x| |y| = f(x) f(y) (3) 是同态， f(xy) = (xy)2 = x2 y2 = f(x) f(y) (4) 是同态， f(xy) = 1/(xy) =1/x

27、1/y = f(x) f(y) 41第41页，共50页，2022年，5月20日，11点11分，星期五特殊同态映射的分类同态映射如果是单射，则称为单同态；如果是满射，则称为 满同态，这时称 V2 是 V1 的同态像，记作 V1V2；如果是双射，则称为 同构，也称代数系统 V1 同构于V2，记作 V1V2 . 对于代数系统 V，它到自身的同态称为自同态. 类似地可以定义单自同态、满自同态和自同构. 42第42页，共50页，2022年，5月20日，11点11分，星期五同态映射的实例例2 设V=，aZ，令 fa：ZZ，fa(x)=ax那么 fa是V的自同态. 因为x,yZ，有 fa(x+y) = a(

28、x+y) = ax+ay = fa(x)+fa(y) 当 a = 0 时称 f0为零同态；当a=1时，称 fa为自同构；除此之外其他的 fa 都是单自同态. 43第43页，共50页，2022年，5月20日，11点11分，星期五例3 设V1=, V2= ，其中Q*= Q0，令 f：QQ*, f(x)=ex 那么 f 是V1到V2的同态映射，因为x, yQ有 f(x+y) = ex+y = exey = f(x) f(y). 不难看出 f 是单同态. 同态映射的实例（续）44第44页，共50页，2022年，5月20日，11点11分，星期五同态映射的实例（续）例4 V1=，V2=，Zn=0,1, , n-1, 是模 n 加. 令 f：ZZn，f(x) = (x)mod n则 f 是V1到 V2 的满同态. x, yZ有 f(x+y) = (x+y)mod n = (x)mod n (y)mod n = f(x) f(y)45第45页，共50页，20