離散數(shù)學(xué)-第十章的課件

1、第十章 群與環(huán),主要內(nèi)容群的定義與性質(zhì)子群與生成子群循環(huán)群與置換群,2,半群、獨(dú)異點(diǎn)與群的定義半群、獨(dú)異點(diǎn)、群的實(shí)例群中的術(shù)語群的基本性質(zhì),10.1 群的定義與性質(zhì),3,半群、獨(dú)異點(diǎn)與群的定義,定義10.1(1) 設(shè)V=是代數(shù)系統(tǒng)，°為二元運(yùn)算，如果°運(yùn)算是可 結(jié)合的，則稱V為半群.(2) 設(shè)V=是半群，若e∈S是關(guān)于°運(yùn)算的單位元，則稱V 是幺半群，也叫做獨(dú)異點(diǎn). 有時(shí)也將獨(dú)異點(diǎn)V 記作

2、 V=. (3) 設(shè)V=是獨(dú)異點(diǎn)，e?S關(guān)于°運(yùn)算的單位元，若 ?a?S，a?1?S，則稱V是群. 通常將群記作G.,注意：在半群、獨(dú)異點(diǎn)和群中，由于只有一個(gè)二元運(yùn)算，在不發(fā)生混淆的情況下，經(jīng)常將算符省去，例如將x°y寫作xy 。 下文將采用這種簡略表示。,4,實(shí)例,例10.1 (1) ,,,,,都是半群，+是普通加法. 這些半群中除外都是獨(dú)異點(diǎn),其中,,,都是群，分別叫做整數(shù)加群、有理數(shù)加群、實(shí)數(shù)加群和復(fù)數(shù)

3、加群(2) 設(shè)n是大于1的正整數(shù)，和都是半群，也都是獨(dú)異點(diǎn)，其中+和·分別表示矩陣加法和矩陣乘法， 是群，不是群(3) 為半群，也是獨(dú)異點(diǎn)和群，其中?為集合對稱差運(yùn)算(4) 為半群，也是獨(dú)異點(diǎn)和群，其中Zn={0,1,…,n?1}，?為模n加法 (5) 為半群，也是獨(dú)異點(diǎn)，其中?為函數(shù)的復(fù)合運(yùn)算(6) 為半群，其中R*為非零實(shí)數(shù)集合，?運(yùn)算定義如下：?x, y?R*, x?y=y,這個(gè)系統(tǒng)不構(gòu)成獨(dú)異點(diǎn)和群，因?yàn)樗鼪]

4、有單位元,5,例10.2 設(shè)G={ e, a, b, c }，G上的運(yùn)算由下表給出，稱為Klein四元群,,實(shí)例,特征：1. G中的單位元是e2. G中的運(yùn)算滿足交換律2. 每個(gè)元素的逆元就是它自己3. a, b, c中任何兩個(gè)元素運(yùn)算結(jié) 果都等于另一個(gè)元素,6,有關(guān)群的術(shù)語,定義10.2 (1) 若群G是有窮集，則稱G是有限群，否則稱為無限群. 群G 的基數(shù)稱為群 G 的階，有限群G的階記

5、作|G|. (2) 只含單位元的群稱為平凡群. (3) 若群G中的二元運(yùn)算是可交換的，則稱G為交換群或阿貝爾 (Abel) 群.,7,定義10.3 設(shè)G是群，a∈G，n∈Z，則a 的 n次冪,群中元素的冪,群中元素可以定義負(fù)整數(shù)次冪. 元素的冪可推廣到半群和獨(dú)異點(diǎn)。但是冪指數(shù)在半群中只能取正整數(shù)Z+，在獨(dú)異點(diǎn)中只能取N，只有在群中可以取負(fù)整數(shù)Z-在中有 2?3 = (2-1)3 = 13

6、 = 1?1?1 = 0 在中有 (?2)?3 = ((?2)?1)3 = 23 = 2+2+2 = 6,3?5=？,元素的階,定義10.4 設(shè)G是群，a∈G，使得等式 ak=e 成立的最小正整數(shù)k 稱為a 的階，記作|a|=k，稱 a 為 k 階元. 若不存在這樣的正整數(shù) k，則稱 a 為無限階元.,例如，在中， 2和4是3階元， 3是2階元， 1和5是6階元

7、， 0是1階元. 在中，0是1階元，其它整數(shù)的階都不存在. Klein四元群中e為1階元，其它元素都是2階元,群的性質(zhì),定理10.1 設(shè)G 為群，則G中的冪運(yùn)算滿足： (1) ?a∈G，(a?1)?1=a(2) ?a,b∈G，(ab)?1=b?1a?1(3) ?a∈G，anam = an+m，n, m∈Z(4) ?a∈G，(an)m = anm，n, m∈Z (5) 若G為交換群，則 (ab)n = anbn.,

8、定理10.2 G為群，則G中適合消去律，即對任意a,b,c∈G 有(1) 若 ab = ac，則 b = c.(2) 若 ba = ca，則 b = c.,定理10.3 G為群，a∈G且 |a| = r. 設(shè)k是整數(shù)，則 (1) ak = e當(dāng)且僅當(dāng)r | k (2 )|a?1| = |a|,10,10.2 子群與群的陪集分解,定義10.5 設(shè)G是群，H是G的非空子集，(1) 如果H關(guān)于G中的運(yùn)算構(gòu)成群，則稱H是G的子群,

9、記作H≤G. (2) 若H是G的子群，且H?G，則稱H是G的真子群，記作H<G.,例如 nZ (n是自然數(shù)) 是整數(shù)加群 的子群. 當(dāng)n≠1時(shí),nZ是Z的真子群.對任何群G都存在子群. G和{e}都是G的子群，稱為G的平凡子群.,11,子群的判定定理,定理10.4（判定定理一）設(shè)G為群，H是G的非空子集，則H是G的子群當(dāng)且僅當(dāng)(1) ?a,b∈H ，有ab∈H(2) ?a∈H ，有a?1∈H.,定理10.5 （判定

10、定理二）設(shè)G為群，H是G的非空子集. H是G的子群當(dāng)且僅當(dāng)?a,b∈H有ab?1∈H.,定理10.6 （判定定理三） 設(shè)G為群，H是G的非空有窮子集，則H是G的子群當(dāng)且僅當(dāng)?a,b∈H ，有ab∈H.,12,生成子群,例10.8 設(shè)G為群，a∈G，令H={ak| k∈Z}，即H由a的所有的冪構(gòu)成的集合，則H是G的子群，稱為由 a 生成的子群，記作.,實(shí)例：例如整數(shù)加群，由2生成的子群是 ={2k | k∈Z}=2Z中，

11、由2生成的子群={0,2,4}Klein四元群 G = {e,a,b,c}的所有生成子群是： ={e}, ={e,a}, ={e,b}, ={e,c}.,13,10.3 循環(huán)群與置換群,定義10.7 設(shè)G是群，若存在a∈G使得 G={ak| k∈Z} 則稱G是循環(huán)群，記作G=，稱 a 為G 的生成元.,循環(huán)群根據(jù)生成元a的階

12、可分兩類：n 階循環(huán)群和無限循環(huán)群. 設(shè)G=是循環(huán)群，若a是n 階元，則 G = { a0=e, a1, a2, … , an?1 }那么|G| = n，稱 G 為 n 階循環(huán)群. 若a 是無限階元，則 G = { a0=e, a±1, a±2, … } 稱 G 為無限循環(huán)群.,14,循環(huán)群的生成元,

13、定理10.11 設(shè)G=是循環(huán)群.  (1) 若G是無限循環(huán)群，則G只有兩個(gè)生成元，即a和a?1. (2) 若G是 n 階循環(huán)群，則G含有?(n)個(gè)生成元. 對于任何小 于n且與 n 互素的數(shù)r∈{0,1,…,n-1}, ar是G的生成元. ?(n)是歐拉函數(shù)，表示0,1,…,n-1中與n互素的數(shù)的個(gè)數(shù)。例如 n=9，小于9且與9互素的正整數(shù)有6個(gè)：

14、 1, 2, 4, 5 , 7, 8 所以?(9)=6.,例 設(shè)G=是模12的整數(shù)加群，因?yàn)樾∮?2并且與12互素的數(shù)是 1, 5, 7, 11，所以?(12)=4. 根據(jù)定理10.11，G的生成元是：1, 5, 7和11.,15,循環(huán)群的子群,定理10.12 設(shè)G=是循環(huán)群. (1) 設(shè)G=是循環(huán)群，則G的子群仍是循環(huán)群.(2) 若G=是無限循環(huán)群，則G的子群除{e}以外都是無限循環(huán)群.(

15、3) 若G=是n階循環(huán)群，則對n的每個(gè)正因子d，G恰好含有一個(gè)d 階子群. 根據(jù)以上定理可以得到求循環(huán)子群的方法。如果G=是n階循環(huán)群，先求出n的所有的正因子。對于每一個(gè)正因子d，是G的唯一的d階子群。,實(shí)例,例題 設(shè)G=是12階循環(huán)群.（1）求出G的所有生成元；（2）求出G的所有子群。解： G = Z12 = {0,1,2,3,4,5,6,7,8,9,10,11}（1）小于12且與12互素的數(shù)是 1, 5, 7

16、, 11，?(12)=4. 故G的生成元是：1, 5, 7和11. （2）G=Z12是12階循環(huán)群. 12的正因子是1,2,3,4,6,12，因此G 的子群是: 1階子群 =={0} 2階子群 ={0,6} 3階子群 ={0,4,8} 4階子群 ={0,3,6,9} 6階子群 ={0,2,4,6,8,

17、10} 12階子群 = {0,1,2,3,4,5,6,7,8,9,10,11} = G,由單位元生成,由原本的生成元生成,17,n 元置換及乘法,定義10.8 設(shè) S = {1, 2, …, n}, S上的任何雙射函數(shù)σ:S→S 稱為S上的n元置換. 一般將n元置換σ記為例如 S={1, 2, 3, 4, 5}, 下述為5元置換,,定義10.9 設(shè)σ,τ是n元置換, σ和τ的復(fù)合σ °τ 也是n元置換, 稱

18、為σ與τ 的乘積, 記作σ τ. 例如,18,n元置換的輪換表示,定義10.10 設(shè)?是S = {1, 2, …, n}上的n元置換。若 ?(i1) = i2 , ?(i2) = i3 , … , ?(ik?1) = ik , ?(ik) = i1且保持S中的其它元素不變，則稱?為S上的k階輪換，記作(i1 i2 … ik) 。 若k =2，稱?為S上的對換。設(shè) S = {1, 2,

19、 …, n}，對于任何S上的 n 元置換 ?, 存在著一個(gè)有限序列 i1, i2, …,ik, k≥1, (可以取i1=1) 使得 ?(i1) = i2, ?(i2) = i3, …, ?(ik?1) = ik, ?(ik) = i1令 ?1 = (i1 i2 … ik), 則 ?1 是從?中分解出來的第一個(gè)輪換. 根據(jù)函數(shù)的復(fù)合定義可將 ? 寫作 ?1??,其中??作用于S-{i1, i2, …,i

20、k}上的元素。繼續(xù)對 ?? 進(jìn)行類似的分解. 由于S 中只有n個(gè)元素, 經(jīng)過有限步以后，必得到?的輪換分解式： ? = ? 1 ? 2 … ? t,輪換分解式的特征輪換的不交性：上述分解式中任何兩個(gè)輪換都作用于不同的元素上分解的惟一性: 若 ? = ?1?2 …?t 和 ? = ?1?2 …?s 是?的兩個(gè)輪換表示式，則有 { ?1,

21、 ?2, …, ?t } = {?1,? 2, …,?s } 任何n元置換都可以表示成不交的輪換之積。,19,例10.16 設(shè)S = {1, 2, … , 8},  ,則 輪換分解式為： ? = (1 5 2 3 6) (4) (7 8) = (1 5 2 3 6) (7 8) ? = (1 8 3 4 2) (5 6 7) ,實(shí)例,20,置換的對換

22、分解,設(shè)S = {1,2,…,n}，? = (i1 i2 … ik) 是S上的 k 階輪換， ? 可以進(jìn)一步表成對換之積，即 (i1 i2 … ik) = (i1 i2) (i1 i3) … (i1 ik) 任何n元置換表成輪換之積，然后將每個(gè)輪換表成對換之積. 例如 8 元置換 ? = (1 5 2 3 6) (7 8) = (1 5) (1 2) (1 3) (1 6

23、) (7 8) ? = (1 8 3 4 2) (5 6 7) = (1 8) (1 3) (1 4) (1 2) (5 6) (5 7),作業(yè),書本第203頁第7題第8題第9題書本204頁第28題第29題（1）和（2）,22,對換分解的特征,,對換分解式中對換之間可以有交，分解式也不惟一. 例如4元置換 可以有下面不同的對換表示：  ? = (1 2) (1 3)， ?