版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1 15.1 5.1 半群和独异点半群和独异点一、半群半群 定义定义5-1 设设S是一个非空集合,是一个非空集合, 是是S上的一个上的一个二元运算,如果二元运算,如果 是可是可 结结 合合 的的 , 则则 称称 代代 数数 系系 统统 是半群。是半群。;s 例例1 1 代数系统代数系统 N + 和和 N 、I+和和I 、R + 和和 R 都是半群,都是半群, 但但 和和 不是半群不是半群 . ; I/;0R例例2 代数系统代数系统和和都半群,都半群, 2 2 例例3 3 设设S=|是集合是集合A上的关系,对于关系的复上的关系,对于关系的复合运算合运算 可构成代数系统可构成代数系统 ,是半群是半
2、群.。 对任意对任意 aS ,定义,定义 a1=a (n=1,2,) aaann1)()(,mnnmnmnmaaaaa并且对于任意正整数并且对于任意正整数 m 和和 n ,有,有 若若F=f | f : A A,则对于函数的复合运,则对于函数的复合运算算 ,代数系统,代数系统也是半群。也是半群。 3 3在独异点在独异点中,对任意中,对任意a S,有有 a0=e ( )式中的两个等式在独异点中亦成立。式中的两个等式在独异点中亦成立。), 2 , 1 , 0(1naaann 二、独异点二、独异点 定义定义5-25-2 若半群若半群 中运算中运算* *有单位有单位元,则称元,则称 为独异点。为独异点
3、。; s; s 例例4 4 ,, ,和和、和和; 和和。例例3中的中的 和和4 4 例例6 6 对于半群对于半群 , N的子集的子集NnnN|22,|4,|343NnnNNnnN 都是都是的子半群。的子半群。 例例7 7 对于半群对于半群 的任一元素的任一元素 a S , 令集合令集合 , ,32aaaT 是是的子半群。的子半群。三、三、 子半群和子独异点子半群和子独异点 定义定义5-3 设设是一个半群是一个半群 ,若,若 是是的子代数,则称的子代数,则称是是的子半群。的子半群。5 5 定义定义5-45-4 设设是一独异点,若是一独异点,若是是的子代数,且单位元的子代数,且单位元 e T,则称
4、,则称是是的子独异点。的子独异点。 例例8 8 对于独异点对于独异点 , 子集子集N2,N3,N4, 它们均不能构成它们均不能构成的子独异点,的子独异点, 令令 ,|4,|3,|2432ZnnZZnnZZnnZ则则,都是都是 的子独异点。的子独异点。6 6Y YY YY YY YY YN N练习练习5-1 1判断下述论断正确与否,在相应的括号中键入判断下述论断正确与否,在相应的括号中键入“Y”或或“N”, (1)在实数集)在实数集R上定义二元运算上定义二元运算 为:对于任意的为:对于任意的 a,b R a* *b=a+b+ab (a) 是一个代数系统;是一个代数系统; ( ) (b) 是一个半
5、群;是一个半群; ( ) (c) 是一个独异点。是一个独异点。 ( )(2) 在实数集在实数集R上定义二元运算为,对任意上定义二元运算为,对任意 a, b R ,a b=|a|b(其中其中表示通常数的乘法运算表示通常数的乘法运算) (a) 是一个代数系统;是一个代数系统; ( ) (b) 是一个半群;是一个半群; ( ) (c) 是一个独异点。是一个独异点。 ( )7 75.2 5.2 群的定义群的定义一、群的定义一、群的定义 定义定义5-55-5 设设是一个代数系统,如果运算是一个代数系统,如果运算* *是可结合的,存在单位元是可结合的,存在单位元e,且,且G中任何元素中任何元素a都有逆都有
6、逆元元 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- 不是群。不是群。都是群。都是群。8 8 例例2 2
7、 设有设有Z Z4 4= =0,1,2,30,1,2,3,模,模4 4的加法运算的加法运算 定义为定义为 。构成代数。构成代数系统系统 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 29 9对于任意的对于任意的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)于是于是(a 4b) 4c= res4(a+
8、b) 4c=res4(res4(a+b)+c) = res4(4m1+res4(a+b)+c)=res4(a+b)+c) a 4(b 4c) = a 4res4(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满足结合律。满足结合律。1010二、循环群二、循环群 1
9、1群中元素的幂群中元素的幂 对于任意对于任意aG,a0=e, ( n = 0, 1 , 2, )aaann1(a-1)0=e, (n=0,1,2,) (*)1111)()(aaann引进记号引进记号 ( n个个a-1 )1111)( aaaaann因此(因此( )式可表示为)式可表示为),(*,)(2101101naaaeannmnnmnmnmaaaaa)(;*对于任意整数对于任意整数 和和n n,下面二式仍然成立。,下面二式仍然成立。m11)()(nnnaaa1111例如例如 32525aaaa因为因为 )()()(*1121525aaaaaaaaaaa3111111)()()()()()(
10、)()()(aaaaeaaaaaaaaaeaaaaaaaaaaaaaaaaaa又例如又例如632)( aa因为因为11112121231232)()()()()()()()(aaaaaaaaaaa661111111111111321111111)()()()()()()()()()(aaaaaaaaaaaaaaaaaaaeaaaaaaaa因因此此所所以以根根据据结结合合律律12122 2循环群循环群 定义定义5-65-6 在群在群中,如果存在一元素中,如果存在一元素g G,使,使得每一元素得每一元素 a G 都能表示成都能表示成 g i ( i I)的形式,则称群的形式,则称群 为循环群,称为
11、循环群,称 g 为该循环群的生成元,并称群为该循环群的生成元,并称群 由由 g 生成。生成。按照群中逆元的表示方法按照群中逆元的表示方法nnn1)1 (1111111例例3 3 群群是循环群,是循环群,1是生成元,是生成元,10=0,对任意正,对任意正整数整数n,n=1+1+1,按照群中元素的幂的表示方法,按照群中元素的幂的表示方法n=1n.)()()(,111nn对任意负整数对任意负整数 ,1313 例例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
12、 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也是其生成元。也是其生成元。1414 例例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
13、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是一阿贝尔群,但它不是循环群,一般称这是一阿贝尔群,但它不是循环群,一般称这个群为个群为Klein四元群。四元群。1515三、群的阶和元素的周期三、群的阶和元素的周期 定义定义5-75-7 设设G 是一个群,如果是一个群,如果G G是有限集,则是有限集,则称称G 是有限群,是有限群,G G中元素的个数称为群中元素的个数称为群G 的阶;的阶;若若G G是
14、无限集,则称是无限集,则称G 是无限群。是无限群。 定义定义5-85-8 设设G; 是一个群,是一个群,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 的周期为的周期为无限。无限。1616例例6 6 在群在群 中,单位元中,单位元1的周期为的周期为1。 (- -1)2=(- -1)4=(- -1)6=
15、 =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 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 , 1717定理定理5-15-1 设设是一由元素是一由元素 g 生成的循环群,则生成的循环群,则 (1)若)若 g
16、的周期为的周期为 n ,则,则是一个阶为是一个阶为 n 的有的有限循环群;限循环群; (2)若)若 g 的周期为无限,则的周期为无限,则是一个无限阶的是一个无限阶的循环群。循环群。例如例如 循环群循环群I+的生成元的生成元1 1和和11,其周期均为无,其周期均为无限,群限,群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和和
17、3 3的周期均为的周期均为4 4,循环群,循环群Z 的阶也为的阶也为4 4。1818练习练习5-25-21设有集合设有集合A= 是函数的复合运算,判断是函数的复合运算,判断下述各论断是否正确,在相应的括号中键入下述各论断是否正确,在相应的括号中键入“Y”或或“N” (1)令)令FA 是一个群是一个群. ,dcba ;,:|AFAAff则 ( )(2 2)令)令E EA A = =.是一个群则是双射 ;,:|AEAAff ( )(3)EA定义同上,定义同上,是交换群。是交换群。 ( ) (4 (4) E EA A定义同上,定义同上,E 是循环群。是循环群。 ( )N NN NN NY Y1919
18、5 53 3 群的性质群的性质一、关于相约性一、关于相约性 定理定理5-2 设设是一个群,则对任意的是一个群,则对任意的a,b G, (1)存在唯一的元素)存在唯一的元素xG,使,使a* *x=b; (2)存在唯一的元素)存在唯一的元素yG,使,使y* *a=b。 证明证明(1)因为)因为a,b G ,所以所以 。令。令Gba1bax1 假设假设 也使得也使得 成立,则成立,则 bxaGx 因此因此 是满足是满足 的唯一的元素。的唯一的元素。bax1bxa xxe)(1xaaba 1 则则 , 因此因此 , 是方程是方程 的解的解bbebaabaa)()(11ba1bxaxaa)(12020
19、定理定理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,根据定理,根据定理5-25-2,方程方程a a* *x = d x = d 在在G G中只有唯一的解,故得中只有唯一的解,故得b=cb=c。2121二、元素运算后求逆元等于元素分别求逆元后颠二、元素运算后求逆元等于元素分别求逆元后颠倒次序相运算倒次序相运算 定理定理5-45
20、-4 设设G 是一个群,则对任意是一个群,则对任意a,b G a,b G ,有有111abba)( 证明证明 因为因为(a b) * * (a b) = e1)()(11abba又又)()()()()(111111abbababaeaaabba,因因此此根据定理根据定理5-35-3,有,有111abba)(对对 任意任意 有有11111121)(aaaaaannn,21Gaaan2222三、关于元素的周期三、关于元素的周期 定理定理5-55-5 群群G 中的元素中的元素 a a 若具有有限周期若具有有限周期 r r,则,则当且仅当当且仅当 k k 是是 r r 的整数倍时的整数倍时 ,a ak
21、 k = e = e 。定理定理5-65-6 群中任一元素与它的逆元具有相同的周期。群中任一元素与它的逆元具有相同的周期。 定理定理5-75-7 在有限群在有限群G 中,每个元素均具有有限周中,每个元素均具有有限周期,且周期不超过群期,且周期不超过群G 的阶。的阶。 证明证明 设设G 是有限群,是有限群,#G = n#G = n,对任意,对任意a a G G,构造序列构造序列a,aa,a2 2,a,a3 3,a,an n,a,an+1n+1, , 因为因为#G=n,所以序列中必存在所以序列中必存在ai=aj. )(11nji于是于是 因此因此 a a 的周期至多为的周期至多为 , ,而而 。G
22、ijij得)0(nijeaaaaaijijii2323定理定理5-7的结论对于无限群不成立。的结论对于无限群不成立。例如群例如群 . 例例1 1 对于对于5.25.2节例节例2 2中的群中的群Z , 单位元单位元0的周期是的周期是1;1和和3的周期均为的周期均为4;2的周期为的周期为2,群群的阶的阶4. 例例2 2 设设 是一个群,且对于任意的是一个群,且对于任意的a,b G,有(有(a * * b)2=a2 * * b2 , 则则 是阿贝尔群,是阿贝尔群, 由已知(由已知(a b)=a2 b2(a * * b) * *(a * * b)=(a * * a) * *(b * * b)a a*
23、*(b(b* *a)a)* *b = ab = a* *(a(a* *b)b)* *b b利用定理利用定理5-3的相约性得的相约性得 b* *a = a* *b 2424 练习练习 5-35-31填空填空 设设Z6 = , 6 是模是模6的加法,定义为:的加法,定义为: a 6b = res6(a+b),是一个群。是一个群。 (1)群)群 的单位元是的单位元是 。 (2)1的逆元是的逆元是 ;2的逆元是的逆元是 ;3的逆元是的逆元是 。 (3)1的周期是的周期是 ,1与与 的周期相同。的周期相同。 (4)2的周期是的周期是 ,2与与 的周期相同。的周期相同。5 , 4 , 3 , 2 , 1
24、, 0 N Y2判断下述论断正确与否,在相应的括号中键入判断下述论断正确与否,在相应的括号中键入“Y” 或或“N” 设设 是群,是群,a,b G , 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 ( ) ( ) ( ) ( ) ( ) ( ) N Y N0 05 54 43 36 65 53 34 4N Y NY Y Y2525 半群,独异点和群这三个概念之间的区别:半群半群,独异点和群这三个概念之间的区别
25、:半群N+,独异点独异点Z+,群,群I+。 若若是是的子群,则的子群,则也是群也是群. 5 54 4 子群及其判别子群及其判别一、子群的定义一、子群的定义定义定义5-95-9 设设是一个群,若是一个群,若是是的子代数,单位元的子代数,单位元e H,且对于任意的,且对于任意的a H,有有a-1 H,则称,则称是是的子群。的子群。 e ea a G G1aH H2626 I+既是半群、独异点,也是一个群,既是半群、独异点,也是一个群,对于对于 I I 的三个子集:的三个子集: E E1 1= =IiiEZzzENnn|,|,22232E+只能看作是只能看作是I +的子半群,的子半群, E+只能看作
26、是只能看作是I +的子独异点,的子独异点, 只有只有 E+才是才是I+的子群。的子群。 对于任意的整数对于任意的整数m,若令,若令Im= .则则均可构成均可构成的子群。的子群。 Iiim|2727 例例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 ee a b ce a b c, ae,,
27、be, ce,。和和2828二、子群的判别二、子群的判别 要判断要判断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 a* *bHbH; (2)(2)
28、对任意的对任意的aHaH,有,有 HH, 则则H; 是是G 的子群。的子群。1a2929 定理定理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 的子群。的子群。Hba11)(3030 解解 显然显
29、然H是是G的非空子集。的非空子集。例例2 2 设设G 是一个群,是一个群,a a是是 G G中任一元素,令中任一元素,令 即即H H是是a a的所有整数次幂的集合,问的所有整数次幂的集合,问H H对于运算对于运算能否构成能否构成G 的子群?的子群? ,320123aaaaaaaIiaHi (1)对任意)对任意ai,aj H,有,有ai aj=ai+j 因为因为i+j I,所以所以ai+j H;i(2)对任意对任意 ai H , 有有a ai=ai a =a0=e,即即a 是是 ai 的逆元,的逆元,ii 又由又由H的定义的定义a H 于是根据定理于是根据定理5-8,是是的子群。的子群。 显然显
30、然是由元素是由元素a生成的一个循环群生成的一个循环群.i3131例例3 3 设设是一个群,定义是一个群,定义G的子集的子集H为为 H= 试问试问H对于运算能否构成对于运算能否构成的子群。的子群。axxaGxa,对对于于任任意意解:解: 对任意对任意 x G,有,有x e = e x = x , 所以所以e H, 故故H是是G的非空子集。的非空子集。 任取任取a , b H,则对任意则对任意x G必有必有a x = x a,b x = x b ,于是根据群的性质,于是根据群的性质)()(xbaxba1111)(bxa11 )(xba)(1bxa)()()(111baxbaxbxa 因此因此a b
31、 Ha b H,根据定理,根据定理5-9, H5-9, 是是G 的子群。的子群。 13232 定理定理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 的子群。的子群。 其中其中ar 1 =ar * * a 1 =e * * a 1 =a,因此,因此a1H,故,故是是的子群。
32、的子群。 又因为运算又因为运算 在在 H H 上封闭,所以元素上封闭,所以元素 a,aa,a2 2,a,a3 3,a ar -1r -1,a,ar r(=e)(=e)均在均在 H H 中,中, 3333 例例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),作出
33、作出 群群Z 的运算表如下:的运算表如下:65 5 5 50 01 12 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 53434三、子群的等价定义三、子群的等价定义 如前所述,若如前所述,若是群是群的子群,则的子群,则自身也必是群。自身也必是群。 反之,设反之,设G 是一个群,是一个群,H H 是是 G G的非空子集,若的非空子集,若H 也是群,则也是群,则H 必是必是G
34、的子群。的子群。 证明如下:证明如下: * *在在H H上是封闭的,所以上是封闭的,所以H 是是G 的子代数。的子代数。 又设又设 是群是群H 的单位元,的单位元,e e为群为群G 的单位元。的单位元。 e 则有则有 = , e = ,于是,于是 = e ,由群的相约性,得由群的相约性,得 e = ,因此,因此 e H。eeeeeeeee 又对任又对任 a H, 表示表示a在在中的逆元,中的逆元,a 表表示示a在在中的逆元,中的逆元,a1 根据定义根据定义5-9,是群是群的子群。的子群。a于是有于是有a = e =a a 。由相约性,得。由相约性,得 =a,因此,因此a H。1a13535 定
35、义定义5-95-9 设设G 是一个群,是一个群,H H是是G G的非空子集,的非空子集,若若H 也是群,则称也是群,则称H 是是G 的子群。的子群。练习练习5-41 1判断下述论断正确与否,在相应的括号中键入判断下述论断正确与否,在相应的括号中键入“Y”Y”或或“N”N”。 对于群对于群Z 有如下子群。有如下子群。)()()()()()(;3 , 2 , 1 , 0,;3 , 1 , 0,;3 , 0,;2 , 0,;1 , 0,;0444444YNYNNY36363737 5.55.5格格一偏序集一偏序集1 1。偏序集。偏序集 定义定义5-105-10 集合集合L L和定义在和定义在 L L
36、 上的偏序关系上的偏序关系 “ “” ” 一起称为偏序集,用一起称为偏序集,用L 表示。表示。 若若 是集合是集合A上的偏序关系,则上的偏序关系,则 的逆关系的逆关系也必是上的偏序关系,证明如下:也必是上的偏序关系,证明如下: R,I,2 和和N|都是偏都是偏序集。序集。3838对任意的对任意的 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
37、 = 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) ,因此,因此 是可传递的。是可传递的。 由上证得由上证得 也是偏序关系。也是偏序关系。 3939根据逆关系的定义根据逆关系的定义 = = )6 , 6(),3 , 6(),3 , 3(),2 , 6(),2 , 2)(1 , 6(),1 , 3(),1 , 2(),1 , 1 (p 由定义由定义 = = ) 6 , 6(),6 ,
38、 3 (),3 , 3 (),6 , 2(),2 , 2)(6 , 1 (),3 , 1 (),2 , 1 (),1 , 1 ( 例例1 1 设设 A= A= ,定义,定义 A A 上的整除关系上的整除关系 : 当旦仅当当旦仅当 a a 整除整除 b b 时,有时,有 。ba6 , 3 ,2, 1 的次序图如下的次序图如下 的次序图如下的次序图如下p6 61 13 36 62 22 23 31 14040若若L 是一个偏序集,则对于任意元素是一个偏序集,则对于任意元素 1 1, , 2, 2, 3 3 L L,有以下六个关系式成立:,有以下六个关系式成立: 1 1 (5- ) 若若 1 2 ,
39、 2 1,则则 1= 2 (5- ) 若若 1 2 , 2 3,则则 1 3 (5- )312注意注意 在偏序集在偏序集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 。 1 1 (5-1) 若若 1 2 , 2 1,则则 1= 2 (5-2) 若若 1 2 , 2 3,则则 1 3 (5-3)4141如果元素如果元素a a是是 1 1和和 2 2的下界。且对于任意的下界。且对于任意 L L,若,若也是也是 1 1和和 2 2
40、的下界,便有的下界,便有 a ,a ,则称则称a a是是 1 1和和 2 2的的最大下界最大下界,简记作,简记作a=glb(a=glb(1 1 , , 2 2).).aa a 2 2最大下界和最小上界最大下界和最小上界定义定义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
41、 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) )bbb4242lub(2,3)=lub(2,3)=?,?,glb(12,18)=?glb(12,18)=?,lub(18,27)=?lub(18,27)=?有有2 6,3 6;2 12,3 12;2 18,3 18。 由于由于
42、6 12,6 18,6 6,因此,因此,lub(2,3)=6。 6 12,6 18;2 12,2 18;3 12,3 18;1 12,1 18; 因因1 1 6 6,2 2 6 6,3 3 6 6,所以,所以glb(12,18)glb(12,18)6 6。 例例2 2 设设A= “A= “整除整除”关系是关系是A A上上的偏序关系,其次序图如下,因此,它们构成一个的偏序关系,其次序图如下,因此,它们构成一个偏序集偏序集A 。27,18,12, 9 , 6 , 3 , 2 , 11 11818121227272 23 36 69 94343 试问试问 glb(18,12)=?, lub(2,3)
43、=? 218,2 12;3 18,3 12,1 18,1 12。 但但glb(18,12)glb(18,12)不存在。不存在。 类似地,类似地,1212,1818和和3636均是均是2 2和和3 3的上界,的上界,但但 lublub(2 2,3 3)不存在。)不存在。 例例3 3设设A=A=,整除关系是,整除关系是A A上上的偏序关系,其次序图如下的偏序关系,其次序图如下 36,12,18, 3 , 2 , 13618122314444 定理定理5-125-12 设和是偏序集设和是偏序集L的的两个元素,如果和有两个元素,如果和有glb,glb,则则glbglb是唯一的,是唯一的,如果和如果和
44、有有lublub,则,则lublub是唯一的。是唯一的。121212 证明证明设和都是和的设和都是和的glbglb, 1a2a21由定义由定义5-115-11,则,则 , , , ,于是有于是有= = 。1a2a1a2a1a2a 类似地可以证明类似地可以证明, , 和若存在和若存在lublub,则,则lublub也一定是唯一的。也一定是唯一的。1245453 3 最小元素和最大元素最小元素和最大元素 定义定义5-135-13 设设是一偏序集。是一偏序集。 (1) 如果存在元素如果存在元素a L,使得对于所有的元素,使得对于所有的元素 L,有有a ,则称,则称a是是的最小元素。的最小元素。 (2
45、) 如果存在元素如果存在元素b L,使得对于所有的元素,使得对于所有的元素 L,有有 b,则称,则称b是是的最大元素。的最大元素。 定理定理5-135-13 如果偏序集如果偏序集L有最小元素,则最有最小元素,则最小元素是唯一的。如果小元素是唯一的。如果L有最大元素,则最大元有最大元素,则最大元素也是唯一的。素也是唯一的。 证明证明 设设 和和 都是都是L的最小元素,则有的最小元素,则有 ,且,且 ,得,得 。 1a2a1a2a2a2a1a1a4646 若若L是一个格,则意味着是一个格,则意味着L也是一个形也是一个形为为L 的代数系统,其中的代数系统,其中 和和 是是L L上的两个二上的两个二元
46、运算,对于任意元运算,对于任意 , , 表示在偏序表示在偏序“”意义下,意义下, 和和 的最小上界,的最小上界, 表示表示 和和 的最大的最大下界。下界。221121L2112 二、二、 格格 1 1格的定义格的定义 定义定义5-145-14 设设L是一个偏序集,如果是一个偏序集,如果L L中中任意两个元素都存在着最大下界和最小上界,则称任意两个元素都存在着最大下界和最小上界,则称L是格。是格。12121 =glb=glb( , ),), =lub=lub( , )。)。1224747例例4 4 试判断下列次序图给出的偏序集哪些是格?试判断下列次序图给出的偏序集哪些是格?解解 (a a)不是格
47、,)不是格, (b)(b)不是格,不是格, (c)(c)是一个格,是一个格, (d d)是一个格)是一个格 efdcab(a)(a)edbca(b)(b)fhgdebca(c)(c)51210153630(d)(d)4848)55(2132313)45(221121)45(221121,55,llllllllllllllllllllllllll则则若若)(则则若若2132313。关系式代表了格的定义这十个、)()()()(55155515在格在格L L;中有如下四个关系式成立中有如下四个关系式成立: :4949 2 2格的性质格的性质 定理定理5-145-14 在格在格L中,对于任意中,对于任
48、意以下三式中若任意一式成立,那么其它两式也成立以下三式中若任意一式成立,那么其它两式也成立. .L21,)()();()();()(12221121321llllllll证明证明 = = 设设 , 121lll,452212llll又由自反性)有由(.55212lll )于是由(221221,)45(llllll故故由由反反对对称称性性有有由由另另一一方方面面,5050,221lll = = 设设 12,121)45(lllll即即由由 = = 设设 ,12ll ,11ll 由自反性,2111llll因此因此,55211lll)由(定定理理结结论论得得证证。故故由由反反对对称称性性.121ll
49、l,45121lll)由(5151 定义定义5-155-15 设设L是格,是格,P P是包是包含格的元素和符号含格的元素和符号= =、, ,的命的命题,将题,将P P中的中的、,和和分别替换成分别替换成、 、 和和所得的命题所得的命题P PD D称为称为P P的对偶。的对偶。 例如例如 的对偶是的对偶是 33213321 对偶原理对偶原理 : 对于格对于格L上的任上的任一真命题一真命题P P,其对偶,其对偶 P PD D 亦为格亦为格L上的真上的真命题。命题。 525212211221)()(llllblllla定理定理5-155-15(交换律)(交换律) 设设L是格,则对任意的是格,则对任意
50、的有有: : Lll21,5353定理定理5-165-16 (结合律)(结合律) 设设L是格,则对任意的是格,则对任意的 ,有Llll321,321321;321321)()()()()()(llllllblllllla,)45(332232,32,1llllllllala且由,3,2lala由传递性,2121llalala)有有和和(又又由由55.,)(55321321balllalalla即即,)和和(和和由由. baab 。于是由反对称性得。于是由反对称性得类似的方法可以证明类似的方法可以证明,)(, )(321321lllblllaa令令)(证明证明5454定理定理5-175-17 (
51、吸收律)(吸收律)设设L;是格,则对任意是格,则对任意 ,有,有 Lll21 ,12111211)()(;)()(llllblllla证明证明 (b) (b) 由(由(5-45-4) )1 ()(1211llll另一方面,由(另一方面,由(5-15-1)2111145lllll)(,由于是,由(于是,由(5-5) (2))(2111llll 由(由(1)1)、(2(2)和反对称性)和反对称性.)(1211llll得5555 定理定理5-185-18 (等幂律)(等幂律) 设设L L;是格,则对任意是格,则对任意 ,有,有 Ll .)(;)(lllblllal 证明证明 (a a)由定理)由定理
52、5-17 ,5-17 ,lll)(lll5656 定理定理5-195-19 (格的保序性)(格的保序性) 设设L L;是格,则对于任意是格,则对于任意 ,有,有Lllll4321,43214321, 42,3131213121,32,llllllllllllllllllllll则则)若若(则则)若若(21 证明证明 (1 1)331131llllll 又已知又已知 2312335lllll)(.于是,由 31212131llllllll即),(55由由, ,和和432342) 1 (llllll有有,所以由,所以由因为因为4321llll由由传传递递性性,有有因为因为 所以由所以由(1)有有3
53、1ll 2321llll5757 例例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) = 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)1264315858 定理定理5-205-
54、20 设设L是格,则对任意是格,则对任意 , ,有有Llll321,)()()()()()()()(31213213121321lllllllbllllllla 证明证明 (a a)由)由(5-4)(5-4)有有332232llll, 于是,根据定理于是,根据定理5-195-19有有21321lllll)(31321)(lllll又由(又由(5-45-4)有)有 )()()(3121321lllllll5959 3 3格的另一种定义方式格的另一种定义方式 定理定理5-215-21 设设L 是一个代数系统,其是一个代数系统,其中中和和都是二元运算,满足交换律,结合律和吸收律,都是二元运算,满足交
55、换律,结合律和吸收律,则在则在L L上必存在一偏序关系,使得上必存在一偏序关系,使得L 是一个格。是一个格。 可以证明关系可以证明关系是是L L上的自反,反对称和可传递的上的自反,反对称和可传递的关系,因此关系,因此是是L L上的偏序关系。上的偏序关系。 在在L上定义二元关系:对任意上定义二元关系:对任意 当且仅当且仅当当 时,有时,有 。L,2112112 进一步还可以证明,对任意进一步还可以证明,对任意 , 是在是在偏序关系偏序关系意义下意义下 1 1和和 2 2的最小上界,的最小上界, 1 2 1 2 是是 1 1和和 2 2的最大下界。的最大下界。 故故L 是一个格。是一个格。 L21
56、 ,21 6060 格既可以看作是一个偏序集格既可以看作是一个偏序集L ,也可以看作是一个代数系统也可以看作是一个代数系统L 。 定义定义5-165-16 设设L 是一个代数系是一个代数系统,统, 和和 是是 L L 上的两个二元运算,如果这上的两个二元运算,如果这两个运算满足交换律,结合律和吸收律,则两个运算满足交换律,结合律和吸收律,则称称L 是格。是格。 6161 例例5 5 在全集合在全集合 U U 的幂集的幂集 2 2U U = = 上的上的 包含关系包含关系“ ”“ ”是是 2 2U U 上的一偏序关系。上的一偏序关系。 USS| 因为对任意因为对任意Si 2U,总有,总有Si S
57、i,所以,所以 是自反的。是自反的。对任意对任意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 是一偏序集。是一偏序集。6262因此因此S Si iSSj j是是S Si i和和S Sj j的上界。的
58、上界。 对于任意对于任意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是一个格。是一个格。 Ujiss2, 则必有则必有S Si iSSj j S S。因此。因
59、此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, 6363 例例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 对应的代数系统形式的格是对应
60、的代数系统形式的格是2.子格也是一个格。子格也是一个格。6464令令 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,bacb65652 6 1 112 12 练习练习5-55-51 1 设设 L = 1L = 1,2 2,3 3,4 4,6 6,1212,在,在L
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年度桥梁栏杆采购合同模板6篇
- 2025年度口腔诊所投资合作与风险分担合同3篇
- 二零二五版材料采购合同补充协议:技术创新共享2篇
- 二零二五版抵押借款合同与借款合同签订流程与风险防范3篇
- 二零二五版国有房产出售合同(智慧社区共建协议)3篇
- 2025年度餐饮业中央厨房租赁合同3篇
- 二零二五年度35KV变电站电气设备技术改造合同3篇
- 二零二五年房地产项目乡村振兴战略合作开发合同3篇
- 二零二五版班组分包道路养护合同3篇
- 2025版金融产品股权及债权转让与风险管理合同3篇
- 公务员考试工信部面试真题及解析
- GB/T 15593-2020输血(液)器具用聚氯乙烯塑料
- 2023年上海英语高考卷及答案完整版
- 西北农林科技大学高等数学期末考试试卷(含答案)
- 金红叶纸业简介-2 -纸品及产品知识
- 《连锁经营管理》课程教学大纲
- 《毕淑敏文集》电子书
- 颈椎JOA评分 表格
- 员工岗位能力评价标准
- 定量分析方法-课件
- 朱曦编著设计形态知识点
评论
0/150
提交评论