离散代数运算精品课件

1、离散代数运算第1页，共12页，2022年，5月20日，11点4分，星期五. -吴扬扬制-27.1 代数运算与代数系统 1. 代数运算定义(1) 定义：设A为非空集合，nI+,f:AnA称为A上的n元运算， n称为运算的阶。例1：R上的加法+、乘法运算是R上的二元运算。例2：幂集(U)上, 集合的补是(U)上的一元运算，交、并是二元运算。例3：字符串的连接运算是字符串集合上的二元运算。 字母集合， *由中的字母构成的字符串集合， o字符串的连接运算, o: (*)2* 例4：设A= 深色，浅色 *深色 浅色深色浅色深色深色深色浅色*：A2A *是A上的二元运算。封闭性性质单位元零元逆元可约判别第

2、2页，共12页，2022年，5月20日，11点4分，星期五. -吴扬扬制-3封闭性设o是A上的n元运算，SA且S，如果a1,anS, 均有o(a1,an)S,则称S关于运算o是封闭的。定理7.1.1: 设o是A上的n元运算，C是(A)的非空子集， 若SC,S关于运算o是封闭的，则C关于运算o也是封闭的。证明：设a1,anC， 则SC, 有a1,anS, S关于运算o是封闭的, o(a1, , an)S, o(a1, , an)C, 故C关于运算o也是封闭的。7.1 代数运算与代数系统 2. 代数运算的性质(1)第3页，共12页，2022年，5月20日，11点4分，星期五. -吴扬扬制-4设 *

3、, o是集合A上的二元运算交换律：a,bA, 有a*b=b*a结合律：a,b,cA, 有(a*b)*c=a*(b*c)常用an 表示a*a*a, 并称为a的n次幂，n为a的指数。定理7.1.3 若*是集合A上的可结合的二元运算，则 aA，m, nI, 有am*an=am+n; (am)n=amn分配律：*对o既是左可分配，又是右可分配；*对o左可分配: a,b,cA,有a*(boc)=(a*b)o(a*c)*对o右可分配：a,b,cA,有(aob)*c=(a*c)o(b*c).分析例1-47.1 代数运算与代数系统 2. 代数运算的性质(2)第4页，共12页，2022年，5月20日，11点4分

4、，星期五. -吴扬扬制-5单位元（幺元）定义：设*是A上的二元运算，0+a=a a+0=a 0+a=a+0=a 若elA, 使得aA, 有el*a=a,则称el为关于*的左单位元. 若erA, 使得aA, 有a*er=a,则称er为关于*的右单位元. 若eA, 使得aA, 有e*a=a*e=a, 则称e为关于*的单位元.例1中：7.1 代数运算与代数系统 3.与二元运算相关的特殊元(1)R关于+: 左单位元、右单位元、单位元均为0。R关于: 左单位元、右单位元、单位元均为1。 例2中：(U)关于: 左单位元、右单位元、单位元均为。 (U)关于: 左单位元、右单位元、单位元均为U。例3中：*关于

5、o: 左单位元、右单位元、单位元均为空串 。例4中：A关于*: 左单位元、右单位元、单位元均为“浅色”。第5页，共12页，2022年，5月20日，11点4分，星期五. -吴扬扬制-6例5：N上定义*：a, bN, a*b=b N关于*的左单位元 右单位元 单位元7.1 代数运算与代数系统 3.与二元运算相关的特殊元(2)：每个元素都是左单位元；：无；：无定理7.1.4 设*是A上的二元运算，el和er分别是关于*的左右单位元， 则 el=er，且它是关于*的唯一单位元。证明： el * er= er el =令 e=er=el, 则e是关于*的单位元，设e也是关于*的单位元，则 e=e*e=e

6、, 所以，e是关于*的唯一单位元零元可约第6页，共12页，2022年，5月20日，11点4分，星期五R关于+: 左零元、右零元、零元均无。R关于: 左零元、右零元、零元均为0。7.1 代数运算与代数系统 3.与二元运算相关的特殊元(3)零元：定义：设*是A上的二元运算， 若zlA,使得aA, 有zl*a=zl, 则称zl为关于*的左零元. 若zrA,使得aA, 有a*zr=zr, 则称zr为关于*的右零元. 若zA, 使得aA, 有z*a=a*z=z, 则称z为关于*的零元.例1中: 例2中: (U)关于: 左零元、右零元、零元均为U。 (U)关于: 左零元、右零元、零元均为。例3中:*关于o

7、: 无左零元、右零元和零元。例4中：A关于*: 左零元、右零元、零元均为 “深色”例5中：N关于*: 每个元素都是右零元、无左零元和零元。定理7.1.5 若关于*的左右零元都存在，则他们相等，是唯一零元。第7页，共12页，2022年，5月20日，11点4分，星期五8逆元：定义：设*是A上的二元运算，e是关于*的单位元，aA 若alA, 使得al*a=e, 则称al为a关于*的左逆元. 若arA, 使得a*ar=e, 则称ar为a关于*的右逆元. 若aA, 使得a*a=a*a=e, 则称a为a关于*的逆元.例1中：7.1 代数运算与代数系统 3.与二元运算相关的特殊元(4)关于+: aR的左逆元

8、、右逆元和逆元均为-a。关于: aRa0, a的左逆元、右逆元和逆元均为1/a。例2中：关于: (A)中，的左逆元、右逆元和逆元均为 。 关于: (A)中，U左逆元、右逆元和逆元均为U。例3中：关于o: *中，空串的左逆元、右逆元和逆元均为 。例4中：关于*: A中，浅色的左逆元、右逆元和逆元均为浅色 。第8页，共12页，2022年，5月20日，11点4分，星期五9定理7.1.6 设*是A上的可结合的二元运算，e是关于*的单位元， al,ar分别为a关于*的左右逆元，则al=ar且它是a关于*的唯一逆元。7.1 代数运算与代数系统 3.与二元运算相关的特殊元(5)幂等元：定义：设*是A上二元运

9、算，aA，若a*a=a,则称a是关于*的幂等元。可约元：定义：设*是A上二元运算，aA， x,yA,a*x=a*yx=y,则称a关于*左可约； x,yA,x*a=y*ax=y,则称a关于*右可约； 若a关于*既左可约又右可约，则称a关于*可约； 若aA 都是可约的，则称*满足消去律。分析例1-4 第9页，共12页，2022年，5月20日，11点4分，星期五. -吴扬扬制-10例1中：关于+: aR均为左可约，右可约，也是可约的； 关于: aRa0均为左可约，右可约，也是可约的； +满足消去律。例2中：关于：是可约的；关于：U可约。例3中：关于o: * 均可约。例4中：关于*: 浅色可约。例5中

10、：关于*: iN均左可约。定理7.1.7 设*为A上的可结合的二元运算，aA，若a关于*可逆， 则a关于*可约。* 此定理的逆不成立。例6：N中的乘法运算.7.1 代数运算与代数系统 3.与二元运算相关的特殊元(6)第10页，共12页，2022年，5月20日，11点4分，星期五. -吴扬扬制-11定理7.1.7:设*为A上的可结合的二元运算，aA， 若a关于*可逆，则a关于*可约。证明：x,y A，如果 a*x=a*y, a关于*可逆, =e*x 由a*x=a*y，又有a-1*(a*x)=a-1*(a*y) =(a-1*a)*y=e*y=y =x x=y 故a关于*左可约。 有a-1,使a-1*a=a*a-1=e; a-1*(a*x)=(a-1*a)*x 同理可证a关于*右可约。分析例4的运算表，如何识别运算的性质及特殊元？封闭型 iff 运算表中的每个元素均属于A;可交换性 iff 运算表关于主对角线对称；单位元 iff 该元素对应行与表头