第一講 引言

一、課程內(nèi)容

·數(shù)理邏輯：是計(jì)算機(jī)科學(xué)的基礎(chǔ)，應(yīng)熟練掌握將現(xiàn)實(shí)生活中的條件化成邏輯公式，并能做適當(dāng)?shù)耐评恚@對(duì)程序設(shè)計(jì)等課程是極有用處的。

·集合論：數(shù)學(xué)的基礎(chǔ)，對(duì)于學(xué)習(xí)程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、編譯原理等幾乎所有計(jì)算機(jī)專業(yè)課程和數(shù)學(xué)課程都很有用處。熟練掌握有關(guān)集合、函數(shù)、關(guān)系等基本概念。

·代數(shù)結(jié)構(gòu)：對(duì)于抽象數(shù)據(jù)類型、形式語義的研究很有用處。培養(yǎng)數(shù)學(xué)思維，將以前學(xué)過的知識(shí)系統(tǒng)化、形式化和抽象化。熟練掌握有關(guān)代數(shù)系統(tǒng)的基本概念，以及群、環(huán)、域等代數(shù)結(jié)構(gòu)的基本知識(shí)。

·圖論：對(duì)于解決許多實(shí)際問題很有用處，對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、編譯原理課程也很有幫助。要求掌握有關(guān)圖、樹的基本概念，以及如何將圖論用于實(shí)際問題的解決，并培養(yǎng)其使用數(shù)學(xué)工具建立模型的思維方式。

·講課時(shí)間為兩個(gè)學(xué)期，第一學(xué)期講授數(shù)理邏輯與集合論，第二學(xué)期講授代數(shù)結(jié)構(gòu)和圖論。考試內(nèi)容限于書中的內(nèi)容和難度，但講課內(nèi)容不限于書中的內(nèi)容和難度。

 

二、數(shù)理邏輯發(fā)展史

1.目的

·了解有關(guān)的背景，加深對(duì)計(jì)算機(jī)學(xué)科的全面了解，特別是理論方面的了解，而不限于將計(jì)算機(jī)看成是一門技術(shù)或工程性的學(xué)科。

·通過重要的歷史事件，了解計(jì)算機(jī)科學(xué)中的一些基本思維方式和一些基本問題。

 

2.數(shù)理邏輯的發(fā)展前期

·前史時(shí)期——古典形式邏輯時(shí)期：亞里斯多德的直言三段論理論

·初創(chuàng)時(shí)期——邏輯代數(shù)時(shí)期（17世紀(jì)末）

·資本主義生產(chǎn)力大發(fā)展，自然科學(xué)取得了長(zhǎng)足的進(jìn)步，數(shù)學(xué)在認(rèn)識(shí)自然、發(fā)展技術(shù)方面起到了相當(dāng)重要的作用。

·人們希望使用數(shù)學(xué)的方法來研究思維，把思維過程轉(zhuǎn)換為數(shù)學(xué)的計(jì)算。

·萊布尼茲(Leibniz, 1646~1716)完善三段論，提出了建立數(shù)理邏輯或者說理性演算的思想：

·提出將推理的正確性化歸于計(jì)算，這種演算能使人們的推理不依賴于對(duì)推理過程中的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。

·使用一種符號(hào)語言來代替自然語言對(duì)演算進(jìn)行描述，將符號(hào)的形式和其含義分開。使得演算從很大程度上取決與符號(hào)的組合規(guī)律，而與其含義無關(guān)。

·布爾(G. Boole, 1815~1864)代數(shù)：將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。

 

3.數(shù)理邏輯的奠基時(shí)期

·弗雷格(G. Frege, 1848~1925)：《概念語言——一種按算術(shù)的公式語言構(gòu)成的純思維公式語言》(1879)的出版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分——命題演算和謂詞演算的正式建立。

·皮亞諾(Giuseppe Peano, 1858~1932)：《用一種新的方法陳述的算術(shù)原理》(1889)提出了自然數(shù)算術(shù)的一個(gè)公理系統(tǒng)。

·羅素(Bertrand Russell, 1872~1970)：《數(shù)學(xué)原理》(與懷特黑合著，1910, 1912, 1913)從命題演算和謂詞演算開始，然后通過一元和二元命題函項(xiàng)定義了類和關(guān)系的概念，建立了抽象的類演算和關(guān)系演算。由此出發(fā)，在類型論的基礎(chǔ)上用連續(xù)定義和證明的方式引出了數(shù)學(xué)（主要是算術(shù)）中的主要概念和定理。

·邏輯演算的發(fā)展：甘岑(G. Gentzen)的自然推理系統(tǒng)(Natural Deduction System)，邏輯演算的元理論：公理的獨(dú)立性、一致性、完全性等。

·各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis, 1883~1964)的模態(tài)邏輯，實(shí)質(zhì)蘊(yùn)涵怪論和嚴(yán)格蘊(yùn)涵、相干邏輯等，盧卡西維茨的多值邏輯等。

 

4.集合論的發(fā)展

·看待無窮集合的兩種觀點(diǎn)：實(shí)無窮與潛無窮

·康托爾(G. Cantor, 1845~1918)：以實(shí)無窮的思想為指導(dǎo)，建立了樸素集合論

·外延原則（集合由它的元素決定）和概括原則（每一性質(zhì)產(chǎn)生一集合）。

·可數(shù)集和不可數(shù)集，確定無窮集合的本質(zhì)在于集合本身能與其子集一一對(duì)應(yīng)。能與正整數(shù)集合對(duì)應(yīng)的集合是可數(shù)的，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對(duì)角線法證明了實(shí)數(shù)集合是不可數(shù)的。

·超窮基數(shù)和超窮序數(shù)

·樸素集合論的悖論：羅素悖論

·公理集合論的建立：ZFC系統(tǒng)

 

6.第三次數(shù)學(xué)危機(jī)與邏輯主義、直覺主義與形式主義

·集合論的悖論使得人們覺得數(shù)學(xué)產(chǎn)生了第三次危機(jī)，提出了數(shù)學(xué)的基礎(chǔ)到底是什么這樣的問題。

·羅素等的邏輯主義：數(shù)學(xué)的基礎(chǔ)是邏輯，倡導(dǎo)一切數(shù)學(xué)可從邏輯符號(hào)推出，《數(shù)學(xué)原理》一書是他們這一思想的體現(xiàn)。為解決悖論產(chǎn)生了邏輯類型論。

·布勞維爾(Brouwer, 1881~1966)的直覺主義：數(shù)學(xué)是心靈的構(gòu)造，只承認(rèn)可構(gòu)造的數(shù)學(xué)，強(qiáng)調(diào)構(gòu)造的能行性，與計(jì)算機(jī)科學(xué)有重要的聯(lián)系。堅(jiān)持潛無窮，強(qiáng)調(diào)排中律不能用于無窮集合。海丁(Heyting)的直覺主義邏輯。

·希爾伯特(D. Hilbert)的形式主義：公理化方法與形式化方法，元數(shù)學(xué)和證明論，提倡將邏輯演算和數(shù)學(xué)證明本身形式化，把用普通的語言傳達(dá)的內(nèi)容上的數(shù)學(xué)科學(xué)變?yōu)橛脭?shù)學(xué)符號(hào)和邏輯符號(hào)按一定法則排列的一堆公式。為了消除悖論，要數(shù)學(xué)建立在公理化基礎(chǔ)上，將各門數(shù)學(xué)形式化，構(gòu)成形式系統(tǒng)，并證明其一致性，這是希爾伯特的數(shù)學(xué)綱領(lǐng)。

 

7.數(shù)理邏輯的發(fā)展初期

·哥德爾(Godel, 1906~1978)不完全性定理：一個(gè)足夠強(qiáng)大的形式系統(tǒng)，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。

·各種計(jì)算模型：哥德爾的遞歸函數(shù)理論，邱吉爾的l演算，圖靈機(jī)模型

·這些計(jì)算模型是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，是計(jì)算機(jī)的理論模型。

三、預(yù)備知識(shí)

1.集合的基本概念

·集合(set)：集合是數(shù)學(xué)中最基本的概念之一，不能以更簡(jiǎn)單的概念來定義(define)，只能給出它的描述(description)。一些對(duì)象的整體就稱為一個(gè)集合，這個(gè)整體的每個(gè)對(duì)象稱為該集合的一個(gè)元素(member或element)。

·用大寫字母A, B, C等表示集合，用小寫字母a, b, c等表示集合的元素

·a?A表示：a是集合A的元素，或說a屬于集合A

·a?A表示：a不是集合A的元素，或說a不屬于集合A

·集合中的元素是無序的，不重復(fù)的。通常使用兩種方法來給出一個(gè)集合：

·列元素法：列出某集合的所有元素，如：

·A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于10的自然數(shù)所構(gòu)成的集合

·B = {a, b, …, z} 表示所有小寫英文字母所構(gòu)成的集合

·性質(zhì)概括法：使用某個(gè)性質(zhì)來概括集合中的元素，如：

·A = { n | n 是小于10的自然數(shù)}

·C = { n | n 是質(zhì)數(shù)} 表示所有質(zhì)數(shù)所構(gòu)成的集合

·集合由它的元素所決定，換句話說，兩個(gè)集合A和B相等，記為A = B，如果A和B具有相同的元素，即a屬于集合A當(dāng)且僅當(dāng)a屬于集合B。 

·子集(subset)：說集合A是集合B的子集，記為AíB，如果a屬于集合A則a也屬于集合B。因此A=B當(dāng)且僅當(dāng)AíB且BíA。說集合A是集合B的真子集(proper subset)，如果AíB且A不等于B(A 1 B)。

·空集(empty set)：約定存在一個(gè)沒有任何元素的集合，稱為空集，記為f，有時(shí)也用{}來表示。按子集的定義，空集是任何集合的子集(為什么？)。

·冪集(power set)：集合A的冪集，記為P(A)，是A的所有子集所構(gòu)成的集合，即：

·P(A) = { B | B í A }

·例如，A = {0, 1}，則P(A) = { {}, {0}, {1}, {0, 1} }

·顯然，對(duì)任意集合A，有f? P(A)和A?P(A) 

·補(bǔ)集(complement set)：集合A的補(bǔ)集，記為A，是那些不屬于集合A的元素所構(gòu)成的集合，即A = {x | x?A}。通常來說，是在存在一個(gè)全集U的情況下討論集合的補(bǔ)集。全集U是所討論的問題域中所有元素所構(gòu)成的集合。

·集合的并(union)：集合A和B的并AèB定義為：AèB = {x | x?A或者x?B}，集合的并可推廣到多個(gè)集合，設(shè)A1, A2, …, An都是集合，它們的并定義為：

A1èA2…èAn = {x | 存在某個(gè)i，使得x?Ai}

·集合的交(intersection)：集合A和B的并A?B定義為：A?B = {x | x?A而且x?B}，集合的交也可推廣到多個(gè)集合，設(shè)A1, A2, …, An都是集合，它們的交定義為：

A1èA2…èAn = {x | 對(duì)所有的i，都有x?Ai}

·集合的差(difference)：集合A和B的差A(yù)-B定義為：A-B = {x | x?A而且x?B}。

 

2.關(guān)系和函數(shù)的基本概念

·有序?qū)?ordered pair)：設(shè)A和B是兩個(gè)集合，a?A, b?B是兩個(gè)元素，a和b的有序?qū)Γ洖?lt;a, b>，定義為集合{{a}, {a, b}}。

·設(shè)<a1, b1>和<a2, b2>是兩個(gè)有序?qū)Γ梢宰C明<a1, b1> = <a2, b2>當(dāng)且僅當(dāng)a1 = a2且b1 = b2。(如何證？)

·有序?qū)赏茝V到n個(gè)元素，設(shè)A1, A2, …, An是集合，a1?A1, a2?A2, …, an?An是元素，定義有序n元組(ordered n-tuple)<a1, a2, …, an>為<<a1, a2, …, an-1>, an>，注意這是一個(gè)歸納(inductive)定義，將有序n元組的定義歸結(jié)為有序n-1元組的定義。

·顯然有<a1, a2, …, an> = <b1, b2, …, bn>當(dāng)且僅當(dāng)a1 = b1且a2 = b2且…且an = bn。 

·集合的笛卡爾積(cartesian product)：兩個(gè)集合A和B的笛卡爾積A′B定義為：

A′B = {<a, b> | a?A且b?B}

·例如，設(shè)A = {a, b, c}，B = {1, 2}，則：

A′B = {<a, 1>, <a, 2>, <b, 1>, <b, 2>, <c, 1>, <c, 2>}

·笛卡爾積可推廣到多個(gè)集合的情況，集合A1, A2, …, An的笛卡爾積定義為：

A1′A2′…′An = {<a1, a2, …, an> | a1?A1且a2?A2且…且an?An} 

·集合之間的關(guān)系(relation)：定義n個(gè)集合A1, A2, …, An之間的一個(gè)n元關(guān)系R為集合A1, A2, …, An的笛卡爾積A1′A2′…′An的一個(gè)子集。設(shè)<a1, a2, …, an>?A1′A2′…′An，若<a1, a2, …, an>?R，則稱a1, a2, …, an間具有關(guān)系R，否則稱它們不具有關(guān)系R。特別地：

·當(dāng)A1 = A2 = … = An = A時(shí)，稱R為A上的n元關(guān)系。

·當(dāng)n = 2時(shí)，有RíA1′A2，稱R為A1與A2間的一個(gè)二元關(guān)系(binary relation)。這時(shí)若<a1, a2>?R則簡(jiǎn)記為a1Ra2，否則（即<a1, a2>?R）記為a1Ra2。通常研究得最多的是二元關(guān)系，n元關(guān)系的許多性質(zhì)可從二元關(guān)系的性質(zhì)擴(kuò)充而得到。如果沒有特別指明的話，說R是一個(gè)關(guān)系則是指R是一個(gè)二元關(guān)系。

·當(dāng)n = 1時(shí)，這時(shí)可認(rèn)為R是集合A上滿足某種性質(zhì)的子集。

·關(guān)系的一些性質(zhì)：設(shè)R是A上的二元關(guān)系：

·說R是自反的(reflexive)，如果對(duì)任意的a?A有aRa。

·說R是反自反的(irreflexive)，如果對(duì)任意的a?A有aRa。

·說R是對(duì)稱的(symmetric)，如果對(duì)任意的a, b?A有若aRb則bRa。

· 說R是反對(duì)稱的(antisymmetric)，如果對(duì)任意的a, b?A有若aRb且bRa則a = b。

·說R是傳遞的(transitive)，如果對(duì)任意的a, b, c ?A有若aRb且bRc則aRc。

·說R是等價(jià)關(guān)系(equivalence)，如果R是自反的、對(duì)稱的和傳遞的。 

·集合之間的函數(shù)(function，或說映射mapping)：定義集合A到B的函數(shù)f是A和B的笛卡爾積A′B的一個(gè)子集，且滿足若<x, y>?f及<x, z>?f則y = z。因此函數(shù)是A和B之間的一個(gè)特殊的二元關(guān)系。通常記集合A到B的函數(shù)f為f : A?B。

·函數(shù)f : A?B的定義域(domain)dom(f )定義為：

dom(f ) = {x | 存在某個(gè)y?B使得<x, y>?f }

·函數(shù)f : A?B的值域(range)ran(f )定義為：

ran(f ) = {y | 存在某個(gè)x?A使得<x, y>?f }

·若<x, y>?f，通常記y為f(x)，并稱y為x在函數(shù)f下的像(image)，x為y在函數(shù)f下的原像。

·函數(shù)也可推廣到n元的情形：f : A1′A2′…′An?B，意味著：

·f是A1′A2′…′An′B的一個(gè)子集，且

·<x1, x2, …, xn, y>? f且<x1, x2, …, xn, z>? f則y = z。 

·函數(shù)的一些性質(zhì)：設(shè)f : A?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，即對(duì)任意的y?B都有原像。

·說f是單射(injection，或說f is one-one)，如果有f (x1) = f(x2)則x1 = x2，即對(duì)任意的y?B，如果它有原像的話，則有唯一的原像。

·說f是雙射(bijection，或說f是一一對(duì)應(yīng))，如果f既是滿射，又是單射，即對(duì)任意的y?B，都有唯一的原像，同樣根據(jù)全函數(shù)的定義，對(duì)于任意x?A都有唯一的像。這時(shí)可以定義f的逆函數(shù)(inverse function)，記為f -1 : B?A，f -1(y) = x當(dāng)且僅當(dāng)f(x) = y。顯然f -1也是雙射。 

·集合的基數(shù)(cardinal number)或說勢(shì)：集合A的基數(shù)記為|A|，且有：

·對(duì)于有限集合A，令A(yù)的基數(shù)為A中元素的個(gè)數(shù)。

·定義無限集合，不直接定義基數(shù)，而是通過定義兩個(gè)集合之間的等勢(shì)關(guān)系來刻劃集合的基數(shù)或勢(shì)，說集合A和集合B是等勢(shì)的(equipotent)，如果存在一個(gè)從A到B的雙射。根據(jù)雙射的性質(zhì)，可以證明等勢(shì)是集合上的一個(gè)等價(jià)關(guān)系。

·稱與自然數(shù)集等勢(shì)的集合為可列集(enumerable)，有限集和可列集統(tǒng)稱為可數(shù)集(countable)。

·設(shè)A和B是有限集合，有|P(A)| = 2|A|，|A′B| = |A| ′ |B|。

. 歸納定義和歸納證明

·一個(gè)集合的歸納定義(inductive definition)通常分為三步：

·歸納基：一些基本的元素屬于該集合；

·歸納步：定義一些規(guī)則（或者說操作），從該集合中已有的元素來生成該集合的新的元素；

·最小化：該集合中的所有元素都是通過基本元素以及所定義的規(guī)則生成的，換句話說，該集合是由基本元素及規(guī)則所生成的最小的集合。

·自然數(shù)集N的歸納定義：

[1]. 歸納基：0是一個(gè)自然數(shù)，即0? N。

[2]. 歸納步：若n是自然數(shù)，則n的后繼也是自然數(shù)。記n的后繼為succ(n)，即若n?N，則succ(n)?N。為方便起見，后面也記n的后繼為n+1。

[3]. 最小化：所有的自然都通過步驟[1]和[2]得到，或者說自然數(shù)集是通過步驟[1]和[2]得到的最小集合。

·這種定義方式可推廣到對(duì)其他一些概念的定義，例如上述多個(gè)集合的并、交、笛卡爾積以及多個(gè)元素的有序n元組都可通過遞歸的方式定義。例如，對(duì)于多個(gè)集合的并可定義為：

·歸納基：A1èA2 = {x | x?A1或者x?A2}

·歸納步：A1èA2…èAn = (A1èA2…èAn-1) è An

·這里不需要最小化，因?yàn)檫@里不是定義集合。

·數(shù)學(xué)歸納法：關(guān)于自然數(shù)的許多性質(zhì)都可通過數(shù)學(xué)歸納法來證明，對(duì)于性質(zhì)R，如果它對(duì)0成立，而且如果對(duì)于n成立的話，能夠得到它對(duì)于n+1也成立，那么性質(zhì)R對(duì)所有的自然數(shù)成立。這種證明方法的正確性本身可通過自然數(shù)的歸納定義來得到證明：

·定義集合S = {n?N | 性質(zhì)R對(duì)n成立}

·歸納基：根據(jù)上面的定義有0?S

·歸納步：根據(jù)上面的定義有如果n?S，則n+1?S，所以S是滿足上面自然數(shù)集的歸納定義中的1、2點(diǎn)的一個(gè)集合，而自然數(shù)集N是滿足這兩點(diǎn)的最小集合，所以有N íS，而顯然有SíN，所以S = N。

·數(shù)學(xué)歸納法舉例：使用數(shù)學(xué)歸納法證明1 + 2 + … + n = (n * (n+1))/2

·歸納基：當(dāng)n = 0時(shí)顯然成立。

·歸納步：如果對(duì)于n成立，則有1 + 2 + … + n = (n * (n+1))/2（這稱為歸納假設(shè)），現(xiàn)在要證對(duì)于n+1也成立。顯然有：

1 + 2 + … + n + (n + 1) = (n * (n+1))/2 + (n+1) // 根據(jù)歸納假設(shè)

= (n * (n+1) + 2 * (n+1))/2 = ((n+1) * ((n+1) + 1))/2

因此要證的公式對(duì)于n+1成立，所以對(duì)于所有的自然數(shù)成立。

·顯然在數(shù)學(xué)歸納法中，對(duì)于歸納基改為R對(duì)于自然數(shù)k成立，歸納步不變的話，則可證明R對(duì)于所有大于k的自然數(shù)都成立。

·在數(shù)學(xué)歸納法中，也可將歸納步改為如果R對(duì)于所有小于n的自然數(shù)成立，則推出R對(duì)于n也成立，即歸納步是假設(shè)對(duì)于所有小于n的自然數(shù)性質(zhì)R成立來導(dǎo)出性質(zhì)R對(duì)于自然數(shù)n成立。這種形式的數(shù)學(xué)歸納法通常稱為第二數(shù)學(xué)歸納法。
 

5. 形式系統(tǒng)

·形式系統(tǒng)的定義：一個(gè)形式系統(tǒng)S由下列4個(gè)集合構(gòu)成：

·一個(gè)非空集合SS，稱為形式系統(tǒng)S的字母表或說符號(hào)(Symbol)表；

·一個(gè)由SS中字母的有限序列（字符串）所構(gòu)成的集合FS，稱為形式系統(tǒng)S的公式(Formula)集；

·從FS中選取一個(gè)子集AS，稱為形式系統(tǒng)S的公理(Axiom)集；

·FS上有一個(gè)部分函數(shù)集RS = {Rn | Rn : FS ′ FS ′…′ FS ?FS , n = 1, 2, …}，稱為形式系統(tǒng)S的規(guī)則(Rule)集，其中Rn : FS ′ FS ′…′ FS ?FS是n元的部分函數(shù)，我們稱其為n元規(guī)則。

·形式系統(tǒng)中的定理(Theorem)：

·歸納基：t ? AS 是形式系統(tǒng)S中的定理。

· 歸納步：t1, t2, …, tn是形式系統(tǒng)S中的定理，而Rn?是S中的規(guī)則，那么Rn(t1, t2, …, tn)也是形式系統(tǒng)S中的定理。

·對(duì)于形式系統(tǒng)中的規(guī)則Rn : FS ′ FS ′…′ FS ?FS，通常表示成下面的形式：

t1, t2, …, tn

Rn(t1, t2, …, tn)

·形式系統(tǒng)具有兩個(gè)特征：

·形式化實(shí)際上是一個(gè)可機(jī)械實(shí)現(xiàn)的過程，在它里面，符號(hào)、規(guī)則和演算等被表示得嚴(yán)密、精確。在形式系統(tǒng)S中，只能使用字母表SS中的符號(hào)，只承認(rèn)公式集FS中的符號(hào)串的合理性，只能由公理集，根據(jù)規(guī)則推出有意義的東西來。

·形式系統(tǒng)一旦完成，就成了符號(hào)串及根據(jù)規(guī)則進(jìn)行的符號(hào)串的改寫，系統(tǒng)與一切實(shí)際意義就毫不相干，或者說已經(jīng)通過這種符號(hào)，從實(shí)際問題中抽象出了我們所需要研究的內(nèi)容。在形式系統(tǒng)內(nèi)部，所能認(rèn)識(shí)的只能是符號(hào)串及其改寫，只能在形式系統(tǒng)外對(duì)這種符號(hào)串及規(guī)則賦予意義。 

·對(duì)象語言(Object language)與元語言(Meta language)：

·數(shù)理邏輯所研究的是“數(shù)學(xué)推理”，而使用的方法也是數(shù)學(xué)推理，所以有必要區(qū)分這兩個(gè)層次的推理。

·把作為研究對(duì)象的“推理”形式化，使用形式語言來表示作為研究對(duì)象的“推理”的前提、結(jié)論和規(guī)則等，這種形式語言是我們所研究的對(duì)象語言。

·另一方面，關(guān)于形式系統(tǒng)的性質(zhì)、規(guī)律的表達(dá)和作為研究方面的推理方式使用另一種語言來表達(dá)，這個(gè)語言稱為研究的元語言，通常使用半數(shù)學(xué)化的自然語言。

·形式語言的語法(Syntax)與語義(Semantic)：

·形式語言的語法是構(gòu)成形式系統(tǒng)的公式集、公理集和規(guī)則集的法則。

·形式語言的語義是關(guān)于形式系統(tǒng)的解釋和意思。

·形式語言本身沒有含義，但我們?cè)跇?gòu)造它們時(shí)是假想它們能代表某種意義的，特別的當(dāng)我們?cè)谶x擇形式系統(tǒng)的公理時(shí)，總是選擇所研究的問題域中那些最為明顯或最容易公認(rèn)為正確的性質(zhì)。

 

6. 習(xí)題

1. 令集合A = { n | n ￡ 10且n 是奇數(shù)}，B = {n | n ￡ 10且n是素?cái)?shù)}，請(qǐng)回答下列問題：

a) 請(qǐng)用列元素的方法列出集合A和集合B，請(qǐng)問集合B是否是集合A的子集？

b) 請(qǐng)計(jì)算AèB、A?B、A-B、A′B以及P(A)(即A的冪集)。

2. 設(shè)關(guān)系R = {<a, b> | a和b是互質(zhì)的自然數(shù)}，請(qǐng)問R是自反的嗎？對(duì)稱的嗎？傳遞的嗎？為什么？

3. 設(shè)f : A?B是函數(shù)，R是A上的如下二元關(guān)系：R = {<a, b> | a, b?A, f (a) = f (b) }，  證明R是A上的一個(gè)等價(jià)關(guān)系。

4. 使用數(shù)學(xué)歸納法證明：12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6

5. 設(shè)有函數(shù)f : N?N ′ N，f(n) = <n, n+1>，請(qǐng)問f是不是單射、滿射或雙射？

*6.設(shè)R1和R2都是A上的等價(jià)關(guān)系，請(qǐng)問R1èR2和R1?R2是否還是A上的等價(jià)關(guān)系？如果是請(qǐng)證明，否則請(qǐng)舉一反例。

*7.設(shè)R是集合A上的等價(jià)關(guān)系，a?A，可定義：

a) [a] = {b?A | aRb }，稱[a]為a關(guān)于R的等價(jià)類；

b) A/R = {[a] | a?A}，稱A關(guān)于R的商集。

設(shè)函數(shù)f : A?A/R定義為對(duì)任意a?A有f(a) = [a]，請(qǐng)問R滿足怎樣的條件時(shí)f是單射？

*8 請(qǐng)給出<x, y, z>的集合方式的定義。若定義：[x, y, z] = {{x}, {x, y}, {x, y, z}}，則如果有[x1, y1, z1] = [x2, y2, z2]是否意味著有x1 = x2且y1 = y2且z1 = z2？
 

3.命題邏輯公式

【定義1.1】命題邏輯公式(propositional logic formula)由以下子句歸納定義：

[1]. 歸納基：命題常量或命題變量是命題邏輯公式，稱為命題邏輯公式的原子項(xiàng)。

[2]. 歸納步：如果A, B是邏輯公式，則(?A)、(AùB)、(AúB)、(A?B)和(A?B)也是命題邏輯公式。

[3]. 最小化：所有的命題邏輯公式都通過1和2得到。

在這里我們隱含地使用的字母表是大小寫的英文字母、命題聯(lián)結(jié)符和園括號(hào)。英文字母還可帶下標(biāo)。其它的符號(hào)都不屬于我們的符號(hào)表，即在命題邏輯公式中不能出現(xiàn)這些符號(hào)。后面我們將命題邏輯公式簡(jiǎn)稱為命題公式，或在沒有二義的情況下進(jìn)一步簡(jiǎn)稱為公式。

【例子1.1】((p ú q) ? ((?p) ? (q ù r)))是命題公式，它通過以下步驟生成：

1.p是公式；  // 根據(jù)定義1.1的[1]

2.q是公式；  // 根據(jù)定義1.1的[1]

3.(p ú q)是公式；// 根據(jù)定義1.1的[2]

4.(?p)是公式； // 根據(jù)定義1.1的[2]

5.r是公式；  // 根據(jù)定義1.1的[1]

6.(q ù r)是公式；// 根據(jù)定義1.1的[2]

7.((?p) ? (q ù r))是公式；// 根據(jù)定義1.1的[2]，以及4, 6

8.((p ú q) ? ((?p) ? (q ù r)))是公式。  // 根據(jù)定義1.1的[2]，以及3, 7

【定理1.2】設(shè)R是某個(gè)性質(zhì)，如果有：

[1]. 對(duì)于所有的原子項(xiàng)p，都滿足性質(zhì)R；

[2]. 如果對(duì)任意的公式A和B都滿足性質(zhì)R，就有(?A)、(AùB)、(AúB)、(A?B)和(A?B)也滿足性質(zhì)R。

那么，所有的公式A就都滿足性質(zhì)R。□

該定理的證明類似數(shù)學(xué)歸納法的證明，很容易根據(jù)定義1.1得到。

 

【定義1.3】命題公式A的復(fù)雜程度deg(A)定義為：

[1]. 如果A是原子項(xiàng)，則deg(A) = 0；

[2]. deg(?A) = deg(A) + 1;

[3]. deg(A * B) = max(deg(A), deg(B)) + 1，其中*代表ù、ú、?、?之一。 

此定義等價(jià)于教材p11的定義1.7。只不過我們?cè)谶@里給出的是遞歸定義。使用歸納法，我們可證明下面定理：

 

【定理1.4】deg(A)小于等于命題公式A中的命題聯(lián)結(jié)符號(hào)的數(shù)目。

 

【證明】根據(jù)命題公式A的結(jié)構(gòu)進(jìn)行歸納證明：

1. 歸納基：如果A是原子項(xiàng)，則根據(jù)定義1.3有deg(A) = 0，顯然定理成立。

2. 歸納步：假設(shè)定理對(duì)于命題公式A和B成立（歸納假設(shè)），記命題公式A中的命題聯(lián)結(jié)符號(hào)數(shù)為Sym(A)，即有deg(A) ￡ Sym(A)和deg(B) ￡ Sym(B)。那么由于deg(?A) = deg(A) + 1，而Sym(?A) = Sym(A) + 1，所以定理對(duì)于?A也成立。同樣由于deg(A * B) = max(deg(A), deg(B)) + 1，而Sym(A * B) = Sym(A) + Sym(B) + 1，因而有deg(A * B)￡ Sym(A * B)，從而定理對(duì)所有的命題公式都成立。

 

【定理1.5】任意命題邏輯公式A中出現(xiàn)相等數(shù)目的左右園括號(hào)，實(shí)際上，左右園括號(hào)的個(gè)數(shù)都等于A中的命題聯(lián)結(jié)符號(hào)數(shù)。

 

【定理1.6】任意命題邏輯公式A具有下列6種形式之一，且只具有其中一種形式：

[1]. A為原子項(xiàng)；[2]. (?A)[3]. (AùB)

[4]. (AúB)[5]. (A?B)[6]. (A?B)

【定理1.6】的確切含義包括以下幾點(diǎn)：

1. 任意命題公式必然具有上述6中形式之一；

2. 這6中形式都互不相同；

3. 如果(?A)與(?A1)相同，則必有A與A1相同；

4. 如果(A * B)與(A1 * B1)相同，則必有A與A1相同，且B與B1相同。 

根據(jù)定理1.5和定理1.6，我們不難明白例子1.1是如何得到該其中命題公式的語法分析樹的。實(shí)際上每個(gè)命題公式的最左邊都是左園括號(hào)，如果從第二個(gè)符號(hào)不是左園括號(hào)，那么這個(gè)公式只有一個(gè)命題聯(lián)結(jié)符。否則找與第二個(gè)左園括號(hào)配對(duì)的右園括號(hào)，從而將命題公式劃分為這樣的形式：((…) * (…))，如果原來的命題公式為根的話，那么左右兩邊的兩個(gè)命題公式分別為它的左右子樹了，而且對(duì)這兩個(gè)公式可作類似的分析，最后到原子項(xiàng)。

在后面，為了書寫方便起見，我們省略最外邊的括號(hào)，并規(guī)定各個(gè)命題聯(lián)結(jié)符的優(yōu)先級(jí)別為?大于ù，ù大于ú，ú大于?，?大于?，從而可省略命題公式中一些不必要的園括號(hào)，例如例子1.1中的公式可寫為：p ú q ? ?p ? q ù r。不過在后面我們書寫公式的原則是盡量簡(jiǎn)便，但又能讓讀者容易理解。而有關(guān)命題公式的性質(zhì)的討論，則只針對(duì)可由上面定義1.1所能生成的公式形式。

上面討論的命題公式的語法結(jié)構(gòu)，下面討論命題公式的賦值。

 

【定義1.7】 對(duì)命題公式的一次真值賦值t是從所有命題變量所組成的集合到集合{0, 1}的函數(shù)。實(shí)際上，對(duì)于某個(gè)命題公式A來說，我們只關(guān)心t在A中的命題變量上的值。這里我們假定存在一個(gè)所有命題變量所組成的集合U，或者說我們所有命題公式中的變量都取之于集合U，我們記命題公式A中的所有命題變量所組成的集合為Var(A)。設(shè)有一個(gè)真值賦值t : U?{0, 1}，而對(duì)于命題公式A的真值賦值來說，我們只關(guān)心t在Var(A)上的值。

【例子1.3】對(duì)于命題公式A = ((p ú q) ? ((?p) ? (q ù r)))，有：

Var(A) = {p, q, r}

這里不妨假定U = Var(A)，真值賦值就是一個(gè)函數(shù)t : {p, q, r}?{0, 1}，例如可令：

t(p) = 0, t(q) = 1, t(r) = 0

 

【定義1.8】命題公式A在真值賦值t : U?{0, 1}下的真值t(A)遞歸定義如下：

[1].如果命題公式A是一個(gè)命題常量p，則如果p為真，t(A) = 1，否則t(A) = 0；

[2].如果命題公式A是一個(gè)命題變量p，則t(A) = t(p)

[3].若t(A) = 0則t(?A) = 1，否則t(?A) = 0。

[4].若t(A) = t(B) = 1，則t(AùB) = 1，否則t(AùB) = 0。

[5].若t(A) = t(B) = 0，則t(AúB) = 0，否則t(AúB) = 1。

[6].若t(A) = 0或者t(B) = 1，則t(A?B) = 1，否則t(A?B) = 0。

[7].若t(A) = t(B)，則t(A?B) = 1，否則t(A?B) = 0。

【例子1.3，續(xù)】對(duì)于命題公式A = ((p ú q) ? ((?p) ? (q ù r)))，及真值賦值函數(shù)t：

t(p) = 0, t(q) = 1, t(r) = 0

有：

1.  t(p) = 0, t(q) = 1;

2.  t(p ú q) = 1;// 根據(jù)定義1.8的[5]

4.  t(?p) = 1;// 根據(jù)定義1.8的[3]