1、 第2章 邏輯程序設(shè)計語言PROLOG Prolog語言Prolog是一種基于一階謂詞的邏輯程序設(shè)計語言，它在AI和知識庫的實現(xiàn)技術(shù)中具有十分重要的作用。Prolog語言是基于Horn子句的，使用歸結(jié)推理，具有很強的邏輯描述能力和推理能力。 2.1 基本PROLOG 2.2 Turbo PROLOG程序設(shè)計 2.1 基本PROLOG 2.1.1 PROLOG的語句 Prolog語言只有三種語句，分別稱為事實、規(guī)則和問題。 1. 事實(fact) 格式 謂詞名(項表). student(john). like(mary,music). abc. /無參量 repeat. /無參量 功能 一般表示

2、對象的性質(zhì)或關(guān)系。 2. 規(guī)則(rule) 格式 謂詞名(項表):-謂詞名(項表),謂詞名(項表). bird(X):-animal(X),has(X,feather). grandfather(X,Y):- father(X,Z),father(Z,Y). run:-start,step1(X),step2(X),end. / 無參量 功能 一般表示對象間的因果關(guān)系、蘊含關(guān)系或?qū)?yīng)關(guān)系。 3. 問題(question) 格式?-謂詞名(項表),謂詞名(項表). ?-student(john). ?-like(mary,X). 問題就是Horn子句邏輯中的目標子句，只是形式略有不同 功能問題表

3、示用戶的詢問, 它就是程序運行的目標。 問題可以與規(guī)則及事實一同給出，也可以在程序運行時臨時給出。 2.1.2 PROLOG的程序 PROLOG程序一般由一組事實、 規(guī)則和問題組成。問題是程序執(zhí)行的起點, 稱為程序的目標。 likes(bell,sports). /描述對象間的關(guān)系 likes(mary,music). likes(mary,sports). likes(jane,smith). /同一謂詞名排一起 friend(john,X):-likes(X,reading),likes(X,music). friend(john,X):-likes(X,sports),likes(X,m

4、usic)./描述條件 ?-friend(john,Y). /目標：john和誰是朋友 ?-likes(mary,X).或 ?-likes(mary,music).或 ?-friend(X,Y).或 ?-likes(bell,sports), likes(mary,music), friend(john,X). /三個一起寫出，中間用，隔開PROLOG程序中的事實或規(guī)則一般稱為它們對應(yīng)謂詞的子句，例如上面程序中的前四句都是謂詞likes的子句。Prolog規(guī)定，同一謂詞的子句應(yīng)排在一起。從語句形式和程序組成來看，prolog就是一種基于Horn子句的邏輯程序。這種程序要求用事實和規(guī)則來求證詢問

5、，即證明所給出的條件子句和無條件子句與目標子句是矛盾的，或者說程序中的子句集是不可滿足的。這就是所謂的PROLOG的說明性語義。PROLOG語言的文法結(jié)構(gòu)相當簡單，描述能力很強，是一種應(yīng)用相當廣泛的智能程序設(shè)計語言。2.1.3 PROLOG程序的運行機理 prolog的運行機理就是基于歸結(jié)原理的演繹推理（歸結(jié)原理將在第五章介紹）。 prolog程序的運行是從目標出發(fā)，并不斷進行匹配、合一、歸結(jié)，有時還要回溯，直到目標被完全滿足或不能滿足時為止。1. 自由變量與約束變量 自由變量：無值的變量 約束變量：有值的變量 一個變量取了某值就說該變量約束于某值，或者說該變量被某值所約束，再或者說該變量被某

6、值實例化了。在程序運行期間，一個自由變量可以被實例化成約束變量，反之，也可。2. 匹配合一 兩個謂詞可匹配合一, 是指兩個謂詞的名相同, 參量項的個數(shù)相同, 參量類型對應(yīng)相同, 并且對應(yīng)參量項還滿足下列條件之一： (1) 如果兩個都是常量, 則必須完全相同。 (2) 如果兩個都是約束變量, 則兩個約束值必須相同。 (3) 如果其中一個是常量, 一個是約束變量, 則約束值與常量必須相同。 (4) 至少有一個是自由變量。 考慮下面的各組謂詞是否可匹配合一？ pre1(ob1,ob2,Z) pre1(ob1, ob3,Y) pre1(ob1,ob2,Z) pre1(ob1,X, ob3) pre1(

7、ob1,ob2,Z) pre1(ob1,X,Y)3. 回溯 所謂回溯, 就是在程序運行期間, 當某一個子目標不能滿足(即謂詞匹配失敗)時,控制就返回到前一個已經(jīng)滿足的子目標(如果存在的話), 并撤消其有關(guān)變量的約束值, 然后再使其重新滿足。 成功后, 再繼續(xù)滿足原子目標。如果失敗的子目標前再無子目標, 則控制就返回到該子目標的上一級目標(即該子目標謂詞所在規(guī)則的頭部)使它重新匹配。回溯也是PROLOG的一個重要機制。 likes(bell,sports). likes(mary,music). likes(mary,sports). likes(jane,smith). friend(john

8、,X):-likes(X,reading),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music). ?-friend(john,Y). /問題：john和誰是朋友則求解目標為 friend(john,Y). 系統(tǒng)對程序進行掃描，尋找能與目標謂詞匹配合一的事實或規(guī)則頭部。顯然程序中前面四條事實均不能與目標匹配，而第五個語句的左端，也即其頭部可與目標謂詞匹配合一。該規(guī)則若要成立，須其前提全部成立。新目標 likes(X,reading),likes(X,music). 相當于規(guī)則頭部被消去，目標子句變成 ？-likes（X，r

9、eading）,likes(X,music).對新目標求解： 子目標的求解過程與主目標完全一樣，也是從頭對程序進行掃描，不斷測試盒匹配合一等，直到匹配成功或掃描完整個程序為止。 第一個子目標likes(X,reading)，沒有可以匹配的事實和規(guī)則，因此求解失敗，所以第五條語句失敗。 那么，剛才的子目標 likes(X,reading),likes(X,music)被撤銷，系統(tǒng)回溯到原目標 friend(john,Y). 系統(tǒng)從失敗的匹配語句處（第五條語句）向下繼續(xù)掃描程序中的子句，視圖重新使原目標匹配，結(jié)果發(fā)現(xiàn)第六條語句的左部即規(guī)則friend(john,X):-likes(X,sports

10、),likes(X,music).的頭部可與目標為謂詞匹配。 第一個次子目標likes(X,sports)與程序中的事實立即匹配成功，且變量X被約束為bell。于是系統(tǒng)便接著求解第二個子目標。由于變量X已被約束，所以這時第二個子目標已變成了 likes(bell,music). 由于程序中不存在該事實，所以該目標求解失敗。于是，系統(tǒng)就放棄這個子目標，并恢復X為自由變量，然后回溯到第一個子目標，重新對它進行求解。 系統(tǒng)重新從下一個事實開始測試。測試到第三個事實時，第一個子目標便求解成功，且變量X被約束為mary。這樣，第二個子目標也就變成了 likes(mary,music).再求解，成功。 兩

11、個子目標都求解成功，所以原目標也成功，且變量Y被約束為mary（Y與X的合一關(guān)系）。于是，系統(tǒng)回答： Y=mary程序運行結(jié)束。上述程序的運行是一個通過推理實現(xiàn)的求值過程。Prolog程序的執(zhí)行是一個（歸結(jié)）演繹推理的過程。特點：（1）推理方式為反向推理；（2）控制策略是深度優(yōu)先；（3）有回溯。具體實現(xiàn)方法：（1）匹配子句的順序是自上而下；（2）子目標選擇順序是從左向右；（3）歸結(jié)后產(chǎn)生的新子目標總是插入被削去的目標處（即目標隊列的左部）。PROLOG的這種歸結(jié)演繹方法被稱為SLD歸結(jié)，或SLD反駁-消解法。這就是PROLOG程序的運行機理，它就是所謂的PROLOG語言的過程性語義。 2.2

12、Turbo PROLOG程序設(shè)計PROLOG版本： 早期基本為解釋型語言； 1986年BORLAND公司推出Turbo PROLOG，它是一種編譯型語言。特點： 速度快； 功能強； 具有集成化開發(fā)環(huán)境； 可同其它語言接口； 能實現(xiàn)動態(tài)數(shù)據(jù)庫和大型外部數(shù)據(jù)庫； 可直接訪問機器系統(tǒng)硬軟件和圖形、窗口等。2.2.1 程序結(jié)構(gòu) 一個完整的Turbo PROLOG（2.0版）程序一般包括常量段、領(lǐng)域段、數(shù)據(jù)庫段、謂詞段、目標段和子句段等六個部分，其標識及完整程序結(jié)構(gòu)如下(一個程序不一定要包括所有段)：/* 注 釋 */ 編譯指令 constants 常量說明 domains 域說明 / 大多數(shù)情況需要，

13、用以說明表、復合結(jié)構(gòu)及用戶自定義的域名 database 數(shù)據(jù)庫說明 predicates 謂詞說明 /至少有一個 goal 目標語句/至少且只能有一個 clauses 子句集 /至少有一個例 如果把上節(jié)的例子程序作為Turbo PROLOG程序, 則應(yīng)改寫為： DOMAINS name=symbol PREDICATES likes(name,name) friend(name,name) GOAL friend(john,Y), write(Y=, Y)/輸出Y= CLAUSES likes(bell,sports). likes(mary,music). likes(mary,sport

14、s). likes(jane,smith). friend(john,X):-likes(X,sports),likes(X,music). friend(john,X):-likes(X,reading),likes(X,music). 領(lǐng)域段該段說明程序謂詞中所有參量項所屬的領(lǐng)域。 Turbo PROLOG的標準領(lǐng)域包括整數(shù)、實數(shù)、符號、串和符號等, 其具體說明如下表所示。謂詞段 該段說明程序中用到的謂詞的名和參量項的名(但Turbo PROLOG 的內(nèi)部謂詞無須說明)子句段 該段是Turbo PROLOG程序的核心, 程序中的所有事實和規(guī)則就放在這里, 系統(tǒng)在試圖滿足程序的目標時就對它們

15、進行操作。目標段 該段是放置程序目標的地方。 目標段可以只有一個目標謂詞, 例如上面的例子中就只有一個目標謂詞； 也可以含有多個目標謂詞, 如 goal readint(X),Y=X+3,write(Y=,Y).就有三個目標謂詞。 這種目標稱為復合目標。 2.2.2 數(shù)據(jù)與表達式1. 領(lǐng)域 1) 標準領(lǐng)域 整數(shù)、實數(shù)、 字符、 串和符號 2) 結(jié)構(gòu) 結(jié)構(gòu)也稱復合對象（特殊的參量項）, 一般形式為 函子(參量表)函子及參量的標示符與謂詞相同，結(jié)構(gòu)包含結(jié)構(gòu)，表達樹形數(shù)據(jù)結(jié)構(gòu)，如下例子：likes(Tom, sports(football, basketball, table_tennis). /紅

16、色部分也是謂詞結(jié)構(gòu)，就是復合結(jié)構(gòu) reading(王宏,book(人工智能技術(shù)導論,西安電子科技大學出版社).friend(father(Li), father(Zhao).復合對象在程序中的說明, 需分層進行。 例如, 對于上面的謂詞 likes(Tom, sports(football, basketball, table_tennis). 在程序中可說明如下： domains name=symbol sy=symbol / 說明sy的領(lǐng)域 sp=sports(sy, sy, sy) /sp使用已說明領(lǐng)域的sy predicates likes(name, sp) 3) 表 表的一般形式

17、x1, x2, , xn 其中xi(i=1, 2, , n)為PROLOG的項, 一般要求同一個表的元素必須屬于同一領(lǐng)域。不含任何元素的表稱為空表, 記為 。 1, 2, 3 apple, orange, banana, grape, cane PROLOG,PROGRAMMING,in logic a, b, c, d, e name(LiMing), age(20),sex(male),addr(xian)/元素可以是結(jié)構(gòu)或表，且這時元素可以屬于不同領(lǐng)域表是一種特殊的結(jié)構(gòu)，它是遞歸結(jié)構(gòu)的另一種表達形式。結(jié)構(gòu)函數(shù)名用一個圓點表示。例如：結(jié)構(gòu)形式 表達式(a,) a(a, (b,) a,b(a

18、, (b, (c,) a,b,c表的說明方法是在其組成元素的說明符后加一個星號*。 如： domains lists=string* predicates pl(lists)例如，謂詞 p(name(Liming), age(20)則需這樣說明: domains rec=seg* /rec是表，seg是表中的元素 seg=name(string);age(integer) predicates p(rec) /p是謂詞 2. 常量與變量 Turbo PROLOG的常量有整數(shù)、實數(shù)、 字符、串、符號、結(jié)構(gòu)、表和文件這八種數(shù)據(jù)類型。同理, Turbo PROLOG的變量也就有這八種取值。另外, 變

19、量名要求必須是以大寫字母或下劃線開頭的字母、數(shù)字和下劃線序列, 或者只有一個下劃線。 這后一種變量稱為無名變量。 3. 算術(shù)表達式 Turbo PROLOG提供了五種最基本的算術(shù)運算：加、減、 乘、除和取模, 相應(yīng)運算符號為+、 -、*、 /、 mod。 這五種運算的順序為： *、/、 mod優(yōu)先于+、 -。括號優(yōu)先。 數(shù)學中的算術(shù)表達式 PROLOG中的算術(shù)表達式 x+yz X+Y*Z ab-c/d A*B-C/D u mod v U mod V 算術(shù)表達式采用的中綴形式，它是PROLOG的一種異體結(jié)構(gòu)，結(jié)構(gòu)表示形式如下： +（X,*(Y,Z)） （*（A,B),/(C,D) mod（U,V

20、）一個算術(shù)表達式中的變元全部被實例化（即被約束），則這個算術(shù)表達式的值就會被求出。求出的值可用來實例化某變量，也可用來同其它數(shù)量進行比較，實例化用謂詞“is”或“=”來實現(xiàn)。 Y is X+5 Y=X+5 X=X+1 /不同于賦值的地方注意：PROLOG雖然是一種邏輯程序設(shè)計語言，但在目前的 硬件條件下卻非突破邏輯框架不可。因為，有些實用操作無法用邏輯描述（如輸入輸出），有些運算在原則上可用邏輯描述，但效率太低。解決方法：PROLOG提供若干內(nèi)部謂詞（亦稱預定義謂詞），來實現(xiàn)這些非邏輯的操作。上例關(guān)系表達式稱為異體謂詞。4.關(guān)系表達式 Turbo PROLOG提供了六種常用的關(guān)系運算, 即小于

21、、 小于或等于、等于、大于、大于或等于和不等于, 其運算符依次為 , , =, 數(shù)學中的關(guān)系式 Turbo PROLOG中的關(guān)系式 X+1Y X+1=Y XY XY 它們都采用中綴形式。Prolog中的原子形式表示如下：=(X+1,Y) (X,Y)這六中關(guān)系運算符就是Turbo PROLOG內(nèi)部定義好的六個謂詞。用來比較兩個關(guān)系式大小。brother(Name1, Name2):- person(Name1, man, Age1), person(Name2, man, Age2), mother(Z, Name1), mother(Z, Name2), Age1Age2. “=”的用法 ：比

22、較符和約束符 p(X, Y, Z):-Z=X+Y.當變量X、Y、Z全部被實例化時, “=”就是比較符。 如： 對于問題 Goal: p(3, 5, 8).機器回答： yes。 而對于 Goal: p(3, 5, 7). 機器回答： no。 但當X, Y被實例化, 而Z未被實例化時, “=”號就是約束符。 如： Goal: p(3, 5, Z).機器回答： Z=8這時, 機器使Z實例化為X+Y的結(jié)果。 2.2.3 輸入與輸出為從鍵盤輸入有關(guān)數(shù)據(jù)，PROLOG一般提供專門的輸入和輸出謂詞;(1) readln (X) /讀字符串給X(2) readint (X) /讀整數(shù)給X,若不是則謂 詞失敗(

23、3) readreal (X) /讀實數(shù)給X,若不是則謂詞失敗(4) readchar (X) /讀字符給X，否，失敗(5) write (X1, X2, ,Xn) /輸出X（實例化，否則失敗）Write（”computer”,”PROLOG”,Y,1992)(6) nl /換行,等同“n”例 用輸入輸出謂詞編寫一個簡單的成績 數(shù)據(jù)庫查詢程序。 PREDICATES student(integer, string, real) grade GOAL grade. CLAUSES student(1, 張三, 90.2). student(2, 李四, 95.5). student(3, 王五,

24、 96.4). grade: -write(請輸入姓名:), readln(Name), student(_, Name, Score), nl, write(Name, 的成績是, Score). grade: -write(對不起, 找不到這個學生!).下面是程序運行時的屏幕顯示： 請輸入姓名：王五 王五的成績是：96.42.2.4 分支與循環(huán)PROLOG沒有專門的分支和循環(huán)語句，但也可以實現(xiàn)循環(huán)。1. 分支 對于IF-THEN-ELSE分支結(jié)構(gòu)， 將 IF x0 THEN x:=1 /假設(shè)為真則執(zhí)行 ELSE x:=0 /假設(shè)為假則執(zhí)行用PROLOG實現(xiàn)則可以是 br:-x0, x=1.

25、 br:-x=0.也可用多條規(guī)則實現(xiàn)多分支： br:-x0,x=1. br:-x=0,x=0. br:-x0,x=-1.2. 循環(huán) PROLOG可以執(zhí)行 FOR循環(huán)：記次數(shù) DO循環(huán)：不記次數(shù)程序1（記次）： student(1, 張三, 90.2). student(2, 李四, 95.5). student(3, 王五, 96.4). print:-student(Number, Name, Score), write(Number, Name, Score), nl, Number=3. 程序2（不記次）： student(1, 張三, 90.2). student(2, 李四, 95.

26、5). student(3, 王五, 96.4). print:-student(Number, Name, Score), write(Number, Name, Score), nl, fail. print:-. Fail是一個內(nèi)部謂詞，語義是恒失敗。所以后面要增加一個print為程序設(shè)置一個出口，若無出口，將引起print本身的失敗，導致程序失敗。遞歸機制也可以實現(xiàn)循環(huán)，不過遞歸循環(huán)通常和表配合，其他情況一般不用遞歸循環(huán)，容易引起內(nèi)存溢出。遞歸遞歸是一種功能強大的編程算法，現(xiàn)在絕大部分的程序語言都支持函數(shù)的遞歸調(diào)用，Prolog也不例外，而且如果沒有遞歸，Prolog就不能叫做Prol

27、og了。在Prolog中，當某個謂詞的目標中包含了此謂詞本身時，Prolog將進行遞歸調(diào)用。任何語言中的遞歸定義都包括兩個部分： 邊界條件 遞歸部分邊界條件定義最簡單的情況。而遞歸部分，則首先解決一部分問題，然后再調(diào)用其自身來解決剩下的部分，每一次都將進行邊界檢測，如果剩下的部分已經(jīng)是邊界條件中所定義的情況時，那么遞歸就圓滿成功了 2.2.5 動態(tài)數(shù)據(jù)庫 動態(tài)數(shù)據(jù)庫就是在內(nèi)存中實現(xiàn)的動態(tài)數(shù)據(jù)結(jié)構(gòu)。它由事實組成，程序可以對它操作，所以再程序運行期間它可以動態(tài)變化。 動態(tài)數(shù)據(jù)庫操作謂詞（三個）: asserta(fact). 插入同名謂詞之前 assertz(fact). 插入同名謂詞之后 ret

28、ract(fact). 從數(shù)據(jù)庫中刪除例 asserta(student(20, 李明, 90.5). retract(student(20,_,_)./無名變量_PROLOG還提供了存入磁盤和從磁盤讀出的謂詞： save() /存入 consult() /讀出2.2.6 表處理與遞歸 表在prolog中是一種有用的數(shù)據(jù)結(jié)構(gòu)，特點： 表述能力強； 長度不固定； 可對表進行一些操作，比如元素的添加和刪除，表的合并等。可用表方便地構(gòu)造堆棧、隊列、鏈表、樹等動態(tài)數(shù)據(jù)結(jié)構(gòu)。 表的另一個重要特點，就是它可以分為表頭和表尾兩部分。1.表頭與表尾 表頭是表中的第一個元素；表尾是表中除第一個元素外的其余元素按

29、原來順序組成的表。 表頭與表尾示例 表 表頭 表尾1, 2, 3,4,5 1 2, 3,4,5 apple, orange, banana apple orange, banana a, b, c, d, e a, b c, d, e PROLOG PROLOG 無定義 無定義 2. 表的匹配合一 表的匹配合一示例 表1 表2 合一后的變量值 XY a, b, c X=a, Y= b, c XY a X=a, Y= a Y X, b X=a, Y= b X,Y,Z a, b, c X=a, Y=b, Z=c a, Y Z X, b , c X=a, Y=b, Z= c “”用來區(qū)分表頭和表尾。

30、表頭和表尾還可以使用變量。通常采用HT,采用這種方式可以通過匹配合一方便提取表頭和表尾。 “”后面只允許有一個變量，前面可以有多個。例如： XY，Z X，YZ 豎杠前后可以是常量,如： aY Xb 此表稱為無尾表如果這兩個表相匹配合一，則有： X=a，Y=b（非Y=b）若無豎杠，則不能分離出表尾，如： X,Y,Z與a,b,c合一后結(jié)果為X=a，Y=b，Z=c 而非c例 設(shè)計一個能判斷對象X是表L的成員的程序。 分析： (1) 如果X與表L中的第一個元素(即表頭)是同一個對象, 則X就是L的成員。 (2) 如果X是L的尾部的成員, 則X也就是L的成員。 程序： member(X, X|_). m

31、ember(X, Head|Tail):-member(X, Tail). 再如： Goal: member(a, a, b, c, d). yes Goal: member(e, a, b, c, d). no Goal: member(X, a, b, c, d). X=a /如果存在變量進行匹配合一，則給出變量值表的拼接例 表的拼接程序, 即把兩個表連接成一個表。 append(, L, L). /邊界條件，即程序終結(jié) append(H|T, L2,H|Tn):-append(T,L2, Tn). /遞歸部分，L1和L2合并為L3若： Goal: append(1, 2, 3, 4, 5

32、, L). L=1, 2, 3, 4, 5/經(jīng)過三次遞歸 第一次：令L1=1,2,3，則須T=2,3與L2拼接； 第二次：令L3=2,3，則須T=3與L2拼接； 第三次：令L4=3,則須T=與L2拼接； 第三次遞歸時需要滿足的是空表與L2拼接，即第一個子句，此子句為邊界條件，終止，然后通過反向依次求出拼接表，最好得出: L=1, 2, 3, 4, 5其他詢問： Goal: append(1,2,3,4,5,1,2,3,4,5). yes Goal: append(1,2,3,4,5,1,2,3,4,5,6). no Goal：append（1,2,3,Y,1,2,3,4,5) Y=4,5 Go

33、al：append（X,Y,1,2,3,4,5) X=,Y=1,2,3,4,5 X=1,Y=2,3,4,5 X=1,2,Y=3,4,5 遞歸技術(shù)一般只在表處理中使用，其他程序中盡量不用，而用迭代循環(huán)。例 表的輸出。 print(). print(H|T):-write(H), print(T).例 表的倒置, 即求一個表的逆序表。 reverse(,). reverse(H|T,L):-reverse(T,L1), append(L1,H,L). 2.2.7 回溯控制 截斷謂詞“!”的三條語義： (1) 若將“!”插在子句體內(nèi)作為一個子目標, 它總是立即成功。 (2) 若“!”位于子句體的最后, 則它就阻止對它所在子句的頭謂詞的所有子句的回溯訪問