1、第一講引言一、課程內(nèi)容數(shù)理邏輯：是計算機(jī)科學(xué)的基礎(chǔ)，應(yīng)熟練掌握將現(xiàn)實(shí)生活中的條件化成邏輯公式，并能做適當(dāng)?shù)耐评?，這對程序設(shè)計等課程是極有用處的。集合論：數(shù)學(xué)的基礎(chǔ)，對于學(xué)習(xí)程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、編譯原理等幾乎所有計算機(jī)專業(yè)課程和數(shù)學(xué)課程都很有用處。熟練掌握有關(guān)集合、函數(shù)、關(guān)系等基本概念。代數(shù)結(jié)構(gòu)：對于抽象數(shù)據(jù)類型、形式語義的研究很有用處。培養(yǎng)數(shù)學(xué)思維，將以前學(xué)過的知識系統(tǒng)化、形式化和抽象化。熟練掌握有關(guān)代數(shù)系統(tǒng)的基本概念，以及群、環(huán)、域等代數(shù)結(jié)構(gòu)的基本知識。圖論：對于解決許多實(shí)際問題很有用處，對于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、編譯原理課程也很有幫助。要求掌握有關(guān)圖、樹的基本概念，以及如何將圖論用于實(shí)際問題的解決

2、，并培養(yǎng)其使用數(shù)學(xué)工具建立模型的思維方式。講課時間為兩個學(xué)期，第一學(xué)期講授數(shù)理邏輯與集合論，第二學(xué)期講授代數(shù)結(jié)構(gòu)和圖論?？荚噧?nèi)容限于書中的內(nèi)容和難度，但講課內(nèi)容不限于書中的內(nèi)容和難度。二、數(shù)理邏輯發(fā)展史1.目的了解有關(guān)的背景，加深對計算機(jī)學(xué)科的全面了解，特別是理論方面的了解，而不限于將計算機(jī)看成是一門技術(shù)或工程性的學(xué)科。通過重要的歷史事件，了解計算機(jī)科學(xué)中的一些基本思維方式和一些基本問題。2.數(shù)理邏輯的發(fā)展前期前史時期古典形式邏輯時期：亞里斯多德的直言三段論理論初創(chuàng)時期邏輯代數(shù)時期（17世紀(jì)末）資本主義生產(chǎn)力大發(fā)展，自然科學(xué)取得了長足的進(jìn)步，數(shù)學(xué)在認(rèn)識自然、發(fā)展技術(shù)方面起到了相當(dāng)重要的作用。人

3、們希望使用數(shù)學(xué)的方法來研究思維，把思維過程轉(zhuǎn)換為數(shù)學(xué)的計算。萊布尼茲(Leibniz, 16461716)完善三段論，提出了建立數(shù)理邏輯或者說理性演算的思想：提出將推理的正確性化歸于計算，這種演算能使人們的推理不依賴于對推理過程中的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。使用一種符號語言來代替自然語言對演算進(jìn)行描述，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規(guī)律，而與其含義無關(guān)。布爾(G. Boole, 18151864)代數(shù)：將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。3.數(shù)理邏輯的奠基時期弗雷格(G. Frege,

4、 18481925)：概念語言一種按算術(shù)的公式語言構(gòu)成的純思維公式語言(1879)的出版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分命題演算和謂詞演算的正式建立。皮亞諾(Giuseppe Peano, 18581932)：用一種新的方法陳述的算術(shù)原理(1889)提出了自然數(shù)算術(shù)的一個公理系統(tǒng)。羅素(Bertrand Russell, 18721970)：數(shù)學(xué)原理(與懷特黑合著，1910, 1912, 1913)從命題演算和謂詞演算開始，然后通過一元和二元命題函項(xiàng)定義了類和關(guān)系的概念，建立了抽象的類演算和關(guān)系演算。由此出發(fā)，在類型論的基礎(chǔ)上用連續(xù)定義和證明的方式引出了數(shù)學(xué)（主要是算術(shù)）中的主要概念和定理。邏輯演算的

5、發(fā)展：甘岑(G. Gentzen)的自然推理系統(tǒng)(Natural Deduction System)，邏輯演算的元理論：公理的獨(dú)立性、一致性、完全性等。各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis, 18831964)的模態(tài)邏輯，實(shí)質(zhì)蘊(yùn)涵怪論和嚴(yán)格蘊(yùn)涵、相干邏輯等，盧卡西維茨的多值邏輯等。4. 集合論的發(fā)展看待無窮集合的兩種觀點(diǎn)：實(shí)無窮與潛無窮康托爾(G. Cantor, 18451918)：以實(shí)無窮的思想為指導(dǎo)，建立了樸素集合論外延原則（集合由它的元素決定）和概括原則（每一性質(zhì)產(chǎn)生一集合）?？蓴?shù)集和不可數(shù)集，確定無窮集合的本質(zhì)在于集合本身能與其子集一一對應(yīng)。能與正整數(shù)集合對應(yīng)的集合是可數(shù)的

6、，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對角線法證明了實(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é)可從邏輯符號推出，數(shù)學(xué)原理一書是他們這一思想的體現(xiàn)。為解決悖論產(chǎn)生了邏輯類型論。布勞維爾(Brouwer, 18811966)的直覺主義：數(shù)學(xué)是心靈的構(gòu)造，只承認(rèn)可構(gòu)造的數(shù)學(xué)，強(qiáng)調(diào)構(gòu)造的能行性，與計算機(jī)科學(xué)有重要的聯(lián)系。堅持潛無窮，強(qiáng)調(diào)排中律不能用于無窮集合。海丁(H

7、eyting)的直覺主義邏輯。希爾伯特(D. Hilbert)的形式主義：公理化方法與形式化方法，元數(shù)學(xué)和證明論，提倡將邏輯演算和數(shù)學(xué)證明本身形式化，把用普通的語言傳達(dá)的內(nèi)容上的數(shù)學(xué)科學(xué)變?yōu)橛脭?shù)學(xué)符號和邏輯符號按一定法則排列的一堆公式。為了消除悖論，要數(shù)學(xué)建立在公理化基礎(chǔ)上，將各門數(shù)學(xué)形式化，構(gòu)成形式系統(tǒng)，并證明其一致性，這是希爾伯特的數(shù)學(xué)綱領(lǐng)。7.數(shù)理邏輯的發(fā)展初期哥德爾(Godel, 19061978)不完全性定理：一個足夠強(qiáng)大的形式系統(tǒng)，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。各種計算模型：哥德爾的遞歸函數(shù)理論，邱吉爾的演算，圖靈機(jī)模型這

8、些計算模型是計算機(jī)科學(xué)的理論基礎(chǔ)，是計算機(jī)的理論模型。三、預(yù)備知識1.集合的基本概念集合(set)：集合是數(shù)學(xué)中最基本的概念之一，不能以更簡單的概念來定義(define)，只能給出它的描述(description)。一些對象的整體就稱為一個集合，這個整體的每個對象稱為該集合的一個元素(member或element)。用大寫字母A, B, C等表示集合，用小寫字母a, b, c等表示集合的元素aA表示：a是集合A的元素，或說a屬于集合AaA表示：a不是集合A的元素，或說a不屬于集合A集合中的元素是無序的，不重復(fù)的。通常使用兩種方法來給出一個集合：列元素法：列出某集合的所有元素，如：A = 0,

9、1, 2, 3, 4, 5, 6, 7, 8, 9表示所有小于10的自然數(shù)所構(gòu)成的集合B = a, b, , z 表示所有小寫英文字母所構(gòu)成的集合性質(zhì)概括法：使用某個性質(zhì)來概括集合中的元素，如：A = n | n 是小于10的自然數(shù)C = n | n 是質(zhì)數(shù) 表示所有質(zhì)數(shù)所構(gòu)成的集合集合由它的元素所決定，換句話說，兩個集合A和B相等，記為A = B，如果A和B具有相同的元素，即a屬于集合A當(dāng)且僅當(dāng)a屬于集合B。子集(subset)：說集合A是集合B的子集，記為AB，如果a屬于集合A則a也屬于集合B。因此A=B當(dāng)且僅當(dāng)AB且BA。說集合A是集合B的真子集(proper subset)，如果AB且

10、A不等于B(A B)?？占?empty set)：約定存在一個沒有任何元素的集合，稱為空集，記為，有時也用來表示。按子集的定義，空集是任何集合的子集(為什么？)。冪集(power set)：集合A的冪集，記為P(A)，是A的所有子集所構(gòu)成的集合，即：P(A) = B | B A 例如，A = 0, 1，則P(A) = , 0, 1, 0, 1 顯然，對任意集合A，有 P(A)和AP(A)補(bǔ)集(complement set)：集合A的補(bǔ)集，記為A，是那些不屬于集合A的元素所構(gòu)成的集合，即A = x | xA。通常來說，是在存在一個全集U的情況下討論集合的補(bǔ)集。全集U是所討論的問題域中所有元素所構(gòu)

11、成的集合。集合的并(union)：集合A和B的并AB定義為：AB = x | xA或者xB，集合的并可推廣到多個集合，設(shè)A1, A2, , An都是集合，它們的并定義為：A1A2An = x | 存在某個i，使得xAi集合的交(intersection)：集合A和B的并AB定義為：AB = x | xA而且xB，集合的交也可推廣到多個集合，設(shè)A1, A2, , An都是集合，它們的交定義為：A1A2An = x | 對所有的i，都有xAi集合的差(difference)：集合A和B的差A(yù)B定義為：AB = x | xA而且xB。2.關(guān)系和函數(shù)的基本概念有序?qū)?ordered pair)：設(shè)A和

12、B是兩個集合，aA, bB是兩個元素，a和b的有序?qū)?，記為，定義為集合a, a, b。設(shè)和是兩個有序?qū)?，可以證明 = 當(dāng)且僅當(dāng)a1 = a2且b1 = b2。(如何證？)有序?qū)赏茝V到n個元素，設(shè)A1, A2, , An是集合，a1A1, a2A2, , anAn是元素，定義有序n元組(ordered n-tuple)為, an，注意這是一個 HYPERLINK l inductive_def 歸納(inductive)定義，將有序n元組的定義歸結(jié)為有序n-1元組的定義。顯然有 = 當(dāng)且僅當(dāng)a1 = b1且a2 = b2且且an = bn。集合的笛卡爾積(cartesian product)：

13、兩個集合A和B的笛卡爾積AB定義為：AB = | aA且bB例如，設(shè)A = a, b, c，B = 1, 2，則：AB = , , , , , 笛卡爾積可推廣到多個集合的情況，集合A1, A2, , An的笛卡爾積定義為：A1A2An = | a1A1且a2A2且且anAn集合之間的關(guān)系(relation)：定義n個集合A1, A2, , An之間的一個n元關(guān)系R為集合A1, A2, , An的笛卡爾積A1A2An的一個子集。設(shè)A1A2An，若R，則稱a1, a2, , an間具有關(guān)系R，否則稱它們不具有關(guān)系R。特別地：當(dāng)A1 = A2 = = An = A時，稱R為A上的n元關(guān)系。當(dāng)n =

14、2時，有RA1A2，稱R為A1與A2間的一個二元關(guān)系(binary relation)。這時若R則簡記為a1Ra2，否則（即R）記為a1Ra2。通常研究得最多的是二元關(guān)系，n元關(guān)系的許多性質(zhì)可從二元關(guān)系的性質(zhì)擴(kuò)充而得到。如果沒有特別指明的話，說R是一個關(guān)系則是指R是一個二元關(guān)系。當(dāng)n = 1時，這時可認(rèn)為R是集合A上滿足某種性質(zhì)的子集。關(guān)系的一些性質(zhì)：設(shè)R是A上的二元關(guān)系：說R是自反的(reflexive)，如果對任意的aA有aRa。說R是反自反的(irreflexive)，如果對任意的aA有aRa。說R是對稱的(symmetric)，如果對任意的a, bA有若aRb則bRa。 說R是反對稱的

15、(antisymmetric)，如果對任意的a, bA有若aRb且bRa則a = b。說R是傳遞的(transitive)，如果對任意的a, b, c A有若aRb且bRc則aRc。說R是等價關(guān)系(equivalence)，如果R是自反的、對稱的和傳遞的。集合之間的函數(shù)(function，或說映射mapping)：定義集合A到B的函數(shù)f是A和B的笛卡爾積AB的一個子集，且滿足若f及f則y = z。因此函數(shù)是A和B之間的一個特殊的二元關(guān)系。通常記集合A到B的函數(shù)f為f : AB。函數(shù)f : AB的定義域(domain)dom(f )定義為：dom(f ) = x | 存在某個yB使得f 函數(shù)f

16、: AB的值域(range)ran(f )定義為：ran(f ) = y | 存在某個xA使得f 若f，通常記y為f(x)，并稱y為x在函數(shù)f下的像(image)，x為y在函數(shù)f下的原像。函數(shù)也可推廣到n元的情形：f : A1A2AnB，意味著：f是A1A2AnB的一個子集，且 f且 f則y = z。函數(shù)的一些性質(zhì)：設(shè)f : AB是集合A到B的函數(shù)：說f是全函數(shù)(total function)，若dom(f )=A，否則稱f是偏函數(shù)(partial function)。下面如果沒有特別指明的話，都是指全函數(shù)。說f是滿射(surjection, 或說f maps A onto B)，如果ran(

17、f ) = B，即對任意的yB都有原像。說f是單射(injection，或說f is one-one)，如果有f (x1) = f(x2)則x1 = x2，即對任意的yB，如果它有原像的話，則有唯一的原像。說f是雙射(bijection，或說f是一一對應(yīng))，如果f既是滿射，又是單射，即對任意的yB，都有唯一的原像，同樣根據(jù)全函數(shù)的定義，對于任意xA都有唯一的像。這時可以定義f的逆函數(shù)(inverse function)，記為f -1 : BA，f -1(y) = x當(dāng)且僅當(dāng)f(x) = y。顯然f -1也是雙射。集合的基數(shù)(cardinal number)或說勢：集合A的基數(shù)記為|A|，且有：

18、對于有限集合A，令A(yù)的基數(shù)為A中元素的個數(shù)。定義無限集合，不直接定義基數(shù)，而是通過定義兩個集合之間的等勢關(guān)系來刻劃集合的基數(shù)或勢，說集合A和集合B是等勢的(equipotent)，如果存在一個從A到B的雙射。根據(jù)雙射的性質(zhì)，可以證明等勢是集合上的一個等價關(guān)系。稱與自然數(shù)集等勢的集合為可列集(enumerable)，有限集和可列集統(tǒng)稱為可數(shù)集(countable)。設(shè)A和B是有限集合，有|P(A)| = 2|A|，|AB| = |A| |B|。3.小結(jié)下面以樹的形式給出了以上主要概念之間的關(guān)系： HYPERLINK l set 集合 HYPERLINK l subset 子集 HYPERLINK

19、 l complement 集合的補(bǔ)、并、交、差 HYPERLINK l ordered_pair 有序?qū)?HYPERLINK l power_set 冪集 HYPERLINK l product 笛卡爾積 HYPERLINK l relation 關(guān)系 HYPERLINK l relation_prop 關(guān)系的自反、對稱、傳遞性 HYPERLINK l function 函數(shù) HYPERLINK l function_prop 單射、滿射、雙射4.歸納定義和歸納證明一個集合的歸納定義(inductive definition)通常分為三步：歸納基：一些基本的元素屬于該集合；歸納步：定義一些規(guī)

20、則（或者說操作），從該集合中已有的元素來生成該集合的新的元素；最小化：該集合中的所有元素都是通過基本元素以及所定義的規(guī)則生成的，換句話說，該集合是由基本元素及規(guī)則所生成的最小的集合。自然數(shù)集N的歸納定義：1.歸納基：0是一個自然數(shù)，即0 N。2.歸納步：若n是自然數(shù)，則n的后繼也是自然數(shù)。記n的后繼為succ(n)，即若nN，則succ(n)N。為方便起見，后面也記n的后繼為n+1。3.最小化：所有的自然都通過步驟1和2得到，或者說自然數(shù)集是通過步驟1和2得到的最小集合。這種定義方式可推廣到對其他一些概念的定義，例如上述多個集合的 HYPERLINK l union 并、 HYPERLINK

21、l intersection 交、 HYPERLINK l n_product 笛卡爾積以及多個元素的 HYPERLINK l n_tuple 有序n元組都可通過遞歸的方式定義。例如，對于多個集合的并可定義為：歸納基：A1A2 = x | xA1或者xA2歸納步：A1A2An = (A1A2An-1) An這里不需要最小化，因?yàn)檫@里不是定義集合。數(shù)學(xué)歸納法：關(guān)于自然數(shù)的許多性質(zhì)都可通過數(shù)學(xué)歸納法來證明，對于性質(zhì)R，如果它對0成立，而且如果對于n成立的話，能夠得到它對于n+1也成立，那么性質(zhì)R對所有的自然數(shù)成立。這種證明方法的正確性本身可通過自然數(shù)的歸納定義來得到證明：定義集合S = nN |

22、性質(zhì)R對n成立歸納基：根據(jù)上面的定義有0S歸納步：根據(jù)上面的定義有如果nS，則n+1S，所以S是滿足上面 HYPERLINK l inductive_N_set 自然數(shù)集的歸納定義中的1、2點(diǎn)的一個集合，而自然數(shù)集N是滿足這兩點(diǎn)的最小集合，所以有N S，而顯然有SN，所以S = N。數(shù)學(xué)歸納法舉例：使用數(shù)學(xué)歸納法證明1 + 2 + + n = (n * (n+1)/2歸納基：當(dāng)n = 0時顯然成立。歸納步：如果對于n成立，則有1 + 2 + + n = (n * (n+1)/2（這稱為歸納假設(shè)），現(xiàn)在要證對于n+1也成立。顯然有：1 + 2 + + n + (n + 1) = (n * (n+

23、1)/2 + (n+1) / 根據(jù)歸納假設(shè)= (n * (n+1) + 2 * (n+1)/2 = (n+1) * (n+1) + 1)/2因此要證的公式對于n+1成立，所以對于所有的自然數(shù)成立。顯然在數(shù)學(xué)歸納法中，對于歸納基改為R對于自然數(shù)k成立，歸納步不變的話，則可證明R對于所有大于k的自然數(shù)都成立。在數(shù)學(xué)歸納法中，也可將歸納步改為如果R對于所有小于n的自然數(shù)成立，則推出R對于n也成立，即歸納步是假設(shè)對于所有小于n的自然數(shù)性質(zhì)R成立來導(dǎo)出性質(zhì)R對于自然數(shù)n成立。這種形式的數(shù)學(xué)歸納法通常稱為第二數(shù)學(xué)歸納法。5.形式系統(tǒng)形式系統(tǒng)的定義：一個形式系統(tǒng)S由下列4個集合構(gòu)成：一個非空集合S，稱為形式

24、系統(tǒng)S的字母表或說符號(Symbol)表；一個由S中字母的有限序列（字符串）所構(gòu)成的集合FS，稱為形式系統(tǒng)S的公式(Formula)集；從FS中選取一個子集AS，稱為形式系統(tǒng)S的公理(Axiom)集；FS上有一個部分函數(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)

25、也是形式系統(tǒng)S中的定理。對于形式系統(tǒng)中的規(guī)則Rn : FS FS FS FS，通常表示成下面的形式：t1, t2, , tnRn(t1, t2, , tn)形式系統(tǒng)具有兩個特征：形式化實(shí)際上是一個可機(jī)械實(shí)現(xiàn)的過程，在它里面，符號、規(guī)則和演算等被表示得嚴(yán)密、精確。在形式系統(tǒng)S中，只能使用字母表S中的符號，只承認(rèn)公式集FS中的符號串的合理性，只能由公理集，根據(jù)規(guī)則推出有意義的東西來。形式系統(tǒng)一旦完成，就成了符號串及根據(jù)規(guī)則進(jìn)行的符號串的改寫，系統(tǒng)與一切實(shí)際意義就毫不相干，或者說已經(jīng)通過這種符號，從實(shí)際問題中抽象出了我們所需要研究的內(nèi)容。在形式系統(tǒng)內(nèi)部，所能認(rèn)識的只能是符號串及其改寫，只能在形式系統(tǒng)

26、外對這種符號串及規(guī)則賦予意義。對象語言(Object language)與元語言(Meta language)：數(shù)理邏輯所研究的是“數(shù)學(xué)推理”，而使用的方法也是數(shù)學(xué)推理，所以有必要區(qū)分這兩個層次的推理。把作為研究對象的“推理”形式化，使用形式語言來表示作為研究對象的“推理”的前提、結(jié)論和規(guī)則等，這種形式語言是我們所研究的對象語言。另一方面，關(guān)于形式系統(tǒng)的性質(zhì)、規(guī)律的表達(dá)和作為研究方面的推理方式使用另一種語言來表達(dá)，這個語言稱為研究的元語言，通常使用半數(shù)學(xué)化的自然語言。形式語言的語法(Syntax)與語義(Semantic)：形式語言的語法是構(gòu)成形式系統(tǒng)的公式集、公理集和規(guī)則集的法則。形式語言的

27、語義是關(guān)于形式系統(tǒng)的解釋和意思。形式語言本身沒有含義，但我們在構(gòu)造它們時是假想它們能代表某種意義的，特別的當(dāng)我們在選擇形式系統(tǒng)的公理時，總是選擇所研究的問題域中那些最為明顯或最容易公認(rèn)為正確的性質(zhì)。6.習(xí)題1.令集合A = n | n 10且n 是奇數(shù)，B = n | n 10且n是素數(shù)，請回答下列問題：a)請用列元素的方法列出集合A和集合B，請問集合B是否是集合A的子集？b)請計算AB、AB、AB、AB以及P(A)(即A的冪集)。2.設(shè)關(guān)系R = | a和b是互質(zhì)的自然數(shù)，請問R是自反的嗎？對稱的嗎？傳遞的嗎？為什么？3.設(shè)f : AB是函數(shù)，R是A上的如下二元關(guān)系：R = | a, bA,

28、 f (a) = f (b) ，證明R是A上的一個等價關(guān)系。4.使用數(shù)學(xué)歸納法證明：12 + 22 + 32 + + n2 = (n * (n + 1) * (2n + 1) / 65.設(shè)有函數(shù)f : NN N，f(n) = ，請問f是不是單射、滿射或雙射？*6.設(shè)R1和R2都是A上的等價關(guān)系，請問R1R2和R1R2是否還是A上的等價關(guān)系？如果是請證明，否則請舉一反例。*7.設(shè)R是集合A上的等價關(guān)系，aA，可定義：a)a = bA | aRb ，稱a為a關(guān)于R的等價類；b)A/R = a | aA，稱A關(guān)于R的商集。設(shè)函數(shù)f : AA/R定義為對任意aA有f(a) = a，請問R滿足怎樣的條件

29、時f是單射？*8請給出的集合方式的定義。若定義：x, y, z = x, x, y, x, y, z，則如果有x1, y1, z1 = x2, y2, z2是否意味著有x1 = x2且y1 = y2且z1 = z2？第二講數(shù)理邏輯一、命題邏輯(Propositional Logic)1.內(nèi)容概述簡單命題與復(fù)合命題：什么是命題？命題聯(lián)結(jié)詞及其含義。命題公式與賦值：命題邏輯公式的歸納定義，命題公式的真值表。等值演算：命題公式的等值賦值，重要的等值式。命題聯(lián)結(jié)詞的完備集：通過等值演算得到命題聯(lián)結(jié)詞的完備集和極小完備集。命題公式的范式：析取范式與合取范式。命題演算系統(tǒng)：使用命題邏輯公式進(jìn)行推理的形式系

30、統(tǒng)。命題演算系統(tǒng)的語義與命題演算系統(tǒng)的元性質(zhì)：注意區(qū)別形式系統(tǒng)的語法和語義。2.簡單命題與復(fù)合命題命題(proposition)：經(jīng)典命題邏輯中，稱能判斷真假但不能既真又假的陳述句為命題。命題對于命題邏輯來說是一個原始的概念，不能在命題邏輯的范圍內(nèi)給出它的精確定義，只能描述它的性質(zhì)。命題必須為陳述句，不能為疑問句、祈使句、感嘆句等，例如下述句子為命題：1.3 是有理數(shù)2.8小于103.2是素數(shù)4.烏鴉是黑色的下列句子不是命題：1.這個小男孩多勇敢?。?.烏鴉是黑色的嗎？3.但愿中國隊(duì)能取勝。4.請把門開一開！下列句子不可能判斷其為真或?yàn)榧伲砸膊皇敲}：1.x + y 102.我正在撒謊命題

31、必須具有真假值，從某種意義上來說，疑問句、祈使句、感嘆句沒有真假之分。但能判斷真假，并不意味著現(xiàn)在就能確定其是真還是假，只要它具有能夠唯一確定的真假值即可，例如下述陳述句是命題：1.明年的中秋節(jié)的晚上是晴天2.地球外的星球上存在生物3.21世紀(jì)末，人類將居住在太空4.哥德巴赫猜想是正確的經(jīng)典命題邏輯不區(qū)分現(xiàn)在已確定為真，還是將來可能確定為真這種情況，處理與時間有關(guān)的真值問題是時態(tài)邏輯的任務(wù)。經(jīng)典命題邏輯也不區(qū)分是在技術(shù)上可以確定為真，還是現(xiàn)在的技術(shù)條件下不可以確定為真的這種情況，只承認(rèn)在技術(shù)上，或者說能給出某種方法確定為真的那些東西才為真是直覺邏輯的觀點(diǎn)。真命題和假命題：命題是為真或?yàn)榧俚年愂?/p>

32、句，稱這種真假的結(jié)果為命題的真值。如果命題的真值為真，則稱為真命題，否則稱為假命題。命題常量與命題變量：使用符號來表示命題，通常用p, q或帶下標(biāo)來表示命題常量或者變量。如果命題符號p代表命題常量則意味它是某個具體命題的符號化，如果p代表命題變量則意味著它可指代任何具體命題。如果沒有特別指明，通常來說命題符號p等是命題變量，即可指代任何命題。簡單命題與復(fù)合命題：不能分成更簡單的陳述句的命題為簡單命題或原子命題，否則稱為復(fù)合命題，復(fù)合命題使用命題聯(lián)結(jié)詞聯(lián)結(jié)簡單命題而得到。復(fù)合命題的聯(lián)結(jié)詞通常包括：設(shè)p是任意命題，復(fù)合命題“非p”稱為p的否定（非），記為 p。設(shè)p和q是任意命題，復(fù)合命題“p且q”

33、稱為p和q的合?。ㄅc），記為pq。設(shè)p和q是任意命題，復(fù)合命題“p或q”稱為p和q的析?。ɑ颍?，記為pq。設(shè)p和q是任意命題，復(fù)合命題“如果p則q”稱為p蘊(yùn)涵q，記為pq。設(shè)p和q是任意命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱為p與q等價，記為pq。上述定義中的非(negation)、合取(conjunction)、析取(disjunction)、蘊(yùn)涵(implication)和等價(equivalence)是在命題邏輯中的術(shù)語，而引號中給出的復(fù)合命題是自然語言中的典型用法。當(dāng)然，命題邏輯中符號化形式的復(fù)合命題在自然語言中有許許多多的表達(dá)方法，這也是為什么自然語言有歧義的原因，參見教材中的各例題，并注

34、意以下幾點(diǎn)：pq的邏輯關(guān)系是pq為真當(dāng)且僅當(dāng)p和q中至少有一個為真。但自然語言中的“或”既可能具有相容性，也可能具有排斥性。命題邏輯中采用了“或”的相容性。pq的邏輯關(guān)系是pq為假當(dāng)且僅當(dāng)p為真，而q為假，稱p為蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件。現(xiàn)實(shí)世界中的“如果則”與這種蘊(yùn)涵有比較大的區(qū)別。簡單命題邏輯中的這種蘊(yùn)涵常常稱為“實(shí)質(zhì)蘊(yùn)涵”，相對應(yīng)地有“嚴(yán)格蘊(yùn)涵（p嚴(yán)格蘊(yùn)涵q，意味著p為真，則q不可能為假）”、“相干蘊(yùn)涵”等。實(shí)質(zhì)蘊(yùn)涵意味著可從假的前提推出任何命題來，或兩個不沒有內(nèi)在聯(lián)系的命題之間存在蘊(yùn)涵關(guān)系。將日常生活中的陳述句符號化為命題邏輯中的公式是在今后的程序編寫等課程中應(yīng)用數(shù)理邏輯知識的重

35、要基礎(chǔ)。但就數(shù)理邏輯這門課程本身而言，我們只關(guān)心公式之間的真值關(guān)系，而不關(guān)心公式所具體指代的命題。復(fù)合命題與簡單命題之間的真值關(guān)系可用下表給出，其中0代表假，1代表真：pq ppqpqpqpq00100110110110100010011011113.命題邏輯公式【定義1.1】命題邏輯公式(propositional logic formula)由以下子句歸納定義：1.歸納基：命題常量或命題變量是命題邏輯公式，稱為命題邏輯公式的原子項(xiàng)。2.歸納步：如果A, B是邏輯公式，則(A)、(AB)、(AB)、(AB)和(AB)也是命題邏輯公式。3.最小化：所有的命題邏輯公式都通過1和2得到。在這里我們

36、隱含地使用的字母表是大小寫的英文字母、命題聯(lián)結(jié)符和園括號。英文字母還可帶下標(biāo)。其它的符號都不屬于我們的符號表，即在命題邏輯公式中不能出現(xiàn)這些符號。后面我們將命題邏輯公式簡稱為命題公式，或在沒有二義的情況下進(jìn)一步簡稱為公式?！纠?.1】(p q) (p) (q r)是命題公式，它通過以下步驟生成：1.p是公式；/ 根據(jù)定義1.1的12.q是公式；/ 根據(jù)定義1.1的13.(p q)是公式；/ 根據(jù)定義1.1的24.(p)是公式；/ 根據(jù)定義1.1的25.r是公式；/ 根據(jù)定義1.1的16.(q r)是公式；/ 根據(jù)定義1.1的27.(p) (q r)是公式；/ 根據(jù)定義1.1的2，以及4, 6

37、8.(p q) (p) (q r)是公式。/ 根據(jù)定義1.1的2，以及3, 7這種生成過程，可以形象地用下面的一棵樹來表示： (p q) (p) (q r) (p q) (p) (q r) p q (p) (q r) p q r這種樹在形式語言與自動機(jī)中就稱為語法分析樹?！痉蠢?.2】根據(jù)定義1.1，p q不是公式，因?yàn)閮蛇厸]有園括號根據(jù)定義1.1，(p q r)不是公式，實(shí)際上，由定義1.1生成的公式，每個命題聯(lián)結(jié)符都會對應(yīng)一對園括號。顯然(pqr)、(q(rp)等都不是公式?！径ɡ?.2】設(shè)R是某個性質(zhì)，如果有：1.對于所有的原子項(xiàng)p，都滿足性質(zhì)R；2.如果對任意的公式A和B都滿足性質(zhì)R，

38、就有(A)、(AB)、(AB)、(AB)和(AB)也滿足性質(zhì)R。那么，所有的公式A就都滿足性質(zhì)R。該定理的證明類似數(shù)學(xué)歸納法的證明，很容易根據(jù)定義1.1得到?！径x1.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，其中*代表、之一。此定義等價于教材p11的定義1.7。只不過我們在這里給出的是遞歸定義。使用歸納法，我們可證明下面定理：【定理1.4】deg(A)小于等于命題公式A中的命題聯(lián)結(jié)符號的數(shù)目?！咀C明】根據(jù)命題公式A的結(jié)構(gòu)進(jìn)行歸納

39、證明：1.歸納基：如果A是原子項(xiàng)，則根據(jù)定義1.3有deg(A) = 0，顯然定理成立。2.歸納步：假設(shè)定理對于命題公式A和B成立（歸納假設(shè)），記命題公式A中的命題聯(lián)結(jié)符號數(shù)為Sym(A)，即有deg(A) Sym(A)和deg(B) Sym(B)。那么由于deg(A) = deg(A) + 1，而Sym(A) = Sym(A) + 1，所以定理對于A也成立。同樣由于deg(A * B) = max(deg(A), deg(B) + 1，而Sym(A * B) = Sym(A) + Sym(B) + 1，因而有deg(A * B) Sym(A * B)，從而定理對所有的命題公式都成立?！径ɡ?

40、.5】任意命題邏輯公式A中出現(xiàn)相等數(shù)目的左右園括號，實(shí)際上，左右園括號的個數(shù)都等于A中的命題聯(lián)結(jié)符號數(shù)?！径ɡ?.6】任意命題邏輯公式A具有下列6種形式之一，且只具有其中一種形式：1.A為原子項(xiàng)；2.(A)3.(AB)4.(AB)5.(AB)6.(AB)定理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í)際上每個命題公式的

41、最左邊都是左園括號，如果從第二個符號不是左園括號，那么這個公式只有一個命題聯(lián)結(jié)符。否則找與第二個左園括號配對的右園括號，從而將命題公式劃分為這樣的形式：() * ()，如果原來的命題公式為根的話，那么左右兩邊的兩個命題公式分別為它的左右子樹了，而且對這兩個公式可作類似的分析，最后到原子項(xiàng)。在后面，為了書寫方便起見，我們省略最外邊的括號，并規(guī)定各個命題聯(lián)結(jié)符的優(yōu)先級別為大于，大于，大于，大于，從而可省略命題公式中一些不必要的園括號，例如例子1.1中的公式可寫為：p q p q r。不過在后面我們書寫公式的原則是盡量簡便，但又能讓讀者容易理解。而有關(guān)命題公式的性質(zhì)的討論，則只針對可由上面定義1.1

42、所能生成的公式形式。上面討論的命題公式的語法結(jié)構(gòu)，下面討論命題公式的賦值?！径x1.7】 對命題公式的一次真值賦值t是從所有命題變量所組成的集合到集合0, 1的函數(shù)。實(shí)際上，對于某個命題公式A來說，我們只關(guān)心t在A中的命題變量上的值。這里我們假定存在一個所有命題變量所組成的集合U，或者說我們所有命題公式中的變量都取之于集合U，我們記命題公式A中的所有命題變量所組成的集合為Var(A)。設(shè)有一個真值賦值t : U0, 1，而對于命題公式A的真值賦值來說，我們只關(guān)心t在Var(A)上的值?！纠?.3】對于命題公式A = (p q) (p) (q r)，有：Var(A) = p, q, r這里不妨

43、假定U = Var(A)，真值賦值就是一個函數(shù)t : p, q, r0, 1，例如可令：t(p) = 0, t(q) = 1, t(r) = 0【定義1.8】命題公式A在真值賦值t : U0, 1下的真值t(A)遞歸定義如下：1.如果命題公式A是一個命題常量p，則如果p為真，t(A) = 1，否則t(A) = 0；2.如果命題公式A是一個命題變量p，則t(A) = t(p)3.若t(A) = 0則t(A) = 1，否則t(A) = 0。4.若t(A) = t(B) = 1，則t(AB) = 1，否則t(AB) = 0。5.若t(A) = t(B) = 0，則t(AB) = 0，否則t(AB)

44、= 1。6.若t(A) = 0或者t(B) = 1，則t(AB) = 1，否則t(AB) = 0。7.若t(A) = t(B)，則t(AB) = 1，否則t(AB) = 0。【例子1.3，續(xù)】對于命題公式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的54.t(p) = 1;/ 根據(jù)定義1.8的35.t(r) = 0;6.t(q r) = 0;/ 根據(jù)定義1.8的47.t(p) (q r) = 0;/ 根據(jù)定義1.8的78.t(p q)

45、(p) (q r) = 0;/ 根據(jù)定義1.8的6因此命題公式A在上述真值賦值下的真值t(A)是0。不難看出，定義1.8與上一節(jié)中給出的復(fù)合命題與簡單命題之間的真值關(guān)系表是一致的。而且從上面的例子與例1.1的比較也可看出，對于命題公式的真值，可根據(jù)該命題公式的生成步驟來得到。命題公式的真值只與命題公式中所出現(xiàn)的命題變量的真值賦值有關(guān)，如果命題公式中含有n個命題變量，則對這些命題變量的真值賦值共有2n種不同情況，可通過一個表，列出在這所有情況下命題公式的真值，這種表稱為該命題公式的真值表，例如上述命題公式A的真值表為：pqr(pq)(p)(qr)(p)(qr)(pq) (p)(qr)000010

46、0100101001010110000111111110010011101100111101001111110100【定義1.9】如果命題公式A在任意的真值賦值函數(shù)t : U0, 1下的真值t(A)都為1,則稱命題公式A為永真式(tautology)（或稱重言式）；如果命題共A在任意的真值賦值函數(shù)下的真值都為0，則稱A為矛盾式(contradiction)；如果A不是矛盾式，則稱為可滿足式?！纠?.4】根據(jù)命題公式A = (p q) (p) (q r)的真值表，我們知該命題公式是可滿足式，但不是永真式。而公式B = (p(qp)r)是永真式，其真值表為：pqr(qp)(p(qp)(p(qp)

47、r)000011001011010111011111100111101111110111111111而公式(pq)q)r)（教材14頁簡寫為(pq)qr）是矛盾式，其真值表為：pqr(pq)(pq)(pq)q)(pq)q)r)00010000011000010100001110001000100101010011010001111000【定義1.10】我們使用符號來表示一組命題公式所構(gòu)成的集合。定義在真值賦值函數(shù)t : U0, 1下的真值t()為：t() = 1當(dāng)且僅當(dāng)對中任意公式A有t(A) = 1，否則定義t() = 0(注意只要中存在某個公式A使得t(A) = 0，就有t() = 0)。

48、說是可滿足的，如果存在某個真值賦值函數(shù)t使得t() = 1，這時稱t滿足。【定義1.11】設(shè)是一組命題公式的集合，說命題公式A是以為前提的永真式，如果滿足對任意滿足的真值賦值函數(shù)t都有t(A) = 1，這時我們記為A。注意在定義1.11中，如果為空集，則A表示A為永真式，因?yàn)閷τ诳占瘉碚f，顯然任意的真值賦值函數(shù)t都滿足它（因?yàn)橹袥]有命題公式），從而A意味著對任意的真值賦值函數(shù)t都有t(A) = 1，即A為永真式。4.等值演算【定義1.12】當(dāng) = A1, A2, , An時，我們也記A為A1, A2, , AnA。如果有AB且BA，則稱命題公式A與B等值，記為AB。實(shí)際上公式A與B等值記為AB

49、會更準(zhǔn)確些，但教材采用了符號AB，為了不會過于混淆，我們也使用這種記號。實(shí)際上，根據(jù)定義1.11，AB就意味著對任意的真值賦值函數(shù)t有t(A) = 1當(dāng)且僅當(dāng)t(B) = 1，也就是說對任意的t有t(A) = t(B)。從而定義1.12與教材中關(guān)于命題公式等值的定義是等價的，即有下述定理：【定理1.13】AB當(dāng)且僅當(dāng)AB是永真式。使用真值表，不難證明下面的定理：【定理1.14】設(shè)A, B, C是任意的命題公式，有：1.雙重否定律：A (A)2.等冪律：A(AA)A(AA)3.交換律：(AB) (BA)(AB) (BA)4.結(jié)合律：(AB)B) (A(BB)(AB)B) (A(BB)5.分配律：

50、(A(BC) (AB)(AC)(A(BC) (AB)(AC)6.德摩根律：(AB) (A)(B)(AB) (A)(B)7.吸收律：(A(AB) A(A(AB) A8.零律：(A1) 1(A0) 09.同一律：(A 0) A(A1) A10.排中律：(A(A) 111.矛盾律：(A(A) 012.蘊(yùn)涵等值式：(AB) (A)B)13.等價等值式：(AB) (AB)(BA)14.假言易位：(AB) (B)(A)15.等價否定等值式：(AB) (A)(B)16.歸謬論：(AB)(A(B) (A)要注意的是，上述定理中的0代表真值為0的任意命題常量，而1代表真值為1的任意命題常量。由于命題聯(lián)結(jié)符號和都

51、滿足結(jié)合律，因此我們可有如下的簡寫：A1A2AnA1A2An根據(jù)以上簡寫，我們可推廣 HYPERLINK l theorem_1_13 定理1.13為以下定理1.15：【定理1.15】1.A1, A2, , AnA當(dāng)且僅當(dāng)(A1A2An)A)。2.A1, A2, , AnA當(dāng)且僅當(dāng)(A1(A2(AnA)?！疽?.16】設(shè)有AA和BB，則有：1.(A)(A)2.(AB)(AB)3.(AB)(AB)4.(AB)(AB)5.(AB)(AB)根據(jù)引理1.16，不難證明下面的置換規(guī)則：【定理1.17】設(shè)有BC，而A是命題公式A通過使用C替換A中出現(xiàn)的某些B（不需要是替換所有的B）而得到的命題公式，則有

52、AA。【證明】對命題公式A的結(jié)構(gòu)進(jìn)行歸納。首先如果B = A，則有C = A，從而有AA。歸納基：如果A是命題變量和命題常量，那么必有B = A，因此定理成立。歸納步：根據(jù) HYPERLINK l theorem_1_6 定理1.6，命題公式A必為如下5種形式之一：A1, A1A2, A1A2, A1A2, A1A2。設(shè)A的形式為A1，如果B = A則定理成立，否則必有B出現(xiàn)A1中，將A1中的B用C替換后得到的為A1，按歸納假設(shè)有A1 = A1，再根據(jù)引理1.15有A1 = A1。定理成立。若A的形式為A1 * A2，則如果B = A則定理成立，否則必有B出現(xiàn)在A1或A2中，或同時出現(xiàn)在這兩者

53、中。設(shè)將A1中的B用C替換后得到的為A1，而將A2中的B用C替換后得到的為A2，按歸納假設(shè)有A1A1和A2 A2，再根據(jù)引理1.15有A1*A2A1*A2，即定理成立?！径x1.18】如果命題公式A中只出現(xiàn)命題變量、命題常量、命題聯(lián)結(jié)符號、和則稱為限制性（命題）公式。定義：1.對于限制性公式A，將其中的命題聯(lián)結(jié)符號換成，命題聯(lián)結(jié)符號換成得到的公式稱為A的對偶公式(dual formula)，記為Aop。2.對于限制性公式A，將其中出現(xiàn)的所有原子項(xiàng)（命題變量或命題常量）p換成p得到的公式稱為A的內(nèi)否式，記為A?！纠?.5】設(shè)公式A = (pq)(r)，則：(1).A的對偶式Aop = (pq)

54、(r)(2).A的內(nèi)否式A = (p) (q) r)【引理1.19】設(shè)公式A、B都是限制性公式，有：1.(Aop)op A(A) A2.(A B)op Aop Bop(A B) A B3.(A B)op Aop Bop(A B) A B4.(Aop) (A)op引理1.19中的(恒等號)表示兩邊的公式在（語法）形式上完全一樣，例如(Aop)op A表示對A的對偶公式Aop再做一次對偶操作得到的就是A本身。而(Aop) (A)op表示對A做一次對偶操作得到Aop，然后再求Aop的內(nèi)否式，得到的公式與先求A的內(nèi)否式，然后再做對偶操作得到的公式完全一樣，用代數(shù)學(xué)的術(shù)語來說，就是這兩種操作可交換。引理

55、1.19很容易根據(jù)定義1.18證明，也可直觀理解引理1.19所代表的含義。讀者可通過對一些公式求它的對偶式和內(nèi)否式來驗(yàn)證引理1.19的每個恒等式，例如：【例子1.5，續(xù)】設(shè)公式A = (pq)(r)，則：(1).Aop = (pq)(r), (Aop) = (p)(q) r)(2).A = (p) (q) r), (A)op = (p) (q) r)顯然有(Aop) (A)op?！径ɡ?.20】設(shè)公式A是任意的限制性公式，有：1.(A)op (Aop)(A) (A)2.(Aop) A【證明】略【推論1.21】設(shè)公式A和B都是限制性公式，有A B則(Aop) (Bop)【證明】根據(jù)引理1.16及

56、(A) A不難得到A B當(dāng)且僅當(dāng)A B。則：(Aop) A B (Bop)在 HYPERLINK l theorem_1_14 定理1.14中已經(jīng)看到了推論1.21的許多佐證，例如對于吸收律(A(AB) A，其中(A(AB)的對偶公式是(A(AB)，從而有(A(AB) A，這與第二個吸收律公式(A(AB) A是相同的，因?yàn)锳、B代表任意命題公式。【例子1.6】驗(yàn)證下列等值式(1).(pq)r) (qp)r)(2).(p(qr) (pq)r)(3).(pq)r) (pr)(qr)(4).(pq)r) (pr)(qr)(5).(p(qr) (pq)(pr)(6).(p(qr) (pq)(pr)【證

57、明】證明的思路有兩種，第一種思路是通過列真值表，可看到上述等值式的兩邊在任何真值賦值下都有相同的真值，從而完成上述等值式的驗(yàn)證。讀者不妨自己按照這種思路進(jìn)行證明。第二種思路是利用 HYPERLINK l theorem_1_14 定理1.14中的基本等值式來證明?？梢钥吹缴鲜龅戎凳街饕顷P(guān)于蘊(yùn)涵的等值式，證明關(guān)于蘊(yùn)涵的等值式的方法是利用定理1.14中的12將蘊(yùn)涵化成只出現(xiàn)與、或、非的公式，再來驗(yàn)證它們的相等。(1).(pq)r) (pq)r) / 定理1.14中的12：蘊(yùn)涵等值式 (pq)r/ 定理1.14中的12：蘊(yùn)涵等值式 (p(q)r/ 德摩爾根律 (qp)r)/ 的交換律(2).(p(

58、qr) (p(qr)/ 蘊(yùn)涵等值式 (p(qr)/ 蘊(yùn)涵等值式 (pq)r)/ 的結(jié)合律 (pq)r)/ 德摩爾根律，反向運(yùn)用 (pq)r)/ 蘊(yùn)涵等值式，反向運(yùn)用(3).(pq)r) (pq)r)/ 蘊(yùn)涵等值式 (pq)r)/ 德摩爾根律 (pr)(qr)/ 分配律與交換律 (pr)(qr)/ 蘊(yùn)涵等值式(5).(p(qr) (p)(qr)/ 蘊(yùn)涵等值式 (p)(p)(qr)/ 的冪等律 (pq)(pr)/ 的交換律和結(jié)合律 (pq)(pr)/ 蘊(yùn)涵等值式(4)(6)留作練習(xí)【例子1.7】德摩爾根律的推廣：(1).(A1A2An) (A1)(A2)(An)(2).(A1A2An) (A1)(

59、A2)(An)【證明】對n實(shí)施數(shù)學(xué)歸納法，或直接從定理1.202得到。5. 聯(lián)結(jié)詞的完全集【定義1.22】0, 1上的n元函數(shù)f : 0, 1n0, 1就稱為一個n元真值函數(shù)。聯(lián)結(jié)詞實(shí)際上一個一元真值函數(shù)：f(0) = 1, f(1) = 0而聯(lián)結(jié)詞、和則都是二元真值函數(shù)：f(0, 0) = 0, f(0, 1) = 0, f(1, 0) = 0, f(1, 1) = 1f(0, 0) = 0, f(0, 1) = 1, f(1, 0) = 1, f(1, 1) = 1f(0, 0) = 1, f(0, 1) = 1, f(1, 0) = 0, f(1, 1) = 1f(0, 0) = 1,

60、f(0, 1) = 0, f(1, 0) = 0, f(1, 1) = 1反過來，一個真值函數(shù)就可看成一個真值聯(lián)結(jié)詞。設(shè)f : 0, 1n0, 1是一個n元真值函數(shù)，則可如下定義一個n元真值聯(lián)結(jié)詞Nf : 對于n個命題變元p1, p2, , pn，命題公式Nf(p1, p2, , pn)在真值賦值函數(shù)下的真值為f(t1, t2, , tn)。顯然互不相同的n元真值函數(shù)的個數(shù)為22n，因此可定義22n個n元真值聯(lián)結(jié)詞，例如1元真值函數(shù)有四個：f1: 00, 10f2: 00, 11f3: 01, 10f4: 01, 11而2元真值函數(shù)有16個，可定義16個真值聯(lián)結(jié)詞，而我們常用的只不過是其中的4