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

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

謂詞形式1.邏輯和邏輯程序7【例】證明：Fido會(huì)死謂詞形式1.邏輯和邏輯程序71.邏輯和邏輯程序謂詞演算推理規(guī)則為了應(yīng)用推理規(guī)則進(jìn)行推理，推理機(jī)必須能夠判斷兩個(gè)表達(dá)式是否相同（匹配）。這種尋找項(xiàng)對(duì)變量的置換，使謂詞一致的過程叫做合一的過程（合一算法）項(xiàng)：常量、函數(shù)或其他變量公式集F={man(X)，man(socrates)}中的兩個(gè)公式是可合一的，置換θ=scorates/X是該公式集的一個(gè)合一。81.邏輯和邏輯程序謂詞演算81.邏輯和邏輯程序謂詞演算推理規(guī)則①化簡(jiǎn)式（與消除）：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ī)則自然演繹推理從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程101.邏輯和邏輯程序謂詞演算10內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言11內(nèi)容1.邏輯和邏輯程序112.Horn子句Horn子句是形如的命題其中a只能是簡(jiǎn)單的不包含連接詞的命題a的數(shù)量可以為零注意：Horn子句能夠被用來表示大多數(shù)的邏輯命題，但不是全部沒有or和量詞所有的a為真則b真b恒真事實(shí)122.Horn子句Horn子句是形如沒有or和量詞所有的【例】證明：Fido會(huì)死①所有的狗都是動(dòng)物②Fido是狗③所有的動(dòng)物都會(huì)死謂詞形式子句形式2.Horn子句隱式全稱約束13【例】證明：Fido會(huì)死謂詞形式子句形式2.Horn子句2.Horn子句目標(biāo)驅(qū)動(dòng)自動(dòng)推理系統(tǒng)，反向使用Horn子句詢問(目標(biāo)語句)子句體子句頭無頭子句對(duì)b的定義142.Horn子句目標(biāo)驅(qū)動(dòng)子句體子句頭無頭子句對(duì)b的定義1內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言15內(nèi)容1.邏輯和邏輯程序153.歸結(jié)與合一歸結(jié)(消解)兩個(gè)Horn子句第一個(gè)Horn子句的頭與第二個(gè)子句體的一個(gè)命題匹配則第二個(gè)子句中的命題可以被替換為第一個(gè)子句的體【例】bi匹配a163.歸結(jié)與合一歸結(jié)(消解)bi匹配a163.歸結(jié)與合一歸結(jié)過程(目標(biāo)驅(qū)動(dòng))用已知子句的頭部來匹配無頭子句體中的一個(gè)目標(biāo)如果成功，用已知子句的體替換被匹配的目標(biāo)(歸結(jié))，建立新的子句繼續(xù)用同樣的方式修改目標(biāo)系列這些新的目標(biāo)被稱為子目標(biāo)如果成功消除了所有的目標(biāo)，則初始命題得證詢問173.歸結(jié)與合一歸結(jié)過程(目標(biāo)驅(qū)動(dòng))詢問173.歸結(jié)與合一子句集“死狗”問題的歸結(jié)證明□合一要匹配包含變量的語句必須令變量等于某項(xiàng)183.歸結(jié)與合一子句集“死狗”問題的歸結(jié)證明□合一要匹配包含3歸結(jié)與合一必須解決的問題邏輯程序系統(tǒng)必須使用一個(gè)高效執(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é)作為自然語言理解項(xiàng)目的一部分研制成功目前，愛丁堡大學(xué)開發(fā)的Prolog版本使用最為廣泛主要應(yīng)用于人工智能領(lǐng)域相關(guān)問題的求解易于表達(dá)人的邏輯思維迄今最能體現(xiàn)邏輯程序設(shè)計(jì)思想的邏輯編程語言“說明式”的語言；采用一階謂詞演算說明（描述）問題知識(shí)庫（事實(shí)和規(guī)則）的描述采用子句（Clause）形式Prolog是目前唯一廣泛使用的邏輯程序設(shè)計(jì)語言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符號(hào)和數(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符號(hào)和數(shù)據(jù)結(jié)構(gòu)基本符號(hào)常量以小寫字母開始的一串字母、數(shù)字、下劃線或用單引號(hào)界定的一串任何可打印的ASCII字符。變量以大寫字母開始一串字母、數(shù)字和下劃線；下劃線（_）表示匿名變量；連接詞，//and;//or:-//implementation254.1符號(hào)和數(shù)據(jù)結(jié)構(gòu)基本符號(hào)254.1符號(hào)和數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)（謂詞/復(fù)雜項(xiàng)）

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

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

enough

memory

to

complete

query!現(xiàn)代版本的Prolog實(shí)現(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合一利用合一簡(jiǎn)化操作cons表的構(gòu)造與選擇向后運(yùn)行消解自動(dòng)產(chǎn)生合一需要合一的模式寫入子句頭374.3合一利用合一簡(jiǎn)化操作向后運(yùn)行消解自動(dòng)產(chǎn)生合一需要合一4.3合一利用合一簡(jiǎn)化操作append拼接兩張表ABYB+YWA輸入:W:結(jié)果:+384.3合一利用合一簡(jiǎn)化操作ABYB+YWA輸入:W:結(jié)果:4.3合一利用合一簡(jiǎn)化操作append394.3合一利用合一簡(jiǎn)化操作394.3合一利用合一簡(jiǎn)化操作append向后運(yùn)行404.3合一利用合一簡(jiǎn)化操作向后運(yùn)行404.3合一利用合一簡(jiǎn)化操作reverse逆置表中元素414.3合一利用合一簡(jiǎn)化操作41內(nèi)容1.邏輯和邏輯程序2.Horn子句3.歸結(jié)與合一4.Prolog語言4.1符號(hào)和數(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)部最基本的自動(dòng)的控制流機(jī)制需要搜索更多解時(shí)，如何控制程序繼續(xù)進(jìn)行求解問題？分號(hào)表示結(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符號(hào)和數(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)強(qiáng)制回溯實(shí)現(xiàn)循環(huán)和重復(fù)搜索724.5循環(huán)和控制結(jié)構(gòu)強(qiáng)制回溯724.5循環(huán)和控制結(jié)構(gòu)截?cái)嗷厮萃Ｖ箤?duì)整棵搜索樹的遍歷734.5循環(huán)和控制結(jié)構(gòu)截?cái)嗷厮?34.5循環(huán)和控制結(jié)構(gòu)Prologcut（截?cái)?阻止回溯）機(jī)制使用內(nèi)部無參謂詞（！）；可以作為子目標(biāo)放在規(guī)則子句的體內(nèi)；

解釋：①程序調(diào)用cut總是成功；②當(dāng)某個(gè)子目標(biāo)失敗回溯時(shí)，不允許越過！回溯。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（截?cái)?阻止回溯）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