第9章 群環(huán)域-《離散數(shù)學(xué)（微課版）》教學(xué)課件

《離散數(shù)學(xué)》第九章群環(huán)域內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5群論的誕生16世紀(jì)，四次以下的方程均已得到解決。但在隨后的幾個(gè)世紀(jì)，5次及以上方程的一般解法均沒(méi)有得到解決。1770年前后，法國(guó)數(shù)學(xué)家拉格朗日轉(zhuǎn)變代數(shù)的思維方法，提出方程根的排列與置換理論是解代數(shù)方程的關(guān)鍵所在，他的工作有力地促進(jìn)了代數(shù)方程論的進(jìn)步。相繼魯菲尼和高斯都在這方面進(jìn)行了研究.1824年到1826年，挪威數(shù)學(xué)家阿貝爾得到嚴(yán)格證明：如果一個(gè)方程可以根式求解，則出現(xiàn)在根的表達(dá)式中的每個(gè)根式都可表示成方程的根和某些單位根的有理函數(shù)。并進(jìn)一步得到阿貝爾定理：一般高于四次的方程不可能代數(shù)地求解。群論的誕生阿貝爾解決了構(gòu)造任意次數(shù)的代數(shù)可解的方程的問(wèn)題，卻沒(méi)能解決判定已知方程是否可用根式求解的問(wèn)題。法國(guó)數(shù)學(xué)家伽羅瓦正是處在這樣的背景下，開(kāi)始接手阿貝爾未競(jìng)的事業(yè)。他提出了群的概念，用群的理論徹底解決了根式求解代數(shù)方程的問(wèn)題，并且由此發(fā)展了一整套關(guān)于群和域的理論。后人為了紀(jì)念他，將這套理論稱(chēng)之為伽羅瓦理論。這個(gè)理論可以推導(dǎo)出五次以上的一般代數(shù)方程根式不可解以及用圓規(guī)、直尺(無(wú)刻度的尺)三等分任意角和作倍立方體不可能等結(jié)論．重要的群及其應(yīng)用重要的群：代數(shù)方程群，點(diǎn)群和空間群、線(xiàn)性群和矩陣群、正交群、幺正群、李群、轉(zhuǎn)動(dòng)群、辛群、同倫群、有限單群，。。。

應(yīng)用：高次方程的一般解，尺規(guī)作圖，物理中的晶體分類(lèi)，原子核的自旋和轉(zhuǎn)動(dòng)，基本粒子的結(jié)構(gòu)模型，偏微分方程求解，信息通信中的編碼理論，對(duì)稱(chēng)互聯(lián)網(wǎng)及其優(yōu)化問(wèn)題，凸幾何和流形上的拓?fù)?，。。。重點(diǎn)1各類(lèi)群環(huán)域相關(guān)的判定和證明2各類(lèi)子代數(shù)的判定和證明（含子群、子環(huán)等）3群的同態(tài)和同構(gòu)的證明4循環(huán)群的生成元計(jì)算5置換群的輪換表示、奇偶性和類(lèi)型判定6陪集計(jì)算和拉格朗日定理的應(yīng)用難點(diǎn)1群和子群的判定及證明2各類(lèi)特殊群和元素的階相關(guān)的綜合證明3與陪集和拉格朗日定理相關(guān)的綜合證明

學(xué)習(xí)要求內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5伽羅瓦埃瓦里斯特·伽羅瓦（1811-1832），法國(guó)數(shù)學(xué)家，群論和域論創(chuàng)始人：1811年10月25日出生于法國(guó)巴黎近郊，母親擔(dān)負(fù)起他的早期教育，直到12歲才進(jìn)入學(xué)校，16歲開(kāi)始學(xué)習(xí)數(shù)學(xué)。伽羅瓦非常有數(shù)學(xué)天賦，據(jù)說(shuō)通常需要用兩年學(xué)習(xí)的課本《幾何學(xué)原理》，伽羅瓦只用兩天就學(xué)完了。他的學(xué)校老師給出的評(píng)價(jià)是：該生只適合在數(shù)學(xué)的最高領(lǐng)域工作。17歲時(shí)，伽羅瓦已經(jīng)開(kāi)始研究一般的一元五次方程求解的問(wèn)題，并提交了2篇論文給法國(guó)科學(xué)院，但竟然陰差陽(yáng)錯(cuò)的丟失了（柯西，傅里葉）。1831年，伽羅瓦又給法國(guó)科學(xué)院送呈了一篇名為“關(guān)于方程根式可解的條件”的論文，這次由泊松和拉克魯瓦評(píng)審，但最終的結(jié)論是：他們無(wú)法看懂伽羅瓦的證明。伽羅瓦埃瓦里斯特·伽羅瓦（1811-1832），法國(guó)數(shù)學(xué)家，群論和域論創(chuàng)始人：但伽羅瓦已經(jīng)沒(méi)有時(shí)間了，1832年，他在一次愚蠢的決斗中失去了生命。1843年，法國(guó)科學(xué)家劉維爾在法國(guó)科學(xué)院做報(bào)告，他的開(kāi)頭是：“我希望我這一宣布能使在座的各位院士們深感興趣，在伽羅瓦的論文中我發(fā)現(xiàn)了，他

有多精確就有多深刻精辟

證明了下述優(yōu)美定理：對(duì)給定的一個(gè)素?cái)?shù)次不可約方程能判斷出它是否能根式求解”。三年后，劉維爾出版了伽羅瓦的全部論文。1856年起，德國(guó)和法國(guó)的高等學(xué)府中開(kāi)始開(kāi)設(shè)伽羅瓦理論的高級(jí)課程。伽羅瓦，終于名震世界。他用短短的4年，摘取了數(shù)學(xué)史上一頂璀璨的桂冠。伽羅瓦的遺書(shū)

我請(qǐng)求我的愛(ài)國(guó)同胞們，我的朋友們，不要指責(zé)我不是為我的國(guó)家而死。

我是作為一個(gè)不名譽(yù)的風(fēng)騷女人和她的兩個(gè)受騙者的犧牲品而死的。我將在可恥的誹謗中結(jié)束我的生命。噢!為什么要為這么微不足道的，這么可鄙的事去死呢?我懇求蒼天為我作證，只有武力和強(qiáng)迫才使我在我曾想方設(shè)法避開(kāi)的挑釁中倒下。

我親愛(ài)的朋友:

我已經(jīng)得到分析學(xué)方面的一些新發(fā)現(xiàn).....

在我一生中，我常常敢于預(yù)言當(dāng)時(shí)我還不十分有把握的一些命題。但是我在這里寫(xiě)下的這一切已經(jīng)清清楚楚地在我的腦海里一年多了，我不愿意使人懷疑我宣布了自己未完全證明的定理。

請(qǐng)公開(kāi)請(qǐng)求雅可比或高斯就這些定理的重要性(不是就定理的正確與否)發(fā)表他們的看法。然后，我希望有人會(huì)發(fā)現(xiàn)將這一堆東西整理清楚會(huì)是很有益處的一件事。阿貝爾尼爾斯·亨利克·阿貝爾（1802－1829），挪威數(shù)學(xué)家，橢圓函數(shù)領(lǐng)域開(kāi)拓者，代數(shù)方程論重大貢獻(xiàn)者1802年8月5日生于挪威芬島，父親是牧師，家境貧寒，啟蒙教育來(lái)自于父親。中學(xué)階段對(duì)開(kāi)始數(shù)學(xué)產(chǎn)生興趣。21歲時(shí)，他用反證法證明了“一般五次方程是不可根式求解的”，但因?yàn)榻?jīng)濟(jì)原因，不得不把論文壓縮到6頁(yè)，但這使得高斯不認(rèn)為這是可能的，直到1826年才發(fā)表在《純數(shù)學(xué)和應(yīng)用數(shù)學(xué)雜志》上。1826年，阿貝爾撰寫(xiě)了一篇關(guān)于超越函數(shù)的論文，參加法國(guó)科學(xué)院的數(shù)學(xué)大獎(jiǎng)賽，但柯西忘記評(píng)審，勒讓德則說(shuō)字跡看不清。阿貝爾尼爾斯·亨利克·阿貝爾（1802－1829），挪威數(shù)學(xué)家，橢圓函數(shù)領(lǐng)域開(kāi)拓者，代數(shù)方程論重大貢獻(xiàn)者1829年，年僅26歲的阿貝爾因感冒長(zhǎng)期沒(méi)有治愈引發(fā)的肺結(jié)核離世。1830年，法國(guó)科學(xué)院宣布阿貝爾和雅可比獲得數(shù)學(xué)大獎(jiǎng)。以阿貝爾命名的數(shù)學(xué)名詞：

阿貝爾群，阿貝爾積分，阿貝爾函數(shù)，阿貝爾積分方程，阿貝爾級(jí)數(shù)，阿貝爾部分和公式，阿貝爾基本定理，阿貝爾極限定理，阿貝爾可和性。2003年，一項(xiàng)專(zhuān)門(mén)為數(shù)學(xué)家設(shè)立的，獎(jiǎng)金高達(dá)80萬(wàn)美元的阿貝爾獎(jiǎng)在挪威奧斯陸開(kāi)始頒發(fā)。阿貝爾獎(jiǎng)和菲爾茲獎(jiǎng)、沃爾夫獎(jiǎng)一起，并稱(chēng)數(shù)學(xué)界三大獎(jiǎng)項(xiàng)。內(nèi)容導(dǎo)航CONTENTS群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5歷史人物本章導(dǎo)讀及學(xué)習(xí)要求引言結(jié)合律有幺元單位元利用代數(shù)系統(tǒng)滿(mǎn)足的運(yùn)算律以及具有的特殊元素對(duì)代數(shù)系統(tǒng)進(jìn)行分類(lèi)研究。有幺元逆元群論

群的定義

群的定義

封閉性結(jié)合律單位元每個(gè)元素有逆元交換律解題小貼士數(shù)群

Klein四元群

*eabceeabcaaecbbbceaccbae

一個(gè)群的運(yùn)算表稱(chēng)為群表。此群稱(chēng)為Klein四元群，也是一個(gè)可換群。整數(shù)模n同余類(lèi)加法群

整數(shù)模n同余類(lèi)加法群

整數(shù)模n同余類(lèi)乘法群

整數(shù)模n同余類(lèi)乘法群

對(duì)稱(chēng)群

N次全線(xiàn)性群

群的性質(zhì)

群的性質(zhì)

約定

元素的冪

元素的階

000000000000001012345012345020240240240240303030303030304042042042042050543210543210元素的階

計(jì)算元素的階

元素的階的性質(zhì)

元素的階的性質(zhì)

子群的定義

子群的判定

子群的判定

有限子群的判定

解題小貼士子群的判定子群的判定

子群的判定

子群的判定

子群的性質(zhì)(保守性)

子群的性質(zhì)(保守性)

群的同態(tài)和同構(gòu)定義

應(yīng)用代數(shù)系統(tǒng)的同態(tài)與同構(gòu)的概念，可以得到群的同態(tài)和同構(gòu)的定義：群同態(tài)和同構(gòu)的判定

群同態(tài)的性質(zhì)

同態(tài)核

群同構(gòu)

如果兩個(gè)群同構(gòu)，則這兩個(gè)群在同構(gòu)的意義下可以看作是相同的群。群表中每行的元素應(yīng)互不相同，每列的元素也應(yīng)互不相同。內(nèi)容導(dǎo)航CONTENTS群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5歷史人物本章導(dǎo)讀及學(xué)習(xí)要求特殊群循環(huán)群：較簡(jiǎn)單，結(jié)構(gòu)確定置換群：應(yīng)用廣泛，任何有限群可轉(zhuǎn)換為置換群循環(huán)群的定義

循環(huán)群的判定

解題小貼士循環(huán)群的判定循環(huán)群的判定

典型循環(huán)群

循環(huán)群的性質(zhì)

有限循環(huán)群的性質(zhì)

有時(shí)候，此定理可用于證明某個(gè)有限群是循環(huán)群。類(lèi)似的，可知無(wú)限階循環(huán)群的生成元的階必然是無(wú)限的。循環(huán)群的同構(gòu)

循環(huán)群的生成元

循環(huán)群的子群

循環(huán)群的子群

解題小貼士計(jì)算循環(huán)群的所有生成元和子群的方法特殊群循環(huán)群：較簡(jiǎn)單，結(jié)構(gòu)確定置換群：應(yīng)用廣泛，任何有限群可轉(zhuǎn)換為置換群對(duì)稱(chēng)群

圖形的對(duì)稱(chēng)性圖形變換等腰三角形正方形圖形的對(duì)稱(chēng)性方程復(fù)根的對(duì)稱(chēng)性

置換群定義

回顧置換的定義

輪換和對(duì)換的定義

一個(gè)置換可表示為一些輪換或?qū)Q的乘積。置換的分解

置換的分解

置換的奇偶性

置換的奇偶性

置換的類(lèi)型

二面體群

二面體群

二面體群

二面體群這些置換的類(lèi)型如下：置換類(lèi)型二面體群

凱萊定理

凱萊定理

凱萊定理例9.18求與Klein四元群同構(gòu)的置換群。

內(nèi)容導(dǎo)航CONTENTS群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5歷史人物本章導(dǎo)讀及學(xué)習(xí)要求引言

首先考慮一個(gè)立體幾何中的例子

引言

陪集的定義

顯然，當(dāng)G是可換群時(shí)，子群H的左、右陪集相等。陪集計(jì)算

陪集計(jì)算

陪集的性質(zhì)

解題小貼士求所有左右陪集的方法陪集

陪集

拉格朗日定理

拉格朗日定理的推論

拉格朗日定理的應(yīng)用

這個(gè)例子證明了四元群在同構(gòu)的意義上，只有兩個(gè)：四階循環(huán)群或Klein四元群。內(nèi)容導(dǎo)航CONTENTS群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5歷史人物本章導(dǎo)讀及學(xué)習(xí)要求正規(guī)子群的定義

正規(guī)子群的判定

正規(guī)子群的判定

正規(guī)子群的判定

正規(guī)子群的判定

商群的定義

商群的定義

商群的定義

自然映射

同態(tài)基本定理

同態(tài)基本定理

同態(tài)基本定理同態(tài)基本定理不但指出了由商群得到的同構(gòu)關(guān)系，還可根據(jù)此定理推導(dǎo)出兩個(gè)群同態(tài)的子群和商群之間的對(duì)應(yīng)關(guān)系，對(duì)分析群的結(jié)構(gòu)和性質(zhì)有十分關(guān)鍵的意義。內(nèi)容導(dǎo)航CONTENTS群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5歷史人物本章導(dǎo)讀及學(xué)習(xí)要求引言群論：只具有一個(gè)二元運(yùn)算的代數(shù)結(jié)構(gòu)，但無(wú)法描述多個(gè)運(yùn)算之間的關(guān)聯(lián)。環(huán)和域：具有兩個(gè)二元運(yùn)算的代數(shù)結(jié)構(gòu)。環(huán)和域建立在群的基礎(chǔ)上，所以它的很多基本概念和理論是群論相應(yīng)內(nèi)容的推廣。同時(shí)，環(huán)和域也有自己的應(yīng)用領(lǐng)域，如因子分解問(wèn)題，計(jì)算機(jī)密碼學(xué)等。環(huán)的定義

典型的環(huán)

典型的環(huán)

典型的環(huán)

重要約定

環(huán)中的減法

可見(jiàn)，0在加法中作為單位元，但對(duì)于乘法來(lái)講是零元。零因子

零因子與消去律

各種特殊環(huán)、域

有限域

子環(huán)的定義群論：子群、正規(guī)子群和商群環(huán)論：子環(huán)、理想和商環(huán)

子環(huán)的判定

理想的定義

理想的判定

理想的判定

理想的判定

商環(huán)

商環(huán)

環(huán)的同態(tài)與同構(gòu)

同態(tài)核及同態(tài)基本定理

與群同態(tài)的同態(tài)核是正規(guī)子群類(lèi)似，環(huán)同態(tài)的同態(tài)核是一個(gè)理想，從而環(huán)A關(guān)于同態(tài)核K可形成一個(gè)商環(huán)A/K。同態(tài)的尋找

同態(tài)的尋找

同態(tài)的尋找

內(nèi)容導(dǎo)航CONTENTS群的基本概念特殊群陪集與拉格朗日定理群環(huán)域的應(yīng)用

9.1

9.2

9.3

9.6作業(yè)

9.7正規(guī)子群與商群環(huán)和域

9.4

9.5歷史人物本章導(dǎo)讀及學(xué)習(xí)要求計(jì)數(shù)問(wèn)題(*)

項(xiàng)鏈問(wèn)題這個(gè)問(wèn)題的數(shù)學(xué)描述是，m顆珠子做成一個(gè)項(xiàng)鏈，可用一個(gè)正m邊形來(lái)表示，每個(gè)頂點(diǎn)代表一顆珠子。從任意一個(gè)頂點(diǎn)開(kāi)始，沿逆時(shí)針?lè)较?，每個(gè)頂點(diǎn)用1,2,…,m來(lái)標(biāo)號(hào)。這樣的一個(gè)有標(biāo)號(hào)項(xiàng)鏈中，每一顆珠子有n種選擇，所以總共有nm種。但是，有一些其實(shí)本質(zhì)上是一樣的，比如旋轉(zhuǎn)一個(gè)角度或者翻轉(zhuǎn)后就會(huì)重合。若只考慮本質(zhì)上不同的項(xiàng)鏈，當(dāng)n和m數(shù)值較大時(shí)，則很難用簡(jiǎn)單的枚舉方法來(lái)解決。群論方法是當(dāng)前解決這一類(lèi)問(wèn)題最為簡(jiǎn)單和有效的方法。二面體群Dn的一般表達(dá)形式

二面體群Dn的一般表達(dá)形式

二面體群Dn的一般表達(dá)形式

二面體群Dn的一般表達(dá)形式

項(xiàng)鏈問(wèn)題的解法

項(xiàng)鏈問(wèn)題的解法

多項(xiàng)式編碼各類(lèi)計(jì)算機(jī)終端設(shè)備間普遍采用數(shù)字信號(hào)進(jìn)行通信，但通信過(guò)程中有時(shí)會(huì)出現(xiàn)差錯(cuò)，比如受到電磁干擾或溫度、灰塵等環(huán)境的影響。這個(gè)問(wèn)題的解決有兩個(gè)方面：一是檢錯(cuò)，即能夠判斷所接收到的數(shù)據(jù)是否有錯(cuò)；二是糾錯(cuò)，在出錯(cuò)的時(shí)候改正錯(cuò)誤而不必重傳?；靖拍睿涸O(shè)用一個(gè)k位的二進(jìn)制數(shù)表示一個(gè)信息,稱(chēng)為一個(gè)k位信息碼,對(duì)每個(gè)信息碼附加n-k位用于檢錯(cuò)的二進(jìn)制數(shù)，構(gòu)成的n位二進(jìn)制數(shù)稱(chēng)為一個(gè)碼詞。這種碼稱(chēng)為(n,k)碼。由信息碼得到碼詞的過(guò)程稱(chēng)為編碼(encoding)。接收者收到碼詞經(jīng)過(guò)檢錯(cuò)后取出信息,此過(guò)程稱(chēng)為譯碼(decoding)。奇偶校驗(yàn)碼最常用也是最簡(jiǎn)單的方式是奇偶校驗(yàn)碼。原理：在k位信息碼后增加一位，使碼字中1的個(gè)數(shù)成奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。特點(diǎn)：只能檢測(cè)一位錯(cuò)誤，例如要傳輸?shù)男畔⑹?01，采用奇校驗(yàn)時(shí)，校驗(yàn)位為1，組成的碼詞為1011。當(dāng)傳輸受到干擾變成0011時(shí)，接收方發(fā)現(xiàn)1的個(gè)數(shù)是偶數(shù)，說(shuō)明傳輸數(shù)據(jù)出錯(cuò)，但無(wú)法判斷是哪一位出錯(cuò)，因而無(wú)法糾正。這種方法通常用于1個(gè)字符型數(shù)據(jù)的檢錯(cuò)，因而在傳輸速率不高的串行通信中應(yīng)用較多?；诙囗?xiàng)式環(huán)的循環(huán)碼--CRC（循環(huán)冗余校驗(yàn)碼）

CRC（循環(huán)冗余校驗(yàn)碼）CRC的生成和校驗(yàn)方法：選定一個(gè)n-k次多項(xiàng)式p(x)

Z2[x]作為生成多項(xiàng)式，（1）發(fā)送方生成：在k位信息碼后附加n-k個(gè)0，相當(dāng)于信息碼多項(xiàng)式m(x)乘以xn-k。然后用生成多項(xiàng)式p(x)去除xn-km(x)，得到余數(shù)多項(xiàng)式r(x)，r(x)對(duì)應(yīng)的就是n-k位校驗(yàn)碼。k位信息碼加上n-k位校驗(yàn)碼就構(gòu)成了要傳輸?shù)臄?shù)據(jù)幀。（2）接收方校驗(yàn)：用生成多項(xiàng)式p(x)去除接收到的數(shù)據(jù)多項(xiàng)式，如果余數(shù)為0，通過(guò)校驗(yàn)，去除n-k位校驗(yàn)位，接收k位信息碼。如果余數(shù)不為0，校驗(yàn)不通過(guò)，報(bào)告錯(cuò)誤。名稱(chēng)生成多項(xiàng)式CRC-8CRC-10CRC-12CRC-16CRC-CCITTC