第一講 引言
一、課程內容
·數理邏輯：是計算機科學的基礎，應熟練掌握將現實生活中的條件化成邏輯公式，並能做適當的推理，這對程序設計等課程是極有用處的。
·集合論：數學的基礎，對於學習程序設計、數據結構、編譯原理等幾乎所有計算機專業課程和數學課程都很有用處。熟練掌握有關集合、函數、關係等基本概念。
·代數結構：對於抽象數據類型、形式語義的研究很有用處。培養數學思維，將以前學過的知識系統化、形式化和抽象化。熟練掌握有關代數系統的基本概念，以及群、環、域等代數結構的基本知識。
·圖論：對於解決許多實際問題很有用處，對於學習數據結構、編譯原理課程也很有幫助。要求掌握有關圖、樹的基本概念，以及如何將圖論用於實際問題的解決，並培養其使用數學工具建立模型的思維方式。
·講課時間為兩個學期，第一學期講授數理邏輯與集合論，第二學期講授代數結構和圖論。考試內容限於書中的內容和難度，但講課內容不限於書中的內容和難度。
二、數理邏輯發展史
1.目的
·了解有關的背景，加深對計算機學科的全面了解，特別是理論方面的了解，而不限於將計算機看成是一門技術或工程性的學科。
·通過重要的歷史事件，了解計算機科學中的一些基本思維方式和一些基本問題。
2.數理邏輯的發展前期
·前史時期——古典形式邏輯時期：亞裡斯多德的直言三段論理論
·初創時期——邏輯代數時期（17世紀末）
·資本主義生產力大發展，自然科學取得了長足的進步，數學在認識自然、發展技術方面起到了相當重要的作用。
·人們希望使用數學的方法來研究思維，把思維過程轉換為數學的計算。
·萊布尼茲(Leibniz, 1646~1716)完善三段論，提出了建立數理邏輯或者說理性演算的思想：
·提出將推理的正確性化歸於計算，這種演算能使人們的推理不依賴於對推理過程中的命題的含義內容的思考，將推理的規則變為演算的規則。
·使用一種符號語言來代替自然語言對演算進行描述，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規律，而與其含義無關。
·布爾(G. Boole, 1815~1864)代數：將有關數學運算的研究的代數系統推廣到邏輯領域，布爾代數既是一種代數系統，也是一種邏輯演算。
3.數理邏輯的奠基時期
·弗雷格(G. Frege, 1848~1925)：《概念語言——一種按算術的公式語言構成的純思維公式語言》(1879)的出版標誌著數理邏輯的基礎部分——命題演算和謂詞演算的正式建立。
·皮亞諾(Giuseppe Peano, 1858~1932)：《用一種新的方法陳述的算術原理》(1889)提出了自然數算術的一個公理系統。
·羅素(Bertrand Russell, 1872~1970)：《數學原理》(與懷特黑合著，1910, 1912, 1913)從命題演算和謂詞演算開始，然後通過一元和二元命題函項定義了類和關係的概念，建立了抽象的類演算和關係演算。由此出發，在類型論的基礎上用連續定義和證明的方式引出了數學（主要是算術）中的主要概念和定理。
·邏輯演算的發展：甘岑(G. Gentzen)的自然推理系統(Natural Deduction System)，邏輯演算的元理論：公理的獨立性、一致性、完全性等。
·各種各樣的非經典邏輯的發展：路易斯(Lewis, 1883~1964)的模態邏輯，實質蘊涵怪論和嚴格蘊涵、相干邏輯等，盧卡西維茨的多值邏輯等。
4.集合論的發展
·看待無窮集合的兩種觀點：實無窮與潛無窮
·康託爾(G. Cantor, 1845~1918)：以實無窮的思想為指導，建立了樸素集合論
·外延原則（集合由它的元素決定）和概括原則（每一性質產生一集合）。
·可數集和不可數集，確定無窮集合的本質在於集合本身能與其子集一一對應。能與正整數集合對應的集合是可數的，否則是不可數的。證明了有理數集是可數的，使用對角線法證明了實數集合是不可數的。
·超窮基數和超窮序數
·樸素集合論的悖論：羅素悖論
·公理集合論的建立：ZFC系統
6.第三次數學危機與邏輯主義、直覺主義與形式主義
·集合論的悖論使得人們覺得數學產生了第三次危機，提出了數學的基礎到底是什麼這樣的問題。
·羅素等的邏輯主義：數學的基礎是邏輯，倡導一切數學可從邏輯符號推出，《數學原理》一書是他們這一思想的體現。為解決悖論產生了邏輯類型論。
·布勞維爾(Brouwer, 1881~1966)的直覺主義：數學是心靈的構造，只承認可構造的數學，強調構造的能行性，與計算機科學有重要的聯繫。堅持潛無窮，強調排中律不能用於無窮集合。海丁(Heyting)的直覺主義邏輯。
·希爾伯特(D. Hilbert)的形式主義：公理化方法與形式化方法，元數學和證明論，提倡將邏輯演算和數學證明本身形式化，把用普通的語言傳達的內容上的數學科學變為用數學符號和邏輯符號按一定法則排列的一堆公式。為了消除悖論，要數學建立在公理化基礎上，將各門數學形式化，構成形式系統，並證明其一致性，這是希爾伯特的數學綱領。
7.數理邏輯的發展初期
·哥德爾(Godel, 1906~1978)不完全性定理：一個足夠強大的形式系統，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。
·各種計算模型：哥德爾的遞歸函數理論，邱吉爾的l演算，圖靈機模型
·這些計算模型是計算機科學的理論基礎，是計算機的理論模型。