《第三部分 代数结构.ppt》由会员分享，可在线阅读，更多相关《第三部分 代数结构.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三部分 代数结构,主要内容代数系统-二元运算及其性质、代数系统和子代数半群与群-半群、独异点、群环与域-环、整环、域格与布尔代数-格、布尔代数,第九章 代数系统,主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构,第九章: 代数系统,第一节：二元运算及其性质 第二节：代数系统第三节：代数系统的同态与同态,第九章: 代数系统,第一节：二元运算及其性质 第二节：代数系统第三节：代数系统的同态与同态,9.1 二元运算及其性质,本部分用代数方法来研究数学结构,故又叫代数结构,它将用抽象的方法来研究集合上的关系和运算。代数的概念
2、和方法已经渗透到计算机科学的许多分支中,它对程序理论,数据结构,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。代数，也称代数结构或代数系统，是指定义有若干运算的集合,9.1 二元运算及其性质,代数常由3部分组成：1.一个集合，叫做代数的载体。2.定义在载体上的运算。3.载体的特异元素，叫做代数常数。因此，代数通常用载体，运算和常数组成的n重组表示,9.1 二元运算及其性质,二元运算:设S是个集合,SS到S的一个函数(映射)f: SSS称为S上的一个二元代数运算注：映射有存在性和唯一性的要求,运算当然要此要求。存在性，x,yS，f()要有结果，并且此结果S唯一性，x,yS，f()只能
3、有一个结果S,9.1 二元运算及其性质,通常用*，+，来表示二元运算，称为算符例整数集合上的加法，乘法任意集合S的幂集上的并、交运算命题集合上的合取，析取运算例:f是A上的二元运算，即f是AAA的映射。x,yA，f()=zA,用算符*表示,即x*y=z,9.1 二元运算及其性质,例：f是R上的二元运算:x,yR，f()=x,用算符*表示,即x*y=x计算：3*4，(-5)*0.2,9.1 二元运算及其性质,一元运算：设A是个集合, 函数f: AA称为A上的一个一元代数运算例：整数集合、有理数集合上的相反数非零有理数x的倒数1/x集合的补运算逻辑公式的补运算,9.1 二元运算及其性质,例：在I+
4、上定义运算：*，+。x,yI+x*y=x,y的最大公约数，x+y=x,y的最小公倍数6*8=2，6+8=24，12*15=3，12+15=60例：在R上求平方根运算（一元运算）不是一个代数运算。-9不存在平方根，存在性不满足9有两个平方根，3，-3，唯一性不满足,9.1 二元运算及其性质,可以用运算表表示：S=a,b,c上的，*运算,9.1 二元运算及其性质,例：设S1,2,给出P(S)上的运算和运算表，S为全集合,9.1 二元运算及其性质,可交换的运算：*为S上的二元运算，对于任意的x，yS都有x*y=y*x*满足交换律实数集合的加法、逻辑公式集合的合取可结合的运算：*为S上的二元运算，对于
5、任意的x，y,zS都有(x*y)*z=x*(y*z)*满足结合律实数集合的加法、逻辑公式集合的合取,9.1 二元运算及其性质,*适合幂等律：*为S上的二元运算，对于任意的xS都有x*x=x满足x*x=x的x称为运算*的幂等元例集合的并和交适合幂等律集合的减一般不适合幂等律0是加法的幂等元0和1是乘法的幂等元,9.1 二元运算及其性质,运算*对是可分配的：和*为S上的二元运算，对于任意的x，y，zS都有 x*(yz)=(x*y)(x*z) （左分配律） (yz)*x=(y*x)(z*x) （右分配律）*对是满足分配律例实数上的乘法对加法是可分配的集合上的交对并是可分配的逻辑公式上的合取对析取是可
6、分配的,9.1 二元运算及其性质,运算*和满足吸收律：和*为S上的二元运算，对于任意的x，y，zS都有 x*(xy)=x x(x*y)=x例集合上的交和并满足吸收律逻辑公式上的合取和析取满足吸收律,9.1 二元运算及其性质,左幺元（右幺元）：设*是A上的二元运算，如果存在元素eL（或er）A，使得对一切xA， 均有eL * x=x（或x * er =x）则称eL（er）是A中关于运算*的一个左幺元（右幺元）若元素e既是左幺元，又是右幺元，则称e是A中关于*的一个幺元（e也可记为1，称单位元）,9.1 二元运算及其性质,例：实数集上加法运算，0是幺元；乘法运算则1是幺元幂集P（A）上的运算是幺元
7、，而运算则A是幺元例：实数集R上定义运算a,bR，a*b=a，则不存在左幺元，使得bR，eL*b=b，而对一切aR，bR，有b*a=b，该代数系统不存在左幺元。但是R中的每一个元素a都是右幺元,9.1 二元运算及其性质,定理：若el和er分别是S上对于*的左幺元和右幺元,那么el=er，且这个元素就是幺元证明： el=el *er=er推论：一个二元运算的幺元是唯一的证明：设e=el=er. 假设e是S中的单位元，则 e=e *e=e,9.1 二元运算及其性质,左零元（右零元）：*是A上的二元运算，如果存在元素0L（或0r）A，使得对一切xA， 均有0L * x= 0L（或x * 0r= 0r
8、）则称0L（0r）是A中关于运算*的一个左零元（右零元）若元素0既是左零元，又是右零元，则称0是A中关于运算*的一个零元注：零元不一定是0！,9.1 二元运算及其性质,例：实数集合R上,对运算而言,0是零元P(A)上,对运算A是零元；对运算是零元命题上,对运算T是零元；对运算F是零元,9.1 二元运算及其性质,定理：若0l和0r分别是S上对于*的左零元和右零元,那么0l=0r，且这个元素就是零元。而且零元是唯一的定理：设*为S上的二元运算，1和0分别为*运算的幺元和零元，如果S至少有两个元素，则10证明：反证法。假设1=0，任意xS有 x=x*1=x*0=0与假设矛盾！,9.1 二元运算及其性
9、质,设*是集合A上的二元运算，1A是运算*的幺元，对于xA，如果存在一个元素yA，使得x*y=1，y*x=1，则称y是x的逆元，记y=x-1，如果x的逆元存在，则称x是可逆的如果x*y=1 ，那么关于运算*，x是y的左逆元，y是x的右逆元例：I上的加法运算，则任一元素的逆元就是它的相反数；而对N上的加法运算，只有0存在逆元是0,9.1 二元运算及其性质,代数A由下表定义可以看出，b是幺元。a的逆元是c, b的逆元是自身，c的逆元是a和c,9.1 二元运算及其性质,定理10.4：设Z是集合, *是Z上的二元运算,并且是可结合的，运算*的幺元是1。若xZ有左逆元和右逆元,则它的左逆元等于右逆元,且
10、逆元是唯一的。证明：（1）先证左逆元=右逆元：设xl和xr分别是x的左逆元和右逆元,x是可逆的和可结合的（条件给出） xl*x=x*xr=1 xl*x*xr=(xl*x)*xr=1*xr=xr； xl*x*xr=xl*(x*xr)= xl*1 =xl； xl=xr,9.1 二元运算及其性质,（2）证明逆元是唯一的：假设y和z是x的二个不同的逆元,则y=y*1=y*（x*z）=（y*x）*z=1*z=z,这和假设相矛盾。x若存在逆元的话一定是唯一的（前提*是可结合的）,9.1 二元运算及其性质,*满足消去律：*是S上的二元运算，对于每一x,y,zS有 若x*y=x*z,且x0,则y=z； 若y*
11、x=z*x,且x0,则y=z；例：整数集合上加法，乘法运算都满足消去律幂集合上交和并运算不满足消去律对称差运算满足消去律（为什么？）,第九章: 代数系统,第一节：二元运算及其性质 第二节：代数系统第三节：代数系统的同态与同态,9.2 代数系统,代数系统：非空集合S和集合上k个一元或二元运算f1,fk所组成的系统符号V=构成一个代数系统必须具备的条件：一个非空集合S,称为载体在S上的运算,9.2 代数系统,常见代数系统：特异元素（代数常元）：二元运算中的单位元与零元中的+运算的单位元0中和运算的单位元和S,9.2 代数系统,通常也可把特异元素（常数）放在代数系统之中,形成 ：代数系统的基数|V|
12、=|S|,就是非空集合的基数,9.2 代数系统,同类型的代数系统：两个代数系统中有相同个数的运算和常数，且对应运算的元数相同例：V1=V2=,9.2 代数系统,如果具有相同构成成分的代数系统也有一组相同的称为公理的规则，那么他们同是某种特殊的代数系统例：代数系统有如下公理a+b=b+a(a+b)+c=a+(b+c)a+0=a代数系统,和它类似，都是可交换独异点这种代数类型的成员,9.2 代数系统,例：集合代数构成代数系统,是P(A)上代数运算例：逻辑代数A为命题公式的全体,是A上两个逻辑运算,9.2 代数系统,运算封闭：设*和是集合S上的二元和一元运算，S是S的子集如果a,bS蕴涵着a*bS，
13、那么S对*是封闭的如果aS蕴涵着 aS，那么S对是封闭的例：减法是Z上的运算，Z的子集自然数N可能x,yN，但x-yN减法在N上不是封闭的，即N对减法不封闭例：N对Z的加法运算+是封闭的,9.2 代数系统,子代数系统：是一个代数系统BA,BB对运算f1,f2,fk是封闭的B和S有相同的代数常元是的代数子系统例：整数集合Z在加法下构成一个代数系统Z2是偶数集合,是否其子代数系统？Z1是奇数集合,是否其子代数系统？,9.2 代数系统,例： 是代数系统 不是子代数系统N对减法不封闭的注：任何V=的子代数一定存在最大的子代数是它自己最小子代数：所有常元构成的子代数可能不存在！,9.2 代数系统,积代数
14、V：设V1=和V2=是同类型的代数系统，和为二元代数系统V=为V1, V2的积代数, 定义为 =V1和V2为V的因子代数,9.2 代数系统,定理：设V1=和V2=是同类型的代数系统，V=为V1和V2的积代数如果和运算是可交换(可结合、幂等)的，那么运算也是可交换(可结合、幂等)的如果e1和e2(01,02)分别为和运算的单位元(零元)，那么()也是运算的单位元(零元)如果x和y分别为和运算的可逆元素，那么也是运算的可逆元素，逆元为,第九章: 代数系统,第一节：二元运算及其性质 第二节：代数系统第三节：代数系统的同态与同态,9.3 同态和同构,动机：不同代数系统可能类型相同更进一步，可能有共同的
15、运算性质有些系统在结构上相似或相同同态和同构讨论代数系统的相似或相同的关系,9.3 同态和同构,例子：给定V1=, V2=, Z3=0,1,2, A=0,2,4, 3和6分别是表示模3和模6加定义函数f: Z3Af=, , f是双射函数在f的映射下，Z3和A有相同结构,9.3 同态和同构,同态映射(同态)f: AB V1=, V2=是同类型代数系统f(xy)=f(x)f(y)同态映射分类单同态：f为单射满同态：f为满射V1 V2同构：f为双射V1 V2自同态f: AA,9.3 同态和同构,例：设代数系统G1和G2, Nn =0,1,2,n-1f: NNn, f(x)=(x)mod nf是G1到
16、G2的同态 x,y N有 f(x+y)=(x+y)mod n =(x)mod n +n (y)mod n =f(x)+nf(y) 由于f为满射，f为满同态,9.3 同态和同构,例：设代数系统G和Hf: e,a,b,c 1,2f(e)=1; f(a)=1; f(b)=2; f(c)=2,第九章 习题课,主要内容代数系统的构成：非空集合、封闭的二元和一元运算、代数常数 二元运算性质和特异元素：交换律、结合律、幂等律、分配律、吸收律、单位元、零元、可逆元和逆元同类型的与同种的代数系统子代数的定义与实例积代数的定义与性质代数系统的同态与同构,基本要求,判断给定集合和运算能否构成代数系统判断给定二元运算
17、的性质求而二元运算的特异元素了解同类型和同种代数系统的概念了解子代数的基本概念计算积代数判断函数是否为同态映射和同构映射,练习1,1设运算为Q上的二元运算， x, yQ, xy = x+y+2xy, (1) 判断运算是否满足交换律和结合律，并说明理由.(2) 求出运算的单位元、零元和所有可逆元素的逆元.,(1) 运算可交换，可结合. 任取 x, yQ, xy = x+y+2xy = y+x+2yx = y x,任取 x, y, zQ, (xy)z = (x+y+2xy)+z+2(x+y+2xy)z = x+y+z+2xy+2xz+2yz+4xyz x(yz) = x+(y+z+2yz)+2x(
18、y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz,(2) 设运算的单位元和零元分别为 e 和 ，则对于任意 x 有 xe = x 成立，即 x+e+2xe = x e = 0 由于运算可交换，所以 0 是幺元.对于任意 x 有x = 成立，即 x+2x = x+2x = 0 = 1/2 给定 x，设 x 的逆元为 y, 则有 xy = 0 成立，即 x+y+2xy = 0 (x 1/2 )因此当x 1/2时， 是x的逆元.,解答,2下面是三个运算表(1) 说明那些运算是可交换的、可结合的、幂等的. (2) 求出每个运算的单位元、零元、所有可逆元素的逆元,练习2,解,解答,(1)
19、 * 满足交换律，满足结合律，不满足幂等律. 不满足交换律，满足结合律，满足幂等律. 满足交换律，满足结合律，不满足幂等律.(2) * 的单位元为b，没有零元， a1=c, b1=b,c1=a 的单位元和零元都不存在，没有可逆元素. 的单位元为 a，零元为c，a1=a，b, c不是可逆元素. 说明：关于结合律的判断需要针对运算元素的每种选择进行验证，若|A|=n，一般需要验证n3个等式.单位元和零元不必参与验证.通过对具体运算性质的分析也可能简化验证的复杂性.,练习3,3. 设G为非0实数集R*关于普通乘法构成的代数系统，判断下述函数是否为G的自同态？如果不是，说明理由. 如果是，判别它们是否
20、为单同态、满同态、同构. (1) f(x) = |x| +1(2) f(x) = |x| (3) f(x) = 0(4) f(x) = 2,解答,解 (1) 不是同态, 因为 f(22)=f(4)=5, f(2)f(2)=33=9 (2) 是同态，不是单同态，也不是满同态，因为 f(1)= f(1), 且 ran f 中没有负数.(3) 不是G 的自同态，因为 f 不是 G 到 G 的函数(4) 不是G 的自同态，因为 f(22)=2, f(2)f(2)=22=4 说明：判别或证明同态映射的方法(1) 先判断（或证明）f 是G1 到 G2的映射 f: G1G2. 如果已 知 f: G1G2，则这步判断可以省去.(2) x, y G1, 验证 f(xy) = f(x) f(y) (3) 判断同态性质只需判断函数的单射、满射、双射性即可.,