《离散数学第9章-代数系统ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第9章-代数系统ppt课件.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7/31/2022 12:33 PM Discrete Math. , Chen Chen1离散数学离散数学Discrete MathematicsDiscrete Mathematics 7/31/2022 12:33 PM Discrete Math. , Chen Chen2第九章第九章 代数系统代数系统9.1 二元运算二元运算9.2 代数系统代数系统 本章在集合、关系和函数等概念基础上，研究更为复杂的对本章在集合、关系和函数等概念基础上，研究更为复杂的对象象代数系统，研究代数系统的性质和特殊的元素，代数系代数系统，研究代数系统的性质和特殊的元素，代数系统与代数系统之间的关系。如代数系统
2、的同态、满同态和同构，统与代数系统之间的关系。如代数系统的同态、满同态和同构，这些概念较为复杂也较为抽象，是本课程中的难点。它们将集这些概念较为复杂也较为抽象，是本课程中的难点。它们将集合、集合上的运算以及集合间的函数关系结合在一起进行研究。合、集合上的运算以及集合间的函数关系结合在一起进行研究。 前面四章内容是本章的基础，熟练地掌握集合、关系、函数前面四章内容是本章的基础，熟练地掌握集合、关系、函数等概念和性质是理解本章内容的关键。等概念和性质是理解本章内容的关键。 主要内容如下：主要内容如下：7/31/2022 12:33 PM Discrete Math. , Chen Chen3 二元
3、运算定义及其实例二元运算定义及其实例 一元运算定义及其实例一元运算定义及其实例 运算的表示运算的表示 二元运算的性质二元运算的性质n交换律、结合律、幂等律、消去律交换律、结合律、幂等律、消去律n分配律、吸收律分配律、吸收律 二元运算的特异元素二元运算的特异元素n单位元单位元n零元零元n可逆元素及其逆元可逆元素及其逆元7/31/2022 12:33 PM Discrete Math. , Chen Chen4定义定义9.1 设设 S 为集合为集合,函数函数 f：SSS 称为称为 S 上的上的二元运算二元运算, 简称为简称为二二元运算元运算. 也称也称 S 对对 f 封闭封闭. 验证一个运算是否为
4、集合验证一个运算是否为集合S上的二元运算主要考虑两点：上的二元运算主要考虑两点： 1. S中任何两个元素都可以进行这种运算，且运算结果是中任何两个元素都可以进行这种运算，且运算结果是唯一唯一的；的； 2. S中任何两个元素的运算结果都属于中任何两个元素的运算结果都属于S，即，即S对该运算是封闭对该运算是封闭的。的。 例例9.1 (1) N 上的二元运算：上的二元运算： (2) Z 上的二元运算：上的二元运算： (3) 非零实数集非零实数集 R* 上的二元运算上的二元运算: (4) 设设 S = a1, a2, , an, ai aj = ai : (5) 幂集幂集 P(S) 上的二元运算：上的
5、二元运算： (6) SS 为为 S 上的所有函数的集合：上的所有函数的集合：加法、乘法加法、乘法. 加法、减法、乘法加法、减法、乘法. 乘法、除法乘法、除法. 为为 S 上二元运算上二元运算. , . 合成运算合成运算 . 7/31/2022 12:33 PM Discrete Math. , Chen Chen5 (7) 设设 Mn(R) 表示所有表示所有 n 阶阶 (n2) 实矩阵的集合，即实矩阵的集合，即 njiRaaaaaaaaaaRMijnnnnnnn,.,2 , 1,)(212222111211 矩阵加法和乘法都是矩阵加法和乘法都是 Mn(R) 上的二元运算上的二元运算. 例例9.
6、2 设设R为实数集合为实数集合,定义定义R上的二元运算上的二元运算*： x,yR,x*y=x.计算：计算：*, (-5) *0.2 , 0*1/2. 解：解：3*4=3, (-5) *0.2=-5, 0*1/2=0 .7/31/2022 12:33 PM Discrete Math. , Chen Chen6定义定义9.2 设设 S 为集合，函数为集合，函数 f：SS 称为称为 S 上的一元运算，简称为上的一元运算，简称为一元运算一元运算. 例例9.3 (1) Z, Q 和和 R 上的一元运算上的一元运算: (2) 非零有理数集非零有理数集 Q*，非零实数集，非零实数集 R*上的一元运算上的一
7、元运算: (3) 复数集合复数集合 C 上的一元运算上的一元运算: (4) 幂集幂集 P(S) 上上, 全集为全集为 S: (5) A 为为 S 上所有双射函数的集合，上所有双射函数的集合，A SS: (6) 在在 Mn(R) ( n2 )上上: 求相反数求相反数 求倒数求倒数 求共轭复数求共轭复数 求绝对补运算求绝对补运算 求反函数求反函数 求转置矩阵求转置矩阵 算符算符： , , , , 等符号等符号, 表示二元或一元运算表示二元或一元运算 对二元运算对二元运算 ，如果，如果 x 与与 y 运算得到运算得到 z，记作，记作x y = z； 对一元运算对一元运算 , x 的运算结果记作的运算
8、结果记作 x 表示二元或一元运算的方法：公式、表示二元或一元运算的方法：公式、 运算表运算表注意：在同一问题中不同的运算使用不同的算符注意：在同一问题中不同的运算使用不同的算符7/31/2022 12:33 PM Discrete Math. , Chen Chen7公式表示公式表示 例例 设设 R 为实数集合，如下定义为实数集合，如下定义 R 上的二元运算上的二元运算 ： x, yR, x y = y . 那么那么 3 4 = 4 0.5 (-3) = -3运算表运算表（表示有穷集上的一元和二元运算）（表示有穷集上的一元和二元运算） a1 a2 an ai a1 a2 . . . ana1
9、a1 a1 a2 a1 ana2 a1 a2 a2 a2 an . . . . . . . . .an a1 an a2 an an a1 a2 . . . an a1 a2 . . . an7/31/2022 12:33 PM Discrete Math. , Chen Chen8 1 1 1,1121,2 例例9.4 S = P(1, 2), , 分别为对称差和绝对补运算分别为对称差和绝对补运算1, 2为全集）为全集） 的的运运算算表表 的的运运算算表表 解：解：例例9.5 Z5 = 0, 1, 2, 3, 4 , , 分别为模分别为模 5 加法与乘法加法与乘法 0 1 2 3 4 012
10、34 解：解： 0 1 2 3 4 0 1 2 3 4 a a 1 21,2 a 1 1,11 1.2 22 1,2 1 1,2 2 1 1,212 0 1 2 3 41 2 3 4 0 2 3 4 0 13 4 0 1 2 4 0 1 2 3 0 0 0 0 00 1 2 3 40 2 4 1 30 3 1 4 20 4 3 2 17/31/2022 12:33 PM Discrete Math. , Chen Chen9 定义定义9.35 设设 为为 S 上的二元运算上的二元运算, (1) 如果如果 x, y S 有有 x y = y x, 则称运算在则称运算在 S 上满足上满足交换律交换
11、律. (2) 如果如果 x, y, z S 有有 (x y) z = x (y z), 则称运算在则称运算在 S 上上满足满足结合律结合律. (3) 如果如果 x S 有有x x = x, 则称运算在则称运算在 S 上满足上满足幂等律幂等律.集合集合运算运算交换律交换律结合律结合律幂等律幂等律Z, Q, R普通加法普通加法+普通乘法普通乘法 Mn(R) ( n 2)矩阵加法矩阵加法+矩阵乘法矩阵乘法 P(B)并并 交交 相对补相对补 对称差对称差 AA( |A| 2)函数符合函数符合 有有有有有有有有有有有有有有有有有有有有有有有有有有有有有有无无无无无无无无无无无无无无无无无无无无无无有有7
12、/31/2022 12:33 PM Discrete Math. , Chen Chen10 定义定义9.67 设设 和和 为为 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 则称则称 和和 运算满足运算满足吸收律吸收律. 集合集合 运算运算分配律分配律吸收律吸收律 Z, Q, R普通
13、加法普通加法 + 与乘法与乘法 对对 + 可分配可分配无无+ 对对 不分配不分配 Mn(R)矩阵加法矩阵加法 + 与乘法与乘法 对对 + 可分配可分配无无+ 对对 不分配不分配 P(B)并并 与交与交 对对 可分配可分配有有 对对 可分配可分配交交 与对称差与对称差 对对 可分配可分配无无 对对 不分配不分配7/31/2022 12:33 PM Discrete Math. , Chen Chen11单位元单位元定义定义9.8 设设 为为S上的二元运算上的二元运算, 如果存在如果存在el（或（或er） S，使得对任意，使得对任意 xS 都有都有 el x = x ( 或或 x er = x )
14、，则称则称 el ( 或或 er )是是 S 中关于中关于 运算的运算的 左左 ( 或右或右 ) 单位元单位元. 若若 eS 关于关于 运算既是左单位元又是右单位元，则称运算既是左单位元又是右单位元，则称 e 为为 S 上关于上关于 运算的运算的 单位元单位元.单位元也叫做单位元也叫做 幺元幺元.零元零元定义定义9.9 设设 为为 S 上的二元运算上的二元运算, 如果存在如果存在l（或（或r）S，使得对任，使得对任意意 xS 都有都有 l x =l ( 或或 x r =r )，则称则称l ( 或或r )是是 S 中关于中关于 运算的运算的 左左 ( 或右或右) 零元零元. 若若S关于关于 运算
15、既是左零元又是右零元，则称运算既是左零元又是右零元，则称为为 S 上关于运上关于运算算 的的 零元零元.7/31/2022 12:33 PM Discrete Math. , Chen Chen12可逆元素及其逆元可逆元素及其逆元 定义定义9.10 令令 e 为为 S 中关于运算中关于运算 的单位元的单位元. 对于对于 xS，如果存在，如果存在yl（或（或 yr）S 使得使得 yl x = e（或（或 x yr = e），），则称则称 yl ( 或或 yr )是是 x 的的 左逆元左逆元 ( 或右逆元或右逆元 ). 关于关于 运算，若运算，若 yS 既是既是 x 的左逆元又是的左逆元又是 x
16、的右逆元，则称的右逆元，则称 y 为为 x 的的逆元逆元. 如果如果 x 的逆元存在，就称的逆元存在，就称 x 是是可逆的可逆的.7/31/2022 12:33 PM Discrete Math. , Chen Chen13集合集合运算运算单位元单位元零元零元逆元逆元Z,Q,R普通加法普通加法+普通乘法普通乘法 Mn(R)矩阵加法矩阵加法+矩阵乘法矩阵乘法 P(B)并并 交交 对称差对称差 0无无X 的逆元的逆元 x10X 的逆元的逆元 x 1(x-1属于给定集合属于给定集合)n阶全阶全0矩阵矩阵无无X逆元逆元 X n阶单位阶单位 矩阵矩阵n阶全阶全0矩阵矩阵X的逆元的逆元 X 1（X是可逆矩
17、阵）是可逆矩阵）B 的逆元为的逆元为 BB 的逆元为的逆元为 B无无X 的逆元为的逆元为 X7/31/2022 12:33 PM Discrete Math. , Chen Chen14定理定理9.1 设设 为为S上的二元运算，上的二元运算，el 和和 er 分别为分别为 S 中关于运算的左中关于运算的左和右单位元，则和右单位元，则 el = er = e 为为 S 上关于上关于 运算的惟一的单位元运算的惟一的单位元. 证证 el = el er = er 所以所以 el = er , 将这个单位元记作将这个单位元记作 e. 假设假设 e 也是也是 S 中的单位元，则有中的单位元，则有 e =
18、 e e = e. 惟一性得证惟一性得证.类似地可以证明关于零元的惟一性定理类似地可以证明关于零元的惟一性定理.定理定理9.2 设设 为为S上的二元运算，上的二元运算，l 和和r 分别为分别为 S 中关于运算的左中关于运算的左和右和右零零元，则元，则 l = r = 为为 S 上关于上关于 运算的惟一的运算的惟一的零元零元.定理定理9.3 当当 |S| 2，单位元与零元是不同的；，单位元与零元是不同的； 当当 |S| = 1 时，这个元素既是单位元也是零元时，这个元素既是单位元也是零元. 7/31/2022 12:33 PM Discrete Math. , Chen Chen15定理定理9.
19、4 设设 为为 S 上可结合的二元运算上可结合的二元运算, 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
20、= y 所以所以 y 是是 x 惟一的逆元惟一的逆元.说明：说明：对于可结合的二元运算，可逆元素对于可结合的二元运算，可逆元素 x 只有只有惟一的逆元惟一的逆元，记作，记作 x 1. 7/31/2022 12:33 PM Discrete Math. , Chen Chen16定义定义9.11 设设 为为V上二元运算，如果上二元运算，如果 x, y, z V， 若若 x y = x z，且，且 x不是零元，则不是零元，则 y = z; 若若 y x = z x, 且且 x 不是零元，则不是零元，则 y = z. 那么称那么称 运算满足运算满足 消去律消去律. 实例实例: (1) Z, Q, R
21、 关于普通加法和乘法满足消去律关于普通加法和乘法满足消去律.(2) Mn(R) 关于矩阵加法满足消去律，但是关于乘法不满足消去律关于矩阵加法满足消去律，但是关于乘法不满足消去律. (3) Zn关于模关于模 n 加法满足消去律，当加法满足消去律，当 n 为素数时关于模为素数时关于模 n乘法满足消乘法满足消去律去律. 当当 n 为合数时关于模为合数时关于模 n 乘法不满足消去律乘法不满足消去律. 7/31/2022 12:33 PM Discrete Math. , Chen Chen17解解 (1) 运算可交换，可结合，不满足幂等律，满足消去律。运算可交换，可结合，不满足幂等律，满足消去律。 x
22、, 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-xy) z = x+y+z-xy-xz-yz+xyz x (y z)= x + (y+z-yz) -x(y+z-yz) = x+y+z-xy-xz-yz+xyz 故故(x y) z= x (y z) ，即有，即有 运算可结合。运算可结合。例例9.6 设设 运算为运算为 Q 上的二元运算，上的二元运算， x, y Q, x y = x+y-xy, (1) 指出指出 运算的性质运算的性质. (2) 求求 运算的单
23、位元、零元和所有可逆元运算的单位元、零元和所有可逆元.7/31/2022 12:33 PM Discrete Math. , Chen Chen18给定给定 x，设，设 x 的逆元为的逆元为 y, 则有则有 x y = 0 成立，即成立，即 x+y-xy = 0 (x = 1) 因此当因此当 x 1时，时， 是是 x 的逆元的逆元. 1xyx1xyx(2) 设设 运算的单位元和零元分别为运算的单位元和零元分别为 e 和和 ，则，则 x 有有 x e = x 成立，即成立，即 x+e-xe = x e = 0 由于由于 运算可交换，所以运算可交换，所以 0 是幺元是幺元. x 有有 x = 成立
24、，即成立，即 x+ -x = x -x = 0 = 1 运算运算不满足幂等律：不满足幂等律：因为因为2 Q，但，但 2 2 = 2+2-2 2 =0 2。 运算满足消去律。运算满足消去律。 x, y, z Q, （x1）有）有x y=x z x+y-xy=x+z-xz (y-z) =x(y-z) y=z 故故 运算满足左消去律。运算满足左消去律。7/31/2022 12:33 PM Discrete Math. , Chen Chen19例例9.7 (1) 说明那些运算是交换的、可结合的、幂等的说明那些运算是交换的、可结合的、幂等的. (2) 求出运算的单位元、零元、所有可逆元素的逆元求出运算
25、的单位元、零元、所有可逆元素的逆元. 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, 没零元，没零元， a 1 = c, b 1 = b, c 1 = a 的单位元和零元都不存在，没有可逆元素的单位元和零元都不存在，没有可逆元素. 的单位元为的单位元为 a，零元为，零元为c, a 1=a. b, c不可逆不
26、可逆. 7/31/2022 12:33 PM Discrete Math. , Chen Chen20例例 设设 A = a, b, c , 构造构造 A 上的二元运算上的二元运算* 使得使得 a*b =c, c*b = b, 且且*运算是幂等的、可交换的，给出关于运算是幂等的、可交换的，给出关于*运算的一个运算表，运算的一个运算表，说明它是否可结合，为什么？说明它是否可结合，为什么？ * a b c a b c a c b b c cb根据幂等律和已知条件根据幂等律和已知条件a*b =c, c*b = b 得到运算表得到运算表根据交换律得到新的运算表根据交换律得到新的运算表方框方框 可以填入
27、可以填入a, b, c中任一选定的中任一选定的符号符号, ,完成运算表完成运算表不结合，因为不结合，因为 (a*b)*b = c*b = b, a*(b*b) = a*b = c 7/31/2022 12:33 PM Discrete Math. , Chen Chen21交换律：运算表关于主对角线对称交换律：运算表关于主对角线对称幂等律：主对角线元素排列与表头顺序一致幂等律：主对角线元素排列与表头顺序一致消去律：所在的行与列中没有重复元素消去律：所在的行与列中没有重复元素单位元单位元: 所在的行与列的元素排列都与表头一致所在的行与列的元素排列都与表头一致零元：元素的行与列都由该元素自身构成零
28、元：元素的行与列都由该元素自身构成A 的可逆元：的可逆元：a 所在的行中某列所在的行中某列 (比如第比如第 j 列列) 元素为元素为 e，且第，且第 j 行行 i 列的元素也是列的元素也是 e，那么，那么 a 与第与第 j 个元素互逆个元素互逆结合律：除了单位元、零元之外，要对所有结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示个元素的组合验证表示结合律的等式是否成立结合律的等式是否成立7/31/2022 12:33 PM Discrete Math. , Chen Chen22代数系统定义代数系统定义同类型代数系统同类型代数系统子代数子代数7/31/2022 12:33 PM D
29、iscrete Math. , Chen Chen23定义定义 9.12非空集合非空集合 S 和和 S 上上 k 个一元或二元运算个一元或二元运算 f1, f2, , fk 组组成的系统称为一个成的系统称为一个代数系统代数系统, 简称简称代数代数，记做，记做 V=. 实例实例:(1) , , 是代数系统，是代数系统，+ 和和 分别表示普通加分别表示普通加法和乘法法和乘法. (2) 是代数系统，是代数系统， + 和和 分别表示分别表示n 阶阶 (n2) 实矩阵的加实矩阵的加法和乘法法和乘法. (3) 是代数系统，是代数系统，Zn0, 1, , n-1， 和和 分别表示模分别表示模 n 的加法和乘
30、法，的加法和乘法， x,yZn， x y = (xy) mod n，x y = (xy) mod n(4) 也是代数系统，也是代数系统， 和和为并和交，为并和交，为绝对补为绝对补 S 称为代数系统的称为代数系统的载体载体， S 和运算叫做代数系统的成分和运算叫做代数系统的成分. 有的代有的代数系统定义指定了数系统定义指定了S中的中的特殊元素特殊元素，称为，称为代数常数代数常数, 例如二元运算的例如二元运算的单位元单位元.有时也将代数常数作为系统的成分有时也将代数常数作为系统的成分. 7/31/2022 12:33 PM Discrete Math. , Chen Chen24定义定义9.13
31、如果两个代数系统中运算的个数相同，对应运算的元数相如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分成成分,也称它们是也称它们是 同类型的同类型的 代数系统代数系统.例例: V1 = , V2 = , 为为 n 阶全阶全 0 矩阵，矩阵，E 为为 n 阶单位矩阵阶单位矩阵 V3 = V1V2V3+ 可交换, 可结合 可交换, 可结合+ 满足消去律 满足消去律 对+可分配+ 对 不可分配+与 没有吸收律+ 可交换, 可结合 可交换, 可结合+ 满足消去律 满足消去律 对+可分
32、配+ 对 不可分配+与 没有吸收律可交换, 可结合可交换, 可结合不满足消去律 不满足消去律对可分配对可分配与满足吸收律7/31/2022 12:33 PM Discrete Math. , Chen Chen25定义定义9.14 设设V= 是代数系统，是代数系统，B 是是 S 的非空子集的非空子集 ，如果，如果 B 对对 f1, f2, , fk 都是都是封闭封闭的，且的，且 B 和和 S 含有含有相同的代数常数相同的代数常数，则称，则称 是是 V 的子代数系统，简称的子代数系统，简称 子代数子代数. 有时将子代数系统简记有时将子代数系统简记为为 B.实例实例 N是是 和和的子代数的子代数.
33、 N 0是是的子代数，但不是的子代数，但不是的子代数的子代数说明：代数和原代数是同类型的代数系统说明：代数和原代数是同类型的代数系统 对于任何代数系统对于任何代数系统 V ，其子代数一定存在，其子代数一定存在. 最大的子代数最大的子代数 就是就是V 本身本身. 如果如果V 中所有代数常数构成集合中所有代数常数构成集合 B，且，且 B 对对V 中所有运算封闭，则中所有运算封闭，则 B 就就构成了构成了V 的的最小的子代数最小的子代数. 最大和最小子代数称为最大和最小子代数称为V 的的平凡的子代数平凡的子代数. 若若 B 是是 S 的真子集，则的真子集，则 B 构成的子代数称为构成的子代数称为V 的的真子代数真子代数 .7/31/2022 12:33 PM Discrete Math. , Chen Chen26例例9.8 设设V=，令，令 nZ = nz | zZ，n 为自然数，则为自然数，则 (1)nZ 是是 V 的子代数的子代数, (2)当当 n = 1 和和 0 时，时，nZ 是是 V 的平凡的子代数，的平凡的子代数， (3)其他的其他的n都是都是 V 的非平凡的真子代数的非平凡的真子代数.