1、6/18/20201:15AM,Zll-sci.hhu,1,主講：張麗麗,數(shù)理邏輯,河海大學(xué)計(jì)信學(xué)院,E-mail:lilzhang,6/18/20201:15AM,Zll-sci.hhu,2,教材：數(shù)理邏輯與集合論石純一,王家厥，清華大學(xué)出版社,6/18/20201:15AM,Zll-sci.hhu,3,參考教材,數(shù)理邏輯引論（王憲鈞）數(shù)理邏輯基礎(chǔ)（胡世華，陸鐘萬(wàn)）計(jì)算機(jī)科學(xué)中的現(xiàn)代邏輯學(xué)（王元元，科學(xué)出版社）離散數(shù)學(xué)（左孝琳、李為檻、劉永才，上?？萍嘉墨I(xiàn)版）,6/18/20201:15AM,Zll-sci.hhu,4,教學(xué)內(nèi)容:,主要講授數(shù)理邏輯部分的1-7章集合論的部分知識(shí)屬于拓寬知識(shí)面

2、,6/18/20201:15AM,Zll-sci.hhu,5,引言introductiontomathematicslogic,6/18/20201:15AM,Zll-sci.hhu,6,什么叫數(shù)學(xué)？數(shù)學(xué)的研究對(duì)象是什么？,數(shù)學(xué)家語(yǔ)錄（1914年）：幾百個(gè)數(shù)學(xué)的定義,6/18/20201:15AM,Zll-sci.hhu,7,本身已如此一目了然，已沒(méi)有任何詞匯能夠把他解說(shuō)得更清楚的事物，絕不要試圖給他下定義。以免被所使用的含混不清的詞匯所欺騙。帕斯卡（法、17世紀(jì)）,6/18/20201:15AM,Zll-sci.hhu,8,數(shù)學(xué)：心智的產(chǎn)物柏拉圖,數(shù)學(xué)是研究數(shù)量的科學(xué)亞里士多德,6/18/2

3、0201:15AM,Zll-sci.hhu,9,數(shù)是一種離散的數(shù)量、線是一種連續(xù)的數(shù)量。,研究數(shù)及其屬性的學(xué)科叫做算術(shù)研究量及其屬性的學(xué)科叫做幾何,研究數(shù)和量的學(xué)科叫做數(shù)學(xué)亞里士多德,6/18/20201:15AM,Zll-sci.hhu,10,數(shù)學(xué)是研究順序和度量的科學(xué)笛卡爾,順序=數(shù)度量=量,6/18/20201:15AM,Zll-sci.hhu,11,數(shù)學(xué)=邏輯羅素,邏輯是數(shù)學(xué)的少年時(shí)代數(shù)學(xué)是邏輯的成年時(shí)代,數(shù)學(xué)是研究結(jié)構(gòu)的科學(xué)布爾巴基學(xué)派（30年代）,6/18/20201:15AM,Zll-sci.hhu,12,數(shù)學(xué)作為人類智慧的一種表達(dá)形式，反映生動(dòng)活潑的意念、深入細(xì)致的思考、以及完

4、美和諧的愿望。他的基礎(chǔ)是邏輯和直覺(jué)、分析和推理、共性和個(gè)性?？评?，羅賓斯（美）數(shù)學(xué)是什么，1941年,6/18/20201:15AM,Zll-sci.hhu,13,數(shù)學(xué)的研究對(duì)象是客觀世界的和邏輯可能的數(shù)量關(guān)系和結(jié)構(gòu)關(guān)系丁孫石,數(shù)學(xué)是研究現(xiàn)實(shí)世界中量的關(guān)系的科學(xué)關(guān)肇直,6/18/20201:15AM,Zll-sci.hhu,14,離散數(shù)學(xué)與數(shù)理邏輯的關(guān)系：離散數(shù)學(xué)的內(nèi)容：數(shù)理邏輯（MathematicsLogic)集合論(Sets)組合論（Combination)圖論（GraphTheory)代數(shù)結(jié)構(gòu)（AlgbraStructure),6/18/20201:15AM,Zll-sci.hhu,1

5、5,邏輯學(xué)：研究推理的一門(mén)學(xué)科.數(shù)理邏輯：用數(shù)學(xué)方法研究推理的一門(mén)數(shù)學(xué)學(xué)科.-一套符號(hào)體系+一組規(guī)則,離散數(shù)學(xué)研究離散量的關(guān)系的一門(mén)科學(xué)。研究離散結(jié)構(gòu)的數(shù)學(xué)分科。（辭海）,6/18/20201:15AM,Zll-sci.hhu,16,數(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é)的方法來(lái)研究思維，把思維過(guò)程轉(zhuǎn)換為數(shù)學(xué)的計(jì)算。萊布尼茲(Leibniz,16461716)完善三段論，提出了建立數(shù)理邏輯或者說(shuō)理性演算的思想：提出將

6、推理的正確性化歸于計(jì)算，這種演算能使人們的推理不依賴于對(duì)推理過(guò)程中的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。使用一種符號(hào)語(yǔ)言來(lái)代替自然語(yǔ)言對(duì)演算進(jìn)行描述，將符號(hào)的形式和其含義分開(kāi)。使得演算從很大程度上取決與符號(hào)的組合規(guī)律，而與其含義無(wú)關(guān)。,第一創(chuàng)始人,6/18/20201:15AM,Zll-sci.hhu,17,布爾(G.Boole,18151864)代數(shù)：將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。弗雷格(G.Frege,18481925)：概念語(yǔ)言一種按算術(shù)的公式語(yǔ)言構(gòu)成的純思維公式語(yǔ)言(1879)的出版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分命題演

7、算和謂詞演算的正式建立。皮亞諾(GiuseppePeano,18581932)：用一種新的方法陳述的算術(shù)原理(1889)提出了自然數(shù)算術(shù)的一個(gè)公理系統(tǒng)。,第三創(chuàng)始人,第二創(chuàng)始人,6/18/20201:15AM,Zll-sci.hhu,18,羅素(BertrandRussell,18721970)：數(shù)學(xué)原理(與懷特黑合著，1910,1912,1913)從命題演算和謂詞演算開(kāi)始，然后通過(guò)一元和二元命題函項(xiàng)定義了類和關(guān)系的概念，建立了抽象的類演算和關(guān)系演算。由此出發(fā)，在類型論的基礎(chǔ)上用連續(xù)定義和證明的方式引出了數(shù)學(xué)（主要是算術(shù)）中的主要概念和定理。邏輯演算的發(fā)展：甘岑(G.Gentzen)的自然推理

8、系統(tǒng)(NaturalDeductionSystem)，邏輯演算的元理論：公理的獨(dú)立性、一致性、完全性等。各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis,18831964)的模態(tài)邏輯，實(shí)質(zhì)蘊(yùn)涵怪論和嚴(yán)格蘊(yùn)涵、相干邏輯等，盧卡西維茨的多值邏輯等。,6/18/20201:15AM,Zll-sci.hhu,19,第一章命題邏輯基本概念,邏輯是解決推理方法的學(xué)科，中心是推理，基本要素是命題，所以稱為命題邏輯。數(shù)理邏輯則是用數(shù)學(xué)方法研究推理。學(xué)習(xí)目的本章首先要深刻理解命題的概念，理解原子命題和復(fù)合命題的關(guān)系，在此基礎(chǔ)之上理解邏輯聯(lián)結(jié)詞的定義，命題公式的定義和分類，最后熟練掌握并應(yīng)用真值表的構(gòu)造。,6/18

9、/20201:15AM,Zll-sci.hhu,20,基本內(nèi)容：命題概念；邏輯聯(lián)結(jié)詞概念,復(fù)合命題和聯(lián)結(jié)詞的關(guān)系；命題符號(hào)化和翻譯合式公式概念及分類；構(gòu)造真值表判定公式類型,6/18/20201:15AM,Zll-sci.hhu,21,1.1命題(statement,proposition),概念在二值邏輯中，命題是或真或假，而不會(huì)同時(shí)又真又假的陳述句。陳述句；或真或假；唯一真值.例：(1)地球是方的；假的陳述句，是命題；(2)2+3=5；真的陳述句，是命題；(3)你知道命題邏輯嗎？非陳述句，故非命題；,6/18/20201:15AM,Zll-sci.hhu,22,(4)3-x=5；陳述句,但

10、真假隨x的變化而變化，非命題；(5)請(qǐng)安靜！非陳述句，故非命題；(6)火星表面的溫度是800C；（現(xiàn)時(shí)不知真假的陳述句，但只能要么真要么假，故是命題）(7)明天是晴天；盡管要到第二天才能得知其真假，但的確是要么真要么假，故是命題；(8)我正在說(shuō)謊；無(wú)法得知其真假，這是悖論。注意:(4)不是命題，后續(xù)章節(jié)中會(huì)提到，這被稱為謂詞，命題函數(shù)或命題變項(xiàng)。,6/18/20201:15AM,Zll-sci.hhu,23,分類：簡(jiǎn)單命題，通常用p,q,r,等表示命題變項(xiàng)，命題常項(xiàng)用1(T)，0(F)表示；復(fù)合命題，由簡(jiǎn)單命題和聯(lián)結(jié)詞構(gòu)成；,6/18/20201:15AM,Zll-sci.hhu,24,1.2

11、邏輯聯(lián)結(jié)詞和復(fù)合命題,1)否定式和否定聯(lián)結(jié)詞(negation)命題p的非或否定，稱為p的否定式，表示為p；符號(hào)即為否定聯(lián)結(jié)詞。真值表：,嚴(yán)格說(shuō)，p不是復(fù)合命題。例：p：今天天氣好；p：今天天氣不好p：2+51；p：2+51；在此情形下，p為真，p為假。,6/18/20201:15AM,Zll-sci.hhu,25,2)合取式和合取聯(lián)結(jié)詞(conjunction)p且q稱為p,q的合取式，記為pq；符號(hào)即為合取聯(lián)結(jié)詞。這是邏輯“與”。,相應(yīng)的日常用語(yǔ)為：“既又”，“不但(僅)而且”“雖然但是”等等。,例：1)p:今天大太陽(yáng)，q:今天熱，pq:今天大太陽(yáng)且熱；2)p:今天上課有人遲到，q:2+5

12、1，pq:今天上課有人遲到且2+51；注意2)中的結(jié)果，我們可以用邏輯聯(lián)結(jié)詞來(lái)聯(lián)結(jié)兩個(gè)日常生活中無(wú)關(guān)的命題。,6/18/20201:15AM,Zll-sci.hhu,26,3)析取式和析取聯(lián)結(jié)詞(disjunction)p或者q稱為p,q的析取式，記為pq；符號(hào)即為析取聯(lián)結(jié)詞。這是邏輯“或”。,注意p和q可以同時(shí)為真，所以這是“相容或”。另外還有p、q不可能同時(shí)為真的“相斥或”。在數(shù)學(xué)和計(jì)算機(jī)學(xué)科中“或”是指“相容或”，“相斥或”用另一名稱“異或”表示。,6/18/20201:15AM,Zll-sci.hhu,27,4)異或式和異或聯(lián)結(jié)詞(exclusiveor)p或q中只可能有一個(gè)為真稱為p

13、,q的異或式，記作pq，讀作“p異或q”。符號(hào)稱為異或聯(lián)結(jié)詞。,6/18/20201:15AM,Zll-sci.hhu,28,例(1)p：今天大太陽(yáng)，q：今天熱；pq:今天大太陽(yáng)或者熱。(2)p：今天上課有人遲到，q：2+51；pq：今天上課有人遲到或2+51。(3)p：他生于1966年，q：他生于1965年；pq：他生于1966年或1965年。(4)p:他今天騎車來(lái)上課，q:他今天走路來(lái)上課，p、q為異或,6/18/20201:15AM,Zll-sci.hhu,29,5)蘊(yùn)涵式和蘊(yùn)涵聯(lián)結(jié)詞(conditionalstatement,implication)如果p則q稱作p、q的蘊(yùn)涵式，記為p

14、q。為蘊(yùn)涵聯(lián)結(jié)詞，p、q分別為蘊(yùn)涵式的前件和后件。,注意p是q的充分條件，q是p的必要條件。“只要p就q”、“p僅當(dāng)q”、“只有q才p”等可表示成pq,6/18/20201:15AM,Zll-sci.hhu,30,蘊(yùn)涵式的一個(gè)應(yīng)用：數(shù)學(xué)歸納法(1)證明P(n0)成立；(2)證明kn0,P(k)P(k+1)總是成立在(1)中，P(k)P(k+1)總是成立意味著P(k)P(k+1)的真值為T(mén)，從而只可能是真值表中的1,3,4情形，而(1)中證明前件為真，所以后件也一定為真。,6/18/20201:15AM,Zll-sci.hhu,31,6)等價(jià)式和等價(jià)聯(lián)結(jié)詞(equivalence,bicondi

15、tional)p當(dāng)且僅當(dāng)q稱作p、q的等價(jià)式，記pq。稱為等價(jià)聯(lián)結(jié)詞，p是q的充要條件。,6/18/20201:15AM,Zll-sci.hhu,32,以上介紹了六種常用的邏輯聯(lián)結(jié)詞以及與之相關(guān)的復(fù)合命題。這些聯(lián)結(jié)詞反映了復(fù)合命題及其支命題之間抽象的邏輯關(guān)系。復(fù)合命題的符號(hào)化一般可以根據(jù)上述定義進(jìn)行，基本步驟如下：1)找出各個(gè)支命題，并逐個(gè)符號(hào)化；2)找出各個(gè)連接詞，符號(hào)成相應(yīng)聯(lián)結(jié)詞；3)用聯(lián)結(jié)詞將各支命題逐個(gè)聯(lián)結(jié)起來(lái).,6/18/20201:15AM,Zll-sci.hhu,33,例1.7將下列命題符號(hào)化：(1)李明是計(jì)算機(jī)系的學(xué)生，他住在312室或313室(2)辱罵和恐嚇決不是戰(zhàn)斗；(3)

16、李瑞和李珊是姐妹。(4)除非天氣好，否則我是不會(huì)去公園的；,6/18/20201:15AM,Zll-sci.hhu,34,解(1)首先用字母表示簡(jiǎn)單命題p：李明是計(jì)算機(jī)系的學(xué)生q：李明住在312室r：李明住在313室該復(fù)合命題可表示為p(qr)。,6/18/20201:15AM,Zll-sci.hhu,35,(2)設(shè)p：辱罵不是戰(zhàn)斗。q：恐嚇不是戰(zhàn)斗。pq(3)設(shè)p：李瑞和李珊是姐妹p(4)設(shè)p：今天天氣好。q：我去公園。qp,6/18/20201:15AM,Zll-sci.hhu,36,1.3合式公式和真值函數(shù),命題形式：各種復(fù)合命題的符號(hào)化表達(dá)式，即為此命題的命題形式，它給出的是復(fù)合命題及

17、其簡(jiǎn)單命題之間真值關(guān)系的邏輯骨架。命題形式必定是合式公式。,6/18/20201:15AM,Zll-sci.hhu,37,歸納定義:一個(gè)集合的歸納定義(inductivedefinition)通常分為三步：歸納基：一些基本的元素屬于該集合；歸納步：定義一些規(guī)則（或者說(shuō)操作），從該集合中已有的元素來(lái)生成該集合的新的元素；最小化：該集合中的所有元素都是通過(guò)基本元素以及所定義的規(guī)則生成的，換句話說(shuō)，該集合是由基本元素及規(guī)則所生成的最小的集合。自然數(shù)集N的歸納定義：1.歸納基：0是一個(gè)自然數(shù)，即0N。2.歸納步：若n是自然數(shù)，則n的后繼也是自然數(shù)。記n的后繼為succ(n)，即若nN，則succ(n)

18、N。為方便起見(jiàn)，后面也記n的后繼為n+1。3.最小化：所有的自然都通過(guò)步驟1和2得到，或者說(shuō)自然數(shù)集是通過(guò)步驟1和2得到的最小集合。,6/18/20201:15AM,Zll-sci.hhu,38,合式公式，也稱命題公式，遞歸定義為：(1)p,q,r,1,0是合式公式；(2)如果A是合式公式，則A也是；(3)如果A和B是合式公式，則由邏輯聯(lián)結(jié)詞聯(lián)結(jié)A和B的符號(hào)串也是；(4)有限次應(yīng)用(1)-(3)構(gòu)成的符號(hào)串才是合式公式。(1)是遞歸定義的基礎(chǔ)，直接規(guī)定簡(jiǎn)單的內(nèi)容；(2),(3)是遞歸定義的歸納，規(guī)定了是由簡(jiǎn)單到復(fù)雜的過(guò)程；4)是遞歸定義的界限，規(guī)定了滿足前述(1)(3)條件的最小范圍。,6/1

19、8/20201:15AM,Zll-sci.hhu,39,在一個(gè)復(fù)雜的公式中，為了避免歧義需要引進(jìn)許多的括號(hào)，但如果括號(hào)太多會(huì)使人眼花繚亂，如(p(qr)(pq)(rs)，共有6對(duì)括號(hào)，為了減少括號(hào)并不引起歧義，引進(jìn)如下省略括號(hào)的約定：(1)公式最外層的括號(hào)可以省略；(2)規(guī)定聯(lián)結(jié)詞運(yùn)算優(yōu)先級(jí)別由高到低是、，若無(wú)括號(hào)，優(yōu)先級(jí)高的先運(yùn)算；(3)若同一個(gè)聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無(wú)括號(hào)，則按從左到右的順序運(yùn)算。按照上述約定，(p(qr)(pq)(rs)省略了三對(duì)括號(hào)簡(jiǎn)化為p(qr)(pq)(rs)。省略括號(hào)只是讓公式書(shū)寫(xiě)簡(jiǎn)便，但并不能改變其復(fù)雜性。,6/18/20201:15AM,Zll-sci.hhu,

20、40,合式公式的層次(遞歸定義)：,(1)如果A是單個(gè)命題常項(xiàng)或命題變項(xiàng)p,q,r,s,0,1，則稱A是0層公式；(2)稱A是n+1(n0)層公式,是指A符合下列情況之一：(a)A=B，B是n層公式；(b)A=(AB)，其中B、C分別是i層和j層公式,且n=max(i,j)；(c)A=(AB)，其中B、C的層次同(b)；(d)A=(AB)，其中B、C的層次同(b)；(e)A=(AB)，其中B、C的層次同(b)；(3)若A的最高層次為k，則稱A是k層公式。注意:(1)“=”即為通常意義上的等號(hào)。(2)定義中不僅有p,q,r,s,0,1等，而且引入了大寫(xiě)的A、B、C等代表任意的合式公式，不同于p,

21、q,r,及聯(lián)結(jié)詞構(gòu)成的表示某個(gè)具體的公式，兩者是命題邏輯中不同層次上的語(yǔ)言。,(2)定義中不僅有p,q,r,s,0,1等，而且引入了大寫(xiě)的A、B、C等代表任意的合式公式，不同于p,q,r,及聯(lián)結(jié)詞構(gòu)成的表示某個(gè)具體的公式，兩者是命題邏輯中不同層次上的語(yǔ)言。,6/18/20201:15AM,Zll-sci.hhu,41,真值賦值及公式分類,令A(yù)是命題形式，p1,p2,pn是出現(xiàn)在A中的所有命題變項(xiàng)，給p1,p2,pn指派一組真值，稱為對(duì)A的一個(gè)賦值，也稱為一個(gè)解釋。若一個(gè)賦值使得A的真值為真，則稱此賦值滿足A，而稱此賦值為A的一個(gè)成真賦值，相應(yīng)地若A的值為假，稱此賦值不滿足A，而稱此賦值為A的一

22、個(gè)成假賦值。一個(gè)含有n個(gè)命題變項(xiàng)的命題形式，共有個(gè)賦值。,6/18/20201:15AM,Zll-sci.hhu,42,例:已知A是含命題變項(xiàng)p,q,r的命題形式，其成真賦值為000,010,101，求A的成真賦值和成假賦值。解：A的成假賦值為001,011,100,110,111，所以A的成真賦值為：001,011,100,110,111；成假賦值為：000,010,101。用命題形式B1,B2,Bn分別替換命題形式A中的命題變項(xiàng)p1,p2,pn得到的新的命題形式稱為A的一個(gè)替換實(shí)例。例如，p(pq),以pq替換p,以r替換q,則得到原式的一個(gè)替換實(shí)例為(pq)(pq)r)。,6/18/20

23、201:15AM,Zll-sci.hhu,43,命題形式的分類,重言式(tautology)：值總是為真的命題形式。如果一個(gè)蘊(yùn)涵式AB是重言式，則記作AB，表示由A可推導(dǎo)出B；同樣如果一個(gè)等價(jià)式AB是重言式，則記作AB，表示A和B等值。注意和不是邏輯聯(lián)結(jié)詞，它們表示的分別是邏輯推理和邏輯等值運(yùn)算，下面的章節(jié)將分別討論。矛盾式(contradiction)：值總是為假的命題形式?？蓾M足式(contingency)。,6/18/20201:15AM,Zll-sci.hhu,44,命題形式間的關(guān)系,重言式也是可滿足式，不過(guò)還是將命題形式分成三類：重言式、矛盾式、可滿足式；即可滿足式不包含重言式。這種

24、分類主要是為了體現(xiàn)重言式的重要性，實(shí)際上在命題邏輯中公理、定理都是重言式，在自然推理的過(guò)程中，一個(gè)正確的推理也必須是重言式。設(shè)A命題形式，則A是重言式，則A的任何替換實(shí)例都是重言式；A是矛盾式，則A的任何替換實(shí)例都是矛盾式；,6/18/20201:15AM,Zll-sci.hhu,45,真值表和構(gòu)成真值表的方法,真值表：命題形式在其命題變項(xiàng)取所有可能取值時(shí)對(duì)應(yīng)的真值列成的表。構(gòu)成真值表的方法：找出給定命題形式中的所有命題變項(xiàng)，列出所有可能的取值；由低到高列出命題形式的各層次；計(jì)算各層次的的值，直至最后計(jì)算命題形式的值?？偪梢栽谟邢薏絻?nèi)構(gòu)造一個(gè)命題形式的真值表，并根據(jù)該真值表來(lái)判斷其類型。這種在有限步內(nèi)判定一個(gè)命題形式是重言式、矛盾式還是可滿足式的問(wèn)題，稱為命題形式的判定問(wèn)題,6/18/20201:15AM,Zll-sci.hhu,46,真值函數(shù)：一個(gè)n元真值函數(shù)是指F：0，1，(n1)，即此函數(shù)以n個(gè)命題變項(xiàng)為變?cè)?，其定義域和值域均由真、假兩值構(gòu)成。真值函數(shù)同樣可以用真值表表示，這是真值函數(shù)在其命題變項(xiàng)所有可能取值