第9章邏輯程序設(shè)計課件

內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言1內(nèi)容1.邏輯和邏輯程序11.邏輯和邏輯程序邏輯程序設(shè)計邏輯程序設(shè)計支持說明性程序設(shè)計范型根據(jù)問題的高層描述來構(gòu)建程序告訴計算機“什么是真的”和“需要做什么”，而不是“怎樣做”。程序員把精力放在問題（封閉的問題世界）的描述上，而不是寫一些諸如“下一步做什么”之類的底層算法指令。21.邏輯和邏輯程序邏輯程序設(shè)計21.邏輯和邏輯程序謂詞演算邏輯程序設(shè)計中使用的邏輯【例】用謂詞表示的邏輯命題0是自然數(shù)2是自然數(shù)對于所有的x，如果x是自然數(shù)，則x+1也是自然數(shù)-1是自然數(shù)natural(0)natural(2)natural(-1)forallx,natural(x)natural(successor(x))二值邏輯31.邏輯和邏輯程序謂詞演算natural(0)natural1.邏輯和邏輯程序謂詞演算謂詞演算元素①常量：數(shù)或名稱②謂詞：值域為真或假的函數(shù)名③函數(shù)：區(qū)別謂詞的其余函數(shù)④變量：不確定值⑤連接詞：⑥量詞：描述變量⑦標(biāo)點符號：(),;a為真時b為真ab存在量詞全稱量詞natural(0)forallx,natural(x)natural(successor(x))41.邏輯和邏輯程序謂詞演算a為真時b為真ab存在量詞全稱量詞1.邏輯和邏輯程序謂詞演算一階謂詞演算（first-orderpredicatecalculus）全稱量化變量和存在量化變量僅可以指向論域中的對象，而不允許指向謂詞和函數(shù)謂詞和函數(shù)的參數(shù)是項常量變量函數(shù)51.邏輯和邏輯程序謂詞演算51.邏輯和邏輯程序謂詞演算推理規(guī)則【例】有如下三段論：“所有人會死；蘇格拉底是人，所以蘇格拉底會死。”

,abab61.邏輯和邏輯程序謂詞演算,abab6【例】證明：Fido會死①Fido是狗②所有的狗都是動物③所有的動物都會死證明①所有的狗都是動物：②Fido是狗：③取式假言推理和{fido/X}：④所有的動物都會死：⑤取式假言推理和{fido/Y}：

謂詞形式1.邏輯和邏輯程序7【例】證明：Fido會死謂詞形式1.邏輯和邏輯程序71.邏輯和邏輯程序謂詞演算推理規(guī)則為了應(yīng)用推理規(guī)則進(jìn)行推理，推理機必須能夠判斷兩個表達(dá)式是否相同（匹配）。這種尋找項對變量的置換，使謂詞一致的過程叫做合一的過程（合一算法）項：常量、函數(shù)或其他變量公式集F={man(X)，man(socrates)}中的兩個公式是可合一的，置換θ=scorates/X是該公式集的一個合一。81.邏輯和邏輯程序謂詞演算81.邏輯和邏輯程序謂詞演算推理規(guī)則①化簡式（與消除）：P∧Q=>P和P∧Q=>Q②附加式：P=>P∨Q和Q=>P∨Q③析取三段論：P，PVQ=>Q④取式假言推理：P，P→Q=>Q⑤拒式假言推理：Q，P→Q=>P⑥假言三段論：P→Q，Q→R=>P→R⑦二難推理：P∨Q，P→R，Q→R=>R⑧全稱固化：（x）P（x）=>P（a）⑨存在固化：（x）P（x）=>P（a）91.邏輯和邏輯程序謂詞演算91.邏輯和邏輯程序謂詞演算推理規(guī)則自然演繹推理從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程101.邏輯和邏輯程序謂詞演算10內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言11內(nèi)容1.邏輯和邏輯程序112.Horn子句Horn子句是形如的命題其中a只能是簡單的不包含連接詞的命題a的數(shù)量可以為零注意：Horn子句能夠被用來表示大多數(shù)的邏輯命題，但不是全部沒有or和量詞所有的a為真則b真b恒真事實122.Horn子句Horn子句是形如沒有or和量詞所有的【例】證明：Fido會死①所有的狗都是動物②Fido是狗③所有的動物都會死謂詞形式子句形式2.Horn子句隱式全稱約束13【例】證明：Fido會死謂詞形式子句形式2.Horn子句2.Horn子句目標(biāo)驅(qū)動自動推理系統(tǒng)，反向使用Horn子句詢問(目標(biāo)語句)子句體子句頭無頭子句對b的定義142.Horn子句目標(biāo)驅(qū)動子句體子句頭無頭子句對b的定義1內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言15內(nèi)容1.邏輯和邏輯程序153.歸結(jié)與合一歸結(jié)(消解)兩個Horn子句第一個Horn子句的頭與第二個子句體的一個命題匹配則第二個子句中的命題可以被替換為第一個子句的體【例】bi匹配a163.歸結(jié)與合一歸結(jié)(消解)bi匹配a163.歸結(jié)與合一歸結(jié)過程(目標(biāo)驅(qū)動)用已知子句的頭部來匹配無頭子句體中的一個目標(biāo)如果成功，用已知子句的體替換被匹配的目標(biāo)(歸結(jié))，建立新的子句繼續(xù)用同樣的方式修改目標(biāo)系列這些新的目標(biāo)被稱為子目標(biāo)如果成功消除了所有的目標(biāo)，則初始命題得證詢問173.歸結(jié)與合一歸結(jié)過程(目標(biāo)驅(qū)動)詢問173.歸結(jié)與合一子句集“死狗”問題的歸結(jié)證明□合一要匹配包含變量的語句必須令變量等于某項183.歸結(jié)與合一子句集“死狗”問題的歸結(jié)證明□合一要匹配包含3歸結(jié)與合一必須解決的問題邏輯程序系統(tǒng)必須使用一個高效執(zhí)行的算法，規(guī)定求解目標(biāo)應(yīng)用子句的順序193歸結(jié)與合一必須解決的問題193歸結(jié)與合一203歸結(jié)與合一20內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言21內(nèi)容1.邏輯和邏輯程序21Prolog語言概述Prolog（ProgramminginLogic）誕生于20世紀(jì)70年代初法國馬賽大學(xué)作為自然語言理解項目的一部分研制成功目前，愛丁堡大學(xué)開發(fā)的Prolog版本使用最為廣泛主要應(yīng)用于人工智能領(lǐng)域相關(guān)問題的求解易于表達(dá)人的邏輯思維迄今最能體現(xiàn)邏輯程序設(shè)計思想的邏輯編程語言“說明式”的語言；采用一階謂詞演算說明（描述）問題知識庫（事實和規(guī)則）的描述采用子句（Clause）形式Prolog是目前唯一廣泛使用的邏輯程序設(shè)計語言22Prolog語言概述Prolog（ProgrammingiProlog語言概述SWI-Prolog/安裝文件（注意順序安裝）（1）SWI-PrologforMS-Windows（2）SWI-Prolog-Editorhttp://lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html

23Prolog語言概述SWI-Prolog23內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言4.1符號和數(shù)據(jù)結(jié)構(gòu)4.2Prolog的執(zhí)行4.3合一4.4Prolog的搜索策略4.5循環(huán)和控制結(jié)構(gòu)24內(nèi)容1.邏輯和邏輯程序244.1符號和數(shù)據(jù)結(jié)構(gòu)基本符號常量以小寫字母開始的一串字母、數(shù)字、下劃線或用單引號界定的一串任何可打印的ASCII字符。變量以大寫字母開始一串字母、數(shù)字和下劃線；下劃線（_）表示匿名變量；連接詞，//and;//or:-//implementation254.1符號和數(shù)據(jù)結(jié)構(gòu)基本符號254.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)（謂詞/復(fù)雜項）

vertical(line(point(X,Y),point(X,Z))).264.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)264.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)表（List）：有限的元素序列。由方括號[]之間由逗號隔開的有序元素組成。表中的元素可以是原子、結(jié)構(gòu)、或任何其它的項，包括表在內(nèi)。274.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)274.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)表任何非空的表=表頭（head）+表尾（tail）表頭：表的第一個元素；表尾：除第一個元素，表的其它元素組成的表。Prolog內(nèi)部謂詞“|”用于將表分解為表頭和表尾；靈活使用|是寫好Prolog表處理程序的關(guān)鍵！284.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)284.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)表謂詞“|”的使用294.1符號和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)29內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言4.1符號和數(shù)據(jù)結(jié)構(gòu)4.2Prolog的執(zhí)行4.3合一4.4Prolog的搜索策略4.5循環(huán)和控制結(jié)構(gòu)30內(nèi)容1.邏輯和邏輯程序304.2Prolog的執(zhí)行Prolog程序運行通過提問查詢知識庫使用分號（；）查詢多個解（multipleanswers）314.2Prolog的執(zhí)行Prolog程序運行31內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言4.1符號和數(shù)據(jù)結(jié)構(gòu)4.2Prolog的執(zhí)行4.3合一4.4Prolog的搜索策略4.5循環(huán)和控制結(jié)構(gòu)32內(nèi)容1.邏輯和邏輯程序324.3合一合一對變量初始化或者分配存儲空間和值的過程在某種意義上是將兩個項等同的過程?-a=a.yes//常量與自己合一?-a=b.no//常量不能與其他常量合一?-foo(a,b)=foo(a,b).yes//結(jié)構(gòu)遞歸合一Prolog中“=”表示合一334.3合一合一Prolog中“=”表示合一33合一?-X=a.X=a;//變量和常量合一no//僅此一次合一?-foo(a,b)=foo(X,b).X=a;//參數(shù)合一no//只有是一種可能?-A=B.A=_G206B=_G206;no內(nèi)部共享變量4.3合一34合一內(nèi)部共享變量4.3合一344.3合一合一算法①如果Term1和Term2是常量，那么當(dāng)且僅當(dāng)Term1和Term2是相同的原子或整數(shù)；②如果Term1是變量，Term2是任何類型的項，那么Term1實例化為Term2；注：如果Term2也是變量，互相實例化，共享值。③如果Term1和Term2都是結(jié)構(gòu)，兩者合一，當(dāng)且僅當(dāng)（a）兩者有相同的算符（謂詞）；（b）兩者對應(yīng)的參數(shù)匹配，即能夠遞歸地合一；（c）變量實例化必須保持一致性；④當(dāng)滿足前面三種情況時，兩者項合一。354.3合一合一算法354.3合一【思考】Prolog實現(xiàn)合一操作時是否使用標(biāo)準(zhǔn)的合一算法？

老版本的Prolog實現(xiàn):Not

enough

memory

to

complete

query!現(xiàn)代版本的Prolog實現(xiàn)： X

=

father(father(father(father(father(father

(father(father(father(father(father(father

(father(father(father(father(father(father

(father(father(father(father(father(father(father(father(father(father(father(fatherX

=

father(father(father(father(...))))))))SICStusPrologSWIPrologX

=

father(**)364.3合一【思考】X

=

father(father(fa4.3合一利用合一簡化操作cons表的構(gòu)造與選擇向后運行消解自動產(chǎn)生合一需要合一的模式寫入子句頭374.3合一利用合一簡化操作向后運行消解自動產(chǎn)生合一需要合一4.3合一利用合一簡化操作append拼接兩張表ABYB+YWA輸入:W:結(jié)果:+384.3合一利用合一簡化操作ABYB+YWA輸入:W:結(jié)果:4.3合一利用合一簡化操作append394.3合一利用合一簡化操作394.3合一利用合一簡化操作append向后運行404.3合一利用合一簡化操作向后運行404.3合一利用合一簡化操作reverse逆置表中元素414.3合一利用合一簡化操作41內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言4.1符號和數(shù)據(jù)結(jié)構(gòu)4.2Prolog的執(zhí)行4.3合一4.4Prolog的搜索策略4.5循環(huán)和控制結(jié)構(gòu)42內(nèi)容1.邏輯和邏輯程序424.4Prolog的搜索策略搜索策略搜索方向—基于目標(biāo)導(dǎo)向搜索類型—深度優(yōu)先搜索從左至右考慮子目標(biāo)從上到下考慮子句合一失敗，如何控制程序繼續(xù)進(jìn)行求解問題？回溯Prolog內(nèi)部最基本的自動的控制流機制需要搜索更多解時，如何控制程序繼續(xù)進(jìn)行求解問題？分號表示結(jié)束當(dāng)前合一，回溯查找其它可滿足的解434.4Prolog的搜索策略搜索策略43回溯：系統(tǒng)地穿越狀態(tài)空間的所有路徑的一種技術(shù)4.4Prolog的搜索策略44回溯：系統(tǒng)地穿越狀態(tài)空間的所有路徑的一種技術(shù)4.4Prol4.4Prolog的搜索策略【例1】454.4Prolog的搜索策略【例1】454.4Prolog的搜索策略【例1】464.4Prolog的搜索策略【例1】464.4Prolog的搜索策略【例2】匹配失敗474.4Prolog的搜索策略【例2】匹配失敗474.4Prolog的搜索策略【例2】484.4Prolog的搜索策略【例2】48【例3】4.4Prolog的搜索策略49【例3】4.4Prolog的搜索策略49【例3】4.4Prolog的搜索策略'DRNO‘/Title50【例3】4.4Prolog的搜索策略'DRNO‘/Tit【例3】4.4Prolog的搜索策略'DRNO‘/Title匹配失敗51【例3】4.4Prolog的搜索策略'DRNO‘/Tit【例3】4.4Prolog的搜索策略'DRNO‘/Title310/Length52【例3】4.4Prolog的搜索策略'DRNO‘/Tit【例3】4.4Prolog的搜索策略'DRNO‘/Title310/Length53【例3】4.4Prolog的搜索策略'DRNO‘/Tit4.4Prolog的搜索策略【例4】C=X=_G206seattle/_G206失敗并回溯544.4Prolog的搜索策略【例4】C=X=_G206se4.4Prolog的搜索策略【例4】C=X=_G206seattle/_G206rochester/_G206554.4Prolog的搜索策略【例4】C=X=_G206se4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Y解1564.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解2解1574.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解2解1b/X,c/Za/Y解3584.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略【例5】X=_G206,Y=_G207a/X,c/Za/Yb/Y解2解1b/X,c/Za/Y解3b/Y解4594.4Prolog的搜索策略【例5】X=_G206,Y=4.4Prolog的搜索策略e/X,b/Y【例6】604.4Prolog的搜索策略e/X,b/Y【例6】604.4Prolog的搜索策略e/X,b/Ye/X,b/Yd/Zd/Z【例6】614.4Prolog的搜索策略e/X,b/Ye/X,b4.4Prolog的搜索策略e/X,b/Ye/X,b/Yd/Zd/Zd/X,b/Yc/Z【例6】624.4Prolog的搜索策略e/X,b/Ye/X,b4.4Prolog的搜索策略Prolog是否是純邏輯式編程語言？634.4Prolog的搜索策略Prolog是否是純邏輯式編程4.4Prolog的搜索策略【例7】bob/Yamy/X,bob/Zbob/X,bob/Y644.4Prolog的搜索策略【例7】bob/Yamy/X,4.4Prolog的搜索策略【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/X654.4Prolog的搜索策略【例7】bob/Yamy/X,4.4Prolog的搜索策略【例7】bob/Yamy/X,bob/Zbob/X,bob/Ybob/Xbob/X664.4Prolog的搜索策略【例7】bob/Yamy/X,4.4Prolog的搜索策略【例8】bob/YX/Z,bob/Y674.4Prolog的搜索策略【例8】bob/YX/Z,b4.4Prolog的搜索策略【例9】bob/X684.4Prolog的搜索策略【例9】bob/X684.4Prolog的搜索策略【例9】bob/Xbob/Ybob/Zamy/X694.4Prolog的搜索策略【例9】bob/Xbob/Yb4.4Prolog的搜索策略【例9】bob/Xbob/Yamy/XZ`/X,bob/Y704.4Prolog的搜索策略【例9】bob/Xbob/Ya內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言4.1符號和數(shù)據(jù)結(jié)構(gòu)4.2Prolog的執(zhí)行4.3合一4.4Prolog的搜索策略4.5循環(huán)和控制結(jié)構(gòu)71內(nèi)容1.邏輯和邏輯程序714.5循環(huán)和控制結(jié)構(gòu)強制回溯實現(xiàn)循環(huán)和重復(fù)搜索724.5循環(huán)和控制結(jié)構(gòu)強制回溯724.5循環(huán)和控制結(jié)構(gòu)截斷回溯停止對整棵搜索樹的遍歷734.5循環(huán)和控制結(jié)構(gòu)截斷回溯734.5循環(huán)和控制結(jié)構(gòu)Prologcut（截斷/阻止回溯）機制使用內(nèi)部無參謂詞（?。?；可以作為子目標(biāo)放在規(guī)則子句的體內(nèi)；

解釋：①程序調(diào)用cut總是成功；②當(dāng)某個子目標(biāo)失敗回溯時，不允許越過！回溯。a:-b,c,d,e,!,f,g,h,I,j.

a:-b,c,d,e,!,f,g,h,I,j.a:-b,c,d,e,!,f,g,h,I,j.立即失敗SucceedFailRedoBacktrack744.5循環(huán)和控制結(jié)構(gòu)Prologcut（截斷/阻止回溯）1/X1/X2/X3/X【例1】751/X1/X2/X3/X【例1】751/X1/X【例2】761/X1/X【例2】76【例3】1/X1/Y2/Y3/Y0/X,0/Y