离散数学-耿素云PPT(第5版)9.1.ppt

《离散数学-耿素云PPT(第5版)9.1.ppt》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT(第5版)9.1.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 代数系统简介代数系统简介2第第9章章 代数系统简介代数系统简介n9.1 二元运算及其性质二元运算及其性质n9.2 代数系统代数系统n9.3 几个典型的代数系统几个典型的代数系统39.1 二元运算及其性质二元运算及其性质n二元运算及一元运算的定义二元运算及一元运算的定义n二元运算的性质二元运算的性质交换律、结合律、幂等律、消去律交换律、结合律、幂等律、消去律分配律、吸收律分配律、吸收律n 二元运算的特异元素二元运算的特异元素单位元单位元零元零元可逆元素及其逆元可逆元素及其逆元4二元运算的定义及其实例二元运算的定义及其实例定义定义设设S 为集合为集合,函数函数f：SSS 称为称为S 上的二元上

2、的二元运算运算,简称为简称为二元运算二元运算.也称也称S 对对f 封闭封闭.例例1(1)N上的二元运算：加法、乘法上的二元运算：加法、乘法.(2)Z上的二元运算：加法、减法、乘法上的二元运算：加法、减法、乘法.(3)非零实数集非零实数集R*上的二元运算上的二元运算:乘法、除法乘法、除法.(4)设设S=a1,a2,an,ai aj=ai，为为S上二上二元运算元运算.5二元运算的实例（续）二元运算的实例（续）(5)设设Mn(R)表示所有表示所有n 阶阶(n2)实矩阵的集实矩阵的集合，即合，即矩阵加法和乘法都是矩阵加法和乘法都是Mn(R)上的二元运算上的二元运算.(6)幂集幂集P(S)上的二元运算：

3、上的二元运算：,.(7)SS 为为S 上的所有函数的集合：合成运算上的所有函数的集合：合成运算.6n元运算元运算定义定义设设S 为集合，为集合，n为正整数，函数为正整数，函数称为称为S 上的上的n 元运算，简称为元运算，简称为n元运算元运算.例例2(1)Z,Q 和和R 上的一元运算上的一元运算:求相反数求相反数(2)非零有理数集非零有理数集Q*和实数集和实数集R*的一元运算的一元运算:倒数倒数(3)复数集合复数集合C 上的一元运算上的一元运算:求共轭复数求共轭复数(4)幂集幂集P(S)上上,全集为全集为S:求绝对补运算求绝对补运算(5)A 为为S 上所有双射函数的集合，上所有双射函数的集合，A

4、 SS:求反函数求反函数(6)在在 Mn(R)(n2)上，求转置矩阵上，求转置矩阵7运算的表示运算的表示算符算符：,等符号等符号表示表示n 元运算元运算(a1,a2,an)=b.对二元运算对二元运算 ，如果，如果x 与与y 运算得到运算得到z，记做，记做x y=z；对一元运算对一元运算,x 的运算结果记作的运算结果记作 x 注意：在同一问题中不同的运算使用不同的算符注意：在同一问题中不同的运算使用不同的算符8公式表示公式表示例例3设设R 为实数集合，如下定义为实数集合，如下定义 R 上的二元运上的二元运算算：x,yR,x y=x.那么那么3 4=30.5(-3)=0.5二元与一元运算的表示二元

5、与一元运算的表示9运算表的形式运算表的形式 a1a2an ai a1 a2.ana1 a1a1 a2a1 ana2 a1a2 a2a2 an.an a1an a2an an a1 a2.an a1 a2.an运算表运算表（表示有穷集上的一元和二元运算）（表示有穷集上的一元和二元运算）10运算表的实例运算表的实例例例4A=P(a,b),分别为对称差和绝对补运算分别为对称差和绝对补运算（a,b为全集）为全集）的运算表的运算表 的运算表的运算表 aba,bX Xaba,b aba,baa.bbba,baa,bba aba,ba,bab11运算表的实例（续）运算表的实例（续）例例5Z5=0,1,2,3

6、,4,分别为模分别为模5加法加法与乘法与乘法 的运算表的运算表 的运算表的运算表 01234 01234012340123412340234013401240123 01234000000123402413031420432112二元运算的性质二元运算的性质 定义定义设设 为为S 上的二元运算上的二元运算,(1)如果对于任意的如果对于任意的x,y S 有有x y=y x,则称运算在则称运算在S 上满足上满足交换律交换律.(2)如果对于任意的如果对于任意的x,y,z S 有有(x y)z=x (y z),则称运算在则称运算在S 上满足上满足结合律结合律.(3)如果对于任意的如果对于任意的x S

7、有有x x=x,则称运算在则称运算在S 上满足上满足幂等律幂等律.13实例分析实例分析Z,Q,R分别为整数、有理数、实数集；分别为整数、有理数、实数集；Mn(R)为为n 阶实阶实矩阵集合矩阵集合,n 2；P(B)为幂集；为幂集；AA 为为A上上A，|A|2.集合集合运算运算交交换换律律结结合律合律幂幂等律等律Z,Q,R普通加法普通加法+有有有有无无普通乘法普通乘法 有有有有无无Mn(R)矩矩阵阵加法加法+有有有有无无矩矩阵阵乘法乘法 无无有有无无P(B)并并 有有有有有有交交 有有有有有有相相对补对补 无无无无无无对对称差称差 有有有有无无AA函数符合函数符合 无无有有无无14二元运算的性质（

8、续）二元运算的性质（续）定义定义设设 和和 为为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则称则称 和和 运算满足运算满足吸收律吸收律.15实例分析实例分析集合集合运算运算分配律分配律吸收律吸收律 Z,Q,R普通加法普通加法+与乘法与乘法 对对+可分配可分配无无+对对 不分配不分配 Mn(R)矩矩阵阵加法加法+与乘法与乘法 对对+可分

9、配可分配无无+对对 不分配不分配 P(B)并并 与交与交 对对 可分配可分配有有 对对 可分配可分配交交 与与对对称差称差 对对 可分配可分配无无 对对 不分配不分配Z,Q,R分别为整数、有理数、实数集；分别为整数、有理数、实数集；Mn(R)为为n 阶实阶实矩阵集合矩阵集合,n 2；P(B)为幂集；为幂集；AA为为A上上A，|A|2.16二元运算的特异元素二元运算的特异元素单位元单位元定义定义设设 为为S上的二元运算上的二元运算,如果存在如果存在el（或（或er）S，使得对任意，使得对任意xS 都有都有 el x=x(或或x er=x)，则称则称el(或或er)是是S 中关于中关于 运算的运算

10、的左左(或右或右)单位元单位元.若若eS 关于关于 运算既是左单位元又是右单位运算既是左单位元又是右单位元，则称元，则称e 为为S 上关于上关于 运算的运算的单位元单位元.单位元也叫做单位元也叫做幺元幺元.17二元运算的特异元素（续）二元运算的特异元素（续）零元零元设设 为为S 上的二元运算上的二元运算,如果存在如果存在l（或（或r）S，使得对任意，使得对任意xS 都有都有 l x=l(或或x r=r)，则称则称l(或或r)是是S 中关于中关于 运算的运算的左左(或右或右)零元零元.若若S关于关于 运算既是左零元又是右零元，则运算既是左零元又是右零元，则称称为为S 上关于运算上关于运算 的的零

11、元零元.18二元运算的特异元素（续）二元运算的特异元素（续）可逆元素及其逆元可逆元素及其逆元令令e 为为S 中关于运算中关于运算 的单位元的单位元.对于对于xS，如，如果存在果存在yl（或（或yr）S 使得使得 yl x=e（或（或x yr=e），），则称则称yl(或或yr)是是x 的的左逆元左逆元(或右逆元或右逆元).关于关于 运算，若运算，若yS 既是既是x 的左逆元又是的左逆元又是x 的的右逆元，则称右逆元，则称y 为为x 的的逆元逆元.如果如果x 的逆元存在，就称的逆元存在，就称x 是是可逆的可逆的.19实例分析实例分析集合集合运算运算单位元单位元零元零元逆元逆元Z,Q,R普通加法普通

12、加法+0无无X 的逆元的逆元 x普通乘法普通乘法 10X 的逆元的逆元x 1(x-1属于给定集合属于给定集合)Mn(R)矩矩阵阵加法加法+n阶全阶全0矩阵矩阵无无X逆元逆元 X矩矩阵阵乘法乘法 n阶单位阶单位矩阵矩阵n阶全阶全0矩阵矩阵X的逆元的逆元X 1（X是可逆矩阵）是可逆矩阵）P(B)并并 B的逆元为的逆元为交交 BB 的逆元为的逆元为B对对称差称差 无无X 的逆元为的逆元为X20唯一性定理唯一性定理定理定理设设 为为S上的二元运算，上的二元运算，el 和和er 分别为分别为S 中关于运算的左和右单位元，则中关于运算的左和右单位元，则el=er=e 为为S 上关于上关于 运算的惟一的单位

13、元运算的惟一的单位元.证证el=el er=el er=er所以所以el=er,将这个单位元记作将这个单位元记作e.假设假设e 也是也是S 中的单位元，则有中的单位元，则有e=e e=e.惟一性得证惟一性得证.类似地可以证明关于零元的惟一性定理类似地可以证明关于零元的惟一性定理.注意：当注意：当|S|2，单位元与零元是不同的；，单位元与零元是不同的；当当|S|=1时，这个元素既是单位元也是零元时，这个元素既是单位元也是零元.21惟一性定理（续）惟一性定理（续）定理定理设设 为为S 上可结合的二元运算上可结合的二元运算,e 为该运算为该运算的单位元的单位元,对于对于xS 如果存在左逆元如果存在左

14、逆元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.22消去律消去律定义定义设设 为为V上二元运算，如果上二元运算，如果 x,y,z

15、 V，若若x y=x z，且，且x不是零元，则不是零元，则y=z若若y x=z x,且且x 不是零元，则不是零元，则y=z那么称那么称 运算满足运算满足消去律消去律.实例实例:Z,Q,R关于普通加法和乘法满足消去律关于普通加法和乘法满足消去律.Mn(R)关于矩阵加法满足消去律，但是关于矩阵关于矩阵加法满足消去律，但是关于矩阵乘法不满足消去律乘法不满足消去律.Zn关于模关于模n加法满足消去律，当加法满足消去律，当n为素数时关于为素数时关于模模n乘法满足消去律乘法满足消去律.当当n为合数时关于模为合数时关于模n乘乘法不满足消去律法不满足消去律.23例题分析例题分析解解(1)运算可交换，可结合运算可

16、交换，可结合.任取任取x,y Q,x y=x+y+2xy=y+x+2yx=y x,任取任取x,y,z Q,(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例例6设设 运算为运算为Q上的二元运算，上的二元运算，x,y Q,x y=x+y+2xy,(1)运算是否满足交换和结合律运算是否满足交换和结合律?说明理由说明理由.(2)求求 运算的单位元、零元和所有可逆元运算的单位元、零元和所有可逆元.24给定给定x，设，设x 的逆元为的逆元为

17、y,则有则有x y=0成立，即成立，即 x+y+2xy=0(x=1/2)因此当因此当x 1/2时，时，是是x 的逆元的逆元.例题分析（续）例题分析（续）(2)设设 运算的单位元和零元分别为运算的单位元和零元分别为e 和和，则对于，则对于任意任意x 有有x e=x 成立，即成立，即 x+e+2xe=x e=0由于由于 运算可交换，所以运算可交换，所以0是幺元是幺元.对于任意对于任意x 有有x =成立，即成立，即x+2x =x+2x =0=1/225例题分析（续）例题分析（续）例例7(1)说明那些运算是交换的、可结合的、幂等的说明那些运算是交换的、可结合的、幂等的.(2)求出运算的单位元、零元、所

18、有可逆元素的逆元求出运算的单位元、零元、所有可逆元素的逆元.abc abc abc a b c cab abc bca a b c aaa bbb ccc a b c abc bcc ccc解解(1)满足交换、结合律；满足交换、结合律；满足结合、幂等律；满足结合、幂等律；满足交换、结合律满足交换、结合律.(2)的单位元为的单位元为b,没零元，没零元，a 1=c,b 1=b,c 1=a 的单位元和零元都不存在，没有可逆元素的单位元和零元都不存在，没有可逆元素.的单位元为的单位元为a，零元为，零元为c,a 1=a.b,c不可逆不可逆.26例题分析（续）例题分析（续）例例8设设A=a,b,c,构造构

19、造A 上的二元运算上的二元运算*使得使得a*b=c,c*b=b,且且*运算是幂等的、可交换的，给运算是幂等的、可交换的，给出关于出关于*运算的一个运算表，说明它是否可结合，运算的一个运算表，说明它是否可结合，为什么？为什么？*a b c a b c a c b b c cb 根据幂等律和已知条件根据幂等律和已知条件a*b=c,c*b=b 得到运算表得到运算表根据交换律得到新的运算表根据交换律得到新的运算表方框方框 可以填入可以填入a,b,c中任一中任一选定的符号选定的符号,完成运算表完成运算表不结合，因为不结合，因为(a*b)*b=c*b=b,a*(b*b)=a*b=c 27由运算表判别算律的

20、一般方法由运算表判别算律的一般方法n交换律：运算表关于主对角线对称交换律：运算表关于主对角线对称n幂等律：主对角线元素排列与表头顺序一致幂等律：主对角线元素排列与表头顺序一致n消去律：所在的行与列中没有重复元素消去律：所在的行与列中没有重复元素n单位元单位元:所在的行与列的元素排列都与表头一致所在的行与列的元素排列都与表头一致n零元：元素的行与列都由该元素自身构成零元：元素的行与列都由该元素自身构成nA 的可逆元：的可逆元：a 所在的行中某列所在的行中某列(比如第比如第j 列列)元素元素为为e，且第，且第j 行行 i 列的元素也是列的元素也是e，那么，那么a与第与第j 个个元素互逆元素互逆n结合律：除了单位元、零元之外，要对所有结合律：除了单位元、零元之外，要对所有3个元个元素的组合验证表示结合律的等式是否成立素的组合验证表示结合律的等式是否成立