用于人工智能的Prolog語言.ppt

用于人工智能的Prolog語言,歸結(jié)原理與Prolog語言,家庭關(guān)系程序示例,TurboProlog程序結(jié)構(gòu),表與遞歸,Prolog程序分析,本章主要內(nèi)容：,文件與數(shù)據(jù)庫,字符串處理,回溯及控制,輸入與輸出,Prolog是一種邏輯程序設(shè)計(jì)語言，基于一階謂詞邏輯，是典型的敘述型語言（DeclarationLanguage）。Prolog語言的特點(diǎn)：(1)建立在一階謂詞邏輯和歸結(jié)原理基礎(chǔ)上，有自動(dòng)推理功能。(2)用Prolog設(shè)計(jì)應(yīng)用程序時(shí)，僅需指明領(lǐng)域中各對(duì)象間的關(guān)系和決策規(guī)則，而應(yīng)用這些知識(shí)的推理由Prolog完成。(3)Prolog應(yīng)用程序，由數(shù)據(jù)庫和規(guī)則庫組成。(4)Prolog程序設(shè)計(jì)要做三件事，即說明事實(shí)、定義規(guī)則、提出問題。,4.1歸結(jié)原理與Prolog語言,Prolog有三種形式的語句：,1.B:-A1,A2,An.,含義是A1A2.AnB，相當(dāng)于A1A2AnB?？梢曌魅斯ぶ悄芟到y(tǒng)中的推理規(guī)則。也可將該句看作一個(gè)過程，B為過程頭，是過程名，而A1,A2,An為過程體。,2.A1,A2,An.,含義是A1A2.AnF，相當(dāng)于A1A2An，可視作推理的目標(biāo)，或稱目標(biāo)子句。,3.B.,含義是公式B無條件地為真?？梢曌饕阎氖聦?shí)。,x(M(x)R(x)M(“張三”)R(“張三”),如三段論：,推理規(guī)則：R(X):-M(X).,事實(shí)：M(張三).,目標(biāo)：R(張三).,Prolog語句：,證明公式：(M(X)R(X)M(張三)R(張三)恒真,即證明公式：(M(X)R(X)M(張三)R(張三)恒假,化成公式集：(M(X)R(X)M(張三)，R(張三),子句集：M(X)R(X)，M(張三)，R(張三),推理規(guī)則,事實(shí),目標(biāo),子句B:-A1,A2,An.和子句B.都是僅有一個(gè)正文字的子句。稱作定子句。,目標(biāo)子句A1,A2,An.是沒有正文字出現(xiàn)的子句。,定子句和目標(biāo)子句統(tǒng)成為Horn子句。Prolog子句都是Horn子句。,用Prolog證明三段論：,推理規(guī)則：R(X):-M(X).,事實(shí)：M(張三).,目標(biāo)：R(張三).,M(張三).,完整的Prolog程序：,predicatesM(symbol)R(symbol)clausesR(X):-M(X).M(zhsan).goalR(zhsan).,運(yùn)行,4.2家庭關(guān)系程序示例,下圖是一個(gè)表示家庭關(guān)系的實(shí)例：,parent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).,用Prolog語句表示為：,完整的Prolog程序：,predicatesparent(symbol,symbol)clausesparent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).,此程序可以回答的問題：,1.bob是pat的父母嗎？parent(bob,pat).,2.liz是pat的父母嗎？parent(liz,pat).,3.誰是liz的父母？parent(X,liz).,4.誰是誰的父母？parent(X,Y).,1.系統(tǒng)回答,2.系統(tǒng)回答,3.系統(tǒng)回答,4.系統(tǒng)回答,5.誰是jim的祖父母？,分析：程序中并沒有直接的祖父母關(guān)系。此問題可分兩步：,(1)誰是jim的父母？假設(shè)是Y,(2)誰是Y的父母？假設(shè)是X,X,jim,Y,parent,parent,grandparent,Prolog目標(biāo)語句：,parent(Y,jim),parent(X,Y).,6.類似的問題可以是：,“誰是tom的孫子？”,prolog目標(biāo)語句：,parent(tom,X),parent(X,Y).,5.系統(tǒng)回答,6.系統(tǒng)回答,parent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).,clauses,以上程序說明的幾個(gè)重要觀點(diǎn)：,(1)在Prolog中定義一個(gè)關(guān)系是容易的，可以通過滿足關(guān)系的n個(gè)對(duì)象來表達(dá)。,(2)對(duì)程序中已定義的關(guān)系，用戶可以輕而易舉地詢問Prolog系統(tǒng)。,(3)關(guān)系的對(duì)象可以是常量(如：tom,ann)，也可以是變量(如：X,Y)。,(4)向系統(tǒng)提出問題，可由一個(gè)或多個(gè)目標(biāo)組成。,(5)一個(gè)Prolog程序由一些子句(clauses)組成。每個(gè)子句用句號(hào)結(jié)束。,(6)對(duì)一個(gè)問題的回答是肯定的或者是否定的，取決于相應(yīng)的目標(biāo)是否滿足。在肯定回答的情況下，說相應(yīng)的目標(biāo)是可滿足的，而且這個(gè)目標(biāo)成功了。否則，說目標(biāo)不可滿足，目標(biāo)失敗了。,(7)如果有多個(gè)回答都滿足目標(biāo)，那么Prolog將盡可能多地回答。,Predicatesparent(symbol)clausesparent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).,male(tom).male(bob).male(jim).female(pam).female(liz).female(pat).female(ann).,在示例程序中，添加有關(guān)性別的信息：,在Prolog中定義offspring(后代）關(guān)系,對(duì)所有的X和Y，Y是X的后代，如果X是Y的父母。,對(duì)應(yīng)的prolog語句為：,offspring(Y,X):-parent(X,Y).,子句頭,子句體,注意：以上定義的是直接后代關(guān)系。,對(duì)于間接后代：,對(duì)所有的X和Y，Y是X的后代，如果Z是Y的父母,且Z是X的后代。,offspring(Y,X):-parent(Z,Y),offspring(Z,X).,對(duì)應(yīng)的prolog語句為：,X,Y,Z,parent,offspring,offspring,關(guān)于sister的規(guī)則定義：,predicatesparent(symbol,symbol)sister(symbol,symbol)female(symbol)male(symbol)clausesparent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).,male(tom).male(bob).male(jim).female(pam).female(liz).female(ann).female(pat).sister(X,Y):-parent(Z,X),parent(Z,Y),female(X).goalsister(X,pat).,運(yùn)行,Pat的姐妹是誰？,predicatesparent(symbol,symbol)sister(symbol,symbol)female(symbol)male(symbol)different(symbol,symbol)clausesparent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).male(tom).,male(bob).male(jim).female(pam).female(liz).female(ann).female(pat).sister(X,Y):-parent(Z,X),parent(Z,Y),female(X),different(X,Y).different(X,Y):-XY.goalsister(X,pat).,改進(jìn)的sister規(guī)則：,運(yùn)行,Pat的姐妹是誰？,mother規(guī)則：,對(duì)所有的X和Y，,X是Y的母親，,如果X是Y的父母，,并且，X為女性。,用prolog規(guī)則表示為：,mother(X,Y):-parent(X,Y),female(X).,predicatesparent(symbol,symbol)mother(symbol,symbol)female(symbol)male(symbol)clausesparent(pam,bob).parent(tom,bob).parent(tom,liz).parent(bob,ann).parent(bob,pat).parent(pat,jim).,mother(X,Y):-parent(X,Y),female(X).,male(tom).male(bob).male(jim).female(pam).female(liz).female(ann).female(pat).,goalmother(pat,X).,Pat是誰的母親？,運(yùn)行,4.3TurboProlog程序結(jié)構(gòu),一個(gè)TurboProlog程序通常包括5個(gè)部分。如下：,/*注釋*/domains域說明database數(shù)據(jù)庫說明predicates謂詞說明goal目標(biāo)說明clauses子句說明/*注釋*/,1.域說明部分，說明謂詞對(duì)象的數(shù)據(jù)類型。,2.數(shù)據(jù)庫說明部分，包含一些數(shù)據(jù)庫謂詞的定義，是說明用于動(dòng)態(tài)數(shù)據(jù)庫管理的謂詞。如果程序不需要?jiǎng)討B(tài)數(shù)據(jù)庫，該部分可省略。,3.謂詞說明部分，定義程序中除內(nèi)部謂詞以外的所有謂詞。,4.在目標(biāo)部分，說明程序的目標(biāo)。一個(gè)程序目標(biāo)可以由多個(gè)字目標(biāo)復(fù)合而成。,5.子句部分，列出全部事實(shí)和規(guī)則，也可看作是程序的靜態(tài)數(shù)據(jù)。,/*程序名:Wordsmith文件名:*/*目標(biāo):查找并打印一單詞的同義詞或反義詞。*/domainsword,syn,ant=symbolpredicatessynonym(word,syn)antonym(word,ant)goalsynonym(brave,X),antonym(brave,Y),write(brave的同義詞是:,X),nl,write(brave的反義詞是:,Y),nl.clausessynonym(brave,daring).synonym(honest,truthful).synonym(modern,new).synonym(rare,uncommon).antonym(brave,cowardly).antonym(honest,dishonest).antonym(mordern,ancient).antonym(rare,common).,4.4TurboProlog程序分析,/*程序名:Thesaurus文件名:*/*目標(biāo):建立一個(gè)打印單詞的同義詞和反義詞的小詞典。*/domainsword,syn1,syn2,syn3,ant1,ant2,ant3=symbolpredicatessynonym(word,syn1,syn2,syn3)antonym(word,ant1,ant2,ant3)goalsynonym(brave,S1,S2,S3),antonym(brave,A1,A2,A3),write(brave的同義詞是:),nl,write(S1,S2,S3,),write(brave的反義詞是:),nl,write(A1,A2,A3,.),nl.,clausessynonym(brave,daring,defiant,courageous).synonym(honest,truthful,open,sincere).synonym(modern,new,novel,recent).synonym(rare,uncommon,scrace,infrequent).antonym(brave,cowardly,fearful,timid).antonym(honest,dishonest,crooked,deceltful).antonym(mordern,ancient,old,obsolete).antonym(rare,common,ordinary,ubiquitous).,多元謂詞、多元子句,/*程序名:Presidents文件名:*/*目標(biāo):使用混合對(duì)象類型舉例。*/domainsname,party,state=symbolbirth_year,year_in,year_out=integerpredicatespresident(name,party,state,birth_year,year_in,year_out)goalpresident(X,democrat,S,Yb,Yi,Yo),nl,write(X,-democrat),nl,write(State-,S),nl,write(Birth_year-,Yb),nl,write(Year_in-,Yi),nl,write(Year_out-,Yo),nl,nl.clausespresident(elsenhower,republican,texas,1890,1953,1961).president(kennedy,democrat,massachusetts,1917,1961,1963).president(johnson,democrat,texas,1908,1963,1969).president(nixon,republican,california,1913,1969,1974).president(ford,republican,nebraska,1913,1974,1977).president(carter,democrat,georgia,1924,1977,1981).,混合域的使用,/*程序名:Rlatives文件名:*/*目標(biāo):規(guī)則結(jié)構(gòu)舉例*/domainsperson=symbolpredicatesmale(person)female(person)parents(person,person,person)sister(person,person)who_is_the_sistergoalwho_is_the_sister.clauses/*事實(shí)*/male(Frank).male(Sam).female(Mary).female(Debbie).parents(Sam,Frank,Mary).parents(Debbie,Frank,Mary).,/*規(guī)則*/who_is_the_sister:-sister(Sister,Brother),write(Sister,isthesisterof,Brother,.),nl.sister(Sister,Brother):-female(Sister),male(Brother),parents(Sister,Father,Mother),parents(Brother,Father,Mother).,目標(biāo)中使用規(guī)則,domainsman=symbolpredicateschoice(man)short_height(man)medium_height(man)tall_height(man)black_hair(man)brown_hair(man)blond_hair(man)old_car(man)new_car(man)sports_car(man)kathy_choice(man)who_is_the_choicegoalwho_is_the_choice.clauses/*事實(shí)*/choice(bill).choice(jim).choice(mark).choice(robert).choice(willy).,/*規(guī)則*/who_is_the_choice:-kathy_choice(Choice),write(Kathyschoiceis,Choice,.),nl.kathy_choice(Choice):-choice(Choice),tall_height(Choice),blond_hair(Choice),sports_car(Choice).,choice(tom).choice(frank).short_height(mark).short_height(willy).medium_height(jim).medium_height(tom).tall_height(jim).tall_height(robert).tall_height(frank).black_hair(bill).black_hair(willy).brown_hair(jim).brown_hair(tom).blond_hair(mark).blond_hair(robert).blond_hair(frank).new_car(mark).new_car(willy).new_car(frank).old_car(mark).old_car(tom).sports_car(jim).sports_car(robert).,簡單數(shù)據(jù)庫,/*程序名:Europair文件名:*/*目標(biāo):否定謂詞應(yīng)用舉例*/domainscountry=symbolpredicateseuro_pair(country,country)border(country,country)find_non_border_pairgoalfind_non_border_pair.clauseseuro_pair(France,Germany).euro_pair(France,Spain).euro_pair(France,Italy).euro_pair(Germany,Spain).euro_pair(Germany,Italy).euro_pair(Spain,Italy).border(France,Germany).border(France,Spain).border(France,Italy).find_non_border_pair:-euro_pair(X,Y),not(border(X,Y),write(X,-,Y),nl.,否定謂詞的應(yīng)用,domainspersonal_library=book(title,author,publisher,year)collector,title,author,publisher=symbolyear=integerpredicatescollection(collector,personal_library)clausescollection(kahn,book(TheComputerandtheBrain,vonNeumann,YaleUniversityPress,1958).collection(kahn,book(SymbolicLogic,LewisCarroll,DoverPublications,1958).collection(john,book(Database:APrimer,C.J.Date,Addison-Wesley,1983).collection(john,book(Problem-SolvingMethodsinAI,NilsNilsson,McGraw-Hill,1971).collection(smith,book(Alice,inWonderland,LewisCarroll,TheNewAmericanLibrary,1960).collection(smith,book(FablesofAesop,Aesop-Calder,DoverPublications,1967).,復(fù)合對(duì)象的應(yīng)用,域結(jié)構(gòu)圖,域,第0層(結(jié)構(gòu)),第1層(對(duì)象),DomainStructureDiagram,collection,collector,book,title,author,publisher,year,謂詞結(jié)構(gòu)圖,PredicateStructureDiagram,謂詞(主函子),函子,第0層,第1層,第2層,domainspersonal_library=book(title,author,publication)publication=publication(publisher,year)collector,title,author,publisher=symbolyear=integerpredicatescollection(collector,personal_library)clausescollection(kahn,book(TheComputerandtheBrain,vonNeumann,publication(YaleUniversityPress,1958).collection(kahn,book(SymbolicLogic,LewisCarroll,publication(DoverPublications,1958).collection(john,book(Database:APrimer,C.J.Date,publication(Addison-Wesley,1983).collection(john,book(Problem-SolvingMethodsinAI,NilsNilsson,publication(McGraw-Hill,1971).collection(smith,book(Alice,inWonderland,LewisCarroll,publication(TheNewAmericanLibrary,1960).collection(smith,book(FablesofAesop,Aesop-Calder,publication(DoverPublications,1967).,三層域結(jié)構(gòu)和四層謂詞結(jié)構(gòu),personal_library,book,title,author,publication,year,域結(jié)構(gòu)圖,域,第0層,第1層,DomainStructureDiagram,collection,collector,book,title,author,publisher,year,謂詞結(jié)構(gòu)圖,PredicateStructureDiagram,謂詞(主函子),函子,第0層,第1層,第2層,publisher,第2層,publisher,第3層,4.5表與遞歸,表是含有任意數(shù)目的其他對(duì)象的一個(gè)對(duì)象。,一個(gè)包含1,2,3的表可被寫成：1,2,3,表中的每個(gè)項(xiàng)被稱為一個(gè)元素。,在域說明中需要對(duì)表類型進(jìn)行說明。如：,domainsintegerlist=integer*predicatesnumber(integerlist),表頭：是表中的第一個(gè)元素。如：表a,b,c中a是表頭。,表尾：是表中除表頭外的另一張表。如：表a,b,c中b,c是表尾。,空表：沒有元素的表。對(duì)于表c,c是表頭，是表尾。,a,b,c,d,a,b,c,d,b,c,d,c,d,d,Prolog提供一種使表頭和表尾明確分開的方法：用逗號(hào)將元素分開，用|號(hào)將表頭和表尾分開。如：,a,b,c等價(jià)于a|b,c等價(jià)于a|b|c等價(jià)于a|b|c|,打印表中元素的例子：,domainslis