离散代数运算精选文档.ppt

《离散代数运算精选文档.ppt》由会员分享，可在线阅读，更多相关《离散代数运算精选文档.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散代数运算本讲稿第一页，共十二页.-吴扬扬制-27.1 7.1 代数运算与代数系统代数运算与代数系统 1.1.代数运算定义代数运算定义(1)(1)定义：设定义：设A A为非空集合，为非空集合，n n I I+,f:A,f:An nAA称为称为A A上的上的n n元运算，元运算，n n称为运算的阶。称为运算的阶。例例1 1：R R上的加法上的加法+、乘法、乘法 运算是运算是R R上的二元运算。上的二元运算。例例2 2：幂集：幂集(U)(U)上上,集合的补是集合的补是(U)(U)上的一元运算，交、并是二元运算。上的一元运算，交、并是二元运算。例例3 3：字符串的连接运算是字符串集合上的二元运算。

2、：字符串的连接运算是字符串集合上的二元运算。字母集合，字母集合，*由由中的字母构成的字符串集合，中的字母构成的字符串集合，oo字符串的连接运算字符串的连接运算,o:(,o:(*)2 2*例例4 4：设：设A=A=深色，浅色深色，浅色 *深色深色 浅色浅色深色深色浅色浅色深色深色深色深色深色深色浅色浅色*：A A2 2A A*是是A A上的二元运算。上的二元运算。封闭性封闭性性质单位元零元逆元可约判别本讲稿第二页，共十二页.-吴扬扬制-3n封闭性封闭性n设设o o是是A A上上的的n n元运算，元运算，S S A A且且S S，如果，如果 a a1 1,a,an n S,S,均有均有o(ao(a

3、1 1,a,an n)S,S,则称则称S S关于运算关于运算o o是封闭的。是封闭的。n定理定理7.1.1:7.1.1:设设o o是是A A上上的的n n元运算，元运算，C C是是(A)(A)的非空子集，的非空子集，若若 S S C,SC,S关于运算关于运算o o是封闭的，则是封闭的，则C C关于运算关于运算o o也是封闭的。也是封闭的。证明：设证明：设a a1 1,a,an n CC，则则 S S C,C,有有a a1 1,a,an n S,S,S S关于运算关于运算o o是封闭的是封闭的,o(a o(a1 1,a,an n)S,S,o(a o(a1 1,a,an n)C,C,故故C C关于

4、运算关于运算o o也是封闭的。也是封闭的。7.1 7.1 代数运算与代数系统代数运算与代数系统 2.2.代数运算的性质代数运算的性质(1)(1)本讲稿第三页，共十二页.-吴扬扬制-4设设*,o,o是集合是集合A A上的二元运算上的二元运算n交换律：交换律：a,ba,b A,A,有有a*b=b*aa*b=b*an结合律：结合律：a,b,ca,b,c A,A,有有(a*b)*c=a*(b*c)(a*b)*c=a*(b*c)n常用常用a an n 表示表示a*a*a,a*a*a,并称为并称为a a的的n n次幂，次幂，n n为为a a的指数。的指数。n定理定理7.1.3 7.1.3 若若*是集合是集

5、合A A上的可结合的二元运算，则上的可结合的二元运算，则 a a A A，m,nm,n I,I,有有a am m*a*an n=a=am+nm+n;(a;(am m)n n=a=amnmnn分配律：分配律：*对对o o既是左可分配，又是右可分配；既是左可分配，又是右可分配；n*对对o o左可分配左可分配:a,b,ca,b,c A,A,有有a*(boc)=(a*b)o(a*c)a*(boc)=(a*b)o(a*c)n*对对o o右可分配：右可分配：a,b,ca,b,c A,A,有有(aob)*c=(a*c)o(b*c).(aob)*c=(a*c)o(b*c).分析分析例例1-41-47.1 7.

6、1 代数运算与代数系统代数运算与代数系统 2.2.代数运算的性质代数运算的性质(2)(2)本讲稿第四页，共十二页.-吴扬扬制-5n单位元（幺元）单位元（幺元）n定义：设定义：设*是是A A上上的二元运算，的二元运算，0+a=a a+0=a 0+a=a+0=a0+a=a a+0=a 0+a=a+0=a 若若 e el l A,A,使得使得 a a A,A,有有e el l*a=a,*a=a,则称则称e el l为关于为关于*的左的左单位元单位元.若若 e er r A,A,使得使得 a a A,A,有有a*ea*er r=a,=a,则称则称e er r为关于为关于*的右的右单位元单位元.若若 e

7、 e A,A,使得使得 a a A,A,有有e*a=a*e=a,e*a=a*e=a,则称则称e e为关于为关于*的的单位元单位元.例例1 1中：中：7.1 7.1 代数运算与代数系统代数运算与代数系统 3.3.与二元运算相关的特殊元与二元运算相关的特殊元(1)(1)R R关于关于+:+:左左单位元、单位元、右右单位元、单位元均为单位元、单位元均为0 0。R R关于关于:左左单位元、单位元、右右单位元、单位元均为单位元、单位元均为1 1。例例2 2中：中：(U)(U)关于关于:左左单位元、单位元、右右单位元、单位元均为单位元、单位元均为。(U)(U)关于关于:左左单位元、单位元、右右单位元、单位

8、元均为单位元、单位元均为U U。例例3 3中：中：*关于关于o:o:左左单位元、单位元、右右单位元、单位元均为空串单位元、单位元均为空串 。例例4 4中：中：A A关于关于*:左左单位元、单位元、右右单位元、单位元均为单位元、单位元均为“浅色浅色”。本讲稿第五页，共十二页.-吴扬扬制-6例例5 5：N N上定义上定义*：a,ba,b N,a*b=b N,a*b=b N N关于关于*的的左左单位元单位元 右右单位元单位元 单位元单位元7.1 7.1 代数运算与代数系统代数运算与代数系统 3.3.与二元运算相关的特殊元与二元运算相关的特殊元(2)(2)：每个元素都是左单位元；：每个元素都是左单位元

9、；：无；：无；：无：无n定理定理7.1.4 7.1.4 设设*是是A A上上的二元运算，的二元运算，e el l和和e er r分别是关于分别是关于*的左右单位元，的左右单位元，则则 e el l=e=er r，且它是关于，且它是关于*的唯一单位元。的唯一单位元。证明：证明：e el l*e*er r=e=er r e el l=令令 e=ee=er r=e=el l,则则e e是关于是关于*的单位元，的单位元，设设e e也是关于也是关于*的单位元，则的单位元，则 e e=e*e=e*e=e,=e,所以，所以，e e是关于是关于*的唯一单位元的唯一单位元零元可约本讲稿第六页，共十二页R R关于

10、关于+:+:左零左零元、元、右零右零元、元、零零元均无。元均无。R R关于关于:左零左零元、元、右零右零元、元、零零元均为元均为0 0。7.1 7.1 代数运算与代数系统代数运算与代数系统 3.3.与二元运算相关的特殊元与二元运算相关的特殊元(3)(3)n零元：零元：n定义：设定义：设*是是A A上上的二元运算，的二元运算，若若 z zl l A,A,使得使得 a a A,A,有有z zl l*a=z*a=zl l,则称则称z zl l为关于为关于*的左零的左零元元.若若 z zr r A,A,使得使得 a a A,A,有有a*za*zr r=z=zr r,则称则称z zr r为关于为关于*的

11、右零的右零元元.若若 z z A,A,使得使得 a a A,A,有有z*a=a*z=z,z*a=a*z=z,则称则称z z为关于为关于*的零的零元元.例例1 1中中:例例2 2中中:(U)(U)关于关于:左零左零元、元、右零右零元、元、零零元均为元均为U U。(U)(U)关于关于:左零左零元、元、右零右零元、元、零零元均为元均为。例例3 3中中:*关于关于o:o:无无左零左零元、元、右零右零元和元和零零元。元。例例4 4中：中：A A关于关于*:左零左零元、元、右零右零元、元、零零元均为元均为“深色深色”例例5 5中：中：N N关于关于*:每个元素都是右每个元素都是右零零元、无左元、无左零零元

12、和元和零零元。元。n定理定理7.1.5 7.1.5 若关于若关于*的左右零的左右零元都存在，则他们相等，是唯一零元。元都存在，则他们相等，是唯一零元。本讲稿第七页，共十二页8n逆元：逆元：n定义：设定义：设*是是A A上上的二元运算，的二元运算，e e是关于是关于*的单位元，的单位元，a a A A 若若 a al l A,A,使得使得a al l*a=e,*a=e,则称则称a al l为为a a关于关于*的左逆的左逆元元.若若 a ar r A,A,使得使得a*aa*ar r=e,=e,则称则称a ar r为为a a关于关于*的右逆的右逆元元.若若 a a A,A,使得使得a a*a=a*a

13、*a=a*a=e,=e,则称则称a a为为a a关于关于*的逆的逆元元.例例1 1中：中：7.1 7.1 代数运算与代数系统代数运算与代数系统 3.3.与二元运算相关的特殊元与二元运算相关的特殊元(4)(4)关于关于+:+:a a R R的左逆的左逆元、元、右逆右逆元和元和逆逆元均为元均为-a-a。关于关于:a a R R a a 0,a0,a的左逆的左逆元、元、右逆右逆元和元和逆逆元均为元均为1/a1/a。例例2 2中：关于中：关于:(A)(A)中，中，的左逆的左逆元、元、右逆右逆元和元和逆逆元均为元均为 。关于关于:(A)(A)中，中，U U左逆左逆元、元、右逆右逆元和元和逆逆元均为元均为

14、U U。例例3 3中：关于中：关于o o:*中，空串中，空串 的左逆的左逆元、元、右逆右逆元和元和逆逆元均为元均为 。例例4 4中：关于中：关于*:A:A中，浅色的左逆中，浅色的左逆元、元、右逆右逆元和元和逆逆元均为浅色元均为浅色 。本讲稿第八页，共十二页9n定理定理7.1.6 7.1.6 设设*是是A A上上的可结合的二元运算，的可结合的二元运算，e e是关于是关于*的单位元，的单位元，a al l,a,ar r分别分别为为a a关于关于*的左右逆的左右逆元，则元，则a al l=a=ar r且它是且它是a a关于关于*的唯一逆的唯一逆元。元。7.1 7.1 代数运算与代数系统代数运算与代数

15、系统 3.3.与二元运算相关的特殊元与二元运算相关的特殊元(5)(5)n幂等元：幂等元：n定义：设定义：设*是是A A上上二元运算，二元运算，a a A A，若，若a*a=a,a*a=a,则称则称a a是关于是关于*的幂等元。的幂等元。n可约元：可约元：n定义：设定义：设*是是A A上上二元运算，二元运算，a a A A，x,yx,y A,a*x=a*yA,a*x=a*yx=y,x=y,则称则称a a关于关于*左可约；左可约；x,yx,y A,x*a=y*aA,x*a=y*ax=y,x=y,则称则称a a关于关于*右可约；右可约；若若a a关于关于*既左可约又右可约，则称既左可约又右可约，则称

16、a a关于关于*可约；可约；若若 a a A A 都是可约的，则称都是可约的，则称*满足消去律。满足消去律。分析分析例例1-41-4 本讲稿第九页，共十二页.-吴扬扬制-10例例1 1中：关于中：关于+:+:a a R R均为左可约，右可约，也是可约的；均为左可约，右可约，也是可约的；关于关于:a a R R a a 0 0均为左可约，右可约，也是可约的；均为左可约，右可约，也是可约的；+满足消去律。满足消去律。例例2 2中：关于中：关于：是可约的；关于是可约的；关于：U U可约。可约。例例3 3中：关于中：关于o:o:*均可约。均可约。例例4 4中：关于中：关于*:浅色可约。浅色可约。例例5

17、 5中：关于中：关于*:i i N N均左可约。均左可约。n定理定理7.1.7 7.1.7 设设*为为A A上的可结合的二元运算，上的可结合的二元运算，a a A A，若，若a a关于关于*可逆，可逆，则则a a关于关于*可约。可约。*此定理的逆不成立。此定理的逆不成立。例例6 6：N N中的乘法运算中的乘法运算.7.1 7.1 代数运算与代数系统代数运算与代数系统 3.3.与二元运算相关的特殊元与二元运算相关的特殊元(6)(6)本讲稿第十页，共十二页.-吴扬扬制-11定理定理7.1.7:7.1.7:设设*为为A A上的可结合的二元运算，上的可结合的二元运算，a a A A，若若a a关于关于

18、*可逆，则可逆，则a a关于关于*可约。可约。证明：证明：x,y x,y A A，如果，如果 a*x=a*y,a*x=a*y,a a关于关于*可逆可逆,=e*x=e*x 由由a*x=a*ya*x=a*y，又有，又有a a-1-1*(a*x)=a*(a*x)=a-1-1*(a*y)*(a*y)=(a=(a-1-1*a)*y*a)*y=e*y=e*y=y=y =x=x x=y x=y 故故a a关于关于*左可约。左可约。有有a a-1-1,使使a a-1-1*a=a*a*a=a*a-1-1=e;=e;a a-1-1*(a*x)=(a*(a*x)=(a-1-1*a)*x*a)*x 同理可证同理可证a

19、 a关于关于*右可约。右可约。分析分析例例4 4的运算表，如何的运算表，如何识别运算的性质及特殊元？识别运算的性质及特殊元？封闭型封闭型 iff iff 运算运算表中的每个元素均属于表中的每个元素均属于A;A;可交换性可交换性 iff iff 运算运算表关于主对角线对称；表关于主对角线对称；单位元单位元 iff iff 该元素对应行与表头行相同，对应列与表头列相同；该元素对应行与表头行相同，对应列与表头列相同；零元零元 iff iff 零元素对应的行和列全部元素都等于零元；零元素对应的行和列全部元素都等于零元；幂等元幂等元 iff iff 主对角线上元素与该行（列）的表头元素相同。主对角线上元素与该行（列）的表头元素相同。本讲稿第十一页，共十二页.-吴扬扬制-12作业：作业：P P146 146 1 1(3,5),(3,5),2,5,72,5,7(1)(1)本讲稿第十二页，共十二页