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

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