離散數(shù)學-幾種典型的代數(shù)系統(tǒng)

1、1 15.1 5.1 半群和獨異點半群和獨異點一、半群半群 定義定義5-1 設設S是一個非空集合，是一個非空集合， 是是S上的一個上的一個二元運算，如果二元運算，如果 是可是可 結結 合合 的的 , 則則 稱稱 代代 數(shù)數(shù) 系系 統(tǒng)統(tǒng) 是半群。是半群。;s 例例1 1 代數(shù)系統(tǒng)代數(shù)系統(tǒng) N + 和和 N 、I+和和I 、R + 和和 R 都是半群，都是半群， 但但 和和 不是半群不是半群 . ; I/;0R例例2 代數(shù)系統(tǒng)代數(shù)系統(tǒng)和和都半群，都半群， 2 2 例例3 3 設設S=|是集合是集合A上的關系，對于關系的復上的關系，對于關系的復合運算合運算 可構成代數(shù)系統(tǒng)可構成代數(shù)系統(tǒng) ，是半群是半

2、群.。 對任意對任意 aS ，定義，定義 a1=a (n=1,2,) aaann1)()(,mnnmnmnmaaaaa并且對于任意正整數(shù)并且對于任意正整數(shù) m 和和 n ，有，有 若若F=f | f : A A，則對于函數(shù)的復合運，則對于函數(shù)的復合運算算 ，代數(shù)系統(tǒng)，代數(shù)系統(tǒng)也是半群。也是半群。 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 設設是一個半群是一個半群 ，若，若 是是的子代數(shù)，則稱的子代數(shù)，則稱是是的子半群。的子半群。5 5 定義定義5-45-4 設設是一獨異點，若是一獨異點，若是是的子代數(shù)，且單位元的子代數(shù)，且單位元 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）在實數(shù)集）在實數(shù)集R上定義二元運算上定義二元運算 為：對于任意的為：對于任意的 a,b R a* *b=a+b+ab (a) 是一個代數(shù)系統(tǒng)；是一個代數(shù)系統(tǒng)； （ ） (b) 是一個半

5、群；是一個半群； （ ） （c） 是一個獨異點。是一個獨異點。 （ ）(2) 在實數(shù)集在實數(shù)集R上定義二元運算為，對任意上定義二元運算為，對任意 a, b R ，a b=|a|b(其中其中表示通常數(shù)的乘法運算表示通常數(shù)的乘法運算) （a） 是一個代數(shù)系統(tǒng)；是一個代數(shù)系統(tǒng)； （ ） (b) 是一個半群；是一個半群； （ ） (c) 是一個獨異點。是一個獨異點。 （ ）7 75.2 5.2 群的定義群的定義一、群的定義一、群的定義 定義定義5-55-5 設設是一個代數(shù)系統(tǒng)，如果運算是一個代數(shù)系統(tǒng)，如果運算* *是可結合的，存在單位元是可結合的，存在單位元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的加法運算的加法運算 定義為定義為 。構成代數(shù)。構成代數(shù)系統(tǒng)系統(tǒng) 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二、循環(huán)群二、循環(huán)群 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)(;*對于任意整數(shù)對于任意整數(shù) 和和n n，下面二式仍然成立。，下面二式仍然成立。m11)()(nnnaaa1111例如例如 32525aaaa因為因為 )()()(*1121525aaaaaaaaaaa3111111)()()()()()(

10、)()()(aaaaeaaaaaaaaaeaaaaaaaaaaaaaaaaaa又例如又例如632)( aa因為因為11112121231232)()()()()()()()(aaaaaaaaaaa661111111111111321111111)()()()()()()()()()(aaaaaaaaaaaaaaaaaaaeaaaaaaaa因因此此所所以以根根據(jù)據(jù)結結合合律律12122 2循環(huán)群循環(huán)群 定義定義5-65-6 在群在群中，如果存在一元素中，如果存在一元素g G，使，使得每一元素得每一元素 a G 都能表示成都能表示成 g i ( i I)的形式，則稱群的形式，則稱群 為循環(huán)群，稱為

11、循環(huán)群，稱 g 為該循環(huán)群的生成元，并稱群為該循環(huán)群的生成元，并稱群 由由 g 生成。生成。按照群中逆元的表示方法按照群中逆元的表示方法nnn1)1 (1111111例例3 3 群群是循環(huán)群，是循環(huán)群，1是生成元，是生成元，10=0，對任意正，對任意正整數(shù)整數(shù)n，n=1+1+1，按照群中元素的冪的表示方法，按照群中元素的冪的表示方法n=1n.)()()(,111nn對任意負整數(shù)對任意負整數(shù) ,1313 例例4 4 例例2 2中的群中的群Z 是循環(huán)群，是循環(huán)群， 因為因為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是一阿貝爾群，但它不是循環(huán)群，一般稱這是一阿貝爾群，但它不是循環(huán)群，一般稱這個群為個群為Klein四元群。四元群。1515三、群的階和元素的周期三、群的階和元素的周期 定義定義5-75-7 設設G 是一個群，如果是一個群，如果G G是有限集，則是有限集，則稱稱G 是有限群，是有限群，G G中元素的個數(shù)稱為群中元素的個數(shù)稱為群G 的階；的階；若若G G是

14、無限集，則稱是無限集，則稱G 是無限群。是無限群。 定義定義5-85-8 設設G; 是一個群，是一個群，a Ga G，若存在，若存在正整數(shù)正整數(shù) r r ，使得，使得 a ar r =e=e，則稱元素，則稱元素 a a 具有有限周期。具有有限周期。使使a ar r=e=e成立的最小的正整數(shù)成立的最小的正整數(shù) r r 稱為稱為 a a 的周期。如果的周期。如果對于任何正整數(shù)對于任何正整數(shù)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 生成的循環(huán)群，則生成的循環(huán)群，則 （1）若）若 g

16、的周期為的周期為 n ，則，則是一個階為是一個階為 n 的有的有限循環(huán)群；限循環(huán)群； （2）若）若 g 的周期為無限，則的周期為無限，則是一個無限階的是一個無限階的循環(huán)群。循環(huán)群。例如例如 循環(huán)群循環(huán)群I+的生成元的生成元1 1和和11，其周期均為無，其周期均為無限，群限，群I+是一個無限階的循環(huán)群。是一個無限階的循環(huán)群。 循環(huán)群循環(huán)群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，循環(huán)群，循環(huán)群Z 的階也為的階也為4 4。1818練習練習5-25-21設有集合設有集合A= 是函數(shù)的復合運算，判斷是函數(shù)的復合運算，判斷下述各論斷是否正確，在相應的括號中鍵入下述各論斷是否正確，在相應的括號中鍵入“Y”或或“N” （1）令）令FA 是一個群是一個群. ,dcba ;,:|AFAAff則 ( )（2 2）令）令E EA A = =.是一個群則是雙射 ;,:|AEAAff ( )（3）EA定義同上，定義同上，是交換群。是交換群。 ( ) (4 (4） E EA A定義同上，定義同上，E 是循環(huán)群。是循環(huán)群。 ( )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，根據(jù)定理，根據(jù)定理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，因因此此根據(jù)定理根據(jù)定理5-35-3，有，有111abba)(對對 任意任意 有有11111121)(aaaaaannn,21Gaaan2222三、關于元素的周期三、關于元素的周期 定理定理5-55-5 群群G 中的元素中的元素 a a 若具有有限周期若具有有限周期 r r，則，則當且僅當當且僅當 k k 是是 r r 的整數(shù)倍時的整數(shù)倍時 ，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節(jié)例節(jié)例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 半群，獨異點和群這三個概念之間的區(qū)別：半群半群，獨異點和群這三個概念之間的區(qū)別

25、：半群N+，獨異點獨異點Z+，群，群I+。 若若是是的子群，則的子群，則也是群也是群. 5 54 4 子群及其判別子群及其判別一、子群的定義一、子群的定義定義定義5-95-9 設設是一個群，若是一個群，若是是的子代數(shù)，單位元的子代數(shù)，單位元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+的子群。的子群。 對于任意的整數(shù)對于任意的整數(shù)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 , 于是根據(jù)定理于是根據(jù)定理5-85-8，H 是是 G 的子群。的子群。Hba11)(3030 解解 顯然顯

29、然H是是G的非空子集。的非空子集。例例2 2 設設G 是一個群，是一個群，a a是是 G G中任一元素，令中任一元素，令 即即H H是是a a的所有整數(shù)次冪的集合，問的所有整數(shù)次冪的集合，問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 于是根據(jù)定理于是根據(jù)定理5-8，是是的子群。的子群。 顯然顯

30、然是由元素是由元素a生成的一個循環(huán)群生成的一個循環(huán)群.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 ，于是根據(jù)群的性質，于是根據(jù)群的性質)()(xbaxba1111)(bxa11 )(xba)(1bxa)()()(111baxbaxbxa 因此因此a b

31、 Ha b H，根據(jù)定理，根據(jù)定理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 的子代數(shù)，則的子代數(shù)，則H 是是G 的子群。的子群。 定理定理5-115-11 設設G 是一個群，若是一個群，若H 是是G 的的有限子代數(shù)，則有限子代數(shù)，則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 的子代數(shù)。的子代數(shù)。 又設又設 是群是群H 的單位元，的單位元，e e為群為群G 的單位元。的單位元。 e 則有則有 = , e = ，于是，于是 = e ,由群的相約性，得由群的相約性，得 e = ，因此，因此 e H。eeeeeeeee 又對任又對任 a H， 表示表示a在在中的逆元，中的逆元，a 表表示示a在在中的逆元，中的逆元，a1 根據(jù)定義根據(jù)定義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根據(jù)逆關系的定義根據(jù)逆關系的定義 = = )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 上的整除關系上的整除關系 ： 當?shù)﹥H當當?shù)﹥H當 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、有有l(wèi)ublub，則，則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 的代數(shù)系統(tǒng)，其中的代數(shù)系統(tǒng)，其中 和和 是是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, 于是，根據(jù)定理于是，根據(jù)定理5-195-19有有21321lllll)(31321)(lllll又由（又由（5-45-4）有）有 )()()(3121321lllllll5959 3 3格的另一種定義方式格的另一種定義方式 定理定理5-215-21 設設L 是一個代數(shù)系統(tǒng)，其是一個代數(shù)系統(tǒng)，其中中和和都是二元運算，滿足交換律，結合律和吸收律，都是二元運算，滿足交

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 ，也可以看作是一個代數(shù)系統(tǒng)也可以看作是一個代數(shù)系統(tǒng)L 。 定義定義5-165-16 設設L 是一個代數(shù)系是一個代數(shù)系統(tǒng)，統(tǒng)， 和和 是是 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構成代數(shù)系統(tǒng)構成代數(shù)系統(tǒng)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, 的子代數(shù)，則稱的子代數(shù)，則稱T, 是是L, 的子的子格。格。 格格2 對應的代數(shù)系統(tǒng)形式的格是對應

60、的代數(shù)系統(tǒng)形式的格是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