離散數(shù)學(xué)第六章群論課件

1、第六章 群論 6.1 半群與單元半群 6.2 群 第六章 群論 6.1 半群與單元半群 群在代碼的查錯(cuò)、改錯(cuò)的研究，自動(dòng)機(jī)理論等方面都有應(yīng)用。 群在代碼的查錯(cuò)、改錯(cuò)的研究，自動(dòng)機(jī)理論等方面都有應(yīng)6.1 半群與單元半群 半群與群都是具有一個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，群是半群的特殊例子。事實(shí)上，群是歷史上最早研究的代數(shù)系統(tǒng)，它比半群復(fù)雜一些，而半群概念是在群的理論發(fā)展之后才引進(jìn)的。邏輯關(guān)系見(jiàn)圖6.1.1。6.1 半群與單元半群 半群與群圖 6.1.1 群半群圖 6.1.1 群半群 一、半群1、半群的有關(guān)定義 定義6.1 設(shè)(S，)是代數(shù)系統(tǒng)，是二元運(yùn)算，如果運(yùn)算滿足結(jié)合律，則稱它為半群。 換言之，a,

2、b, cS, 若是S上的封閉運(yùn)算且滿足(a b） c=a （b c），則(S，)是半群。 許多代數(shù)系統(tǒng)都是半群。例如：(I,+)，(I,)， ( E), ) ，( E), ), (N4，+ 4) , (N4，4)均是半群。 一、半群 再如，設(shè)X是有限字母表，X+是 X 中的字母串， X *= X +，其中是不含字母的空串，運(yùn)算是字母串的“并置”運(yùn)算，則( X *， )是半群。如Com X * ，puter X *，經(jīng) 運(yùn)算后，得Computer仍是字母串。 再如，設(shè)X是有限字母表，X+是 X 定理6.1 一個(gè)半群(S，)，如果它有一個(gè)子代數(shù) (M， ) ，則此子代數(shù)也是一個(gè)半群。 定義6.2

3、一個(gè)半群(S，)的子代數(shù) (M， )也是半群，稱為(S，)的子半群。 定理6.1 一個(gè)半群(S，)，如果它有一 一個(gè)半群(S，)中的元素a ，可定義它的冪： a1=a , a2=a a , ，an+1=an a 即半群中的元素有時(shí)可用某些元素的冪表示出來(lái)。 因?yàn)榘肴簼M足結(jié)合律，所以可得到 a m a n=a m + n， (a n) m=a m n。 如果有a2=a，則稱a為半群中的等冪元素。 一個(gè)半群(S，)中的元素a ，可定義它的 2、一些特殊半群。 (1) 可交換半群： 如果半群(S，)中二元運(yùn)算是可交換的，則稱(S，) 是可交換半群。 例如：(I,+)，(I,)， ( E), ) ，(

4、 E), ) (N4，+ 4) , (N4，4)均是可交換半群。但( X *， )不是可交換半群。(2) 循環(huán)半群：一個(gè)半群(S，)如果它的每個(gè)元素均為S內(nèi)某一固定元素 a 的某一方冪，則此半群稱為由 a 所生成的循環(huán)半群，元素 a 稱為此半群的生成元素。 2、一些特殊半群。(2) 循環(huán)半群：一個(gè)半群(S，(3) 單元半群（或單位半群）：有單位元素e的半群(S，)，常記為(S，e)。定理6.2：一個(gè)循環(huán)半群一定是可交換半群。定理6.3：一個(gè)半群內(nèi)的任一元素 a 和它所有的冪組成一個(gè)由 a 所生成的循環(huán)子半群。(3) 單元半群（或單位半群）：有單位元素e的半群(S，)例：下面半群都是單位半群 (

5、I,+)單位元素是0，可記為(I,+,0); (I,)單位元素是1 ，可記為(I,1) ； ( X *， )單位元素是(空串) ， 可記為( X *， ,) ； ( E), )單位元素是 ，可記為( E), , ) ； ( E), )單位元素是E ，可記為( E), ,E) 。 (N4，+4)單位元素是0 ，可記為(N4，+4， 0 ) (N4， 4)單位元素是1 ，可記為(N4， 4 ， 1 )例：下面半群都是單位半群 定理6.5 一個(gè)單位半群(S，)，如果存在一個(gè)子代數(shù) (M， ) ，且其單位元 e M，則 (M， ) 也是一個(gè)單位半群。 定義6.5 一個(gè)單位半群(S，)，如果存在一個(gè)子代

6、數(shù) (M， ) ，且其單位元 e M，則 (M， ) 也是一個(gè)單位半群，稱為(S，)的子單位半群 。 定理6.5 一個(gè)單位半群(S，)，如果存定義6.5 ：一個(gè)單位半群(S，)如果由它的一個(gè)元素a 所生成，則稱為由 a 所生成的循環(huán)單位半群，元素 a 稱為此單位半群的生成元素。定理6.6 ：一個(gè)循環(huán)單位半群是一個(gè)可換單位半群。定義6.5 ：一個(gè)單位半群(S，)如果由它的一個(gè)元素a 所6.2 群一、群與群的同構(gòu)1、群的有關(guān)定義 定義6.7 如果代數(shù)系統(tǒng)(G， )滿足 （1） (G， )為一半群； （2） (G， )中有單位元e； （3） (G，)中每一元素aG都有逆元 a-1 則稱代數(shù)系統(tǒng)(G，

7、 )為群。6.2 群一、群與群的同構(gòu)例如：(I,+)是群，因 a I 都有逆元 - a ； (N4，+4)是群,0的逆元是0，1的逆元是3， 2的逆元是2。(I,)， ( X *， )，( E), ) ，( E), ), (N4， 4)均不是群。定義6.8 一個(gè)群(G， )如果滿足交換律，則稱為可交換群或稱阿貝爾群。例如：群(I,+)， (N4，+4)都是阿貝爾群。例如：(I,+)是群，因 a I 都有逆元 - a ；定義定義6.9 一個(gè)群(G， )如果它的一個(gè)子代數(shù)(H， )也是一個(gè)群，則稱(H， )是(G， )的一個(gè)群。定義6.10 一個(gè)群(G， )如果它的元素個(gè)數(shù)是有限的，則稱為有限群。

8、如果它的元素個(gè)數(shù)是無(wú)限的，則稱為無(wú)限群。定義6.11 一個(gè)群(G， )的階記為|G|，如果一個(gè)群是有限群，則階為元素個(gè)數(shù)，如果一個(gè)群為無(wú)限群，則階為無(wú)窮大。定義6.9 一個(gè)群(G， )如果它的一個(gè)子代數(shù)(H， 2、群的一些性質(zhì)（1） 群滿足消去律（2） 一個(gè)階大于1的群一定沒(méi)有零元（3）除了單位元外，一個(gè)群一定沒(méi)有等冪元素。（4）一個(gè)群(G， )的方程：a x = b 與 y a = b，其 中 a, b G 在群內(nèi)有唯一解。2、群的一些性質(zhì)（1） 群滿足消去律（2） 一個(gè)階大于1的群3、群的第二個(gè)定義 定義6.12 一個(gè)代數(shù)系統(tǒng)(G， )若滿足下列條件，則稱為群 （1）滿足結(jié)合律； （2）方

9、程：a x = b 與 y a = b，其 中 a, b G 在G內(nèi)有唯一解。3、群的第二個(gè)定義 定義6.12 一個(gè)代數(shù)系統(tǒng)(G4、群的同構(gòu)定義6.13 設(shè)(G， )與(H，*)是兩個(gè)群，若存在一個(gè)函數(shù) g : G H，使得對(duì)每個(gè)a, b G ，有 g (a b) = g (a ) * g (b ) 則稱g是從 (G， ) 到 ( H, * ) 的群同態(tài)。 若 g : G H 是一一對(duì)應(yīng)的，則稱 g 是從 (G， ) 到 ( H, * ) 的群同構(gòu)。4、群的同構(gòu)定義6.13 設(shè)(G， )與(H，*)是兩個(gè)定理6.9 ：設(shè)(G， )與(H，*)是兩個(gè)群，有一個(gè)函數(shù) g : G H 使其群同態(tài)，則

10、有 g (e G) = e H g (a-1) = g (a)-1定理6.9 ：設(shè)(G， )是一個(gè)群，若(G， )與(H，*)滿同態(tài)或同構(gòu)，則(H，*)也構(gòu)成群。定理6.9 ：設(shè)(G， )與(H，*)是兩個(gè)群，有一個(gè)函數(shù)二、變換群 定義6.14 集合S上的若干個(gè)變換與復(fù)合運(yùn)算若構(gòu)成群，則此種群叫變換群。定理6.9 ：任一個(gè)群均與一個(gè)變換群同構(gòu)。二、變換群 定義6.14 集合S上的若干個(gè)變換與復(fù)三、有限群群表：對(duì)有限群，可用一張組合表將其運(yùn)算表示出來(lái)，稱為群表。 設(shè)有限群(G，* )，其中G=1，2，3，這個(gè)群可用表6.3所示的群表定義*123112322313312表6.3三、有限群群表：對(duì)有

11、限群，可用一張組合表將其運(yùn)算表示出來(lái)，稱群表的特性： (1) 總存在一行（或一列）其元素與橫線上（或豎 線左邊）的元素一樣。(2) 每一行（列）內(nèi)元素各不相同，且任兩行（列） 對(duì)應(yīng)元素間也均不相同，故群表每一行（列）是 G中元素的一個(gè)全排列。(3) 若群是可換群，則群表是對(duì)稱的。群表的特性： (1) 總存在一行（或一列）其元素與橫線上（或 由群表可知，一個(gè)階為n的有限群(G，* )，它的每個(gè)元素對(duì)應(yīng)G的一個(gè)置換，就是說(shuō)： 設(shè)有有限群(G，* )，其中G=a1, a2, , an，則存在一個(gè)函數(shù)：由這些置換組成一個(gè)集合則集合P與其復(fù)合運(yùn)算構(gòu)成一個(gè)群，即一個(gè)置換群。 由群表可知，一個(gè)階為n的有限群

12、(G，* )，它的如表6.3中G的每個(gè)元素對(duì)應(yīng)的置換所組成的集合為存在一個(gè)函數(shù)：集合P與其復(fù)合運(yùn)算構(gòu)成一個(gè)置換群。定理6.15 ：每個(gè)有限群均與一個(gè)置換群同構(gòu)。如表6.3中G的每個(gè)元素對(duì)應(yīng)的置換所組成的集合為存在一個(gè)函數(shù)因此，當(dāng)有限群(G，* ) 分別為1，2，3階群時(shí)，*運(yùn)算都只有一個(gè)定義方式（即不計(jì)元素記號(hào)的不同,只有一張定義*運(yùn)算的運(yùn)算表，分別如表6.4、6.5和6.3所示），于是可以說(shuō)：1，2，3階的群都只有一個(gè)。*111表6.4*12112223表6.5因此，當(dāng)有限群(G，* ) 分別為1，2，3階群時(shí)，*運(yùn)算都4階群的群表不只一個(gè)*123411234221433342144312*

13、1234112342241333142443214階群的群表不只一個(gè)*1234112342214333421*123411234223413341244123*123411234223413341244123四、循環(huán)群定義6.16： 設(shè)(G，)是一個(gè)群，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群中元素方冪的定義四、循環(huán)群定義6.16： 設(shè)(G，)是一個(gè)群，aG ，則定義6.17：若一個(gè)群(G，)的每一個(gè)元素均是它的某一個(gè)固定元素 a 的某次方冪，則稱

14、(G，)是由 a 生成的循環(huán)群，而a 稱為(G，)的生成元素。記為定義6.18：一個(gè)由 a 生成的循環(huán)群(G，)，若存在m，使得 am =e 的最小正整數(shù) m 稱為 a 的周期，若不存在這樣的一個(gè)m，則稱 a 的周期為無(wú)限。定義6.17：若一個(gè)群(G，)的每一個(gè)元素均是它的某一個(gè)固例1：整數(shù)加群 (I,+) 是一個(gè)生成周期為無(wú)限的循環(huán)群。 1或（l）為其生成元。例2：剩余類加群 (Nm，+m)是一個(gè)生成周期為m的循環(huán)群。 1 為其生成元。定理6.16 ：設(shè)有一個(gè)由 a 生成的循環(huán)群 (G，)，則有若a 的周期無(wú)限，則(G，) 與(I,+)同構(gòu)。(2) 若a 的周期為m，則(G，) 與(Nm，+m)同構(gòu)。例1：整數(shù)加群 (I,+) 是一個(gè)生成周期為無(wú)限的循環(huán)群。 四、子群定理6.17： 一個(gè)群(G， )及由它的一個(gè)子集H組成一個(gè)代數(shù)(H， )，該代數(shù)構(gòu)成一個(gè) (G， )的子群的充要條件是： a, b H，則 a b H a H，則 a -1 H定理6.18： 設(shè)(G， )是一個(gè)群，而 (H， )是(G， )的子群，則(H， )的單位元素即是(G， )的單位元素； (H，