《清华离散数学（第2版）：（11）》由会员分享，可在线阅读，更多相关《清华离散数学（第2版）：（11）（23页珍藏版）》请在金锄头文库上搜索。
1、1,第14章 代数系统,2,第14章 代数系统,14.1 二元运算及其性质 14.2 代数系统 14.3 几个典型的代数系统,3,14.1 二元运算及其性质,14.1.1 二元运算与一元运算的定义 二元运算定义及其实例 一元运算定义及其实例 运算的表示 14.1.2 二元运算的性质 交换律、结合律、幂等律、分配律、吸收律 特异元素：单位元、零元、可逆元 消去律,4,二元运算的定义及其实例,定义14.1 设 S 为集合,函数 f : SSS 称为S上的二元 运算, 简称为二元运算. 也称 S 对 f 封闭. 例1 (1) N上的二元运算：加法、乘法. (2) Z上的二元运算：加法、减法、乘法.
2、(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的合成运算.,5,一元运算的定义与实例,定义14.2 设S为集合，函数 f : SS 称为S上的一元运算，简称为一元运算. 例2 (1) Z, Q 和 R上求相反数的运算 (2) 非零有理数集Q*，非零实数集 R*上求倒数运算 (3) 复数集合C上求共轭复数的运算
3、(4) 幂集P(S)上, 全集为S，求绝对补运算 (5) A 为S上所有双射函数的集合，ASS，求反函数 (6) 在 Mn(R) (n2)上求转置矩阵,6,二元与一元运算的表示,算符：, , , , 等符号 表示二元或一元运算 对二元运算，如果 x 与 y 运算得到 z，记做 xy=z； 对一元运算, x 的运算结果记作 x 表示二元或一元运算的方法：公式、 运算表 注意：在同一个问题中不同的运算使用不同的算符,7,公式表示 例3 设 R 为实数集合，如下定义 R 上的二元运算 ： x, yR, x y = x. 那么 3 4 = 3， 0.5 (3) = 0.5 运算表（表示有穷集上的一元和
4、二元运算） 二元运算的运算表 一元运算的运算表,实例,8,运算表的实例,例4 A=P(a,b), , 分别为对称差和绝对补运算 （a,b为全集） 的运算表 的运算表,9,运算表的实例(续),例5 Z5= 0, 1, 2, 3, 4 , , 分别为模 5 加法与乘法 的运算表 的运算表,10,二元运算的性质,定义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
5、 = x, 则称运算在 S 上满足幂等律.,11,实例,例6 Z, Q, R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合, n2；P(B)为幂集；AA为A上A，|A|2.,12,二元运算的性质(续),定义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 则称 和 运算满足吸收律.,13,实例分析,例7 Z, Q,
6、 R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合, n2；P(B)为幂集；AA为A上A，|A|2.,14,二元运算的特异元素,单位元 定义14.5 设 为S上的二元运算, 如果存在el（或er）S，使得对任意 xS 都有 el x = x ( 或 x er = x )， 则称 el ( 或 er )是 S 中关于 运算的 左 ( 或右 ) 单位元. 若 eS 关于 运算既是左单位元又是右单位元，则称 e 为 S 上关于 运算的单位元. 单位元也叫做幺元.,15,二元运算的特异元素(续),零元 定义 设 为 S 上的二元运算, 如果存在l ( 或r)S，使得对任意 xS 都有 l x
7、=l ( 或 x r =r )， 则称l ( 或r )是 S 中关于 运算的 左 ( 或右) 零元. 若S关于 运算既是左零元又是右零元，则称为 S 上关于运算的零元.,16,二元运算的特异元素(续),可逆元素及其逆元 定义 令 e 为 S 中关于运算 的单位元. 对于 xS，如果存在yl（或 yr）S 使得 yl x = e（或 x yr = e）， 则称 yl ( 或 yr )是 x 的左逆元 ( 或右逆元 ). 关于 运算，若 yS 既是 x 的左逆元又是 x 的右逆元，则称 y 为 x 的逆元. 如果 x 的逆元存在，就称 x 是可逆的.,17,实例分析, 和 E 分别表示n 阶全0
8、矩阵 和 单位实数矩阵,18,惟一性定理,定理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时，这个元素既是单位元也是零元.,19,惟一性定理(续),定理14.2 设 为 S 上可结合的二元运算, e 为该运算的单位元, 对于 xS 如果
9、存在左逆元 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.,20,消去律,定义14.6 设 为集合S上二元运算，如果对于任意元素 x, y, z
10、S, x ，都有 x y = x z y = z, y x = z x y = z 成立，则称 运算满足消去律. 例如，普通加法和乘法满足消去律，矩阵加法满足消去律，矩阵乘法不满足消去律. 集合的并和交运算也不满足消去律，例如11,2=21,2，但是12.,21,例题分析,例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,
11、 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,22,(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为零元.,23,例题分析(续),下面是三个运算表 (1) 说明那些运算是可交换的、可结合的、幂等的. (2) 求出每个运算的单位元、零元、所有可逆元素的逆元.,解 (1) 满足交换律、结合律； 满足结合律、幂等律； 满足交换律、结合律.,(2) 的单位元为 b, 没有零元， a1=c, b1=b, c1=a 的单位元和零元都不存在，没有可逆元素. 的单位元为 a，零元为c, a1=a. b, c不是可逆元素,
