离散数学屈婉玲第十四章.ppt

《离散数学屈婉玲第十四章.ppt》由会员分享，可在线阅读，更多相关《离散数学屈婉玲第十四章.ppt（55页珍藏版）》请在三一办公上搜索。

1、1,第五部分 代数系统简介,主要内容二元运算及其性质 二元运算和一元运算、二元运算性质、特异元素代数系统的概念几个典型的代数系统 半群、独异点、群 环与域 格与布尔代数代数系统的同构与同态,2,第十四章 代数系统简介,主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构,3,14.1 代数系统的基本概念,定义14.1 设S为集合，函数f：SSS 称为S上的二元运算，简称为二元运算函数 f:SS 称为S上的一元运算，简称一元运算.S 中任何元素都可以进行运算，且运算的结果惟一S 中任何元素的运算结果都属于 S，即 S 对该运

2、算封闭,例1(1)自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是(2)整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是求一个数的相反数是Z上的一元运算.(3)非零实数集R*上的乘法和除法都是R*上的二元运算，而加法和减法不是求倒数是R*上的一元运算.,4,实例,(4)设Mn(R)表示所有n 阶(n2)实矩阵的集合，即 矩阵加法、乘法是Mn(R)上的二元运算.转置是一元运算.(5)S为任意集合，则、为P(S)上二元运算.运算为一元运算.(6)SS为S上的所有函数的集合，则合成运算为SS上二元运算.求反函数不一定是一元运算.,5,二元与一元运算的表示,1算符可以用,等符号

3、表示二元或一元运算，称为算符.对二元运算，如果 x 与 y 运算得到 z，记做 xy=z对一元运算,x的运算结果记作x.,2表示二元或一元运算的方法:解析公式和运算表公式表示 例 设R为实数集合，如下定义R上的二元运算：x,yR,x y=x.那么 34=3，0.5(3)=0.5,6,运算表：表示有穷集上的一元和二元运算,运算表,二元运算的运算表 一元运算的运算表,7,例2 设 S=P(a,b)，S上的和 运算的运算表如下,运算表的实例,8,二元运算的性质,定义14.2-4 设为S上的二元运算,(1)若对任意x,yS 有 xy=yx,则称运算在S上满足交换律.(2)若对任意x,y,zS有(xy)

4、z=x(yz),则称运算在S上满足结 合律.(3)若对任意xS 有 xx=x,则称运算在S上满足幂等律.,定义14.5-6 设和为S上两个不同的二元运算,(1)若对任意x,y,zS有(xy)z=(xz)(yz)，z(xy)=(zx)(zy),则称运算对运算满足分配律.(2)若和都可交换,且对任意x,yS有 x(xy)=x，x(xy)=x,则称和运算满足吸收律.,9,实例,Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2,10,实例,Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA

5、为从A到A的函数集，|A|2,11,特异元素：单位元、零元,定义14.7-9 设为S上的二元运算,(1)如果存在el(或er)S，使得对任意 xS 都有 elx=x(或 xer=x)，则称el(或er)是S中关于运算的左(或右)单位元.若eS关于运算既是左单位元又是右单位元，则称e为S上关于运算的单位元.单位元也叫做幺元.(2)如果存在 l(或 r)S，使得对任意 xS 都有 l x=l(或 x r=r)，则称 l(或 r)是S 中关于运算的左(或右)零元.若 S 关于运算既是左零元又是右零元，则称为S上关于运算的零元.,12,可逆元素和逆元,(3)设为S上的二元运算,令e为S中关于运算的单位

6、元.对于xS，如果存在yl(或yr)S使得 ylx=e（或xyr=e）则称yl(或 yr)是x的左逆元（或右逆元）.关于运算，若yS 既是 x 的左逆元又是 x 的右逆元，则称 y为x的逆元.如果 x 的逆元存在，就称 x 是可逆的.可以证明：对于给定二元运算，单位元或零元如果存在，则是唯一的.对于可结合的二元运算，给定元素若存在逆元，则是唯一的逆元,13,实例,消去律,定义14.10 设为S上的二元运算，如果对于任意的 x,y,zS满足以下条件：(1)若xy=xz且x，则y=z；(2)若yx=zx且x，则y=z；称运算满足消去律，其中(1)为左消去律，(2)为右消去律注意被消去的 x 不能是

7、运算的零元 整数集合上的加法和乘法满足消去律P(S)上的并和交一般不满足消去律.对称差运算满足消去律,A,B,CP(S)，都有 AB=ACB=C BA=CAB=C,14,15,代数系统,定义14.11 非空集合S和S上k个一元或二元运算f1,f2,fk组成的系统称为代数系统,简称代数，记做.实例：(1),是代数系统，+和分别表示普通加法和乘法.(2)是代数系统，和分别表示 n 阶(n2)实矩阵的加法和乘法.(3)是代数系统，Zn0,1,n-1，和分别表示模n的加法和乘法，对于x,yZn，xy=(xy)modn，xy=(xy)modn(4)是代数系统，和为并和交，为绝对补,16,代数系统的成分与

8、表示,构成代数系统的成分：集合（也叫载体，规定了参与运算的元素）运算（这里只讨论有限个二元和一元运算）代数常数（通常是与运算相关的特异元素：如单位元等）研究代数系统时，如果把运算具有它的特异元素也作为系统的性质之一，那么这些特异元素可以作为系统的成分，叫做代数常数.例如：代数系统：集合Z,运算+,代数常数0代数系统：集合P(S),运算和，无代数常数,17,代数系统的表示,(1)列出所有的成分：集合、运算、代数常数（如果存在）如,(2)列出集合和运算，在规定系统性质时不涉及具有单位元 的性质（无代数常数）如,(3)用集合名称简单标记代数系统 在前面已经对代数系统作了说明的前提下使用 如代数系统Z

9、,P(B),18,同类型与同种代数系统,定义14.12(1)如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.(2)如果两个同类型的代数系统规定的运算性质也相同，则称为同种的代数系统.例如 V1=,V2=,为 n 阶全0矩阵，E为 n 阶单位矩阵,V3=V1,V2,V3是同类型的代数系统，它们都含有2个二元运算,2个代数常数.V1,V2是同种的代数系统，V1,V2与V3不是同种的代数系统,19,运算性质比较,20,14.2几个典型的代数系统,主要内容半群、独异点与群环与域格与布尔代数,21,半群、独异点与群的定义,定义14.13(1)设V

10、=是代数系统，为二元运算，如果运算是可 结合的，则称V为半群.(2)设V=是半群，若eS是关于运算的单位元，则称V 是含幺半群，也叫做独异点.有时也将独异点V 记作 V=.(3)设V=是独异点，eS关于运算的单位元，若 aS，a1S，则称V是群.通常将群记作G.,22,实例,例1(1),都是半群，+是普通加 法.这些半群中除外都是独异点(2)设n是大于1的正整数，和都是半 群，也都是独异点，其中+和分别表示矩阵加法和矩阵 乘法(3)为半群，也是独异点，其中为集合对称差运算(4)为半群，也是独异点，其中Zn=0,1,n1，为模n加法(5)为半群，也是独异点，其中为函数的复合运算(6)为半群，其中

11、R*为非零实数集合，运算定义如 下：x,yR*,xy=y,半群：上的字代数和语言,例2 设是有穷字母表，kN，定义下述集合：k=a1a2ak|ai是上所有长度为k的串的集合.当k=0时，0=，表示空串.令 表示上所有有限长度的串的集合，+=*则表示上所有长度至少为1的有限串的集合.在*上可以定义串的连接运算，1,2*，1=a1a2am,2=b1b2bn有 12=a1a2amb1b2bn显然*关于连接运算构成一个独异点,称为上的字代数.上的语言L就是*的一个子集.,23,群码,例3 某二进制码的码字x=x1x2x7由7位构成，其中x1,x2,x3和x4为数据位,x5,x6和x7为校验位，且满足：

12、x5=x1x2x3 x6=x1x2x4 x7=x1x3x4这里的是模2加法.设G为所有码字构成的集合，在G上定义二元运算如下：x,yG,xy=z1z2.z7,zi=xiyi,i=1,2,7.那么构成群.这样的码称为群码,24,25,群的相关概念及子群,有限群：若群G是有穷集，则称G是有限群，否则称为无限群群 G的阶：群G含有的元素数，有限群G的阶记作|G|.交换群或阿贝尔(Abel)群：群中运算可交换实例：和是无限群，是n阶群上述所有的群都是交换群，但n阶（n2）实可逆矩阵的集合（是Mn(R)的真子集）关于矩阵乘法构成的群是非交换群子群：群G的非空子集H关于群的运算构成群，称为G的子群.实例：

13、H=nZ=nk|kZ，n为给定自然数，是的子群.当n=0和1时，子群分别是0和Z，称为平凡子群；2Z由能被2整除的全体整数构成，也是子群.,群的直积,定义14.14 设G1=和G2=是群，和分别为它们的二元运算，在集合AB上定义新的二元运算，,AB，有=称G=为G1与G2的直积，记作G1G2.例4 G1,G2分别为模2加和模3加群，它们的直积运算,26,27,环与域,定义10.15 设是代数系统，+和是二元运算.如果满足以下条件:(1)构成交换群(2)构成半群(3)运算关于+运算适合分配律则称是一个环.通常称+运算为环中的加法，运算为环中的乘法.,定义14.16 设是环，若(1)环中乘法 可交

14、换；(2)R中至少含有两个元素.且aR0，都有a1R；则称R是域.0指加法单位元，a1指a的乘法逆元,28,环与域的实例,例5(1)整数集、有理数集、实数集和复数集关于普通的加法和 乘法构成环，分别称为整数环Z，有理数环Q，实数环R 和复数环C.Q、R 和 C 也称为有理数域、实数域、复数 域.(2)n(n2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构 成环，称为 n 阶实矩阵环.(3)集合的幂集P(B)关于集合的对称差运算和交运算构成环.(4)设Zn0,1,.,n1，和分别表示模n的加法和乘 法，则构成环，称为模 n的整数环.当n为素数 时Zn构成域.,29,格的定义与性质,定义14.1

15、7 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格.求x,y 最小上界和最大下界看成 x 与 y 的二元运算和，,例6 设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集构成格.x,ySn，xy是lcm(x,y)，即x与y的最小公倍数.xy是gcd(x,y)，即x与y的最大公约数.,30,图2,例7 判断下列偏序集是否构成格，并说明理由.(1)，其中P(B)是集合B的幂集.(2)，其中Z是整数集，为小于或等于关系.(3)偏序集的哈斯图分别在下图给出.,实例,(1)幂集格.x,yP(B)，xy就是xy，xy就是xy.(2)是格.x,yZ，xy=max(

16、x,y)，xy=min(x,y)，(3)都不是格.可以找到两个结点缺少最大下界或最小上界,31,格的性质：算律,设是格,则运算和适合交换律、结合律、幂等律和吸收律,即(1)a,bL 有 ab=ba,ab=ba(2)a,b,cL 有(ab)c=a(bc),(ab)c=a(bc)(3)aL 有 aa=a,aa=a(4)a,bL 有 a(ab)=a,a(ab)=a,32,格作为代数系统的定义,设是具有两个二元运算的代数系统,若对于和运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序,使得 构成格,且a,bS 有 ab=ab,ab=ab.,格的等价定义：设是代数系统,和是二元运算,如果和满足交换

17、律、结合律和吸收律,则构成格.,33,分配格、有补格与布尔代数,定义14.18 设是格,若a,b,cL,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称L为分配格.注意：可以证明以上两个条件互为充分必要条件,L1 和 L2 是分配格,L3 和 L4不是分配格.称 L3为钻石格,L4为五角格.,实例,34,分配格的判别,分配格的判别：设 L 是格,则 L 是分配格当且仅当 L 不含有与钻石格或五角格同构的子格.小于五元的格都是分配格.任何一条链都是分配格.例6 说明图中的格是否为分配格,为什么？,解 都不是分配格.a,b,c,d,e 是L1的子格,同构于钻石格 a,b,c,e,f

18、 是L2的子格,同构于五角格；a,c,b,e,f 是L3的子格 同构于钻石格.,35,有补格的定义,定义14.19 设L是格,(1)若存在aL使得xL有 a x,则称a为L的全下界，记 为0；若存在bL使得xL有 x b,则称b为L的全上界，记为1.(2)若L存在全下界和全上界,则称L 为有界格,一般将有界 格L记为.,定义14.20 设是有界格,aL,若存在bL 使得 ab=0 和 ab=1 成立,则称b是a的补元.定义14.21 设是有界格,若L中所有元素都有补元存在,则称L为有补格.,36,补元的性质,注意：在任何有界格中,全下界0与全上界1互补.对于一般元素,可能存在补元,也可能不存在

19、补元.如果存在补元,可能是惟一的,也可能是多个补元.对于有界分配格,如果元素存在补元,一定是惟一的.,37,有界格中的补元及实例,例7,L1：a 与 c 互补,a 为全下界,c为全上界,b 没有补元.L2：a 与 d 互补,a 为全下界,d 为全上界,b与 c互补.L3：a 与 e 互补,a 为全下界,e 为全上界,b 的补元是 c 和 d;c 的补元是 b 和 d;d 的补元是 b 和 c.L4：a 与 e 互补,a 为全下界,e 为全上界,b 的补元是 c 和 d;c 的补元是 b;d 的补元是 b.L2,L3和L4是有补格,L1不是有补格.,38,布尔代数的定义与实例,定义14.22 如

20、果一个格是有补分配格,则称它为布尔格或布尔代数.布尔代数标记为,为求补运算.,例8 设 S110=1,2,5,10,11,22,55,110是110的正因子集合，gcd表示求最大公约数的运算，lcm表示求最小公倍数的运算，问是否构成布尔代数？为什么？,解(1)不难验证S110关于gcd 和 lcm 运算构成格.(略)(2)验证分配律 x,y,zS110 有 gcd(x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格,1作为S110中的全下界,110为全上界,1和110互为补元,2和55互为补元,5和22互为补元,10和 11互为补元,从而证明了为布尔代数.,3

21、9,实例,例9 设B为任意集合,证明B的幂集格构成布尔代数,称为集合代数.证(1)P(B)关于和构成格,因为和运算满足交换律,结合律和吸收律.(2)由于和互相可分配,因此P(B)是分配格.(3)全下界是空集,全上界是B.(4)根据绝对补的定义,取全集为B,xP(B),x是x的补元.从而证明P(B)是有补分配格,即布尔代数.有限布尔代数含有2n个元素.,代数系统的同构与同态,定义14.23 设V1=和V2=是同类型的代数系统，f：AB，且x,yA有 f(xy)=f(x)f(y)，则称f是V1到V2的同态映射，简称同态.f若是单射，称为单同态；若是满射，称为满同态(V2是V1的同态像，记作V1V2

22、）；若是双射，称为同构，记作V1V2.V到V的同态f 称为自同态.类似地可以定义单自同态、满自同态和自同构.同态性质：设 f 是V1=到V2的同态映射，(1)若运算具有交换律、结合律、幂等律等，那么在f(V1)中运算也具有相同的算律（注意，消去律可能有例外）.(2)f(e1)=e2，f(1)=2，f(x1)=f(x)1,40,实例,例10(1)V1=,V2=Z为整数集合，+为普通加法；Zn=0,1,n1，为模n加.令 f：ZZn，f(x)=(x)mod n f 是V1到V2的满同态(2)设V1=,V2=，R和R*分别为实数集与非零实数集，+和分别表示普通加法与乘法令 f：RR*，f(x)=ex

23、 f 是V1到V2的单同态.(3)设V=，Z为整数集，+为普通加法.aZ，令 fa：ZZ，fa(x)=ax，fa是V的自同态.f0为零同态；当a=1时，称fa为自同构；除此之外其他的fa都是单自同态.,41,42,第十四章 习题课,主要内容代数系统的构成：非空集合、封闭的二元和一元运算、代数常数 二元运算性质和特异元素：交换律、结合律、幂等律、分配律、吸收律、单位元、零元、可逆元和逆元同类型的与同种的代数系统、积代数半群、独异点与群、环与域、格与布尔代数的定义代数系统的同态与同构,43,基本要求,判断给定集合和运算能否构成代数系统判断给定二元运算的性质求二元运算的特异元素计算积代数判断或证明给

24、定集合和运算是否构成半群、独异点、群、环、域、格、布尔代数判断函数是否为同态映射和同构映射,44,练习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(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz,45,(2)设运

25、算的单位元和零元分别为 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的逆元.,解答,46,2下面是三个运算表(1)说明那些运算是可交换的、可结合的、幂等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元,练习2,47,解,解答,(1)*满足交换律，满足结合律，不满足幂等律.不满足交换律，满足结合律，满足幂等律.满足交换律，满足结合律，不满足幂等律.(

26、2)*的单位元为b，没有零元，a1=c,b1=b,c1=a 的单位元和零元都不存在，没有可逆元素.的单位元为 a，零元为c，a1=a，b,c不是可逆元素.说明：关于结合律的判断需要针对运算元素的每种选择进行验证，若|A|=n，一般需要验证n3个等式.单位元和零元不必参与验证.通过对具体运算性质的分析也可能简化验证的复杂性.,48,练习3,3.判断下列集合和运算是否构成半群、独异点和群.(1)a 是正整数，G=an|nZ,运算是普通乘法.(2)Q+是正有理数集，运算为普通加法.(3)一元实系数多项式的集合关于多项式加法.,解(1)是半群、独异点和群(2)是半群但不是独异点和群(3)是半群、独异点

27、和群方法：根据定义验证，注意运算的封闭性,49,4.判断下列集合和给定运算是否构成环和域,如果不构成,说明理由.(1)A=a+bi|a,bQ,其中i2=1,运算为复数加法和乘法.(2)A=2z+1|zZ,运算为实数加法和乘法(3)A=2z|zZ,运算为实数加法和乘法(4)A=x|x0 xZ,运算为实数加法和乘法.(5),运算为实数加法和乘法,解(1)是环,也是域.(2)不是环,因为关于加法不封闭.(3)是环,但不是域,因为乘法没有么元.(4)不是环,因为正整数关于加法的负元不存在.(5)不是环,因为关于乘法不封闭.,练习4,50,图13,5判别下述格L是否为分配格.,L1不是分配格,因为它含有

28、与钻石格同构的子格.L2和L3不是分配格,因为它们含有与五角格同构的子格.,L1 L2 L3,练习5,51,L1 L2 L3,图12,6针对下图，求出每个格的补元并说明它们是否为有补格,L1中,a与h互为补元,其他元素没补元.L2中,a与g互为补元.b的补元为c,d,f；c的补元为b,d,e,f；d的补元为b,c,e；e的补元为c,d,f；f的补元为b,c,e.L3中,a与h互为补元,b的补元为d；c的补元为d；d的补元为b,c,g；g的补元为d.L2与L3是有补格.,练习6,52,7对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）,并说明理由.(

29、1)S1=1,1/2,2,1/3,3,1/4,4,为普通乘法.(2)S2=a1,a2,.,an,ai,ajS2,aiaj=ai,这里的 n 为给定 正整数,n1.(3)S3=0,1,为普通乘法.(4)S4=1,2,3,6,x,yS4,xy与xy分别表示 x 与 y 的最小公倍数和最大公约数.(5)S5=0,1,为模2加法,为模2乘法.,练习7,53,解：,解答,(1)不是代数系统,因为乘法不封闭,例如44=16.(2)是半群但不是独异点,因为运算满足结合律,但是没有单 位元.(3)是独异点但不是群.因为运算满足结合律,单位元是1,可 是0没有乘法逆元.(4)是格,也是布尔代数.因为这两个运算满

30、足交换律和分配 律；求最小公倍数运算的单位元是1,求最大公约数运算 的单位元是6,满足同一律；两个运算满足补元律.(5)是域.对于模 n 的环Zn,当n为素数时构成域.,54,练习8,8.设G为非0实数集R*关于普通乘法构成的代数系统，判断下述函数是否为G的自同态？如果不是，说明理由.如果是，判别它们是否为单同态、满同态、同构.(1)f(x)=|x|+1(2)f(x)=|x|(3)f(x)=0(4)f(x)=2,55,解答,解(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)判断同态性质只需判断函数的单射、满射、双射性即可.,