計學(xué)科中的數(shù)學(xué)方法

1、數(shù)學(xué)的基本特征數(shù)學(xué)的基本特征數(shù)學(xué)方法數(shù)學(xué)方法o 是指解決數(shù)學(xué)問題的策略、途徑和步驟，它是是指解決數(shù)學(xué)問題的策略、途徑和步驟，它是計算學(xué)科中最根本的研究方法。計算學(xué)科中最根本的研究方法。o 理論上，凡能被計算機(jī)處理的問題均可以轉(zhuǎn)換理論上，凡能被計算機(jī)處理的問題均可以轉(zhuǎn)換為一個數(shù)學(xué)問題，換言之，所有為一個數(shù)學(xué)問題，換言之，所有能被計算機(jī)處能被計算機(jī)處理的問題均可以用數(shù)學(xué)方法解決理的問題均可以用數(shù)學(xué)方法解決；o 反之，凡能以離散數(shù)學(xué)為代表的反之，凡能以離散數(shù)學(xué)為代表的構(gòu)造性構(gòu)造性數(shù)學(xué)方數(shù)學(xué)方法描述的問題，當(dāng)該問題所涉及的法描述的問題，當(dāng)該問題所涉及的論域為有窮論域為有窮，或雖為無窮但或雖為無窮但存在

2、有窮表示存在有窮表示時，這個問題也一時，這個問題也一定能用計算機(jī)來處理。定能用計算機(jī)來處理。數(shù)學(xué)的基本特征數(shù)學(xué)的基本特征o 高度的抽象性高度的抽象性 ：量的關(guān)系和空間的形式量的關(guān)系和空間的形式 o 邏輯的嚴(yán)密性邏輯的嚴(yán)密性 ：嚴(yán)格遵守形式邏輯的基本法嚴(yán)格遵守形式邏輯的基本法則，充分保證邏輯的可靠性，才能保證結(jié)論的則，充分保證邏輯的可靠性，才能保證結(jié)論的正確性。正確性。 o 普遍的適用性普遍的適用性 ：數(shù)學(xué)的高度抽象性決定了它數(shù)學(xué)的高度抽象性決定了它的普遍適用性。的普遍適用性。 數(shù)學(xué)方法的作用數(shù)學(xué)方法的作用o 為科學(xué)技術(shù)研究提供簡潔精確的形式化語言為科學(xué)技術(shù)研究提供簡潔精確的形式化語言 o 為科

3、學(xué)技術(shù)研究提供數(shù)量分析和計算的方法為科學(xué)技術(shù)研究提供數(shù)量分析和計算的方法o 為科學(xué)技術(shù)研究提供了邏輯推理的工具為科學(xué)技術(shù)研究提供了邏輯推理的工具 計算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語計算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語集合集合o 集合的概念集合的概念 n 構(gòu)造性數(shù)學(xué)方法的基礎(chǔ)。構(gòu)造性數(shù)學(xué)方法的基礎(chǔ)。n 集合就是一組無重復(fù)的對象的全體。集合就是一組無重復(fù)的對象的全體。n 集合中的對象稱為集合的元素。集合中的對象稱為集合的元素。n 如：計算機(jī)專業(yè)學(xué)生全部必修課程可以組成一個如：計算機(jī)專業(yè)學(xué)生全部必修課程可以組成一個集合，其中的每門課程就是這一集合中的元素。集合，其中的每門課程就是這一集合中的元素。集合的三種描

4、述方法集合的三種描述方法o 枚舉法：列出所有元素的表示方法。枚舉法：列出所有元素的表示方法。；，|集合的運算集合的運算 o 集合的并集合的并 n 設(shè)設(shè)5.1 集合的差集合的差 o 設(shè)設(shè) 、 為兩個任意集合，所有屬于為兩個任意集合，所有屬于 而不屬于而不屬于的一切元素構(gòu)成的集合的一切元素構(gòu)成的集合 ，稱為，稱為 和和 的差集。的差集?？杀硎緸椋嚎杀硎緸椋?= = 。n 求差集的運算稱為差（運算）。求差集的運算稱為差（運算）。交集的交交集的交o 設(shè)設(shè) 、 為兩個任意集合，由和的所有相同元為兩個任意集合，由和的所有相同元素構(gòu)成的集合素構(gòu)成的集合 ，稱為，稱為 和和 的交集?？杀硎緸椋旱慕患？杀硎緸?/p>

5、： 。n 求交集的運算稱為交（運算）。求交集的運算稱為交（運算）。集合的補集合的補 o 設(shè)設(shè)=5集合的乘積集合的乘積 o 1集合集合1，2，的乘積一般用法國數(shù)學(xué)的乘積一般用法國數(shù)學(xué)家笛卡爾（家笛卡爾（rene descartes）的名字命名，即）的名字命名，即笛卡爾積。該乘積表示如下：笛卡爾積。該乘積表示如下：12=（1，2，） ，1，2， 12的結(jié)果是一個有序元組的集合。的結(jié)果是一個有序元組的集合。函數(shù)函數(shù)o 函數(shù)又稱映射，是指把輸入轉(zhuǎn)變成輸出的運算，函數(shù)又稱映射，是指把輸入轉(zhuǎn)變成輸出的運算，該運算也可理解為從某一該運算也可理解為從某一“定義域定義域”的對象到的對象到某一某一“值域值域”的對

6、象的映射。函數(shù)是程序設(shè)計的對象的映射。函數(shù)是程序設(shè)計的基礎(chǔ)，程序定義了計算函數(shù)的算法，而定義的基礎(chǔ)，程序定義了計算函數(shù)的算法，而定義函數(shù)的方法又影響著程序語言的設(shè)計，好的程函數(shù)的方法又影響著程序語言的設(shè)計，好的程序設(shè)計語言一般都便于函數(shù)的計算。序設(shè)計語言一般都便于函數(shù)的計算。o 設(shè)設(shè) 為一個函數(shù)，當(dāng)輸入值為為一個函數(shù)，當(dāng)輸入值為 時輸出值為時輸出值為 ，則記作：則記作：baf)(關(guān)系關(guān)系o 關(guān)系是一個謂詞，其定義域為關(guān)系是一個謂詞，其定義域為 元組的集合。通常的元組的集合。通常的關(guān)系為二元關(guān)系，其定義域為有序?qū)Φ募希谶@個關(guān)系為二元關(guān)系，其定義域為有序?qū)Φ募希谶@個集合中，我們說有序?qū)Φ牡?/p>

7、一個元素和第二個元素有集合中，我們說有序?qū)Φ牡谝粋€元素和第二個元素有關(guān)系。如學(xué)生選課關(guān)系。如學(xué)生選課 等價關(guān)系等價關(guān)系o 在關(guān)系中，有一種特殊的關(guān)系，即等價關(guān)系，在關(guān)系中，有一種特殊的關(guān)系，即等價關(guān)系，它滿足以下它滿足以下，可將可將例例o 證明：首先將該關(guān)系形式化地表示為：證明：首先將該關(guān)系形式化地表示為：=( ， ) ， ， mod 3= mod 3例例5.7 計算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語計算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語o 所有的計算機(jī)程序設(shè)計語言都是形式語言，其所有的計算機(jī)程序設(shè)計語言都是形式語言，其構(gòu)成基礎(chǔ)同一般自然語言一樣，也是符號或字構(gòu)成基礎(chǔ)同一般自然語言一樣，也是符號或字母。常用的

8、符號有數(shù)字（母。常用的符號有數(shù)字（0 9）、大小寫字母）、大小寫字母（ ， ）、括號、運算符（）、括號、運算符（+，-，*，/）等。等。o 有限字母表指的是由有限個任意符號組成的非有限字母表指的是由有限個任意符號組成的非空集合，簡稱為字母表，用空集合，簡稱為字母表，用 表示。字母表上表示。字母表上的元素稱作字符或符號，用小寫字母或數(shù)字表的元素稱作字符或符號，用小寫字母或數(shù)字表示，如示，如 、 、 、1、2、3等。等。o 字母表可以理解為計算機(jī)輸入鍵盤上符號的集合。字字母表可以理解為計算機(jī)輸入鍵盤上符號的集合。字母可以理解為鍵盤上的每一個英文字母、數(shù)字、標(biāo)點母可以理解為鍵盤上的每一個英文字母、數(shù)

9、字、標(biāo)點符號、運算符號等。符號、運算符號等。o 字符串，也稱為符號串，指的是由字符組成的有限序字符串，也稱為符號串，指的是由字符組成的有限序列，常用小寫希臘字母表示。字母表列，常用小寫希臘字母表示。字母表 上的字符串以上的字符串以下列方式生成：下列方式生成：（1） 為為 上的一個特殊串，稱為空串，對任何上的一個特殊串，稱為空串，對任何 ，；（2）若）若 是是上的符號串，且上的符號串，且 ，則，則是是上的符號上的符號串；串；（3）若）若 是是上的符號串，當(dāng)且僅當(dāng)它由（上的符號串，當(dāng)且僅當(dāng)它由（1）和（）和（2）導(dǎo)出。導(dǎo)出。 o 直觀來說，直觀來說，上的符號串是由其上的符號以任上的符號串是由其上的

10、符號以任意次序拼接起來構(gòu)成的，任何符號都可以在串意次序拼接起來構(gòu)成的，任何符號都可以在串中重復(fù)出現(xiàn)。中重復(fù)出現(xiàn)。 作為一個特殊的串，由零個符作為一個特殊的串，由零個符號組成。應(yīng)當(dāng)指出的是，空串號組成。應(yīng)當(dāng)指出的是，空串 不同于我們計不同于我們計算機(jī)鍵盤上的空格鍵。算機(jī)鍵盤上的空格鍵。o 語言指的是給定字母表語言指的是給定字母表上的字符串的集合。上的字符串的集合。o 語言是字符串的集合，因此，傳統(tǒng)的集合運算（如并、語言是字符串的集合，因此，傳統(tǒng)的集合運算（如并、交、差、補、笛卡爾積）對語言都適用。除此之外，交、差、補、笛卡爾積）對語言都適用。除此之外，語言還有一種重要的專門的運算，即閉包運算。語

11、言還有一種重要的專門的運算，即閉包運算。o 定義、定理和證明是數(shù)學(xué)的核心，也是計算學(xué)定義、定理和證明是數(shù)學(xué)的核心，也是計算學(xué)科理論形態(tài)的核心內(nèi)容。其中，定義是蘊含在科理論形態(tài)的核心內(nèi)容。其中，定義是蘊含在公理系統(tǒng)之中的概念和命題；定理是被證明為公理系統(tǒng)之中的概念和命題；定理是被證明為真的數(shù)學(xué)命題；證明是為使人們確信一個命題真的數(shù)學(xué)命題；證明是為使人們確信一個命題是真的而作的一種邏輯論證。是真的而作的一種邏輯論證。證明方法證明方法 直接證明直接證明o 假定假定 為真，通過使用公理或已證明的定理以為真，通過使用公理或已證明的定理以及正確的推理規(guī)則證明及正確的推理規(guī)則證明 也為真，以此證明蘊也為真，

12、以此證明蘊含式含式 為真。這種證明方法為直接證明法。為真。這種證明方法為直接證明法。間接證明間接證明o 因為蘊含式因為蘊含式 與其逆否命題與其逆否命題 等價，因等價，因此可以通過證明此可以通過證明 來證明蘊含式來證明蘊含式 為真。為真。這種證明方法為間接證明法。這種證明方法為間接證明法。o 首先假定一個與原命題相反的命題成立，然后首先假定一個與原命題相反的命題成立，然后通過正確的推理得出與已知（或假設(shè)）條件、通過正確的推理得出與已知（或假設(shè)）條件、公理、已證過的定理等相互矛盾或自相矛盾的公理、已證過的定理等相互矛盾或自相矛盾的結(jié)果，以此證明原命題正確。這種證明方法就結(jié)果，以此證明原命題正確。這

13、種證明方法就是反證法，也稱歸謬法，是一種常用的數(shù)學(xué)證是反證法，也稱歸謬法，是一種常用的數(shù)學(xué)證明方法。明方法。2歸納法的定義歸納法的定義o 所謂歸納法，是指從特殊推理出一般的一種證明方法。所謂歸納法，是指從特殊推理出一般的一種證明方法。歸納法可分為不完全歸納法、完全歸納法和數(shù)學(xué)歸納歸納法可分為不完全歸納法、完全歸納法和數(shù)學(xué)歸納法。法。數(shù)學(xué)歸納法的形式化定義數(shù)學(xué)歸納法的形式化定義o 根據(jù)數(shù)學(xué)歸納法的原理，可以對數(shù)學(xué)歸納法形根據(jù)數(shù)學(xué)歸納法的原理，可以對數(shù)學(xué)歸納法形式化地定義為：式化地定義為： (1)()( ( ) ( +1) ( ) 證明證明o 歸納基礎(chǔ)：當(dāng)歸納基礎(chǔ)：當(dāng) =1時，等式成立，即時，等式

14、成立，即1=12o 歸納步驟：歸納步驟：設(shè)對任意設(shè)對任意 1， ( )成立，即：成立，即： 1+3+5+（2 1）=2構(gòu)造性證明構(gòu)造性證明 o 構(gòu)造性證明構(gòu)造性證明通過找出一個使得命題通過找出一個使得命題 ( )為為真的元素真的元素a，從而完成該函數(shù)值的存在性證明，從而完成該函數(shù)值的存在性證明稱為構(gòu)造性證明。稱為構(gòu)造性證明。o 構(gòu)造性證明方法是計算科學(xué)中廣泛使用的一種構(gòu)造性證明方法是計算科學(xué)中廣泛使用的一種證明方法，本章證明方法，本章armstrong公理系統(tǒng)的完備性公理系統(tǒng)的完備性證明就采用了構(gòu)造性的證明方法。證明就采用了構(gòu)造性的證明方法。 遞歸和迭代遞歸和迭代 :很多序列項常常可以以這樣的

15、方很多序列項常?？梢砸赃@樣的方 式得到：由式得到：由1得到得到，按這樣的法則，按這樣的法則， 可以從一個已知的首項開始，有限次地重可以從一個已知的首項開始，有限次地重 復(fù)做下去，最后產(chǎn)生一個序列，該序列是復(fù)做下去，最后產(chǎn)生一個序列，該序列是 實現(xiàn)遞歸和迭代的基礎(chǔ)。實現(xiàn)遞歸和迭代的基礎(chǔ)。 遞歸及其有關(guān)概念遞歸及其有關(guān)概念o 20世紀(jì)世紀(jì)30年代，正是可計算的遞歸函數(shù)理論與圖靈機(jī)、年代，正是可計算的遞歸函數(shù)理論與圖靈機(jī)、演算和演算和post規(guī)范系統(tǒng)等理論一起為計算理論的建立規(guī)范系統(tǒng)等理論一起為計算理論的建立奠定了基礎(chǔ)。奠定了基礎(chǔ)。遞歸與數(shù)學(xué)歸納法遞歸與數(shù)學(xué)歸納法 例例5.13 o 遞歸由遞歸基礎(chǔ)和

16、遞歸步驟兩部分組成。遞歸由遞歸基礎(chǔ)和遞歸步驟兩部分組成。遞歸的定義功能遞歸的定義功能 例：例：定義集合定義集合例例5.16 ；阿克曼函數(shù)阿克曼函數(shù) o 該函數(shù)是由希爾伯特的學(xué)生、德國著名數(shù)學(xué)家該函數(shù)是由希爾伯特的學(xué)生、德國著名數(shù)學(xué)家威爾海姆威爾海姆阿克曼于阿克曼于1928年發(fā)現(xiàn)的。這是一個年發(fā)現(xiàn)的。這是一個圖靈機(jī)可計算的，但不是原始遞歸的函數(shù)。下圖靈機(jī)可計算的，但不是原始遞歸的函數(shù)。下面，我們介紹這個經(jīng)典的遞歸函數(shù)，并給出相面，我們介紹這個經(jīng)典的遞歸函數(shù)，并給出相應(yīng)的計算過程。應(yīng)的計算過程。o 阿克曼函數(shù)：阿克曼函數(shù)：)1,(, 1() 1),1(1),(nmamamannma若若若0,00n

17、mnm解阿克曼函數(shù)的遞歸算法解阿克曼函數(shù)的遞歸算法:begin if m=0 then n+1 else if n=0 then a(m-1,1) else a(m-1,a(m,n-1)end計算計算 (1,2)解解: (1,2)=(0,(1,1) = (0,(0,(1,0) = (0,(0,(0,1) = (0,(0,2) = (0,3) =4迭代迭代 o 迭代與遞歸有著密切的聯(lián)系，甚至，一類如迭代與遞歸有著密切的聯(lián)系，甚至，一類如o 斐波那契數(shù)的求解算法而言，可以使用迭代方斐波那契數(shù)的求解算法而言，可以使用迭代方法或遞歸方法來解決。法或遞歸方法來解決。o 一些遞歸算法，如求解梵天塔問題的算

18、法就不一些遞歸算法，如求解梵天塔問題的算法就不能用迭代方法，而只能用遞歸方法。能用迭代方法，而只能用遞歸方法。公理化方法公理化方法 理論體系理論體系 o 從數(shù)學(xué)的角度來說，理論是基本概念、基本原從數(shù)學(xué)的角度來說，理論是基本概念、基本原理或定律（聯(lián)系這些概念的判斷）以及由這些理或定律（聯(lián)系這些概念的判斷）以及由這些概念與原理邏輯推理出來的結(jié)論組成的集合，概念與原理邏輯推理出來的結(jié)論組成的集合，該概念可以形式化的定義為：該概念可以形式化的定義為：構(gòu)建理論體系的常用方法構(gòu)建理論體系的常用方法 o 每一個理論都由一組特定的概念和一組特定的每一個理論都由一組特定的概念和一組特定的命題組成。命題組成。o

19、在一個理論中，基本概念（原始概念）和基本在一個理論中，基本概念（原始概念）和基本命題（原始命題）必須是明確的，否則就會出命題（原始命題）必須是明確的，否則就會出現(xiàn)現(xiàn)“循環(huán)定義循環(huán)定義”和和“循環(huán)論證循環(huán)論證”的嚴(yán)重問題。的嚴(yán)重問題。o 構(gòu)建一個理論體系必須采用科學(xué)的方法。構(gòu)建一個理論體系必須采用科學(xué)的方法。公理化方法公理化方法 o 公理化方法，我們在第公理化方法，我們在第公理系統(tǒng)的公理系統(tǒng)的3個條件個條件 o 用公理化構(gòu)建的理論體系稱為公理系統(tǒng)，該公用公理化構(gòu)建的理論體系稱為公理系統(tǒng)，該公理系統(tǒng)需要滿足無矛盾性、獨立性和完備性的理系統(tǒng)需要滿足無矛盾性、獨立性和完備性的條件。條件。o 簡單化是科

20、學(xué)研究追求的目標(biāo)之一。一般而言，簡單化是科學(xué)研究追求的目標(biāo)之一。一般而言，正確的一定是簡單的（注意，這句話是單向的，正確的一定是簡單的（注意，這句話是單向的，反之不一定成立）。反之不一定成立）。o 關(guān)于公理系統(tǒng)的完備性要求，自哥德爾發(fā)表關(guān)關(guān)于公理系統(tǒng)的完備性要求，自哥德爾發(fā)表關(guān)于形式系統(tǒng)的于形式系統(tǒng)的“不完備性定理不完備性定理”的論文后，數(shù)的論文后，數(shù)學(xué)家們對公理系統(tǒng)的完備性要求大大放寬了。學(xué)家們對公理系統(tǒng)的完備性要求大大放寬了。公理化方法在計算學(xué)科中的應(yīng)用公理化方法在計算學(xué)科中的應(yīng)用 o 公理化方法主要用于計算學(xué)科理論形態(tài)方面的公理化方法主要用于計算學(xué)科理論形態(tài)方面的研究。在計算學(xué)科各分支領(lǐng)

21、域，均采用了公理研究。在計算學(xué)科各分支領(lǐng)域，均采用了公理化方法。如化方法。如n 形式語義學(xué)形式語義學(xué)n 關(guān)系數(shù)據(jù)庫理論關(guān)系數(shù)據(jù)庫理論n 分布式代數(shù)系統(tǒng)分布式代數(shù)系統(tǒng)n 計算認(rèn)知領(lǐng)域計算認(rèn)知領(lǐng)域例例o 原始概念：原始概念：例例o 以點、線、面為原始概念，以以點、線、面為原始概念，以：兩點之間可作一條直線；：兩點之間可作一條直線；：在平面上，過給定直線之外的一點，存在且僅：在平面上，過給定直線之外的一點，存在且僅存在一條平行線，即所謂的存在一條平行線，即所謂的“平行公設(shè)（公理）平行公設(shè)（公理）”。例例5.20 中國古代唯一的一次公理化嘗試：周髀算經(jīng)中國古代唯一的一次公理化嘗試：周髀算經(jīng)o 據(jù)有關(guān)記

22、載，據(jù)有關(guān)記載，周髀算經(jīng)周髀算經(jīng)成書于公元前成書于公元前100年年左右。在左右。在周髀算經(jīng)周髀算經(jīng)中，介紹了一個描述天象的蓋中，介紹了一個描述天象的蓋天學(xué)說，該學(xué)說構(gòu)建了一個幾何宇宙模型。天學(xué)說，該學(xué)說構(gòu)建了一個幾何宇宙模型。o 該學(xué)說中的公理有兩個：一個是該學(xué)說中的公理有兩個：一個是“天地為平行平天地為平行平面，天地相距面，天地相距80,000里，在北極下方的大地中央有里，在北極下方的大地中央有一底面直徑為一底面直徑為23,000里，高為里，高為60,000里的上尖下里的上尖下粗的粗的 “璇璣璇璣”（即極下，極下陽光照不到，故不生（即極下，極下陽光照不到，故不生萬物）；萬物）；o 另一個是關(guān)

23、于太陽光照以及人目所見的極限范圍，即另一個是關(guān)于太陽光照以及人目所見的極限范圍，即“日照四旁各十六萬七千里；人所望見，遠(yuǎn)近宜如日日照四旁各十六萬七千里；人所望見，遠(yuǎn)近宜如日光所照光所照”，其大意為，日光向四周照射的極限距離是，其大意為，日光向四周照射的極限距離是167,000里，人所見到也是這個距離。換言之，日里，人所見到也是這個距離。換言之，日光照不到光照不到167,000里之外，人也看不見里之外，人也看不見167,000里之外。里之外。o 從公理可以演繹出：夏至南萬六千里，冬至南十從公理可以演繹出：夏至南萬六千里，冬至南十三萬五千里，日中立竿無影。此一者天道之?dāng)?shù)。周髀三萬五千里，日中立竿無

24、影。此一者天道之?dāng)?shù)。周髀長八尺，夏至之日晷一尺六寸。髀者，股也；正晷者，長八尺，夏至之日晷一尺六寸。髀者，股也；正晷者，勾也。正南千里，勾一尺五寸；正北千里，勾一尺七勾也。正南千里，勾一尺五寸；正北千里，勾一尺七寸。其大意為，在某地豎一個寸。其大意為，在某地豎一個8尺高的竿，太陽移動尺高的竿，太陽移動了一千里，這個竿的影子和原來的相差一寸，即日影了一千里，這個竿的影子和原來的相差一寸，即日影千里差一寸。千里差一寸。o 而從而從“日照四旁日照四旁”167,000里，以及用公理演里，以及用公理演繹出的冬至日道半徑繹出的冬至日道半徑238,000里，又可導(dǎo)出宇宙半里，又可導(dǎo)出宇宙半徑為徑為405,0

25、00里，從而構(gòu)建了一個天、地為圓形平里，從而構(gòu)建了一個天、地為圓形平行平面的宇宙模型。行平面的宇宙模型。o 今天，我們知道，這個宇宙模型的描述與實際的今天，我們知道，這個宇宙模型的描述與實際的天象吻合得并不好，與同時代古希臘類似模型相比，天象吻合得并不好，與同時代古希臘類似模型相比，也存在較大的差距，而當(dāng)時，我國天文學(xué)家完全可以也存在較大的差距，而當(dāng)時，我國天文學(xué)家完全可以用代數(shù)方法相當(dāng)精確地解決一些天文學(xué)問題，至于宇用代數(shù)方法相當(dāng)精確地解決一些天文學(xué)問題，至于宇宙究竟是什么形狀或結(jié)構(gòu)，完全可以不去過問。然而，宙究竟是什么形狀或結(jié)構(gòu)，完全可以不去過問。然而，周髀算經(jīng)周髀算經(jīng)是個例外，并成為我國

26、古代學(xué)者惟一的是個例外，并成為我國古代學(xué)者惟一的一次公理化方法的嘗試，這種思想，是受外來因素的一次公理化方法的嘗試，這種思想，是受外來因素的影響，還是我國本土科學(xué)中某種隨機(jī)出現(xiàn)的變異？已影響，還是我國本土科學(xué)中某種隨機(jī)出現(xiàn)的變異？已引起科學(xué)史領(lǐng)域?qū)＜业臉O大興趣。引起科學(xué)史領(lǐng)域?qū)＜业臉O大興趣。形式化方法形式化方法 具體公理系統(tǒng)和抽象公理系統(tǒng)具體公理系統(tǒng)和抽象公理系統(tǒng) o 在歐氏幾何公理系統(tǒng)中，原始概念（點、線、在歐氏幾何公理系統(tǒng)中，原始概念（點、線、面）和所有的公理都有直觀的背景或客觀的意面）和所有的公理都有直觀的背景或客觀的意義，像這樣有現(xiàn)實世界背景的公理系統(tǒng)，一般義，像這樣有現(xiàn)實世界背景的公

27、理系統(tǒng)，一般被稱為具體公理系統(tǒng)。被稱為具體公理系統(tǒng)。 o 由于非歐幾何的出現(xiàn)，使人們感到具體公理系由于非歐幾何的出現(xiàn)，使人們感到具體公理系統(tǒng)過于受直覺的局限。因而，在統(tǒng)過于受直覺的局限。因而，在19世紀(jì)末和世紀(jì)末和20世紀(jì)初，一些杰出的數(shù)學(xué)家和邏輯學(xué)家開始了世紀(jì)初，一些杰出的數(shù)學(xué)家和邏輯學(xué)家開始了對抽象公理系統(tǒng)的研究。對抽象公理系統(tǒng)的研究。o 在抽象公理系統(tǒng)中，原始概念的直覺意義被忽在抽象公理系統(tǒng)中，原始概念的直覺意義被忽視，甚至沒有任何預(yù)先設(shè)定的意義，而公理也視，甚至沒有任何預(yù)先設(shè)定的意義，而公理也無需以任何實際意義為背景，它們無非是一些無需以任何實際意義為背景，它們無非是一些形式約定的符號

28、串。這時，抽象公理系統(tǒng)可以形式約定的符號串。這時，抽象公理系統(tǒng)可以有多種解釋。有多種解釋。形式系統(tǒng)的組成部分形式系統(tǒng)的組成部分o 初始符號。初始符號不具有任何意義。初始符號。初始符號不具有任何意義。o 形式規(guī)則。形式規(guī)則規(guī)定一種程序，借以判定形式規(guī)則。形式規(guī)則規(guī)定一種程序，借以判定哪些符號串是本系統(tǒng)中的公式，哪些不是。哪些符號串是本系統(tǒng)中的公式，哪些不是。o 公理。即在本系統(tǒng)的公式中，確定不加推導(dǎo)就公理。即在本系統(tǒng)的公式中，確定不加推導(dǎo)就可以斷定的公式集?？梢詳喽ǖ墓郊 變形規(guī)則。變形規(guī)則亦稱演繹規(guī)則或推導(dǎo)規(guī)則。變形規(guī)則。變形規(guī)則亦稱演繹規(guī)則或推導(dǎo)規(guī)則。變形規(guī)則規(guī)定，從已被斷定的公式，如

29、何得出變形規(guī)則規(guī)定，從已被斷定的公式，如何得出新的被斷定公式。被斷定的公式又稱為系統(tǒng)中新的被斷定公式。被斷定的公式又稱為系統(tǒng)中的定理。的定理。形式系統(tǒng)的基本特點形式系統(tǒng)的基本特點 o 嚴(yán)格性嚴(yán)格性n 形式系統(tǒng)中，初始符號和形式規(guī)則都要進(jìn)行嚴(yán)格形式系統(tǒng)中，初始符號和形式規(guī)則都要進(jìn)行嚴(yán)格的定義，不允許出現(xiàn)在有限步內(nèi)無法判定的公式。的定義，不允許出現(xiàn)在有限步內(nèi)無法判定的公式。形式系統(tǒng)采用的是一種純形式的機(jī)械方法，它的形式系統(tǒng)采用的是一種純形式的機(jī)械方法，它的嚴(yán)格性高于一般的數(shù)學(xué)推導(dǎo)。嚴(yán)格性高于一般的數(shù)學(xué)推導(dǎo)。形式系統(tǒng)的局限性形式系統(tǒng)的局限性 o 不完備性不完備性n 1931年，哥德爾提出的關(guān)于形式系

30、統(tǒng)的年，哥德爾提出的關(guān)于形式系統(tǒng)的“不完備性定理不完備性定理”指出：如果一個形式的指出：如果一個形式的數(shù)學(xué)理論是足夠復(fù)雜的（復(fù)雜到所有的遞數(shù)學(xué)理論是足夠復(fù)雜的（復(fù)雜到所有的遞歸函數(shù)在其中都能夠表示），而且它是無歸函數(shù)在其中都能夠表示），而且它是無矛盾的，那么在這一理論中存在一個語句，矛盾的，那么在這一理論中存在一個語句，而這一語句在這一理論中是既不能證明，而這一語句在這一理論中是既不能證明，也不能否證的。也不能否證的。形式系統(tǒng)的局限性形式系統(tǒng)的局限性 o 不可判定性不可判定性n 如果對一類語句如果對一類語句c而言，存在一個算法而言，存在一個算法al，使，使得對得對c中的任一語句中的任一語句s而

31、言，可以利用算法而言，可以利用算法al來來判定其是否成立，則判定其是否成立，則c稱為可判定的，否則，稱稱為可判定的，否則，稱為不可判定的。為不可判定的。n 著名的著名的“停機(jī)問題停機(jī)問題”就是一個不可判定性的問就是一個不可判定性的問題。該問題是指，一個任給的圖靈機(jī)對于一個題。該問題是指，一個任給的圖靈機(jī)對于一個任給的輸入而言是否停機(jī)的問題。圖靈證明這任給的輸入而言是否停機(jī)的問題。圖靈證明這類問題是不可判定的。類問題是不可判定的。形式化與公理化形式化與公理化 o 形式化不一定導(dǎo)致公理化，公理系統(tǒng)也不一定形式化不一定導(dǎo)致公理化，公理系統(tǒng)也不一定是形式系統(tǒng)。是形式系統(tǒng)。一個實例一個實例armstro

32、ng公理系統(tǒng)公理系統(tǒng) 預(yù)備知識預(yù)備知識 o 定義定義1：設(shè)：設(shè) =是一個關(guān)系模式，其中，是一個關(guān)系模式，其中， 是關(guān)是關(guān)系名，系名， 為組成該關(guān)系屬性名的集合，為組成該關(guān)系屬性名的集合， 為為 上的一個上的一個函數(shù)依賴關(guān)系的集合。設(shè)函數(shù)依賴關(guān)系的集合。設(shè) ， ( )，則對，則對任何任何 ， ，只要，只要 = ，就必有，就必有 = ，則，則稱滿足稱滿足 ，也稱中存在函數(shù)依賴，也稱中存在函數(shù)依賴 。o 注：關(guān)系模式注：關(guān)系模式 =上的所有實例的集合記作上的所有實例的集合記作( )。o 定義定義2：在關(guān)系模式：在關(guān)系模式 =中，為中，為 所邏輯蘊含的所邏輯蘊含的函數(shù)依賴全體的集合稱為函數(shù)依賴全體的集合稱為 的閉包（的閉包（clo