用于人工智能的Prolog语言

1、用于人工智能的Prolog语言,归结原理与Prolog语言,家庭关系程序示例,Turbo Prolog程序结构,表与递归,Prolog 程序分析,本章主要内容：,文件与数据库,字符串处理,回溯及控制,输入与输出,Prolog 是一种逻辑程序设计语言，基于一阶谓词逻辑，是典型的叙述型语言（Declaration Language）。 Prolog语言的特点： (1) 建立在一阶谓词逻辑和归结原理基础上，有自动推理功能。 (2) 用Prolog设计应用程序时，仅需指明领域中各对象间的关系和决策规 则，而应用这些知识的推理由Prolog 完成。 (3) Prolog应用程序，由数据库和规则库组成。

2、(4) Prolog程序设计要做三件事，即说明事实、定义规则、提出问题。,4.1 归结原理与Prolog语言,Prolog 有三种形式的语句：,1.B:- A1,A2,An .,含义是 A1 A2. An B ，相当于A1A2 An B。可视作人工智能系统中的推理规则。也可将该句看作一个过程，B为过程头，是过程名，而A1,A2,An 为过程体。,2.A1,A2,An .,含义是 A1 A2 . An F ，相当于A1A2 An，可视作推理的目标，或称目标子句。,3.B.,含义是公式B无条件地为真。可视作已知的事实。,x(M(x) R(x) M(“张三”) R(“张三”),如三段论：,推理规则：

3、R(X):- M(X).,事实：M(张三).,目标：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(张三) ,推理规则,事实,目标,子句 B:- A1,A2,An .和子句B.都是仅有一个正文字的子句。称作定子句。,目标子句 A1,A2,An .是没有正文字出现的子句。,定子句和目标子句统成为Horn子句。Prolog

4、子句都是Horn子句。,用Prolog证明三段论：,推理规则：R(X):- M(X).,事实：M(张三).,目标：R(张三).,M(张三).,完整的Prolog程序：,predicates M(symbol) R(symbol) clauses R(X):- M(X). M(zhsan). goal R(zhsan).,运行,4.2 家庭关系程序示例,下图是一个表示家庭关系的实例：,parent(pam,bob). parent(tom,bob). parent(tom,liz). parent(bob,ann). parent(bob,pat). parent(pat,jim).,用Prol

5、og 语句表示为：,完整的Prolog程序：,predicates parent(symbol, symbol) clauses parent(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.系统回答,2.系统

6、回答,3.系统回答,4.系统回答,5.谁是jim的祖父母？,分析：程序中并没有直接的祖父母关系。此问题可分两步：,(1)谁是jim 的父母？假设是Y,(2)谁是Y 的父母？假设是X,X,jim,Y,parent,parent,grandparent,Prolog目标语句：,parent(Y,jim),parent(X,Y).,6.类似的问题可以是：,“谁是tom的孙子？”,prolog目标语句：,parent(tom,X),parent(X,Y).,5.系统回答,6.系统回答,parent(pam,bob). parent(tom,bob). parent(tom,liz). parent(b

7、ob,ann). parent(bob,pat). parent(pat,jim).,clauses,以上程序说明的几个重要观点：,(1)在Prolog中定义一个关系是容易的，可以通过满足关系的n个对象来表达。,(2)对程序中已定义的关系，用户可以轻而易举地询问Prolog 系统。,(3)关系的对象可以是常量 (如：tom,ann) ，也可以是变量(如：X,Y)。,(4)向系统提出问题，可由一个或多个目标组成。,(5)一个Prolog 程序由一些子句(clauses)组成。每个子句用句号结束。,(6)对一个问题的回答是肯定的或者是否定的，取决于相应的目标是否满足。在肯定回答的情况下，说相应的目

8、标是可满足的，而且这个目标成功了。否则，说目标不可满足，目标失败了。,(7)如果有多个回答都满足目标，那么Prolog 将尽可能多地回答。,Predicates parent(symbol) clauses parent(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).,在示例程序中，添加

9、有关性别的信息：,在Prolog中定义offspring(后代）关系,对所有的X和Y， Y是X的后代， 如果X是Y的父母。,对应的prolog 语句为：,offspring(Y,X):- parent(X,Y).,子句头,子句体,注意：以上定义的是直接后代关系。,对于间接后代：,对所有的X和Y， Y是X的后代， 如果Z是Y的父母,且 Z是X的后代。,offspring(Y,X):- parent(Z,Y), offspring(Z,X).,对应的prolog 语句为：,X,Y,Z,parent,offspring,offspring,关于sister的规则定义：,predicates pare

10、nt(symbol,symbol) sister(symbol,symbol) female(symbol) male(symbol) clauses parent(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

11、), female(X). goal sister(X,pat).,运行,Pat的姐妹是谁？,predicates parent(symbol,symbol) sister(symbol,symbol) female(symbol) male(symbol) different(symbol,symbol) clauses parent(pam,bob). parent(tom,bob). parent(tom,liz). parent(bob,ann). parent(bob,pat). parent(pat,jim). male(tom).,male(bob). male(jim). fe

12、male(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. goal sister(X,pat).,改进的sister规则：,运行,Pat的姐妹是谁？,mother规则：,对所有的X和Y，,X是Y的母亲，,如果X是Y的父母，,并且，X为女性。,用prolog规则表示为：,mother(X,Y):- parent(X,Y), female(X).,predicates parent(

13、symbol,symbol) mother(symbol,symbol) female(symbol) male(symbol) clauses parent(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).,go

14、al mother(pat,X).,Pat是谁的母亲？,运行,4.3 Turbo Prolog程序结构,一个Turbo Prolog程序通常包括5个部分。如下：,/*注释 */ domains 域说明 database 数据库说明 predicates 谓词说明 goal 目标说明 clauses 子句说明 /*注释 */,1.域说明部分，说明谓词对象的数据类型。,2.数据库说明部分，包含一些数据库谓词的定义，是说明用于动态数据库管理的谓词。如果程序不需要动态数据库，该部分可省略。,3.谓词说明部分，定义程序中除内部谓词以外的所有谓词。,4.在目标部分，说明程序的目标。一个程序目标可以由多个字

15、目标复合而成。,5.子句部分，列出全部事实和规则，也可看作是程序的静态数据。,/* 程序名 : Wordsmith 文件名 : */ /* 目 标 : 查找并打印一单词的同义词或反义词。 */ domains word,syn,ant=symbol predicates synonym(word,syn) antonym(word,ant) goal synonym(brave,X), antonym(brave,Y), write(brave 的同义词是: ,X), nl, write(brave 的反义词是: ,Y), nl. clauses synonym(br

16、ave,daring). synonym(honest,truthful). synonym(modern,new). synonym(rare,uncommon). antonym(brave,cowardly). antonym(honest,dishonest). antonym(mordern,ancient). antonym(rare,common).,4.4 Turbo Prolog程序分析,/* 程序名 : Thesaurus 文件名 : */ /* 目 标 : 建立一个打印单词的同义词和反义词的小词典。*/ domains word, syn1,sy

17、n2,syn3, ant1,ant2,ant3=symbol predicates synonym(word,syn1,syn2,syn3) antonym(word,ant1,ant2,ant3) goal synonym(brave,S1,S2,S3), antonym(brave,A1,A2,A3), write(brave 的同义词是: ), nl, write(S1,S2,S3,), write(brave 的反义词是: ), nl, write(A1,A2,A3,.),nl.,clauses synonym(brave,daring,defiant,courageous). syn

18、onym(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).,多元谓词、多元子句,/* 程序名 : Pres

19、idents 文件名 : */ /* 目 标 : 使用混合对象类型举例。 */ domains name,party,state=symbol birth_year,year_in,year_out=integer predicates president(name,party,state,birth_year,year_in,year_out) goal president(X,democrat,S,Yb,Yi,Yo),nl, write(X, - democrat),nl, write(State - ,S),nl, write(Birth_year - ,Yb)

20、,nl, write(Year_in - ,Yi),nl, write(Year_out - ,Yo),nl,nl. clauses president(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,

21、republican,nebraska,1913,1974,1977). president(carter,democrat,georgia,1924,1977,1981).,混合域的使用,/* 程序名 : Rlatives 文件名 : */ /* 目 标 : 规则结构举例 */ domains person=symbol predicates male(person) female(person) parents(person,person,person) sister(person,person) who_is_the_sister goal who_is_the

22、_sister. clauses /* 事 实 */ male(Frank). male(Sam). female(Mary). female(Debbie). parents(Sam,Frank,Mary). parents(Debbie,Frank,Mary).,/* 规 则 */ who_is_the_sister:- sister(Sister,Brother), write(Sister,is the sister of ,Brother,.), nl. sister(Sister,Brother):- female(Sister), male(Brother), parents(S

23、ister,Father,Mother), parents(Brother,Father,Mother).,目标中使用规则,domains man=symbol predicates choice(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_choice goal who_is_the_

24、choice. clauses /* 事 实 */ choice(bill). choice(jim). choice(mark). choice(robert). choice(willy).,/* 规 则 */ who_is_the_choice:- kathy_choice(Choice), write(Kathys choice is ,Choice,.), nl. kathy_choice(Choice):- choice(Choice), tall_height(Choice), blond_hair(Choice), sports_car(Choice).,choice(tom)

25、. 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).

26、new_car(willy). new_car(frank). old_car(mark). old_car(tom). sports_car(jim). sports_car(robert).,简单数据库,/* 程序名 : Europair 文件名 : */ /* 目 标 : 否定谓词应用举例 */ domains country=symbol predicates euro_pair(country,country) border(country,country) find_non_border_pair goal find_non_border_pair. cl

27、auses euro_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.

28、,否定谓词的应用,domains personal_library=book(title,author,publisher,year) collector,title,author,publisher=symbol year=integer predicates collection(collector,personal_library) clauses collection(kahn, book(The Computer and the Brain, von Neumann, Yale University Press,1958). collection(kahn, book(Symboli

29、c Logic, Lewis Carroll, Dover Publications,1958). collection(john, book(Database: A Primer, C. J. Date, Addison-Wesley,1983). collection(john, book(Problem-Solving Methods in AI, Nils Nilsson, McGraw-Hill,1971). collection(smith, book(Alice, in Wonder land, Lewis Carroll, The New American Library,19

30、60). collection(smith, book(Fables of Aesop, Aesop-Calder, Dover Publications,1967).,复合对象的应用,域结构图,域,第0层(结构),第1层(对象),Domain Structure Diagram,collection,collector,book,title,author,publisher,year,谓词结构图,Predicate Structure Diagram,谓词 (主函子),函子,第0层,第1层,第2层,domains personal_library=book(title,author,publ

31、ication) publication=publication(publisher,year) collector,title,author,publisher=symbol year=integer predicates collection(collector,personal_library) clauses collection(kahn, book(The Computer and the Brain, von Neumann, publication(Yale University Press,1958). collection(kahn, book(Symbolic Logic

32、, Lewis Carroll, publication(Dover Publications,1958). collection(john, book(Database: A Primer, C. J. Date, publication(Addison-Wesley,1983). collection(john, book(Problem-Solving Methods in AI, Nils Nilsson, publication(McGraw-Hill,1971). collection(smith, book(Alice, in Wonder land, Lewis Carroll

33、, publication(The New American Library,1960). collection(smith, book(Fables of Aesop, Aesop-Calder, publication(Dover Publications,1967).,三层域结构和四层谓词结构,personal_library,book,title,author,publication,year,域结构图,域,第0层,第1层,Domain Structure Diagram,collection,collector,book,title,author,publisher,year,谓词结

34、构图,Predicate Structure Diagram,谓词 (主函子),函子,第0层,第1层,第2层,publisher,第2层,publisher,第3层,4.5 表与递归,表是含有任意数目的其他对象的一个对象。,一个包含1,2,3的表可被写成：1,2,3,表中的每个项被称为一个元素。,在域说明中需要对表类型进行说明。如：,domains integerlist=integer* predicates number(integerlist),表头：是表中的第一个元素。如：表a,b,c中a是表头。,表尾：是表中除表头外的另一张表。如：表a,b,c中b,c是表尾。,空表：没有元素的表 。对于表c,c是表头， 是表尾。,a,b,c,d,a,b,c,d,b,c,d,c,d,d, ,Prolog 提供一种使表头和表尾明确分开的方法：用逗号将元素分开，用 | 号将表头和表尾分开。如：,a,b,c 等价于a|b,c 等价于 a|b|c 等价于a|b|c| ,打印表中元素的例子：,domains list=integer* predicates wr