《大学课件 离散数学(第二版)(蔡英) 第5章 代数系统的基本概念》由会员分享，可在线阅读，更多相关《大学课件 离散数学(第二版)(蔡英) 第5章 代数系统的基本概念（87页珍藏版）》请在金锄头文库上搜索。
1、大学课件(第二版)()第5章 代数系统的基本概念,5.1 二元运算及性质 5.2 代数系统 5.3 代数系统的同态与同构 5.4 例题选解 习题五,第三篇 幅代数结构,集合中的代数运算实质上是集合中的一类函数。定义5.1.1 设A是集合，函数f: AnA称为集合A上的n元代数运算(operators)， 整数n称为运算的阶(order)。当n=1时，f: AA称为集合A中的一元运算。当n=2时，f: AAA称为集合A中的二元运算。,5.1 二元运算及其性质,一般地，二元运算用算符 。，* ，等等表示，并将其写于两个元素之间，如ZZZ的加法： F(2，3)=+(2，3)=2+3=5注意到Ran
2、fA，即运算结果是A中的元素，这称为运算的封闭性。另外，运算是函数，要具备函数所具有的对每一个自变元有唯一的像的特性。,【例5.1.1】下面均是一元运算的例子。(1) 在Z集合上(或Q，或R)，f: ZZ，xZ，f(x)=-x。(2) 在A=0，1集合上，f: AA，pA，f(p)=p，表示否定。(3) 在R+集合上，f: R+R+，xR+，f(x)= (但在R上，倒数不是一元运算，因为0无像)。,【例5.1.2】下面均是二元运算的例子。(1) 在Z集合上(或Q，或R)，f: ZZZ，x, yZ2，f(x，y)=x+y(或f(x，y)=x-y或f(x，y)=xy)，如f(2，3)=5。注意在N
3、集合上，“减法”因其不封闭性，而不是N上的二元运算。,(2) A为集合，P(A)为其幂集。f: P(A)P(A)P(A)。 f可以是、 、 -、 。(3) A=0，1。f: AAA。f可以是、 、 、 。(4) AA=f|f: AA。“。(复合)”是AA上的二元运算。当A是有穷集合时，运算可以用运算表给出。如A=0，1，2，3，4，5，二元运算“。”的定义见表5.1.1。,事实上，对于表5.1.1，通过观察我们可看出其运算为(x，y )=xy(mod 3)其中，“”是普通乘法。而对于表5.1.2，此时的“*”运算应是在集合0，1上的(逻辑合取运算符)。下面介绍二元运算的性质。,定义5.1.2设
4、*，均为集合S上的二元运算。(1) 若xyz(x，y，zSx*(y*z)=(x*y)*z)，则称“*”运算满足结合律。(2) 若xy(x，ySx*y=y*x)，则称“*”运算满足交换律。(3) 若xyz(x，y，zSx*(yz)=(x*y)(x*z)，则称“*”运算对运算满足左分配律； 若xyz(x，y，zS(yz)*x=(y*x)(z*x)，则称“*”运算对运算满足右分配律。若二者均成立，则称“*”运算对“”运算满足分配律。,(4) 设*，均可交换，若x，yA，有x*(xy)=xx(x*y)=x则称“*”运算和“”运算满足吸收律。(5) 若x(xA，x*x=x)，则称“*”运算满足幂等律。,
5、【例5.1.3】加法、 乘法运算是自然数集上的二元运算，减法和除法便不是。但是减法是有理数集、 实数集上的二元运算，除法却仍不是。加法、 乘法满足结合律、 交换律，乘法对加法、 减法满足分配律，减法不满足这些定律。乘法“”对加法“+”运算满足分配律(对“-”也满足)。但加法“+”对乘法“”运算不满足分配律。,【例5.1.4】设A是集合，在A的幂集P(A)上的二元运算并、 交满足交换律、 结合律、 吸收律、 幂等律且彼此满足分配律。【例5.1.5】设A=a，b，A上的运算*、 分别如表5.1.3和表5.1.4所示。,解从*运算表可知，*是可交换的。因为 (a*a)*b=a*b=ba*(a*b)=
6、a*b=b (a*b)*b=b*b=a a*(b*b)=a*a=a所以*是可结合的。 从运算表可知，是可交换的。因为 (aa)b=ab=aa(ab)=aa=a (ab)b=ab=a a(bb)=ab=a,所以是可结合的。 (1) b(a*b)=bb=b (ba)*(bb)=a*b=b (2) a(a*b)=ab=a (aa)*(ab)=a*a=a b(a*a)=ba=a (ba)*(ba)=a*a=a b(b*b)=ba=a (bb)*(bb)=b*b=a a(a*a)=aa=a (aa)*(aa)=a*a=a a(b*b)=aa=a (ab)*(ab)=a*a=a所以对*是可分配的。(由于运
7、算满足交换律成立，因此右分配也成立。),(3) b*(ab)=b*a=b (b*a)(b*b)=ba=a故*对是不可分配的。又由a*(ab)=a*a=a 及上面(1)、 (2)、 (3)式可知和*满足吸收律。由运算表可知，满足幂等律，而*不满足幂等律。下面我们来定义与集合A中的二元运算有关的集合A中的特异元素。,定义5.1.3设*是集合S中的一种二元运算，如果存在erS(elS)且对任意元素xS 均有x*er=x(el*x=x)，则称元素er(el)为S中关于运算*的右幺元(左幺元)或右单位元(左单位元)。定理5.1.1设*是S中的二元运算且er与el分别是对于*的右幺元和左幺元，则er=el
8、=e， 使对任意元素xS有x*e=e*x=x， 称元素e为关于运算*的幺元(identity elements)且唯一。,证明因为er和el分别是*的右幺元和左幺元，故有 el*er=el，el*er=er，所以er=el。 令其为e，有x*e=e*x=x设另有一幺元为右幺元e，那么e=e*e=e故e对*是唯一的幺元。证毕显然，对于可交换的二元运算来说，左幺元即为右幺元，反之亦然。因此对于可交换的二元运算，左(右)幺元即幺元。另外，我们必须强调是对哪一个运算而言的幺元。,【例5.1.6】在实数集R中，对加法“+”运算，0是幺元； 在实数集R中，对乘法“”运算，1是幺元； 对于全集E的子集的并“
9、”运算，是幺元； 对于全集E的子集的交“”运算，E是幺元;在命题集合中，对于析取“”运算，矛盾式是幺元； 在命题集合中，对于合取“”运算，重言式是幺元； 在AA=f|f:AA中，对于复合“”运算，IA是幺元。,定义5.1.4设*是集合S中的一种二元运算，如果存在rS(lS)且对任意元素xS均有x*r=r(l*x=l)，则称元素r(l)是S中关于运算*的右零元(左零元)。定理5.1.2设*是S中的二元运算且r 与l分别是对于*的右零元和左零元，则r=l=， 使对任意元素xS有x*=*x=， 称元素是S中关于运算*的零元(zero)且唯一。,证明因为r 和l分别是*的右零元和左零元，故有 l*r=
10、l，l*r=r，所以r=l。 令其为，有x*=*x=设另有一零元为右零元，那么=*=故对S中的*运算是唯一的零元。证毕同样，需强调零元是针对于哪个运算的。,【例5.1.7】在实数集R中，对加法“+”运算，没有零元； 在实数集R中，对乘法“”运算，0是零元； 对于全集E的子集的并“”运算，E是零元； 对于全集E的子集的交“”运算，是零元;在命题集合中，对于析取“”运算，重言式是零元； 在命题集合中，对于合取“”运算，矛盾式是零元。【例5.1.8】设Sa，b，c， S上*运算由运算表(如表5.1.5所示)确定，那么b是右零元， a是幺元。,表 5.1.5,我们注意到，关于同一运算可能同时有幺元和零
11、元，甚至可能有这样的元素，它关于同一运算既是左(右)幺元，又是右(左)零元，例如表5.1.5第一行(不计表头)改为三个a时，那么*运算有左零元a和右幺元a。,我们强调以下几点： (1) 左、 右幺元，幺元，左、 右零元，零元都是常元。 (2) 左、 右幺元，幺元，左、 右零元，零元都是依赖于运算的。例如，在代数结构 N，+，中，0关于数加 + 是幺元，关于数乘是零元； 1关于是幺元，关于+则既非幺元又非零元。又如在P(A)中，是关于的幺元，是关于的零元； A是关于的零元，又是关于的幺元。,(3) 今后，在不致造成混淆时，特殊元素是关于什么运算的不再一一指出，但当有两个或两个以上的运算时仍将对此
12、作出申明。这时，常常出现这样的情况，一个运算与数加的性质接近，另一个运算与数乘的性质接近，为了简明、 直观，我们把前一种运算叫做加法运算，关于它的幺元、 零元称为加法幺元、 加法零元； 常把后一种运算叫做乘法运算，关于它的幺元、 零元称为乘法幺元、 乘法零元。例如，在P(A)，中可称为P(A)的加法幺元、 乘法零元， 称A为P(A)的乘法幺元、 加法零元。,定义5.1.5设*是集合S中的一种二元运算，且S中对于*有e为幺元，x，y为S中元素。若x*ye，那么称x为y的左逆元，y为x的右逆元，若x对于*运算既有左逆元又有右逆元，则称x是左、 右可逆的。若x左右均可逆，称x可逆。显然对于二元运算*
13、，若*是可交换的，则任何左(右)可逆的元素均可逆。,定理5.1.3设*是集合S中的一个可结合的二元运算，且S中对于*有e为幺元，若xS是可逆的，则其左、 右逆元相等，记作x-1，称为元素x对运算*的逆元(inverse elements)且是唯一的。(x的逆元通常记为x-1; 但当运算被称为“加法运算”(记为+)时， x的逆元可记为-x。),证明设xr 和xl分别是x对*运算的右逆元和左逆元，故有xl*x=x*xr=e由于*可结合，于是xl=xl*e=xl*(x*xr)=(xl*x)*xr=e*xr=xr故xl=xr。假设 ， 均是x对*的逆元，则=*e=*(x*)=(*x)*=e*=由，故唯
14、一性成立。由逆元定义知，若x-1存在，则x-1*x=x*x-1=e。证毕,定理5.1.4设*是集合S中的一个可结合的二元运算，且e为S中对于*的幺元，x有逆元x-1，则(x-1)-1=x。证明(x-1)-1=(x-1)-1*e=(x-1)-1*(x-1*x)=(x-1)-1*x-1)*x=e*x=x。证毕 由以上讨论可得结论： (1) e-1=e。(2) 并非每个元素均可逆。,【例5.1.9】(1) 在自然数集合N上，对于数乘“”运算，只有数 1有逆元 1，对于数加“+”运算，只有数0有逆元0。总之，任何代数结构其幺元恒有逆元，逆元为其自身。 (2) 在整数集合I上(+，的定义同上)，I上每个
15、元素均有加法逆元，但除1以外的数都没有乘法逆元。对任意xI，x的逆元是-x。 (3) 在有理数集合Q上(+，的定义同上)，Q上每个元素x，都有加法逆元-x，除0以外的每个元素x都有乘法逆元x-1=1/x。,(4) 在P(A)中，对于运算，其幺元为，每个元素B(B)均无逆元； 对于运算，其幺元为A，每个元素B(BA)均无逆元。 (5) 在集合AA(其中 AA f|f： AA)中，为函数的合成运算，恒等函数IA为幺元，从而A中所有双射函数都有逆元，所有单射函数都有左逆元， 所有满射函数都有右逆元。定理5.1.5设*是S上的二元运算，e为幺元，为零元，并且|S|2，那么无左(右)逆元。证明首先证 e
16、，否则=e，则S中另有元素a，a不是幺元和零元，从而*ae*aa与a不是零元矛盾，故e得证。,再用反证法证无左(右)逆元，即可设有左(右)逆元x，那么=x*=e(=*x=e)与e矛盾，故无左(右)逆元。得证。 证毕注意逆元是对某个元素而言的，它并不是常元，它不仅依赖于运算，而且更依赖于是哪个元素的逆元。,【例5.1.10】有理数集合Q上的加法“+”运算与乘法“”运算，10的加法逆元是 -10， 乘法逆元是1/10; 而-10的加法逆元是10，乘法逆元是-1/10。当一个集合中每一元素都有逆元时，可以认为该集合上定义了一个一元求逆运算。与逆元概念密切相关的是可约性概念。定义5.1.6设*是集合S中的一个二元运算， aS，a，如果a满足: 对任意x，yS 均有 a*x=a*yx=y(1) x*a=y*ax=y(2),则称元素a对*是可约(可消去)的(cancelable)，当a满足(1)式时，也称a是左可约(左可消去)的，当a满足(2)式时，也称a是右可约(右可消去)的。 特别地，若对任意x，y，zS，
