為什么要研究代數(shù)系統(tǒng).doc

、為什么要研究代數(shù)系統(tǒng)？答：代數(shù)是專門研究離散對(duì)象的數(shù)學(xué)，是對(duì)符號(hào)的操作。它是現(xiàn)代數(shù)學(xué)的三大支柱之一（另兩個(gè)為分析與幾何）。代數(shù)從19世紀(jì)以來(lái)有驚人的發(fā)展，帶動(dòng)了整個(gè)數(shù)學(xué)的現(xiàn)代化。隨著信息時(shí)代的到來(lái)，計(jì)算機(jī)、信息都是數(shù)字（離散化）的，甚至電視機(jī)攝像機(jī)、照相機(jī)都在數(shù)字化。知識(shí)經(jīng)濟(jì)有人也稱為數(shù)字經(jīng)濟(jì)。這一切的背后的科學(xué)基礎(chǔ)，就是數(shù)學(xué)，尤其是專門研究離散對(duì)象的代數(shù)。代數(shù)發(fā)端于“用符號(hào)代替數(shù)”，后來(lái)發(fā)展到以符號(hào)代替各種事物。在一個(gè)非空集合上，確定了某些運(yùn)算以及這些運(yùn)算滿足的規(guī)律，于是該非空集合中的元素就說(shuō)是有了一種代數(shù)結(jié)構(gòu)?，F(xiàn)實(shí)世界中可以有許多具體的不相同的代數(shù)系統(tǒng)。但事實(shí)上，不同的代數(shù)系統(tǒng)可以有一些共同的性質(zhì)。正因?yàn)榇耍覀円芯砍橄蟮拇鷶?shù)系統(tǒng)，并假設(shè)它具有某一類具體代數(shù)系統(tǒng)共同擁有的性質(zhì)。任何在這個(gè)抽象系統(tǒng)中成立的結(jié)論，均可適用于那一類代數(shù)系統(tǒng)中的任何一個(gè)。2、代數(shù)的歷史代數(shù)學(xué)歷史悠久。代數(shù)的發(fā)展可分成兩個(gè)階段。19世紀(jì)這前的代數(shù)稱為古典代數(shù)，19世紀(jì)至今的代數(shù)稱為近世代數(shù)（抽象代數(shù)）。遠(yuǎn)在古希臘時(shí)期，人們就知道可以用符號(hào)代表所解問(wèn)題中的未知數(shù)，并且這些符號(hào)可以像數(shù)一樣進(jìn)行運(yùn)算，直到獲得問(wèn)題的解。古典代數(shù)的基本研究對(duì)象是方程，它是以討論方程的解法為中心。在古典代數(shù)中，每一個(gè)符號(hào)代表的總是一個(gè)數(shù)，但這個(gè)數(shù)可以是整數(shù)也可以是實(shí)數(shù)。古典代數(shù)的主要目標(biāo)是用代數(shù)運(yùn)算解一元多次方程。它成功地解決了一元二次、一元三次和一元四次方程的求解問(wèn)題。19世紀(jì)初，人們逐漸認(rèn)識(shí)到，符號(hào)不僅可以代表數(shù)，而且可以代表任何事物。在這種思想認(rèn)識(shí)的支配下，人們開(kāi)始將任意集合上所進(jìn)行的代數(shù)運(yùn)算作為研究的對(duì)象，從而出現(xiàn)了近世代數(shù)體系和方法。19世紀(jì)30年代，在尋找一元五次方程根式求解方法的過(guò)程中，年青的法國(guó)數(shù)學(xué)家伽羅瓦(E. Galois)首次得出了群的概念用置換群的方法徹底證明了高于四次的代數(shù)方程的根式不可解性。起初他的奇思妙想和巧妙方法雖然并不被當(dāng)時(shí)人接受和理解，卻發(fā)展出了一門新的學(xué)科-抽象代數(shù)學(xué)。抽象代數(shù)學(xué)的研究對(duì)象是抽象的，它不是以某一具體事物為研究對(duì)象，而是以一大類具有共同性質(zhì)的事物為研究對(duì)象。因此其研究成果適用于這一類事物中的每一個(gè)，從而收到事半功倍之效。抽象代數(shù)學(xué)的主要內(nèi)容是研究各種各樣的代數(shù)系統(tǒng)。它把一些形式上很不相同的代數(shù)系統(tǒng)，用統(tǒng)一的方法描述、研究和推理，從而得到反映出它們共性的一些本質(zhì)的結(jié)論，然后再把這些結(jié)論應(yīng)用到具體的代數(shù)系統(tǒng)中。從而抽象產(chǎn)生了廣泛的應(yīng)用。3、抽象代數(shù)學(xué)在計(jì)算機(jī)中的應(yīng)用100多年來(lái)，隨著科學(xué)的發(fā)展，抽象代數(shù)越來(lái)越顯示出它在數(shù)學(xué)的各個(gè)分支、物理學(xué)、化學(xué)、力學(xué)、生物學(xué)等科學(xué)領(lǐng)域的重要作用。抽象代數(shù)的概念和方法也是研究計(jì)算科學(xué)的重要數(shù)學(xué)工具。有經(jīng)驗(yàn)和成熟的計(jì)算科學(xué)家都知道，除了數(shù)理邏輯處，對(duì)計(jì)算科學(xué)最有用的數(shù)學(xué)分支學(xué)就是代數(shù)，特別是抽象代數(shù)。抽象代數(shù)是關(guān)于運(yùn)算的學(xué)問(wèn)，是關(guān)于計(jì)算規(guī)則的學(xué)問(wèn)。在許多實(shí)際問(wèn)題的研究中都離不開(kāi)數(shù)學(xué)模型，而構(gòu)造數(shù)學(xué)模型就要用到某種數(shù)學(xué)結(jié)構(gòu)，而抽象世代數(shù)研究的中心問(wèn)題就是一種很重要的數(shù)學(xué)結(jié)構(gòu)-代數(shù)系統(tǒng)：半群、群、格與布爾代數(shù)等等。計(jì)算科學(xué)的研究也離不開(kāi)抽象代數(shù)的應(yīng)用：半群理論在自動(dòng)機(jī)理論和形式語(yǔ)言中發(fā)揮了重要作用；有限域理論是編碼理論的數(shù)學(xué)基礎(chǔ)，在通訊中起過(guò)重要的作用；至于格和布爾代數(shù)則更不用說(shuō)了，是電子線路設(shè)計(jì)、電子計(jì)算機(jī)硬件設(shè)計(jì)和通訊系統(tǒng)設(shè)的重要工具。另外描述機(jī)器可計(jì)算的函數(shù)、研究算術(shù)計(jì)算的復(fù)雜性、刻畫(huà)抽象數(shù)據(jù)結(jié)構(gòu)、描述作為程序設(shè)計(jì)基礎(chǔ)的形式語(yǔ)義學(xué)，都需要抽象代數(shù)知識(shí)。4、布爾代數(shù)在邏輯線路中的應(yīng)用19世紀(jì)50年代，只受過(guò)初級(jí)數(shù)學(xué)教育、自學(xué)成才的英國(guó)人喬治.布爾（George Boole）先后發(fā)表了邏輯之?dāng)?shù)學(xué)分析(The Mathematical Analysis of Logic)和思維規(guī)律(The Laws of Thought)這兩部杰作。他創(chuàng)造出了一套符號(hào)系統(tǒng)，利用符號(hào)來(lái)表示邏輯中的各種概念。并且建立了一系列的運(yùn)算法則，利用代數(shù)方法研究邏輯問(wèn)題，初步奠定了數(shù)理邏輯的基礎(chǔ)。布爾代數(shù)從此問(wèn)世，數(shù)學(xué)史上樹(shù)起了一座新的里程碑。布爾將邏輯推理過(guò)程簡(jiǎn)化成極為容易和簡(jiǎn)單的一種代數(shù)運(yùn)算。他規(guī)定在布爾代數(shù)中：1)所有可能出現(xiàn)的數(shù)只有0和1兩個(gè)；2)基本運(yùn)算只有“與”、“或”、“非”三種；在布爾代數(shù)中用等式表示命題，把推理過(guò)程看作等式的變換。這種變換只依賴于基本運(yùn)算的性質(zhì)。在其誕生100多年后才發(fā)現(xiàn)其應(yīng)用和價(jià)值。雖然在布爾代數(shù)剛剛問(wèn)世的時(shí)間里并沒(méi)有受到人們應(yīng)有的重視，但布爾仍然堅(jiān)信自己的研究會(huì)對(duì)后世有相當(dāng)大的幫助。隨著布爾的去世，人們對(duì)布爾代數(shù)的了解也越來(lái)越少，直到20世紀(jì)初羅素在自己的數(shù)學(xué)原理中重新提到了布爾代數(shù)的名稱才引起了世人足夠的關(guān)注。但是，此時(shí)距布爾去世早已相隔多年。對(duì)計(jì)算科學(xué)而言，布爾代數(shù)的重要性是不言而喻的。布爾代數(shù)也確實(shí)是在其誕生100多年后才在計(jì)算機(jī)的發(fā)展中找到了它的用武之地，它為電子數(shù)字計(jì)算機(jī)開(kāi)關(guān)電路設(shè)計(jì)提供了最重要的數(shù)學(xué)方法。1938年，美國(guó)數(shù)學(xué)家、信息論創(chuàng)始人香農(nóng)(C. Shannon)發(fā)表了著名的論文繼電器和開(kāi)關(guān)電路的符號(hào)分析(A Symbolic Analysis of Relay and Switching Circuits)，首次用布爾代數(shù)進(jìn)行開(kāi)關(guān)電路分析。由于布爾代數(shù)只有0和1兩個(gè)值，恰好與二進(jìn)制數(shù)對(duì)應(yīng)，香農(nóng)把它運(yùn)用于以脈沖方式處理信息的繼電器開(kāi)關(guān)。并證明布爾代數(shù)的邏輯運(yùn)算，可以通過(guò)繼電器電路來(lái)實(shí)現(xiàn)，明確地給出了實(shí)現(xiàn)加、減、乘、除等運(yùn)算的電子電路的設(shè)計(jì)方法，從而從理論到技術(shù)徹底改變了數(shù)字電路的設(shè)計(jì)方向。這篇論文成為開(kāi)關(guān)電路理論的開(kāi)端，在現(xiàn)代電子數(shù)字計(jì)算機(jī)史上具有劃時(shí)代的意義。 香農(nóng)在貝爾實(shí)驗(yàn)室工作中進(jìn)一步證明，可以采用能實(shí)現(xiàn)布爾代數(shù)運(yùn)算的繼電器或電子元件來(lái)制造計(jì)算機(jī)。香農(nóng)的理論還為計(jì)算機(jī)邏輯功能的設(shè)計(jì)奠定了基礎(chǔ)，從而使電子計(jì)算機(jī)既能用于數(shù)值計(jì)算，又具有各種非數(shù)值應(yīng)用功能，使得以后的計(jì)算機(jī)在幾乎任何領(lǐng)域中，都得到廣泛應(yīng)用。今天，所有的電子計(jì)算機(jī)芯片里使用的成千上萬(wàn)個(gè)微小的邏輯部件，都是由各種布爾邏輯元件邏輯門和觸發(fā)器組成的。由邏輯元件可以組成各種邏輯網(wǎng)絡(luò)，這樣任何復(fù)雜的邏輯關(guān)系都可以由邏輯元件經(jīng)過(guò)相應(yīng)的組合來(lái)實(shí)現(xiàn)，使其具有復(fù)雜的邏輯判斷功能。5、半群與文法及形式語(yǔ)言計(jì)算機(jī)可以完成很多任務(wù)。但是給定一個(gè)任務(wù)，我們面臨的第一個(gè)問(wèn)題是：它是否可以用計(jì)算機(jī)來(lái)解決？若可以的話，我們就要考慮第二個(gè)問(wèn)題：如何解決。這些問(wèn)題的回答都和計(jì)算模型有關(guān)。一般有三種類型的計(jì)算模型：文法(Grammars)、有限狀態(tài)機(jī)(Finite-state Machines)和圖靈機(jī)(Turing Machines)。其中文法是用來(lái)生成一門語(yǔ)言的所有詞匯和判斷一個(gè)詞匯是否在一門語(yǔ)言中。方法產(chǎn)生形式語(yǔ)言，而形式語(yǔ)言既為象英語(yǔ)這樣的自然語(yǔ)言提供了模型，又為象PASCAL，C，PROLOG和JAVA這樣的編程語(yǔ)言提供了模型。在編譯原理和匯編程序的創(chuàng)造中，文法有著不可替代的作用。設(shè)是一個(gè)非空有限集合，稱為字母表，由中有限個(gè)字母組成的有序集合（即字符串）稱為上的一個(gè)字，串中的字母?jìng)€(gè)數(shù)m稱為字長(zhǎng)，m=0時(shí)，稱為空字，記為 。 表示上的字的集合， 上的連接運(yùn)算 定義為， ， =，則是一個(gè)代數(shù)系統(tǒng)，而且是一個(gè)獨(dú)異點(diǎn)。 的任一子集就稱為語(yǔ)言。我們將利用文法來(lái)給定一門語(yǔ)言。一個(gè)文法給出了一個(gè)字母表（用來(lái)產(chǎn)生語(yǔ)言中詞的符號(hào)集合），和一個(gè)產(chǎn)生詞的規(guī)則集。一個(gè)文法是一個(gè)四元組G=（，T，s，P），其中是字母表，T是的子集，它的元素是終止符（它不能再被中其它字符代替），s是的一個(gè)元素，它是初始符，P是所謂生成規(guī)則的集合（生成規(guī)則實(shí)質(zhì)上就是語(yǔ)言的短語(yǔ)構(gòu)成規(guī)則，它們決定 中的一個(gè)字符串可以被 中的哪個(gè)符號(hào)串替換）。N=-T中的元素稱為非終止符（它能被中其它字符代替），P中的每個(gè)產(chǎn)生式的左端至少要有一非終止符。定義了一門語(yǔ)言的文法后，利用產(chǎn)生式，我們就可以從初始符號(hào)s出發(fā)演繹出一個(gè)一個(gè)詞，從而確定由該文法產(chǎn)生出來(lái)的語(yǔ)言。設(shè)G=（，T，s，P）是一個(gè)文法，則由G產(chǎn)生的語(yǔ)言L（G）就是能由初始符號(hào)s演繹出來(lái)的所有字符串的集合，即L（G）= T | s 。6、糾錯(cuò)碼中的群碼由于在計(jì)算機(jī)中和通訊系統(tǒng)中信號(hào)傳遞非常頻繁與廣泛，因此如何防止傳輸錯(cuò)誤是一件很重要的事情。當(dāng)然，要解決這個(gè)問(wèn)題可以有不同的途徑。其中的一個(gè)途徑就是采用糾錯(cuò)碼(Error Correcting Code)，即從編碼上下功夫，使得二進(jìn)制數(shù)碼一旦在傳遞過(guò)程中出錯(cuò)，接收端的糾錯(cuò)碼裝置就能立即發(fā)現(xiàn)錯(cuò)誤，并將其糾正。當(dāng)二進(jìn)制信號(hào)串從發(fā)送端發(fā)出時(shí)，需要按規(guī)定具有干擾能力的糾錯(cuò)碼，然后才能發(fā)送出去。在接收端，當(dāng)接收到二進(jìn)制信號(hào)串后立即對(duì)收到的糾錯(cuò)碼進(jìn)行檢查，檢查是否失真，若失真則要負(fù)責(zé)糾正。這就是在計(jì)算機(jī)和數(shù)據(jù)通訊系統(tǒng)中被廣泛采用的方法。我們先舉一個(gè)日常生活中的實(shí)例。如果你發(fā)出一個(gè)通知：“明天14：00-16：00開(kāi)會(huì)”，但在通知過(guò)程中由于某種原因產(chǎn)生了錯(cuò)誤，變成“明天10：00-16：00開(kāi)會(huì)”。別人收到這個(gè)錯(cuò)誤通知后由于無(wú)法判斷其正確與否，就會(huì)按這個(gè)錯(cuò)誤時(shí)間去行動(dòng)。為了使收者能判斷正誤，可以在發(fā)通知內(nèi)容中增加“下午”兩個(gè)字，即改為：“明天下午14:00-16:00開(kāi)會(huì)”，這時(shí)，如果仍錯(cuò)為：“明天下午10:00-16:00開(kāi)會(huì)”，則收到此通知后根據(jù)“下午”兩字即可判斷出其中“10:00”發(fā)生了錯(cuò)誤。但仍不能糾正其錯(cuò)誤，因?yàn)闊o(wú)法判斷“10:00”錯(cuò)在何處，即無(wú)法判斷原來(lái)到底是幾點(diǎn)鐘。這時(shí)，收者可以告訴發(fā)端再發(fā)一次通知，這就是檢錯(cuò)重發(fā)。為了實(shí)現(xiàn)不但能判斷正誤(檢錯(cuò))，同時(shí)還能改正錯(cuò)誤(糾錯(cuò))，可以把發(fā)的通知內(nèi)容再增加“兩個(gè)小時(shí)”四個(gè)字，即改為：“明天下午14:0016:00兩個(gè)小時(shí)開(kāi)會(huì)”。這樣，如果其中“14:00”錯(cuò)為“10:00”，不但能判斷出錯(cuò)誤，同時(shí)還能糾正錯(cuò)誤，因?yàn)槠渲性黾拥摹?兩個(gè)小時(shí)”四個(gè)字可以判斷出正確的時(shí)間為14:0016:00”。 通過(guò)上例可以說(shuō)明，為了能判斷傳送的信息是否有誤，可以在傳送時(shí)增加必要的附加判斷數(shù)據(jù)；如果又能糾正錯(cuò)誤，則需要增加更多的附加判斷數(shù)據(jù)。這些附加數(shù)據(jù)在不發(fā)生誤碼的情況之下是完全多余的，但如果發(fā)生誤碼，即可利用被傳信息數(shù)據(jù)與附加數(shù)據(jù)之間的特定關(guān)系來(lái)檢出錯(cuò)誤和糾正錯(cuò)誤。具體地講就是：為了使信源代碼具有檢錯(cuò)和糾錯(cuò)能力，應(yīng)當(dāng)按一定的規(guī)則在信源編碼的基礎(chǔ)上增加一些冗余碼元(又稱監(jiān)督碼)，使這些冗余碼元與被傳送信息碼元之間建立一定的關(guān)系，發(fā)送端完成這個(gè)任務(wù)的過(guò)程就稱為誤碼控制編碼；在接收端，根據(jù)信息碼元與監(jiān)督碼元的特定關(guān)系，實(shí)現(xiàn)檢錯(cuò)或糾錯(cuò)，輸出原信息碼元，完成這個(gè)任務(wù)的過(guò)程就稱誤碼控制譯碼(或解碼)。 另外，無(wú)論檢錯(cuò)和糾錯(cuò)，都有一定的誤別范圍，如上例中，若開(kāi)會(huì)時(shí)間錯(cuò)為“16:0018:00”，則無(wú)法實(shí)現(xiàn)檢錯(cuò)與糾錯(cuò)，因?yàn)檫@個(gè)時(shí)間也同樣滿足附加數(shù)據(jù)的約束條件，這就應(yīng)當(dāng)增加更多的附加數(shù)據(jù)(即冗余碼元)。我們已知，信源編碼的中心任務(wù)是消去冗余，可是為了檢錯(cuò)與糾錯(cuò)，又不得不增加冗余，這又必然導(dǎo)致傳輸效率降低，顯然這是個(gè)矛盾。我們分析誤碼控制編碼的目的，正是為了尋求較好的編碼方式，能在增加冗余不 太多的前提下來(lái)實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)。設(shè)信息以字(Word)為單位進(jìn)行傳輸，每個(gè)字是一個(gè)m二進(jìn)制數(shù)，每個(gè)二進(jìn)制位稱為碼元(Code Letter)?，F(xiàn)在選擇整數(shù)nm，構(gòu)造一個(gè)一對(duì)一函數(shù)e:B B (其中B=0,1,B 是所有的m位二進(jìn)制數(shù)集，B 是所有的n位二進(jìn)制數(shù)集)。稱e為(m,n)編碼函數(shù)，通過(guò)它我們用一個(gè)n位二進(jìn)制數(shù)代表一個(gè)m位二進(jìn)制數(shù)。若b B ，則稱e(b)是代表b的碼字(code word)，e(b)中的冗余碼元將有助于檢出或糾正傳輸過(guò)程中產(chǎn)生的誤碼。在B 上定義二元運(yùn)算 ：X= x x x , Y=y y y B ,Z= X Y=z z z ，其中z =x + y (k=1,2,n)(即 是n位二進(jìn)制數(shù)的按位模2加法)。則（B ； ）是一個(gè)群，000是運(yùn)算 *的單位元，每個(gè)元素的逆元是它本身（每個(gè)非單位元的階是2）。同樣（B ； ）也是一個(gè)群。若(m,n)編碼函數(shù)e:B B 滿足C=e(B )=e(b)|b B =Ran(e)是B 的子群，則稱C一個(gè)群碼(Group Code)。在計(jì)算機(jī)中經(jīng)常使用的漢明碼(Hamming Code)就是一種群碼。它就利用群的性質(zhì)實(shí)現(xiàn)糾錯(cuò)。7、布爾代數(shù)在開(kāi)關(guān)電路設(shè)計(jì)中的應(yīng)用開(kāi)關(guān)是一種具有一個(gè)輸入和一個(gè)輸出的器件，我們將若干個(gè)開(kāi)關(guān)的串聯(lián)與并聯(lián)構(gòu)成的電路稱為開(kāi)關(guān)電路(Switching Circuits)。整個(gè)開(kāi)關(guān)電路從功能上可看作是一個(gè)開(kāi)關(guān)，把電路接通記為1，把電路斷開(kāi)記為0。而開(kāi)關(guān)電路中的開(kāi)關(guān)也要么處于接通狀態(tài)，要么處于斷開(kāi)狀態(tài)，這兩種狀態(tài)也可以用二值布爾代數(shù)來(lái)描述。一個(gè)具有n個(gè)獨(dú)立開(kāi)關(guān)組成的開(kāi)關(guān)電路稱為n元開(kāi)關(guān)電路。整個(gè)開(kāi)關(guān)電路是否接通完全取決于這些開(kāi)關(guān)的狀態(tài)以及連接方式（串聯(lián)、并聯(lián)或反