离散数学几个典型的代数系统62公开课获奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,6.2,环与域,环定义与实例,特殊环,互换环,含幺环,无零因子环,整环,域,第1页,2,环定义,定义 设是代数系统，+和是二元运算.,假如满足如下条件:（1）构成互换群（2）构成半群（3）运算有关+运算适合分派律,则称是一种环.,第2页,3,环中术语,一般称+运算为环中加法，运算为环中乘法.,环中加法单位元记作 0,乘法单位元（假如存在）记作 1.,对任何元素 x，称 x 加法逆元为负元，记作x.,若 x 存在乘法逆元话，则称之为逆元，记作 x1.,第3页,4,环实例,(1)整数集、有理数集、实数集和复数集有关普,通加法和乘法构成环，分别称为整数环Z，有,理数环Q，实数环R 和 复数环C.(2)n(n2)阶实矩阵集合Mn(R)有关矩阵加,法和乘法构成环，称为n阶实矩阵环.,(3)集合幂集P(B)有关集合对称差运算和,交运算构成环.(4)设Zn0,1,.,n1，和分别表达模n,加法和乘法，则构成环，称为模n整,数环.,第4页,5,特殊环,定义 设是环，(1)若环中乘法适合互换律，则称 R是互换环.(2)若环中乘法存在单位元，则称 R是含幺环.(3)若a,bR，a b=0 a=0b=0，则称R是无零因子环.(4)若 R 既是互换环、含幺环，也是无零因子环，则称 R 是整环.,(5)若 R为整环，|R|1,且aR*=R0，a1R,则称 R 为域.,第5页,6,零因子定义与存在条件,设是环，若存在 ab=0,且 a0,b0,称 a 为左零因子，b为右零因子，环 R 不是无零因子环.,实例，其中 23=0，2 和 3 都是零因子.,无零因子环条件：,可以证明：ab=0 a=0 b=0 消去律,第6页,7,特殊环实例,(1)整数环Z、有理数环Q、实数环R、复数环C都是互换环、含幺环、无零因子环和整环.其中除Z之外都是域,(2)令2Z=2z|zZ，则构成互换环和无零因子环.但不是含幺环和整环.,(3)设nZ,n2,则 n 阶实矩阵集合 Mn(R)有关矩阵加法和乘法构成环，它是含幺环，但不是互换环和无零因子环，也不是整环.,(4)构成环，它是互换环、含幺环，但不是无零因子环和整环.,注意：对于一般 n,Zn是整环且是域 n是素数.,第7页,8,例题,判断如下集合和给定运算与否构成环、整环和域.,(1)A=a+bi|a,bQ,i2=1,运算为复数加法和乘法.,(2)A=2z+1|zZ,运算为一般加法和乘法,(3)A=2z|zZ,运算为一般加法和乘法,(4)A=x|x0 xZ,运算为一般加法和乘法.,(5)，运算为一般加法和乘法,解,(2),(4),(5),不是环,.,为何？,(1),是环,是整环,也是域,.,(3),是环,不是整环和域,.,第8页,9,环性质,定理,设,是环，则,(1),a,R,，,a,0=0,a,=0(2),a,b,R,，,(,a,),b,=,a,(,b,)=,ab,(3),a,b,R,，,(,a,)(,b,)=,ab,(4),a,b,c,R,，,a,(,b,c,)=,ab,ac,，,(,b,c,),a,=,ba,ca,第9页,10,环中运算,例 在环中计算,(,a,+,b,),3,(,a,b,),2,解,(,a,+,b,),3,=(,a,+,b,)(,a,+,b,)(,a,+,b,)=(,a,2,+,ba,+,ab,+,b,2,)(,a,+,b,)=,a,3,+,ba,2,+,aba,+,b,2,a,+,a,2,b,+,bab,+,ab,2,+,b,3,(,a,b,),2,=(,a,b,)(,a,b,)=,a,2,ba,ab,+,b,2,第10页,11,6.3,格与布尔代数,格定义与实例,格性质,对偶原理,互换律、结合律、幂等律、吸取律,格等价定义,子格,格同构,特殊格：分派格、有界格、有补格、布尔格,第11页,12,格定义,定义 设是偏序集，假如x,yS，x,y均有,最小上界和最大下界，则称S有关偏序作成一种格.,由于最小上界和最大下界惟一性，可以把求x,y,最小上界和最大下界当作 x 与 y 二元运算和,，即 xy 和 xy 分别表达 x 与 y 最小上界和,最大下界.,注意：这里出现和符号只代表格中运算，,而不再有其他含义.,第12页,13,格实例,例 设n是正整数，Sn是n正因子集合.D为,整除关系，则偏序集构成格.x,ySn，,xy 是 lcm(x,y)，即 x 与 y 最小公倍数.xy,是 gcd(x,y)，即 x 与 y 最大公约数.,下图给出了格，和.,第13页,14,例 判断如下偏序集与否构成格，并阐明理由.,(1)，其中P(B)是集合B幂集.,(2)，其中Z是整数集，为不不小于等于关系.,(3)偏序集哈斯图分别在下图给出.,格实例（续）,解,(1),是格,.,称,为,B,幂集格,.,(2),是格,.(3),都不是格,.,第14页,15,格性质：对偶原理,定义 设 f 是具有格中元素以及符号=,和,命题.令 f*是将 f 中替代成,替代成,替代成,替代成所得到命题.称 f*为 f 对偶命题.,例如,在格中：f 是(ab)cc,f*是(ab)cc.,格对偶原理：设 f 是含格中元素以及符号=,和等命题.若 f 对一切格为真,则 f 对偶命题,f*也对一切格为真.,例如,若对一切格L均有 a,bL,aba，那么对一,切格L均有 a,bL,aba,第15页,16,格性质：算律,定理 设是格,则运算和适合互换律、结,合律、幂等律和吸取律,即(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,第16页,17,算律证明,证 (1)互换律.,ab 是 a,b 最小上界,ba 是 b,a最小上界,a,b =b,a,ab=ba.,由对偶原理,ab=ba 得证.,第17页,18,算律证明（续）,(2)结合律.由最小上界定义有 (ab)caba (I),(ab)cabb (II)(ab)cc (III),由式(II)和(III)有,(ab)cbc (IV),由式(I)和(IV)有 (ab)ca(bc).同理可证,(ab)c a(bc).根据偏序反对称性得到,(ab)c=a(bc).由对偶原理,(ab)c=,a(bc)得证.,第18页,19,算律证明（续）,(3)幂等律.显然 a aa,又由 a a 得 aa a.,由反对称性 aa=a.用对偶原理,aa=a 得证.,(4)吸取律.显然有,a(ab)a (V),由 a a,ab a 可得,a(ab)a (VI),由式(V)和(VI)可得 a(ab)=a,根据对偶原理,a(ab)=a 得证.,第19页,20,格作为代数系统定义,定理 设是具有两个二元运算代数系统,若对于和运算适合互换律、结合律、吸取律,则,可以合适定义S中偏序,使得构成格,且,a,bS有 ab=ab,ab=ab.,根据定理,可以给出格另一种等价定义.,定义 设是代数系统,和是二元运算,假如,和 运算满足互换律、结合律和吸取律,则,构成格.,第20页,21,子格定义及鉴别,定义 设是格,S 是 L 非空子集,若 S,有关L中运算和仍构成格,则称S是L 子格.,例 设格 L 如图所示.令,S1=a,e,f,g,S2=a,b,e,g,S1不是 L子格,S2是 L子格.由于对于,e,fS1，efS1.,第21页,22,格同态,定义,设,L,1,和,L,2,是格,f,:,L,1,L,2,若,a,b,L,1,有,f,(,a,b,)=,f,(,a,),f,(,b,),f,(,a,b,)=,f,(,a,),f,(,b,),成立,则称,f,为格,L,1,到,L,2,同态映射,简称,格同态,.,第22页,23,分派格定义,定义 设是格,若a,b,cL,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac),则称 L 为分派格.,注意：以上条件互为充足必要条件,在证明L为分派格时,只须证明其中一种等式即可.,第23页,24,分派格定义（续）,L1和 L2是分派格,L3和 L4不是分派格.,在 L3中,b(cd)=b，(bc)(bd)=a在 L4中,c(bd)=c，(cb)(cd)=d称 L3为钻石格,L4为五角格.,第24页,25,分派格鉴定及其性质,定理 设 L 是格,则 L 是分派格当且仅当 L 不具有,与钻石格或五角格同构子格.,证明省略.,定理 格 L 是分派格当且仅当 a,b,cL,ab=ac且ab=ac b=c.,推论,(1)不不小于五元格都是分派格.(2)任何一条链都是分派格.,第25页,26,分派格鉴定（续）,解 L1,L2和 L3都不是分派格.,a,b,c,d,e 是 L1子格,并且同构于钻石格；,a,b,c,e,f 是 L2子格,并且同构于五角格；,a,c,b,e,f 是 L3子格,也同构于钻石格.,例 阐明图中格与否为分派格,为何？,第26页,27,全上界与全下界,定义 设L是格,若存在 aL 使得 xL 有 a x,则称 a 为 L 全,下界；,若存在 bL 使得 xL 有 x b,则称 b 为 L 全,上界.,阐明：,格 L 若存在全下界或全上界,一定是惟一.,一般将格 L 全下界记为 0,全上界记为 1.,第27页,28,有界格定义及其性质,定义 设 L是格,若 L存在全下界和全上界,则称 L为,有界格,全下界记为0，全上界记为1.有界格 L 记为,.,注意：有限格 L=a1,a2,an是有界格,a1a2,an是 L 全下界,a1a2an是全上界.0,是有关运算零元,运算单位元.1 是有关,运算零元,运算单位元.,对于包括有界格命题,假如其中具有全下界0或全,上界1,求其对偶命题时,必须将0与1互换.,第28页,29,补元定义,定义,设,是有界格,a,L,若存在,b,L,使得,a,b,=0,和,a,b,=1,成立,则称,b,是,a,补元,.,注意：若,b,是,a,补元,那么,a,也是,b,补元,.,a,和,b,互为补元,.,第29页,30,实例,:,求补元,解：,L,1,中,a,c,互补,b,没补元,.,L,2,中,a,d,互补,b,c,互补,.,L,3,中,a,e,互补,b,补元是,c,和,d,c,补元是,b,和,d,d,补元是,b,和,c,.,L,4,中,a,e,互补,b,补元是,c,和,d,c,补元是,b,d,补元是,b,.,第30页,31,有界分派格中补元惟一性,定理 设是有界分派格.若L中元素 a,存在补元,则存在惟一补元.,证 假设 b,c 是 a 补元,则有 ac=1,ac=0,ab=1,ab=0,从而得到 ac=ab,ac=ab,由于L是分派格,b=c.,第31页,32,有补格定义,定义 设是有界格,若 L 中所有元素都,有补元存在,则称 L 为有补格.,例如,下图中 L2,L3和 L4是有补格,L1不是有补格.,第32页,33,布尔代数定义,定义,假如一种格是有补分派格,则称它为布尔格或布尔,代数.,在布尔代数中，假如一种元素存在补元,则是惟一,.可以把求补元运算看作是布尔代数中一元,运算.布尔代数标识为,其中为求补,运算,第33页,34,布尔代数实例,例 设 S110=1,2,5,10,11,22,55,110 是110正,因子集合.,gcd 表达求最大公约数运算,lcm表达求最小公倍数运算.,则 与否构成布尔代数？,第34页,35,布尔代数等价定义,定义 设是代数系统,和是二元运算.若,和运算满足互换律、结合律、幂等律、吸取律,即(1)a,bB有ab=ba,ab=ba,(2)a,b,cB有,a(bc)=(ab)(ac),a(bc)=(ab)(ac),(3)即存在0,1B,使得aB有 a1=a,a0=a,(4)aB,存在 aB 使得 aa=0,aa=1,则称是一种布尔代数.,可以证明，布尔代数两种定义是等价.,第35页,36,布尔代数性质,定理 设是布尔代数,则,(1)aB,(a)=a.,(2)a,bB,(3)(ab)=ab,(ab)=ab（德摩根律）,注意：德摩根律对有限个元素也是对旳.,第36页,37,证明,证(1)(a)是 a补元.A 是 a 补元.由补元惟一性得(a)=a.,(2)对任意 a,bB有(ab)(ab)=(aab)(bab)=(1b)(a1)=11=1,(ab)(ab)=(aba)(abb)=(0b)(a0)=00=0.,因此 ab是 ab 补元,根据补元惟一性可得,(ab)=ab.,同理可证(ab)=ab.,第37页,38,有限布尔代数表达定理,定理 设 L 是有限布尔代数，则 L 具有 2n 个元素,(nN)，且 L 与 同构，其中 S 是,一种 n 元集合.,结论：具有 2n 个元素布尔代数在同构意义下只有,一种.,第38页,