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

1、1 1第五章第五章 几种典型的代数系统几种典型的代数系统 本章在了解了代数系统一般概念的基础上，着重介绍几种本章在了解了代数系统一般概念的基础上，着重介绍几种典型的代数系统：半群、独异点和群，格和布尔代数。讨论这典型的代数系统：半群、独异点和群，格和布尔代数。讨论这些代数系统中的特殊元素以及这些代数系统具有的性质。些代数系统中的特殊元素以及这些代数系统具有的性质。 主要内容如下：主要内容如下： 5.1 5.1 半群和独异点；半群和独异点；5.5 5.5 格；格； 5.2 5.2 群的定义；群的定义； 5.6 5.6 分配格和有补格；分配格和有补格； 5.3 5.3 群的性质；群的性质； 5.7

2、 5.7 布尔代数布尔代数 5.4 5.4 子群及其判别；子群及其判别；2 25.1 5.1 半群和独异点半群和独异点一、半群半群 定义定义5-1 设设S是一个非空集合，是一个非空集合，是是S上的一个上的一个二元运算，如果二元运算，如果是可是可结结合合的的,则则称称代代数数系系统统是半群。是半群。;s 例例1 1 代数系统代数系统 N + 和和 N 、I+和和I 、R + 和和 R 都是半群，都是半群， 但但 和和 不是半群不是半群 . ; I/;0R例例2 代数系统代数系统和和都半群，都半群，3 3 例例3 3 设设S=|是集合是集合A上的关系，对于关系的复上的关系，对于关系的复合运算合运算

3、可构成代数系统可构成代数系统，是半群是半群.。对任意对任意aS，定义，定义a1=a(n=1,2,)aaann1)()(,mnnmnmnmaaaaa并且对于任意正整数并且对于任意正整数m和和n，有，有 若若F=f|f:AA，则对于函数的复合运，则对于函数的复合运算算 ，代数系统，代数系统也是半群。也是半群。4 4在独异点在独异点中，对任意中，对任意aS,有有a0=e()式中的两个等式在独异点中亦成立。式中的两个等式在独异点中亦成立。), 2 , 1 , 0(1naaann二、独异点二、独异点 定义定义5-25-2 若半群若半群中运算中运算* *有单位有单位元，则称元，则称为独异点。为独异点。;

4、s; s 例例4 4 ，,，和和、和和；和和。例例3中的中的和和5 5 例例6 6 对于半群对于半群，N的子集的子集NnnN|22,|4,|343NnnNNnnN 都是都是的子半群。的子半群。 例例7 7 对于半群对于半群的任一元素的任一元素aS，令集合令集合 , ,32aaaT 是是的子半群。的子半群。三、三、 子半群和子独异点子半群和子独异点定义定义5-3 设设是一个半群是一个半群，若，若是是的子代数，则称的子代数，则称是是的子半群。的子半群。6 6 定义定义5-45-4 设设是一独异点，若是一独异点，若是是的子代数，且单位元的子代数，且单位元eT，则称，则称是是的子独异点。的子独异点。

5、例例8 8 对于独异点对于独异点, 子集子集N2，N3，N4，它们均不能构成它们均不能构成的子独异点，的子独异点， 令令 ,|4,|3,|2432ZnnZZnnZZnnZ则则，都是都是的子独异点。的子独异点。7 7Y YY YY YY YY YN N练习练习5-1 1判断下述论断正确与否，在相应的括号中键入判断下述论断正确与否，在相应的括号中键入“Y”或或“N”，（1）在实数集）在实数集R上定义二元运算上定义二元运算为：对于任意的为：对于任意的a,bRa* *b=a+b+ab(a)是一个代数系统；是一个代数系统；（）(b)是一个半群；是一个半群；（）（c）是一个独异点。是一个独异点。（）(2)

6、在实数集在实数集R上定义二元运算为，对任意上定义二元运算为，对任意a,bR，ab=|a|b(其中其中表示通常数的乘法运算表示通常数的乘法运算)（a）是一个代数系统；是一个代数系统；（）(b)是一个半群；是一个半群；（）(c)是一个独异点。是一个独异点。（）8 85.2 5.2 群的定义群的定义一、群的定义一、群的定义 定义定义5-55-5 设设是一个代数系统，如果运算是一个代数系统，如果运算* *是可结合的，存在单位元是可结合的，存在单位元e，且，且G中任何元素中任何元素a都有逆都有逆元元a-1，则称，则称是一个群。是一个群。 （1 1）对于任意的）对于任意的a,b,c Ga,b,c G，有，

7、有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- 不是群。不是群。都是群。都是群。9 9 例例2 2 设有设有Z Z4 4= =0,1,2,30,1,2,3，模，模4 4的加法运算的加法运算 定义为定义为 。构成代

8、数。构成代数系统系统 Z; 。4)(44baresba 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 21010对于任意的对于任意的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)a

9、4(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满足结合律。满足结合律。1111二、循环群二、循环群 1 1群中元素的幂群中元素的幂 对于任意对于任意aG，a0=e, (n=0,1,2,)aaann1（a-1)0=e,(n=0,1,2,)（*）1111)

10、()(aaann引进记号引进记号(n个个a-1)1111)( aaaaann因此（因此（）式可表示为）式可表示为),(*,)(2101101naaaeannmnnmnmnmaaaaa)(;*对于任意整数对于任意整数 和和n n，下面二式仍然成立。，下面二式仍然成立。m11)()(nnnaaa1212例如例如 32525aaaa因为因为 )()()(*1121525aaaaaaaaaaa3111111)()()()()()()()()(aaaaeaaaaaaaaaeaaaaaaaaaaaaaaaaaa又例如又例如632)( aa因为因为11112121231232)()()()()()()()(

11、aaaaaaaaaaa661111111111111321111111)()()()()()()()()()(aaaaaaaaaaaaaaaaaaaeaaaaaaaa因因此此所所以以根根据据结结合合律律13132 2循环群循环群 定义定义5-65-6 在群在群中，如果存在一元素中，如果存在一元素gG，使，使得每一元素得每一元素aG都能表示成都能表示成gi(iI)的形式，则称群的形式，则称群为循环群，称为循环群，称g为该循环群的生成元，并称群为该循环群的生成元，并称群由由g生成。生成。按照群中逆元的表示方法按照群中逆元的表示方法nnn1)1 (1111111例例3 3 群群是循环群，是循环群，1

12、是生成元，是生成元，10=0，对任意正，对任意正整数整数n，n=1+1+1，按照群中元素的幂的表示方法，按照群中元素的幂的表示方法n=1n.)()()(,111nn对任意负整数对任意负整数,1414 例例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

13、 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也是其生成元。也是其生成元。1515 例例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 c a* *a=b* *b=c* *c=e* *e=e,a* *b=b* *a=c,b* *c=c* *b=a，a* *c=c* *a=b是一阿贝尔

14、群，但它不是循环群，一般称这是一阿贝尔群，但它不是循环群，一般称这个群为个群为Klein四元群。四元群。1616三、群的阶和元素的周期三、群的阶和元素的周期 定义定义5-75-7 设设G 是一个群，如果是一个群，如果G G是有限集，则是有限集，则称称G 是有限群，是有限群，G G中元素的个数称为群中元素的个数称为群G 的阶；的阶；若若G G是无限集，则称是无限集，则称G 是无限群。是无限群。 定义定义5-85-8 设设G; 是一个群，是一个群，a Ga G，若存在，若存在正整数正整数 r r ，使得，使得 a ar r =e=e，则称元素，则称元素 a a 具有有限周期。具有有限周期。使使a

15、ar r=e=e成立的最小的正整数成立的最小的正整数 r r 称为称为 a a 的周期。如果的周期。如果对于任何正整数对于任何正整数r r，均有，均有 a ar r e e，则称，则称 a a 的周期为的周期为无限。无限。1717例例6 6 在群在群 中，单位元中，单位元1的周期为的周期为1。（- -1）2=（- -1）4=（- -1）6= =1=1，;0R 例例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

16、 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 , 1818定理定理5-15-1 设设是一由元素是一由元素g生成的循环群，则生成的循环群，则（1）若）若g的周期为的周期为n，则，则是一个阶为是一个阶为n的有的有限循环群；限循环群；（2）若）若g的周期为无限，则的周期为无限，则是一个无限阶的是一个无限阶的循环群。循环群。例如例如 循环群循环群I+的生成元的生成元1 1和和11，其周期均为无，其周期均为无限，群限，群I+是一

17、个无限阶的循环群。是一个无限阶的循环群。 循环群循环群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。1919练习练习5-25-21设有集合设有集合A=是函数的复合运算，判断是函数的复合运算，判断下述各论断是否正确，在相应的括号中键入下述各论断是否正确，在相应的括号中键入“Y”或或“N”（1）令）令FA是一个

18、群是一个群.,dcba ;,:|AFAAff则()（2 2）令）令E EA A = =.是一个群则是双射 ;,:|AEAAff()（3）EA定义同上，定义同上，是交换群。是交换群。 () (4 (4） E EA A定义同上，定义同上，E 是循环群。是循环群。 ()N NN NN NY Y20205 53 3 群的性质群的性质一、关于相约性一、关于相约性定理定理5-2 设设是一个群，则对任意的是一个群，则对任意的a,bG，（1）存在唯一的元素）存在唯一的元素xG，使，使a* *x=b；（2）存在唯一的元素）存在唯一的元素yG，使，使y* *a=b。 证明证明（1）因为）因为a,bG,所以所以。令

19、。令Gba1bax1 假设假设也使得也使得成立，则成立，则bxaGx 因此因此是满足是满足的唯一的元素。的唯一的元素。bax1bxa xxe)(1xaaba 1 则则，因此因此，是方程是方程的解的解bbebaabaa)()(11ba1bxaxaa)(12121 定理定理5-35-3 设设G 是一个群，则对任意是一个群，则对任意的的a,b,cGa,b,cG （1 1）若）若a a* *b=ab=a* *c, c, 则则 b=cb=c； （2 2）若）若b b* *a=ca=c* *a a，则，则 b=cb=c。 证证 明明 （1 1）令）令a a* *b=ab=a* *c=dc=d，根据定理，根

20、据定理5-25-2，方程方程a a* *x = d x = d 在在G G中只有唯一的解，故得中只有唯一的解，故得b=cb=c。2222二、元素运算后求逆元等于元素分别求逆元后颠二、元素运算后求逆元等于元素分别求逆元后颠倒次序相运算倒次序相运算 定理定理5-45-4 设设G 是一个群，则对任意是一个群，则对任意a,b G a,b G ，有有111abba)( 证明证明 因为因为(ab)* * (ab)=e1)()(11abba又又)()()()()(111111abbababaeaaabba，因因此此根据定理根据定理5-35-3，有，有111abba)(对对任意任意有有11111121)(aa

21、aaaannn,21Gaaan2323三、关于元素的周期三、关于元素的周期 定理定理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 a

22、 G G，构造序列构造序列a,aa,a2 2,a,a3 3,a,an n,a,an+1n+1, , 因为因为#G=n，所以序列中必存在所以序列中必存在ai=aj. )(11nji于是于是 因此因此 a a 的周期至多为的周期至多为 , ,而而 。Gijij得)0(nijeaaaaaijijii2424定理定理5-7的结论对于无限群不成立。的结论对于无限群不成立。例如群例如群 . 例例1 1 对于对于5.25.2节例节例2 2中的群中的群Z ， 单位元单位元0的周期是的周期是1；1和和3的周期均为的周期均为4；2的周期为的周期为2，群群的阶的阶4. 例例2 2 设设是一个群，且对于任意的是一个群

23、，且对于任意的a,bG，有（有（a* *b)2=a2* *b2,则则 是阿贝尔群，是阿贝尔群，由已知（由已知（ab)=a2b2(a* *b)* *(a* *b)=(a* *a)* *(b* *b)a a* *(b(b* *a)a)* *b = ab = a* *(a(a* *b)b)* *b b利用定理利用定理5-3的相约性得的相约性得b* *a=a* *b2525练习练习 5-35-31填空填空设设Z6=，6是模是模6的加法，定义为：的加法，定义为：a6b=res6(a+b)，是一个群。是一个群。（1）群）群的单位元是的单位元是。（2）1的逆元是的逆元是；2的逆元是的逆元是；3的逆元是的逆元

24、是。（3）1的周期是的周期是，1与与的周期相同。的周期相同。（4）2的周期是的周期是，2与与的周期相同。的周期相同。5 , 4 , 3 , 2 , 1 , 0 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 4NYNYYY2626 半群，独异点和群这三个

25、概念之间的区别：半群半群，独异点和群这三个概念之间的区别：半群N+，独异点独异点Z+，群，群I+。 若若是是的子群，则的子群，则也是群也是群. 5 54 4 子群及其判别子群及其判别一、子群的定义一、子群的定义定义定义5-95-9 设设是一个群，若是一个群，若是是的子代数，单位元的子代数，单位元eH，且对于任意的，且对于任意的aH，有有a-1H，则称，则称是是的子群。的子群。 e ea a G G1aH H2727 I+既是半群、独异点，也是一个群，既是半群、独异点，也是一个群，对于对于 I I 的三个子集：的三个子集： E E1 1= =IiiEZzzENnn|,|,22232E+只能看作是

26、只能看作是I +的子半群，的子半群， E+只能看作是只能看作是I +的子独异点，的子独异点， 只有只有 E+才是才是I+的子群。的子群。 对于任意的整数对于任意的整数m，若令，若令Im=.则则均可构成均可构成的子群。的子群。Iiim|2828 例例1 1 KleinKlein的四元群的四元群a,b,c,e; 有如下子群：有如下子群： e， 子集子集 不能构成不能构成G 的子群，的子群， bae,子集子集 或或 也不能构成也不能构成G 的子群，的子群， acba, 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

27、 ee a b ce a b c，ae,，be, ce,。和和2929二、子群的判别二、子群的判别 要判断要判断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，

28、有，有a a* *bHbH； (2)(2)对任意的对任意的aHaH，有，有 HH， 则则H; 是是G 的子群。的子群。1a3030 定理定理5-95-9 设设 是一个群，是一个群，H H是是G G的一个非空子的一个非空子集，若对于任意集，若对于任意 ，有，有 ，则，则 是是 的子群。的子群。;GHba ;H;GHba1 证明证明 设设aH，则由定理，则由定理5-9的条件的条件由由e,aH,则则Heaa1Haae11 又设又设a,bHa,bH，由上证得，由上证得b b-1-1HH，因此，因此 , ,即即a a* *bH , bH , 于是根据定理于是根据定理5-85-8，H 是是 G 的子群。的

29、子群。Hba11)(3131解解 显然显然H是是G的非空子集。的非空子集。例例2 2 设设G 是一个群，是一个群，a a是是 G G中任一元素，令中任一元素，令 即即H H是是a a的所有整数次幂的集合，问的所有整数次幂的集合，问H H对于运算对于运算能否构成能否构成G 的子群？的子群？ ,320123aaaaaaaIiaHi （1）对任意）对任意ai,ajH，有，有aiaj=ai+j因为因为i+jI，所以所以ai+jH；i（2）对任意对任意aiH,有有aai=aia=a0=e,即即a是是ai的逆元，的逆元，ii 又由又由H的定义的定义aH于是根据定理于是根据定理5-8，是是的子群。的子群。显

30、然显然是由元素是由元素a生成的一个循环群生成的一个循环群.i3232例例3 3 设设是一个群，定义是一个群，定义G的子集的子集H为为H=试问试问H对于运算能否构成对于运算能否构成的子群。的子群。axxaGxa,对对于于任任意意解：解： 对任意对任意xG，有，有xe=ex=x,所以所以eH，故故H是是G的非空子集。的非空子集。 任取任取a,bH,则对任意则对任意xG必有必有ax=xa,bx=xb，于是根据群的性质，于是根据群的性质)()(xbaxba1111)(bxa11 )(xba)(1bxa)()()(111baxbaxbxa 因此因此a b Ha b H，根据定理，根据定理5-9, H5-

31、9, 是是G 的子群。的子群。 13333 定理定理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 上封闭，所以元素上封闭，

32、所以元素 a,aa,a2 2,a,a3 3，a ar -1r -1,a,ar r(=e)(=e)均在均在 H H 中，中， 3434 例例4 4 对于群对于群Z ，找出它的所有子群。，找出它的所有子群。 单位元单位元e=0e=0，1 1和和5 5互为逆元，互为逆元，2 2和和4 4互为逆元，互为逆元，3 3以以3 3自身为逆元。自身为逆元。Z 有如下子群：有如下子群： ,;60,;,630,;,6420.;66Z解解 按照运算按照运算 6 6的定义，的定义，a a 6 6b=resb=res6 6(a+b),(a+b),作出作出 群群Z 的运算表如下：的运算表如下：65 5 5 50 01 1

33、2 23 34 40 0 0 01 12 23 34 45 51 1 1 12 23 34 45 50 02 2 2 23 34 45 50 01 13 3 3 34 45 50 01 12 24 4 4 45 50 01 12 23 30 01 12 23 34 45 53535三、子群的等价定义三、子群的等价定义 如前所述，若如前所述，若是群是群的子群，则的子群，则自身也必是群。自身也必是群。 反之，设反之，设G 是一个群，是一个群，H H 是是 G G的非空子集，若的非空子集，若H 也是群，则也是群，则H 必是必是G 的子群。的子群。 证明如下：证明如下： * *在在H H上是封闭的，所

34、以上是封闭的，所以H 是是G 的子代数。的子代数。 又设又设 是群是群H 的单位元，的单位元，e e为群为群G 的单位元。的单位元。 e 则有则有=,e=，于是，于是=e,由群的相约性，得由群的相约性，得e=，因此，因此eH。eeeeeeeee 又对任又对任aH，表示表示a在在中的逆元，中的逆元，a表表示示a在在中的逆元，中的逆元，a1 根据定义根据定义5-9，是群是群的子群。的子群。a于是有于是有a=e=aa。由相约性，得。由相约性，得=a，因此，因此aH。1a13636 定义定义5-95-9 设设G 是一个群，是一个群，H H是是G G的非空子集，的非空子集，若若H 也是群，则称也是群，则

35、称H 是是G 的子群。的子群。练习练习5-41 1判断下述论断正确与否，在相应的括号中键入判断下述论断正确与否，在相应的括号中键入“Y”Y”或或“N”N”。 对于群对于群Z 有如下子群。有如下子群。)()()()()()(;3 , 2 , 1 , 0,;3 , 1 , 0,;3 , 0,;2 , 0,;1 , 0,;0444444YNYNNY37373838 5.55.5格格一偏序集一偏序集1 1。偏序集。偏序集 定义定义5-105-10 集合集合L L和定义在和定义在 L L 上的偏序关系上的偏序关系 “ “” ” 一起称为偏序集，用一起称为偏序集，用L 表示。表示。 若若是集合是集合A上的

36、偏序关系，则上的偏序关系，则的逆关系的逆关系也必是上的偏序关系，证明如下：也必是上的偏序关系，证明如下： R，I，2 和和N|都是偏都是偏序集。序集。3939对任意的对任意的 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）

37、 ,(b,c,(b,c） ， 则有（则有（c,bc,b） 且（且（b,ab,a） ，必有，必有 （c,ac,a） ，于是（，于是（a,ca,c） ，因此，因此 是可传递的。是可传递的。 由上证得由上证得 也是偏序关系。也是偏序关系。 4040根据逆关系的定义根据逆关系的定义 = = )6 , 6(),3 , 6(),3 , 3(),2 , 6(),2 , 2)(1 , 6(),1 , 3(),1 , 2(),1 , 1 (p 由定义由定义 = = ) 6 , 6(),6 , 3 (),3 , 3 (),6 , 2(),2 , 2)(6 , 1 (),3 , 1 (),2 , 1 (),1 ,

38、1 ( 例例1 1 设设 A= A= ，定义，定义 A A 上的整除关系上的整除关系 ： 当旦仅当当旦仅当 a a 整除整除 b b 时，有时，有 。ba6 , 3 ,2, 1 的次序图如下的次序图如下 的次序图如下的次序图如下p6 61 13 36 62 22 23 31 14141若若L 是一个偏序集，则对于任意元素是一个偏序集，则对于任意元素 1 1, , 2, 2, 3 3 L L，有以下六个关系式成立：，有以下六个关系式成立： 11(5-)若若12，21，则则1=2(5-)若若12，23，则则13(5-)312注意注意 在偏序集在偏序集L 中，对任意元素中，对任意元素 1 1， 2

39、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)4242如果元素如果元素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).).aa a 2 2最大下界和最小上界最大下界

40、和最小上界定义定义5-115-11 设设 1 1和和 2 2是偏序集是偏序集L 中的两个元素中的两个元素, ,元素元素a La L，如果满足，如果满足a a 1 1,a,a 2 2 , ,则称则称a a是是 1 1和和 2 2的的下界下界。 定义定义5-125-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和和

41、 2 2的上界，便有的上界，便有b b，则称，则称 b b 是是1 1和和2 2的的最小上界最小上界，简记作，简记作b=lub(b=lub(1 1, , 2 2) )bbb4343lub(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 1 6 6，2 2 6 6，3 3 6 6，所以，所以glb(12,18)glb(12,1

42、8)6 6。 例例2 2 设设A= “A= “整除整除”关系是关系是A A上上的偏序关系，其次序图如下，因此，它们构成一个的偏序关系，其次序图如下，因此，它们构成一个偏序集偏序集A 。27,18,12, 9 , 6 , 3 , 2 , 11 11818121227272 23 36 69 94444试问试问 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）不存在。）

43、不存在。 例例3 3设设A=A=，整除关系是，整除关系是A A上上的偏序关系，其次序图如下的偏序关系，其次序图如下 36,12,18, 3 , 2 , 13618122314545 定理定理5-125-12 设和是偏序集设和是偏序集L的的两个元素，如果和有两个元素，如果和有glb,glb,则则glbglb是唯一的，是唯一的，如果和如果和 有有lublub，则，则lublub是唯一的。是唯一的。121212 证明证明设和都是和的设和都是和的glbglb， 1a2a21由定义由定义5-115-11，则，则 , , , ,于是有于是有= = 。1a2a1a2a1a2a 类似地可以证明类似地可以证明,

44、 , 和若存在和若存在lublub，则，则lublub也一定是唯一的。也一定是唯一的。1246463 3 最小元素和最大元素最小元素和最大元素 定义定义5-135-13 设设是一偏序集。是一偏序集。(1)如果存在元素如果存在元素aL，使得对于所有的元素，使得对于所有的元素L，有有a，则称，则称a是是的最小元素。的最小元素。(2)如果存在元素如果存在元素bL，使得对于所有的元素，使得对于所有的元素L，有有b，则称，则称b是是的最大元素。的最大元素。 定理定理5-135-13 如果偏序集如果偏序集L有最小元素，则最有最小元素，则最小元素是唯一的。如果小元素是唯一的。如果L有最大元素，则最大元有最大

45、元素，则最大元素也是唯一的。素也是唯一的。 证明证明 设设 和和 都是都是L的最小元素，则有的最小元素，则有 ，且，且 ，得，得 。 1a2a1a2a2a2a1a1a4747 若若L是一个格，则意味着是一个格，则意味着L也是一个形也是一个形为为L 的代数系统，其中的代数系统，其中 和和 是是L L上的两个二上的两个二元运算，对于任意元运算，对于任意 ， ， 表示在偏序表示在偏序“”意义下，意义下， 和和 的最小上界，的最小上界， 表示表示 和和 的最大的最大下界。下界。221121L2112 二、二、 格格 1 1格的定义格的定义 定义定义5-145-14 设设L是一个偏序集，如果是一个偏序集

46、，如果L L中中任意两个元素都存在着最大下界和最小上界，则称任意两个元素都存在着最大下界和最小上界，则称L是格。是格。12121 =glb=glb（ ， ），）， =lub=lub（ ， ）。）。1224848例例4 4 试判断下列次序图给出的偏序集哪些是格？试判断下列次序图给出的偏序集哪些是格？解解 （a a）不是格，）不是格， (b)(b)不是格，不是格， (c)(c)是一个格，是一个格， （d d）是一个格）是一个格 efdcab(a)(a)edbca(b)(b)fhgdebca(c)(c)51210153630(d)(d)4949)55(2132313)45(221121)45(221

47、121,55,llllllllllllllllllllllllll则则若若）（则则若若2132313。关系式代表了格的定义这十个、)()()()(55155515在格在格L L；中有如下四个关系式成立中有如下四个关系式成立: :5050 2 2格的性质格的性质 定理定理5-145-14 在格在格L中，对于任意中，对于任意以下三式中若任意一式成立，那么其它两式也成立以下三式中若任意一式成立，那么其它两式也成立. .L21,)()();()();()(12221121321llllllll证明证明 = = 设设 ， 121lll,452212llll又由自反性）有由（.55212lll ）于是由（

48、221221,)45(llllll故故由由反反对对称称性性有有由由另另一一方方面面，5151,221lll = = 设设 12,121)45(lllll即即由由 = = 设设 ,12ll ,11ll 由自反性,2111llll因此因此,55211lll）由（定定理理结结论论得得证证。故故由由反反对对称称性性.121lll,45121lll）由（5252 定义定义5-155-15 设设L是格，是格，P P是包是包含格的元素和符号含格的元素和符号= =、， ，的命的命题，将题，将P P中的中的、，和和分别替换成分别替换成、 、 和和所得的命题所得的命题P PD D称为称为P P的对偶。的对偶。 例

49、如例如 的对偶是的对偶是 33213321 对偶原理对偶原理 ： 对于格对于格L上的任上的任一真命题一真命题P P，其对偶，其对偶 P PD D 亦为格亦为格L上的真上的真命题。命题。 535312211221)()(llllblllla定理定理5-155-15（交换律）（交换律） 设设L是格，则对任意的是格，则对任意的有有: : Lll21,5454定理定理5-165-16 （结合律）（结合律）设设L是格，则对任意的是格，则对任意的 ，有Llll321,321321;321321)()()()()()(llllllblllllla,)45(332232,32,1llllllllala且由,3

50、,2lala由传递性,2121llalala）有有和和（又又由由55.,)(55321321balllalalla即即，）和和（和和由由. baab 。于是由反对称性得。于是由反对称性得类似的方法可以证明类似的方法可以证明,)(, )(321321lllblllaa令令）（证明证明5555定理定理5-175-17 （吸收律）（吸收律）设设L；是格，则对任意是格，则对任意，有，有Lll21 ,12111211)()(;)()(llllblllla证明证明 (b) (b) 由（由（5-45-4） )1 ()(1211llll另一方面，由（另一方面，由（5-15-1）2111145lllll)(,由

51、于是，由（于是，由（5-5）（2）)(2111llll 由（由（1)1)、(2(2）和反对称性）和反对称性.)(1211llll得5656 定理定理5-185-18 （等幂律）（等幂律） 设设L L；是格，则对任意是格，则对任意 ，有，有 Ll .)(;)(lllblllal 证明证明 （a a）由定理）由定理5-17 ,5-17 ,lll)(lll5757 定理定理5-195-19 （格的保序性）（格的保序性） 设设L L；是格，则对于任意是格，则对于任意 ，有，有Lllll4321,43214321, 42,3131213121,32,llllllllllllllllllllll则则）若若

52、（则则）若若（21 证明证明 （1 1）331131llllll 又已知又已知 2312335lllll)(.于是，由 31212131llllllll即），（55由由, ,和和432342) 1 (llllll有有，所以由，所以由因为因为4321llll由由传传递递性性，有有因为因为所以由所以由(1)有有31ll 2321llll5858 例例4 4 设设 L = L = ，L L上的整除关系上的整除关系 与与L L构成一个格，记作构成一个格，记作L， 126431,3( 6 4 ) = 3 1= 33( 6 4 ) = 3 1= 3 (36)(34) = 6 12 = 6(36)(34)

53、= 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)1264315959 定理定理5-205-20 设设L是格，则对任意是格，则对任意 , ,有有Llll321,)()()()()()()()(31213213121321lllllllbllllllla 证明证明 （a a）由）由(5-4)(5-4)有有332232llll, 于是，根据定理于是，根据定理5-195-19有有213

54、21lllll)(31321)(lllll又由（又由（5-45-4）有）有 )()()(3121321lllllll6060 3 3格的另一种定义方式格的另一种定义方式 定理定理5-215-21 设设L 是一个代数系统，其是一个代数系统，其中中和和都是二元运算，满足交换律，结合律和吸收律，都是二元运算，满足交换律，结合律和吸收律，则在则在L L上必存在一偏序关系，使得上必存在一偏序关系，使得L 是一个格。是一个格。 可以证明关系可以证明关系是是L L上的自反，反对称和可传递的上的自反，反对称和可传递的关系，因此关系，因此是是L L上的偏序关系。上的偏序关系。 在在L上定义二元关系：对任意上定义

55、二元关系：对任意当且仅当且仅当当时，有时，有。L,2112112 进一步还可以证明，对任意进一步还可以证明，对任意 ， 是在是在偏序关系偏序关系意义下意义下 1 1和和 2 2的最小上界，的最小上界， 1 2 1 2 是是 1 1和和 2 2的最大下界。的最大下界。 故故L 是一个格。是一个格。 L21 ,21 6161 格既可以看作是一个偏序集格既可以看作是一个偏序集L ，也可以看作是一个代数系统也可以看作是一个代数系统L 。 定义定义5-165-16 设设L 是一个代数系是一个代数系统，统， 和和 是是 L L 上的两个二元运算，如果这上的两个二元运算，如果这两个运算满足交换律，结合律和吸

56、收律，则两个运算满足交换律，结合律和吸收律，则称称L 是格。是格。 6262 例例5 5 在全集合在全集合 U U 的幂集的幂集 2 2U U = = 上的上的 包含关系包含关系“ ”“ ”是是 2 2U U 上的一偏序关系。上的一偏序关系。 USS| 因为对任意因为对任意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 S

57、j 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 是一偏序集。是一偏序集。6363因此因此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 是一个格是

58、一个格 另一方面，集合的并运算和交运算和另一方面，集合的并运算和交运算和2 2U U构成代数系统构成代数系统2 ，因为运算，因为运算和和都满足交换律，结合律都满足交换律，结合律 和吸收律，因此和吸收律，因此2是一个格。是一个格。 Ujiss2, 则必有则必有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， 6464例例6设设U=a,b,cU=a,b,c 则则2

59、 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.子格也是一个格。子格也是一个格。6565令令 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是是

60、2的子格。的子格。S也是也是2的子格。的子格。 S S3 3不能与这两个运算构成不能与这两个运算构成2的子格。的子格。a,b,ca,cb,ca,bacb6666261 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） 该偏序集的最小元素是该偏序集的最小元素是 ， 最大元素是最大元素是 。126432167673 43 4110（1）glb(6,9)=;gl