离散左孝凌第6章代数系统.ppt

《离散左孝凌第6章代数系统.ppt》由会员分享，可在线阅读，更多相关《离散左孝凌第6章代数系统.ppt（26页珍藏版）》请在三一办公上搜索。

1、第6章 代数系统,6.1 代数系统的基本概念,6.2 二元运算的性质,6.3 子代数和积代数,返回总目录,6.1代数系统的基本概念 运算 1.运算的定义 定义6.1.1 设A是非空集合，从笛卡尔积AAA到A的映射f称为集合A上的n元运算。简称为n元运算。在定义中，当n=1时，f称为集合A上的一元运算；当n=2时，f称为集合A上的二元运算。在讨论抽象运算时，“运算”常记为“*”、“”等。设*是二元运算，如果a与b运算得到c，记作a*b=c；若*是一元运算，a的运算结果记作*a或*(a)。,第6章 代数系统,设A=1,a,，其中，a是非零实数。f：AA，定义为：aA，f(a)=。容易看出f是A上的

2、一元运算。又如，f：NNN，定义为：m,nN，f(m,n)=mn，f是自然数集合N上的二元运算，它就是普通加法运算。普通减法不是自然数集合N上的二元运算，因为两个自然数相减可能得到负数，而负数不是自然数。所以普通的减法不是自然数集合N上的二元运算。通过以上讨论可以看出，一个运算是否为集合A上的运算必须满足以下两点：A中任何元素都可以进行这种运算，且运算的结果是惟一的。A中任何元素的运算结果都属于A。A中任何元素的运算结果都属于A通常称为运算在A是封闭的。,【例6.1】设N为自然数集合，*和是NN到N映射，规定为：m,nN，mn=minm,n mn=maxm,n则和是N上的二元运算。【例6.2】

3、设Nk=0,1,k-1。Nk上的二元运算+k定义为：对于Nk中的任意两个元素i和j，有 称二元运算+k为模k加法。,2.运算的表示 表示运算的方法通常有两种：解析公式和运算表。解析公式是指用运算符号和运算对象组成的表达式。如 f(a)=，,运算表是指运算对象和运算结果构成的二维表。设N4=0,1,2,3，N4上的模4加法4可以用运算表表示，它的运算表如表6.1所示。N4上的模4乘法4也可以用运算表表示，它的运算表如表6.2所示。,代数系统 定义6.1.2 一个非空集合A连同若干个定义在该集合上的运算1,2,k所组成的系统称为一个代数系统，记作。一个代数系统需要满足下面两个条件：有一个非空集合A

4、。有一些定义在集合A上的运算。【例】设R-0是全体非零实数集合，*是R-0上二元运算，定义为：a,b R-0，a*b=b。则是代数系统。,6.2 二元运算的性质 运算的基本性质 1.交换律 定义6.2.1 设*是非空集合A上的二元运算，如果对于任意的a,bA，有ab=ba，则称二元运算在A上是可交换的。例如，设R为实数集合，对于任意的a,bR，规定 ab=(ab)2 ab=a2+b2 ab=a+bab则运算、和都是可交换的。2.结合律 定义6.2.2 设*是非空集合A上的二元运算，如果对于任意的a,b,cA，有(a*b)*c=a*(b*c)，则称二元运算*在A上是可结合的。,返回章目录,实数集

5、合上的普通加法和乘法是二元运算，矩阵的加法和乘法也是二元运算，满足结合律；向量的内积、外积是二元运算，但不满足结合律。【例6.5】设*是非空集合A上的二元运算，定义为：a,bA，ab=b。证明运算*是可结合的。证明：对于任意的a,b,cA，有(ab)c=c，而a(bc)=ac=c，故有(ab)c=a(bc)，即运算是可结合的。当二元运算*在A上适合结合律时，在只有该运算符的表达式中，表示运算顺序的括号常被省略。所以将(x*y)*z=x*(y*z)常写成x*y*z。这样，可以令,当运算*满足结合律时，an的也可以递归定义如下：a1=a an+1=ana 由此利用数学归纳法，不难证明下列的公式：a

6、man=am+n(am)n=amn 3.分配律 定义6.2.3 设*和 是非空集合A上的两个二元运算，如果对于任意a,b,cA，有a*(bc)=(a*b)(a*c)(左分配律)(bc)*a=(b*a)(c*a)(右分配律)则称运算*对运算 是可分配的。也称运算*对运算 满足分配律。,【例6.6】设A=0,1，*和都是A上的二元运算，定义为：00=1*1=0，0*1=1*0=1 00=01=10=0，11=1 则容易验证对于运算*是可分配的，但*对于运算是不可分配的。如1*(01)=10=(1*0)(1*1)定理设*和是非空集合A上的两个二元运算，*是可交换的。如果*对于运算满足左分配律或右分配

7、律，则运算*对于运算是可分配的。证明：设*对于运算满足左分配律，且是可交换的，则对于任意a,b,cA，有(bc)a=a(bc)=(ab)(ac)=(ba)(ca)即(bc)a=(ba)(ca)故对于运算是可分配的。同理可证另一半。,4.吸收律 定义6.2.4 设*和是非空集合A上的两个可交换的二元运算，如果对于任意a,bA，有a*(ab)=aa(a*b)=a则称运算和运算满足吸收律。【例6.7】设N为自然数集合，*和是集合N上的二元运算，定义为：aN，bN a*b=max(a,b)，ab=min(a,b)验证运算*和适合吸收律。解：aN，bN 若ab，a*(ab)=a*min(a,b)=a*b

8、=max(a,b)=a 若ab，a*(ab)=a*min(a,b)=a*a=max(a,a)=a 若ab，a*(ab)=a*min(a,b)=a*a=max(a,a)=a 即 a*(ab)=a 同理可证a(a*b)=a 因此运算*和适合吸收律。,5.幂等律 定义6.2.5 设*是非空集合A上的二元运算，如果对于任意的aA，有aa=a，则称运算*是幂等的。如果A的某个元素a满足aa=a，则称a为运算*的幂等元。集合的并、交运算满足幂等律，每一个集合都是幂等元。定理6.2.2 设是非空集合A上的二元运算，a为运算的幂等元，对任意的正整数n，则an=a。特殊元素 1.幺元 定义6.2.6 设是定义在

9、集合A上的二元运算，如果有一个elA，对于任意的aA，有el a=a，则称el为A中关于运算的左单位元或左幺元；如果有一个erA，对于任意的aA，有a er=a，则称er为A中关于运算的右单位元或右幺元；如果在A中有一个元素，它既是左单位元又是右单位元，则称为A中关于运算的单位元或幺元。,定理6.2.3 设是定义在集合A上的二元运算，el为A中关于运算的左幺元，er为A中关于运算的右幺元，则el=er=e，且A中的幺元是惟一的。证明：因为el和er分别是A中关于运算的左幺元和右幺元，所以el=el er=er=e设另一幺元e1A，则e1=e1 e=e 2.零元 定义6.2.7 设是集合A上的二

10、元运算，如果有一个lA，对于任意的aA都有l a=l，则称l为A中关于运算的左零元；如果有一个rA，对于任意的aA，都有a r=r，则称r为A中关于运算的右零元；如果A中有一个元素A，它既是左零元又是右零元，则称为A中关于运算的零元。,定理6.2.4 设是集合A上的二元运算，l为A中关于运算的左零元，r为A中关于运算的右零元，则l=r=，且A中的零元是惟一的。证明：因为l和r分别是A中关于运算的左零元和右零元，所以l=lr=r=设另一零元1A，则1=1=定理6.2.5 设是集合A上的二元运算，集合A中元素的个数大于1。如果A中存在幺元e和零元，则e。证明：用反证法。设e=，那么对于任意的aA，

11、必有 a=ea=a=，于是A中的所有元素都是零元，与A中至少有两个元素矛盾。,3.逆元 定义6.2.8 设是集合A上的二元运算，e为A中关于运算的幺元。如果对于A中的元素a存在着A中的某个元素b，使得ba=e，那么称b为a的左逆元；如果存在A中的某个元素b，使得ab=e，那么称b为a的右逆元；如果存在着A中的某个元素b，它既是a的左逆元又是a的右逆元，那么称b为a的逆元。a的逆元记为a1。如果aA存在逆元a1A，那么称a为可逆元。一般地说，一个元素的左逆元不一定等于该元素的右逆元。一个元素可以有左逆元而没有右逆元，同样可以有右逆元而没有左逆元。甚至一个元素的左逆元或者右逆元还可以不是惟一的。定

12、理6.2.6 设为A中的一个二元运算，A中存在幺元e且每个元素都有左逆元。如果是可结合的运算，则在A中任何元素的左逆元必定是该元素的右逆元，且每个元素的逆元是惟一的。,证明：设a,b,cA，b是a的左逆元，c是b的左逆元。于是(ba)b=eb=b，所以 e=cb=c(ba)b)=(c(ba)b=(cb)a)b=(ea)b=ab因此，b也是a的右逆元。设元素a有两个逆元b和d，那么b=be=b(ad)=(ba)d=ed=d故a的逆元是惟一的。4.消去律 定义6.2.9 设是集合A上的二元运算，为A中关于运算的零元，a,b,cA，a。如果 若ab=ac，便有b=c，则称运算满足左消去律，称a为运算

13、的左可消元。若ba=ca，便有b=c，则称运算满足右消去律，称a为运算的右可消元。,若运算既满足左消去律又满足右消去律，则称运算满足消去律，称a为运算的可消元。注意可消元a不能是零元。定理6.2.7 设是A中可结合的二元运算，如果a的逆存在且a，则a为关于的可消元。证明：设b,cA，且有ab=ac或ba=ca。由于为可结合的二元运算、a的逆存在且a，则a 1(a b)=(a 1 a)b=e b=ba 1(a c)=(a 1 a)c=e c=c而 a 1(a b)=a 1(a c)于是b=c，同理由ba=ca，得b=c，故a为关于的可消元。,【例6.8】实数集R上的下列二元运算是否满足结合律和交

14、换律？ab=a+bab ab=(a+b)解：因为a,b,cR，有(ab)c=(a+b-ab)c=(a+b-ab)+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc又 a(bc)=a(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-ac-bc+abc所以(ab)c=a(bc)因此运算满足结合律。又 ab=a+bab=b+aba=ba 所以运算满足交换律。因为a,b,cR，有(ab)c=(a+b)c=(a+b)+c)=(a+b+2c),a(bc)=a(b+c)=(a+(b+c)=(2a+b+c)在一般情况下(a+b+2c)(2a+b+c)所以运算不满足结合律。而

15、ab=(a+b)=(b+a)=ba所以运算满足交换律。【例6.9】在例6.8中，运算*是否有单位元，零元和幂等元？若有单位元，哪些元素有逆元？解：运算的定义为：ab=a+bab 若e是单位元，则对任意元素aR，有ae=ea=a，由于元素是可交换的，仅考虑ea=a，即ea=e+aea=a，于是eea=0，即e(1a)=0。由于a是任意的，要使上式成立，只有e=0。因此0是运算的单位元。,6.3子代数和积代数 定义 如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。例如：V1=R,-,0,1 V2=P(A

16、),A V1和V2都含有两个二元运算、一个一元运算和两个代数常数，它们是同类型的代数系统。同类型的代数系统仅仅是构成成分相同，不一定具有相同的运算性质。定义6.3.2 设V=是代数系统，BA。如果1,2,k都在B上封闭，B和A含有相同的代数常数，则称代数系统是V的子代数系统，简称子代数。,例如I,0是代数系统，NI，加法在N上封闭，0N，所以N,0是I,0的子代数，当然N,也是I,的子代数。N-0,是I,的子代数，但不是I,0的子代数，因为I,0中的代数常数0N-0。【例6.10】设I是整数集合，是普通加法，I,0是代数系统，设B=x|x=2nnI，证明B,0是I,0的子代数。证明：任取B的两个元素2n1和2n2，n1I，n2I。2n12n2=2(n1n2)B n1n2I所以，加法在B上封闭。又0=20B所以B,0 是I,0的子代数。,定义 设V1=A,和V2=B,是两个代数系统，其中、和都是二元运算。a1,b1,a2,b2AB，定义AB上的二元运算和为：a1,b1a2,b2=a1*a2,b1b2 a1,b1a2,b2=a1a2,b1b2代数系统AB,称为V1到V2的积代数或直积。记为V1V2。,