計(jì)算科學(xué)內(nèi)容和方法.ppt

第五章 計(jì)算科學(xué)內(nèi)容和方法,李陶深 ,第5章 計(jì)算學(xué)科的內(nèi)容 與方法,5.1 計(jì)算科學(xué)的基本問(wèn)題,能行性,能行性：什么能（有效地）自動(dòng)進(jìn)行，什么不能（有效地）自動(dòng)進(jìn)行。 “能行性”這個(gè)計(jì)算學(xué)科的根本問(wèn)題決定了計(jì)算機(jī)本身的結(jié)構(gòu)和它處理的對(duì)象都是離散型的，甚至許多連續(xù)型的問(wèn)題也必須在轉(zhuǎn)化為離散型問(wèn)題以后才能被計(jì)算機(jī)處理。 例如，計(jì)算定積分就是把它變成離散量，再用分段求和的方法來(lái)處理的。,計(jì)算科學(xué)的發(fā)展主線,具體來(lái)說(shuō)，有三大問(wèn)題： 1）計(jì)算的平臺(tái)和環(huán)境問(wèn)題（計(jì)算模型問(wèn)題） 2）計(jì)算過(guò)程的能行操作和效率問(wèn)題（算法問(wèn)題） 3）計(jì)算的正確性問(wèn)題（語(yǔ)義學(xué)問(wèn)題） 計(jì)算機(jī)研究的目標(biāo)是:拓展和提高計(jì)算機(jī)的應(yīng)用領(lǐng)域和應(yīng)用水平。 圍繞學(xué)科的三個(gè)基本問(wèn)題使學(xué)科的發(fā)展形成了三條相對(duì)獨(dú)立的主線，形成了許多相對(duì)獨(dú)立的分支學(xué)科和研究方向。 不同時(shí)期，圍繞著學(xué)科的一些重大問(wèn)題和基本問(wèn)題，若干方向便構(gòu)成了所謂的主流方向，由主流方向又形成了學(xué)科的發(fā)展主線。,計(jì)算的平臺(tái)與環(huán)境問(wèn)題,計(jì)算的平臺(tái)與環(huán)境問(wèn)題是指描述計(jì)算問(wèn)題的計(jì)算模型，或者實(shí)際制造出來(lái)的針對(duì)各種待處理問(wèn)題特點(diǎn)和要求的自動(dòng)計(jì)算機(jī)器。 不難看出，理論研究中提出的各種計(jì)算模型，各種實(shí)際的計(jì)算機(jī)系統(tǒng)，各種高級(jí)程序設(shè)計(jì)語(yǔ)言，各種計(jì)算機(jī)體系結(jié)構(gòu)，各種軟件開(kāi)發(fā)工具與環(huán)境，編譯程序與操作系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)等都是圍繞這一基本問(wèn)題發(fā)展而來(lái)的，其內(nèi)容實(shí)質(zhì)可歸結(jié)為計(jì)算的模型問(wèn)題，也就是說(shuō)，這個(gè)基本問(wèn)題實(shí)際上關(guān)心的是計(jì)算問(wèn)題在理論上是否能行的問(wèn)題。,計(jì)算過(guò)程的能行操作與效率問(wèn)題,含義是：當(dāng)一個(gè)問(wèn)題在判明為可計(jì)算的性質(zhì)后，從具體解決這個(gè)問(wèn)題著眼，必須按照能行可構(gòu)造的特點(diǎn)與要求，給出實(shí)際解決該問(wèn)題的一步一步的具體操作，同時(shí)還必須確保這樣一種過(guò)程的開(kāi)銷(xiāo)成本是我們能夠承受的。 相關(guān)的分支學(xué)科有：數(shù)值與非數(shù)值計(jì)算方法，算法設(shè)計(jì)與分析，結(jié)構(gòu)化程序設(shè)計(jì)技術(shù)，密碼學(xué)與快速算法，演化計(jì)算，程序設(shè)計(jì)方法學(xué)，自動(dòng)布線，RISC技術(shù)，人工智能的邏輯基礎(chǔ)等。,計(jì)算的正確性問(wèn)題,計(jì)算的正確性是指：一個(gè)計(jì)算問(wèn)題在給出了能行操作序列并解決了其效率問(wèn)題之后，必須確保計(jì)算的正確性，否則，計(jì)算是無(wú)意義的，也是容易產(chǎn)生不利影響的。 這一基本問(wèn)題相關(guān)的分支學(xué)科有：算法理論，程序設(shè)計(jì)方法學(xué)，程序設(shè)計(jì)語(yǔ)言的語(yǔ)義學(xué)，進(jìn)程代數(shù)與分布式事件代數(shù)，程序測(cè)試技術(shù)，電路測(cè)試技術(shù)，軟件工程技術(shù)，計(jì)算語(yǔ)言學(xué)，容錯(cuò)理論與技術(shù)，Petri網(wǎng)理論，CSP理論，CCS理論，分布式網(wǎng)絡(luò)協(xié)議等。 今天，計(jì)算的正確性問(wèn)題常常歸結(jié)為各種語(yǔ)言的語(yǔ)義問(wèn)題。,計(jì)算科學(xué)的三大基本問(wèn)題,計(jì)算學(xué)科的三個(gè)基本問(wèn)題普遍出現(xiàn)在學(xué)科的各個(gè)分支學(xué)科和研究方向之中，是學(xué)科研究與發(fā)展中經(jīng)常面對(duì)而又必須解決的問(wèn)題。 循著這一線索，我們不難看出，整個(gè)學(xué)科正是在圍繞這些基本問(wèn)題和不同時(shí)期重大問(wèn)題而展開(kāi)的研究與發(fā)展中形成了學(xué)科的發(fā)展主線與主流方向。,第5章 計(jì)算學(xué)科的內(nèi)容 與方法,5.2 計(jì)算科學(xué)內(nèi)容的三個(gè)層面,計(jì)算科學(xué)的應(yīng)用層,包括人工智能應(yīng)用與系統(tǒng)，信息、管理與決策系統(tǒng)，移動(dòng)計(jì)算、計(jì)算可視化、科學(xué)計(jì)算等計(jì)算機(jī)應(yīng)用的各個(gè)方向。其中，人工智能應(yīng)用與系統(tǒng)涵蓋人工智能，機(jī)器人，神經(jīng)元計(jì)算，知識(shí)工程，自然語(yǔ)言處理與機(jī)器翻譯，自動(dòng)推理等方向；信息、管理與決策系統(tǒng)涵蓋數(shù)據(jù)庫(kù)設(shè)計(jì)與數(shù)據(jù)管理技術(shù)，數(shù)據(jù)表示與存儲(chǔ)（包括多媒體技術(shù)），數(shù)據(jù)與信息檢索，管理信息系統(tǒng)，計(jì)算機(jī)輔助系統(tǒng)，決策系統(tǒng)等方向；計(jì)算可視化涵蓋計(jì)算機(jī)圖形學(xué)，計(jì)算幾何，模式識(shí)別與圖像處理等方向。,計(jì)算科學(xué)的專(zhuān)業(yè)基礎(chǔ)層,它是為應(yīng)用層提供技術(shù)和環(huán)境的一個(gè)層面，包括軟件開(kāi)發(fā)方法學(xué)，計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)，程序設(shè)計(jì)科學(xué)，計(jì)算機(jī)體系結(jié)構(gòu)，電子計(jì)算機(jī)系統(tǒng)基礎(chǔ)。其中，軟件開(kāi)發(fā)方法學(xué)涵蓋順序、并行與分布式軟件開(kāi)發(fā)方法學(xué)，如軟件工程技術(shù)，軟件開(kāi)發(fā)工具和環(huán)境等方向；計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)涵蓋計(jì)算機(jī)網(wǎng)絡(luò)互聯(lián)技術(shù)，數(shù)據(jù)通信技術(shù)，以及信息保密與安全技術(shù)等方向；程序設(shè)計(jì)科學(xué)涵蓋數(shù)據(jù)結(jié)構(gòu)技術(shù)，數(shù)值與符號(hào)計(jì)算，算法設(shè)計(jì)與分析，程序設(shè)計(jì)語(yǔ)言，程序設(shè)計(jì)語(yǔ)言的文法與語(yǔ)義，程序設(shè)計(jì)方法學(xué)，程序理論等方向；電子計(jì)算機(jī)系統(tǒng)基礎(chǔ)涵蓋數(shù)字邏輯技術(shù)，計(jì)算機(jī)組成原理，故障診斷與器件測(cè)試技術(shù)，操作系統(tǒng)，編譯技術(shù)，數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)技術(shù)，容錯(cuò)技術(shù)等方向。,計(jì)算科學(xué)的基礎(chǔ)層,它包括計(jì)算的數(shù)學(xué)理論，高等邏輯等內(nèi)容。其中，計(jì)算的數(shù)學(xué)理論涵蓋可計(jì)算性（遞歸論）與計(jì)算復(fù)雜性理論，形式語(yǔ)言與自動(dòng)機(jī)理論，形式語(yǔ)義學(xué)（主要指代數(shù)語(yǔ)義，公理語(yǔ)義等），Petri網(wǎng)理論等方向；高等邏輯涵蓋模型論，各種非經(jīng)典邏輯與公理集合論等方向。 支撐這三個(gè)層面的是計(jì)算科學(xué)這一學(xué)科的理工科基礎(chǔ)科目，包括物理學(xué)（主要是電子技術(shù)科學(xué)）、基礎(chǔ)數(shù)學(xué)（含離散數(shù)學(xué)）等。,移動(dòng)計(jì)算與全球定位 計(jì)算機(jī)自動(dòng)控制 計(jì)算機(jī)輔助制造 計(jì)算機(jī)集成制造系統(tǒng) 計(jì)算 機(jī)器人 計(jì)算可視化與虛擬現(xiàn)實(shí) 數(shù)據(jù)與信息檢索 計(jì)算機(jī)創(chuàng)作 計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用軟件 科學(xué) 科學(xué)計(jì)算 多媒體信息系統(tǒng) 計(jì)算機(jī)輔助設(shè)計(jì) 信息、管理與決策系統(tǒng) 自然語(yǔ)言處理 應(yīng)用 模式識(shí)別與圖像處理技術(shù) 計(jì)算機(jī)圖形學(xué) 計(jì)算幾何 人工智能與知識(shí)工程 層 數(shù)據(jù)表示與存儲(chǔ) 網(wǎng)絡(luò)與開(kāi)放系統(tǒng)互聯(lián)標(biāo)準(zhǔn) 軟件測(cè)試技術(shù) 人機(jī)工程學(xué)（人機(jī)界面） 計(jì)算 軟件開(kāi)發(fā)方法學(xué): 軟件工程技術(shù)、程序設(shè)計(jì)方法學(xué)、軟件開(kāi)發(fā)工具和環(huán)境、軟件開(kāi)發(fā)規(guī)范 科學(xué) 編碼理論 密碼學(xué) 計(jì)算機(jī)體系結(jié)構(gòu) 程序理論 數(shù)據(jù)表示理論與數(shù)據(jù)庫(kù)系統(tǒng) 專(zhuān)業(yè) 電子計(jì)算機(jī)系統(tǒng)基礎(chǔ) 計(jì)算機(jī)接口與通信 計(jì)算機(jī)網(wǎng)絡(luò)與數(shù)據(jù)通信技術(shù) 自動(dòng)推理 基礎(chǔ) 故障診斷與器件測(cè)試技術(shù) 容錯(cuò)技術(shù) 匯編技術(shù) 操作系統(tǒng) 高級(jí)語(yǔ)言 程序設(shè)計(jì) 層 數(shù)字系統(tǒng)設(shè)計(jì) 符號(hào)計(jì)算與計(jì)算機(jī)代數(shù) 數(shù)據(jù)結(jié)構(gòu)技術(shù) 算法設(shè)計(jì)與分析 編譯與解釋技術(shù) 計(jì)算 控制論基礎(chǔ) 數(shù)字系統(tǒng)設(shè)計(jì)基礎(chǔ) 信息論基礎(chǔ) 網(wǎng)論（Petri網(wǎng)理論等） 形式語(yǔ)義學(xué) 科學(xué) 框圖理論 算法理論 可計(jì)算性（遞歸論） 計(jì)算復(fù)雜性 程序設(shè)計(jì)語(yǔ)言理論 基礎(chǔ) 計(jì)算模型（各種抽象機(jī)） 模型論與非經(jīng)典邏輯 公理集合論 形式語(yǔ)言與自動(dòng)機(jī) 層 數(shù)學(xué) 光電子技術(shù)基礎(chǔ) 電路基礎(chǔ) 電子線路基礎(chǔ) 數(shù)字與模擬電路基礎(chǔ) 數(shù)值分析與計(jì)算方法 與 大學(xué)物理學(xué) 函數(shù)論基礎(chǔ)（復(fù)變函數(shù)、演算、泛函分析等） 泛代數(shù) 概率與數(shù)理統(tǒng)計(jì) 物理 常微分方程 偏微分方程 集合論與圖論 組合數(shù)學(xué) 抽象代數(shù) 數(shù)理邏輯基礎(chǔ) 層 空間解析幾何 數(shù)學(xué)分析 布爾代數(shù) 高等代數(shù) 數(shù)論,第5章 計(jì)算學(xué)科的內(nèi)容 與方法,5.3 計(jì)算科學(xué)的發(fā)展主線,計(jì)算科學(xué)的發(fā)展主線,在計(jì)算機(jī)基礎(chǔ)研究、應(yīng)用基礎(chǔ)研究和技術(shù)開(kāi)發(fā)與應(yīng)用的研究中，計(jì)算學(xué)科逐步發(fā)展形成了三條相對(duì)獨(dú)立的主線： 1）計(jì)算模型與計(jì)算機(jī)系統(tǒng) 2）計(jì)算模型、語(yǔ)言與軟件開(kāi)發(fā)方法學(xué) 3）應(yīng)用數(shù)學(xué)與計(jì)算機(jī)應(yīng)用,第5章 計(jì)算學(xué)科的內(nèi)容 與方法,5.4 計(jì)算科學(xué)的分類(lèi)與分支學(xué)科簡(jiǎn)介,構(gòu)造性數(shù)學(xué)基礎(chǔ),對(duì)數(shù)學(xué)基礎(chǔ)問(wèn)題的討論促進(jìn)了構(gòu)造性數(shù)學(xué)的產(chǎn)生和發(fā)展，產(chǎn)生了數(shù)學(xué)發(fā)展史上著名的三大邏輯學(xué)派：邏輯主義學(xué)派，形式主義學(xué)派和直覺(jué)主義邏輯學(xué)派。 盡管數(shù)學(xué)科學(xué)的發(fā)展在計(jì)算科學(xué)的發(fā)展中得到廣泛的應(yīng)用，但是與計(jì)算科學(xué)在科學(xué)方法論上形成一致的是構(gòu)造性數(shù)學(xué)。這是直覺(jué)主義所以受到計(jì)算科學(xué)家歡迎的原因。 可以這么說(shuō)：歷史上，對(duì)計(jì)算的能行性和可構(gòu)造性研究的最著名的產(chǎn)物要數(shù)圖靈機(jī)。如果沒(méi)有19世紀(jì)末20世紀(jì)初關(guān)于數(shù)學(xué)基礎(chǔ)問(wèn)題的討論，沒(méi)有直覺(jué)主義學(xué)派對(duì)數(shù)學(xué)的貢獻(xiàn)，計(jì)算科學(xué)可能要推遲出現(xiàn)。,構(gòu)造性數(shù)學(xué)基礎(chǔ),數(shù)理邏輯與抽象代數(shù)是計(jì)算科學(xué)最重要的兩項(xiàng)數(shù)學(xué)基礎(chǔ)，它們的研究思想和研究方法在計(jì)算科學(xué)許多有深度的領(lǐng)域得到了最廣泛的應(yīng)用。 數(shù)理邏輯是研究推理的科學(xué)，特別，在過(guò)去主要是研究數(shù)學(xué)中推理的科學(xué)。數(shù)理邏輯與哲學(xué)有著密切的聯(lián)系，其哲學(xué)方面是形式邏輯，而形式邏輯的數(shù)學(xué)化方面構(gòu)成了數(shù)理邏輯的研究?jī)?nèi)容。,構(gòu)造性數(shù)學(xué)基礎(chǔ),在計(jì)算科學(xué)的研究和發(fā)展中，應(yīng)該接受什么樣的數(shù)學(xué)理論呢？羅賓遜認(rèn)為，如果大家不對(duì)一個(gè)數(shù)學(xué)理論的可解釋性提出非議，那么，有幾條通常被看作是基本的可接受性的準(zhǔn)則： (1) 一個(gè)數(shù)學(xué)理論，僅當(dāng)它是協(xié)調(diào)的，或稱(chēng)無(wú)矛盾的，才能被看作是可接受的； (2) 一個(gè)數(shù)學(xué)理論是可接受的，要是它能夠作為自然科學(xué)的一個(gè)基礎(chǔ)； (3) 一個(gè)數(shù)學(xué)理論要由美學(xué)標(biāo)準(zhǔn)來(lái)判斷，比如它的美或內(nèi)在的適當(dāng)性。 (3)中提及的標(biāo)準(zhǔn)，迄今還無(wú)從進(jìn)行任何科學(xué)的研究。,構(gòu)造性數(shù)學(xué)基礎(chǔ),對(duì)于(1)中提出的標(biāo)準(zhǔn)，足可以使我們認(rèn)識(shí)到數(shù)理邏輯對(duì)計(jì)算科學(xué)的重要性。 眾所周知，在計(jì)算科學(xué)的各個(gè)分支學(xué)科中，使用了各種數(shù)學(xué)理論，包括數(shù)理邏輯。要保證一個(gè)數(shù)學(xué)理論是協(xié)調(diào)的，或稱(chēng)無(wú)矛盾的，實(shí)際上是要保證該數(shù)學(xué)理論對(duì)客觀世界或應(yīng)用范疇的（語(yǔ)義）解釋是無(wú)矛盾的，用邏輯學(xué)的術(shù)語(yǔ)來(lái)說(shuō)就是該數(shù)學(xué)理論必須存在模型。這在方法論上是靠邏輯學(xué)中的模型理論提供的。而要學(xué)習(xí)模型論的內(nèi)容，僅有命題演算、一階謂詞演算的知識(shí)是不夠的。 對(duì)于(2)中提及的標(biāo)準(zhǔn)，讀者在今后的學(xué)習(xí)中會(huì)逐步體會(huì)到其涵義。,構(gòu)造性數(shù)學(xué)基礎(chǔ),現(xiàn)在，有經(jīng)驗(yàn)和成熟的計(jì)算科學(xué)家都知道，除了數(shù)理邏輯以外，對(duì)計(jì)算科學(xué)最重要的數(shù)學(xué)分支是代數(shù)，特別是抽象代數(shù)。 在計(jì)算科學(xué)中，代數(shù)方法被廣泛應(yīng)用于許多分支學(xué)科。例如，可計(jì)算性與計(jì)算復(fù)雜性，形式語(yǔ)言與自動(dòng)機(jī)理論，密碼學(xué)，算法理論，數(shù)據(jù)表示理論，網(wǎng)絡(luò)與通信理論，Petri網(wǎng)理論，程序理論，形式語(yǔ)義學(xué)等許多方面都離不開(kāi)代數(shù)。,計(jì)算的數(shù)學(xué)理論,所謂計(jì)算的數(shù)學(xué)理論是指一切關(guān)于能行性問(wèn)題的數(shù)學(xué)理論的總和。也有一種更具體的定義是指一切關(guān)于計(jì)算與計(jì)算模型問(wèn)題的數(shù)學(xué)理論的總和。 計(jì)算理論廣義的可以看作同計(jì)算的數(shù)學(xué)理論，狹義的主要指算法理論、可計(jì)算理論、計(jì)算復(fù)雜性理論。,計(jì)算機(jī)組成原理、器件與體系結(jié)構(gòu),計(jì)算機(jī)組成原理與設(shè)計(jì)是計(jì)算機(jī)發(fā)展的一個(gè)主流方向。這一方向的主要任務(wù)是根據(jù)各種計(jì)算模型研究計(jì)算機(jī)的工作原理，并按照器件、設(shè)備和工藝條件設(shè)計(jì)、制造具體的計(jì)算機(jī)。 早期計(jì)算機(jī)的設(shè)計(jì)是建立在分離元器件的基礎(chǔ)之上，這方面的工作更多的是集中在對(duì)各個(gè)部件微觀的精細(xì)分析，后來(lái)，隨著集成電路技術(shù)的進(jìn)步，工作的重點(diǎn)已開(kāi)始轉(zhuǎn)到計(jì)算機(jī)的組織結(jié)構(gòu)。 集成電路對(duì)電路和功能部件的高集成度和計(jì)算機(jī)設(shè)計(jì)與軟件開(kāi)發(fā)之間建立的密切關(guān)系，使這一方向的發(fā)展逐步形成了一個(gè)新的計(jì)算機(jī)體系結(jié)構(gòu)方向。,計(jì)算機(jī)應(yīng)用基礎(chǔ),要開(kāi)展各個(gè)領(lǐng)域的各種計(jì)算機(jī)具體應(yīng)用，就必須首先要有一些計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)。對(duì)計(jì)算科學(xué)專(zhuān)業(yè)的學(xué)生來(lái)說(shuō)，計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)包括算法基礎(chǔ)、程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)基礎(chǔ)、微機(jī)原理與接口技術(shù)等。,計(jì)算機(jī)基本應(yīng)用技術(shù),我們知道，計(jì)算機(jī)應(yīng)用和計(jì)算機(jī)基本應(yīng)用技術(shù)是一回事，涉及到的分支學(xué)科很多。然而，從計(jì)算機(jī)應(yīng)用的定義和科學(xué)方法論的角度出發(fā)，大致可以將計(jì)算機(jī)應(yīng)用分支學(xué)科的范疇確定下來(lái)，即它所研究的內(nèi)容在方法和技術(shù)上為計(jì)算機(jī)在各個(gè)領(lǐng)域的具體應(yīng)用奠定了基礎(chǔ)。,軟件基礎(chǔ),軟件是計(jì)算科學(xué)一個(gè)較大的學(xué)科門(mén)類(lèi)，包括眾多的分支學(xué)科方向，主要有高級(jí)程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)理論、程序設(shè)計(jì)原理、編譯程序原理與編譯系統(tǒng)實(shí)現(xiàn)技術(shù)、數(shù)據(jù)庫(kù)原理與數(shù)據(jù)庫(kù)管理系統(tǒng)、操作系統(tǒng)原理與實(shí)現(xiàn)技術(shù)、軟件工程技術(shù)、程序設(shè)計(jì)方法學(xué)、各種應(yīng)用軟件等。,新一代計(jì)算機(jī)體系結(jié)構(gòu)與軟件開(kāi)發(fā)方法學(xué),所謂新一代計(jì)算機(jī)體系結(jié)構(gòu)是相對(duì)于過(guò)去的體系結(jié)構(gòu)而言的。目前，對(duì)這類(lèi)體系結(jié)構(gòu)的研究?jī)?nèi)容很多，主要是各種新型并行計(jì)算機(jī)的體系結(jié)構(gòu)、集群式計(jì)算機(jī)體系結(jié)構(gòu)，體系結(jié)構(gòu)的可擴(kuò)展性、任務(wù)級(jí)并性、指令級(jí)并行性、動(dòng)態(tài)可改變結(jié)構(gòu)等方面的內(nèi)容，也有一些內(nèi)容還不成熟，正在發(fā)展之中。 高起點(diǎn)的軟件開(kāi)發(fā)方法學(xué)的主要基礎(chǔ)是新一代計(jì)算機(jī)體系結(jié)構(gòu)、高等邏輯、形式語(yǔ)義學(xué)、計(jì)算模型理論以及算法基礎(chǔ)。這實(shí)際上也指出了新一代計(jì)算機(jī)體系結(jié)構(gòu)與軟件開(kāi)發(fā)方法學(xué)（包括并行與分布式計(jì)算機(jī)系統(tǒng)、人工智能計(jì)算機(jī)系統(tǒng)、并行與分布式軟件開(kāi)發(fā)方法學(xué)等）是計(jì)算科學(xué)界需要長(zhǎng)期努力奮斗的工作重點(diǎn)。,第5章 計(jì)算學(xué)科的內(nèi)容 與方法,5.5 計(jì)算學(xué)科中的數(shù)學(xué)方法 5.5.1 數(shù)學(xué)的基本特征,數(shù)學(xué)方法,是指解決數(shù)學(xué)問(wèn)題的策略、途徑和步驟，它是計(jì)算學(xué)科中最根本的研究方法。 理論上，凡能被計(jì)算機(jī)處理的問(wèn)題均可以轉(zhuǎn)換為一個(gè)數(shù)學(xué)問(wèn)題，換言之，所有能被計(jì)算機(jī)處理的問(wèn)題均可以用數(shù)學(xué)方法解決； 反之，凡能以離散數(shù)學(xué)為代表的構(gòu)造性數(shù)學(xué)方法描述的問(wèn)題，當(dāng)該問(wèn)題所涉及的論域?yàn)橛懈F，或雖為無(wú)窮但存在有窮表示時(shí)，這個(gè)問(wèn)題也一定能用計(jì)算機(jī)來(lái)處理。,數(shù)學(xué)的基本特征,高度的抽象性 ：量的關(guān)系和空間的形式 邏輯的嚴(yán)密性 ：嚴(yán)格遵守形式邏輯的基本法則，充分保證邏輯的可靠性，才能保證結(jié)論的正確性。 普遍的適用性 ：數(shù)學(xué)的高度抽象性決定了它的普遍適用性。,數(shù)學(xué)方法的作用,為科學(xué)技術(shù)研究提供簡(jiǎn)潔精確的形式化語(yǔ)言 為科學(xué)技術(shù)研究提供數(shù)量分析和計(jì)算的方法 為科學(xué)技術(shù)研究提供了邏輯推理的工具,5.5 計(jì)算學(xué)科中的數(shù)學(xué) 方法,5.5.2 為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ),為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？,(1) 首先，從計(jì)算模型和可計(jì)算性的研究來(lái)看，可計(jì)算函數(shù)和可計(jì)算謂詞（一種能夠能行判定其真值的斷言或邏輯公式）是等價(jià)的，相互之間可以轉(zhuǎn)化。這就是說(shuō)，計(jì)算可以用函數(shù)演算來(lái)表達(dá)，也可以用邏輯系統(tǒng)來(lái)表達(dá)。作為計(jì)算模型可以計(jì)算的函數(shù)恰好與可計(jì)算謂詞是等價(jià)的，而且，數(shù)理邏輯本身的研究也廣泛使用代數(shù)方法，同時(shí)，邏輯系統(tǒng)又能通過(guò)自身的無(wú)矛盾性保證這樣一種計(jì)算模型是合理的。由此可見(jiàn)，作為一種數(shù)學(xué)形式系統(tǒng)，圖林機(jī)及其與它等價(jià)的計(jì)算模型的邏輯基礎(chǔ)是堅(jiān)實(shí)的。,為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？,(2) 實(shí)際計(jì)算機(jī)的設(shè)計(jì)與制造中，使用數(shù)字邏輯技術(shù)實(shí)現(xiàn)計(jì)算機(jī)的各種運(yùn)算的理論基礎(chǔ)是代數(shù)和布爾代數(shù)。布爾代數(shù)只是在形式演算方面使用了代數(shù)的方法，其內(nèi)容的實(shí)質(zhì)仍然是邏輯。依靠代數(shù)操作實(shí)現(xiàn)的指令系統(tǒng)具有（原始）遞歸性，而數(shù)字邏輯技術(shù)和集成電路技術(shù)只是計(jì)算機(jī)系統(tǒng)的一種產(chǎn)品的技術(shù)形式。,為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？,(3) 從計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言方面考察，語(yǔ)言的理論基礎(chǔ)是形式語(yǔ)言、自動(dòng)機(jī)與形式語(yǔ)義學(xué)。而形式語(yǔ)言、自動(dòng)機(jī)和形式語(yǔ)義學(xué)所采用的主要研究思想和方法來(lái)源于數(shù)理邏輯和代數(shù)。程序設(shè)計(jì)語(yǔ)言中的許多機(jī)制和方法，如子程序調(diào)用中的參數(shù)代換、賦值等都出自數(shù)理邏輯的方法。此外，在語(yǔ)言的語(yǔ)義研究中，四種語(yǔ)義方法最終可歸結(jié)為代數(shù)和邏輯的方法。這就是說(shuō)，數(shù)理邏輯和代數(shù)為語(yǔ)言學(xué)提供了方法論的基礎(chǔ)。,為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？,(4) 在計(jì)算機(jī)體系結(jié)構(gòu)的研究中，象容錯(cuò)計(jì)算機(jī)系統(tǒng)、Transputer計(jì)算機(jī)、陣列式向量計(jì)算機(jī)、可變結(jié)構(gòu)的計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)及其計(jì)算模型等都直接或間接與邏輯與代數(shù)密不可分。如容錯(cuò)計(jì)算機(jī)的重要基礎(chǔ)之一是多值邏輯，Transputer計(jì)算機(jī)的理論基礎(chǔ)是CSP理論，陣列式向量計(jì)算機(jī)必須以向量運(yùn)算為基礎(chǔ)，可變結(jié)構(gòu)的計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)及其計(jì)算模型主要采用邏輯與代數(shù)的方法。,為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？,(5) 從計(jì)算機(jī)各種應(yīng)用的程序設(shè)計(jì)方面考察，任何一個(gè)可在存儲(chǔ)程序式電子數(shù)字計(jì)算機(jī)上運(yùn)行的程序，其對(duì)應(yīng)的計(jì)算方法首先都必須是構(gòu)造性的，數(shù)據(jù)表示必須離散化，計(jì)算操作必須使用邏輯或代數(shù)的方法進(jìn)行，這些，都應(yīng)體現(xiàn)在算法和程序之中。此外，到現(xiàn)在為止，程序的語(yǔ)義及其正確性的理論基礎(chǔ)仍然是數(shù)理邏輯，或進(jìn)一步的模型論。,為什么說(shuō)數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？, 高等代數(shù)和一般抽象代數(shù)只解決了個(gè)體對(duì)象為簡(jiǎn)單個(gè)體的論域上的大量運(yùn)算問(wèn)題，但是對(duì)具有結(jié)構(gòu)特征和屬性成分的復(fù)雜個(gè)體的論域上的運(yùn)算問(wèn)題，表達(dá)和處理是不方便的，常常是有困難的。針對(duì)這類(lèi)對(duì)象的運(yùn)算操作及其正確性等語(yǔ)義學(xué)問(wèn)題，有必要發(fā)展泛代數(shù)和高階邏輯理論。,5.5 計(jì)算學(xué)科中的數(shù)學(xué) 方法,5.5.3 計(jì)算學(xué)科中常用的數(shù)學(xué) 概念和術(shù)語(yǔ),集合,構(gòu)造性數(shù)學(xué)方法的基礎(chǔ)。 集合就是一組無(wú)重復(fù)的對(duì)象的全體。 集合中的對(duì)象稱(chēng)為集合的元素。 如：計(jì)算機(jī)專(zhuān)業(yè)學(xué)生全部必修課程可以組成一個(gè)集合，其中的每門(mén)課程就是這一集合中的元素。,函數(shù),函數(shù)又稱(chēng)映射，是指把輸入轉(zhuǎn)變成輸出的運(yùn)算，該運(yùn)算也可理解為從某一“定義域”的對(duì)象到某一“值域”的對(duì)象的映射。函數(shù)是程序設(shè)計(jì)的基礎(chǔ)，程序定義了計(jì)算函數(shù)的算法，而定義函數(shù)的方法又影響著程序語(yǔ)言的設(shè)計(jì)，好的程序設(shè)計(jì)語(yǔ)言一般都便于函數(shù)的計(jì)算。 設(shè)f為一個(gè)函數(shù)，當(dāng)輸入值為a時(shí)輸出值為b，則記作：,關(guān)系,關(guān)系是一個(gè)謂詞，其定義域?yàn)閗元組的集合。通常的關(guān)系為二元關(guān)系，其定義域?yàn)橛行驅(qū)Φ募?，在這個(gè)集合中，我們說(shuō)有序?qū)Φ牡谝粋€(gè)元素和第二個(gè)元素有關(guān)系。如學(xué)生選課 學(xué)生 課程 成績(jī) 張三 文學(xué) 90 張三 哲學(xué) 95 李四 數(shù)學(xué) 80 李四 藝術(shù) 85 王五 歷史 92 王五 文學(xué) 88,等價(jià)關(guān)系,在關(guān)系中，有一種特殊的關(guān)系，即等價(jià)關(guān)系，它滿(mǎn)足以下3個(gè)條件： 自反性，即對(duì)集合中的每一個(gè)元素a，都有aRa； 對(duì)稱(chēng)性，即對(duì)集合中的任意元素a，b，aRb成立當(dāng)且僅當(dāng)bRa成立； 傳遞性，即對(duì)集合中的任意元素a，b，c，若aRb和bRc成立，則aRc一定成立。 等價(jià)關(guān)系的一個(gè)重要性質(zhì)是：集合A上的一個(gè)等價(jià)關(guān)系R可將A劃分為若干個(gè)互不相交的子集，稱(chēng)為等價(jià)類(lèi)。,例5.7 假設(shè)某人在唱歌（事件e1）的同時(shí)，還可以開(kāi)車(chē)（事件e2）或者步行（事件e3），但一個(gè)人不能同時(shí)開(kāi)車(chē)和步行。 問(wèn)：以上反映的并發(fā)現(xiàn)象，如用關(guān)系來(lái)表示時(shí)，是否是等價(jià)關(guān)系？ 答：以上反映的是一種并發(fā)（co）現(xiàn)象，如用關(guān)系來(lái)表示，則這種并發(fā)關(guān)系具有自反性和對(duì)稱(chēng)性， 即可表示為：e1 co e1，e2 co e2，e3 co e3；及e1 co e2（或e2 co e1），e1 co e3（或e3 co e1）， 不滿(mǎn)足傳遞性，即（e2 co e1）（e1 co e3）不能推出e2 co e3，即不能在開(kāi)車(chē)的同時(shí)，又步行。 因此，以上并發(fā)關(guān)系不是等價(jià)關(guān)系。,定義、定理和證明是數(shù)學(xué)的核心，也是計(jì)算學(xué)科理論形態(tài)的核心內(nèi)容。其中，定義是蘊(yùn)含在公理系統(tǒng)之中的概念和命題；定理是被證明為真的數(shù)學(xué)命題；證明是為使人們確信一個(gè)命題是真的而作的一種邏輯論證。 例5.8 在歐氏幾何中，平面角的定義為：平面角是在一平面內(nèi)，但不在一直線上的兩條相交線的相互傾斜度；等腰三角形的定理為：兩邊相等的三角形為等腰三角形。,5.5 計(jì)算學(xué)科中的數(shù)學(xué) 方法,5.5.3 證明方法,直接證明,假定p為真，通過(guò)使用公理或已證明的定理以及正確的推理規(guī)則證明q也為真，以此證明蘊(yùn)含式pq為真。這種證明方法為直接證明法。 例5.9 用直接證明法證明“若p是偶數(shù)，則p2是偶數(shù)”。 證明：假定p是偶數(shù)為真，設(shè)p=2k（k為整數(shù)）。由此可得，p2=2（2k2）。因此，p2是偶數(shù)（它是一個(gè)整數(shù)的2倍）。,間接證明,因?yàn)樘N(yùn)含式pq與其逆否命題qp等價(jià)，因此可以通過(guò)證明qp來(lái)證明蘊(yùn)含式pq為真。這種證明方法為間接證明法。 例5.10 用間接證明法證明“若p2是偶數(shù)，則p是偶數(shù)”。 證明：假定此蘊(yùn)含式后件為假，即假定p是奇數(shù)。則對(duì)某個(gè)整數(shù)k來(lái)說(shuō)有p=2k+1。由此可得p2=4k2+4k+1=2（2k2+2k）+1，因此，p2是奇數(shù)（它是一個(gè)整數(shù)的2倍加1）。因?yàn)閷?duì)這個(gè)蘊(yùn)含式后件的否定蘊(yùn)含著前件為假，因此該蘊(yùn)含式為真。,首先假定一個(gè)與原命題相反的命題成立，然后通過(guò)正確的推理得出與已知（或假設(shè)）條件、公理、已證過(guò)的定理等相互矛盾或自相矛盾的結(jié)果，以此證明原命題正確。這種證明方法就是反證法，也稱(chēng)歸謬法，是一種常用的數(shù)學(xué)證明方法。 例5.11 證 是無(wú)理數(shù),歸納法的定義,所謂歸納法，是指從特殊推理出一般的一種證明方法。歸納法可分為不完全歸納法、完全歸納法和數(shù)學(xué)歸納法。 2不完全歸納法 不完全歸納法是根據(jù)部分特殊情況作出推理的一種方法，該方法多用于無(wú)窮對(duì)象的論證，然而，論證的結(jié)果不一定正確。因此，不完全歸納法不能作為嚴(yán)格的證明方法。 3完全歸納法 完全歸納法也稱(chēng)窮舉法，它是對(duì)命題中存在的所有特殊情況進(jìn)行考慮的一種方法，用該方法論證的結(jié)果是正確的，然而，它只能用于“有限”對(duì)象的論證。,數(shù)學(xué)歸納法的形式化定義,根據(jù)數(shù)學(xué)歸納法的原理，可以對(duì)數(shù)學(xué)歸納法形式化地定義為： P(1)()(P(n)P(n+1)P(n) 例5.12 求證命題P(n)：“從1開(kāi)始連續(xù)n個(gè)奇數(shù)之和是n的平方”，即公式 1+3+5+（2n1）=n2成立。,證明,歸納基礎(chǔ)：當(dāng)n=1時(shí)，等式成立，即1=12 歸納步驟： 設(shè)對(duì)任意k1，P(k)成立，即： 1+3+5+（2K1）=K2 而 1+3+5+(2K1)+(2(K+1)1) = K2+2K+1=(K+1)2 則當(dāng)P(k)成立時(shí)，P(K+1)也成立，根據(jù)數(shù)學(xué)歸納法，該命題得證。,構(gòu)造性證明,構(gòu)造性證明通過(guò)找出一個(gè)使得命題P(a)為真的元素a，從而完成該函數(shù)值的存在性證明稱(chēng)為構(gòu)造性證明。 構(gòu)造性證明方法是計(jì)算科學(xué)中廣泛使用的一種證明方法，本章Armstrong公理系統(tǒng)的完備性證明就采用了構(gòu)造性的證明方法。,5.5 計(jì)算學(xué)科中的數(shù)學(xué) 方法,5.5.5 遞歸和迭代 (構(gòu)造性方法),遞歸及其有關(guān)概念,很多序列項(xiàng)常?？梢砸赃@樣的方式得到：由an1得到an，按這樣的法則，可以從一個(gè)已知的首項(xiàng)開(kāi)始，有限次地重復(fù)做下去，最后產(chǎn)生一個(gè)序列，該序列是 實(shí)現(xiàn)遞歸和迭代的基礎(chǔ)。 20世紀(jì)30年代，正是可計(jì)算的遞歸函數(shù)理論與圖靈機(jī)、演算和POST規(guī)范系統(tǒng)等理論一起為計(jì)算理論的建立奠定了基礎(chǔ)。,遞歸及其有關(guān)概念,遞歸關(guān)系指的是：一個(gè)數(shù)列的若干連續(xù)項(xiàng)之間的關(guān)系 遞歸數(shù)列指的是：由遞歸關(guān)系所確定的數(shù)列。 遞歸過(guò)程指的是：調(diào)用自身的過(guò)程。 遞歸算法指的是：包含遞歸過(guò)程的算法。 遞歸程序指的是：直接或間接調(diào)用自身的程序。 遞歸方法（也稱(chēng)遞推法），是一種在“有限”步驟內(nèi)，根據(jù)特定的法則或公式對(duì)一個(gè)或多個(gè)前面的元素進(jìn)行運(yùn)算，以確定一系列元素（如數(shù)或函數(shù)）的方法。,遞歸與數(shù)學(xué)歸納法,例5.13 計(jì)算56 計(jì)算方法之一：6，6+6=12，12+6=18，18+6=24，24+6=30； 計(jì)算方法之二：56，46，36，26，16；16+6=12，12+6=18，18+6=24，24+6=30； 從56開(kāi)始計(jì)算，假設(shè)一個(gè)剛學(xué)乘法的小學(xué)生計(jì)算不出這個(gè)數(shù)，那么，這個(gè)小學(xué)生一般會(huì)先計(jì)算46，然后再加6就可以了，若仍計(jì)算不出，則會(huì)再追溯到36，直到16，然后，再依次加6，最后得到30。這種計(jì)算方法其實(shí)就反映了一種遞歸的思想，這個(gè)例子還可以用更一般的遞歸關(guān)系表示： an=Can-1+g(n)，2，3，4， 其中，C是已知常數(shù)，g(n)是一個(gè)已知數(shù)列。,遞歸由遞歸基礎(chǔ)和遞歸步驟兩部分組成。 數(shù)學(xué)歸納法是一種論證方法，而遞歸是算法和程序設(shè)計(jì)的一種實(shí)現(xiàn)技術(shù)； 數(shù)學(xué)歸納法是遞歸的基礎(chǔ)。如果已知an-1就可以確定an。從數(shù)學(xué)歸納法的角度來(lái)看，這相當(dāng)于數(shù)學(xué)歸納法歸納步驟的內(nèi)容。但僅有這個(gè)關(guān)系，還不能確定這個(gè)數(shù)列，若使它完全確定，還應(yīng)給出這個(gè)數(shù)列的初始值a1，這相當(dāng)于數(shù)學(xué)歸納法歸納基礎(chǔ)的內(nèi)容。,遞歸的定義功能,例： 序列：2，5，11，23，an=2an1+1，請(qǐng)給出其遞歸定義。 解 該序列的遞歸定義如下： a1=2； 遞歸基礎(chǔ) an=2an1+1，n=2，3，4，； 遞歸步驟 例5.15 給出階乘F(n)=n!的遞歸定義 解 階乘F(n)=n!的遞歸定義如下： F(0)=1； 遞歸基礎(chǔ) F(n)=nF(n1)，n=1，2，3，； 遞歸步驟,阿克曼函數(shù),該函數(shù)是由希爾伯特的學(xué)生、德國(guó)著名數(shù)學(xué)家威爾海姆阿克曼于1928年發(fā)現(xiàn)的。這是一個(gè)圖靈機(jī)可計(jì)算的，但不是原始遞歸的函數(shù)。下面，我們介紹這個(gè)經(jīng)典的遞歸函數(shù)，并給出相應(yīng)的計(jì)算過(guò)程。 阿克曼函數(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,計(jì)算A(1,2),解: A(1,2)= A(0, A(1,1) =A(0, A(0, A(1,0) =A(0, A(0, A(0,1) =A(0, A(0,2) =A(0,3) =4,迭代,迭代與遞歸有著密切的聯(lián)系，甚至，一類(lèi)如X0=a，Xn+1=f(n)的遞歸關(guān)系也可以看作是數(shù)列的一個(gè)迭代關(guān)系。 可以證明，迭代程序都可以轉(zhuǎn)換為與它等價(jià)的遞歸程序， 反之，則不然。就效率而言，遞歸程序的實(shí)現(xiàn)要比迭代程序的實(shí)現(xiàn)耗費(fèi)更多的時(shí)間和空間。因此，在具體實(shí)現(xiàn)時(shí)，又希望盡可能將遞歸程序轉(zhuǎn)化為等價(jià)的迭代程序。,斐波那契數(shù)的求解算法而言，可以使用迭代方法或遞歸方法來(lái)解決。 一些遞歸算法，如求解梵天塔問(wèn)題的算法就不能用迭代方法，而只能用遞歸方法。,5.5 計(jì)算學(xué)科中的數(shù)學(xué) 方法,5.5.6 公理化方法,理論體系,從數(shù)學(xué)的角度來(lái)說(shuō)，理論是基本概念、基本原理或定律（聯(lián)系這些概念的判斷）以及由這些概念與原理邏輯推理出來(lái)的結(jié)論組成的集合，該概念可以形式化的定義為： T=， 其中： （1）表示理論； （2）表示基本概念的集合； （3）表示基本原理或定律的集合； （4）表示由這些概念與原理邏輯推理出來(lái)的結(jié)論組成的集合。,構(gòu)建理論體系的常用方法,每一個(gè)理論都由一組特定的概念和一組特定的命題組成。 在一個(gè)理論中，基本概念（原始概念）和基本命題（原始命題）必須是明確的，否則就會(huì)出現(xiàn)“循環(huán)定義”和“循環(huán)論證”的嚴(yán)重問(wèn)題。 構(gòu)建一個(gè)理論體系必須采用科學(xué)的方法。 公理化方法 邏輯和歷史相統(tǒng)一的方法 從抽象上升到具體的方法。,公理化方法,公理化方法是一種構(gòu)造理論體系的演繹方法，也是計(jì)算科學(xué)的一種典型方法。 從盡可能少的基本概念、公理出發(fā)，運(yùn)用演繹推理規(guī)則，推出一系列的命題，從而建立整個(gè)理論體系的思想方法。 它能幫助學(xué)生認(rèn)識(shí)一個(gè)系統(tǒng)如何嚴(yán)格表述，認(rèn)識(shí)到完備性和無(wú)矛盾性對(duì)一個(gè)公理系統(tǒng)的重要性，認(rèn)識(shí)每一條公理深刻的背景，獨(dú)立性和它的作用?？上?，其深刻的哲學(xué)意義、學(xué)術(shù)深度和理解上的困難性使得它在本科的課程中較少出現(xiàn)。,公理化方法,近年來(lái)，這一方法出現(xiàn)在一些學(xué)科的前沿研究中。除了形式語(yǔ)義學(xué)的研究中使用公理化方法外，開(kāi)放信息系統(tǒng)的思想和設(shè)計(jì)，自定義邏輯框架系統(tǒng)的研究，以及分布式代數(shù)系統(tǒng)的研究都采用了公理化方法或吸取了公理化方法的思想。隨著學(xué)科發(fā)展的深化，預(yù)計(jì)這一方法還將在一些分支方向上得到運(yùn)用，并推動(dòng)學(xué)科進(jìn)一步深入發(fā)展。,公理系統(tǒng)的3個(gè)條件,用公理化構(gòu)建的理論體系稱(chēng)為公理系統(tǒng)，該公理系統(tǒng)需要滿(mǎn)足無(wú)矛盾性、獨(dú)立性和完備性的條件。 （1）無(wú)矛盾性。 （2）獨(dú)立性。 （3）完備性。,簡(jiǎn)單化是科學(xué)研究追求的目標(biāo)之一。一般而言，正確的一定是簡(jiǎn)單的（注意，這句話(huà)是單向的，反之不一定成立）。 關(guān)于公理系統(tǒng)的完備性要求，自哥德?tīng)柊l(fā)表關(guān)于形式系統(tǒng)的“不完備性定理”的論文后，數(shù)學(xué)家們對(duì)公理系統(tǒng)的完備性要求大大放寬了。 也就是說(shuō)，能完備更好，即使不完備，同樣也具有重要的價(jià)值。,公理化方法在計(jì)算學(xué)科中的應(yīng)用,公理化方法主要用于計(jì)算學(xué)科理論形態(tài)方面的研究。在計(jì)算學(xué)科各分支領(lǐng)域，均采用了公理化方法。如 形式語(yǔ)義學(xué) 關(guān)系數(shù)據(jù)庫(kù)理論 分布式代數(shù)系統(tǒng) 計(jì)算認(rèn)知領(lǐng)域,例5.18 正整數(shù)的公理化概括,原始概念：1； 原始命題（公理）：任何正整數(shù)n或者等于1，或者可以從1開(kāi)始，重復(fù)地“加1”來(lái)得到它。,例5.19 平面幾何的公理化概括（歐氏幾何）,以點(diǎn)、線、面為原始概念，以5條公設(shè)和5條公理為原始命題，給出了平面幾何中的119個(gè)定義，465條命題及其證明，構(gòu)成了歷史上第一個(gè)數(shù)學(xué)公理體系。 原始概念：點(diǎn)、線、面 原始命題（公設(shè)和公理）如下： 公設(shè)1：兩點(diǎn)之間可作一條直線； 公設(shè)2：一條有限直線可不斷延長(zhǎng)； 公設(shè)3：以任意中心和直徑可以畫(huà)圓； 公設(shè)4：凡直角都彼此相等； 公設(shè)5：在平面上，過(guò)給定直線之外的一點(diǎn)，存在且僅存在一條平行線，即所謂的“平行公設(shè)（公理）”。,例5.20 中國(guó)古代唯一的一次公理化嘗試：周髀算經(jīng),據(jù)有關(guān)記載，周髀算經(jīng)成書(shū)于公元前100年左右。在周髀算經(jīng)中，介紹了一個(gè)描述天象的蓋天學(xué)說(shuō)，該學(xué)說(shuō)構(gòu)建了一個(gè)幾何宇宙模型。 該學(xué)說(shuō)中的公理有兩個(gè)：一個(gè)是“天地為平行平面，天地相距80,000里，在北極下方的大地中央有一底面直徑為23,000里，高為60,000里的上尖下粗的 “璇璣”（即極下，極下陽(yáng)光照不到，故不生萬(wàn)物）； 另一個(gè)是關(guān)于太陽(yáng)光照以及人目所見(jiàn)的極限范圍，即“日照四旁各十六萬(wàn)七千里；人所望見(jiàn)，遠(yuǎn)近宜如日光所照”，其大意為，日光向四周照射的極限距離是167,000里，人所見(jiàn)到也是這個(gè)距離。換言之，日光照不到167,000里之外，人也看不見(jiàn)167,000里之外。,從公理可以演繹出：夏至南萬(wàn)六千里，冬至南十三萬(wàn)五千里，日中立竿無(wú)影。此一者天道之?dāng)?shù)。周髀長(zhǎng)八尺，夏至之日晷一尺六寸。髀者，股也；正晷者，勾也。正南千里，勾一尺五寸；正北千里，勾一尺七寸。其大意為，在某地豎一個(gè)8尺高的竿，太陽(yáng)移動(dòng)了一千里，這個(gè)竿的影子和原來(lái)的相差一寸，即日影千里差一寸。 而從“日照四旁”167,000里，以及用公理演繹出的冬至日道半徑238,000里，又可導(dǎo)出宇宙半徑為405,000里，從而構(gòu)建了一個(gè)天、地為圓形平行平面的宇宙模型。,今天，我們知道，這個(gè)宇宙模型的描述與實(shí)際的天象吻合得并不好，與同時(shí)代古希臘類(lèi)似模型相比，也存在較大的差距，而當(dāng)時(shí)，我國(guó)天文學(xué)家完全可以用代數(shù)方法相當(dāng)精確地解決一些天文學(xué)問(wèn)題，至于宇宙究竟是什么形狀或結(jié)構(gòu)，完全可以不去過(guò)問(wèn)。然而，周髀算經(jīng)是個(gè)例外，并成為我國(guó)古代學(xué)者惟一的一次公理化方法的嘗試，這種思想，是受外來(lái)因素的影響，還是我國(guó)本土科學(xué)中某種隨機(jī)出現(xiàn)的變異？已引起科學(xué)史領(lǐng)域?qū)＜业臉O大興趣。,5.6 計(jì)算學(xué)科中的數(shù)學(xué) 方法,5.6.7 形式化方法,具體公理系統(tǒng)和抽象公理系統(tǒng),在歐氏幾何公理系統(tǒng)中，原始概念（點(diǎn)、線、面）和所有的公理都有直觀的背景或客觀的意義，像這樣有現(xiàn)實(shí)世界背景的公理系統(tǒng)，一般被稱(chēng)為具體公理系統(tǒng)。 由于非歐幾何的出現(xiàn)，使人們感到具體公理系統(tǒng)過(guò)于受直覺(jué)的局限。因而，在19世紀(jì)末和20世紀(jì)初，一些杰出的數(shù)學(xué)家和邏輯學(xué)家開(kāi)始了對(duì)抽象公理系統(tǒng)的研究。,在抽象公理系統(tǒng)中，原始概念的直覺(jué)意義被忽視，甚至沒(méi)有任何預(yù)先設(shè)定的意義，而公理也無(wú)需以任何實(shí)際意義為背景，它們無(wú)非是一些形式約定的符號(hào)串。這時(shí)，抽象公理系統(tǒng)可以有多種解釋。 形式化的運(yùn)算規(guī)則1+1可以解釋為一個(gè)蘋(píng)果加一個(gè)蘋(píng)果，或者為一本書(shū)加一本書(shū)； 布爾代數(shù)抽象公理系統(tǒng)可以解釋為有關(guān)命題真值的命題代數(shù)，或者有關(guān)電路設(shè)計(jì)研究的開(kāi)關(guān)代數(shù)。,形式系統(tǒng)的組成部分,初始符號(hào)。初始符號(hào)不具有任何意義。 形式規(guī)則。形式規(guī)則規(guī)定一種程序，借以判定哪些符號(hào)串是本系統(tǒng)中的公式，哪些不是。 公理。即在本系統(tǒng)的公式中，確定不加推導(dǎo)就可以斷定的公式集。 變形規(guī)則。變形規(guī)則亦稱(chēng)演繹規(guī)則或推導(dǎo)規(guī)則。變形規(guī)則規(guī)定，從已被斷定的公式，如何得出新的被斷定公式。被斷定的公式又稱(chēng)為系統(tǒng)中的定理。,形式系統(tǒng)的基本特點(diǎn),嚴(yán)格性 形式系統(tǒng)中，初始符號(hào)和形式規(guī)則都要進(jìn)行嚴(yán)格的定義，不允許出現(xiàn)在有限步內(nèi)無(wú)法判定的公式。形式系統(tǒng)采用的是一種純形式的機(jī)械方法，它的嚴(yán)格性高于一般的數(shù)學(xué)推導(dǎo)。 抽象性 抽象性不是形式系統(tǒng)的專(zhuān)利，抽象是人們認(rèn)識(shí)客觀世界的基本方法，只不過(guò)形式系統(tǒng)具有更強(qiáng)的抽象性。 形式系統(tǒng)的抽象性表現(xiàn)在它自身僅僅是一個(gè)符號(hào)系統(tǒng)，除了表示符號(hào)間的關(guān)系（字符號(hào)串的變換）外，不表示任何別的意義。,形式系統(tǒng)的局限性,不完備性 1931年，哥德?tīng)柼岢龅年P(guān)于形式系統(tǒng)的“不完備性定理”指出：如果一個(gè)形式的數(shù)學(xué)理論是足夠復(fù)雜的（復(fù)雜到所有的遞歸函數(shù)在其中都能夠表示），而且它是無(wú)矛盾的，那么在這一理論中存在一個(gè)語(yǔ)句，而這一語(yǔ)句在這一理論中是既不能證明，也不能否證的。,形式系統(tǒng)的局限性,不可判定性 如果對(duì)一類(lèi)語(yǔ)句C而言，存在一個(gè)算法AL，使得對(duì)C中的任一語(yǔ)句S而言，可以利用算法AL來(lái)判定其是否成立，則C稱(chēng)為可判定的，否則，稱(chēng)為不可判定的。 著名的“停機(jī)問(wèn)題”就是一個(gè)不可判定性的問(wèn)題。該問(wèn)題是指，一個(gè)任給的圖靈機(jī)對(duì)于一個(gè)任給的輸入而言是否停機(jī)的問(wèn)題。圖靈證明這類(lèi)問(wèn)題是不可判定的。 需要指出的是：計(jì)算機(jī)系統(tǒng)就是一種形式系統(tǒng)，因此，計(jì)算機(jī)系統(tǒng)一樣也具有形式系統(tǒng)的局限性。,形式化與公理化,形式化不一定導(dǎo)致公理化，公理系統(tǒng)也不一定是形式系統(tǒng)。 如歐氏幾何公理系統(tǒng)就不是形式系統(tǒng)。 形式化與公理化雖然不同，但在近代數(shù)學(xué)中，形式系統(tǒng)大都是形式化的公理系統(tǒng)。,第5章 計(jì)算學(xué)科的內(nèi)容 與方法,5.5 布爾代數(shù)基礎(chǔ),邏輯與代數(shù)是計(jì)算機(jī)科學(xué)最重要的基礎(chǔ)，布爾代數(shù)是數(shù)理邏輯早期的雛形，是一種用代數(shù)演算的方法來(lái)研究思維結(jié)構(gòu)的邏輯系統(tǒng)。 問(wèn)題：什么是邏輯呢？ 對(duì)邏輯來(lái)說(shuō)不存在清規(guī)戒律，每個(gè)人都可以構(gòu)造自己的邏輯，即他自己的語(yǔ)言形式，只要他愿意。對(duì)他的唯一要求是：如果他想討論這種邏輯，那么他必須說(shuō)清楚他的方法，并給出語(yǔ)法規(guī)則，而不是給出哲學(xué)論據(jù)。 Carnap（卡爾納普）,5.5 布爾代數(shù)基礎(chǔ),5.5.1 集合的基本概念與 基本運(yùn)算,概念,由事物或?qū)ο蠼M成的集體，無(wú)論它們是由其成員通過(guò)枚舉方式直接表示出來(lái)的，還是由其成員所具有的某些本質(zhì)屬性表示出來(lái)的，都稱(chēng)為集合。 稱(chēng)兩個(gè)集合是相等的，如果構(gòu)成這兩個(gè)集合的成員完全相同。集合的成員也叫元素。 一個(gè)集合A中元素的個(gè)數(shù)叫做集合A的基數(shù)，記為A。 請(qǐng)注意，這不是基數(shù)的嚴(yán)格的定義。對(duì)有窮集合，這樣定義基數(shù)勉強(qiáng)可行，但對(duì)無(wú)窮集合不恰當(dāng)。有關(guān)集合基數(shù)的概念和知識(shí)將來(lái)讀者會(huì)在離散數(shù)學(xué)或集合論等課程中系統(tǒng)地學(xué)習(xí)，目前，我們暫且使用這種不嚴(yán)格的直觀上的定義。,2. 集合的三種描述方法,枚舉法：列出所有元素的表示方法。 如1至5的整數(shù)集合可表示為： =1，2，3，4，5； 外延表示法：當(dāng)集合中所列元素的一般形式很明顯時(shí)，可只列出部分元素，其他則用省略號(hào)表示。 如斐波那契數(shù)列可表示為： 0，1，1，2，3，5，8，13，21，34， ； 謂詞表示法：用謂詞來(lái)概括集合中元素的屬性。 如斐波那契數(shù)列可表示為： Fn|Fn+2=Fn+1+Fn，F(xiàn)0=0，F(xiàn)1=1，n0,3. 從屬與包含關(guān)系,通常用大寫(xiě)英文字母作為集合的名稱(chēng)。若某事物a是集合A的一個(gè)元素，則記為： aA 并說(shuō)“a屬于A”，或者說(shuō)“a在A中”。 若a不是集合A的元素，則記為： a A 當(dāng)以枚舉形式表示一個(gè)集合時(shí)，我們用一個(gè)大括號(hào)把這些枚舉的元素括起來(lái)以表示這個(gè)集合。,3. 從屬與包含關(guān)系,例1 麻雀，黃鸝，杜鵑，白鷺，紅嘴鷗是一個(gè)由五種鳥(niǎo)組成的集合； 如果a,b,c,d,x,y,z是由英語(yǔ)的26個(gè)小寫(xiě)字母組成的集合。 例2 Axax2+bx+c0 且 a,b,cR，R是實(shí)數(shù)集。 例3 Ba,b,aa,ab,bb,aaa,aab,abb,bbb,aaaa, 這種帶省略的表示形式實(shí)際上可表示一些集合元素有某種出現(xiàn)規(guī)律的無(wú)窮集合。,3. 從屬與包含關(guān)系,集合的表示應(yīng)當(dāng)注意以下兩點(diǎn)： (1) 同一個(gè)集合中的元素是互不相同的。 (2) 集合中的元素之間不規(guī)定次序。 與空集合相對(duì)應(yīng)的一個(gè)大的集合是所謂的全集合，即一切事物構(gòu)成的集合。這是一個(gè)虛構(gòu)的集合，但它在布爾代數(shù)的運(yùn)算中是有用的。我們用1來(lái)表示這個(gè)虛設(shè)的全集合。,3. 從屬與包含關(guān)系,考慮兩個(gè)集合A和B。若集合A的每一個(gè)元素也是集合B的一個(gè)元素，則稱(chēng)集合B包含集合A，也稱(chēng)集合A包含在集合B中，記為AB 若AB，則稱(chēng)A是B的子集合，B是A的母集合。顯然，對(duì)任何集合A，有AA。 若集合A、B之間存在AB且AB，則稱(chēng)A是B的真子集合，記為AB。若AB，又有BA，則可以得出結(jié)論AB。這是因?yàn)锳的元素都是B的元素，而B(niǎo)的元素也是A的元素，說(shuō)明A，B中擁有相同的元素，所以A和B相同，故相等。顯然，對(duì)任何集合A，A1。特別地，1。,3. 從屬與包含關(guān)系,通常用大寫(xiě)英文字母作為集合的名稱(chēng)。若某事物a是集合A的一個(gè)元素，則記為： aA 并說(shuō)“a屬于A”，或者說(shuō)“a在A中”。 若a不是集合A的元素，則記為： a A 當(dāng)以枚舉形式表示一個(gè)集合時(shí)，我們用一個(gè)大括號(hào)把這些枚舉的元素括起來(lái)以表示這個(gè)集合。 例1 麻雀，黃鸝，杜鵑，白鷺，紅嘴鷗是一個(gè)由五種鳥(niǎo)組成的集合；,4. 集合的基本運(yùn)算,集合的并 設(shè)A、B為兩個(gè)任意集合，將集合A的元素和集合B的元素合并在一起，組成一個(gè)新的集合C，稱(chēng)為集合A和集合B的并集，簡(jiǎn)稱(chēng)A和B的并。可表示為： CABxxAxB 求并集的運(yùn)算稱(chēng)為并（運(yùn)算）。 例5.1 若A=a，b，c，d，B=b，d，e，求集合A和B的并。 解：ABa，b，c，d，e,集合的交,設(shè)A、B為兩個(gè)任意集合，定義A和B的公共元素構(gòu)成的集合C為A和B的交集，簡(jiǎn)稱(chēng)A和B的交，記為: CABxxAxB 例5.3 若A=x | x -5，B=x|x5xx1x5x1,集合的差,設(shè)A、B為兩個(gè)任意集合，所有屬于A而不屬于B的一切元素構(gòu)成的集合S，稱(chēng)為A和B的差集?？杀硎緸椋?S=AB=xxAxB。 求差集的運(yùn)算稱(chēng)為差（運(yùn)算）。 例5.2 若A=a，b，c，d，B=b，d，e，求集合A和B的差。 解：AB=a，c,集合的補(bǔ),設(shè)I為全集，A為I的任意一子集，IA則為A的補(bǔ)集，記為A?？杀硎緸?A=IA=xxI， 求補(bǔ)集的運(yùn)算稱(chēng)為補(bǔ)（運(yùn)算）求補(bǔ)集的運(yùn)算稱(chēng)為補(bǔ)（運(yùn)算） 例5.4 若I=x5x5，A=x0x1，求。 解：A=IA=x5x01x5,集合的乘積,集合A1，A2，An的乘積一般用法國(guó)數(shù)學(xué)家笛卡爾（Rene Descartes）的名字命名，即笛卡爾積。該乘積表示如下： A1A2An=（a1，a2，an）aiAi，i1，2，n A1A2An的結(jié)果是一個(gè)有序元組的集合。 例5.5 若A=1，2，3，B=a，b，求AB。 解：AB=（1，a），（1，b），（2，a），（2，b），（3，a），（3，b）,集合運(yùn)算的定理,定理1 設(shè)A為一個(gè)集合，B為A的補(bǔ)集合，I為全集，則 (1) AB， (2) ABI， (3) I， (4) I， (5) (A)A， (6) (I)I， (7) ()。 我們選擇證明其中的(1)，其余的證明留給讀者作為練習(xí)。,集合運(yùn)算的定理,證明 (1) 用反證法。設(shè)AB，則必存在非空元素xAB，故xA且xB，此與B為A的補(bǔ)集合矛盾。所以， AB。 例4 設(shè)Aa,b,c,d，Bc,d,e,f，Ce,f,g,h，則 ABc,d， ABa,b,c,d,e,f， AC， ACa,b,c,d,e,f,g,h。,集合運(yùn)算的定理,根據(jù)定義，不難證明定理2。 定理2 對(duì)任意集合A和集合B，有 (1) ABBA， （交換律） (2) ABBA， （交換律） (3) AAA， (4) AAA， （冪等律） (5) AA， (6) AA1， (7) A， (8) AA。,集合運(yùn)算的定理,我們選擇證明其中的(2)，其余的(1)、(3)-(8)大家可以自己試著去證明。 證明 (2) 我們分兩部分來(lái)證明。首先證明左邊的集合是右邊集合的子集合，然后再證明右邊的集合是左邊集合的子集合。這樣，若兩個(gè)集合互為子集合時(shí)，必然相等。 設(shè)任意元素xAB，則xA或者xB，也可表述為xB或者xA，故ABBA； 同理可證，BAAB。 所以，ABBA。 定理2(2)的上述證明方法是證明兩個(gè)集合相等時(shí)最常用的方法，也是最基本的方法。,5. 集合上的一些基本關(guān)系,下面我們?cè)诩舷嘌a(bǔ)、包含、交與并的基礎(chǔ)上，首先來(lái)建立一些基本關(guān)系。 定理3 設(shè)A，B為任意集合，則 (1) ABA， (2) ABB， (3) AAB， (4) BAB。 我們選擇證明其中的(1)，其余的(2)-(4)大家可以自己試著去證明。 證明 (1) 設(shè)任意元素xAB，由交的定義知，xA，故ABA。 ,5. 集合上的一些基本關(guān)系,定理4 設(shè)A、B為任意集合，則 (1) AB，當(dāng)且僅當(dāng)ABA， (2) ABA，當(dāng)且僅當(dāng)ABB， (3) ABB，當(dāng)且僅當(dāng)AB。 這個(gè)定理說(shuō)明了一個(gè)循環(huán)等價(jià)關(guān)系。象這樣的等價(jià)關(guān)系，今后可用來(lái)作等價(jià)的概念定義。 證明 (1) 我們分兩部分來(lái)證明定理的充分性。 設(shè)任意元素xAB，故xA且xB，可得ABA； 又設(shè)任意元素xA，由AB知xB，故xAB，可得AAB。 綜合、，知ABA。 由ABA導(dǎo)出AB是顯然的。 ,5. 集合上的一些基本關(guān)系,上面的證明中，仍然采用了論證兩個(gè)集合相等最基本的方法，即設(shè)法先證明等式兩邊的集合互為子集合。若兩個(gè)集合互為子集合，那么，顯然這兩個(gè)集合是相等的。 證明一個(gè)定理，有時(shí)候需要從定義出發(fā)推導(dǎo)、論證，有時(shí)候需要引用已知的結(jié)論來(lái)簡(jiǎn)化證明步驟。事實(shí)上，定理4(1)的證明中第一部分可以直接引用定理3的(1)。今后我們應(yīng)該逐步習(xí)慣于簡(jiǎn)化的證明方式。,5. 集合上的一些基本關(guān)系,定理5（De Morgan 律） 設(shè)A、B為任意集合，則 (1) (AB)AB， (2) (AB)AB。 證明 我們只要證明其中的一個(gè)就可以了，因?yàn)檫@兩個(gè)式子中的任何一個(gè)是另一個(gè)在相補(bǔ)關(guān)系下的直接結(jié)果。下面，我們證明(1)。 設(shè)任意元素x(AB)，則x(AB)，因此x A或xB。換言之xA或xB，故xAB。所以， (AB)AB； 反之，設(shè)任意元素xAB，則xA或xB。換 言之xA或xB，因此x(AB)，故x(AB)。所以: AB(AB) 從而，可知(AB)AB。 ,5. 集合上的一些基本關(guān)系,定理6 對(duì)任意的集合A，A。 證明 使用反證法。假設(shè)定理不成立，即存在集合A，使得A不成立。這就是說(shuō)，存在元素x,但xA，這與是空集合相矛盾。故定理成立，空集合是一切集合的子集合。 定理7 空集合是唯一的。 證明 設(shè)1和2都是空集合，由定理6知: 11 且 21， 所以12。 ,6. 集合上的一些運(yùn)算定律,定理8 設(shè)A、B、C是任意的集合，則 (1) A(BC)(AB)C， （結(jié)合律） (2) A(BC)