【正文】 第一講 引言一、課程內容 數(shù)理邏輯：是計算機科學的基礎，應熟練掌握將現(xiàn)實生活中的條件化成邏輯公式，并能做適當?shù)耐评恚@對程序設計等課程是極有用處的。 集合論：數(shù)學的基礎，對于學習程序設計、數(shù)據(jù)結構、編譯原理等幾乎所有計算機專業(yè)課程和數(shù)學課程都很有用處。熟練掌握有關集合、函數(shù)、關系等基本概念。 代數(shù)結構：對于抽象數(shù)據(jù)類型、形式語義的研究很有用處。培養(yǎng)數(shù)學思維，將以前學過的知識系統(tǒng)化、形式化和抽象化。熟練掌握有關代數(shù)系統(tǒng)的基本概念，以及群、環(huán)、域等代數(shù)結構的基本知識。 圖論：對于解決許多實際問題很有用處，對于學習數(shù)據(jù)結構、編譯原理課程也很有幫助。要求掌握有關圖、樹的基本概念，以及如何將圖論用于實際問題的解決，并培養(yǎng)其使用數(shù)學工具建立模型的思維方式。 講課時間為兩個學期，第一學期講授數(shù)理邏輯與集合論，第二學期講授代數(shù)結構和圖論?？荚噧热菹抻跁械膬热莺碗y度，但講課內容不限于書中的內容和難度。二、數(shù)理邏輯發(fā)展史1. 目的 了解有關的背景，加深對計算機學科的全面了解，特別是理論方面的了解，而不限于將計算機看成是一門技術或工程性的學科。 通過重要的歷史事件，了解計算機科學中的一些基本思維方式和一些基本問題。2. 數(shù)理邏輯的發(fā)展前期 前史時期——古典形式邏輯時期：亞里斯多德的直言三段論理論 初創(chuàng)時期——邏輯代數(shù)時期（17世紀末）資本主義生產力大發(fā)展，自然科學取得了長足的進步，數(shù)學在認識自然、發(fā)展技術方面起到了相當重要的作用。人們希望使用數(shù)學的方法來研究思維，把思維過程轉換為數(shù)學的計算。萊布尼茲(Leibniz, 1646~1716)完善三段論，提出了建立數(shù)理邏輯或者說理性演算的思想：提出將推理的正確性化歸于計算，這種演算能使人們的推理不依賴于對推理過程中的命題的含義內容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。使用一種符號語言來代替自然語言對演算進行描述，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規(guī)律，而與其含義無關。布爾(G. Boole, 1815~1864)代數(shù)：將有關數(shù)學運算的研究的代數(shù)系統(tǒng)推廣到邏輯領域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。3. 數(shù)理邏輯的奠基時期 弗雷格(G. Frege, 1848~1925)：《概念語言——一種按算術的公式語言構成的純思維公式語言》(1879)的出版標志著數(shù)理邏輯的基礎部分——命題演算和謂詞演算的正式建立。 皮亞諾(Giuseppe Peano, 1858~1932)：《用一種新的方法陳述的算術原理》(1889)提出了自然數(shù)算術的一個公理系統(tǒng)。 羅素(Bertrand Russell, 1872~1970)：《數(shù)學原理》(與懷特黑合著，1910, 1912, 1913)從命題演算和謂詞演算開始，然后通過一元和二元命題函項定義了類和關系的概念，建立了抽象的類演算和關系演算。由此出發(fā)，在類型論的基礎上用連續(xù)定義和證明的方式引出了數(shù)學（主要是算術）中的主要概念和定理。 邏輯演算的發(fā)展：甘岑(G. Gentzen)的自然推理系統(tǒng)(Natural Deduction System)，邏輯演算的元理論：公理的獨立性、一致性、完全性等。 各種各樣的非經典邏輯的發(fā)展：路易斯(Lewis, 1883~1964)的模態(tài)邏輯，實質蘊涵怪論和嚴格蘊涵、相干邏輯等，盧卡西維茨的多值邏輯等。4. 集合論的發(fā)展 看待無窮集合的兩種觀點：實無窮與潛無窮 康托爾(G. Cantor, 1845~1918)：以實無窮的思想為指導，建立了樸素集合論 外延原則（集合由它的元素決定）和概括原則（每一性質產生一集合）。 可數(shù)集和不可數(shù)集，確定無窮集合的本質在于集合本身能與其子集一一對應。能與正整數(shù)集合對應的集合是可數(shù)的，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對角線法證明了實數(shù)集合是不可數(shù)的。 超窮基數(shù)和超窮序數(shù) 樸素集合論的悖論：羅素悖論 公理集合論的建立：ZFC系統(tǒng)6. 第三次數(shù)學危機與邏輯主義、直覺主義與形式主義 集合論的悖論使得人們覺得數(shù)學產生了第三次危機，提出了數(shù)學的基礎到底是什么這樣的問題。 羅素等的邏輯主義：數(shù)學的基礎是邏輯，倡導一切數(shù)學可從邏輯符號推出，《數(shù)學原理》一書是他們這一思想的體現(xiàn)。為解決悖論產生了邏輯類型論。 布勞維爾(Brouwer, 1881~1966)的直覺主義：數(shù)學是心靈的構造，只承認可構造的數(shù)學，強調構造的能行性，與計算機科學有重要的聯(lián)系。堅持潛無窮，強調排中律不能用于無窮集合。海丁(Heyting)的直覺主義邏輯。 希爾伯特(D. Hilbert)的形式主義：公理化方法與形式化方法，元數(shù)學和證明論，提倡將邏輯演算和數(shù)學證明本身形式化，把用普通的語言傳達的內容上的數(shù)學科學變?yōu)橛脭?shù)學符號和邏輯符號按一定法則排列的一堆公式。為了消除悖論，要數(shù)學建立在公理化基礎上，將各門數(shù)學形式化，構成形式系統(tǒng)，并證明其一致性，這是希爾伯特的數(shù)學綱領。7. 數(shù)理邏輯的發(fā)展初期 哥德爾(Godel, 1906~1978)不完全性定理：一個足夠強大的形式系統(tǒng)，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。 各種計算模型：哥德爾的遞歸函數(shù)理論，邱吉爾的l演算，圖靈機模型 這些計算模型是計算機科學的理論基礎，是計算機的理論模型。三、預備知識1. 集合的基本概念 集合(set)：集合是數(shù)學中最基本的概念之一，不能以更簡單的概念來定義(define)，只能給出它的描述(description)。一些對象的整體就稱為一個集合，這個整體的每個對象稱為該集合的一個元素(member或element)。用大寫字母A, B, C等表示集合，用小寫字母a, b, c等表示集合的元素a206。A表示：a是集合A的元素，或說a屬于集合Aa207。A表示：a不是集合A的元素，或說a不屬于集合A集合中的元素是無序的，不重復的。通常使用兩種方法來給出一個集合： 列元素法：列出某集合的所有元素，如：A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于10的自然數(shù)所構成的集合B = {a, b, …, z} 表示所有小寫英文字母所構成的集合 性質概括法：使用某個性質來概括集合中的元素，如： A = { n | n 是小于10的自然數(shù)} C = { n | n 是質數(shù)} 表示所有質數(shù)所構成的集合 集合由它的元素所決定，換句話說，兩個集合A和B相等，記為A = B，如果A和B具有相同的元素，即a屬于集合A當且僅當a屬于集合B。 子集(subset)：說集合A是集合B的子集，記為A205。B，如果a屬于集合A則a也屬于集合B。因此A=B當且僅當A205。B且B205。A。說集合A是集合B的真子集(proper subset)，如果A205。B且A不等于B(A 185。 B)。 空集(empty set)：約定存在一個沒有任何元素的集合，稱為空集，記為f，有時也用{}來表示。按子集的定義，空集是任何集合的子集(為什么？)。 冪集(power set)：集合A的冪集，記為P(A)，是A的所有子集所構成的集合，即： P(A) = { B | B 205。 A } 例如，A = {0, 1}，則P(A) = { {}, {0}, {1}, {0, 1} } 顯然，對任意集合A，有f206。 P(A)和A206。P(A) 補集(plement set)：集合A的補集，記為A，是那些不屬于集合A的元素所構成的集合，即A = {x | x207。A}。通常來說，是在存在一個全集U的情況下討論集合的補集。全集U是所討論的問題域中所有元素所構成的集合。 集合的并(union)：集合A和B的并A200。B定義為：A200。B = {x | x206。A或者x206。B}，集合的并可推廣到多個集合，設A1, A2, …, An都是集合，它們的并定義為： A1200。A2…200。An = {x | 存在某個i，使得x206。Ai} 集合的交(intersection)：集合A和B的并A199。B定義為：A199。B = {x | x206。A而且x206。B}，集合的交也可推廣到多個集合，設A1, A2, …, An都是集合，它們的交定義為： A1200。A2…200。An = {x | 對所有的i，都有x206。Ai} 集合的差(difference)：集合A和B的差AB定義為：AB = {x | x206。A而且x207。B}。2. 關系和函數(shù)的基本概念 有序對(ordered pair)：設A和B是兩個集合，a206。A, b206。B是兩個元素，a和b的有序對，記為a, b，定義為集合{{a}, {a, b}}。 設a1, b1和a2, b2是兩個有序對，可以證明a1, b1 = a2, b2當且僅當a1 = a2且b1 = b2。(如何證？) 有序對可推廣到n個元素，設A1, A2, …, An是集合，a1206。A1, a2206。A2, …, an206。An是元素，定義有序n元組(ordered ntuple)a1, a2, …, an為a1, a2, …, an1, an，注意這是一個歸納(inductive)定義，將有序n元組的定義歸結為有序n1元組的定義。 顯然有a1, a2, …, an = b1, b2, …, bn當且僅當a1 = b1且a2 = b2且…且an = bn。 集合的笛卡爾積(cartesian product)：兩個集合A和B的笛卡爾積A180。B定義為： A180。B = {a, b | a206。A且b206。B} 例如，設A = {a, b, c}，B = {1, 2}，則：A180。B = {a, 1, a, 2, b, 1, b, 2, c, 1, c, 2} 笛卡爾積可推廣到多個集合的情況，集合A1, A2, …, An的笛卡爾積定義為： A1180。A2180?！?80。An = {a1, a2, …, an | a1206。A1且a2206。A2且…且an206。An} 集合之間的關系(relation)：定義n個集合A1, A2, …, An之間的一個n元關系R為集合A1, A2, …, An的笛卡爾積A1180。A2180?！?80。An的一個子集。設a1, a2, …, an206。A1180。A2180?！?80。An，若a1, a2, …, an206。R，則稱a1, a2, …, an間具有關系R，否則稱它們不具有關系R。特別地： 當A1 = A2 = … = An = A時，稱R為A上的n元關系。 當n = 2時，有R205。A1180。A2，稱R為A1與A2間的一個二元關系(binary relation)。這時若a1, a2206。R則簡記為a1Ra2，否則（即a1, a2207。R）記為a1Ra2。通常研究得最多的是二元關系，n元關系的許多性質可從二元關系的性質擴充而得到。如果沒有特別指明的話，說R是一個關系則是指R是一個二元關系。 當n = 1時，這時可認為R是集合A上滿足某種性質的子集。 關系的一些性質：設R是A上的二元關系： 說R是自反的(reflexive)，如果對任意的a206。A有aRa。 說R是反自反的(irreflexive)，如果對任意的a206。A有aRa。 說R是對稱的(symmetric)，如果對任意的a, b206。A有若aRb則bRa。 說R是反對稱的(antisymmetric)，如果對任意的a, b206。A有若aRb且bRa則a = b。 說R是傳遞的(transitive)，如果對任意的a, b, c 206。A有若aRb且bRc則aRc。 說R是等價關系(equivalence)，如果R是自反的、對稱的和傳遞的。 集合之間的函數(shù)(function，或說映射mapping)：定義集合A到B的函數(shù)f是A和B的笛卡爾積A180。B的一個子集，且滿足若x, y206。f及x, z206。f則y = z。因此函數(shù)是A和B之間的一個特殊的二元關系。通常記集合A到B的函數(shù)f為f : A174。B。 函數(shù)f : A174。B的定義域(domain)dom(f )定義為： dom(f ) = {x | 存在某個y206。B使得x, y206。f } 函數(shù)f : A174。B的值域(range)ran(f )定義為： ran(f ) = {y | 存在某個x206。A使得x, y206。f } 若x, y206。f，通常記y為f(x)，并稱y為x在函數(shù)f下的像(image)，x為y在函數(shù)f下的原像。 函數(shù)也可推廣到n元的情形：f : A1180。A2180?！?80。An174。B，意味著： f是A1180。A2180?！?80。An180。B的一個子集，且 x1, x2, …, xn, y206。 f且x1, x2, …, xn, z206。 f則y = z。 函數(shù)的一些性質：設f : A174。B是集合A到B的函數(shù)： 說f是全函數(shù)(total function)，若dom(f )=A，否則稱f是偏函數(shù)(partial function)。下面如果沒有特別指明的話，都是指全函數(shù)。 說f是滿射(surjection, 或說f maps A onto B)，如果ran(f ) = B，即對任意的y206。B都有原像。 說f是單射(injection，或說f is oneone)，如果有f (x1) = f(x2)則x1 = x2，即對任意的y206。B，如果它有原像的話，則有唯一的原像。 說f是雙射(bijection，或說f是一一對應)，如果f既是滿射，又是單射，即對任意的y206。B，都有唯一的原像，同樣根據(jù)全函數(shù)的定義，對于任意x206。A都有唯一的像。這時可以定義f的逆函數(shù)(inverse function)，記為f 1 : B174。A，f 1(y) = x當且僅當f(x) = y。顯然f 1也是雙射。 集合的基數(shù)(cardinal number)或說勢：集合A的基數(shù)記為|A|，且有： 對于有限集合A，令A的基數(shù)為A中元素的個數(shù)。 定義無限集合，不直接定義基數(shù)，而是通過定義兩個集合之間的等勢關系來刻劃集合的基數(shù)或勢，說集合A和集合B是等勢的(equipotent)，如果存在一個從A到B的雙射。根據(jù)雙射的性質，可以證明等勢是集合上的一個等價關系。 稱與自然數(shù)集等勢的集合為可列集(enumerable)，有限集和可列集統(tǒng)稱為可數(shù)集(countable)。 設A和B是有限集合，有|P(A)| = 2|A|，|A180。B| = |A| 180。 |B|。3. 小結 下面以樹的形式給出了以上主要概念之間的關系： 集合 子集 集合的補、并、交、差 有序對 冪集 笛卡爾積