离散数学--14.1代数系统.ppt

第14章 代数系统 1 第14章 代数系统 14.1 二元运算及其性质 14.2 代数系统 14.3 几个典型的代数系统 2 14.1 二元运算及其性质 14.1.1 二元运算与一元运算的定义 二元运算定义及其实例 一元运算定义及其实例 运算的表示 14.1.2 二元运算的性质 交换律、结合律、幂等律、分配律、吸收律 特异元素：单位元、零元、可逆元 消去律 3 二元运算的定义及其实例 定义14.1 设 S 为集合,函数 f : SSS 称为S上的二元 运算, 简称为二元运算. 也称 S 对 f 封闭. 例1 (1) N上的二元运算：加法、乘法. (2) Z上的二元运算：加法、减法、乘法. (3) 非零实数集 R*上的二元运算: 乘法、除法. (4) 设 S= a1, a2, , an , ai aj = ai ， 为S上二元运算. (5) 设Mn(R)表示所有n 阶(n2)实矩阵的集合，即 矩阵加法和乘法都是Mn(R)上的二元运算. (6) 幂集 P(S)上的二元运算：、. (7) SS为S上的所有函数的集合, SS的合成运算. 4 一元运算的定义与实例 定义14.2 设S为集合，函数 f : SS 称为S上的一元运算 ，简称为一元运算. 例2 (1) Z, Q 和 R上求相反数的运算 (2) 非零有理数集Q*，非零实数集 R*上求倒数运算 (3) 复数集合C上求共轭复数的运算 (4) 幂集P(S)上, 全集为S，求绝对补运算 (5) A 为S上所有双射函数的集合，ASS，求反函数 (6) 在 Mn(R) (n2)上求转置矩阵 5 二元与一元运算的表示 算符：, , , , 等符号 表示二元或一元运算 对二元运算，如果 x 与 y 运算得到 z，记做 xy=z； 对一元运算, x 的运算结果记作 x 表示二元或一元运算的方法：公式、 运算表 注意：在同一个问题中不同的运算使用不同的算符 6 公式表示 例3 设 R 为实数集合，如下定义 R 上的二元运算 ： x, yR, x y = x. 那么 3 4 = 3， 0.5 (3) = 0.5 运算表（表示有穷集上的一元和二元运算） 二元运算的运算表 一元运算的运算表 a1 a2 an ai a1 a2 . . an a1a1 a1a2 a1an a2a1 a2a2 a2an . . . . . . ana1 ana2 anan a1 a2 . . an a1 a2 . . an 实例 7 运算表的实例 例4 A=P(a,b), , 分别为对称差和绝对补运算 （a,b为全集） 的运算表 的运算表 a b a,b X X a b a,b a b a,b a a.b b b a,b a a,b b a a b a,b a,b a b 8 运算表的实例(续) 例5 Z5= 0, 1, 2, 3, 4 , , 分别为模 5 加法与乘法 的运算表 的运算表 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 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 9 二元运算的性质 定义14.3 设 为 S 上的二元运算, (1) 如果对于任意的 x, yS 有 x y = y x, 则称运算在 S 上满足交换律. (2) 如果对于任意的 x, y, zS 有 (x y) z = x (y z), 则称运算在 S 上满足结合律. (3) 如果对于任意的 xS 有 x x = x, 则称运算在 S 上满足幂等律. 10 实例 例6 Z, Q, R分别为整数、有理数、实数集；Mn(R)为n阶 实矩阵集合, n2；P(B)为幂集；AA为A上A，|A|2. 集合运算交换换律结结合律幂幂等律 Z, Q, R普通加法+有有无 普通乘法有有无 Mn(R)矩阵阵加法+有有无 矩阵阵乘法无有无 P(B)并有有有 交有有有 相对补对补 无无无 对对称差有有无 AA 函数复合 无有无 11 二元运算的性质(续) 定义14.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 则称 和 运算满足吸收律. 12 实例分析 集合 运算分配律吸收律 Z,Q,R 普通加法 + 与乘法 对对 + 可分配无 + 对对 不分配 Mn(R) 矩阵阵加法 + 与乘法 对对 + 可分配无 + 对对 不分配 P(B) 并 与交 对对 可分 配 有 对对 可分 配 交 与对对称差 对对 可分 配 无 对对 不分 配 例7 Z, Q, R分别为整数、有理数、实数集；Mn(R)为n阶 实矩阵集合, n2；P(B)为幂集；AA为A上A，|A|2. 13 二元运算的特异元素 单位元 定义14.5 设 为S上的二元运算, 如果存在el（或er）S ，使得对任意 xS 都有 el x = x ( 或 x er = x )， 则称 el ( 或 er )是 S 中关于 运算的 左 ( 或右 ) 单位元. 若 eS 关于 运算既是左单位元又是右单位元，则称 e 为 S 上关于 运算的单位元. 单位元也叫做幺元. 14 二元运算的特异元素(续) 零元 定义 设 为 S 上的二元运算, 如果存在l ( 或r)S， 使得对任意 xS 都有 l x =l ( 或 x r =r )， 则称l ( 或r )是 S 中关于 运算的 左 ( 或右) 零元. 若S关于 运算既是左零元又是右零元，则称为 S 上关于运算的零元. 15 二元运算的特异元素(续) 可逆元素及其逆元 定义 令 e 为 S 中关于运算 的单位元. 对于 xS，如果 存在yl（或 yr）S 使得 yl x = e（或 x yr = e）， 则称 yl ( 或 yr )是 x 的左逆元 ( 或右逆元 ). 关于 运算，若 yS 既是 x 的左逆元又是 x 的右逆元 ，则称 y 为 x 的逆元. 如果 x 的逆元存在，就称 x 是可逆的. 16 实例分析 集合运算单单位元零元逆元 Z, Q, R 普通加法+0无x 的逆元 x 普通乘法10x 的逆元 x1 (x-1属于给给定集合) Mn(R)矩阵阵加法+无X 逆元X 矩阵阵乘法EX的逆元 X1 （X是可逆矩阵阵） P(B)并B的逆元为为 交BB的逆元为为B 对对称差无X的逆元为为X 和 E 分别表示n 阶全0 矩阵 和 单位实数矩阵 17 惟一性定理 定理14.1 设 为S上的二元运算，el 和 er 分别为 S 中关 于运算的左和右单位元，则 el = er = e 为 S 上关于 运算 的惟一的单位元. 证 el = el er = er 所以 el = er , 将这个单位元记作 e. 假设 e 也是 S 中的单 位元，则有 e = e e = e. 惟一性得证. 类似地可以证明关于零元的惟一性定理. 注意：当|S|2，单位元与零元是不同的； 当|S|=1时，这个元素既是单位元也是零元. 18 惟一性定理(续) 定理14.2 设 为 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 = y 所以 y 是 x 惟一的逆元. 说明：对于可结合的二元运算，可逆元素 x 只有惟一的 逆元，记作 x-1. 19 消去律 定义14.6 设 为集合S上二元运算，如果对于任意元素 x, y, zS, x ，都有 x y = x z y = z, y x = z x y = z 成立，则称 运算满足消去律. 例如，普通加法和乘法满足消去律，矩阵加法满足消去 律，矩阵乘法不满足消去律. 集合的并和交运算也不满 足消去律，例如11,2=21,2，但是12. 20 例题分析 例7 设 运算为 Q 上的二元运算， x, yQ, x y = x+y+2xy, (1) 判断 运算是否满足交换律和结合律，并说明理由. (2) 求出 运算的单位元、零元和所有可逆元素的逆元. 解 (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 21 (2) 设 运算的单位元和零元分别为 e 和 ，则对于任意 x 有 x e = x 成立，即 x+e+2xe = x e = 0 由于 运算可交换，所以 0 是幺元. 给定 x，设 x 的逆元为 y, 则有 x y = 0 成立，即 x+y+2xy = 0 (x = 1/2) 是 x 的逆元, x 1/2. 例题分析(续) 对于任意 x 有 x = 成立，即 x+2x = x+2x =0 = 1/2 1/2为零元. 22 例题分析(续) 下面是三个运算表 (1) 说明那些运算是可交换的、可结合的、幂等的. (2) 求出每个运算的单位元、零元、所有可逆元素的逆元. a