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

計(jì)算科學(xué)內(nèi)容和方法第1頁(yè)，共178頁(yè)，2023年，2月20日，星期四

第5章計(jì)算學(xué)科的內(nèi)容

與方法5.1計(jì)算科學(xué)的基本問題第2頁(yè)，共178頁(yè)，2023年，2月20日，星期四能行性能行性：什么能（有效地）自動(dòng)進(jìn)行，什么不能（有效地）自動(dòng)進(jìn)行。“能行性”這個(gè)計(jì)算學(xué)科的根本問題決定了計(jì)算機(jī)本身的結(jié)構(gòu)和它處理的對(duì)象都是離散型的，甚至許多連續(xù)型的問題也必須在轉(zhuǎn)化為離散型問題以后才能被計(jì)算機(jī)處理。例如，計(jì)算定積分就是把它變成離散量，再用分段求和的方法來(lái)處理的。第3頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算科學(xué)的發(fā)展主線具體來(lái)說，有三大問題：1）計(jì)算的平臺(tái)和環(huán)境問題（計(jì)算模型問題）2）計(jì)算過程的能行操作和效率問題（算法問題）3）計(jì)算的正確性問題（語(yǔ)義學(xué)問題）計(jì)算機(jī)研究的目標(biāo)是:拓展和提高計(jì)算機(jī)的應(yīng)用領(lǐng)域和應(yīng)用水平。圍繞學(xué)科的三個(gè)基本問題使學(xué)科的發(fā)展形成了三條相對(duì)獨(dú)立的主線，形成了許多相對(duì)獨(dú)立的分支學(xué)科和研究方向。不同時(shí)期，圍繞著學(xué)科的一些重大問題和基本問題，若干方向便構(gòu)成了所謂的主流方向，由主流方向又形成了學(xué)科的發(fā)展主線。第4頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算的平臺(tái)與環(huán)境問題計(jì)算的平臺(tái)與環(huán)境問題是指描述計(jì)算問題的計(jì)算模型，或者實(shí)際制造出來(lái)的針對(duì)各種待處理問題特點(diǎn)和要求的自動(dòng)計(jì)算機(jī)器。不難看出，理論研究中提出的各種計(jì)算模型，各種實(shí)際的計(jì)算機(jī)系統(tǒng)，各種高級(jí)程序設(shè)計(jì)語(yǔ)言，各種計(jì)算機(jī)體系結(jié)構(gòu)，各種軟件開發(fā)工具與環(huán)境，編譯程序與操作系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)等都是圍繞這一基本問題發(fā)展而來(lái)的，其內(nèi)容實(shí)質(zhì)可歸結(jié)為計(jì)算的模型問題，也就是說，這個(gè)基本問題實(shí)際上關(guān)心的是計(jì)算問題在理論上是否能行的問題。第5頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算過程的能行操作與效率問題含義是：當(dāng)一個(gè)問題在判明為可計(jì)算的性質(zhì)后，從具體解決這個(gè)問題著眼，必須按照能行可構(gòu)造的特點(diǎn)與要求，給出實(shí)際解決該問題的一步一步的具體操作，同時(shí)還必須確保這樣一種過程的開銷成本是我們能夠承受的。相關(guān)的分支學(xué)科有：數(shù)值與非數(shù)值計(jì)算方法，算法設(shè)計(jì)與分析，結(jié)構(gòu)化程序設(shè)計(jì)技術(shù)，密碼學(xué)與快速算法，演化計(jì)算，程序設(shè)計(jì)方法學(xué)，自動(dòng)布線，RISC技術(shù)，人工智能的邏輯基礎(chǔ)等。第6頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算的正確性問題計(jì)算的正確性是指：一個(gè)計(jì)算問題在給出了能行操作序列并解決了其效率問題之后，必須確保計(jì)算的正確性，否則，計(jì)算是無(wú)意義的，也是容易產(chǎ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ì)算的正確性問題常常歸結(jié)為各種語(yǔ)言的語(yǔ)義問題。第7頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算科學(xué)的三大基本問題計(jì)算學(xué)科的三個(gè)基本問題普遍出現(xiàn)在學(xué)科的各個(gè)分支學(xué)科和研究方向之中，是學(xué)科研究與發(fā)展中經(jīng)常面對(duì)而又必須解決的問題。循著這一線索，我們不難看出，整個(gè)學(xué)科正是在圍繞這些基本問題和不同時(shí)期重大問題而展開的研究與發(fā)展中形成了學(xué)科的發(fā)展主線與主流方向。第8頁(yè)，共178頁(yè)，2023年，2月20日，星期四

第5章計(jì)算學(xué)科的內(nèi)容

與方法5.2計(jì)算科學(xué)內(nèi)容的三個(gè)層面第9頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(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í)別與圖像處理等方向。第10頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算科學(xué)的專業(yè)基礎(chǔ)層它是為應(yīng)用層提供技術(shù)和環(huán)境的一個(gè)層面，包括軟件開發(fā)方法學(xué)，計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)，程序設(shè)計(jì)科學(xué)，計(jì)算機(jī)體系結(jié)構(gòu)，電子計(jì)算機(jī)系統(tǒng)基礎(chǔ)。其中，軟件開發(fā)方法學(xué)涵蓋順序、并行與分布式軟件開發(fā)方法學(xué)，如軟件工程技術(shù)，軟件開發(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ù)等方向。第11頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(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é)）等。第12頁(yè)，共178頁(yè)，2023年，2月20日，星期四

移動(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ò)與開放系統(tǒng)互聯(lián)標(biāo)準(zhǔn)軟件測(cè)試技術(shù)人機(jī)工程學(xué)（人機(jī)界面）計(jì)算軟件開發(fā)方法學(xué):軟件工程技術(shù)、程序設(shè)計(jì)方法學(xué)、軟件開發(fā)工具和環(huán)境、軟件開發(fā)規(guī)范科學(xué)編碼理論密碼學(xué)計(jì)算機(jī)體系結(jié)構(gòu)程序理論數(shù)據(jù)表示理論與數(shù)據(jù)庫(kù)系統(tǒng)專業(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ù)論第13頁(yè)，共178頁(yè)，2023年，2月20日，星期四

第5章計(jì)算學(xué)科的內(nèi)容

與方法5.3計(jì)算科學(xué)的發(fā)展主線第14頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算科學(xué)的發(fā)展主線在計(jì)算機(jī)基礎(chǔ)研究、應(yīng)用基礎(chǔ)研究和技術(shù)開發(fā)與應(yīng)用的研究中，計(jì)算學(xué)科逐步發(fā)展形成了三條相對(duì)獨(dú)立的主線：1）計(jì)算模型與計(jì)算機(jī)系統(tǒng)2）計(jì)算模型、語(yǔ)言與軟件開發(fā)方法學(xué)3）應(yīng)用數(shù)學(xué)與計(jì)算機(jī)應(yīng)用第15頁(yè)，共178頁(yè)，2023年，2月20日，星期四

第5章計(jì)算學(xué)科的內(nèi)容

與方法5.4計(jì)算科學(xué)的分類與分支學(xué)科簡(jiǎn)介第16頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(gòu)造性數(shù)學(xué)基礎(chǔ)對(duì)數(shù)學(xué)基礎(chǔ)問題的討論促進(jìn)了構(gòu)造性數(shù)學(xué)的產(chǎn)生和發(fā)展，產(chǎn)生了數(shù)學(xué)發(fā)展史上著名的三大邏輯學(xué)派：邏輯主義學(xué)派，形式主義學(xué)派和直覺主義邏輯學(xué)派。盡管數(shù)學(xué)科學(xué)的發(fā)展在計(jì)算科學(xué)的發(fā)展中得到廣泛的應(yīng)用，但是與計(jì)算科學(xué)在科學(xué)方法論上形成一致的是構(gòu)造性數(shù)學(xué)。這是直覺主義所以受到計(jì)算科學(xué)家歡迎的原因?？梢赃@么說：歷史上，對(duì)計(jì)算的能行性和可構(gòu)造性研究的最著名的產(chǎn)物要數(shù)圖靈機(jī)。如果沒有19世紀(jì)末20世紀(jì)初關(guān)于數(shù)學(xué)基礎(chǔ)問題的討論，沒有直覺主義學(xué)派對(duì)數(shù)學(xué)的貢獻(xiàn)，計(jì)算科學(xué)可能要推遲出現(xiàn)。第17頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(gòu)造性數(shù)學(xué)基礎(chǔ)數(shù)理邏輯與抽象代數(shù)是計(jì)算科學(xué)最重要的兩項(xiàng)數(shù)學(xué)基礎(chǔ)，它們的研究思想和研究方法在計(jì)算科學(xué)許多有深度的領(lǐng)域得到了最廣泛的應(yīng)用。數(shù)理邏輯是研究推理的科學(xué)，特別，在過去主要是研究數(shù)學(xué)中推理的科學(xué)。數(shù)理邏輯與哲學(xué)有著密切的聯(lián)系，其哲學(xué)方面是形式邏輯，而形式邏輯的數(shù)學(xué)化方面構(gòu)成了數(shù)理邏輯的研究?jī)?nèi)容。第18頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(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)的，或稱無(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é)的研究。第19頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(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)的，或稱無(wú)矛盾的，實(shí)際上是要保證該數(shù)學(xué)理論對(duì)客觀世界或應(yīng)用范疇的（語(yǔ)義）解釋是無(wú)矛盾的，用邏輯學(xué)的術(shù)語(yǔ)來(lái)說就是該數(shù)學(xué)理論必須存在模型。這在方法論上是靠邏輯學(xué)中的模型理論提供的。而要學(xué)習(xí)模型論的內(nèi)容，僅有命題演算、一階謂詞演算的知識(shí)是不夠的。對(duì)于(2)中提及的標(biāo)準(zhǔn)，讀者在今后的學(xué)習(xí)中會(huì)逐步體會(huì)到其涵義。第20頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(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é)等許多方面都離不開代數(shù)。第21頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算的數(shù)學(xué)理論所謂計(jì)算的數(shù)學(xué)理論是指一切關(guān)于能行性問題的數(shù)學(xué)理論的總和。也有一種更具體的定義是指一切關(guān)于計(jì)算與計(jì)算模型問題的數(shù)學(xué)理論的總和。計(jì)算理論廣義的可以看作同計(jì)算的數(shù)學(xué)理論，狹義的主要指算法理論、可計(jì)算理論、計(jì)算復(fù)雜性理論。第22頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(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)已開始轉(zhuǎn)到計(jì)算機(jī)的組織結(jié)構(gòu)。集成電路對(duì)電路和功能部件的高集成度和計(jì)算機(jī)設(shè)計(jì)與軟件開發(fā)之間建立的密切關(guān)系，使這一方向的發(fā)展逐步形成了一個(gè)新的計(jì)算機(jī)體系結(jié)構(gòu)方向。第23頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(jì)算機(jī)應(yīng)用基礎(chǔ)要開展各個(gè)領(lǐng)域的各種計(jì)算機(jī)具體應(yīng)用，就必須首先要有一些計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)。對(duì)計(jì)算科學(xué)專業(yè)的學(xué)生來(lái)說，計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)包括算法基礎(chǔ)、程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)基礎(chǔ)、微機(jī)原理與接口技術(shù)等。第24頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(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ǔ)。第25頁(yè)，共178頁(yè)，2023年，2月20日，星期四軟件基礎(chǔ)軟件是計(jì)算科學(xué)一個(gè)較大的學(xué)科門類，包括眾多的分支學(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)用軟件等。第26頁(yè)，共178頁(yè)，2023年，2月20日，星期四新一代計(jì)算機(jī)體系結(jié)構(gòu)與軟件開發(fā)方法學(xué)所謂新一代計(jì)算機(jī)體系結(jié)構(gòu)是相對(duì)于過去的體系結(jié)構(gòu)而言的。目前，對(duì)這類體系結(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)的軟件開發(fā)方法學(xué)的主要基礎(chǔ)是新一代計(jì)算機(jī)體系結(jié)構(gòu)、高等邏輯、形式語(yǔ)義學(xué)、計(jì)算模型理論以及算法基礎(chǔ)。這實(shí)際上也指出了新一代計(jì)算機(jī)體系結(jié)構(gòu)與軟件開發(fā)方法學(xué)（包括并行與分布式計(jì)算機(jī)系統(tǒng)、人工智能計(jì)算機(jī)系統(tǒng)、并行與分布式軟件開發(fā)方法學(xué)等）是計(jì)算科學(xué)界需要長(zhǎng)期努力奮斗的工作重點(diǎn)。第27頁(yè)，共178頁(yè)，2023年，2月20日，星期四

第5章計(jì)算學(xué)科的內(nèi)容

與方法5.5計(jì)算學(xué)科中的數(shù)學(xué)方法5.5.1數(shù)學(xué)的基本特征第28頁(yè)，共178頁(yè)，2023年，2月20日，星期四數(shù)學(xué)方法是指解決數(shù)學(xué)問題的策略、途徑和步驟，它是計(jì)算學(xué)科中最根本的研究方法。理論上，凡能被計(jì)算機(jī)處理的問題均可以轉(zhuǎn)換為一個(gè)數(shù)學(xué)問題，換言之，所有能被計(jì)算機(jī)處理的問題均可以用數(shù)學(xué)方法解決；反之，凡能以離散數(shù)學(xué)為代表的構(gòu)造性數(shù)學(xué)方法描述的問題，當(dāng)該問題所涉及的論域?yàn)橛懈F，或雖為無(wú)窮但存在有窮表示時(shí)，這個(gè)問題也一定能用計(jì)算機(jī)來(lái)處理。第29頁(yè)，共178頁(yè)，2023年，2月20日，星期四數(shù)學(xué)的基本特征高度的抽象性：量的關(guān)系和空間的形式邏輯的嚴(yán)密性：嚴(yán)格遵守形式邏輯的基本法則，充分保證邏輯的可靠性，才能保證結(jié)論的正確性。普遍的適用性：數(shù)學(xué)的高度抽象性決定了它的普遍適用性。第30頁(yè)，共178頁(yè)，2023年，2月20日，星期四數(shù)學(xué)方法的作用為科學(xué)技術(shù)研究提供簡(jiǎn)潔精確的形式化語(yǔ)言為科學(xué)技術(shù)研究提供數(shù)量分析和計(jì)算的方法為科學(xué)技術(shù)研究提供了邏輯推理的工具第31頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.5計(jì)算學(xué)科中的數(shù)學(xué)

方法5.5.2為什么說數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)第32頁(yè)，共178頁(yè)，2023年，2月20日，星期四為什么說數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？(1)首先，從計(jì)算模型和可計(jì)算性的研究來(lái)看，可計(jì)算函數(shù)和可計(jì)算謂詞（一種能夠能行判定其真值的斷言或邏輯公式）是等價(jià)的，相互之間可以轉(zhuǎn)化。這就是說，計(jì)算可以用函數(shù)演算來(lái)表達(dá)，也可以用邏輯系統(tǒng)來(lái)表達(dá)。作為計(jì)算模型可以計(jì)算的函數(shù)恰好與可計(jì)算謂詞是等價(jià)的，而且，數(shù)理邏輯本身的研究也廣泛使用代數(shù)方法，同時(shí)，邏輯系統(tǒng)又能通過自身的無(wú)矛盾性保證這樣一種計(jì)算模型是合理的。由此可見，作為一種數(shù)學(xué)形式系統(tǒng)，圖林機(jī)及其與它等價(jià)的計(jì)算模型的邏輯基礎(chǔ)是堅(jiān)實(shí)的。第33頁(yè)，共178頁(yè)，2023年，2月20日，星期四為什么說數(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ù)形式。第34頁(yè)，共178頁(yè)，2023年，2月20日，星期四為什么說數(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ù)和邏輯的方法。這就是說，數(shù)理邏輯和代數(shù)為語(yǔ)言學(xué)提供了方法論的基礎(chǔ)。第35頁(yè)，共178頁(yè)，2023年，2月20日，星期四為什么說數(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ù)的方法。第36頁(yè)，共178頁(yè)，2023年，2月20日，星期四為什么說數(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)一步的模型論。第37頁(yè)，共178頁(yè)，2023年，2月20日，星期四為什么說數(shù)理邏輯和代數(shù)是計(jì)算科學(xué)的主要基礎(chǔ)？⑹高等代數(shù)和一般抽象代數(shù)只解決了個(gè)體對(duì)象為簡(jiǎn)單個(gè)體的論域上的大量運(yùn)算問題，但是對(duì)具有結(jié)構(gòu)特征和屬性成分的復(fù)雜個(gè)體的論域上的運(yùn)算問題，表達(dá)和處理是不方便的，常常是有困難的。針對(duì)這類對(duì)象的運(yùn)算操作及其正確性等語(yǔ)義學(xué)問題，有必要發(fā)展泛代數(shù)和高階邏輯理論。第38頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.5計(jì)算學(xué)科中的數(shù)學(xué)

方法5.5.3計(jì)算學(xué)科中常用的數(shù)學(xué)概念和術(shù)語(yǔ)第39頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合

構(gòu)造性數(shù)學(xué)方法的基礎(chǔ)。集合就是一組無(wú)重復(fù)的對(duì)象的全體。集合中的對(duì)象稱為集合的元素。如：計(jì)算機(jī)專業(yè)學(xué)生全部必修課程可以組成一個(gè)集合，其中的每門課程就是這一集合中的元素。第40頁(yè)，共178頁(yè)，2023年，2月20日，星期四函數(shù)函數(shù)又稱映射，是指把輸入轉(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，則記作：第41頁(yè)，共178頁(yè)，2023年，2月20日，星期四關(guān)系關(guān)系是一個(gè)謂詞，其定義域?yàn)閗元組的集合。通常的關(guān)系為二元關(guān)系，其定義域?yàn)橛行驅(qū)Φ募?，在這個(gè)集合中，我們說有序?qū)Φ牡谝粋€(gè)元素和第二個(gè)元素有關(guān)系。如學(xué)生選課

學(xué)生課程成績(jī)張三文學(xué)90

張三哲學(xué)95

李四數(shù)學(xué)80

李四藝術(shù)85

王五歷史92

王五文學(xué)88第42頁(yè)，共178頁(yè)，2023年，2月20日，星期四等價(jià)關(guān)系在關(guān)系中，有一種特殊的關(guān)系，即等價(jià)關(guān)系，它滿足以下3個(gè)條件：自反性，即對(duì)集合中的每一個(gè)元素a，都有aRa；對(duì)稱性，即對(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è)互不相交的子集，稱為等價(jià)類。第43頁(yè)，共178頁(yè)，2023年，2月20日，星期四例5.7假設(shè)某人在唱歌（事件e1）的同時(shí)，還可以開車（事件e2）或者步行（事件e3），但一個(gè)人不能同時(shí)開車和步行。問：以上反映的并發(fā)現(xiàn)象，如用關(guān)系來(lái)表示時(shí)，是否是等價(jià)關(guān)系？答：以上反映的是一種并發(fā)（co）現(xiàn)象，如用關(guān)系來(lái)表示，則這種并發(fā)關(guān)系具有自反性和對(duì)稱性，即可表示為：e1co

e1，e2

co

e2，e3

co

e3；及e1co

e2（或e2co

e1），e1co

e3（或e3co

e1），不滿足傳遞性，即（e2co

e1）∧（e1co

e3）不能推出e2co

e3，即不能在開車的同時(shí)，又步行。因此，以上并發(fā)關(guān)系不是等價(jià)關(guān)系。

第44頁(yè)，共178頁(yè)，2023年，2月20日，星期四定義、定理和證明是數(shù)學(xué)的核心，也是計(jì)算學(xué)科理論形態(tài)的核心內(nèi)容。其中，定義是蘊(yùn)含在公理系統(tǒng)之中的概念和命題；定理是被證明為真的數(shù)學(xué)命題；證明是為使人們確信一個(gè)命題是真的而作的一種邏輯論證。例5.8在歐氏幾何中，平面角的定義為：平面角是在一平面內(nèi)，但不在一直線上的兩條相交線的相互傾斜度；等腰三角形的定理為：兩邊相等的三角形為等腰三角形。第45頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.5計(jì)算學(xué)科中的數(shù)學(xué)

方法5.5.3證明方法第46頁(yè)，共178頁(yè)，2023年，2月20日，星期四直接證明假定p為真，通過使用公理或已證明的定理以及正確的推理規(guī)則證明q也為真，以此證明蘊(yùn)含式p→q為真。這種證明方法為直接證明法。例5.9用直接證明法證明“若p是偶數(shù)，則p2是偶數(shù)”。證明：假定p是偶數(shù)為真，設(shè)p=2k（k為整數(shù)）。由此可得，p2=2（2k2）。因此，p2是偶數(shù)（它是一個(gè)整數(shù)的2倍）。第47頁(yè)，共178頁(yè)，2023年，2月20日，星期四間接證明因?yàn)樘N(yùn)含式p→q與其逆否命題?q→?p等價(jià)，因此可以通過證明?q→?p來(lái)證明蘊(yùn)含式p→q為真。這種證明方法為間接證明法。例5.10用間接證明法證明“若p2是偶數(shù)，則p是偶數(shù)”。證明：假定此蘊(yùn)含式后件為假，即假定p是奇數(shù)。則對(duì)某個(gè)整數(shù)k來(lái)說有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)含式為真。第48頁(yè)，共178頁(yè)，2023年，2月20日，星期四首先假定一個(gè)與原命題相反的命題成立，然后通過正確的推理得出與已知（或假設(shè)）條件、公理、已證過的定理等相互矛盾或自相矛盾的結(jié)果，以此證明原命題正確。這種證明方法就是反證法，也稱歸謬法，是一種常用的數(shù)學(xué)證明方法。例5.11證是無(wú)理數(shù)第49頁(yè)，共178頁(yè)，2023年，2月20日，星期四歸納法的定義所謂歸納法，是指從特殊推理出一般的一種證明方法。歸納法可分為不完全歸納法、完全歸納法和數(shù)學(xué)歸納法。2．不完全歸納法不完全歸納法是根據(jù)部分特殊情況作出推理的一種方法，該方法多用于無(wú)窮對(duì)象的論證，然而，論證的結(jié)果不一定正確。因此，不完全歸納法不能作為嚴(yán)格的證明方法。3．完全歸納法完全歸納法也稱窮舉法，它是對(duì)命題中存在的所有特殊情況進(jìn)行考慮的一種方法，用該方法論證的結(jié)果是正確的，然而，它只能用于“有限”對(duì)象的論證。第50頁(yè)，共178頁(yè)，2023年，2月20日，星期四數(shù)學(xué)歸納法的形式化定義根據(jù)數(shù)學(xué)歸納法的原理，可以對(duì)數(shù)學(xué)歸納法形式化地定義為：

P(1)∧()(P(n)→P(n+1))→P(n)例5.12求證命題P(n)：“從1開始連續(xù)n個(gè)奇數(shù)之和是n的平方”，即公式

1+3+5+…+（2n―1）=n2成立。第51頁(yè)，共178頁(yè)，2023年，2月20日，星期四證明

歸納基礎(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é)歸納法，該命題得證。第52頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(gòu)造性證明構(gòu)造性證明——通過找出一個(gè)使得命題P(a)為真的元素a，從而完成該函數(shù)值的存在性證明稱為構(gòu)造性證明。構(gòu)造性證明方法是計(jì)算科學(xué)中廣泛使用的一種證明方法，本章Armstrong公理系統(tǒng)的完備性證明就采用了構(gòu)造性的證明方法。

第53頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.5計(jì)算學(xué)科中的數(shù)學(xué)

方法5.5.5遞歸和迭代(構(gòu)造性方法)第54頁(yè)，共178頁(yè)，2023年，2月20日，星期四遞歸及其有關(guān)概念很多序列項(xiàng)常?？梢砸赃@樣的方式得到：由an–1得到an，按這樣的法則，可以從一個(gè)已知的首項(xiàng)開始，有限次地重復(fù)做下去，最后產(chǎn)生一個(gè)序列，該序列是實(shí)現(xiàn)遞歸和迭代的基礎(chǔ)。

20世紀(jì)30年代，正是可計(jì)算的遞歸函數(shù)理論與圖靈機(jī)、λ演算和POST規(guī)范系統(tǒng)等理論一起為計(jì)算理論的建立奠定了基礎(chǔ)。第55頁(yè)，共178頁(yè)，2023年，2月20日，星期四遞歸及其有關(guān)概念遞歸關(guān)系指的是：一個(gè)數(shù)列的若干連續(xù)項(xiàng)之間的關(guān)系遞歸數(shù)列指的是：由遞歸關(guān)系所確定的數(shù)列。遞歸過程指的是：調(diào)用自身的過程。遞歸算法指的是：包含遞歸過程的算法。遞歸程序指的是：直接或間接調(diào)用自身的程序。遞歸方法（也稱遞推法），是一種在“有限”步驟內(nèi)，根據(jù)特定的法則或公式對(duì)一個(gè)或多個(gè)前面的元素進(jìn)行運(yùn)算，以確定一系列元素（如數(shù)或函數(shù)）的方法。第56頁(yè)，共178頁(yè)，2023年，2月20日，星期四遞歸與數(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開始計(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ù)列。

第57頁(yè)，共178頁(yè)，2023年，2月20日，星期四遞歸由遞歸基礎(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)容。第58頁(yè)，共178頁(yè)，2023年，2月20日，星期四遞歸的定義功能例：序列：2，5，11，23，…，an=2an–1+1，…，請(qǐng)給出其遞歸定義。解該序列的遞歸定義如下：

a1=2； 遞歸基礎(chǔ)

an=2an–1+1，n=2，3，4，…； 遞歸步驟例5.15給出階乘F(n)=n!的遞歸定義解階乘F(n)=n!的遞歸定義如下：

F(0)=1； 遞歸基礎(chǔ)F(n)=n×F(n–1)，n=1，2，3，…； 遞歸步驟第59頁(yè)，共178頁(yè)，2023年，2月20日，星期四阿克曼函數(shù)該函數(shù)是由希爾伯特的學(xué)生、德國(guó)著名數(shù)學(xué)家威爾海姆·阿克曼于1928年發(fā)現(xiàn)的。這是一個(gè)圖靈機(jī)可計(jì)算的，但不是原始遞歸的函數(shù)。下面，我們介紹這個(gè)經(jīng)典的遞歸函數(shù)，并給出相應(yīng)的計(jì)算過程。阿克曼函數(shù)：第60頁(yè)，共178頁(yè)，2023年，2月20日，星期四解阿克曼函數(shù)的遞歸算法:Beginifm=0thenn+1elseifn=0thenA(m-1,1)elseA(m-1,A(m,n-1))End第61頁(yè)，共178頁(yè)，2023年，2月20日，星期四計(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第62頁(yè)，共178頁(yè)，2023年，2月20日，星期四迭代迭代與遞歸有著密切的聯(lián)系，甚至，一類如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à)的迭代程序。

第63頁(yè)，共178頁(yè)，2023年，2月20日，星期四斐波那契數(shù)的求解算法而言，可以使用迭代方法或遞歸方法來(lái)解決。一些遞歸算法，如求解梵天塔問題的算法就不能用迭代方法，而只能用遞歸方法。第64頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.5計(jì)算學(xué)科中的數(shù)學(xué)

方法5.5.6公理化方法第65頁(yè)，共178頁(yè)，2023年，2月20日，星期四理論體系從數(shù)學(xué)的角度來(lái)說，理論是基本概念、基本原理或定律（聯(lián)系這些概念的判斷）以及由這些概念與原理邏輯推理出來(lái)的結(jié)論組成的集合，該概念可以形式化的定義為：

T=<C,P,S>，其中：（1）表示理論；（2）表示基本概念的集合；（3）表示基本原理或定律的集合；（4）表示由這些概念與原理邏輯推理出來(lái)的結(jié)論組成的集合。第66頁(yè)，共178頁(yè)，2023年，2月20日，星期四構(gòu)建理論體系的常用方法每一個(gè)理論都由一組特定的概念和一組特定的命題組成。在一個(gè)理論中，基本概念（原始概念）和基本命題（原始命題）必須是明確的，否則就會(huì)出現(xiàn)“循環(huán)定義”和“循環(huán)論證”的嚴(yán)重問題。構(gòu)建一個(gè)理論體系必須采用科學(xué)的方法。公理化方法邏輯和歷史相統(tǒng)一的方法從抽象上升到具體的方法。第67頁(yè)，共178頁(yè)，2023年，2月20日，星期四公理化方法公理化方法是一種構(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)。第68頁(yè)，共178頁(yè)，2023年，2月20日，星期四公理化方法近年來(lái)，這一方法出現(xiàn)在一些學(xué)科的前沿研究中。除了形式語(yǔ)義學(xué)的研究中使用公理化方法外，開放信息系統(tǒng)的思想和設(shè)計(jì)，自定義邏輯框架系統(tǒng)的研究，以及分布式代數(shù)系統(tǒng)的研究都采用了公理化方法或吸取了公理化方法的思想。隨著學(xué)科發(fā)展的深化，預(yù)計(jì)這一方法還將在一些分支方向上得到運(yùn)用，并推動(dòng)學(xué)科進(jìn)一步深入發(fā)展。

第69頁(yè)，共178頁(yè)，2023年，2月20日，星期四公理系統(tǒng)的3個(gè)條件用公理化構(gòu)建的理論體系稱為公理系統(tǒng)，該公理系統(tǒng)需要滿足無(wú)矛盾性、獨(dú)立性和完備性的條件。（1）無(wú)矛盾性。（2）獨(dú)立性。（3）完備性。第70頁(yè)，共178頁(yè)，2023年，2月20日，星期四簡(jiǎn)單化是科學(xué)研究追求的目標(biāo)之一。一般而言，正確的一定是簡(jiǎn)單的（注意，這句話是單向的，反之不一定成立）。關(guān)于公理系統(tǒng)的完備性要求，自哥德爾發(fā)表關(guān)于形式系統(tǒng)的“不完備性定理”的論文后，數(shù)學(xué)家們對(duì)公理系統(tǒng)的完備性要求大大放寬了。也就是說，能完備更好，即使不完備，同樣也具有重要的價(jià)值。第71頁(yè)，共178頁(yè)，2023年，2月20日，星期四公理化方法在計(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)域第72頁(yè)，共178頁(yè)，2023年，2月20日，星期四例5.18正整數(shù)的公理化概括原始概念：1；原始命題（公理）：任何正整數(shù)n或者等于1，或者可以從1開始，重復(fù)地“加1”來(lái)得到它。

第73頁(yè)，共178頁(yè)，2023年，2月20日，星期四例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：以任意中心和直徑可以畫圓；公設(shè)4：凡直角都彼此相等；公設(shè)5：在平面上，過給定直線之外的一點(diǎn)，存在且僅存在一條平行線，即所謂的“平行公設(shè)（公理）”。第74頁(yè)，共178頁(yè)，2023年，2月20日，星期四例5.20中國(guó)古代唯一的一次公理化嘗試：周髀算經(jīng)據(jù)有關(guān)記載，《周髀算經(jīng)》成書于公元前100年左右。在《周髀算經(jīng)》中，介紹了一個(gè)描述天象的蓋天學(xué)說，該學(xué)說構(gòu)建了一個(gè)幾何宇宙模型。該學(xué)說中的公理有兩個(gè)：一個(gè)是“天地為平行平面，天地相距80,000里，在北極下方的大地中央有一底面直徑為23,000里，高為60,000里的上尖下粗的“璇璣”（即極下，極下陽(yáng)光照不到，故不生萬(wàn)物）；另一個(gè)是關(guān)于太陽(yáng)光照以及人目所見的極限范圍，即“日照四旁各十六萬(wàn)七千里；人所望見，遠(yuǎn)近宜如日光所照”，其大意為，日光向四周照射的極限距離是167,000里，人所見到也是這個(gè)距離。換言之，日光照不到167,000里之外，人也看不見167,000里之外。第75頁(yè)，共178頁(yè)，2023年，2月20日，星期四從公理可以演繹出：夏至南萬(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è)天、地為圓形平行平面的宇宙模型。第76頁(yè)，共178頁(yè)，2023年，2月20日，星期四今天，我們知道，這個(gè)宇宙模型的描述與實(shí)際的天象吻合得并不好，與同時(shí)代古希臘類似模型相比，也存在較大的差距，而當(dāng)時(shí)，我國(guó)天文學(xué)家完全可以用代數(shù)方法相當(dāng)精確地解決一些天文學(xué)問題，至于宇宙究竟是什么形狀或結(jié)構(gòu)，完全可以不去過問。然而，《周髀算經(jīng)》是個(gè)例外，并成為我國(guó)古代學(xué)者惟一的一次公理化方法的嘗試，這種思想，是受外來(lái)因素的影響，還是我國(guó)本土科學(xué)中某種隨機(jī)出現(xiàn)的變異？已引起科學(xué)史領(lǐng)域?qū)＜业臉O大興趣。第77頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.6計(jì)算學(xué)科中的數(shù)學(xué)

方法5.6.7形式化方法第78頁(yè)，共178頁(yè)，2023年，2月20日，星期四具體公理系統(tǒng)和抽象公理系統(tǒng)在歐氏幾何公理系統(tǒng)中，原始概念（點(diǎn)、線、面）和所有的公理都有直觀的背景或客觀的意義，像這樣有現(xiàn)實(shí)世界背景的公理系統(tǒng)，一般被稱為具體公理系統(tǒng)。由于非歐幾何的出現(xiàn)，使人們感到具體公理系統(tǒng)過于受直覺的局限。因而，在19世紀(jì)末和20世紀(jì)初，一些杰出的數(shù)學(xué)家和邏輯學(xué)家開始了對(duì)抽象公理系統(tǒng)的研究。第79頁(yè)，共178頁(yè)，2023年，2月20日，星期四在抽象公理系統(tǒng)中，原始概念的直覺意義被忽視，甚至沒有任何預(yù)先設(shè)定的意義，而公理也無(wú)需以任何實(shí)際意義為背景，它們無(wú)非是一些形式約定的符號(hào)串。這時(shí)，抽象公理系統(tǒng)可以有多種解釋。形式化的運(yùn)算規(guī)則1+1可以解釋為一個(gè)蘋果加一個(gè)蘋果，或者為一本書加一本書；布爾代數(shù)抽象公理系統(tǒng)可以解釋為有關(guān)命題真值的命題代數(shù)，或者有關(guān)電路設(shè)計(jì)研究的開關(guān)代數(shù)。第80頁(yè)，共178頁(yè)，2023年，2月20日，星期四形式系統(tǒng)的組成部分初始符號(hào)。初始符號(hào)不具有任何意義。形式規(guī)則。形式規(guī)則規(guī)定一種程序，借以判定哪些符號(hào)串是本系統(tǒng)中的公式，哪些不是。公理。即在本系統(tǒng)的公式中，確定不加推導(dǎo)就可以斷定的公式集。變形規(guī)則。變形規(guī)則亦稱演繹規(guī)則或推導(dǎo)規(guī)則。變形規(guī)則規(guī)定，從已被斷定的公式，如何得出新的被斷定公式。被斷定的公式又稱為系統(tǒng)中的定理。第81頁(yè)，共178頁(yè)，2023年，2月20日，星期四形式系統(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)的專利，抽象是人們認(rèn)識(shí)客觀世界的基本方法，只不過形式系統(tǒng)具有更強(qiáng)的抽象性。形式系統(tǒng)的抽象性表現(xiàn)在它自身僅僅是一個(gè)符號(hào)系統(tǒng)，除了表示符號(hào)間的關(guān)系（字符號(hào)串的變換）外，不表示任何別的意義。第82頁(yè)，共178頁(yè)，2023年，2月20日，星期四形式系統(tǒng)的局限性不完備性1931年，哥德爾提出的關(guān)于形式系統(tǒng)的“不完備性定理”指出：如果一個(gè)形式的數(shù)學(xué)理論是足夠復(fù)雜的（復(fù)雜到所有的遞歸函數(shù)在其中都能夠表示），而且它是無(wú)矛盾的，那么在這一理論中存在一個(gè)語(yǔ)句，而這一語(yǔ)句在這一理論中是既不能證明，也不能否證的。第83頁(yè)，共178頁(yè)，2023年，2月20日，星期四形式系統(tǒng)的局限性不可判定性如果對(duì)一類語(yǔ)句C而言，存在一個(gè)算法AL，使得對(duì)C中的任一語(yǔ)句S而言，可以利用算法AL來(lái)判定其是否成立，則C稱為可判定的，否則，稱為不可判定的。著名的“停機(jī)問題”就是一個(gè)不可判定性的問題。該問題是指，一個(gè)任給的圖靈機(jī)對(duì)于一個(gè)任給的輸入而言是否停機(jī)的問題。圖靈證明這類問題是不可判定的。需要指出的是：計(jì)算機(jī)系統(tǒng)就是一種形式系統(tǒng)，因此，計(jì)算機(jī)系統(tǒng)一樣也具有形式系統(tǒng)的局限性。第84頁(yè)，共178頁(yè)，2023年，2月20日，星期四形式化與公理化形式化不一定導(dǎo)致公理化，公理系統(tǒng)也不一定是形式系統(tǒng)。如歐氏幾何公理系統(tǒng)就不是形式系統(tǒng)。形式化與公理化雖然不同，但在近代數(shù)學(xué)中，形式系統(tǒng)大都是形式化的公理系統(tǒng)。第85頁(yè)，共178頁(yè)，2023年，2月20日，星期四

第5章計(jì)算學(xué)科的內(nèi)容

與方法5.5布爾代數(shù)基礎(chǔ)第86頁(yè)，共178頁(yè)，2023年，2月20日，星期四

邏輯與代數(shù)是計(jì)算機(jī)科學(xué)最重要的基礎(chǔ)，布爾代數(shù)是數(shù)理邏輯早期的雛形，是一種用代數(shù)演算的方法來(lái)研究思維結(jié)構(gòu)的邏輯系統(tǒng)。問題：什么是邏輯呢？

對(duì)邏輯來(lái)說不存在清規(guī)戒律，每個(gè)人都可以構(gòu)造自己的邏輯，即他自己的語(yǔ)言形式，只要他愿意。對(duì)他的唯一要求是：如果他想討論這種邏輯，那么他必須說清楚他的方法，并給出語(yǔ)法規(guī)則，而不是給出哲學(xué)論據(jù)。

Carnap（卡爾納普）第87頁(yè)，共178頁(yè)，2023年，2月20日，星期四

5.5布爾代數(shù)基礎(chǔ)5.5.1集合的基本概念與基本運(yùn)算第88頁(yè)，共178頁(yè)，2023年，2月20日，星期四概念由事物或?qū)ο蠼M成的集體，無(wú)論它們是由其成員通過枚舉方式直接表示出來(lái)的，還是由其成員所具有的某些本質(zhì)屬性表示出來(lái)的，都稱為集合。稱兩個(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)格的直觀上的定義。第89頁(yè)，共178頁(yè)，2023年，2月20日，星期四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，n≥0}

第90頁(yè)，共178頁(yè)，2023年，2月20日，星期四3.從屬與包含關(guān)系通常用大寫英文字母作為集合的名稱。若某事物a是集合A的一個(gè)元素，則記為：

a∈A并說“a屬于A”，或者說“a在A中”。若a不是集合A的元素，則記為：

aA當(dāng)以枚舉形式表示一個(gè)集合時(shí)，我們用一個(gè)大括號(hào)把這些枚舉的元素括起來(lái)以表示這個(gè)集合。第91頁(yè)，共178頁(yè)，2023年，2月20日，星期四3.從屬與包含關(guān)系例1{麻雀，黃鸝，杜鵑，白鷺，紅嘴鷗}是一個(gè)由五種鳥組成的集合；如果{a,b,c,d,…,x,y,z}是由英語(yǔ)的26個(gè)小寫字母組成的集合。例2A＝{x│ax2+bx+c＝0且a,b,c∈R}，R是實(shí)數(shù)集。例3B＝{a,b,aa,ab,bb,aaa,aab,abb,bbb,aaaa,…}這種帶省略的表示形式實(shí)際上可表示一些集合元素有某種出現(xiàn)規(guī)律的無(wú)窮集合。第92頁(yè)，共178頁(yè)，2023年，2月20日，星期四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è)的全集合。第93頁(yè)，共178頁(yè)，2023年，2月20日，星期四3.從屬與包含關(guān)系考慮兩個(gè)集合A和B。若集合A的每一個(gè)元素也是集合B的一個(gè)元素，則稱集合B包含集合A，也稱集合A包含在集合B中，記為AB若AB，則稱A是B的子集合，B是A的母集合。顯然，對(duì)任何集合A，有AA。若集合A、B之間存在AB且A≠B，則稱A是B的真子集合，記為AB。若AB，又有BA，則可以得出結(jié)論A＝B。這是因?yàn)锳的元素都是B的元素，而B的元素也是A的元素，說明A，B中擁有相同的元素，所以A和B相同，故相等。顯然，對(duì)任何集合A，A1。特別地，1。第94頁(yè)，共178頁(yè)，2023年，2月20日，星期四3.從屬與包含關(guān)系通常用大寫英文字母作為集合的名稱。若某事物a是集合A的一個(gè)元素，則記為：

a∈A并說“a屬于A”，或者說“a在A中”。若a不是集合A的元素，則記為：

aA當(dāng)以枚舉形式表示一個(gè)集合時(shí)，我們用一個(gè)大括號(hào)把這些枚舉的元素括起來(lái)以表示這個(gè)集合。例1{麻雀，黃鸝，杜鵑，白鷺，紅嘴鷗}是一個(gè)由五種鳥組成的集合；第95頁(yè)，共178頁(yè)，2023年，2月20日，星期四4.集合的基本運(yùn)算集合的并設(shè)A、B為兩個(gè)任意集合，將集合A的元素和集合B的元素合并在一起，組成一個(gè)新的集合C，稱為集合A和集合B的并集，簡(jiǎn)稱A和B的并?？杀硎緸椋?/p>

C＝A∪B＝｛x｜x∈A∨x∈B求并集的運(yùn)算稱為并（運(yùn)算）。例5.1若A={a，b，c，d}，B={b，d，e}，求集合A和B的并。解：A∪B＝｛a，b，c，d，e｝第96頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合的交設(shè)A、B為兩個(gè)任意集合，定義A和B的公共元素構(gòu)成的集合C為A和B的交集，簡(jiǎn)稱A和B的交，記為:C＝A∩B＝｛x｜x∈A∧x∈B｝例5.3若A={x|x>-5}，B={x|x<1}，求集合和B的交。解：A∩B＝｛x｜x>﹣5｝∩｛x｜x<1｝＝｛x｜–5<x<1｝第97頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合的差設(shè)A、B為兩個(gè)任意集合，所有屬于A而不屬于B的一切元素構(gòu)成的集合S，稱為A和B的差集。可表示為：

S=A－B=｛x｜x∈A∨x∈B｝。求差集的運(yùn)算稱為差（運(yùn)算）。例5.2若A={a，b，c，d}，B={b，d，e}，求集合A和B的差。解：A－B={a，c}第98頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合的補(bǔ)設(shè)I為全集，A為I的任意一子集，I–A則為A的補(bǔ)集，記為A’?？杀硎緸?/p>

A’=I–A=｛x｜x∈I，｝求補(bǔ)集的運(yùn)算稱為補(bǔ)（運(yùn)算）求補(bǔ)集的運(yùn)算稱為補(bǔ)（運(yùn)算）例5.4若I=｛x｜–5﹤x﹤5｝，A=｛x｜0﹤x﹤1｝，求。解：A’=I–A=｛x｜–5﹤x﹤0∨1﹤x﹤5｝第99頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合的乘積集合A1，A2，…，An的乘積一般用法國(guó)數(shù)學(xué)家笛卡爾（ReneDescartes）的名字命名，即笛卡爾積。該乘積表示如下：A1×A2×…An={（a1，a2，…，an）｜ai∈Ai，i＝1，2，…，n}A1×A2×…An的結(jié)果是一個(gè)有序元組的集合。例5.5若A={1，2，3}，B={a，b}，求A×B。解：A×B={（1，a），（1，b），（2，a），（2，b），（3，a），（3，b）}第100頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合運(yùn)算的定理定理1

設(shè)A為一個(gè)集合，B為A的補(bǔ)集合，I為全集，則

(1)A∩B＝，

(2)A∪B＝I，

(3)’＝I，

(4)I’＝，

(5)(A’)’＝A，

(6)(I’)’＝I，

(7)(’)’＝。我們選擇證明其中的(1)，其余的證明留給讀者作為練習(xí)。第101頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合運(yùn)算的定理證明

(1)用反證法。設(shè)A∩B≠，則必存在非空元素x∈A∩B，故x∈A且x∈B，此與B為A的補(bǔ)集合矛盾。所以，

A∩B＝?！?/p>

例4

設(shè)A＝{a,b,c,d}，B＝{c,d,e,f}，C＝{e,f,g,h}，則A∩B＝{c,d}，

A∪B＝{a,b,c,d,e,f}，

A∩C＝，

A∪C＝{a,b,c,d,e,f,g,h}。第102頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合運(yùn)算的定理根據(jù)定義，不難證明定理2。定理2

對(duì)任意集合A和集合B，有

(1)A∩B＝B∩A，（交換律）

(2)A∪B＝B∪A，（交換律）

(3)A∩A＝A，

(4)A∪A＝A，（冪等律）

(5)A∩A’＝，

(6)A∪A’＝1，

(7)A∩＝，

(8)A∪＝A。第103頁(yè)，共178頁(yè)，2023年，2月20日，星期四集合運(yùn)算的定理我們選擇證明其中的(2)，其余的(1)、(3)-(8)大家可以自己試著去證明。證明

(2)我們分兩部分來(lái)證明。首先證明左邊的集合是右邊集合的子集合，然后再證明右邊的集合是左邊集合的子集合。這樣，若兩個(gè)集合互為子集合時(shí)，必然相等。①設(shè)任意元素x∈A∪B，則x∈A或者x∈B，也可表述為x∈B或者x∈A，故A∪BB∪A；②同理可證，B∪AA∪B。所以，A∪B＝B∪A?！醵ɡ?(2)的上述證明方法是證明兩個(gè)集合相等時(shí)最常用的方法，也是最基本的方法。第104頁(yè)，共178頁(yè)，2023年，2月20日，星期四5.集合上的一些基本關(guān)系下面我們?cè)诩舷嘌a(bǔ)、包含、交與并的基礎(chǔ)上，首先來(lái)建立一些基本關(guān)系。定理3

設(shè)A，B為任意集合，則

(1)A∩BA，

(2)A∩BB，

(3)AA∪B，

(4)BA∪B。我們選擇證明其中的(1)，其余的(2)-(4)大家可以自己試著去證明。證明

(1)設(shè)任意元素x∈A∩B，由交的定義知，x∈A，故A∩BA?！醯?05頁(yè)，共178頁(yè)，2023年，2月20日，星期四5.集合上的一些基本關(guān)系定理4

設(shè)A、B為任意集合，則

(1)AB，當(dāng)且僅當(dāng)A∩B＝A，

(2)A∩B＝A，當(dāng)且僅當(dāng)A∪B＝B，

(3)A∪B＝B，當(dāng)且僅當(dāng)AB。這個(gè)定理說明了一個(gè)循環(huán)等價(jià)關(guān)系。象這樣的等價(jià)關(guān)系，今后可用來(lái)作等價(jià)的概念定義。證明

(1)我們分兩部分來(lái)證明定理的充分性。①設(shè)任意元素x∈A∩B，故x∈A且x∈B，可得A∩BA；②又設(shè)任意元素x∈A，由AB知x∈B，故x∈A∩B，可得AA∩B。綜合①、②，知A∩B＝A。由A∩B＝A導(dǎo)出AB是顯然的。□第106頁(yè)，共178頁(yè)，2023年，2月20日，星期四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)化的證明方式。第107頁(yè)，共178頁(yè)，2023年，2月20日，星期四5.集合上的一些基本關(guān)系定理5（DeMorgan律）設(shè)A、B為任意集合，則

(1)(A∩B)’＝A’∪B’，

(2)(A∪B)’＝A’∩B’。

證明我們只要證明其中的一個(gè)就可以了，因?yàn)檫@兩個(gè)式子中的任何一個(gè)是另一個(gè)在相補(bǔ)關(guān)系下的直接結(jié)果。下面，我們證明(1)。設(shè)任意元素x∈(A∩B)’，則x(A∩B)，因此xA或xB。換言之x∈A’或x∈B’，故x∈A’∪B’。所以，

(A∩B)’A’∪B’；反之，設(shè)任意元素x∈A’∪B’，則x∈A’或x∈B’。換言之xA或xB，因此x(A∩B)，故x∈(A∩B)’。所以:A’∪B’(A∩B)’從而，可知(A∩B)’＝A’∪B’。□第108頁(yè)，共178頁(yè)，2023年，2月20日，星期四5.集合上的一些基本關(guān)系定理6

對(duì)任意的集合A，A。

證明使用反證法。假設(shè)定理不成立，即存在集合A，使得A不成立。這就是說，存在元素x∈,但xA，這與是空集合相矛盾。故定理成立，空集合是一切集合的子集合?！醵ɡ?

空集合是唯一的。證明設(shè)1和2都是空集合，由定理6知:

11且21，所以1＝2?！醯?09頁(yè)，共178頁(yè)，2023年，2月20日，星期四6.集合上的一些運(yùn)算定律定理8

設(shè)A、B、C是任意的集合，則

(1)A∪(B∪C)＝(A∪B)∪C，（結(jié)合律）

(2)A∩(B∩C)＝(A∩B)∩C，（結(jié)合律）

(3)A∪(B∩C)＝(A∪B)∩(A∪C)，（分配律）

(4)A∩(B∪C)＝(A∩B)∪(A∩C)。（分配律）

證明

(3)設(shè)x∈A∪(B∩C)，則x∈A或x∈B∩C。若是前一種情況，那么x∈A∪B且x∈A∪C，因而x∈(A∪B)∩(A∪C)；若是后一種情況，那么x∈B且x∈C，因此x∈A∪B且x∈A∪C，也有:x∈(A∪B)∩(A∪C)。這就證明了:A∪(B∩C)(A∪B)∩(A∪C)；第110頁(yè)，共178頁(yè)，2023年，2月20日，星期四6.集合上的一些運(yùn)算定律

反之，設(shè)x∈(A∪B)∩(A∪C)，則x∈A∪B且x∈A∪C。若x∈A，那么x∈A∪(B∩C)；若xA，那么必有x∈B且x∈C，因此x∈B∩C，也有x∈A∪(B∩C)。這就證明了:(A∪B)∩(A∪C)A∪(B∩C)；所以，A∪(B∩C)＝(A∪B)∩(A∪C)?！醯?11頁(yè)，共178頁(yè)，2023年，2月20日，星期四7.集合上的其它一些關(guān)系利用集合上的基本關(guān)系和基本運(yùn)算，可以導(dǎo)出集合上的其它一些關(guān)系。定理9

設(shè)A、B、C是任意的集合，那么下列關(guān)系成立：

(1)若AB且AC，則AB∩C；

(2)若AC且BC，則A∪BC。定理10

設(shè)A、B、C是任意的集合，若AB，則

(1)A∩CB∩C，

(2)A∪CB∪C。由定理3和定理10易證定理11。第112頁(yè)，共178頁(yè)，2023年，2月20日，星期四7.集合上的其它一些關(guān)系定理11

設(shè)A，B是任意的集合，則有A∩(A∪B)＝A。證明依定理3有A∩(A∪B)A。又A＝A∩A，AA∪B，因此，由定理10知A∩AA∩(A∪B)，故AA∩(A∪B)。所以，A∩(A∪B)＝A?！?/p>

定理12

設(shè)A、B是任意的集合，則AB，當(dāng)且僅當(dāng)A∩B'＝。

定理13

設(shè)A是一個(gè)集合，那么下列等式成立：

(1)若對(duì)任意的集合B，都有AB，則A＝；

(2)若對(duì)任意的集合B，都有BA，則A＝1。證明

(1)由題設(shè)，特別當(dāng)B＝時(shí)，有A，但A，所以A＝?！醵ɡ?4

設(shè)A、B是兩個(gè)集合，那么下列等式成立：

(1)若A∪B＝，則A＝且B＝；

(2)若A∩B＝1，則A＝1且B＝1。

證明

(1)因AA∪B＝，故A＝；同理可證，B＝?！醯?13頁(yè)，共178頁(yè)，2023年，2月20日，星期四8.集合的差與對(duì)稱差(中學(xué)已經(jīng)學(xué)習(xí))定義1

集合A，B的差A(yù)－B定義為一切屬于A但不屬于B的元素構(gòu)成的集合，即A－B＝A∩B’。對(duì)任意集合A，B，不難證明定理15。

定理15

設(shè)A，B，C都是集合，那么下列等式成立：

(1)1－A＝A’；

(2)A－B＝，當(dāng)且僅當(dāng)AB；

(3)(A－B)∪B＝A∪B；

(4)C∩(A－B)＝(C∩A)－(C∩B)。（分配律）交關(guān)于差是可分配的。但是，并關(guān)于差卻不是可分配的。大家可以通過思考和舉一反例來(lái)認(rèn)識(shí)這一點(diǎn)第114頁(yè)，共178頁(yè)，2023年，2月20日，星期四8.集合的差與對(duì)稱差定義2

集合A，B的對(duì)稱差A(yù)B定義為A與B之差和B與A之差的并，即AB＝(A－B)∪(B－A)。顯然，A與B的對(duì)稱差也可以寫成如下的定義形式：

AB＝(A∩B’)∪(B∩A’)。由定義2，我們還可以得到對(duì)稱差的其它幾種表示形式或等價(jià)定義。定理16

若A，B是兩個(gè)集合，則

(1)AB＝(A∪B)∩(A’∪B’)，

(2)AB＝(A∪B)－(A∩B)，

(3)AB＝A’B’。作為一種運(yùn)算，對(duì)稱差滿足一些定律。第115頁(yè)，共178頁(yè)，2023年，2月20日，星期四8.集合的差與對(duì)稱差定理17

設(shè)A，B，C都是集合，那么下列等式成立：

(1)AB＝BA；（交換律）

(2)(AB)C＝A(BC)；（結(jié)合律）

(3)A∩(BC)＝(A∩B)(A∩C)；（分配律）

(4)A∪(BC)≠(A∪B)(A∪C)。（并關(guān)于對(duì)稱差不滿足分配律）證明

(3)A∩(BC)＝A∩((B－C)∪(C－B))

＝(A∩(B－C))∪(A∩(C－B))

＝(A∩B)－(A∩C))∪(A∩C)－(A∩B))

＝(A∩B)(A∩C)。□第116頁(yè)，共178頁(yè)，2023年，2月20日，星期四8.集合的差與對(duì)稱差定理18

設(shè)A，B是兩個(gè)集合，那么下列等式成立：

(1)AA＝，

(2)若AB＝φ，則A＝B。定義3

設(shè)A，B為集合，AB的補(bǔ)定義為A與B的叉，記為A×B，即

A×B＝(A∩B)∪(A’∩B’)。類似于對(duì)稱差的性質(zhì)，易證定理19。定理19

設(shè)A，B，C都是集合，那么下列等式成立：

(1)A×B＝A’×B’，

(2)A×B＝B×A，（交換律）

(3)(A×B)×C＝A×(B×C)，（結(jié)合律）

(4)A×A＝1，

(5)A×B＝A’B＝AB’，

(6)A×B’＝A’×B＝AB。第117頁(yè)，共178