北大离散数学chap5

代数系统简介这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。我们将介绍代数系统的最基本概念和最基本理论，以及几类常用的代数系统，它们是：半群，幺半群，群，环，域，格和布尔代数。本课程在第五，六章中介绍代数系统的内容。第五章代数系统的一般性质第一节二元运算及性质内容：二元运算，运算律，特殊元素。重点：(1)一元和二元运算的概念，(2)二元运算律(结合律，交换律，分配律)，(3)二元运算的特殊元素(幺元，零元，逆元)。一般：吸收律，消去律，幂等律。一、二元运算。1、定义：设上的二元运算(即s:fSSSS,xySxyS运算封闭)为集合，函数称为，，元运算，n:nfSSSS个掌握1n，2n，即一元，二元运算。一、二元运算。2、记号：用等符号表示二元运算，,,,称为算符。例如：,fxyzxyz记为(二元运算)()fab()ab记为(一元运算)但减法，除法不是。但除法不是。例1、(1)上的加法，乘法都是二元运算，N(2)上的加法，乘法，减法都是二元运算，Z上求相反数的运算是一元运算。Z(3)非零实数集上的乘法和除法都是二元运算。*R但加法，减法不是，而求倒数是一元运算。(4)表示所有阶实矩阵的集合()nMRn(2)n则矩阵的加法和乘法都是二元运算。，都是二元运算，(5)集合的幂集上的S()PS,,,而绝对补集(为全集)是一元运算。S(6)所有命题公式的集合上的,,,都是二元运算，而否定为一元运算。(7)表示集合上的所有函数的集合，函数的合成运算是上的二元运算。SSSSS3、一元，二元运算表。当为有穷集时，都可以用运算表给出。上的一元和二元运算SS例2、(1)设1,2S，给出上的运算绝对和对称差的运算表。~()PS补集解：(),1,2,1,2PS，“”为一元运算，~“”为二元运算，其运算表如下：例2、(2)设，定义二元运算如下：0,1,2,3,4SS上的两个()mod5xyxy(,)xyS()mod5xyxy(,)xyS求运算和的运算表。解：()mod5xy()mod5xy分别是，,xy的和与积除以5的余数，运算表如下：二、有关运算律。设是上的二元运算，,S,,xyzS1、若，则称在(或称满足交换律)xyyxS上可交换。2、若，则称在(或称满足结合律)()()xyzxyz上可结合。S二、有关运算律。设是上的二元运算，,S,,xyzS3、若()()()xyzxyxz()()()yzxyxzx则称运算对是可分配的。(或称对满足分配律)(2)矩阵的加法和乘法在上是可结合的，加法可交换，但乘法不可交换，乘法对加法()nMR是可分配的。例3、(1)普通的加法和乘法在,,,NZQR上都是可结合的，且是可交换的，乘法对加法是可分配的。(3)在幂集上可结合，可交换，,,()PS但是相对补不可结合，不可交换，和是互相可分配的。(4)在全体命题公式集合上可结合，可交换，,和是相互可分配的。三、一些特殊元素。设为上的二元运算，S1、幺元e：若，对则称eSxSexxex，e为运算的幺元。注：(1)若幺元存在必唯一。(2)若只有或只有lexxrxex，则le，称为左幺元或右幺元。re在上，矩阵加法的幺元是阶0矩阵，()nMRn矩阵乘法的幺元是阶单位矩阵。n在幂集()PS上，运算的幺元是，运算的幺元是全集S。例如：在上，加法的幺元是0，乘法的幺元是1。在,,,NZQR算没有幺元，只有右幺元0Z(0)xx上的减法运例4、在(非零实数集)上定义运算如下：*Raba(,*)abR则中的任何元素都是右幺元，*R但没有左幺元，使le(*)bRlebb，从而没有幺元。2、零元：若，对，SxSxx，则称为运算的零元。注：(1)若零元存在必唯一。(2)若只有，或只有llxrrx，则分别称为左零元或右零元。,lr如例4的任何元素都是左零元，(),*abaR从而也没有零元。但没有右零元r，例如：在上加法没有零元，乘法的零元是0。,,,NZQR在上矩阵加法没有零元，矩阵乘法的零元()nMR是阶0矩阵。n在幂集上，运算的零元是()PSS，运算的零元是。3、逆元：设为上的二元运算，S为运算eS的幺元，若对，存在xS1xS，使11xxxxe，则称1x为x的逆元。注：(1)逆元是针对某个元素x而言的(可能有些元素有逆元，有些没有)(2)若二元运算满足结合律且存在则必唯一。的逆元x3、逆元：设为上的二元运算，S为运算eS的幺元，若对，存在xS1xS，使11xxxxe，则称1x为x的逆元。注：(3)若只有1lxxe或只有1rxxe，则称为左逆元或右逆元。11,lrxx例如：普通加法运算在,,,NZQR上有幺元0，仅在,,ZQR上任意元素x有逆元()x，满足()()0xxxx在上只有0有逆元0，而其它的自然数就没有逆元。N在上矩阵的乘法只有可逆矩阵存在逆元。()nMR幂集()PS上关于运算有幺元，但除了外，其余元素都没有逆元。例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(1)11,2S解：加法，乘法都不是二元运算。(2)20,1S解：加法不是二元运算，乘法是二元运算。例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(3)32SxxZ解：加法，乘法都是二元运算。(4)421SxxZ解：加法不是二元运算，乘法是二元运算。例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(5)52,nSxnZ解：加法不是二元运算，乘法是二元运算。例6、在实数集上定义运算如下：R,abR2ababab(1)是上的二元运算吗？R解：因2abababR，是二元运算。(2)在上满足交换律，结合律吗？R解：因abba，满足交换律，()()abcabc，满足结合律。例6、在实数集上定义运算如下：R,abR2ababab(3)关于有幺元，零元吗？R解：因对，aR00aaa，故0为幺元，因111()()222aa，故12为零元。例6、在实数集上定义运算如下：R,abR2ababab(4)关于每个元素有逆元吗？R解：aR12a，有01212aaaaaa且12a时，无逆元。故12a时，112aaa，例7、设，二元运算和定义，问运算,,,Aabcd如下表和是否可交换的；是否有零元；是否有幺元；如果有幺元，指出哪些元素有逆元；逆元是什么？(1)没有零元，可交换，解：运算是幺元，a都有逆元，且1aa1cc,,,abcd，互为逆元。,bd(2)不可交换，解：运算是左零元，a是幺元，b只有有逆元，1bbb，由于cdb，故是的左逆元，的右逆元，是cddc(2)解：但它们的逆元都不存在。四、其它一些运算律和特殊元素。(了解)1、设和都是上的可交换的二元运算，S若,xyS，()xxyx()xxyx则称和满足吸收律。四、其它一些运算律和特殊元素。(了解)2、设是上的二元关系，S若(不是零元),,xyzSx满足：(1)若xyxz，则yz(2)若yxzx，则yz就称运算满足消去律。四、其它一些运算律和特殊元素。(了解)3、幂等元。是上的二元运算，对S设xS，若，则称为幂等元。xxxx若上所有元素都是幂等元，则称运算满足幂等律。S例如：上的运算和，全体命题公式集合()PS上的运算和都满足吸收律，又分别满足幂等律，但都不满足消去律(如ABAC，不一定有)。BC,,,NZQR上的加法运算都不满足幂等律，但它们都有幂等元，幺元就是幂等元。第二节代数系统及其子代数和积代数内容：代数系统，子代数，积代数。重点：掌握代数系统，子代数的有关概念。了解：积代数的概念。一、代数系统。1、定义：非空集合和上的个运算SSk12,,,kfff(其中为元运算，ifin1,2,,ik)组成的系统称为一个代数系统，简称代数，记作12,,,,kSfff。例如：,N,,Z,,R(),,nMR，，，，(),,,~PS都是代数系统。2、代数常数(特异元素)。在某些代数系统中对于给定的二元运算存在幺元或零元，它们对该系统的性质起着重要作用，称为代数常数(特异元素)。例如：的幺元0，也可记为,Z,,0Z，(),,,~PS中和的幺元分别为和S，同样可记为(),,,~,,PSS。二、子代数系统。1、定义：设是代数系统，且12,,,,kVSfffBSB，若B对运算12,,,kfff都是封闭的，且和含有相同的代数常数，则BS称12,,,,kBfff为的子代数系统，简称子代数。V例如：是的子代数，,N,Z是的子代数，,,0N,,0Z但0,N是,Z的子代数，却不是,,0Z的子代数，因代数常数00N。2、平凡子代数，真子代数。设是代数系统12',,,,kVBfff12,,,,kVSfff的子代数，当BS和BV中的代数常数时，称为平凡子代数(分别是最大和最小的子代数)，当时，称BS为的真子代数。'VV例1、设，令,,0VZnZnzzZ为自然数，，n那么是的子代数。,,0nZV12,zzZ，证明：，则12,nznznZ1212()nznznzznZ即对+封闭，nZ又00nnZ，所以,,0nZ是的子代数。V证明：当时，1nnZZ，当0n时，00Z，它们是的平凡子代数，而其它的子代数都是V的非平凡的真子代数。V例1、设，令,,0VZnZnzzZ为自然数，，n那么是的子代数。,,0nZV例1、设，令,,0VZnZnzzZ为自然数，，n那么是的子代数。,,0nZV当时，1nnZZ，当0n时，00Z，它们是的平凡子代数，而其它的子代数都是V的非平凡的真子代数。V三、积代数。设是代数系统，11,VS22,VS，其中和是二元运算，令12SSS，对112212,,,xyxySS11221212,,,xyxyxxyy则为代数系统，称为,S的积代数，12,VV记12VV。例如：1,VZ23(),VMR和的积代数为1V2V123(),VVZMR其中运算为二元运算，11223,,,()zMzMZMR对11221212,,,zMzMzzMM，，，例如：1,VZ23(),VMR和的积代数为1V2V123(),VVZMR，，，有代数常数0，有代数常数1000100011V2V，有代数常数12VV1000,010001。第三节代数系统的同态与同构内容：代数系统的同态映射，同构映射。一般：掌握同态，单同态，满同态，同构的定义及判定。一、同态映射，同构映射的概念。代数系统的同态和同构是研究两个代数系统之间的关系。1、定义：设是代数系统，11,VS22,VS，其中和都是二元运算，若存在映射(即函数)，满足对任意的12:SS,xyS，有()()()xyxy则称是到的同态映射，简称同态。1V2V满同态，记12~VV单同态同构，记12VV注：若存在从到的满同态，则称1V2V为在下的同态象。2V1V例1、(1)，，1,VZ2,nVZ其中为普通加法，为模加法，即n,nxyZ，有()modxyxyn，这里0,1,2,,1nZn令:nZZ()()modxxn，()()xy()mod