【正文】 素 al1對(duì)于運(yùn)算 *是左可逆的，而 al1 稱為 a的左逆元；若存在元素 ar1?A，使得 a*ar1 =e，稱元素 ar1對(duì)于運(yùn)算 *是右可逆的，而 ar1 稱為 a的右逆元。據(jù)史料記載，巴比倫人很早就知道了求解二次方程，文藝復(fù)興時(shí)期的數(shù)學(xué)家也成功地找到了三次和四次方程式的通解。 19世紀(jì)初，包括法國數(shù)學(xué)家伽羅華（ ）在內(nèi)的不少數(shù)學(xué)家都在致力于這個(gè)問題的研究。于是，他轉(zhuǎn)向把問題抽象化，研究起方程式及其解的一般性質(zhì)，從而有了“群”的概念。 以伽羅華開創(chuàng)的群論為標(biāo)志，代數(shù)學(xué)（近世代數(shù)、或抽象代數(shù)）作為研究各種代數(shù)系統(tǒng)的科學(xué)，在計(jì)算領(lǐng)域得到了廣泛地應(yīng)用，如算法理論、網(wǎng)絡(luò)與通信理論、程序理論、密碼學(xué)、數(shù)字邏輯電路等。 定義 2 一個(gè)代數(shù)系統(tǒng) S， *，其中 S是非空集合， *是 S上的一個(gè)二元運(yùn)算。 則稱代數(shù)系統(tǒng) S， *為半群。 不難發(fā)現(xiàn)，半群是可結(jié)合的廣群，群是一個(gè)存在幺元且每一個(gè)元素都存在逆元的半群（如圖 ）?？梢杂眠@類系統(tǒng)解形如 ax=b的一元一次代數(shù)方程式的根（只須在等式的兩邊分別乘以 1/a）；而無法解形如 ax+b=c的一元一次代數(shù)方程式的根，這樣就得在系統(tǒng)中再引入一個(gè)減（ ）運(yùn)算（在等式兩邊分別減 b，然后在等式的兩邊再分別乘以 1/a）。當(dāng)然，環(huán)還要滿足一定的運(yùn)算性質(zhì)，這些內(nèi)容不再此討論，留在以后“離散數(shù)學(xué)”等課程中學(xué)習(xí)。下面僅給出格的定義。 布爾代數(shù)是一種特殊的格，它由 0和 1組成的集合以及定義在其上的“ 3個(gè)運(yùn)算”構(gòu)成。 0，1?A，對(duì)于任意的 x， y， z?A，若以下定律成立 （ 1） x*y=y*x x?y=y?x (交換律 ) （ 2） x* (y?z)=(x*y) ? (x*z) x? (y*z)=(x?y)*(x?z) (分配律 ) （ 3） x*0=x x?1=x (泛界律 ) （ 4） x*x’=1 x?x’=0 (互補(bǔ)律 ) （ 5） x* (y*z)=(x*y) *z x? (y?z)=(x?y) ?z (結(jié)合律 ) 則 A, * ,?,’稱為布爾代數(shù)，其中 *， ?和’分別為并運(yùn)算，交運(yùn)算和補(bǔ)運(yùn)算。 布代數(shù)是英國數(shù)學(xué)家和邏輯學(xué)家布爾（ ） 1847年創(chuàng)立的，最初用來研究邏輯思維的法則。 香農(nóng)的分析源于繼電器的使用，與傳統(tǒng)開關(guān)不同，繼電器是用電來控制開關(guān)的閉合，輸出的電壓是由輸入的電壓決定的，若設(shè)通電為 1，斷電為 0，就能與布爾代數(shù)的兩個(gè)值聯(lián)系起來。在電路的設(shè)計(jì)和分析中，一般用符號(hào)“ ‖可省略），用符號(hào)“ +‖表示邏輯“或”運(yùn)算，用符號(hào)“ ‖表示邏輯“非”運(yùn)算。 表 A B A實(shí)際的邏輯關(guān)系是千變?nèi)f化的，但它們都是“與”、“或”、“非” 3種運(yùn)算組合而成。 研究數(shù)字邏輯電路，我們所關(guān)心的是電路所完成的邏輯功能，而不是電的或機(jī)械的性能。若輸入為布爾變量 A， B， C， ……，輸出則為布爾函數(shù) F，F(xiàn)=f(A， B， C， ……)。因此，可以將一個(gè)具體的數(shù)字邏輯轉(zhuǎn)換成抽象的代數(shù)表達(dá)式而加以分析和研究。 表 ―與”、“或”、“非”門電路圖及相應(yīng)的布爾代數(shù)表達(dá)式 隨著數(shù)字邏輯電路的發(fā)展，現(xiàn)在實(shí)際使用的門電路除了“與”“或”“非”門外，還有“與非”、“或非”、“異或”、“同或”、“與或非”門等，它們都是由“與”“或”“非”邏輯導(dǎo)出的，它們的出現(xiàn)大大簡化了邏輯電路設(shè)計(jì)的復(fù)雜度。由于組合電路都可以用布爾代數(shù)來表示。下面，介紹一位加法器的設(shè)計(jì)，僅供參考。在四則運(yùn)算中，加法是最基本的一種運(yùn)算。由于減法、乘法、除法，甚至乘方、開方等運(yùn)算都可以用加法導(dǎo)出。 進(jìn)行加法運(yùn)算的機(jī)器，我們稱為加法器。下面，介紹一位加法器的設(shè)計(jì)。 不考慮高低進(jìn)位，只考慮兩個(gè)加數(shù)本身的加法器叫半加器。先設(shè)計(jì)半加器，給出真值表， X ， Y表示兩個(gè)加數(shù)， Fn 表示輸出。 圖 半加器邏輯電路圖 在設(shè)計(jì)全加器時(shí)，要考慮進(jìn)位。設(shè)計(jì)全加器，先給出真值表（表 ）。 圖 全加器的邏輯電路圖 字母表、字符串和語言 所有的計(jì)算機(jī)程序設(shè)計(jì)語言都是形式語言，其構(gòu)成基礎(chǔ)同一般自然語言一樣，也是符號(hào)或字母。 有限字母表指的是由有限個(gè)任意符號(hào)組成的非空集合，簡稱為字母表，用 ?表示。 字母表可以理解為計(jì)算機(jī)輸入鍵盤上符號(hào)的集合。 字符串，也稱為符號(hào)串，指的是由字符組成的有限序列，常用小寫希臘字母表示。 直觀來說， ?上的符號(hào)串是由其上的符號(hào)以任意次序拼接起來構(gòu)成的，任何符號(hào)都可以在串中重復(fù)出現(xiàn)。應(yīng)當(dāng)指出的是，空串 ε不同于我們計(jì)算機(jī)鍵盤上的空格鍵。例如，當(dāng) ?={a， b}，則 {ab， aabb， abab， bba}、｛ ε｝、｛ anbn｜ n≥1｝都是 ?上的語言。 Ф不同于｛ ε｝，前者表示空語言，后者表示由空串組成的語言。除此之外，語言還有一種重要的專門的運(yùn)算，即閉包運(yùn)算。語言由文法產(chǎn)生，第三章介紹過，文法是一種數(shù)學(xué)模型，它是建立在有限集合上的一組變換（運(yùn)算）。 計(jì)算機(jī)使用的語言是一種形式語言，形式語言與自動(dòng)機(jī)理論密切相關(guān)，并構(gòu)成計(jì)算機(jī)科學(xué)重要的理論基礎(chǔ)，在形式語言與自動(dòng)機(jī)理論中，語言又可分為短語結(jié)構(gòu)語言、上下文有關(guān)語言、上下文無關(guān)語言和正規(guī)語言，它們分別由 0型文法、 1型文法、 2型文法和 3型文法產(chǎn)生。 需要指出的是，語言與數(shù)學(xué)模型不是一一對(duì)應(yīng)的關(guān)系，一種語言可以由不同的文法產(chǎn)生，也可以由不同的自動(dòng)機(jī)識(shí)別。其中，定義是蘊(yùn)含在公理系統(tǒng)之中的概念和命題；定理是被證明為真的數(shù)學(xué)命題；證明是為使人們確信一個(gè)命題為真，而作的一種邏輯論證。對(duì)一個(gè)問題來說，給出一個(gè)精確的定義是不容易的，以至有人認(rèn)為，若能像圖靈給出“計(jì)算”的形式化定義那樣給出“智能”的定義，那么，“智能”的本質(zhì)將被揭示，“智能”領(lǐng)域也將產(chǎn)生一個(gè)質(zhì)的飛躍。陳波在其著作 《 邏輯是什么？ 》 一書中，從定義的作用、規(guī)則等多方面對(duì)定義作了系統(tǒng)的論述。 （ 1）定義必須揭示被定義對(duì)象的區(qū)別性特征； （ 2）定義項(xiàng)和被定義項(xiàng)的外延必須相等； （ 3）定義不能惡性循環(huán)； （ 4）定義不可用含混、隱晦或比喻性詞語來表示。 例 抽象 在常用詞典中，抽象一般有兩個(gè)解釋。 例 科學(xué) 科學(xué)是反映自然、社會(huì)、思維等的客觀規(guī)律的分科的知識(shí)體系。 例 人 人是能制造工具并使用工具進(jìn)行勞動(dòng)的高等動(dòng)物。該定義，確定了“人”屬于一種“動(dòng)物”；其次，確定了人與動(dòng)物種類的區(qū)別。除最低等的單孔類是卵生的以外，其他哺乳動(dòng)物全是胎生的。然而，要真正的理解并掌握這兩個(gè)概念卻不是一件容易的事。 一般地，若命題 p蘊(yùn)涵命題 q，即 p?q，則我們說， p是 q的充分條件， q是 p的必要條件。 從集合論的角度出發(fā)，借助于文氏圖，有助于對(duì)什么是必要條件，什么是充分條件的判定。 假設(shè) A={x|p}， B={x|q}，若 A?B，設(shè) x 為 A中的任一元素，即 x∈ A，則 x∈ B。 若 p?q, 則 p和 q互為充分必要條件，即 A=B, 如圖 (b)所示。這一命題中，“人”是哺乳類的充分條件，“哺乳類”是人的必要條件。這一命題中，正方形是長方形的充分條件， 圖 集合 A和 B相互關(guān)系的文氏圖 長方形是正方形的必要條件。 例 x=2是 x2=4的充分條件。如找人才，本來是找必要條件，但人們往往會(huì)用充分條件來找。如草率地上馬一個(gè)涉及面廣的項(xiàng)目。下面介紹一個(gè)在生活中與“必要條件”和“充分條件”有關(guān)的例子，以便加深對(duì)兩個(gè)概念的理解，并區(qū)別之。對(duì)于必要條件，由于約束的條件少，人往往會(huì)變得大度，大度的人與“小心眼”的人相比，會(huì)將注意力集中在很少的，卻又是起關(guān)鍵作用的必要條件上（必要條件，用計(jì)算機(jī)的行話來說，就是找不到一個(gè)反例的條件）。這種證明方法為直接證明法。 證明：假定 p是偶數(shù)為真，設(shè) p=2k（ k為整數(shù)）。因此， p2是偶數(shù)（它是一個(gè)整數(shù)的 2倍）。q→ 172。q→ 172。這種證明方法為間接證明法。 證明：假定此蘊(yùn)含式后件為假，即假定 p是奇數(shù)。由此可得 p2=4k2+4k+1=2（ 2k2+2k） +1，因此，p2是奇數(shù)（它是一個(gè)整數(shù)的 2倍加 1）。 反證法 首先假定一個(gè)與原命題相反的命題成立，然后通過正確的推理得出與已知（或假設(shè)）條件、公理、已證過的定理等相互矛盾或自相矛盾的結(jié)果，用來證明原命題的正確。 例 證是 無理數(shù)。而 的發(fā)現(xiàn)，使當(dāng)時(shí)人們的認(rèn)識(shí)產(chǎn)生了混亂，并導(dǎo)致了第一次數(shù)學(xué)危機(jī)。鑒于該學(xué)派迫害數(shù)學(xué)人才的“無理行為”， 15世紀(jì)的達(dá) 本例是數(shù)學(xué)反證法的一個(gè)典型實(shí)例，下面證明之。歸納法可分為不完全歸納法、完全歸納法和數(shù)學(xué)歸納法。因此，不完全歸納法不能作為嚴(yán)格的證明方法。 4．?dāng)?shù)學(xué)歸納法 （ 1）數(shù)學(xué)歸納法的概念 數(shù)學(xué)歸納法是一種用于證明與自然數(shù)有關(guān)的命題正確性的證明方法，該方法能用“有限”的步驟解決無窮對(duì)象的論證問題。 （ 2）數(shù)學(xué)歸納法的基本原理 數(shù)學(xué)歸納法由歸納基礎(chǔ)和歸納步驟兩個(gè)部分組成，其基本原理如下： 假定對(duì)一切正整數(shù) n，有一個(gè)命題 P(n)，若以下證明成立，則 P(n)為真： ① 歸納基礎(chǔ)：證明 P(1)為真； ② 歸納步驟：證明對(duì)任意的 i≥1，若 P(i)為真，則 P(i+1)為真。 證明： ① 歸納基礎(chǔ)：當(dāng) n=1時(shí)，等式成立，即 1=12 ② 歸納步驟： 設(shè)對(duì)任意 k≥1， P(k)成立，即： 1+3+5+…+(2k–1)= k2 而 1+3+5+…+(2k–1)+(2(k+1)–1) = k2+2k+1=(k+1)2 即當(dāng) P(k)成立時(shí)， P(k+1)也成立，根據(jù)數(shù)學(xué)歸納法，該命題得證。對(duì)形如 ?xP(x)的命題的證明稱為存在性證明。或者說，構(gòu)造性證明方法就是通過找出一個(gè)使得命題 P(a)為真的元素 a，從而完成該函數(shù)值的存在性證明的方法。 構(gòu)造性證明方法是計(jì)算機(jī)科學(xué)中廣泛使用的一種證明方法，附錄 B中Armstrong公理系統(tǒng)的完備性證明就采用了構(gòu)造性的證明方法。 遞歸和迭代密切相關(guān)，實(shí)現(xiàn)遞歸和迭代的基礎(chǔ)基于以下一個(gè)事實(shí)。該序列是遞歸和迭代運(yùn)算的基礎(chǔ)。20世紀(jì) 30年代，正是可計(jì)算的遞歸函數(shù)理論與圖靈機(jī)、 λ演算和 POST規(guī)范系統(tǒng)等理論一起為計(jì)算理論的建立奠定了基礎(chǔ)。 （ 1）遞歸關(guān)系指的是：一個(gè)數(shù)列的若干連續(xù)項(xiàng)之間的關(guān)系。 （ 3）遞歸過程指的是：調(diào)用“自身”的過程。 （ 5）遞歸程序指的是：直接或間接調(diào)用“自身”的程序。 在以上有關(guān)遞歸概念的定義中，調(diào)用自身中的“自身”兩個(gè)字加了引號(hào)。事實(shí)上，遞歸定義從來不是以某一事物自身來定義的，而是以比自身簡單一些的說法來定義的。 2．遞歸與數(shù)學(xué)歸納法 遞歸是一個(gè)重要的概念，然而，對(duì)于剛?cè)氪髮W(xué)的同學(xué)來說，理解起來卻有一定的困難，為了更好地理解遞歸思想，我們先給出一個(gè)簡單的例子。 計(jì)算方法之一： 6， 6+6=12， 12+6=18， 18+6=24， 24+6=30； 計(jì)算方法之二： 5?6， 4?6， 3?6， 2?6， 1?6； 1?6+6=12， 12+6=18，18+6=24， 24+6=30； 方法之二從 5?6開始計(jì)算，假設(shè)一個(gè)剛學(xué)乘法的小學(xué)生計(jì)算不出這個(gè)數(shù)，那么，這個(gè)小學(xué)生一般會(huì)先計(jì)算 4?6，然后再加 6就可以了，若仍計(jì)算不出，則會(huì)再追溯到 3?6，直到 1?6，然后，再依次加 6，最后得到 30。如果已知 an1就可以確定 an。但僅有這個(gè)關(guān)系，還不能確定這個(gè)數(shù)列，若使它完全確定，還應(yīng)給出這個(gè)數(shù)列的初始值 a1，這相當(dāng)于數(shù)學(xué)歸納法歸納基礎(chǔ)的內(nèi)容。數(shù)學(xué)歸納法是一種論證方法，遞歸是算法和程序設(shè)計(jì)的一種實(shí)現(xiàn)技術(shù)，涉及遞歸定義的證明通常采用數(shù)學(xué)歸納法。下面，舉例說明之。請(qǐng)給出其遞歸定義。 解 階乘 F(n)=n!的遞歸定義如下： F(0)=1； 遞歸基礎(chǔ) F(n)=n F(n–1)， n=1， 2， 3， …； 遞歸步驟 （ 3）定義集合 例 現(xiàn)有文法 G的生成式如下： S→ 0A1； S是文法 G的開始符號(hào) A→ 01； 遞歸基礎(chǔ) A→ 0A1； 遞歸步驟 以上這個(gè)文法的生成式采用了遞歸方法，該文法其實(shí)定義了這樣一個(gè)集合： L(G)=｛ 0n1n|n≥1｝，這是一個(gè)以相同個(gè)數(shù)的“ 0‖和“ 1‖組成的字符串的集合，即一種特殊的語言。 4．阿克曼函數(shù) 在遞歸函數(shù)論和涉及集合的并的某些算法的復(fù)雜性研究中，有一個(gè)起重要作用的遞歸函數(shù) ——阿克曼（ Ackermann）函數(shù)，該函數(shù)是由希爾伯特的學(xué)生、德國著名數(shù)學(xué)家威爾海姆