离散数学几种典型的代数系统-课件

离散数学几种典型的代数系统 例3 3 设S=|是集合A上的关系,关于关系的复合运算可构成代数系统,是半群、。对任意aS，定义a1=a(n=1,2,)并且对于任意正整数m和n，有 若F=f|f:AA，则对于函数的复合运算 ，代数系统也是半群。在独异点中，对任意aS,有a0=e()式中的两个等式在独异点中亦成立。二、独异点 定义5-25-2若半群中运算*有单位元，则称为独异点。例4 4，,，和、和；和。例3中的和 例6 6对于半群，N的子集都是的子半群。例7 7对于半群的任一元素aS，令集合,是的子半群。三、子半群和子独异点定义5-3设是一个半群，若是的子代数，则称是的子半群。定义5-45-4设是一独异点，若是的子代数，且单位元eT，则称是的子独异点。例8 8关于独异点,子集N2,N3,N4,它们均不能构成的子独异点,令则,都是的子独异点。Y YY YY YY YY YN N练习5-11判断下述论断正确与否，在相应的括号中键入“Y”或“N”，（1）在实数集R上定义二元运算为：对于任意的a,bRa*b=a+b+ab(a)是一个代数系统；（）(b)是一个半群；（）（c）是一个独异点。（）(2)在实数集R上定义二元运算为，对任意a,bR，ab=|a|b(其中表示通常数的乘法运算)（a）是一个代数系统；（）(b)是一个半群；（）(c)是一个独异点。（）5.2 5.2 群的定义一、群的定义 定义5-55-5设是一个代数系统，如果运算*是可结合的，存在单位元e，且G中任何元素a都有逆元a-1，则称是一个群。(1 1)关于任意的a,b,c Ga,b,c G,有a a*(b(b*c)=(ac)=(a*b)b)*c c;(2)(2)存在一元素 e Ge G,使得关于任意的 aGaG,有e e*a=aa=a*e=ae=a;(3)(3)对任意 a Ga G,相应存在一元素 a a-1-1GG,使得 a a-1 1*a=aa=a*a a-1-1=e=e 例1 1 N 和R I +、R+和R-不是群。都是群。例2 2 设有Z Z4 4=0,1,2,30,1,2,3，模4 4的加法运算 定义为 。构成代数系统 Z;。4 40 1 2 30 1 2 30 01 12 23 30 1 2 30 1 2 31 2 3 01 2 3 02 3 0 12 3 0 13 0 1 23 0 1 2关于任意的a,b,cNa,b,cN4 4,令a+b=4ma+b=4m1 1+res+res4 4(a+b),(a+b),b+c=4mb+c=4m2 2+res+res4 4(b+c)(b+c)于是(a4b)4c=res4(a+b)4c=res4(res4(a+b)+c)=res4(4m1+res4(a+b)+c)=res4(a+b)+c)a4(b4c)=a4res4(b+c)=res4(a+res4(b+c)=res4(a+(4m2+res4(b+c)=res4(a+(b+c)=res4(a+b)+c)0是单位元，0的逆元是0，1和3互为逆元，2的逆元是2。是一个群。因此（a a 4 4b b）4 4c=a c=a 4 4(b (b 4 4c)c)，即 4 4满足结合律。二、循环群1 1群中元素的幂对于任意aG，a0=e,(n=0,1,2,)（a-1)0=e,(n=0,1,2,)（*）引进记号(n个a-1)因此（）式可表示为对于任意整数 和n n，下面二式仍然成立。例如 因为 又例如因为2 2、循环群定义5-65-6在群中,假如存在一元素gG,使得每一元素aG都能表示成gi(iI)的形式,则称群为循环群,称g为该循环群的生成元,并称群由g生成。按照群中逆元的表示方法例3 3群是循环群,1是生成元,10=0,对任意正整数n,n=1+1+1,依照群中元素的幂的表示方法n=1n、对任意负整数,例4 4例2 2中的群Z 是循环群,因为1 10 0=0=0,1 11 1=1=1,1 12 2=1=14 41=res1=res4 4(2)=2,(2)=2,1 13 3=1=12 24 41=21=24 41=res1=res4 4(3)=3(3)=3 因此1 1是其生成元。又3 30 0=0=0,3 31 1=3=3,3 32 2=3=34 43=res3=res4 4(6)=2,(6)=2,3 33 3=3=32 24 43=23=24 43=res3=res4 4(5)=1(5)=1 因此3 3也是其生成元。例5 5设G=a,b,c,e，*是G上的二元运算，*e a b ce a b ce ea ab bc ca e c ba e c bb c e ab c e ac b a ec b a ee a b ce a b ca*a=b*b=c*c=e*e=e,a*b=b*a=c,b*c=c*b=a,a*c=c*a=b是一阿贝尔群,但它不是循环群,一般称这个群为Klein四元群。三、群的阶和元素的周期 定义5-75-7设G 是一个群,假如G G是有限集,则称G 是有限群,G G中元素的个数称为群G 的阶;若G G是无限集,则称G 是无限群。定义5-85-8设是一个群,a Ga G,若存在正整数 r r,使得 a ar r=e=e,则称元素 a a 具有有限周期。使a ar r=e=e成立的最小的正整数 r r 称为 a a 的周期。假如关于任何正整数r r,均有 a ar r e e,则称 a a 的周期为无限。例6 6在群 中，单位元1的周期为1。（-1）2=（-1）4=（-1）6=1=1，例7 7在例2 2所给出的群Z 中,(,(参见例4 4)1 14 4=1=13 34 41=31=34 41=res1=res4 4(4)=0,(4)=0,2 21 1=2=2,2 22 2=2=24 42=res2=res4 4(4)=0,(4)=0,3 34 4=3=33 34 43=13=14 43=res3=res4 4(4)=0,(4)=0,定理5-15-1设是一由元素g生成的循环群，则（1）若g的周期为n，则是一个阶为n的有限循环群；（2）若g的周期为无限，则是一个无限阶的循环群。例如 循环群I+的生成元1 1和1 1，其周期均为无限，群I+是一个无限阶的循环群。循环群Z 的生成元是1 1和3 3。1 14 4=1=13 3 4 41=3 1=3 4 41=res1=res4 4(4)=0(4)=0 3 34 4=3=33 3 4 43=1 3=1 4 43=res3=res4 4(4)=0(4)=0 1 1和3 3的周期均为4 4，循环群Z 的阶也为4 4。练习5-25-21设有集合A=是函数的复合运算，判断下述各论断是否正确，在相应的括号中键入“Y”或“N”（1）令FA是一个群.()（2 2）令E EA A=.()（3）EA定义同上，是交换群。()(4 (4）E EA A定义同上，E 是循环群。()N NN NN NY Y5 5、3 3 群的性质一、关于相约性定理5-2设是一个群,则对任意的a,bG,(1)存在唯一的元素xG,使a*x=b;(2)存在唯一的元素yG,使y*a=b。证明（1）因为a,bG,所以。令假设也使得成立，则因此是满足的唯一的元素。则，因此，是方程的解 定理5-35-3 设G 是一个群,则对任意的a,b,cGa,b,cG (1 1)若a*b=a*c,a*b=a*c,则 b=cb=c;(2 2)若b*a=c*ab*a=c*a,则 b=cb=c。证 明 (1 1)令a*b=a*c=da*b=a*c=d,依照定理5-25-2,方程a*x=d a*x=d 在G G中只有唯一的解,故得b=cb=c。二、元素运算后求逆元等于元素分别求逆元后颠倒次序相运算 定理5-45-4设G 是一个群，则对任意a,b G a,b G，有 证明因为(ab)*(ab)=e根据定理5-35-3，有对任意有三、关于元素的周期 定理5-55-5群G 中的元素 a a 若具有有限周期 r r,则当且仅当 k k 是 r r 的整数倍时,a ak k=e=e。定理5-65-6 群中任一元素与它的逆元具有相同的周期。定理5-75-7在有限群G 中,每个元素均具有有限周期,且周期不超过群G 的阶。证明 设G 是有限群,#G=n#G=n,对任意a Ga G,构造序列a,aa,a2 2,a,a3 3,a,an n,a,an+1n+1,因为#G=n，所以序列中必存在ai=aj于是 因此 a a 的周期至多为 ,而 。定理5-7的结论关于无限群不成立。例如群 、例1 1关于5 5、2 2节例2 2中的群Z,单位元0的周期是1;1和3的周期均为4;2的周期为2,群的阶4、例2 2设是一个群,且关于任意的a,bG,有(a*b)2=a2*b2,则 是阿贝尔群,由已知（ab)=a2b2(a*b)*(a*b)=(a*a)*(b*b)a*(b*a)*b=a*(a*b)*ba*(b*a)*b=a*(a*b)*b利用定理5-3的相约性得b*a=a*b练习 5-35-31填空设Z6=，6是模6的加法，定义为：a6b=res6(a+b)，是一个群。（1）群的单位元是。（2）1的逆元是；2的逆元是；3的逆元是。（3）1的周期是，1与的周期相同。（4）2的周期是，2与的周期相同。NY2判断下述论断正确与否，在相应的括号中键入“Y”或“N”设是群，a,bG,a的周期为5,b的周期为3。则1）a3=e,a5=e,a8=e,a10=e,a14=e()()()()()2）b2=e,b3=e,b5=e,b6=e,b9=e,b15=e()()()()()()NYN0 05 54 43 36 65 53 34 4NYNYYY半群,独异点和群这三个概念之间的区别:半群N+,独异点Z+,群I+。若是的子群,则也是群、5 54 4 子群及其判别一、子群的定义定义5-95-9设是一个群，若是的子代数，单位元eH，且对于任意的aH，有a-1H，则称是的子群。e ea a G GH HI+既是半群、独异点，也是一个群，对于 I I 的三个子集：E E1 1=E+只能看作是I+的子半群,E+只能看作是I+的子独异点,只有 E+才是I+的子群。对于任意的整数m，若令Im=.则均可构成的子群。例1 1KleinKlein的四元群a,b,c,e;有如下子群:，子集 不能构成G 的子群，子集 或 也不能构成G 的子群，e a b ce a b ce ea ab bc ca e c ba e c bb c e ab c e ac b a ec b a ee a b ce a b c，。和二、子群的判别要判断H H对于运算能否构成G 的子群，需要弄清以下三个问题。1 1 封闭性：对于任意a,b Ha,b H，是否有a b Ha b H；2 2 单位元：是否有e He H；3 3 可逆性；对于任意a Ha H，是否有a a-1-1 H H；定理5-85-8设G 是群，H H是G G的非空子集，若 (1)(1)对于任意的a,bHa,bH，有a*bHa*bH；(2)(2)对任意的aHaH，有 H H，则是G 的子群。定理5-95-9设 是一个群,H H是G G的一个非空子集,若关于任意 ,有 ,则 是 的子群。证明设aH，则由定理5-9的条件由e,aH,则又设a,bHa,bH，由上证得b b-1-1HH，因此 ,即a*bH,a*bH,于是根据定理5-85-8，H 是 G 的子群。解显然H是G的非空子集。例2 2设G 是一个群,a a是 G G中任一元素,令 即H H是a a的所有整数次幂的集合,问H H关于运算能否构成G 的子群？（1）对任意ai,ajH，有aiaj=ai+j因为i+jI，所以ai+jH；（2）对任意aiH,有aai=aia=a0=e,即a是ai的逆元，又由H的定义aH于是根据定理5-8，是的子群。显然是由元素a生成的一个循环群.例3 3设是一个群,定义G的子集H为H=试问H关于运算能否构成的子群。解：对任意xG，有xe=ex=x,所以eH，故H是G的非空子集。任取a,bH,则对任意xG必有ax=xa,bx=xb，于是根据群的性质因此a b Ha b H，根据定理5-9,H5-9,是G 的子群。定理5-105-10的证明：设a Ha H，由定理5-75-7，a a具有有限周期，设为r r，定理5-105-10设G 是一有限群，若H 是G 的子代数，则H 是G 的子群。定理5-115-11设G 是一个群，若H 是G 的有限子代数，则H 是G 的子群。其中ar1=ar*a1=e*a1=a,因此a1H,故是的子群。又因为运算 在 H H 上封闭，所以元素 a,aa,a2 2,a,a3 3，a ar-1r-1,a,ar r(=e)(=e)均在 H H 中，例4 4对于群Z，找出它的所有子群。单位元e=0e=0,1 1和5 5互为逆元,2 2和4 4互为逆元,3 3以3 3自身为逆元。Z 有如下子群：解按照运算 6 6的定义，a a 6 6b=resb=res6 6(a+b),(a+b),作出 群Z 的运算表如下：5 55 50 01 12 23 34 40 00 01 12 23 34 45 51 11 12 23 34 45 50 02 22 23 34 45 50 01 13 33 34 45 50 01 12 24 44 45 50 01 12 23 30 01 12 23 34 45 5三、子群的等价定义 如前所述，若是群的子群，则自身也必是群。反之，设G 是一个群，H H 是 G G的非空子集，若H 也是群，则H 必是G 的子群。证明如下：*在H H上是封闭的，所以H 是G 的子代数。又设 是群H 的单位元，e e为群G 的单位元。则有=,e=，于是=e,由群的相约性，得e=，因此eH。又对任aH，表示a在中的逆元，a表示a在中的逆元，根据定义5-9，是群的子群。于是有a=e=aa。由相约性，得=a，因此aH。定义5-95-9设G 是一个群，H H是G G的非空子集，若H 也是群，则称H 是G 的子群。练习5-41 1判断下述论断正确与否，在相应的括号中键入“Y Y”或“N N”。对于群Z 有如下子群。YNYNNY 5 5、5 5格一偏序集1 1。偏序集 定义5-105-10集合L L和定义在 L L 上的偏序关系 “”一起称为偏序集,用L 表示。若是集合A上的偏序关系，则的逆关系也必是上的偏序关系，证明如下：R ，I，2 和N|都是偏序集。对任意的 a a ，因为 自反，所以有 （a,aa,a）,于是（a,aa,a），因此 也是自反的。对任意 a,b A a,b A，若（a,ba,b）且（b,ab,a），则有（b,ab,a）且（a,ba,b），必有a=ba=b，因此 是反对称的。对任意a,b,c A,a,b,c A,若（a,ba,b）,(b,c,(b,c），则有（c,bc,b）且（b,ab,a），必有 （c,ac,a），于是（a,ca,c），因此 是可传递的。由上证得 也是偏序关系。根据逆关系的定义 =由定义 =例1 1设 A=A=，定义 A A 上的整除关系 ：当旦仅当 a a 整除 b b 时，有 。的次序图如下 的次序图如下6 61 13 36 62 22 23 31 1若L 是一个偏序集，则对于任意元素 1 1,2,2,3 3 L L，有以下六个关系式成立：11(5-)若12，21，则1=2(5-)若12，23，则13(5-)注意 在偏序集L 中，对任意元素 1 1，2 2 L L，若 1 1 2 2，则必有 2 12 1，若 2 12 1，则必有 1 1 2 2，因此，1 21 2等价于 2 12 1 。11（5-1）若12，21，则1=2（5-2）若12，23，则13(5-3)如果元素a a是 1 1和 2 2的下界。且对于任意 L L，若也是 1 1和 2 2的下界，便有 a,a,则称a a是 1 1和 2 2的最大下界，简记作a=glb(a=glb(1 1,2 2).).2 2最大下界和最小上界定义5-11 5-11 设 1 1和 2 2是偏序集L 中的两个元素,元素a La L，如果满足a a 1 1,a,a 2 2,则称a a是 1 1和 2 2的下界。定义5-12 5-12 设 1 1和 2 2是偏序集L 中的两个元素,元素b L ,b L ,假如满足 1 1 b b,2 2 b b,则称 b b是 1 1和 2 2的上界。如果元素 b b是 1 1和 2 2的上界，且对于任意 L L，若 也是 1 1和 2 2的上界，便有b b，则称 b b 是1 1和2 2的最小上界，简记作b=lub(b=lub(1 1,2 2)lub(2,3)=lub(2,3)=？,glb(12,18)=?glb(12,18)=?,lub(18,27)=?lub(18,27)=?有26，36；212，312；218，318。由于612，618，66，因此，lub（2，3）=6。612,618;212,218;312,318;112,118;因1 61 6,2 62 6,3 63 6,因此glb(12,18)glb(12,18)6 6。例2 2 设A=A=“整除”关系是A A上的偏序关系，其次序图如下，因此，它们构成一个偏序集A。1 11818121227272 23 36 69 9试问 glb(18,12)=?,lub(2,3)=?218,212;318,312,118,112。但glb(18,12)glb(18,12)不存在。类似地,1212,1818和3636均是2 2和3 3的上界,但 lublub(2 2,3 3)不存在。例3 3设A=A=，整除关系是A A上的偏序关系，其次序图如下 361812231 定理5-125-12设和是偏序集L 的两个元素，如果和有glb,glb,则glbglb是唯一的，如果和 有lublub，则lublub是唯一的。证明设和都是和的glbglb，由定义5-115-11,则 ,因此有=。类似地可以证明,和若存在lublub，则lublub也一定是唯一的。3 3 最小元素和最大元素 定义5-135-13设是一偏序集。(1)假如存在元素aL,使得关于所有的元素L,有a,则称a是的最小元素。(2)假如存在元素bL,使得关于所有的元素L,有b,则称b是的最大元素。定理5-135-13假如偏序集L 有最小元素,则最小元素是唯一的。假如L 有最大元素,则最大元素也是唯一的。证明设 和 都是L 的最小元素，则有 ，且 ，得 。若L 是一个格,则意味着L 也是一个形为L 的代数系统,其中 和 是L L上的两个二元运算,关于任意 ,表示在偏序“”意义下,和 的最小上界,表示 和 的最大下界。二、格 1 1、格的定义 定义5-145-14设L 是一个偏序集,假如L L中任意两个元素都存在着最大下界和最小上界,则称L 是格。=glb =glb（，），=lub=lub（，）。例4 4试判断下列次序图给出的偏序集哪些是格？解 (a a)不是格,(b)(b)不是格,(c)(c)是一个格,(,(d d)是一个格 efdcab(a)(a)edbca(b)(b)fhgdebca(c)(c)51210153630(d)(d)在格L L;中有如下四个关系式成立:2 2格的性质 定理5-145-14在格L 中，对于任意以下三式中若任意一式成立，那么其它两式也成立.证明 =设 ，=设 =设 定义5-155-15 设L 是格,P P是包含格的元素和符号=、,的命题,将P P中的、,和分别替换成、和所得的命题P PD D称为P P的对偶。例如 的对偶是 对偶原理:关于格L 上的任一真命题P P,其对偶 P PD D 亦为格L 上的真命题。定理5-155-15（交换律）设L 是格，则对任意的有:定理5-165-16（结合律）设L 是格，则对任意的 ，有证明定理5-175-17（吸收律）设L；是格，则对任意，有证明 (b)(b)由（5-45-4）另一方面，由（5-15-1）于是，由（5-5）（2）由（1)1)、(2(2）和反对称性 定理5-185-18（等幂律）设L L；是格，则对任意 ，有 证明 （a a）由定理5-17,5-17,定理5-19 5-19 (格的保序性)设L L;是格,则关于任意 ,有 证明 （1 1）又已知 由,和因为所以由(1)有 例4 4设 L=L=，L L上的整除关系 与L L构成一个格，记作L，3(6 4)=3 1=33(6 4)=3 1=3(36)(34)=6 12=6(36)(34)=6 12=6因此 3(64)(36)(34)3(64)(36)(34)6(34)=612=66(34)=612=6(63)(64)=31=3(63)(64)=31=3 因此 6(34)(63)(64)6(34)(63)(64)126431 定理5-205-20设L 是格，则对任意 ,有 证明(a a)由(5-4)(5-4)有于是，根据定理5-195-19有又由（5-45-4）有 3 3、格的另一种定义方式 定理5-21 5-21 设L 是一个代数系统,其中和都是二元运算,满足交换律,结合律和吸收律,则在L L上必存在一偏序关系,使得L 是一个格。能够证明关系是L L上的自反,反对称和可传递的关系,因此是L L上的偏序关系。在L上定义二元关系：对任意当且仅当时，有。进一步还可以证明，对任意 ，是在偏序关系意义下 1 1和 2 2的最小上界，1 2 1 2 是 1 1和 2 2的最大下界。故L 是一个格。格既可以看作是一个偏序集L，也可以看作是一个代数系统L。定义5-165-16设L 是一个代数系统，和 是 L L 上的两个二元运算，如果这两个运算满足交换律，结合律和吸收律，则称L 是格。例5 5在全集合 U U 的幂集 2 2U U=上的 包含关系“”是 2 2U U 上的一偏序关系。因为对任意Si2U，总有SiSi，所以是自反的。对任意S Si i,S Sj j 2 2U U ,若S Si i S Sj j，且S Sj j S Si i ，则必有S Si i=S=Sj j ，所以 是反对称的。对任意S Si,i,S Sj j，S Sk k 2 2U U，若S Si i S Sj j，S Sj j S Sk k，则必有S Si i S Sk k，所以 是可传递的。因此2 是一偏序集。因此S Si iSSj j是S Si i和S Sj j的上界。对于任意S Si,i,S Sj j 2 2U U，有S Si i S Si iSSj j，S Sj,j,S Si iSSj j，类似地可以证明，对任意 ，glb(sglb(si i,s,sj j)=s)=si issj j 因此2 是一个格 另一方面，集合的并运算和交运算和2 2U U构成代数系统2 ，因为运算和都满足交换律，结合律 和吸收律，因此2 是一个格。则必有S Si iSSj j S S。因此S Si iSSj j是S Si i和S Sj j的最小上界。即lub(Slub(Si i，S Sj j)=S)=Si iSSj j。若有S 2S 2U U，使得 S Si i S S，S Sj j S S，例6设U=a,b,cU=a,b,c 则2 2U U=,a,b,c,a,b,a,c,b,c,a,b,c=,a,b,c,a,b,a,c,b,c,a,b,c三子格 定 义 5-175-17 设 L,是 格,假 如 T 是L,的子代数,则称T,是L,的子格。格2 对应的代数系统形式的格是2.子格也是一个格。令 S S1 1=b,a,bb,c,a,b,c=b,a,bb,c,a,b,cS S2 2=,a,c,a,c=,a,c,a,cS S3 3=,a,c,a,b,a,c,b,c,a,b,c=,a,c,a,b,a,c,b,c,a,b,cS 是2 的子格。S 也是2 的子格。S S3 3不能与这两个运算构成2 的子格。a,b,ca,cb,ca,bacb261 112 12 练习5-55-51 1 设 L=1L=1，2 2，3 3，4 4，6 6，1212，在L L上定义整除关系，构成偏序集。（1 1）glb(6,4)=glb(6,4)=;lub(2,3)=;lub(2,3)=；（2 2）该偏序集的最小元素是 ，最大元素是 。12643213 43 4110(1)glb(6,9)=;glb(8,12)=、;(2)glb(9,7)=;lub(5,10)=、。12 2 2设L=1，2，3，11，12，在L上定义整除关系，构成偏序集.84211056397113.下面给出的三个次序图，其中哪些是格？在图下方相应的括号内键入“y”或“N”表示肯定或否定。()()()NYYY YY YN NN N 4 4对下图所给出的格判断以下子集是否能构成它的 子格。在相应的括号内键入“Y Y”或“N N”来回答 （1 1）S S1 1=e,c,b ()=e,c,b ()（2 2）S S2 2=d,b,a ()=d,b,a ()（3 3）S S3 3=c,d,b ()=c,d,b ()（4 4）S S4 4=c,d,a ()=c,d,a ()e ed dc cb ba a定义5-185-18设L 是一个格，若对于任意的 1 1,2 2，3 3 L L，有则称 L 是分配格。5 5、6 6 分配格和有补格一、分配格 1 1、分配格的定义dcbaecdbadbca 例1 1对任意的集合A A,2 是一个分配格,=aa=a=aa=a因此 b(cd)b(cd)(bcbc)bdbd)而(bc)(bdbc)(bd)例2 2 b(cd)=be=b b(cd)=be=bebcda 2 2、分配格的判别 定理5-225-22在格L 中,假如交运算对并运就是可分配的,则并运算对交运算也是可分配的;假如并运算对交运就是可分配的,则交运算对并运算也是可分配的。证明 设在格L 中，对任意 1 1，2 2，3 3LL，有 1 1 （2 32 3）=（1 21 2）（1 3 1 3）例如 设 L=1L=1,2 2,4 4,1616,3232,64,64,定义在L L上的整除关系与L L构成一个链。设是一个偏序集，若对于任意的 ，L L，或者 ，或者 ，则称是一个链。643216421 例3 3每一个链都是一个分配格。证明(1 1)先证明是一个格。由链的定义，对于任意 1 1，2 2LL或者 1 1 2 2，或者 2 2 1 1。若 1 1 2 2，则glb(glb(1 1,2 2)=)=1 1,lub(,lub(1 1,2 2)=)=2 2若 2 2 1 1，则glb(glb(1 1,2 2)=)=2 2,lub(,lub(1 1,2 2)=)=1 1所以是一个格，可将其表示为L。对任意 1 1,2 2 L L，1 21 2=lub(=lub(1 1,2 2),),1 21 2=glb(=glb(1 1,2 2)(2)(2)证明L 是一个分配格对任意 1,2,3L必有 2 3或者 3 2，不妨设 2 3，于是有 1 1 （2 32 3）=1 31 3。又因为 1 2 1 2 1 31 3，所以（12）（13）=13 因此 1 1 （2 32 3）=（1 21 2）（1 31 3）若 3 3 2 2，其证明方法类似，因此链是一个分配格。3 3分配格的性质 定理5-235-23设1，2，3是分配格中的任意三个元素，那么当且仅当证明 若 ，则显然反之，设则关于非分配格,定理5 52323不成立。cd=cb,cd=cb，但bd。例如，e ed db bc ca a二 有补格 1 1、最小元素0 0和最大元素1 1 例4 4I 是一个格,但这个格既无最小元素,又无最大元素。N 这个格有最小元素,但没有最大元素。格2 中无论U U是什么样的集合，均有最小元素和最大元素U U。具有最小元素和最大元素的格称为有界格。在有界格L 中，对任意L L，有0 0 ，1.1.于是由定理5-145-14，对任意 ，有 2 2补元素定义5-195-19设L 是一个有界格，L L，若存在元素 L L，使得 =1=1 =0 =0，则称 是 的补元素。在任一有界格中0 0和1 1互为补元素。例5 51 1a ab bc cd d0 01 1a ab bc cd de eg g0 0f f 因为对任意S2S2U U，所以S S的补集 是S S的补元素。例6 6格 是一个有补格，3 3有补格 定义5-205-20设L 是一个有界格，如果L L中每一个元素都有补元素，则称L 是有补格。(a)(a)是分配格,但不是有补格,(c)(c)既是有补格,又是分配格;例7 7 是有补分配格。三、有补分配格若格L 既是分配格,又是有补格,则称L 为有补分配格(d)是有补格，但不是分配格。(b)(b)既不是分配格，又不是有补格；(a(a)(b(b)(c(c)(d(d)1acb01ab01ab0c1acb0de有补分配格有如下一些性质：定理5-24在有补分配格L 中，任一元素的补元素是唯一的。使得 ,，,于是，由定理5-23.我们记的补元素为。证明假设 有两个补元素 和 ，定理5-255-25（对合律）在有补分配格L 中，对每一个 ，有 。证明 因为 ，由交换律有 .所以是的补元素，由补元素的唯一性,故有。定理5-26 5-26 (德摩根定律)在有补分配格 中,关于任意的 (a)(b)(a)(b)证明 （a a）由补元素的唯一性有练习5-65-61 1、填空 (1 1)下图所表示的格中 d d 有 个补元素,它们分别是_、a a 有 个补元素,它们是 、b b 的补元素是 。3a、b、c1dd1 1c cb bd da a0 0B BB B A A(2)(2)判断下列次序图所表示的格是什么性质的格。令A A分配格；B B有补格；C C有补分配格；D D非分配格，非有补格 在各次序图下相应的括号内填入字母 A A、B B、C C 或D D。1 1c cb bd da a0 01 1c cb bd da a0 01 1c cb bd da a0 0()()()5.7 5.7 布尔代数一 布尔代数的定义定义5-205-20如果一个格是有补分配格，则称其为布尔代数，一般记作 B;-。（1 1）交换律：（3)3)等幂律：（4 4）吸收律：（2 2）结合律：布尔代数 B-具有如下性质，对于B B中任意元素x x，y y，z z，有（5 5）分配律：（6 6）同一律：（7 7）零一律：（8 8）互补律：（9 9）对合律：（1010）德摩根定律：例8 8全集合 U U 的幂集 2 2U U 上定义的集合的并,交和补运算与 2 2U U 构成的代数系统2,称作集合代数,它是一个布尔代数,定义5-215-21设B-是一个代数系统,和 是B B上的二元运算,-是一元运算,若这些运算满足交换律,分配律,同一律和互补律,则称B-是布尔代数。例 设 是一布尔代数，a,b,ca,cb,ca,bacb其次序图如下：二、布尔代数的性质 定理5-275-27布尔代数的每一子代数都是布尔代数。定理5-295-29每一有限布尔代数都有2 2n n(nZnZ)个元素,元素个数相同的布尔代数必同构。定理5-285-28布尔代数的每一满同态象也是布尔代数。例9设 ,则 和等都是例8中的子代数.三、有限布尔代数的同构 定义5-115-11设是布尔代数,假如元素a 0,且对每一个x B,有xa=a或xa=0,则称a是原子。定理5-30 5-30 设是有限布尔代数,对每一个非0的x B,必有一原子a,使得xa=a。例9设 ,则原子为a,b,c、定理5-31 5-31 设是布尔代数，a1,a2是原子，则a1a2=0，否则a1=a2.定理5-32 5-32 设是布尔代数,x为B中任意非0的元素,a1,a2,an是满足ai x的所有原子,则x=a1a2an、证明:由ai x,故a1a2an x;因此只要证明:x a1a2an、假如不是如此,令y=a1a2an,则须证明xy=0,若xy！=0,则存在一原子ai使得ai x,ai y,即ai a1a2an=y,故得ai y,且ai y!、定理5-335-33设是有限布尔代数,M是原子的集合,则与同构、证明:令h:B2Mh为双射练习5-75-71在下列各题后面的括号中键入“Y”或“N”来回答各题中相应的问题。（1）设是一个五元素的分配格，问该格是有补格吗？（）（2）设是一个九元素的有补格，问该格是分配格吗？（）（3）U=a,b,c，2U；是布尔代数吗？()(4)上题的2U；的子代数是布尔代数吗？()()N NN NY YY Y2 2、证明在一个独异点中所有左可逆元的集合 形成一个子独异点。证明 设H H是独异点中所有左可逆元的集合,e e 是的单位元。因为e*e=ee*e=e,因此e e是左可逆元,故eHeH且H H非空。有a*bH,a*bH,故是的子独异点。设a,bHa,bH，则必存在元素 ，S S，使得 *a=e,*b=e,a=e,*b=e,于是 （*)*)*（a*ba*b）=*(*a)*b=*b=e=*(*a)*b=*b=e 因此元素 a*b a*b 也存在左逆元 *，感谢您的聆听！