二元运算及其性质

1、1,代数结构,2006/10/8,2,代数结构前言,什么是代数 代数是一门研究运算的科学. 代数中的运算对象是整数,实数, 有理数等 运算可以是:加,减,乘,除 古典代数,数学工作者逐渐认识到, 运算对象不仅可以是数字,事实上还可以其他很多其他元素,如:矩阵,多项式,命题,集合等. 运算还可以是:与,或,非,并,交,补等.,3,并且发现:某些运算遵循的某些规律,如交换律,结合律,分配律等.,近世代数 近世代数是近代数学的一个重要分支,在计算机科学领域有着广泛应用.,x+y=y+x xy=y x 交换律 (x+y)+z=x+(y+z) (x y) z=x (y z) 结合律 问题: 减法和除法是

2、否满足交换律,结合律? x (y+z)=x y+ x z 乘法对加法的分配律 问题:加法对乘法的有分配律吗?,4,在近世代数中,研究的主要对象是代数结构(也叫代数系统),典型的代数系统有:群,环,域等,什么是代数系统呢,简单地说,就是集合上的具有封闭性的运算.,课程将用4学时介绍代数系统的一些基本概念.,5,10.1 二元运算及其性质,什么是二元运算 二元运算有哪些性质 交换律,结合律,分配律,幂等律,吸收律等 二元运算中的一些特异元素 单位元,零元,逆元,6,什么是二元运算,1)首先给定一个集合S,和一个运算 2)参加运算的是S中的任意两个元素 3)满足封闭性:运算的结果必须仍然是S中的元素

3、. 满足以上条件,该运算为该集合上的二元运算. 例1 (1) N 上的加法、乘法是二元运算： 两个自然数相加和相乘仍然是自然数 (2) N上的减和除法是二元运算吗? (2) Z 上的加法、减法、乘法是二元运算. (3) 非零实数集 R* 上的乘法、除法是二元运算.,7,二元运算的实例（续）,(5) 设 Mn(R) 表示所有 n 阶 (n2) 实矩阵的集 合，即 矩阵加法和乘法都是 Mn(R) 上的二元运算. (6) 幂集 P(S) 上的二元运算：, . (7) SS 为 S 上的所有函数的集合：合成运算.,8,一元运算,例2 Z, Q 和 R 上求相反数的运算是一元运算 自然数N上求相反数是一

4、元运算吗? (3) 非零有理数集 Q*，非零实数集 R*上求倒数是一元 运算. (4)N,Z上求倒数是一元运算吗?,1)首先给定一个集合S,和一个运算 2)参加运算的是S中的任意一个元素 3)满足封闭性:运算的结果必须也是S中的元素. 满足以上条件,该运算为该集合上的一元运算.,9,二元与一元运算的表示,通常用算符：, , , , 等符号来表示二元或一元运算 对二元运算 ，如果 x 与 y 运算得到 z，记做 xy = z； 对一元运算 , x 的运算结果记作 x,* 一般可以读做“*运算”，也就是“星运算” 就读做“圈运算”。,10,给出二元或一元运算有两种方法：解析式、 运算表 1 解析式

5、表示 例3 设 R 为实数集合，如下定义 R 上的如下二元运算 ： x, yR, x y = x. 那么 3 4 = 3 0.5 (-3) = 0.5 7 2.5=?,二元与一元运算的表示（续）,11,2 用运算表表示,表头,表头,算符,12,二元运算的运算表一般形式,一元运算的运算表,13,运算表的实例 P183,例10.4 A = P(a, b), , 分别为对称差和绝对补运算 （a,b为全集） 的运算表 的运算表,观察运算的封闭性,14,例10.5 Z5 = 0, 1, 2, 3, 4 , p183 表示模5加法(x+y)mod5 表示模5乘法 (xy)mod5 的运算表 的运算表,观察

6、运算的封闭性,15,课堂练习,P192 第1题 列出运算表: (1) 第4题 判断给定集合上的运算是否封闭? (1) (2) (9),16,二元运算的性质,在实际应用中,只有满足某些特定性质(如交换律,结合律,幂等律,分配律,吸收律,消去律)的运算才有实际意义.,17,交换律,定义 设 为 S 上的二元运算, (1) 如果对于任意的 x, y S 有 x y = y x, 则称运算在 S 上满足交换律. 例如: 1 实数集合上的加法和乘法可交换,减法不可交换 2 幂集P(S)上的, , AB是可交换的, 相对补(A-B)不可交换 AB=B A AB= B A A-BB-A,18,结合律和幂等律

7、,(2) 如果对于任意的 x, y, z S 有 (x y) z = x (y z), 则称运算在 S 上满足结合律. 例如: 普通加法,乘法在N,Z,Q,R上满足结合律 减法不满足 (3) 如果对于任意的 x S 有 x x = x, 则称运算在 S 上满足幂等律.,如: AA=A, AA=A, 即集合的并和交运算满足幂等律 普通数的加和乘运算不满足幂等律.,19,实例分析,Z, Q, R分别为整数、有理数、实数集；Mn(R)为 n 阶实矩阵集合, n2；P(B)为幂集；AA 为 A上A(所有A到A的函数)，|A|2.,20,分配律: 是对两个二元运算而言,定义 设 和 为 S 上两个不同的

8、二元运算, (1) 如果 x, y, zS 有 (x y) z = (x z) (y z) z (x y) = (z x) (z y) 则称 运算对 运算满足分配律. 如: x (y+z)=x y+ x z (y+z) x=yz+zx 则称 乘法对加法满足分配律,例如:实数集上普通乘法对加法是可分配的. n阶实矩阵乘法对加法是可分配的. 幂集P(S)上和是互相可分配的.,21,(2) 如果 和 都可交换, 并且 x, yS 有 x (x y) = x x (x y) = x 则称 和 运算满足吸收律. 例:幂集P(S)上和是满足吸收律 A(AB)=A A (A B)=A,吸收律,22,实例分析

9、,Z, Q, R分别为整数、有理数、实数集；Mn(R) 为 n 阶实矩阵集合, n2；P(B)为幂集；AA为 A上A，|A|2.,23,如何判断二元运算的性质,法一：用运算表进行判断 法二：用解析式验证,24,法一:通过运算表,1交换律：运算表关于主对角线对称 2 幂等律：主对角线元素排列x1,x2xi与表头顺序x1,x2xi一致,即xi xi=xi,其他性质，如结合律,在运算表中没有明显特征，要对所有3个元素的组合验证进行判断, 满足交换、结合律, 满足结合、幂等律, 满足交换、结合律,练习:习题10 (1),25,法：用解析式验证,方法: 任取x,y,z.通过验证相关算律等式是否成立,例6

10、 设 运算为 Q 上的二元运算， x, yQ, xy = x+y+2xy, 运算是否满足交换和结合律? 说明理由.,解 (a) 任取x, yQ, x y = x+y+2xy, y x= y+x+2yx x y = y x 所以， 运算可交换， (b) 结合律: 判断 (x y) z ?= x (y z),26,结合律判断 任取x, y, zQ, (x y) z = (x+y+2xy) z = (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x (y+z+2yz) = x + (y+z+2yz) + 2x(y+z+2

11、yz = x+y+z+2xy+2xz+2yz+4xyz (x y) z= x (y z) 所以， 运算可结合,27,课堂练习:P192 第5题: (1) (2) (9) 课后作业 第1题 (2) 第7题 (1)(2),28,习题解答,P191 习题10 4 判断给定集合上的运算是否封闭 Z上减法封闭, 不符合交换律,结合律,幂等律 Z*上除不封闭, S上加法不封闭 S上乘法封闭, 符合交换律,结合律,幂等律 0*0=0,1*1=1,29,第7题,(2)满足交换律,结合律.幂等律,30,代数系统的几种特异元素,单位元(幺元)(identity elements) 定义 设为S上的二元运算, 如果

12、存在eS，使得对任意 xS 都有 e x = x e= x ， 则称 e是 S 上关于 运算的 单位元. 单位元也叫做 幺元.,例:1 xN, x+0=x 在自然数集合N上加法的单位元是0. 2 x N, x 1 = x 在自然数集合N上乘法的单位元是1,31,零元(zero),设 为 S 上的二元运算, 如果存在S，使得对任意 xS 都有 x = x =， 则称为 S 上关于运算 的 零元.,例 xN, x 0 = 0 自然数集合N上乘法的零元是0 自然数集合N上加法没有零元.,32,逆元 (inverse element),在代数系统中, e 为 单位元,x,y S,对于任意x,存在y使得

13、: x y=y x=e 则称 y 为 x 的逆元. 例: (1) x Z, x +(-x)=0, 且 -x Z 在整数集合z中,加法单位元为0,对任何整数,它的加法逆元都存在,即它的相反数-x. (自然数集合呢),(2) x R, x (1/x)=1, 且 1/x R 在实数集合R中,乘法单位元为1,对任何实数,它的乘法逆元都存在,即它的倒数1/x. (整数集合呢),33,唯一性定理: 1 对于给定的集合和二元运算,如果单位元和零元存在,则必是唯一的. 2 对于可结合的二元运算,元素x的逆元如果存在,该逆元是唯一的. 逆元的特点:逆元和单位元不同,逆元与集合中某个元素相关,不同元素对应不同的逆

14、元. 例: (Q,+, )中,5的加法逆元是-5,乘法逆元是1/5. -2的加法逆元是2,乘法逆元是-1/2.,34,实例分析,35,惟一性定理,定理 设 为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 时，这个元素既是单位元

15、也是零元.,36,惟一性定理（续）,定理 设 为 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

16、只有惟一的逆元，记作 x1.,37,通过运算表求特异元素,单位元：设表头元素的排列顺序为x1,x2.xn,如果元素xi所在的行和列的元素排列顺序也是x1,x2xn,则xi为单位元(幺元). 零元：如果元素xi所在的行和列的元素都是xi,则xi是零元.,表示模5加法(x+y)mod5,表示模5乘法 (xy)mod5,38,逆元：a 所在的行中某列 (比如第 j 列) 元素为 e，且第 j 行 i 列的元素也是 e，那么 a 与第 j 个元素互逆. 也就是说两个单位元关于主对角线对称,那么单位元对应的表头元素互为逆元; 如果单位元在对角线上,那对应的表头元素的逆元就是它自己. 如: x y=y x

17、=e 则称 y 为 x 的逆元.,表示模5加法(x+y)mod5,表示模5乘法 (xy)mod5,39,加法逆元 0 0 1 4 2 3 3 2 4 1,表示模5加法(x+y)mod5,表示模5乘法 (xy)mod5,乘法逆元 0 - 1 1 2 3 3 2 4 4,40,例,例7: 求出运算的单位元、零元、所有可逆元素的逆元.,解,的单位元为 b, 没零元， a1 = c, b1 = b, c1 = a 的单位元和零元都不存在， 没有可逆元素.,41,练习:,求出运算的单位元、零元、所有可逆元素的逆元., 的单位元为 a，零元为c, a的逆元为a. b, c不可逆,42,通过解析式求特异元素

18、,解,例6 设 运算为 Q 上的二元运算， x, yQ, xy = x+y+2xy, 求 运算的单位元、零元和所有可逆元.,设运算的单位元和零元分别为 e 和 ，则对于任意 x 有 xe = x 成立，即 x+e+2xe = x e = 0 由于 运算可交换，所以 0 是幺元.,43,求逆元： 给定 x，设 x 的逆元为 y, 则有 x y = 0 成立，即 x+y+2xy = 0 (x = 1/2) 因此当 x 1/2时， 是 x 的逆元.,求零元：设运算的零元为 ， 对于任意 x 有 x = 成立，即 x+2 x = x + 2 x = 0 = 1/2,44,练习:,设Z+=x|xZx0,*表示求两个数的最小公倍数的运算.则 1)*运算在Z+上是否封闭? 2)4*6=? 3)*运算的特征 4)*运算的单位元,零元? 5)*运算是否