Lecture-1數(shù)理邏輯

1、數(shù)理邏輯(1)計(jì)算機(jī)學(xué)院姜新574656xinwenjiangxinwenjianggfkd.mtnQQ:4712810,本講內(nèi)容,1.課程介紹2.要求及注意事項(xiàng)3.形式系統(tǒng)4.P系統(tǒng)介紹,數(shù)理邏輯課程介紹,邏輯：客觀事物的規(guī)律在人的主觀意識(shí)中的反映推理：就是從一個(gè)或幾個(gè)已知判斷推導(dǎo)出一個(gè)新的判斷的思維過程。,數(shù)理邏輯課程介紹,邏輯學(xué)：研究思維形式和思維規(guī)律的一門科學(xué)。任何推理都有它形式和內(nèi)容的兩個(gè)方面。推理的內(nèi)容是它所施用的具體的科學(xué)理論的研究對(duì)象，而邏輯學(xué)研究的是推理的形式，也就是去除內(nèi)容后前提判斷與結(jié)論的關(guān)系。,數(shù)理邏輯課程介紹,形式邏輯：以思維的形式結(jié)構(gòu)及規(guī)律

2、進(jìn)行研究的邏輯學(xué)。辨證邏輯：以辨證法認(rèn)識(shí)論來進(jìn)行研究的邏輯學(xué)。,數(shù)理邏輯課程介紹,形式邏輯主要從形式結(jié)構(gòu)上研究思維的形式和規(guī)律。形式邏輯推理的每一個(gè)環(huán)節(jié)都是完全確定的，界限分明的，它用邏輯符號(hào)來指稱對(duì)象，有一套嚴(yán)密的邏輯規(guī)則，能夠進(jìn)行精確的邏輯演算。,數(shù)理邏輯課程介紹,歸納邏輯和演繹邏輯歸納邏輯研究特殊到一般、特殊到特殊的推理。它是一種或然性推理。例：美國(guó)加州的自然環(huán)境與我國(guó)南方地區(qū)的自然環(huán)境是相似的，我國(guó)南方地區(qū)適宜種植柑橘，所以，美國(guó)加州也適宜種植柑橘。顯然，這是從特殊到特殊的推理，通常叫做類比推理。,數(shù)理邏輯課程介紹,歸納邏輯研究特殊到一般、特殊到特殊的推理。它是一種或然性推理。例：所有

3、的以前發(fā)現(xiàn)的綠寶石都是綠的，所以，下一個(gè)被發(fā)現(xiàn)的綠寶石將是綠的。當(dāng)人們把關(guān)于過去經(jīng)驗(yàn)的概括整理起來以便做出關(guān)于即將發(fā)生的特定事件的預(yù)見時(shí)，他們常常使用這種歸納推理。,數(shù)理邏輯課程介紹,歸納邏輯研究特殊到一般、特殊到特殊的推理。它是一種或然性推理。例：這個(gè)班上的所有學(xué)生都是高智商的，這個(gè)班上的所有學(xué)生都有強(qiáng)烈的學(xué)習(xí)熱情，這個(gè)班上的所有學(xué)生學(xué)業(yè)負(fù)擔(dān)都比較輕，這個(gè)班上的所有學(xué)生都是心理健康的，所以，這個(gè)班上的所有學(xué)生學(xué)習(xí)成績(jī)都比較好。,數(shù)理邏輯課程介紹,演繹邏輯從一般到特殊的邏輯推理方法，也常被稱之謂一種必然性推理，或保真性推理。演繹主義者認(rèn)為歸納不靠譜。（海城到唐山）歸納主義者反對(duì)或貶低演繹邏輯，

4、認(rèn)為演繹邏輯不是一種科學(xué)的方法，其基本理由有兩個(gè)：1.認(rèn)為演繹邏輯不能給人以新知識(shí)。2.認(rèn)為演繹邏輯不能證明其前提的正確性，必然導(dǎo)致先驗(yàn)論。,數(shù)理邏輯課程介紹,數(shù)理邏輯：用數(shù)學(xué)方法和計(jì)算的方法來研究推理的規(guī)律，又稱符號(hào)邏輯。是一種形式邏輯。屬于演繹邏輯。數(shù)理邏輯中的“數(shù)理”一詞有兩層意思：其一是Leibniz的思想用數(shù)學(xué)的方法研究邏輯；其二是主要研究數(shù)學(xué)中使用的邏輯。,數(shù)理邏輯課程介紹,數(shù)理邏輯的發(fā)展：300年，三個(gè)階段：17世紀(jì)末到19世紀(jì)末，從萊布尼茨到布爾、德摩根，成果有布爾代數(shù)和關(guān)系邏輯。19世紀(jì)中葉以后60年，奠定自己的理論基礎(chǔ)，創(chuàng)建了特有的新方法，成為一門學(xué)科。成就有四個(gè)方面：集合

5、論創(chuàng)建，公理化方法的發(fā)展，邏輯演算的建立，證明論的提出。1940年以后發(fā)展出5各方面內(nèi)容，并與數(shù)學(xué)其他分支和計(jì)算機(jī)科學(xué)有了廣泛的聯(lián)系。,數(shù)理邏輯課程介紹,數(shù)理邏輯的5各方面內(nèi)容邏輯演算，遞歸論，公理集合論，證明論，模型論。,數(shù)理邏輯課程介紹,數(shù)理邏輯研究?jī)?nèi)容：我們主要介紹它的兩個(gè)最基本的也是最重要的組成部分，就是“命題演算”和“謂詞演算”。命題演算是研究關(guān)于命題如何通過一些邏輯連接詞構(gòu)成更復(fù)雜的命題以及邏輯推理的方法。命題是指具有具體意義的又能判斷它是真還是假的句子。謂詞演算也叫做命題涵項(xiàng)演算。在謂詞演算里，把命題的內(nèi)部結(jié)構(gòu)分析成具有主詞和謂詞的邏輯形式，由命題涵項(xiàng)、邏輯連接詞和量詞構(gòu)成命題，

6、然后研究這樣的命題之間的邏輯推理關(guān)系。,數(shù)理邏輯課程介紹,一句有真假意義的陳述句稱為命題。例：（）數(shù)理邏輯是計(jì)算機(jī)專業(yè)的核心課（）三角形之內(nèi)角之和等于（）二進(jìn)制數(shù)（）凡是國(guó)旗都是紅色的。（）我正在說謊。（）本命題是假的。,要求和注意事項(xiàng),反復(fù)思考、琢磨、辨析真正訓(xùn)練計(jì)算思維,形式系統(tǒng),定義稱五元偶FS=為形式系統(tǒng),其中,為非空集合,稱為FS的符號(hào)表,其元素稱為FS的符號(hào)。Term*,稱為FS的項(xiàng)集合,其元素稱為FS的項(xiàng)。Formula*且FormulaTerm=,稱為FS的公式集合,其元素稱為FS的公式。此外，有Formula的一個(gè)子集Atom稱為FS的原子公式集合，其元素稱為FS的原子公式。

7、AxiomFormula,稱為FS的公理集合，其元素稱為FS的公理。Rule,稱為FS的推演規(guī)則的集合，其元素稱為FS的推演規(guī)則。,形式系統(tǒng),如果rRule及A0,A1,An,BFormula(nN)使得r，稱可由推演規(guī)則r以及A0,A1,An重寫出B，簡(jiǎn)稱可由A0,A1,An重寫出B，記為或者,形式系統(tǒng),Term,Formula為FS的語言部分，Axiom和Rule為FS的推演部分Term,Formula,Axiom,和Rule都可以是空集當(dāng)Term=Axiom=Rule=，F(xiàn)S僅僅是一個(gè)語言生成系統(tǒng)FS本身使用的語言稱為FS的對(duì)象語言研究FS還要使用到元語言,形式系統(tǒng),通常還要對(duì)FS加以限

8、制，使得FS推演能夠機(jī)械的實(shí)現(xiàn)a.為有窮集或者可數(shù)集b.Term,Formula,Atom,Axiom,Rule都是遞歸的，即成員關(guān)系是可判定的,初等數(shù)論形式系統(tǒng)FSEN,=0,Term=0,0,0,Formula=t1t2t1,t2Term=AtomAxiom=00Rule=r，其中，r=t1,t2Term,初等代數(shù)中的群論形式系統(tǒng)FSG,=e,*,-1,(,),X,其中，X為集合且Xe,*,-1,(,),=Term=，其中T0=XeTi+1=(t-1),(t1*t2)t,t1,t2Tii=0,1,.Formula=t1t2t1,t2Term=AtomAxiom=aaaXeett,t-1*t

9、e,(t1*t2)*t3t1*(t2*t3)t1,t2,t3Term,初等代數(shù)中的群論形式系統(tǒng)FSG,Rule=r1,r2,r3,r4，其中，r1=t1,t2Termr2=t1,t2Termr3=t1,t2,t3Termr4=t1,t2,t3,t4Term,形式系統(tǒng),（可證）定義1.2設(shè)AFormula，若有A0,A1,A2,AmFormula滿足：Am=A當(dāng)0jm時(shí)，以下兩個(gè)條件至少一個(gè)成立：1.AjAxiom2.有rRule以及j0,j1,jn(nN,0j0,j1,jnr,形式系統(tǒng),就稱A為FS的一個(gè)定理，或者稱A為可證的，記為FSA，并稱A0,A1,A2,Am為A的一個(gè)證明。FSA在不引

10、起混淆時(shí)簡(jiǎn)寫為A。,形式系統(tǒng),（從前提出發(fā)可證）定義設(shè)AFormula，F(xiàn)ormula，若有A0,A1,A2,AmFormula滿足：Am=A當(dāng)0jm時(shí)，以下三個(gè)條件至少一個(gè)成立：1.Aj2.AjAxiom,形式系統(tǒng),3.有rRule以及j0,j1,jn(nN,0j0,j1,jnr就稱A由可證的，記為FSA，并稱A0,A1,A2,Am為A的從出發(fā)一個(gè)證明。FSA在不引起混淆時(shí)簡(jiǎn)寫為A。,形式系統(tǒng),定義Th(FS)=AFormulaFSA不引起混淆時(shí)，Th(FS)=Th()顯然，若為空，Th(FS)=Th(FS),形式系統(tǒng),若干性質(zhì)性質(zhì)1AxiomTh(FS)Th()性質(zhì)2Th()性質(zhì)3Th()

11、=Th(FS)性質(zhì)4Th(Th()=Th(),形式系統(tǒng),定義設(shè)FSi=(i=1,2)為形式系統(tǒng)。若FS1和FS2滿足：12,Term1Term2,Formula1Formula2,Axiom1Th(FS2)且Rule1Rule2，就稱FS2為FS1的一個(gè)擴(kuò)張，記為FS1FS2。當(dāng)還有FS1FS2時(shí)，又記為FS1FS2,P系統(tǒng)、P的定理及導(dǎo)出規(guī)則,P的符號(hào)表通用符號(hào)命題聯(lián)接詞：，括號(hào)：（，）特殊符號(hào)可數(shù)個(gè)命題變?cè)簆，q，r，pi，qi，ri，（i0，1，）P的項(xiàng)集Term，即P無項(xiàng),命題邏輯,P的公式集Formula*為滿足以下條件的集合F*的最小集合：若p為命題變?cè)?，則pF；若AF，則AF若

12、A，BF，則（AB）F,命題邏輯,定理2.1.1（公式結(jié)構(gòu)歸納法）若FFormula滿足以下條件：若p為命題變?cè)瑒tpF；若AF，則AF；若A，BF，則（AB）F則FFormula,命題邏輯,證明：由F也滿足產(chǎn)生公式的條件)及Formula的最小性，知FormulaF，所以再由題設(shè)FFormula即得F=Formula一種證明方法：根據(jù)上面證明的公式結(jié)構(gòu)歸納法，要想證明Formula中的每個(gè)公式都具有某種性質(zhì)時(shí)，可先令F=AFormulaA具有性質(zhì)然后再驗(yàn)證F滿足定理2.1.1中的條件)即可。,命題邏輯,派生命題聯(lián)結(jié)詞：（AB）代表（AB）：（AB）代表（AB）：（AB）代表（AB）（BA）,

13、命題邏輯,符號(hào)，和稱為命題聯(lián)結(jié)詞，其直觀意義分別為：A意指非A（AB）意指A或B（AB）意指A且B（AB）意指A蘊(yùn)含B（AB）意指A當(dāng)且僅當(dāng)B,命題邏輯,（pq）r）（p（qr）表示（【（pq）（pq）】r）（【（pq）（pq）】r）（p(qr)(qr)）（p（qr）（qr）,命題邏輯,約定：公式最外層括號(hào)可以省略；同一命題聯(lián)結(jié)詞的多次出現(xiàn)按從左到右的順序依次處理；不同的命題聯(lián)結(jié)詞按，的優(yōu)先次序處理用“”代表一個(gè)左括號(hào)，而與此“左括號(hào)”相匹配的右括號(hào)，在不改變已有括號(hào)匹配關(guān)系的條件下，要盡可能地遠(yuǎn)；,命題邏輯,pqrsrP(rqrs)pAS3:ABCABCAS3:(AB)(CA)(BC),命題

14、邏輯,4.P的公理集AxiomAS1AS2AS3，其中AS1:AAAAS2:ABAA，B，CFormulaAS3:ABCABC亦即AS1AAA|AFormulaAS2ABA|A，BFormulaAS3ABCABC|A，B，CFormula,命題邏輯,5.P的推演規(guī)則集RuleMP，其中，或者說“若A且AB，則B”。這里，A，BFormula亦即MP|A，BFormula通常，把MP稱為假言推理（modusponens）,命題邏輯,綜合以上所述，我們獲得了一個(gè)命題邏輯形式系統(tǒng)如下：P,命題邏輯,代入運(yùn)算及其性質(zhì)定義2.1.1如果函數(shù)：*滿足以下條件：i）()；（表示空符號(hào)串）ii）若x，則(x)

15、；iii)若X，Y*，則(XY)(X)(Y)就稱為一個(gè)代入。,命題邏輯,定義2.1.2設(shè)為一個(gè)代入。i）若x|(x)x為有窮集，則稱為一個(gè)有窮代入。ii）若滿足以下條件：()，()，(（）（,且（）)就稱為一個(gè)變?cè)搿?命題邏輯,iii）若有命題變?cè)猵1，pn及公式A1，AnFormula使則把記為,x,命題邏輯,定義函數(shù)Var：Formula2如下：若p為命題變?cè)?則Var(p)=p；若AFormula,則Var(A)=Var(A);若A，BFormula，則Var(AB)=Var(A)Var(B),命題邏輯,定義2.1.3設(shè)AFormula，且p為命題變?cè)?。若pVar(A)，則稱p在A中

16、出現(xiàn)，否則稱p不在A中出現(xiàn)。,導(dǎo)出規(guī)則,派生規(guī)則（）：若A，則A派生規(guī)則（+）：若1A且12，則2A派生規(guī)則（）：若1A且2AB，1且2，則B,導(dǎo)出規(guī)則(代入),導(dǎo)出規(guī)則,導(dǎo)出規(guī)則,導(dǎo)出規(guī)則,導(dǎo)出規(guī)則（Dr1,1,2,3,4,5,6）,Therearethreesuspectsforamurder.Admas,Brown,andClark.Admassays“Ididnotdoit.ThevictimwasanoldacquaintanceofBrowns.ButClarkhatedhim.”Brownstates“Ididnotdoit.Ididnotevenknowtheguy.Besid

17、esIwasoutoftownallthatweek.”Clarksays“Ididnotdoit.IsawbothAdmasandBrowndowntownwiththevictimthatday;oneofthemmusthavedoneit.”Assumethatthetwoinnocentmenaretellingtruth,butthattheguiltymanmightnotbe.Whodidit?,導(dǎo)出規(guī)則,釀酒壇壇好做醋缸缸酸養(yǎng)豬大于山老鼠只只亡,導(dǎo)出規(guī)則,釀酒壇壇好做醋，缸缸酸養(yǎng)豬大于山老鼠，只只亡,導(dǎo)出規(guī)則,黃河遠(yuǎn)上白云間一片孤城萬仞山羌笛何須怨楊柳春風(fēng)不渡玉門關(guān),導(dǎo)出規(guī)則

18、,黃河遠(yuǎn)上，白云間一片，孤城萬仞山。羌笛何須怨，楊柳春風(fēng)，不渡玉門關(guān)。,形式系統(tǒng),錄取研究生(c)有許多條件：外語成績(jī)不低于55分(a)，或者不及格科目不多于兩門。三種表達(dá)如下：如果外語成績(jī)低于55分，并且不及格科目多于2門，那么不被錄取。(notaandnotbthennotc)如果某人未被錄取研究生，那么他的外語成績(jī)低于55分，或者不及格門數(shù)多于2門.(notcthennotaornotb)如果外語成績(jī)低于55分，或者不及格門數(shù)多于2門，那么不被錄取。(notaornotb)thennotc),Therearethreesuspectsforamurder.Admas,Brown,andClark.Admassays“Ididnotdoit.ThevictimwasanoldacquaintanceofBrowns.ButClarkhatedhim.”Brownstates