离散数学课件

1、第7章代数系统,代数系统的概念；运算的性质；运算的特殊元素；同态与同构,运算的性质；运算的特殊元素；代数系统的同态与同构。,同态与同构,7.1运算,整数：存储方式，值的范围，可用运算,7.1.1引言,C语言中的不同的数据类型？,整数的取反运算-：F-：ZZ，且：F-（x）=-x;,整数的加运算+：F+：ZZZ，且：F+(）=x+y;,结论：运算是函数的另一种表示形式：A到A的函数是一元运算;AA到A的函数是二元运算；AAA到A的函数是三元运算。Ak=AAAAA到A的函数是k元运算。,7.1运算,7.1.2运算,1)集合A上的k元运算集合Ak到集合A上的函数。,显然，k=1和2时就是所谓的一元运

2、算和二元运算。,2)说明,作为函数的另一种形式，运算通常写成新的表示形式，即表达式形式，如：-()=x-yx-y,以后的讨论以二元运算为主，涉及的运算多为广义的运算，比如出现运算符*并不代表普通的乘法运算（除非特别申请）。,普通的除法，是定义在何集合上的？,7.1运算,7.1.2运算,3)几个术语,运算表表示函数运算关系的表,7.1运算,7.1.2运算,3)几个术语,运算封闭性,y,x,z,y,x,z=x*y,作为运算（函数）z自然应该在A中，但当x,y取自A的子集B时，Z是否也在B中？,7.1运算,7.1.2运算,3)几个术语,运算封闭性,y,x,z=x*y,示例1：R中的普通加法(+)，对

3、其子集N,示例2：R中的普通减法(-)，对其子集Z,示例3：R中的普通除法(/)，对其子集Z,示例4：R中的普通取反(单目-)，对其子集N,7.1运算,7.1.2运算,3)几个术语,-对于A上的2元运算*，若对于A的子集B，任意的x,yB,有x*yB，则称运算*在B中的封闭的。,如，R中的普通减法运算，在整数集合Z中是？,R的普通减法运算，在N中？,R*的普通除法运算，在Z中？,R的普通加法运算，在x|x的某次幂可被16整除中？,R的普通加法运算，在x|x与5互质中？,R的普通加法运算，在x|x是30的因子中？,R的普通加法运算，在x|x是30的倍数中？,运算封闭性,7.1运算,7.1.2运算

4、的性质,交换律设为S上的二元运算，若有x,yS，都有xoy=yox，则称运算是可交换的（运算满足交换律）。,如，R上普通的加，乘法满足交换律，而减，除法不满足交换律。,满足交换律的运算运算表的特点：？,满足交换律的运算（特殊的二元关系）是否就是对称关系？,z=xoy=o(),zo,其它可交换与不可交换的例子：,7.1运算,7.1.2运算的性质,交换律设为S上的二元运算，若有x,yS，都有xoy=yox，则称运算是可交换的（运算满足交换律）。,满足交换律的运算运算表一定是对称的！,7.1运算,7.1.2运算的性质,结合律设为S上的二元运算，若有x，y，zS，都有xo(yoz)=(xoy)oz则称

5、运算o是可结合的(满足结合律)。,如，R上普通的加，乘法满足结合律，而减，除法不满足结合律。,其它可结合与不可结合的例子,7.1运算,7.1.2运算的性质,分配律设和*为S上的二元运算，若有x,y,zS，都有:x*(yz)=(x*y)(x*z)(左分配)(yz)*x=(y*x)(z*x)(右分配)则称运算*对是可分配的(*对满足分配律)。,其它可分配与不可分配的例子.,如，R上普通乘对加,减法满足分配律，但加,减法对乘除法不满足分配律。,7.1运算,7.1.2运算的性质,吸收律设和*为S上的两个可交换的二元运算，若x，yS，都有:x*(xy)=x且x(x*y)=x，则称运算*和满足吸收律。,如

6、，与，都满足吸收律，而R上的普通加，减，乘，除都不满足吸收律。,7.1运算,7.1.2运算的性质,例1N为自然数集,x,yN，x*y=maxx，y,xy=minx，y，试证运算*，满足吸收律,证明：x，yN，x*（xy）=maxx，minx，y=xx（x*y）=minx，maxx，y=x运算*和满足吸收律,吸收律设和*为S上的两个可交换的二元运算，若x，yS，都有:x*(xy)=x且xo(x*y)=x，则称运算*和满足吸收律。,7.1运算,7.1.2运算的性质,等幂的设o为S上的二元运算，若xS，有xox=x，则称运算o是等幂的（称为满足等幂律）。,如，与，都是等幂的，而R上的普通加，减，乘，

7、除都不是等幂的。,结论：在代数系统中，若运算*,o满足吸收律，则必满足等幂律。,a,b,cS，若有：,a*(aob)=aao(a*b)=a,则必有：a*a=aaoa=a,这是因为：a*a=a*(ao(a*b)=a*(ao()=a,同理可得：aoa=a,7.1运算,7.1.2运算的性质,7.1运算,7.1.3运算的特殊元素,幂等元设o为S上的二元运算，若xS，有xox=x，则称x为运算o的幂等元。,R上的普通加，乘法不是等幂的，但是，加法运算中，0是幂等元，乘法运算中，0和1是幂等元,如，与，都是等幂的运算，所以，集合中的任意元素都是幂等元。,7.1运算,7.1.3运算的特殊元素,么元（单位元）

8、设o为S上的二元运算，若存在元素el(er)，xS，有elox=x(xoer=x)，则称el(er)为左（右）么元。,如，R上的普通减法中的0，普通除法中的1，普通乘法中的1,强调忘我,7.1运算,7.1.3运算的特殊元素,么元（单位元）设o为S上的二元运算，若xS，存在元素el(er)，有elox=x(xoer=x)，则称el(er)为左（右）么元。,这是因为根据左右么元的特点必有：eloer=el=er=e,若运算o既有左么元el，又有右么元er，则其左右么元必相等且惟一，此时称为运算o的么元e（单位元）。,而如果我们假设还存在另外一个么元E，则必有：eoE=e=E,么元的例子：逻辑运算，

9、集合，实数.,7.1运算,7.1.3运算的特殊元素,零元设o为S上的二元运算，若存在元素，xS，有zlox=zl(xozr=zr)，则称zl(zr)为左（右）零元。,如，R上的普通除法中的0，普通乘法中的0，集合交，并运算中的空集与全集,强调自我,7.1运算,7.1.3运算的特殊元素，逆元，消去律,零元设o为S上的二元运算，若存在元素，xS，有zlox=zl(xozr=zr)，则称zl(zr)为左（右）零元。,这是因为根据左右么元的特点必有：zlozr=zl=zr=z,若运算o既有左零元zl，又有右零元zr，则其左右零元必相等且惟一，此时称为运算o的零元z。,而如果我们假设还存在另外一个零元Z

10、，则必有：zoZ=z=Z,零元的例子：逻辑运算，集合，实数.,7.1运算,7.1.3运算的特殊元素,逆元设o为S上的有么元的二元运算，若对于元素aS，存在元素al-1，有al-1oa=e，则称元素al-1是的a左逆元（右逆元ar-1？）,结论：若运算o是有么元的可结合的二元运算，且元素a既有左逆元al-1，又有右逆元ar-1，则其左右逆元必相等且惟一，此时称它为元素a的逆元，记为a-1。,如，矩阵乘法运算中的逆矩阵，R上普通加法中，元素x的逆？普通乘法中元素x的逆？,显然，任意二元运算的么元都是可逆的，且逆元就是它自己，而零元一般是不可逆的。,7.1运算,7.1.3运算的特殊元素,在讨论了上述

11、概念之后，我们就可以讨论运算的另一个运算性质：消去律,设o为S上的二元运算，若对于任意元素x,y,zS，满足x非零元，且xoy=xozy=zx非零元，且yox=zoxy=z,则称运算o满足消去律。,集合的并运算：零元，可消去？,集合的笛卡尔积运算：零元，可消去？,矩阵乘法运算：零元，可消去？,R上普通的加法运算：零元，可消去？,课堂练习：P171910111214课外作业：P1721315,7.2代数系统,非空集合S和定义在S上的若干个运算o1,o2,on组成的整体称为一个代数系统，简称为代数，记为：V=,7.2.1代数系统,+为普通的加法+，*,-为普通的加乘法和取反，+为矩阵的乘加法,7.

12、2代数系统,7.2.1代数系统的代数常数,代数系统中运算的特殊元素，即运算的么元和零元统称为代数常数。,例2设A=0,1,2,3,4，定义A上的运算5，5分别为模5的加，乘法，讨论的运算性质和代数常数。,运算满足：交换律，结合律,有么元：0,逆元：？,1与4，2与3，0与0,7.2代数系统,7.2.1代数系统的代数常数,运算满足：交换律，结合律,零元：0,逆元：？,2与3，4与4，1与1,有么元：1,0没有逆元,例2设A=0,1,2,3,4，定义A上的运算5，5分别为模5的加，乘法，讨论的运算性质和代数常数。,7.2代数系统,设V=为代数系统，H为S的子集，若V1=也构成代数系统，则称V1是V

13、的子代数系统。简称子系统。,7.2.2子代数系统,以V=为例和为其平凡子代数,代数系统均存在子代数，从集合的角度看，最大的是它自己，最小的可能是由代数常数构成的集合（平凡子代数）。,和是两个非平凡子代数。,7.2代数系统,7.2.2子代数系统,结论1：代数具有父代数系统相同的运算性质。,结论2：子代数与父代数系统有相同的代数常数。,结论3：设V=为代数系统，H为S的子集，构成子代数当且仅当，运算o1,o2,.on在H中是封闭的。,对于V=+为整数上普通的加法,V1=？,V2=？,则V1是V的子代数，而V2不是V的子代数。,N奇对运算+不满足封闭性。,？-为整数上普通的减法,7.3同态与同构,考

14、察：,7.3.1引例,1)它们是两个完全无关的代数系统,2)它们具有非常相似的运算性质（交换律，结合律，吸收律，分配律，德摩根律）。,难道它们之间一点关系都没有？,7.3同态与同构,1)同类型代数系统两个代数系统，若拥有相同的运算且对应的运算元数也相同。,7.3.2同态与同构,与是相同类型的代数系统。,与不是同类型的代数系统。,7.3同态与同构,2)设V1=，V2=均为代数系统，其中的o1，o2为二元运算，1，2为一元运算，如果存在映射f：S1S2，使得x,y,zS1有：,7.3.2同态与同构,y,x,xo1y,f(x),f(y),f(x)o2f(y),f(xo1y)=f(x)o2f(y)f(

15、1(x)=2(f(x)则函数f为V1到V2的同态映射。,z,1(z),f(z),2(f(z),7.3同态与同构,3)设V1与V2是两个同类型的代数系统，如果存在两个集合之间映射，对每对运算都为同态映射，则称这两个代数系统是同态的代数系统，简称同态。,7.3.2同态与同构,若映射为单射，则称为单同态。,若映射为满射，则称为满同态。,若映射为双射，则称为同构。,7.3同态与同构,例3设V1=，V2=，这里的+，*是R上的普通加法和乘法，定义f：RR为：f(x)=5x，证明V1与V2为单同态。,7.3.2同态与同构,显然有：f(x+y)=5x+y,而：f(x)=5xf(y)=5y,所以有：f(x+y

16、)=f(x)*f(y)=5x*5y=5x+y,所以f为同态映射,且xy时，有：5x5y,所以V1与V2为单同态映射。,证明：,7.3同态与同构,例4设V1=，V2=，这里的+，*是R上的普通加法和乘，证明，V1与V2同构。,7.3.2同态与同构,证明：可取f(x)=ex,据前例显然有：f为单同态,下证f为满同态：,设yR+，取x=y，显然有：ex=ey=y,即任意的yR+，均存在源与其对应。f为满同态。,综上所述，V1与V2同构。,7.3同态与同构,例5对于非空集合S，证明代数系统与是满同态。,7.3.2同态与同构,事实上，正是因为上述两个代数系统是满同态的，所以它们才有许多相同的运算性质。,

17、证明思想：构造两个代数系统间的满同态映射？,由于S非空，我们任取元素aS，我们定义P(S)到0,1上的映射如下：,f(A)=集合A中包含元素a（逻辑值0或1）,即：f(A)=,1当aA,0当aA,7.3同态与同构,例5对于非空集合S，证明代数系统与是满同态。,7.3.2同态与同构,容易证明，上述映射是满同态的：,对于一元运算，显然有：f(A)=f(A),对于二元，显然有：f(AB)=f(A)f(B),对于二元，显然有：f(AB)=f(A)f(B),f对每个运算都为同态映射，且为满同态。,7.3同态与同构,例5对于非空集合S，证明代数系统与是满同态。,7.3.2同态与同构,我们注意到：,且有：f

18、()=0f(S)=1么元映射到么元，零元映射到零元,7.3同态与同构,7.3.2同态的性质,o1(或*1)是可交换的o2(或*2)是可交换的；,设V1=，V2=均为代数系统，且V1与V2存在满同态映射f，则：,o1(或*1)是可结合的o2(或*2)是可结合的,o1对*1是可吸收的o2对*2是可吸收的；,o1对*1是可分配的o2对*2是可分配的；,e是o1(或*1)的么元f(e)是o2(或*2)的么元；,z是o1(或*1)的零元f(z)是o2(或*2)的零元；,x-1是x关于o1运算的逆元f(x-1)是f(x)关于o2运算的逆元。,o1(或*1)是幂等的o2(或*2)是幂等的；,7.3同态与同构

19、,7.3.2同态的性质,o1(或*1)是可交换的o2(或*2)是可交换的；,作为示例，我们证明：,证明：u,vS2，需要证明u,v对o2是可交换的:,由于S1满足交换律，即有：xo1y=yo1x,当然有：f(xo1y)=f(yo1x),根据同态映射性质有：f(x)o2f(y)=f(y)o2f(x),即：uo2v=vo2u,由于映射f是满同态，故u,vS2，存在元素x,yS1，使得：f(x)=u,f(y)=v,7.3同态与同构,7.3.2同态的性质,再来证明：,o1对*1是可吸收的o2对*2是可吸收的；,证明：u,vS2，需要证明：uo2(u*2v)=u,由于o1对*1是可吸收的，即有：xo1(x*1y)=x,当然有：f(xo1(x*1y)=f(x),根据同态映射性质有：f(x)o2(f(x)*2f(y)=f(x),即：uo2(u*2v)=u,由于映射f是满同态，故u,vS2，存在元素x,yS1，使得：f(x)=u,f(y)=v,7.3同态与同构,7.3.2同态的性质,最后，我们证明：,z是o1的零元f(z)是o2的零元；,证明：uS2，需要证明f(z)满足:f(z)o2u=uo2f(z)=f(z),由于z是o1运算的