西安交大离散课件第4章.ppt

《西安交大离散课件第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章代数系统(algebrasystem)§1.代数系统的基本概念§2.代数系统的同态和同构§3.半群与单子§4.群§5.环§6.域§7.同余关系1§1.代数系统的基本概念代数系统代数系统的基本性质子代数系统2§1.代数系统的基本概念定义1.代数系统　代数结构(algebrastructure)一个代数系统(代数结构，简称代数)A是如下的一个有序元组：A=﹤X,O1,O2,,Om,R1,R2,,Rn,c1,c2,,cl)〉其中:(1)X是一个任意集合,称为母集或承载子(carrier)；(2)O1,O2,,Om是X上的m个运算(m

2、1)；(3)R1,R2,,Rn是X上的n个(序)关系(n0)；(4)c1,c2,,clX是X中的l个特殊元素(l0),称为常项(constants)。注：当X是有限集合时，称A为有限代数系统；当X是无限集合时，称A为无限代数系统；在一个代数系统中运算的集合不能是空的，必须至少有一个X上的运算。代数系统中各个运算的元(阶)数可能是不一样的，即每个运算都有自己的运算元数。3例1.(1)﹤I,+),﹤I,),﹤I,+,)，﹤I,+,,,0,1)都是代数系统。这里：I是整数集合：+和是整数的加法和乘法。小于等于关系是I上的二元关

3、系(半序)，0,1I是I上的两个特殊元素。例2.﹤,o)是代数系统。这里：X={a,b}，设={ff:XX}，则={f1,f2,f3,f4}。其中：f1(a)=af2(a)=af3(a)=bf4(a)=bf1(b)=bf2(b)=af3(b)=bf4(b)=ao运算是函数的复合运算o:其运算可列表如下：表1of1f2f3f4f1f2f3f4f1f2f3f4f2f2f2f2f3f3f3f3f4f3f2f14例3.﹤X,*)是代数系统。这里：X={a,b,c,d}，定义运算*:X2X如表2所示。例5.时钟代数﹤X,)是代数系统。

4、这里：X={a1,a2,a3,,an}，定义运算:XX。例4.﹤1)﹤2X,,)是代数系统。这里X是任意非空的集合，2X是X的幂集，和是集合的交和并。(2)集合代数﹤2X,,,)是代数系统。这里是集合的余。*abcdabcdabcdabcddcbadcba表2a1a2a3anan-1图1an-2an-35定义2.结合律　交换律(associativelaw,commutativelaw)设﹤X,)是任一代数系统，是X上的二元运算。则称(1)运算满足结合律(xX)(yX)(zX)((xy)z＝x(yz)

5、)；(2)运算满足交换律(xX)(yX)(xy＝yx)。注：结合律改变的是运算的先后次序；交换律改变的是运算对象的位置顺序。前者是对运算符而言；后者是对运算对象而言。例6.代数系统﹤I,+,)中，二元运算+和的性质。例7.代数系统﹤2X,,)中，二元运算和的性质。例8.代数系统﹤I,-)中，减法运算-的性质。6定义3.幺元　零元(identityelement,zeroelement)设﹤X,)是代数系统，是X上的二元运算，x0X。则称(1)x0是关于运算的幺元(xX)(x0x＝xx0＝x)；(2)x0是

6、关于运算的零元(xX)(x0x＝xx0＝x0)。注：通常将幺元记为e；含有幺元e的代数系统﹤X,),通常记作﹤X,,e)；即(xX)(ex＝xe＝x)；在同时具有幺元和零元的代数系统中，通常将幺元记为1，将零元记为0；即(xX)(1x＝x1＝x)；(xX)(0x＝x0＝0)。例9.代数系统﹤I,+,)中，关于+的幺元、的幺元？例10.代数系统﹤2X,,)中，关于的幺元、的幺元？例11.代数系统﹤I,+,)中，关于+的零元、的零元？例12.代数系统﹤2X,,,)中，关于的零元、的零元？

7、7定理1.幺元、零元的唯一性设﹤X,)是代数系统，是X上的二元运算。则(1)若关于运算的幺元存在，则必是唯一的；(2)若关于运算的零元存在，则必是唯一的。[证].（采用逻辑法）只证幺元的唯一性e1是运算的幺元e2是运算的幺元(xX)(xe1=x)(xX)(e2x=x),(e2e1=e2)(e2e1=e1)(因e1,e2X都是X的普通一元；根据普遍性特殊化：xA(x)A(y)及合成律：(pq)(rs)prqs)(e1=e2e1)(e2e1=e2)(交换律：pqqp，以及=的对称性)

8、e1=e2(=的传递性)所以，幺元是唯一的。8定义4.逆元　可逆性(inverseelement,inve