离散数学-代数系统ppt课件.ppt

《离散数学-代数系统ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-代数系统ppt课件.ppt（71页珍藏版）》请在三一办公上搜索。

1、第5章 代数系统,离 散 数 学,本章说明,本章的主要内容一元和二元运算定义及其实例二元运算的性质代数系统定义及其实例子代数,与后面各章的关系是后面典型代数系统的基础,5.1 二元运算及其性质5.2 代数系统 本章小结 作 业,本章内容,5.1 二元运算及其性质,定义5.1 设S为集合，函数 f：SSS 称为S上的二元运算，简称为二元运算。举例 f:NNN，f()x+y是自然数集合N上的二元运算f:NNN，f()x-y不是自然数集合N上的二元运算称N对减法不封闭。,说明,验证一个运算是否为集合S上的二元运算主要考虑两点：S中任何两个元素都可以进行这种运算，且运算的结果是唯一的。S中任何两个元素

2、的运算结果都属于S，即S对该运算是封闭的。,（1）自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是。（2）整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是。（3）非零实数集R*上的乘法和除法都是R*上的二元运算，加法、减法不是。（4）设Sa1,a2,an，aiaj=ai为S上二元运算。,例5.1,例5.1,（5）设Mn(R)表示所有n阶(n2)实矩阵的集合，即,则矩阵加法和乘法都是Mn(R)上的二元运算。（6）S为任意集合，则、为P(S)上的二元运算。（7）SS为S上的所有函数的集合，则合成运算为SS上的二元运算。,一元运算,定义5.2 设S为集合，函数f：SS称为S上

3、的一元运算，简称为一元运算。例5.3（1）求一个数的相反数是整数集合Z、有理数集合Q和实数集合R上的一元运算。（2）求一个数的倒数是非零有理数集合Q*、非零实数集合R*上的一元运算。（3）求一个复数的共轭复数是复数集合C上的一元运算。,（4）在幂集P(S)上，如果规定全集为S，则求集合的绝对补运算是P(S)上的一元运算。（5）设S为集合，令A为S上所有双射函数的集合，ASS，求一个双射函数的反函数为A上的一元运算。（6）在n(n2)阶实矩阵的集合Mn(R)上，求一个矩阵的转置矩阵是Mn(R)上的一元运算。,一元运算举例,可以用、等符号表示二元或一元运算，称为算符。设f:SSS是S上的二元运算，

4、对任意的x,yS，如果x与y的运算结果为z，即f()z，可以利用算符简记为xy=z。对一元运算，x的运算结果记作x。例题 设R为实数集合，如下定义R上的二元运算 x,yR，x y=x。那么 3 4=3，0.5(3)=0.5。,二元与一元运算的算符,函数的解析公式运算表（表示有穷集上的一元和二元运算）,二元与一元运算的表示,例5.4 设S=1,2，给出P(S)上的运算和的运算表，其中全集为S。,解答,例5.4,例5.5 设S=1,2,3,4，定义S上的二元运算如下x y(xy)mod 5，x,yS 求运算的运算表。,解答,例5.5,定义5.3 设为S上的二元运算，如果对于任意的x,yS都有xy=

5、yx，则称运算在S上满足交换律。定义5.4 设为S上的二元运算，如果对于任意的x,y,zS都有(xy)z=x(yz)，则称运算在S上满足结合律。说明：若+适合结合律，则有(x+y)+(u+v)x+y+u+v。,二元运算的性质,二元运算的性质,定义5.5 设为S上的二元运算，如果对于任意的xS有xx=x，则称运算在S上满足幂等律。如果S中的某些x满足xx=x，则称x为运算的幂等元。举例：普通的加法和乘法不适合幂等律。但0是加法的幂等元，0和1是乘法的幂等元。,例题,Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2。,定义5.

6、6 设和为S上两个二元运算，如果对于任意的x,y,zS，有 x(yz)(xy)(xz)（左分配律）(yz)x(yx)(zx)（右分配律）则称运算对运算满足分配律。说明：若*对运算分配律成立，则*对运算广义分配律也成立。x(y1 y2 yn)(xy1)(x y2)(x yn)(y1 y2 yn)x(y1x)(y2x)(ynx),二元运算的性质,定义5.7 设和为S上两个可交换的二元运算，如果对于任意的x,yS，都有x(xy)x x(xy)x 则称运算和满足吸收律。,二元运算的性质,Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合，n2；P(B)为幂集；AA为从A到A的函数集，|A

7、|2。,例题,定义5.8 设为S上的二元运算，如果存在元素el（或er）S，使得对任意xS都有elx=x(或xer=x)则称el(或er)是S中关于运算的一个左单位元(或右单位元)。若eS关于运算既是左单位元又是右单位元，则称e为S上关于运算的单位元。单位元也叫做幺元。,运算可以没有左单位元和右单位元。运算可以只有左单位元。运算可以只有右单位元。运算可以既有左单位元，又有右单位元。,说明,二元运算中的特异元素单位元,二元运算中的特异元素零元,定义5.9 设为S上的二元运算，如果存在元素l（或r）S，使得对任意xS都有 lx=l(或xr=r)，则称l(或r)是S上关于运算的左零元(或右零元)。若

8、S关于运算既是左零元又是右零元，则称为S上关于运算的零元。,运算可以没有左零元和右零元。运算可以只有左零元。运算可以只有右零元。运算可以既有左零元，又有右零元。,说明,二元运算中的特异元素逆元,定义5.10 设为S上的二元运算，eS为运算的单位元，对于xS，如果存在yl（或yr）S使得ylxe（或xyre）则称yl（或yr）是x的左逆元（或右逆元）。若yS既是x的左逆元又是x的右逆元，则称y为x的逆元。如果x的逆元存在，则称x是可逆的。,运算可以没有左逆元和右逆元。运算可以只有左逆元。运算可以只有右逆元。运算可以既有左逆元，又有右逆元。,说明,特异元素的实例,定理5.1,定理5.1 设为S上的

9、二元运算，el、er分别为运算的左单位元和右单位元，则有 el=er=e 且e 为S上关于运算的唯一的单位元。,el eler(er为右单位元)eler er(el为左单位元)所以el=er，将这个单位元记作e。假设e也是S中的单位元，则有 e=ee=e所以，e 是S中关于运算的唯一的单位元。,证明,定理5.2,定理5.2 设为S上的二元运算，l和r分别为运算的左零元和右零元，则有 l=r=且为S上关于运算的唯一的零元。,l lr(r为左零元)lr r(l为右零元)所以l=r，将这个零元记作。假设 也是S中的零元，则有=所以，是S中关于运算的唯一的零元。,证明,定理5.3,定理5.3 设为S上

10、的二元运算，e 和分别为运算的单位元和零元，如果S至少有两个元素，则e。,用反证法。假设 e=，则xS有x x e x 这与S中至少含有两个元素矛盾。所以，假设不 成立，即e。,证明,定理5.4,定理5.4 设为S上可结合的二元运算，e为该运算的单位元，对于xS，如果存在左逆元yl和右逆元yr，则有yl=yr=y 且y是x的唯一的逆元。,由 ylx=e 和 xyr=e，得,证明,yl=yle,令yl=yr=y，则y是x的逆元。,=yl(xyr),=(ylx)yr,=eyr,=yr,假若yS也是x的逆元，则,y=ye,=y(xy),=(yx)y,=ey,=y,所以y是x唯一的逆元，记作x1。,消

11、去律,定义5.11 设为S上的二元运算，如果对于任意的x,y,zS，满足以下条件：（1）若xy xz且x，则y z（左消去律）（2）若yx zx且x，则yz（右消去律）则称运算满足消去律。例如：整数集合上的加法和乘法都满足消去律。幂集P(S)上的并和交运算一般不满足消去律。,例5.6,例5.6 对于下面给定的集合和该集合上的二元运算，指出该运算的性质，并求出它的单位元、零元和所有可逆元素的逆元。（1）Z+，x,yZ+，xylcm(x,y)，即求x和y的最小公倍数。（2）Q，x,yQ，xy=x+y-xy,解答,（1）运算可交换、可结合、是幂等的。xZ+，x1=x，1x=x，1为单位元。不存在零元

12、。只有1有逆元，是它自己，其他正整数无逆元。,（2）Q，x,yQ，xy=x+y-xy运算满足交换律，因为x,yQ，有 xy=x+y-xy=y+x-yx=yx运算满足结合律，因为x,y,zQ，有(xy)z=(x+y-xy)z=x+y-xy+z-(x+y-xy)z=x+y+z-xy-xz-yz+xyz x(yz)=x(y+z-yz)=x+(y+z-yz)-x(y+z-yz)=x+y+z-xy-xz-yz+xyz运算不满足幂等律，因为2Q，但22=2+2-2202 运算满足消去律，因为x,y,zQ，x1(1为零元)，有 xy=xz x+y-xy=x+z-xz y-z=x(y-z)y=z 由于是可交换

13、的，所以右消去律成立。同理可证明左消去律成立，所以消去律成立。,例5.6,0是运算的单位元，因为 xQ，有 x0=x+0-x0=x=0 x1是运算的零元，因为 xQ，有 x1=x+1-x1=1=1xxQ，欲使 xy=0和 yx=0成立，即 x+y-xy=0 得,所以，,例5.7,例5.7 设A=a,b,c，A上的二元运算、如表所示。(1)说明、运算是否满足交换律、结合律、消去律和幂等律。(2)求出关于、运算的单位元、零元和所有可逆元素的逆元。,运算满足交换律、结合律和消去律，不满足幂等律。单位元是a，没有零元，且a-1=a，b-1=c，c-1=b。运算满足交换律、结合律和幂等律，不满足消去律。

14、单位元是a，零元是b，只有a有逆元，a-1=a。运算满足结合律和幂等律，不满足交换律和消去律。没有单位元，没有零元，没有可逆元。,解答,复习,分析,5.2 代数系统,定义5.12 非空集合S和S上k个一元或二元运算f1,f2,fk组成的系统称为一个代数系统，简称代数，记做。,5.2 代数系统,实例：、都是代数系统，其中+和分别表示普通加法和乘法。是代数系统，其中和分别表示n阶(n2)实矩阵的加法和乘法。是代数系统，其中和为并和交，为绝对补。是代数系统，其中Zn0,1,2,n-1 和分别表示模n的加法和乘法。,集合（规定了参与运算的元素）运算（只讨论有限个二元和一元运算）代数常数在定义代数系统的

15、时候，如果把零元和单位元也作为系统的性质，称这些元素为该代数系统的特异元素或代数常数。有时为了强调某个代数系统是含有代数常数的系统，也可以把这些代数常数列到系统的表达式中。例如：代数系统。,代数系统的成分,列出所有的成分：集合、运算、代数常数(如果存在)例如，列出集合和运算，在规定系统性质时不涉及具有单位元的性质（无代数常数）例如，用集合名称简单标记代数系统例如 在前面已经对代数系统作了说明的前提下，上述两个代数系统可以简记为Z,P(S),代数系统的表示,定义5.13 如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是

16、同类型的代数系统。,同类型的代数系统,例如 V1=V2=V1、V2是同类型的代数系统，因为它们都含有2个二元运算，1个一元运算，2个代数常数。但是它们的运算性质不一样。,同类型的代数系统,在规定了一个代数系统的构成成分，即集合、运算以及代数常数以后，如果在对这些性质所遵从的算律加以限制，那么满足这些条件的代数系统就具有完全相同的性质，从而构成了一类特殊的代数系统。例如：代数系统V，如果*是可结合的，则称V为半群。如、等都是半群。从代数系统的构成成分和遵从的算律出发，将代数系统分类，然后研究每一类代数系统的共同性质，并将研究的结果运用到具体的代数系统中去。(抽象代数的基本方法),代数系统地说明,

17、定义5.14设V是代数系统，BS，如果B对f1,f2,fk 都是封闭的，且B和S含有相同的代数常数，则称是V的子代数系统，简称子代数。简记为B。例如：N是的子代数，N也是的子代数N0是的子代数，但不是的子代数。,子代数和原代数具有相同的成分，运算性质也相同，是同类型的代数系统，在许多方面与原代数非常相似，不过可能小一些。对于任何代数系统，其子代数一定存在。,说明,子代数,最大的子代数：就是V本身。最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数。平凡的子代数：最大和最小的子代数称为V的平凡的子代数。真子代数：若B是S的真子集，则B

18、构成的子代数称为V的真子代数。,子代数的相关概念,例5.8 设V=，令 nZ=nz|zZ，n为自然数，则nZ是V的子代数。,任取nZ中的两个元素nz1和nz2(z1,z2Z)，则有nz1+nz2 n(z1+z2)nZ即nZ对+运算是封闭的。又0=n0 nZ所以，nZ是V的子代数。,证明,当n=1和0时，nZ是V的平凡子代数，其他的都是V的非平 凡的真子代数。,说明,例5.8,试讨论 的运算性质,有单位元,例 在 中,为有理数,零元、逆元吗？,解:对任意,集.对,设单位元为e,设零元为,逆元,时,设a的逆元为x,单位元也是零元,问A是什么集合?,例*为 上的二元运算,它的,解:设aA,且a为A上

19、*的单位元,和零元,对任意xA,有,单位元,零 元,必为单元素集.,即,例 设 上 满足结合律,且对,试证 对任意的自然数,有,证明:对 用归纳法,由,得,当 时,得,时,成立,时,结合,所以对任意的,有,5.3代数系统的同构与同态,两个代数系统(0,1,)和(a,b,*),0 a 1 b,两个代数系统同构的条件1.必须是同型代数系统2.两个集合的元素个数应相等3.运算定义法则相同，即对应元素运算后的结果也对应代数系统(0,1,)和(a,b,*)满足上述条件,即同构,定义：设(X,)和(Y,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个一一对应的函数g：X Y，使得g(x1 x

20、2)=g(x1)*g(x2)x1,x2X则称g 是一个从(X,)到(Y,*)的同构函数或者称(X,)和(Y,*)同构 可记为：(X,)(Y,*),(X,)(Y,*),X1X2x1 x2,g(x1)g(x2)g(x1)*g(x2),看例题书,定理：代数系统(X,)(Y,*)1.若(X,)满足结合律,则(Y,*)也满足结合律2.若(X,)满足交换律,则(Y,*)也满足交换律3.若(X,)有单位元1x,则(Y,*)也有单位元1y，且1y=g(1x)4.若(X,)对xX都存在逆元素x-1，则(Y,*)也对yY都存在逆元素y-1,并且若g(x)=y，则g(x-1)=y-15.若(X,)有零元0 x,则(

21、Y,*)也有零元0y，且0y=g(0 x),定理：代数系统(X,，*)(Y,，)若(X,，*)满足分配律，则(Y,，)也满足分配律定理：代数系统之间的同构关系是等价关系一个代数系统和自身的同构称为自同构,定义：设(X,)和(Y,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个一一对应的函数g：X Y，使得g(x1 x2)=g(x1)*g(x2)x1,x2X则称g 是一个从(X,)到(Y,*)的同构函数或者称(X,)和(Y,*)同构 可记为：(X,)(Y,*),单 射,映射 函数,满(单、双)射,满射,定义：设(X,)和(Y,*)是两个相同类型的代数系统，其运算都是二元运算，如果存

22、在一个函数g：X Y，使得g(x1 x2)=g(x1)*g(x2)x1,x2X则称g 是一个从(X,)到(Y,*)的同态映射或者称(X,)和(Y,*)同态如函数为满函数，则称(X,)和(Y,*)满同态如函数为单射函数，则称(X,)和(Y,*)单同态一个代数系统和自身的同态称为自同态,U=(I,+)V=(S,)是代数系统f:UV偶数0奇数1f是U到V的同态，不是满也不是单,U=(I,+)V=(S,)是代数系统f:UV偶数0奇数1f是U到V的满同态，不是单同态,例题：U=(N,+)，V=(I,+)f:x2x是U到V的单同态，不是满同态,例题：U=(I,+)，V=(2I,+)f:I2I定义为：x 2

23、x是U到V的同构,例题:,则（T，*）是代数系统对U=（I，+）和V=（T，*）讨论U和V的关系,本章主要内容,构成代数系统的基本成分非空集合 集合上若干个封闭的二元和一元运算 代数常数 二元运算性质和特异元素同类型的与同种的代数系统子代数的定义与实例,本章学习要求,判断给定集合和运算能否构成代数系统。判断给定二元运算的性质和特异元素。了解同类型和同种代数系统的概念。了解子代数的基本概念。,作业,习题：,运算的性质与特异元素,二元运算f：SSS一元运算f：SS交换律x,yS，xy yx结合律x,y,z S，(xy)z x(yz)幂等律xS，x x x消去律 x,yS，xy xz且x y z y

24、 xzx且x y z,运算的性质与特异元素,分配律x,y,z S，x(yz)(xy)(xz)，(yz)x(yx)(zx)吸收律x,yS，x(xy)x，x(xy)x单位元exS，x e e x x零元xS，x x 幂等元x x x可逆元x y y x e,通过运算表判别运算性质的方法,交换律的表沿主对角线对称。幂等律的表主对角线与每一行和每一列元素相同。如果在运算表中的某行或某列(除了零元所在的行或列之外)有两个相同的元素，那么运算不满足消去律。有零元的表，当且仅当该元素所对应的行和列与该元素相同。,通过运算表判别运算性质的方法,有单位元的表，当且仅当该元素所对应的行和列依次与运算表的行和列相同。a与b互逆，当且仅当以这两个元素为行和列的交点处为单位元。如果元素x在主对角线中排列的位置与表头中的位置一致，那么该元素是幂等元。,