




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 天津市河?xùn)|區(qū)2024-2025學(xué)年物理八年級(jí)第一學(xué)期期末教學(xué)質(zhì)量檢測(cè)試題含解析
- 廣西玉林陸川縣聯(lián)考2024年數(shù)學(xué)七上期末調(diào)研模擬試題含解析
- 綠色能源背景下生物質(zhì)活性炭市場(chǎng)拓展策略
- 領(lǐng)導(dǎo)在航空航天項(xiàng)目現(xiàn)場(chǎng)施工中的指導(dǎo)講話
- 中國(guó)生物質(zhì)能太空站發(fā)展趨勢(shì)預(yù)測(cè)
- 公交公司運(yùn)營(yíng)部工作總結(jié)
- 美妝品牌行業(yè)綠色發(fā)展路徑實(shí)踐案例分享
- 企業(yè)內(nèi)部審制度及實(shí)施策略
- 時(shí)尚達(dá)人推 薦的設(shè)計(jì)師羽絨服品牌
- 公共管理擔(dān)當(dāng)有為爭(zhēng)先創(chuàng)優(yōu)心得體會(huì)范文
- 2024屆甘南市語文八年級(jí)第二學(xué)期期末聯(lián)考試題含解析
- 無人機(jī)航空測(cè)繪與后期制作 課件 第十二課時(shí) 現(xiàn)場(chǎng)飛行流程
- 2024年梅州市大埔縣重點(diǎn)中學(xué)小升初語文入學(xué)考試卷含答案
- (正式版)JBT 14449-2024 起重機(jī)械焊接工藝評(píng)定
- 2022-2023學(xué)年北京市東城區(qū)高二(下)期末化學(xué)試卷(含解析)
- 防溺水老師培訓(xùn)課件
- 《植物生長(zhǎng)與環(huán)境》課程標(biāo)準(zhǔn)(含課程思政)
- 鐵路行車組織(高職)全套教學(xué)課件
- 注塑標(biāo)準(zhǔn)成型條件表電子表格模板
- 道閘系統(tǒng)施工方案
- 配置管理與漏洞修復(fù)
評(píng)論
0/150
提交評(píng)論