《几个典型的代数系统离散数学优秀PPT.ppt》由会员分享，可在线阅读，更多相关《几个典型的代数系统离散数学优秀PPT.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、几个典型的代数系统离散数学12/2/20221第1页，本讲稿共61页1 半群与群半群与群DEFINITION 1.设设V=是代数系统，是代数系统，为二元运算，为二元运算，如果如果是是可结合可结合的，则称的，则称V为为半群半群。如：如：(1),都是半群，都是半群，其中其中+表示普通加法。表示普通加法。(2)是半群，其中是半群，其中表示矩阵乘法。表示矩阵乘法。12/2/20222第2页，本讲稿共61页可交换半群可交换半群：半群半群V中的二元运算可交换。中的二元运算可交换。含幺半群（独异点）含幺半群（独异点）：半群半群V中的二元运算含有幺元。中的二元运算含有幺元。子半群子半群：半群的子代数。半群的子
2、代数。子独异点子独异点：独异点的子代数。独异点的子代数。积半群积半群：若若V1,V2是半群，则是半群，则V1 V2是积半群。是积半群。积独异点积独异点：若若V1,V2是独异点，则是独异点，则V1 V2是积独异点。是积独异点。12/2/20223第3页，本讲稿共61页(1),都是可交换半都是可交换半群。群。(2)不是可交换半群，因为矩阵乘法不适合交不是可交换半群，因为矩阵乘法不适合交换律。换律。(1)中除了中除了外都是独异点，其中普通加法的幺元外都是独异点，其中普通加法的幺元是是0。(2)是独异点，矩阵乘法的幺元是是独异点，矩阵乘法的幺元是n阶单位矩阵阶单位矩阵E。,都是都是的子半群，且的子半群
3、，且 也是也是的子独异点，但的子独异点，但不是不是的子独异点，的子独异点，因为幺元因为幺元0 Z，但，但0 Z+。12/2/20224第4页，本讲稿共61页DEFINITION 2.设设V1=,V2=为半群，为半群，:S1S2，且且 x,y S1，有：，有：(x y)=(x)*(y)，则称则称 为为半群半群V1到到V2的的同态同态。设设V1=,V2=为独异点，为独异点，:S1S2，且，且 x,y S1，有：，有：(x y)=(x)*(y)，(e1)=e2，则称则称 为为独异点独异点V1到到V2的的同态同态。12/2/20225第5页，本讲稿共61页EXAMPLE 1 设半群设半群V1=，独异点
4、，独异点V2=，其中，其中 ，为矩阵乘法。令：为矩阵乘法。令：，则则T S，且，且T对矩阵乘法对矩阵乘法是封闭的。是封闭的。是是V1=的子半群。的子半群。12/2/20226第6页，本讲稿共61页在在中存在自己的幺元中存在自己的幺元 ，因为，因为也构成一个独异点，但它不是也构成一个独异点，但它不是V2=的子独异点。的子独异点。V2中的幺元中的幺元12/2/20227第7页，本讲稿共61页令令有：有：是半群是半群V1的自同态，但不是满自同态，的自同态，但不是满自同态，且同态象为且同态象为12/2/20228第8页，本讲稿共61页对于独异点对于独异点V2=，还是同一个映，还是同一个映射射，根据前面
5、的证明，对，根据前面的证明，对 x,y S都有：都有：(x y)=(x)(y)，但是但是而而 不是独异点不是独异点V2的幺元，的幺元，不是独异点不是独异点V2的自同态。的自同态。12/2/20229第9页，本讲稿共61页DEFINITION 3.设设是代数系统，是代数系统，为二元运算。如果为二元运算。如果是可是可结合的，存在幺元结合的，存在幺元e G，并且对，并且对G中的任意元中的任意元素素x都有都有x-1 G，则称，则称G为为群群。如，如，(1),都是群，而都是群，而,不是群，不是群，因为因为中的元素都没有逆元，而在中的元素都没有逆元，而在中只有中只有0有逆元有逆元0。(2)不是群，因为不是
6、所有的实矩阵都有逆矩阵。不是群，因为不是所有的实矩阵都有逆矩阵。12/2/202210第10页，本讲稿共61页EXAMPLE 2 设设G=a,b,c,e，为为G上的二元运算，由下表给出，不难上的二元运算，由下表给出，不难证明证明G是一个群。是一个群。e a b ceabce a b ca e c bb c e ac b a e该运算的特点：该运算的特点：e e为为G G中的幺元；中的幺元；是可交换的；是可交换的；G G中中的任何元素的逆元就是它自己；的任何元素的逆元就是它自己；在在a,b,ca,b,c三个元素中，任何两三个元素中，任何两个元素运算的结果都等于另一个元素运算的结果都等于另一个元素
7、。个元素。称这个群为称这个群为Klein四元群四元群。12/2/202211第11页，本讲稿共61页一些特殊的群：一些特殊的群：交换群交换群：群：群G中的二元运算可交换。也叫中的二元运算可交换。也叫阿阿贝尔贝尔(Abel)群群。无限群无限群：群：群G中有无限多个元素。中有无限多个元素。有限群有限群：群：群G中有有限个元素。有限群中有有限个元素。有限群G中的中的元素个数叫做元素个数叫做G的的阶阶，记作，记作|G|。12/2/202212第12页，本讲稿共61页如，如，(1),都是阿贝尔群，都是阿贝尔群，Klein四元群也是阿贝尔群。四元群也是阿贝尔群。(2),都是无限群，都是无限群，是有限群，是
8、有限群，其阶是其阶是n，Klein四元群也是有限群，其阶是四元群也是有限群，其阶是4。12/2/202213第13页，本讲稿共61页定理定理1：设设G为群，则为群，则G中的幂运算满足中的幂运算满足(1)对对 x G，(x-1)-1=x.(2)对对 x,y G，(xy)-1=y-1x-1.(3)对对 x G，xnxm=xn+m.(4)对对 x G，(xn)m=xnm.m,n是整数。是整数。12/2/202214第14页，本讲稿共61页定理定理2：设设G为群，对为群，对 a,b G，方程，方程ax=b和和ya=b在在G中有解，且有唯一解。中有解，且有唯一解。易证方程易证方程ax=b的唯一解是的唯一
9、解是x=a-1b，而方程，而方程ya=b的唯一解是的唯一解是y=ba-1。12/2/202215第15页，本讲稿共61页如，如，S=1,2,3，在群，在群中有方程中有方程1,2 x=1,3，由定理由定理2有有x=a-1b=1,2-1 1,3=1,2 1,3=2,3。即为原方程的解。即为原方程的解。1 2 3 1,2 1,3 2,3 1,2,31231,21,32,31,2,3 1 2 3 1,2 1,3 2,3 1,2,31 1,2 1,3 2 3 1,2,3 2,32 1,2 2,3 1 1,2,3 3 1,33 1,3 2,3 1,2,3 1 2 1,2 1,2 2 1 1,2,3 2,3
10、 1,3 31,3 3 1,2,3 1 2,3 1,2 22,31,2,33 2 1,3 1,2 11,2,32,31,31,2 3 2 1 同理可知，方同理可知，方程程y 1=2,3 的解是的解是y=1,2,3。abab12/2/202216第16页，本讲稿共61页定理定理3：设设G为群，则为群，则G中适合消去律，中适合消去律，即对即对 a,b,c G，有：，有：(1)若若ab=ac，则，则b=c.(2)若若ba=ca，则，则b=c.12/2/202217第17页，本讲稿共61页定理定理4：设设G为有限群，则为有限群，则G的运算表中的每一行（每的运算表中的每一行（每一列）都是一列）都是G中元
11、素的一个置换，且不同的行中元素的一个置换，且不同的行（或列）的置换都不相同。（或列）的置换都不相同。这就是说，在这就是说，在G G的运算表的每一行里。的运算表的每一行里。G G的的每个元素都出现且仅出现一次，行不同，元素每个元素都出现且仅出现一次，行不同，元素的排列顺序也不同。的排列顺序也不同。使用这个定理可以通过运算表使用这个定理可以通过运算表很快地判断出哪些代数系统很快地判断出哪些代数系统G=不是群。不是群。12/2/202218第18页，本讲稿共61页DEFINITION 4.设群设群，H是是G的非空子集。如果的非空子集。如果H关于关于G中中的运算的运算*构成群，则称构成群，则称H为为G
12、的的子群子群，记作，记作HG。如，在群如，在群中，取中，取2Z=2z|z Z，则则2Z关于加法运算构成关于加法运算构成的子群。的子群。同样，同样，0也是也是的子群。的子群。12/2/202219第19页，本讲稿共61页定理定理5：设设G为群，为群，H是是G的非空子集，如果对的非空子集，如果对 x,y H，都有都有xy-1 H，则，则H是是G的子群。的子群。子群判定定理子群判定定理如，对如，对 x G，G为为群，令群，令H=xk|k Z，即即x的所有次幂的集合。则的所有次幂的集合。则H是是G的子群。的子群。xm,xl H，有：，有：xm(xl)-1=xmx-l=xm-l H。称这个子群是由称这个
13、子群是由元素元素x生成的子群生成的子群，记作记作。12/2/202220第20页，本讲稿共61页EXAMPLE 3 群群（其中（其中 表示模表示模6加法）中由加法）中由2生成的子群生成的子群包含包含2的各次幂，的各次幂，21=2，22=2 2=4，23=2 2 2=0 =0,2,4。同理有：同理有：=0，=0,1,2,3,4,5，=0,3，=0,2,4。12/2/202221第21页，本讲稿共61页又如，设又如，设G为群，令为群，令C是与是与G中所有的元素都可交换中所有的元素都可交换的元素构成的集合，即的元素构成的集合，即C=a|a G x G(ax=xa)，则则C是是G的子群。的子群。a,b
14、 C，要证明，要证明ab-1 C，只要证明，只要证明ab-1与与G中所中所有的元素都可交换就行了。有的元素都可交换就行了。x G，有：，有：(ab-1)x=ab-1x=ab-1(x-1)-1)=a(x-1b)-1=a(bx-1)-1 =a(xb-1)=(ax)b-1=(xa)b-1=x(ab-1)。C是是G的子群。的子群。称称C为群为群G的的中心中心12/2/202222第22页，本讲稿共61页DEFINITION 5.在群在群G中如果存在中如果存在a G使得使得G=ak|k Z，则称则称G为为循环群循环群，记作，记作G=，称，称a为为G的的生成元生成元。如，如，是循环群，其生成元是是循环群，
15、其生成元是1或或-1，因为任何整数都可以由，因为任何整数都可以由若干个若干个1或若干个或若干个-1相加而得到。相加而得到。也是循环群，其生成元是也是循环群，其生成元是1或或5，因为，因为0,1,5中的每个中的每个数都可以由数都可以由1或或5作若干次模作若干次模6加法而得到。加法而得到。循环群都是阿贝尔群，但阿贝尔群不一定都是循环群。循环群都是阿贝尔群，但阿贝尔群不一定都是循环群。12/2/202223第23页，本讲稿共61页循环群生成元的判定方法：循环群生成元的判定方法：对无限阶循环群对无限阶循环群G=，G的生成元是的生成元是a和和a-1。对对n阶循环群阶循环群G=e,a,a2,an-1，G的
16、生成元的生成元是是at当且仅当当且仅当t与与n是互质的。是互质的。是无限阶循环群，生成元是是无限阶循环群，生成元是1和和-1，-1是是1的加法逆元。的加法逆元。是是6阶循环群，阶循环群，1和和5都与都与6互质，所以互质，所以1和和5是生成元。是生成元。12阶循环群阶循环群G=e,a,a11中，与中，与12互质的数有互质的数有1,5,7,11，则，则G的生的生成元就是成元就是a,a5,a7,a11。12/2/202224第24页，本讲稿共61页循环群循环群G=的子群仍是循环群。的子群仍是循环群。若若G是无限阶循环群，则是无限阶循环群，则G的子群除了的子群除了e外都是无限阶；外都是无限阶；N阶循环
17、群阶循环群G=的子群的阶都是的子群的阶都是n的正的正因子。对于因子。对于n的每个正因子的每个正因子d，G中只有中只有一个一个d阶子群，就是由阶子群，就是由an/d生成的子群。生成的子群。12/2/202225第25页，本讲稿共61页DEFINITION 6.设设S=1,2,n，S上的任何双射函数上的任何双射函数:SS构成构成了了S上上n个元素的置换，称为个元素的置换，称为n元置换元置换。如，如，S=1,2,3，令，令:SS，且有，且有(1)=2,(2)=3,(3)=1,则则 将将1,2,3分别置换成分别置换成2,3,1。此置换常被。此置换常被记为：记为：12/2/202226第26页，本讲稿共
18、61页一般的一般的n元置换元置换 可记为：可记为：n个不同元素有个不同元素有n!种排列方法。所以种排列方法。所以S上有上有n!个置换。个置换。如，如，1,2,3上有上有3!=6种不同的置换，即种不同的置换，即12/2/202227第27页，本讲稿共61页简记法：简记法：设设n元置换元置换=(a1a2am),mn，则，则 的映射关系是：的映射关系是：(a1)=a2,(a2)=a3,(am-1)=am,(am)=a1，而其它的元，而其它的元素素a都有都有(a)=a，称，称 为为m次轮换次轮换。任何任何n元置换都可表成不交的轮换之积。元置换都可表成不交的轮换之积。如，如，是是1,2,6上的置换，且上
19、的置换，且除了除了3和和4这两个保持不变的元素外，其它元素的映射这两个保持不变的元素外，其它元素的映射关系为：关系为：(1)=6,(6)=1,(2)=5,(5)=2。=(1 6)(2 5)12/2/202228第28页，本讲稿共61页又如，又如，也是也是1,2,6上的置换，且上的置换，且则有则有=(1 4 3 2 5)。根据这种表法，根据这种表法，1,2,3上的置换上的置换可记为：可记为：1=(1),2=(1 2),3=(1 3),4=(2 3),5=(1 2 3),6=(1 3 2)12/2/202229第29页，本讲稿共61页 设设S=1,2,n，S上的上的n!个置换构成集合个置换构成集合
20、Sn，其中恒，其中恒等置换等置换IS=(1)Sn，在，在Sn上规定二元运算上规定二元运算，对任意，对任意n元元置换置换,Sn，表示表示 与与 的复合。的复合。证明证明Sn关于置换的复合构成一个群。关于置换的复合构成一个群。证明：证明：(1)设设,Sn，与与 的复合的复合 显然也是显然也是S上的上的n元置换，即元置换，即 Sn，Sn对对运算是封闭的。运算是封闭的。(2),Sn，显然，显然()=()，Sn对对运算是可结合的。运算是可结合的。(3),Sn，有，有 IS=IS =，则恒等置换，则恒等置换IS 是是Sn中的幺元，且中的幺元，且 的逆置换的逆置换 就是就是 的逆元。的逆元。Sn关于置换的复
21、合关于置换的复合构成一个群。构成一个群。S上的上的n元对称群元对称群12/2/202230第30页，本讲稿共61页 n元对称群的任何子代数称为元对称群的任何子代数称为n元置换群元置换群。如：如：S3=(1),(1 2),(1 3),(2 3),(1 2 3),(1 3 2)就是就是3元元对称群。因为对称群。因为S3关于置换的复合运算关于置换的复合运算不能交换，所不能交换，所以以S3不是阿贝尔群。不是阿贝尔群。S3有有6个子群，即有个子群，即有6个个3元置换群。元置换群。见见P135。12/2/202231第31页，本讲稿共61页2 环与域环与域DEFINITION 7.设设是代数系统，是代数系
22、统，R为集合，为集合，+,为二元运算，如果为二元运算，如果(1)为阿贝尔群；为阿贝尔群；(2)为半群；为半群；(3)乘法乘法对加法对加法+适合分配律。则称适合分配律。则称是是环环。+可结合、可交换，存可结合、可交换，存在幺元，且任何元素在幺元，且任何元素都有逆元。都有逆元。可结合可结合12/2/202232第32页，本讲稿共61页如：如：(1),都是环。都是环。(2)是环。是环。(3)是模是模n的整数环。其中的整数环。其中Zn=0,1,n-1，和和 分别表示模分别表示模n的加法和乘法，即的加法和乘法，即 x,y Zn，有：，有：x y=(x+y)mod nx y=(xy)mod n12/2/2
23、02233第33页，本讲稿共61页交换环交换环：在环：在环中，中，适合交换律。适合交换律。含幺环含幺环：在环在环中，中，有幺元。此时，通常把有幺元。此时，通常把+幺元记作幺元记作0，幺元记作幺元记作1。可以证明。可以证明+的幺元恰好是的幺元恰好是的零元。的零元。左（右）零因子左（右）零因子：在环：在环中，若中，若 a,b R,a 0,b 0，但，但ab=0，则，则a为为R中的中的左零因子左零因子。b为为R中的中的右零因子右零因子。无零因子环无零因子环：环：环R中既不含左零因子，也不含右零因中既不含左零因子，也不含右零因子，即子，即 a,b R,ab=0a=0 b=0.0 0为为的零元的零元12
24、/2/202234第34页，本讲稿共61页如：如：(1),都是交换环。都是交换环。不是交换环，因为矩阵乘法运算不可交换。不是交换环，因为矩阵乘法运算不可交换。(2)它们都是含幺环。因为它们都是含幺环。因为1是是的幺元，也是的幺元，也是 的幺元。的幺元。n阶单阶单位矩阵位矩阵E是环是环Mn(R)的乘法幺元。的乘法幺元。(3),都是无零因子环。而都是无零因子环。而不一定是无零因子环。如不一定是无零因子环。如中有中有2 3=0，但，但2和和3都都不是不是0，所以，所以不是无零因子环，而不是无零因子环，而是是无零因子环无零因子环。12/2/202235第35页，本讲稿共61页DEFINITION 8.
25、若环若环是是交换、含幺、交换、含幺、和和无零因子无零因子的，的，则称则称R为为整环整环。若环若环至少含有至少含有2个元素个元素且是且是含幺含幺和和无无零因子零因子的，并且的，并且 a R(a 0)有有a-1 R，则称，则称R为为除除环环。若环若环既是既是整环整环，又是，又是除环除环，则称，则称R是是域域。（至少含有（至少含有2个元素、交换、含幺、无零因个元素、交换、含幺、无零因子、除子、除0外都有逆元）外都有逆元）12/2/202236第36页，本讲稿共61页如：如：(1)是整环但不是域。是整环但不是域。因为乘法可交换，因为乘法可交换，1是幺元，且不含零因子，所是幺元，且不含零因子，所以是整环
26、。但除了以是整环。但除了 1之外，任何整数都没有乘之外，任何整数都没有乘法的逆元，所以不是域。法的逆元，所以不是域。(2)是域，即实数域。因为是域，即实数域。因为 x R，x 0，有：有：x-1=1/x R.12/2/202237第37页，本讲稿共61页EXAMPLE 4 设设S为下列集合，为下列集合，+和和为普通加法和乘法。为普通加法和乘法。(1)S=x|x=2nn Z.(2)S=x|x=2n+1n Z.(3)S=x|x Zx0=N.(4)问问S和和+,能否构成整环？能否构成域？为什么？能否构成整环？能否构成域？为什么？12/2/202238第38页，本讲稿共61页解：解：(1)不是整环，也
27、不是域。因为乘法幺元是不是整环，也不是域。因为乘法幺元是1，而，而1 S.(2)不是整环，也不是域。因为不是整环，也不是域。因为不是群，不是群，S当当然就不是环，然就不是环，+的幺元是的幺元是0，而，而0 S.(3)不是群，因为除不是群，因为除0以外任何正整数以外任何正整数x的的加法逆元是加法逆元是-x，而，而-x S.S当然就不是环，更不当然就不是环，更不是整环和域。是整环和域。12/2/202239第39页，本讲稿共61页(4)S是域。是域。x1,x2 S，有：，有：S对对+和和是封闭的。是封闭的。又又乘法幺元乘法幺元1 S，易证，易证是整环。是整环。是域。是域。12/2/202240第4
28、0页，本讲稿共61页定理定理6：设设是环，则：是环，则：(1)a R，a0=0a=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.在环中做加法和乘法只能遵在环中做加法和乘法只能遵从加法的交换律和结合律、从加法的交换律和结合律、乘法的结合律、乘法对加法乘法的结合律、乘法对加法的分配律，以及此定理中所的分配律，以及此定理中所给出的算律。给出的算律。12/2/202241第41页，本讲稿共61页EXAMPLE 5 设设是环，是环，a,b R，计算，计算(a-b)2和和(a+b
29、)3.解：解：(a-b)2=(a-b)(a-b)=a2-ba-ab-b(-b)=a2-ba-ab+b2.(a+b)3=(a+b)(a+b)(a+b)=(a2+ba+ab+b2)(a+b)=a3+ba2+aba+b2a+a2b+bab+ab2+b3.幂运算幂运算分配律及定理分配律及定理6(2)6(2)定理定理6(3)6(3)及幂运算及幂运算幂运算幂运算分配律及幂运算分配律及幂运算分配律及幂运算分配律及幂运算注：乘法没有交换律注：乘法没有交换律注：乘法没有交换律注：乘法没有交换律12/2/202242第42页，本讲稿共61页3 格与布尔代数格与布尔代数 格有两种等价的定义：一种是从偏序集的角度给格
30、有两种等价的定义：一种是从偏序集的角度给出格的定义，这种定义可以借助哈斯出格的定义，这种定义可以借助哈斯(Hasse)(Hasse)图来表图来表示，因而比较直观、易于理解，这样定义的格称为示，因而比较直观、易于理解，这样定义的格称为偏偏序格序格；另一种是从代数系统的角度来给出格的定义，；另一种是从代数系统的角度来给出格的定义，这种定义方法我们在上几节的群、环的定义中已有所这种定义方法我们在上几节的群、环的定义中已有所体会，用代数系统的方法定义的格称为体会，用代数系统的方法定义的格称为代数格代数格。12/2/202243第43页，本讲稿共61页 布尔代数是计算机科学最重要的基础理布尔代数是计算机
31、科学最重要的基础理论之一，它在开关网络及数字电路的设计论之一，它在开关网络及数字电路的设计上有广泛深入的应用。上有广泛深入的应用。布尔代数是计算机科学工作者必备的基布尔代数是计算机科学工作者必备的基础知识，应掌握格与布尔代数的一般理论础知识，应掌握格与布尔代数的一般理论和方法。和方法。12/2/202244第44页，本讲稿共61页DEFINITION 7.设设是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上界和最大下界，则称都有最小上界和最大下界，则称S关于关于 构成一构成一个个格格。可将求可将求x,y的最小上界和最大下界看成的最小上界和最大下界看成x与与y的的二元运算二元运算和和，
32、即，即xy和和xy。偏序格偏序格12/2/202245第45页，本讲稿共61页EXAMPLE 6 设设n为正整数，为正整数，Sn为为n的正因子的集合，的正因子的集合，D为为整除关系，则整除关系，则构成格。构成格。x,y Sn，xy是是x与与y的最小公倍数，的最小公倍数，xy是是x与与y的最大公约数。的最大公约数。8421123612356101530如：如：12/2/202246第46页，本讲稿共61页EXAMPLE 7 判断下图中偏序集是否构成格，为什么？判断下图中偏序集是否构成格，为什么？abcdefabdeceabdfc解：都不是格。解：都不是格。(1)中的中的a,b没有下界。没有下界。
33、(2)中的中的b,d有上界有上界c和和e，但没有最小上界。，但没有最小上界。(3)中的中的b,c有上界有上界d,e,f，但没有最小上界。，但没有最小上界。(1)(2)(3)12/2/202247第47页，本讲稿共61页格的格的对偶原理：对偶原理：设设f 是含有格中的元素以及符号是含有格中的元素以及符号=,的的命题，令命题，令f*是将是将f 中的中的改写成改写成，改写成改写成，改写成改写成，改写成改写成所得到的命题，称为所得到的命题，称为f 的的对偶命题对偶命题。若若f 对一切格为真，则对一切格为真，则f*也对一切格为真。也对一切格为真。12/2/202248第48页，本讲稿共61页定理定理7：
34、设设为格，则运算为格，则运算和和适合交换律、适合交换律、结合律、幂等律和吸收律，即：结合律、幂等律和吸收律，即：(1)a,b L，有，有ab=ba,ab=ba.(2)a,b,c L，有，有(ab)c=a(bc),(ab)c=a(bc).(3)a L，有，有aa=a,aa=a.(4)a,b L，有，有a(ab)=a,a(ab)=a.12/2/202249第49页，本讲稿共61页证明：证明：(1)ab和和ba分别是分别是a,b和和b,a的最小上界，由于的最小上界，由于a,b=b,a，所以，所以ab=ba。同理可证同理可证ab=ba.(2)由最小上界的定义有：由最小上界的定义有：aa(bc),bbc
35、a(bc),cbca(bc).由式由式和和有：有：aba(bc).再由式再由式和和有：有：(ab)ca(bc).同理可证：同理可证：(ab)ca(bc).根据偏序关系的反对称性有：根据偏序关系的反对称性有：(ab)c=a(bc).类似地可以证明：类似地可以证明：(ab)c=a(bc).12/2/202250第50页，本讲稿共61页(3)显然显然aaa，又由，又由aa可得可得aaa。根据偏序关系的反。根据偏序关系的反对称性有：对称性有：aa=a.同理可证：同理可证：aa=a.(4)显然显然a(ab)a。又由又由aa,aba，可得：，可得：a(ab)a.由式由式和和可得：可得：a(ab)=a.同理
36、可证：同理可证：a(ab)=a.12/2/202251第51页，本讲稿共61页DEFINITION 8.设设是具有两个二元运算的代数系是具有两个二元运算的代数系统，且对于统，且对于*和和适合交换律、结合律、吸收律，适合交换律、结合律、吸收律，则可以适当定义则可以适当定义S中的偏序中的偏序，使得，使得构成构成一个一个格格，且，且 a,b S，有，有ab=a*b,ab=a b.代数格代数格只要吸收律成立，则幂等律就一定成立。只要吸收律成立，则幂等律就一定成立。证：证：a S，有，有aa=a(a*(aa)=a.同理可证同理可证a*a=a.12/2/202252第52页，本讲稿共61页DEFINITI
37、ON 9.设设是格，若是格，若 a,b,c L，有，有a(bc)=(ab)(ac)a(bc)=(ab)(ac)成立，则称成立，则称L为为分配格分配格。12/2/202253第53页，本讲稿共61页DEFINITION 10.在格在格中存在一个元素中存在一个元素a，b L,ab(或或ba)，则称，则称a为格为格L的的全下界全下界（或（或全上界全上界），记为），记为0（或（或1）。）。具有全上界和全下界的格称为具有全上界和全下界的格称为有界格有界格。记作记作.12/2/202254第54页，本讲稿共61页DEFINITION 11.设设是有界格，是有界格，a L，若存在，若存在b L，使得，使得a
38、 b=0,a b=1，则称则称b为为a的的补元补元。若格中每个元素都至少有一个补元，若格中每个元素都至少有一个补元，则称这个格为则称这个格为有补格有补格。对分配格对分配格L来说，若来说，若a L有补元，则一定是唯一有补元，则一定是唯一的补元。的补元。12/2/202255第55页，本讲稿共61页EXAMPLE 8 判断下图中的格是不是分配格、有补格？判断下图中的格是不是分配格、有补格？abceabdfcghaedbcabc01cab10(1)(2)(3)(4)(5)12/2/202256第56页，本讲稿共61页解：解：(1)、(2)和和(4)是分配格，但是分配格，但(3)和和(5)不是分配格。
39、不是分配格。在在(3)中，中，a(bc)=ae=a,(ab)(ac)=dd=d.而而(5)中，中，a(bc)=a1=a,(ab)(ac)=b0=b.(2)、(3)和和(5)是有补格，但是有补格，但(1)和和(4)不是有补格。不是有补格。在在(2)中，中，a和和h,b和和g,c和和e,d和和f互为补元。互为补元。在在(3)中，中，a,b,c中任意两个都互为补元，中任意两个都互为补元，d和和e互为补元。互为补元。在在(5)中，中，a和和b的补元都是的补元都是c，而，而c的补元是的补元是a和和b，0和和1互为补元。互为补元。在在(1)中，中，b不存在补元，不存在补元，a和和c互为补元。互为补元。在在
40、(4)中，中，a,b,c都不存在补元，都不存在补元，0和和1互为补元。互为补元。12/2/202257第57页，本讲稿共61页DEFINITION 12.如果格如果格是有补分配格，是有补分配格，则则称称L为为布尔格布尔格，也叫做，也叫做布尔代数布尔代数。记作。记作，其中，其中，表示求补运算。表示求补运算。如，如，(1)集合代数集合代数是布尔代数。是布尔代数。(2)开关代数开关代数是布尔代数。是布尔代数。12/2/202258第58页，本讲稿共61页定理定理8：设设是布尔代数，则有：是布尔代数，则有：(1)a L，a是唯一的。是唯一的。(2)a L，(a)=a.(3)a,b L，有，有(ab)=
41、ab.(ab)=ab.德德摩根律摩根律12/2/202259第59页，本讲稿共61页证明：证明：(3)(ab)(ab)=(aba)(abb)=(aa)b)(a(bb)=(1b)(a1)=1.(ab)(ab)=(aab)(bab)=(aa)b)(bb)a)=(0b)(0a)=0.ab是是ab的补元，即的补元，即(ab)=ab.同理可证：同理可证：(ab)=ab.12/2/202260第60页，本讲稿共61页定理定理9：若若L是有限布尔代数，则是有限布尔代数，则L含有含有2n个元个元(n N)，并且，并且L与与同构，同构，其中其中S是一个是一个n元集合。元集合。有限布尔代数有限布尔代数的表示定理的表示定理12/2/202261第61页，本讲稿共61页