1、第第6章章 群論群論 第六章第六章 群論群論 6.1 半群與單元半群半群與單元半群 6.2 群群 第第6章章 群論群論 群在代碼的查錯、改錯的研討，自動機實際群在代碼的查錯、改錯的研討，自動機實際等方面都有運用。等方面都有運用。 第第6章章 群論群論 6.1 半群與單元半群半群與單元半群 半群與群都是具有一個二元運算的代數系統，群是半群的特殊例子。現實上，群是歷史上最早研討的代數系統，它比半群復雜一些，而半群概念是在群的實際開展之后才引進的。邏輯關系見圖6.1.1。第第6章章 群論群論 圖圖 6.1.1 群群半群半群第第6章章 群論群論 一、半群1、半群的有關定義 定義6.1 設(S，)是代數

2、系統，是二元運算，假設運算滿足結合律，那么稱它為半群。 換言之，a, b, cS, 假設是S上的封鎖運算且滿足(a b c=a b c，那么(S，)是半群。 許多代數系統都是半群。例如：(I,+)，(I,)， ( E), ) ，( E), ), (N4，+ 4) , (N4，4)均是半群。第第6章章 群論群論 再如，設X是有限字母表，X+是 X 中的字母串， X *= X +，其中是不含字母的空串，運算是字母串的“并置運算，那么( X *， )是半群。如Com X * ，puter X *，經 運算后，得Computer仍是字母串。 第第6章章 群論群論 定理定理6.1 一個半群一個半群(S，

3、)，假設它有一個子，假設它有一個子代數代數 (M， ) ，那么此子代數也是一個半群。，那么此子代數也是一個半群。 定義定義6.2 一個半群一個半群(S，)的子代數的子代數 (M， )也是半群，稱為也是半群，稱為(S，)的子半群。的子半群。第第6章章 群論群論 一個半群(S，)中的元素a ，可定義它的冪： a1=a , a2=a a , ，an+1=an a 即半群中的元素有時可用某些元素的冪表示出來。 由于半群滿足結合律，所以可得到 a m a n=a m + n， (a n) m=a m n。 假設有a2=a，那么稱a為半群中的等冪元素。第第6章章 群論群論 2、一些特殊半群。 (1) 可交

4、換半群： 假設半群(S，)中二元運算是可交換的，那么稱(S，) 是可交換半群。 例如：(I,+)，(I,)， ( E), ) ，( E), ) (N4，+ 4) , (N4，4)均是可交換半群。但( X *， )不是可交換半群。(2) 循環半群：一個半群循環半群：一個半群(S，)假設它的每個元假設它的每個元素均為素均為S內某一固定元素內某一固定元素 a 的某一方冪，那么此的某一方冪，那么此半群稱為由半群稱為由 a 所生成的循環半群，元素所生成的循環半群，元素 a 稱為此稱為此半群的生成元素。半群的生成元素。第第6章章 群論群論 (3) 單元半群或單位半群：有單位元素單元半群或單位半群：有單位元

5、素e的半的半群群(S，)，常記為，常記為(S，e)。定理定理6.2：一個循環半群一定是可交換半群。：一個循環半群一定是可交換半群。定理定理6.3：一個半群內的任一元素：一個半群內的任一元素 a 和它一切的和它一切的冪組成一個由冪組成一個由 a 所生成的循環子半群。所生成的循環子半群。第第6章章 群論群論 例：下面半群都是單位半群例：下面半群都是單位半群 (I,+)單位元素是單位元素是0，可記為，可記為(I,+,0); (I,)單位元素是單位元素是1 ，可記為，可記為(I,1) ； ( X *， )單位元素是單位元素是(空串空串) ， 可記為可記為( X *， ,) ； ( E), )單位元素是

6、單位元素是 ，可記為，可記為( E), , ) ； ( E), )單位元素是單位元素是E ，可記為，可記為( E), ,E) 。 (N4，+4)單位元素是單位元素是0 ，可記為，可記為(N4，+4， 0 ) (N4， 4)單位元素是單位元素是1 ，可記為，可記為(N4， 4 ， 1 )第第6章章 群論群論 定理定理6.5 一個單位半群一個單位半群(S，)，假設存在一個，假設存在一個子代數子代數 (M， ) ，且其單位元，且其單位元 e M，那么，那么 (M， ) 也是一個單位半群。也是一個單位半群。 定義定義6.5 一個單位半群一個單位半群(S，)，假設存在一個，假設存在一個子代數子代數 (M

7、， ) ，且其單位元，且其單位元 e M，那么，那么 (M， ) 也是一個單位半群，稱為也是一個單位半群，稱為(S，)的子單位半的子單位半群群 。第第6章章 群論群論 定義定義6.5 ：一個單位半群：一個單位半群(S，)假設由它的一個假設由它的一個元素元素a 所生成，那么稱為由所生成，那么稱為由 a 所生成的循環單位所生成的循環單位半群，元素半群，元素 a 稱為此單位半群的生成元素。稱為此單位半群的生成元素。定理定理6.6 ：一個循環單位半群是一個可換單位半：一個循環單位半群是一個可換單位半群。群。第第6章章 群論群論 6.2 群群一、群與群的同構一、群與群的同構1、群的有關定義、群的有關定義

8、 定義定義6.7 假設代數系統假設代數系統(G， )滿足滿足 1 (G， )為一半群；為一半群； 2 (G， )中有單位元中有單位元e； 3 (G，)中每一元素中每一元素aG都有逆元都有逆元 a-1 那么稱代數系統那么稱代數系統(G， )為群。為群。第第6章章 群論群論 例如：例如：(I,+)是群，因是群，因 a I 都有逆元都有逆元 - a ； (N4，+4)是群是群,0的逆元是的逆元是0，1的逆元是的逆元是3， 2的逆元是的逆元是2。(I,)， ( X *， )，( E), ) ，( E), ), (N4， 4)均不是群。均不是群。定義定義6.8 一個群一個群(G， )假設滿足交換律，那么

9、稱假設滿足交換律，那么稱為可交換群或稱阿貝爾群。為可交換群或稱阿貝爾群。例如：群例如：群(I,+)， (N4，+4)都是阿貝爾群。都是阿貝爾群。第第6章章 群論群論 定義定義6.9 一個群一個群(G， )假設它的一個子代數假設它的一個子代數(H， )也是一個群，那么稱也是一個群，那么稱(H， )是是(G， )的一個的一個群。群。定義定義6.10 一個群一個群(G， )假設它的元素個數是有限假設它的元素個數是有限的，那么稱為有限群。假設它的元素個數是無限的，的，那么稱為有限群。假設它的元素個數是無限的，那么稱為無限群。那么稱為無限群。定義定義6.11 一個群一個群(G， )的階記為的階記為|G|

10、，假設一個群，假設一個群是有限群，那么階為元素個數，假設一個群為無限是有限群，那么階為元素個數，假設一個群為無限群，那么階為無窮大。群，那么階為無窮大。第第6章章 群論群論 2、群的一些性質、群的一些性質1 群滿足消去律群滿足消去律2 一個階大于一個階大于1的群一定沒有零元的群一定沒有零元3除了單位元外，一個群一定沒有等冪元素。除了單位元外，一個群一定沒有等冪元素。4一個群一個群(G， )的方程：的方程：a x = b 與與 y a = b，其其 中中 a, b G 在群內有獨一解。在群內有獨一解。第第6章章 群論群論 3、群的第二個定義、群的第二個定義 定義定義6.12 一個代數系統一個代數

11、系統(G， )假設滿足以下假設滿足以下條件，那么稱為群條件，那么稱為群 1滿足結合律；滿足結合律； 2方程：方程：a x = b 與與 y a = b，其，其 中中 a, b G 在在G內有獨一解。內有獨一解。第第6章章 群論群論 4、群的同構、群的同構定義定義6.13 設設(G， )與與(H，*)是兩個群，假設存在是兩個群，假設存在一個函數一個函數 g : G H，使得對每個，使得對每個a, b G ，有，有 g (a b) = g (a ) * g (b ) 那么稱那么稱g是從是從 (G， ) 到到 ( H, * ) 的群同態。的群同態。 假設假設 g : G H 是一一對應的，那么稱是一

12、一對應的，那么稱 g 是從是從 (G， ) 到到 ( H, * ) 的群同構。的群同構。第第6章章 群論群論 定理定理6.9 ：設：設(G， )與與(H，*)是兩個群，有一個函是兩個群，有一個函數數 g : G H 使其群同態，那么有使其群同態，那么有 g (e G) = e H g (a-1) = g (a)-1定理定理6.9 ：設：設(G， )是一個群，假設是一個群，假設(G， )與與(H，*)滿同態或同構，那么滿同態或同構，那么(H，*)也構成群。也構成群。第第6章章 群論群論 二、變換群二、變換群 定義6.14 集合S上的假設干個變換與復合運算假設構成群，那么此種群叫變換群。定理定理6

13、.9 ：任一個群均與一個變換群同構。：任一個群均與一個變換群同構。第第6章章 群論群論 三、有限群三、有限群群表：對有限群，可用一張組合表將其運算表示出群表：對有限群，可用一張組合表將其運算表示出來，稱為群表。來，稱為群表。 設有限群設有限群(G，* )，其中，其中G=1，2，3，這個，這個群可用表群可用表6.3所示的群表定義所示的群表定義*123112322313312表表6.3第第6章章 群論群論 群表的特性：群表的特性： (1) 總存在一行或一列其元素與橫線上或豎總存在一行或一列其元素與橫線上或豎 線左邊的元素一樣。線左邊的元素一樣。(2) 每一行列內元素各不一樣，且任兩行列每一行列內元

14、素各不一樣，且任兩行列 對應元素間也均不一樣，故群表每一行列是對應元素間也均不一樣，故群表每一行列是 G中元素的一個全陳列。中元素的一個全陳列。(3) 假設群是可換群，那么群表是對稱的。假設群是可換群，那么群表是對稱的。第第6章章 群論群論 由群表可知，一個階為由群表可知，一個階為n的有限群的有限群(G，* )，它，它的每個元素對應的每個元素對應G的一個置換，就是說：的一個置換，就是說： 設有有限群設有有限群(G，* )，其中，其中G=a1, a2, , an，那么存在一個函數那么存在一個函數： ), 2 , 1(2121nipaaaaaaaaaakiniiini 由這些置換組成一個集合由這些

15、置換組成一個集合 knkkpppP,21 那么集合那么集合P與其復合運算構成一個群，即一個置換群。與其復合運算構成一個群，即一個置換群。第第6章章 群論群論 如表如表6.3中中G的每個元素對應的置換所組成的集合為的每個元素對應的置換所組成的集合為 651,pppP 存在一個函數存在一個函數： 6513,2,1ppp 集合集合P與其復合運算構成一個置換群。與其復合運算構成一個置換群。定理定理6.15 ：每個有限群均與一個置換群同構。：每個有限群均與一個置換群同構。第第6章章 群論群論 因此，當有限群因此，當有限群(G，* ) 分別為分別為1，2，3階群時，階群時，*運運算都只需一個定義方式即不計

16、元素記號的不同算都只需一個定義方式即不計元素記號的不同,只只需一張定義需一張定義*運算的運算表，分別如表運算的運算表，分別如表6.4、6.5和和6.3所示，于是可以說：所示，于是可以說：1，2，3階的群都只需一個。階的群都只需一個。*111表表6.4*12112223表表6.5第第6章章 群論群論 4階群的群表不只一個階群的群表不只一個*123411234221433342144312*123411234224133314244321第第6章章 群論群論 *123411234223413341244123第第6章章 群論群論 四、循環群四、循環群定義定義6.16： 設設(G，)是一個群，是一個

17、群，aG ，那么令：，那么令： a0=e ， a j+1=a j a ( j 0， a -j=(a -1) j ( j 0 由定義可得到由定義可得到 a m a n=a m + n， (a n) m=a m n群中元素方冪的定義群中元素方冪的定義第第6章章 群論群論 定義定義6.17：假設一個群：假設一個群(G，)的每一個元素均是它的每一個元素均是它的某一個固定元素的某一個固定元素 a 的某次方冪，那么稱的某次方冪，那么稱(G，)是是由由 a 生成的循環群，而生成的循環群，而a 稱為稱為(G，)的生成元素。的生成元素。記為記為定義定義6.18：一個由：一個由 a 生成的循環群生成的循環群(G，

18、)，假設存，假設存在在m，使得，使得 am =e 的最小正整數的最小正整數 m 稱為稱為 a 的周期，的周期，假設不存在這樣的一個假設不存在這樣的一個m，那么稱，那么稱 a 的周期為無限。的周期為無限。第第6章章 群論群論 例例1：整數加群：整數加群 (I,+) 是一個生成周期為無限的循是一個生成周期為無限的循環群。環群。 1或或l為其生成元。為其生成元。例例2：剩余類加群：剩余類加群 (Nm，+m)是一個生成周期為是一個生成周期為m的循環群。的循環群。 1 為其生成元。為其生成元。定理定理6.16 ：設有一個由：設有一個由 a 生成的循環群生成的循環群 (G，)，那，那么有么有假設假設a 的周期無限，那么的周期無限，那么(G，) 與與(I,+)同構。同構。(2) 假設假設a 的周期為的周期為m，那么，那么(G，) 與與(Nm，+m)同同構。構。第第6章章 群論群論 四、子群四、子群定理定理6.17： 一個群一個群(G， )及由它的一個子集及由它的一個子集H組組成一個代數成一個代數(H， )，該代數構成一個，該代數構成一個 (G， )的的子群的充要條件是：子群的充要條件是： a, b H，那么，那么 a b H a H，那么，那么 a -1 H定理定理6.18： 設設(G， )是一個群，而是一個群，而 (H， )是是(G， )的子群，那么的子群，那么(H， )的單位元素即是的單位