計(jì)算機(jī)軟件及應(yīng)用第6章 邏輯程序設(shè)計(jì)語(yǔ)言范型邏輯程序設(shè)計(jì)理論基礎(chǔ)

10七月2023程序設(shè)計(jì)語(yǔ)言范型

ProgrammingLanguagesParadigms教師：張榮華華北電力大學(xué)計(jì)算機(jī)系軟件教研室〔保定〕

邏輯程序設(shè)計(jì)語(yǔ)言范型邏輯程序設(shè)計(jì)理論根底第三局部第六章邏輯程序設(shè)計(jì)理論根底第六章-3內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示2.1謂詞演算2.2基于謂詞演算的知識(shí)表示2.3謂詞演算推理規(guī)那么3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-41.邏輯程序設(shè)計(jì)概述邏輯程序設(shè)計(jì)邏輯程序設(shè)計(jì)支持說(shuō)明性程序設(shè)計(jì)范型根據(jù)問題的高層描述來(lái)構(gòu)建程序告訴計(jì)算機(jī)“什么是真的〞和“需要做什么〞，而不是“怎樣做〞。程序員把精力放在問題〔封閉的問題世界〕的描述上，而不是寫一些諸如“下一步做什么〞之類的底層算法指令。Prolog是目前唯一廣泛使用的邏輯程序設(shè)計(jì)語(yǔ)言Prolog〔ProgramminginLogic〕20世紀(jì)70年代初、法國(guó)馬賽大學(xué)主要應(yīng)用于人工智能〔人類智能活動(dòng)的模擬〕領(lǐng)域相關(guān)問題的求解。易于表達(dá)人的邏輯思維邏輯程序設(shè)計(jì)理論根底第六章-51.邏輯程序設(shè)計(jì)概述【例1】：水平線與垂直線問題。使用兩個(gè)謂詞：vertical/2和horizontal/2vertical(line(point(X,Y),point(X,Z))).

horizontal(line(point(X,Y),point(Z,Y))).

vertical(line(point(1,1),point(1,3))).

yes

事實(shí)查詢/目標(biāo)horizontal(line(point(1,1),point(2,Y))).

Y

=

1

;

nohorizontal(line(point(2,3),P)).

P

=

point(_G434,3)

;

no邏輯程序設(shè)計(jì)理論根底第六章-61.邏輯程序設(shè)計(jì)概述【例2】求解以下六個(gè)英語(yǔ)單詞的縱橫字謎問題。abalone,abandon,anagram,connect,elegant,enhance事實(shí)規(guī)那么邏輯程序設(shè)計(jì)理論根底第六章-71.邏輯程序設(shè)計(jì)概述aabloneanagramocnnectaadneeeathneaadnbonleeatngnehnecaaaoeaarmcnet查詢/目標(biāo)邏輯程序設(shè)計(jì)理論根底第六章-8內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示2.1謂詞演算2.2基于謂詞演算的知識(shí)表示2.3謂詞演算推理規(guī)那么3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-92.知識(shí)的表示知識(shí)閾值理論知識(shí)是一切智能行為的根底智能取決于知識(shí)的數(shù)量及其可運(yùn)用的程度。要使計(jì)算機(jī)具有智能，就必須使它具有知識(shí)。知識(shí)表示方法〔知識(shí)表示語(yǔ)言〕謂詞演算〔一階謂詞邏輯表示法〕產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法框架表示法腳本表示法面向?qū)ο蟊硎痉ǖ鹊取壿嫵绦蛟O(shè)計(jì)理論根底第六章-102.知識(shí)的表示選擇知識(shí)表示方法的重要性【例】缺角棋盤問題邏輯程序設(shè)計(jì)理論根底第六章-11內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示2.1謂詞演算2.2基于謂詞演算的知識(shí)表示2.3謂詞演算推理規(guī)那么3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-122.1謂詞演算這里討論的謂詞演算⑴一階謂詞演算〔first-orderpredicatecalculus〕全稱量化變量和存在量化變量?jī)H可以指向論域中的對(duì)象，而不允許指向謂詞和函數(shù)。這樣的謂詞演算語(yǔ)言稱為一階謂詞演算。

⑵二值邏輯不討論其它邏輯形態(tài)多值邏輯、多維邏輯、缺省邏輯、動(dòng)態(tài)邏輯邏輯程序設(shè)計(jì)理論根底第六章-132.1謂詞演算【例】用謂詞表示命題P：星期二下了雨。謂詞表示：weather〔tuesday，rain〕允許使用變量建立關(guān)于實(shí)體類的通用斷言weather〔X，rain〕謂詞演算符號(hào)〔項(xiàng)〕〔以Prolog語(yǔ)言為例〕由以下三局部組成：①英文字母，包括大寫和小寫。②數(shù)字0，1……9。③下劃線_。以字母開始，后面可以跟這些合法字符的任意序列。邏輯程序設(shè)計(jì)理論根底第六章-142.1謂詞演算謂詞演算符號(hào)〔項(xiàng)〕〔以Prolog語(yǔ)言為例〕①真值符號(hào)：true和false〔保存符號(hào)〕②變量符號(hào):以大寫字母開始的符號(hào)表達(dá)式。③常量符號(hào):以小寫字母開始的符號(hào)表達(dá)式。④函數(shù)符號(hào):以小寫字母開始的符號(hào)表達(dá)式。⑤謂詞符號(hào)：以小寫字母開始的符號(hào)表達(dá)式。例如：likes〔george，kate〕%likes/2likes〔george，sarah，tuesday〕%likes/3likes〔X，kate〕friends〔father_of(david)，father_of(kate)〕邏輯程序設(shè)計(jì)理論根底第六章-15內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示2.1謂詞演算2.2基于謂詞演算的知識(shí)表示2.3謂詞演算推理規(guī)那么3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-162.2基于謂詞演算的知識(shí)表示【例1】事實(shí)性知識(shí)：friends〔father_of(david)，father_of(kate)〕【例2】規(guī)那么性知識(shí)：“所有的教師都有自己的學(xué)生〞⑴根據(jù)所表示的知識(shí)定義謂詞teacher〔X〕：表示X是教師student〔Y〕：表示Y是學(xué)生teach〔X，Y〕：表示X是Y的老師⑵用2個(gè)量詞和5個(gè)連接詞把這些謂詞連結(jié)成語(yǔ)句

邏輯程序設(shè)計(jì)理論根底第六章-172.2基于謂詞演算的知識(shí)表示【例3】機(jī)器人移盒子問題設(shè)在一房間里，C處有一個(gè)機(jī)器人，A和B處各有一張桌子，分別稱為A桌和B桌，A桌子上有一盒子，如以下圖所示。要求機(jī)器人從C處出發(fā)把盒子從A桌上拿到B桌上，然后再回到C處。請(qǐng)用謂詞邏輯來(lái)描述機(jī)器人的行動(dòng)過程。

ABCStartstateAT（robot,C）EMPTY（robot）ON（box，A）TABLE（A）TABLE（B）GoalstateAT（robot,C）EMPTY（robot）ON（box，B）TABLE（A）TABLE（B）使用規(guī)那么！操作前提條件刪除list項(xiàng)增加list項(xiàng)Goto(x,y)AT（robot,x）AT（robot,x）AT（robot,y）Pickup(x)ON(box,x),TABLE(x),AT(robot,x),Empty(robot)Empty(robot),ON(box,x)HOLDS(robot,box)Setdown(x)HOLDS(robot,box)AT（robot,x),TABLE(x)HOLDS(robot,box)ON(box,x),Empty(robot)邏輯程序設(shè)計(jì)理論根底第六章-19謂詞邏輯表示的應(yīng)用StartStateAT（robot,c）EMPTY（robot）ON（box，A）TABLE（A）TABLE（B）GOTO(x,y)C/x,A/yState1AT(robot,A)EMPTY(robot)ON（box，A）TABLE（A）TABLE（B）State2AT(robot,A)HOLDS(robot,box)TABLE（A）TABLE（B）StartPICKUP(x)A/xGOTO(x,y)A/x,B/yState3AT(robot,B)HOLDS(robot,box)TABLE（A）TABLE（B）State4AT(robot,B)EMPTY（robot）ON（box，B）TABLE（A）TABLE（B）SETDOWN(x)B/xGOTO(x,y)B/x,C/yGoalStateAT(robot,C)EMPTY（robot）ON（box，B）TABLE（A）TABLE（B）邏輯程序設(shè)計(jì)理論根底第六章-20內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示2.1謂詞演算2.2基于謂詞演算的知識(shí)表示2.3謂詞演算推理規(guī)那么3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-212.3謂詞演算推理規(guī)那么謂詞公式的永真蘊(yùn)含性對(duì)謂詞公式P和Q，如果P→Q永真，那么稱P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作P=>Q。①化簡(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〕邏輯程序設(shè)計(jì)理論根底第六章-22內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-233.知識(shí)的利用知識(shí)的利用：基于對(duì)某個(gè)封閉世界已表示的知識(shí)的處理，以求解特定的問題。①搜索：根據(jù)問題的實(shí)際情況，不斷尋找可利用知識(shí)，從而構(gòu)造一條代價(jià)最小的推理路線，使問題得以解決的過程，稱為搜索。盲目搜索：深度優(yōu)先搜索、寬度優(yōu)先搜索；啟發(fā)式搜索：最正確優(yōu)先搜索、A*算法；②推理：按照某種策略從事實(shí)出發(fā)去推出結(jié)論的過程——問題求解的過程〔思維過程〕。自然演繹推理歸結(jié)演繹推理〔Prolog語(yǔ)言采用的推理機(jī)制，重點(diǎn)〕合一〔匹配〕操作；推理〔搜索〕方向：深度優(yōu)先；回溯機(jī)制；邏輯程序設(shè)計(jì)理論根底第六章-24內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-253.1搜索搜索的根底是圖論例：九宮游戲的狀態(tài)空間圖邏輯程序設(shè)計(jì)理論根底第六章-26基于圖搜索的問題求解程序問題求解程序能否被賦予可靠的機(jī)制〔不犯任何錯(cuò)誤〕穿越狀態(tài)空間到達(dá)預(yù)期的目標(biāo)狀態(tài)，并建立解路徑？回溯：系統(tǒng)地穿越狀態(tài)空間的所有路徑的一種技術(shù)。邏輯程序設(shè)計(jì)理論根底第六章-273.1搜索對(duì)假想狀態(tài)空間的深度優(yōu)先搜索〔回溯〕邏輯程序設(shè)計(jì)理論根底第六章-28內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-293.2.1置換與合一【例】有如下三段論：“所有人會(huì)死；蘇格拉底是人，所以蘇格拉底會(huì)死。〞

這種尋找項(xiàng)對(duì)變量的置換，使謂詞一致的過程叫做合一的過程〔合一算法〕項(xiàng)：常量、函數(shù)或其他變量公式集F={man(X)，man(socrates)}中的兩個(gè)公式是可合一的，置換θ=scorates/X是該公式集的一個(gè)合一。為了應(yīng)用推理規(guī)那么進(jìn)行推理，推理機(jī)必須能夠判斷兩個(gè)表達(dá)式是否相同〔匹配〕。邏輯程序設(shè)計(jì)理論根底第六章-303.2.1置換與合一合一算法unify〔E1，E2〕計(jì)算兩個(gè)謂詞演算公式間的合一置換。返回合一置換或常量FAIL〔當(dāng)不可能合一時(shí)〕【例】使用用列表語(yǔ)法表示謂詞公式語(yǔ)法。E：p〔f〔a〕，g〔X，Y〕〕〔p〔fa〕〔gXY〕〕邏輯程序設(shè)計(jì)理論根底第六章-34內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-35

3.2.2自然演繹推理自然演繹推理從一組為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)那么推出結(jié)論的過程。①化簡(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〕邏輯程序設(shè)計(jì)理論根底第六章-36

3.2.2自然演繹推理【例1】基于謂詞邏輯演算的財(cái)務(wù)參謀該財(cái)務(wù)參謀的功能是幫助用戶根據(jù)個(gè)人的年收入及已存款數(shù)量決策應(yīng)該繼續(xù)存款還是向股票市場(chǎng)投資。投資策略的標(biāo)準(zhǔn)如下：①存款數(shù)額還不充足的個(gè)體始終該把提高存款額作為他們的首選目標(biāo)，無(wú)論他們的收入如何。②具有充足存款和充足收入的個(gè)體應(yīng)該考慮風(fēng)險(xiǎn)較高但潛在投資收益也更高的股票市場(chǎng)。③收入較低并且已經(jīng)具有充足存款的個(gè)體可以考慮把他們的剩余收入在存款和股票間分?jǐn)偅员慵饶芴岣叽婵顢?shù)額又能嘗試通過股票提高收入。存款和收入的充足性可以由個(gè)體要供養(yǎng)的人數(shù)決定。充足的存款：供養(yǎng)一個(gè)人至少要在銀行存款5000美元。充足的收入：收入必須是穩(wěn)定的，而且年收入至少是15000美元，在加額外的給每個(gè)要供養(yǎng)的人4000美元。minsavings(X)≡5000*Xminincome(X)≡15000+(4000*X)其中：初始邏輯系統(tǒng)〔知識(shí)庫(kù)〕：12.income(inadequate)13.savings_account(adequate)X邏輯程序設(shè)計(jì)理論根底第六章-38

3.2.2自然演繹推理推理方向①數(shù)據(jù)驅(qū)動(dòng)搜索〔data-drivensearch〕正向追索〔forwardchaining〕，問題求解程序從問題的給定事實(shí)和改變狀態(tài)的合法移動(dòng)和規(guī)那么的集合入手。然后把規(guī)那么應(yīng)用到事實(shí)產(chǎn)生新的事實(shí)，接下來(lái)新的事實(shí)又被規(guī)那么用來(lái)產(chǎn)生更多新的事實(shí)，搜索如此進(jìn)行下去，直到產(chǎn)生滿足目標(biāo)條件的一條路徑。②目標(biāo)驅(qū)動(dòng)搜索〔goal-drivensearch〕反向追索〔backwardchaining〕，從求解的目標(biāo)著手。先分析怎樣使用合法的移動(dòng)來(lái)產(chǎn)生這個(gè)目標(biāo)，并求出要應(yīng)用這些移動(dòng)必須具備的條件。這些條件成為要搜索的新目標(biāo)〔子目標(biāo)〕。然后繼續(xù)反向追溯相繼的子目標(biāo)，直至返回到問題中的事實(shí)。這樣便找到了從問題到目標(biāo)的移動(dòng)規(guī)那么鏈。邏輯程序設(shè)計(jì)理論根底第六章-39

3.2.2自然演繹推理【例2】基于謂詞邏輯演算的財(cái)務(wù)參謀基于目標(biāo)驅(qū)動(dòng)的帶回溯的深度優(yōu)先搜索X邏輯程序設(shè)計(jì)理論根底第六章-40

3.2.2自然演繹推理假定某個(gè)投資個(gè)體要供養(yǎng)2人，有20000美元存款，30000美元穩(wěn)定收入。咨詢的目標(biāo)找到一種投資方案：***失敗***財(cái)務(wù)參謀程序搜索的與/或樹成功：X=stocks***失敗并回溯***邏輯程序設(shè)計(jì)理論根底第六章-42內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2.2自然演繹推理3.2.3歸結(jié)演繹推理3.2.4子句集化簡(jiǎn)邏輯程序設(shè)計(jì)理論根底第六章-433.2.3歸結(jié)演繹推理歸結(jié)演繹推理是一種基于魯賓遜歸結(jié)原理的機(jī)器推理技術(shù)，使機(jī)器定理證明的自動(dòng)化成為現(xiàn)實(shí)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫理論的根底上提出的一種基于邏輯的“反證法〞。邏輯程序設(shè)計(jì)理論根底第六章-443.2.3歸結(jié)演繹推理相關(guān)概念： 文字原子謂詞公式及其否認(rèn)統(tǒng)稱為文字。例如：P(x)、Q(y)、P(x)、Q(y)子句〔歸結(jié)的對(duì)象〕任何文字的析取式稱為子句。例如，P(x)∨Q(y)，P(x,f(x))∨Q(x,g(x))空子句不包含任何文字的子句稱為空子句。由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的?？兆泳湟话惚挥洖椤趸騈IL。子句集由Horn子句或空子句所構(gòu)成的集合。邏輯程序設(shè)計(jì)理論根底第六章-453.2.3歸結(jié)演繹推理魯賓遜歸結(jié)原理如果存在某個(gè)公理

和，那么

在邏輯上成立。稱是和的消解式。歸結(jié)演繹推理〔反證法〕的步驟：①將前提和公理轉(zhuǎn)化為子句的形式。②將要證明的結(jié)論取反，并轉(zhuǎn)化為子句形式，與第①步形成的子句共同構(gòu)成子句集。③利用魯賓遜歸結(jié)原理歸結(jié)這些子句，生成可以從邏輯上推導(dǎo)出的新子句。④通過生成空子句得出矛盾?！纠竣貴ido是狗②所有的狗都是動(dòng)物③所有的動(dòng)物都會(huì)死證明：Fido會(huì)死。證明一〔自然演繹推理〕①所有的狗都是動(dòng)物：②Fido是狗：③取式假言推理和{fido/X}：④所有的動(dòng)物都會(huì)死：⑤取式假言推理和{fido/Y}：證明二〔歸結(jié)反駁推理〕①②③④謂詞形式子句形式邏輯程序設(shè)計(jì)理論根底第六章-473.2.3歸結(jié)演繹推理子句集“死狗〞問題的歸結(jié)證明□邏輯程序設(shè)計(jì)理論根底第六章-48內(nèi)容1.邏輯程序設(shè)計(jì)概述2.知識(shí)的表示3.知識(shí)的利用3.1搜索3.2推理3.2.1置換與合一3.2