計算機數(shù)學基礎(chǔ)(上)第4編群

1、計算機數(shù)學基礎(chǔ)(上)第4編 代數(shù)系統(tǒng),第七章 群,本章主要內(nèi)容：,代數(shù)系統(tǒng)群、子群交換群、循環(huán)群、置換群同態(tài)與同構(gòu)重點：代數(shù)運算、群、循環(huán)群、置換群難點：群的判別、循環(huán)群、置換的乘法,7.1 代數(shù)結(jié)構(gòu)概述,一、代數(shù)運算及其性質(zhì)1。代數(shù)運算的定義 設(shè)f 是非空集合A×A到A的一個映射，則稱f 是A上的一個二元運算。 設(shè)f 是非空集合A到A的一個映射，則稱f 是A上的

2、一個一元運算。 因此，代數(shù)運算可以理解為值域包含在定義域中的函數(shù)，這種情況通常稱為對運算封閉。 代數(shù)運算通常用*和　表示，有時也讀作乘?！?例如， ，定義z=x+y-2，顯然， ，可記作 或 。,因此，整數(shù)集、實數(shù)集上的加、減、乘法是二元運算，非零實數(shù)集上的除法是二元運算，矩陣集合上的矩陣加法、矩陣

3、加法是二元運算，冪集上的交、并對稱差是二元運算，命題集合上的析取、合取、蘊含等價、不可兼析取是二元運算。 整數(shù)集、實數(shù)集上的、求相反數(shù)是一元運算，非零實數(shù)集上的求倒數(shù)是一元運算，矩陣集合上的矩陣的轉(zhuǎn)置是一元運算，冪集上的求補是一元運算，命題集合上的否定是一元運算。,[2000年1月填空題10] 設(shè)A={1,2,3}，定義在A上的二元運算 為：

4、 ，則 的運算表為 。解：運算表如下：,2。運算的性質(zhì) 設(shè) 是A上的代數(shù)運算， 如果 ，則稱運算 在A上可交換， 如果 ，則稱 在A上可結(jié)合， 如果

5、 ，則記作 ，余此類推。注意：在代數(shù)運算中的 表示 而不是 。例如， 則 如果 ，則稱運算 在A上滿足冪等律，滿足 的元素x稱為運算 的冪等元。 如果

6、 則稱運算 滿足分配律。,[2000年1月選擇題4] 定義在實數(shù)集R上的二元運算*為 ，則二元運算同時滿足交換律和結(jié)合律。其中+，－，×是普通加法，減法和乘法。 A) a+b－ab B) a+2b C) b

7、D) |a+b|解：B)、C)顯然不滿足交換律，A)滿足結(jié)合律，D)不滿足結(jié)合律。,A,[2000年7月選擇題5] 在自然數(shù)集N上定義二元運算*，滿足結(jié)合律的是 。 A) a*b=a－b B) a*b=a+2b C) a*b=max{a,b} D) a*b=|a－b|解：,C,

8、如果 ，則稱運算 滿足吸收律， 如果 ，則稱為運算 的左單位元， 如果

9、 ，則稱為運算 的右單位元， 如果 ，則稱 是運算 的單位元。 例如，在數(shù)的加法運算中0是單位元，在數(shù)的乘法運算中1是單位元。在集合的并中 是單位元，集合的交中E是單位元。在矩陣加法中O是單位元，在矩陣乘法中In是單位元。在 中2是單位元。,如果 是非空集合A上的二元運算，

10、 是 的單位元，對于A中的某一元素x，如果存在 ，滿足 ，則稱 是x的逆元，稱x是可逆的。 例如，在數(shù)的加法運算中-a是a的逆元，在數(shù)的乘法運算中1/a是a的逆元。在矩陣的加法中-A是A的逆元在矩陣的乘法中A-1是A的逆元。在 中，4-a是a的逆元，

11、 。 并不是在任何運算中都存在逆元的，例如在集合的并或集合的交中就沒有逆元。 在給定的集合和運算中，不同元素的逆元是不同的。單位元和某元素的逆元如果存在，則是唯一的。,二、代數(shù)系統(tǒng) 由非空集合A和定義在A上的一系列運算組成的系統(tǒng)稱為代數(shù)系統(tǒng)，記作

12、 。 如果運算 對A的子集B封閉，則稱 為 的子系統(tǒng)。 檢驗一個系統(tǒng)是否構(gòu)成代數(shù)系統(tǒng)，最重要的一點就是看運算對集合是否封閉，即運算的結(jié)果是否還在集合A中。 例如A={1,2,3,4,5}，f (a,b)=

13、lcm(a,b)(最小公倍數(shù))就不構(gòu)成代數(shù)系統(tǒng)。因為，f (3,5)=15不在集合A中，f 對A不封閉。,[2001年1月填空題10] 設(shè)(R*, )是代數(shù)系統(tǒng)，其中R*=R－{0}，二元運算 定義為： ，那么， a 的逆元是 。解： ∴ 1 是單位元，,7.2 群的概念,一、半群與群

14、 1。設(shè)(G,*)是一個代數(shù)系統(tǒng)，如果二元運算*滿足結(jié)合律，則(G,*)稱為半群。 2。存在單位元，且每一個元素的逆元都存在的半群稱為群。 判斷一個半群是否為群，就是判斷單位元是否存在，有沒有不存在逆元的元素。 3。G中的元素個數(shù)有無窮多個的群稱為無限群， G中的元素個數(shù)為有限個的群稱為有限群，有限群中的元素個數(shù)稱為群的階，記作|G|。,[2001年1月選擇5] 下列集合和運算能

15、構(gòu)成群的是 。(Mn(R),+)，其中Mn(R)是定義在實數(shù)集上的n階矩陣，+是普通加法。(A,+)，其中A={0,±1,±2,…,±n},+是普通加法。({ ,0,2},+)，其中+是普通加法。({0,1,2,3}, )，其中 是模4乘法。,A,解：B) ∵A是有限群，∴A對+不封閉， C) 顯然對+不封閉， D)

16、1 是 的單位元，但 0 沒有逆元。,二、群的性質(zhì) 若(G,*)為群， 有， 1。 2。方程 在G中一定有解。注意：在半群中不一定有解，在群中一定有解。 3。滿足消去律，即由 可得b=c。注意：半群不一定滿足消去律，群一定滿足消去律。三

17、、子群 如果*對G的子集H構(gòu)成群，則(H,*)稱為(G,*)的子群，記作H≤G。 判斷H是G的子群的充要條件是：,[2000年7月證明題19] 設(shè)R是實數(shù)集，定義在R×R上的二元關(guān)系如下：證明(R×R, )是群。證明： 滿足結(jié)合律，∴ (R×R, )是半群， ∴是單位元，

18、 ，因此(R×R, )是群。,7.3 特殊群,一、交換群與循環(huán)群 1。如果群(G,*)中的二元運算*是可交換的，則稱群(G,*)為交換群(阿貝爾群)。 2。如果 ，群(G,*)中的所有元素都可以表示為 ，則稱群G為循環(huán)群，a為群G的生成元。 例如定義a*b=a+b-2，則群(Z,*)是

19、循環(huán)群，1是群G的一個生成元， 因此，G是循環(huán)群。 同樣可以驗證，3也是G的一個生成元。,3。循環(huán)群一定是交換群證明：設(shè)(G,*)是循環(huán)群，a 是G的生成元。設(shè) ，群(G,*)是交換群。 4。幾個重要的結(jié)論 ⑴循環(huán)群的子群一定是循環(huán)群， ⑵若|G|是素數(shù)，則群G一定是交換群， ⑶若|G|≤5，則群G一

20、定是交換群， ⑷若G是有限循環(huán)群，|G|=n， 。,二、變換群 從集合A到集合A的一個一一對應(yīng)的映射，稱為對集合A的一個變換。 由集合A的所有的變換構(gòu)成的集合E(A)，對于變換的乘法(復合變換)，構(gòu)成一個群，稱為A上的一一變換群。 E(A)的子群稱為變換群。,三、置換和置換群 1。置換 從

21、有限集合M到有限集合M的一個一一對應(yīng)的映射，稱為M上的一個n元置換。 置換σ常用元素的對應(yīng)關(guān)系來表示， ，例如， M上全體置換的集合記作Sn， 顯然，Sn中包含有n!個不同的置換。,2。置換的乘積(復合) 設(shè)σ和τ是M的兩個置換，對M中的元素先使用σ置換后，再使用τ置換，

22、記作 置換的乘法滿足結(jié)合律，但不滿足交換律。 3。n元置換群 設(shè)M是有n個元素的集合，M的所有置換的集合Sn關(guān)于置換的乘法構(gòu)成一個群，稱為n元對稱群。 Sn的子群稱為n元置換群。,[2001年7月計算題16] 設(shè)M={1,2,3,4}，試計算解：,4。輪換 如果則稱σ為長度為m的輪換。[定理6] 如果σ和τ是Sn的兩個不相

23、交的輪換即σ和τ中沒有相同的元素，則σ和τ可交換，即 。[定理7] 如果σ是Sn中的一個置換，則σ可以唯一地表示成一系列不相交的輪換之積。,7.4 同態(tài)與同構(gòu),一、同態(tài) 如果(G,*)和(S, )是兩個代數(shù)系統(tǒng)，f 是G到S的一個映射，f (G)=S，則稱G與S同態(tài)，f 是G到S的一個同態(tài)映射。二、群同態(tài) 如果(G,*)和(S, )是兩群，且G與