計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)第4編群

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

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

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

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

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

6、 則稱運(yùn)算 滿足分配律。,[2000年1月選擇題4] 定義在實(shí)數(shù)集R上的二元運(yùn)算*為 ，則二元運(yùn)算同時(shí)滿足交換律和結(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上定義二元運(yù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、如果 ，則稱運(yùn)算 滿足吸收律， 如果 ，則稱為運(yùn)算 的左單位元， 如果

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

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

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

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

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

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

15、構(gòu)成群的是 。(Mn(R),+)，其中Mn(R)是定義在實(shí)數(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í)數(shù)集，定義在R×R上的二元關(guān)系如下：證明(R×R, )是群。證明： 滿足結(jié)合律，∴ (R×R, )是半群， ∴是單位元，

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

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

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

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

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

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