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

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

ProgrammingLanguagesParadigms教師：張榮華華北電力大學計算機系軟件教研室〔保定〕

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

事實查詢/目標horizontal(line(point(1,1),point(2,Y))).

Y

=

1

;

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

P

=

point(_G434,3)

;

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

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

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

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

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

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

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

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

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

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

和，那么

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