逻辑程序设计语言PROLOG.ppt

《逻辑程序设计语言PROLOG.ppt》由会员分享，可在线阅读，更多相关《逻辑程序设计语言PROLOG.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第第2 2章章 逻辑程序设计语言逻辑程序设计语言PROLOGPROLOG 2.1 2.1 基本基本PROLOGPROLOG 2.2 Turbo PROLOG2.2 Turbo PROLOG程序设计程序设计 2.1 2.1 基本基本PROLOG PROLOG 2.1.1 PROLOG2.1.1 PROLOG的语句的语句 1. 1. 事实事实(fact)(fact) 格式格式 谓词名谓词名( (项表项表).). student(john). student(john). like(mary,music).like(mary,music). abc. abc. repeat. repeat. 功能

2、功能 一般表示对象的性质或关系。一般表示对象的性质或关系。 2. 2. 规则规则(rule)(rule) 格式格式 谓词名谓词名( (项表项表):-):-谓词名谓词名( (项表项表),),谓词名谓词名( (项表项表).). bird(X):-animal(X),has(X,feather). bird(X):-animal(X),has(X,feather). grandfather(X,Y):- grandfather(X,Y):- father(X,Z),father(Z,Y). father(X,Z),father(Z,Y). run:-start,step1(X),step2(X),e

3、nd. run:-start,step1(X),step2(X),end. 功能功能 一般表示对象间的因果关系、蕴含关系或对应一般表示对象间的因果关系、蕴含关系或对应关系。关系。 3. 3. 问题问题(question)(question) 格式格式?-?-谓词名谓词名( (项表项表),),谓词名谓词名( (项表项表).). ? ?-student(john).-student(john). ? ?-like(mary,X). -like(mary,X). 功能功能问题表示用户的询问问题表示用户的询问, , 它就是程序运行的它就是程序运行的目标。目标。 2.1.2 PROLOG2.1.2 PR

4、OLOG的程序的程序 PROLOGPROLOG程序一般由一组事实、程序一般由一组事实、 规则和问题组规则和问题组成。问题是程序执行的起点成。问题是程序执行的起点, , 称为程序的目标。称为程序的目标。 likes(bell,sports).likes(bell,sports). likes(mary,music). likes(mary,music). likes(mary,sports). likes(mary,sports). likes(jane,smith). likes(jane,smith). friend(john,X):- friend(john,X):-likes(X,rea

5、ding),likes(X,music). likes(X,reading),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music). ?-friend(john,Y). ?-friend(john,Y). ?-likes(mary,X).或或 ?-likes(mary,music).或或 ?-friend(X,Y).或或 ?-likes(bell,sports), likes(mary,music), friend(john,X

6、).2.1.3 PROLOG2.1.3 PROLOG程序的运行机理程序的运行机理 1. 1. 自由变量与约束变量自由变量与约束变量 2. 2. 匹配合一匹配合一 两个谓词可匹配合一两个谓词可匹配合一, , 是指两个谓词的名相同是指两个谓词的名相同, , 参量项的个数相同参量项的个数相同, , 参量类型对应相同参量类型对应相同, , 并且对应并且对应参量项还满足下列条件之一：参量项还满足下列条件之一： (1) (1) 如果两个都是常量如果两个都是常量, , 则必须完全相同。则必须完全相同。 (2) (2) 如果两个都是约束变量如果两个都是约束变量, , 则两个约束值必则两个约束值必须相同。须相同

7、。 (3) (3) 如果其中一个是常量如果其中一个是常量, , 一个是约束变量一个是约束变量, , 则约束值与常量必须相同。则约束值与常量必须相同。 (4) (4) 至少有一个是自由变量。至少有一个是自由变量。 考虑下面的各组谓词是否可匹配合一？考虑下面的各组谓词是否可匹配合一？ pre1(ob1,ob2,Z)pre1(ob1,ob2,Z) pre1(ob1, ob3,Y) pre1(ob1, ob3,Y) pre1(ob1,ob2,Z) pre1(ob1,ob2,Z) pre1(ob1,X, ob3) pre1(ob1,X, ob3) pre1(ob1,ob2,Z) pre1(ob1,ob2

8、,Z) pre1(ob1,X,Y) pre1(ob1,X,Y)3. 3. 回溯回溯 所谓回溯所谓回溯, , 就是在程序运行期间就是在程序运行期间, , 当某一个子当某一个子目标不能满足目标不能满足( (即谓词匹配失败即谓词匹配失败) )时时, ,控制就返回到控制就返回到前一个已经满足的子目标前一个已经满足的子目标( (如果存在的话如果存在的话), ), 并撤消并撤消其有关变量的约束值其有关变量的约束值, , 然后再使其重新满足。然后再使其重新满足。 成成功后功后, , 再继续满足原子目标。如果失败的子目标前再继续满足原子目标。如果失败的子目标前再无子目标再无子目标, , 则控制就返回到该子目标

9、的上一级目则控制就返回到该子目标的上一级目标标( (即该子目标谓词所在规则的头部即该子目标谓词所在规则的头部) )使它重新匹配。使它重新匹配。回溯也是回溯也是PROLOGPROLOG的一个重要机制。的一个重要机制。 likes(bell,sports).likes(bell,sports). likes(mary,music). likes(mary,music). likes(mary,sports). likes(mary,sports). likes(jane,smith). likes(jane,smith). friend(john,X):-likes(X,reading),like

10、s(X,music). friend(john,X):-likes(X,reading),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music). ?-friend(john,Y). ?-friend(john,Y).则求解目标为则求解目标为 friend(john,Y).friend(john,Y). 新目标新目标 likes(X,reading),likes(X,music).likes(X,reading),likes(X,

11、music). 2.2 Turbo PROLOG2.2 Turbo PROLOG程序设计程序设计2.2.1 2.2.1 程序结构程序结构 / /* * 注注 释释 * */ / 编译指令编译指令 constants constants 常量说明常量说明 domains domains 域说明域说明 database database 数据库说明数据库说明 predicates predicates 谓词说明谓词说明 goal goal 目标语句目标语句 clauses clauses 子句集子句集 例例 如果把上节的例子程序作为如果把上节的例子程序作为Turbo PROLOGTurbo PRO

12、LOG程序程序, , 则应改则应改写为：写为： DOMAINSDOMAINS name=symbol name=symbol PREDICATES PREDICATES likes(name,name). likes(name,name). friend(name,name) friend(name,name) GOAL GOAL friend(john,Y), write(Y=, Y). friend(john,Y), write(Y=, Y). CLAUSES CLAUSES likes(bell,sports). likes(bell,sports). likes(mary,music)

13、. likes(mary,music). likes(mary,sports). likes(mary,sports). likes(jane,smith). likes(jane,smith). friend(john,X):-likes(X,sports),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music). friend(john,X):-likes(X,reading),likes(X,music). friend(john,X):-likes(X,reading),likes(X,music). 领域段领域段该

14、段说明程序谓词中所有参量项所属的领域。该段说明程序谓词中所有参量项所属的领域。 Turbo PROLOGTurbo PROLOG的标准领域包括整数、实数、符号、串和符的标准领域包括整数、实数、符号、串和符号等号等, , 其具体说明如下表所示。其具体说明如下表所示。谓词段谓词段 该段说明程序中用到的谓词的名和参量项的名该段说明程序中用到的谓词的名和参量项的名( (但但Turbo PROLOG Turbo PROLOG 的内部谓词无须说明的内部谓词无须说明) )子句段子句段 该段是该段是Turbo PROLOGTurbo PROLOG程序的核心程序的核心, , 程序中的所有事程序中的所有事实和规则

15、就放在这里实和规则就放在这里, , 系统在试图满足程序的目标时就系统在试图满足程序的目标时就对它们进行操作。对它们进行操作。 目标段目标段 该段是放置程序目标的地方。该段是放置程序目标的地方。 目标段可以只有一目标段可以只有一个目标谓词个目标谓词, , 例如上面的例子中就只有一个目标谓词；例如上面的例子中就只有一个目标谓词； 也可以含有多个目标谓词也可以含有多个目标谓词, , 如如 goalgoal readint(X),Y=X+3,write(Y=,Y). readint(X),Y=X+3,write(Y=,Y).就有三个目标谓词。就有三个目标谓词。 这种目标称为复合目标。这种目标称为复合目

16、标。 2.2.2 2.2.2 数据与表达式数据与表达式1. 1. 领域领域 1) 标准领域标准领域 整数、实数、整数、实数、 字符、字符、 串和符号串和符号 2) 结构结构 结构也称复合对象结构也称复合对象, 一般形式为一般形式为 函子函子(参量表参量表)likes(Tom, sports(football, basketball, table_tennis).reading(王宏王宏,book(人工智能技术导论人工智能技术导论,西安电子科技西安电子科技大学出版社大学出版社). friend(father(Li), father(Zhao). 复合对象在程序中的说明复合对象在程序中的说明, ,

17、 需分层进行。需分层进行。 例如例如, , 对于上面的谓词对于上面的谓词 likes(Tom, sports(football, likes(Tom, sports(football, basketball, table_tennis).basketball, table_tennis). 在程序中可说明如下：在程序中可说明如下： domainsdomains name=symbol name=symbol sy=symbol sy=symbol sp=sports(sy, sy, sy) sp=sports(sy, sy, sy) predicates predicates likes(na

18、me, sp) likes(name, sp) 3) 3) 表表 表的一般形式表的一般形式 x1, x2, x1, x2, , xn, xn 其中其中xi(i=1, 2, xi(i=1, 2, , n), n)为为PROLOGPROLOG的项的项, , 一般要求同一个一般要求同一个表的元素必须属于同一领域。不含任何元素的表称为空表表的元素必须属于同一领域。不含任何元素的表称为空表, , 记为记为 。 1, 2, 31, 2, 3 apple, orange, banana, grape, caneapple, orange, banana, grape, cane PROLOG,PROGRAM

19、MING,in logicPROLOG,PROGRAMMING,in logic a, ba, b, , c, dc, d, , e e name(LiMing), age(20),sex(male),addr(xian)name(LiMing), age(20),sex(male),addr(xian)表的说明方法是在其组成元素的说明符后加一个星号表的说明方法是在其组成元素的说明符后加一个星号* *。 如：如： domainsdomains lists=string lists=string* * predicates predicates pl(lists) pl(lists)例如，谓词例

20、如，谓词 p(p(name(Liming), age(20)name(Liming), age(20) )则需这样说明则需这样说明: : domains domains rec=seg rec=seg* * seg=name(string);age(integer) seg=name(string);age(integer) predicates predicates p(rec) p(rec) 2. 2. 常量与变量常量与变量 Turbo PROLOGTurbo PROLOG的常量有整数、实数、的常量有整数、实数、 字符、字符、串、符号、结构、表和文件这八种数据类型。同串、符号、结构、表和文

21、件这八种数据类型。同理理, Turbo PROLOG, Turbo PROLOG的变量也就有这八种取值。另的变量也就有这八种取值。另外外, , 变量名要求必须是以大写字母或下划线开头变量名要求必须是以大写字母或下划线开头的字母、数字和下划线序列的字母、数字和下划线序列, , 或者只有一个下划或者只有一个下划线。线。 这后一种变量称为无名变量。这后一种变量称为无名变量。 3. 3. 算术表达式算术表达式 Turbo PROLOGTurbo PROLOG提供了五种最基本的算术运算：加、减、提供了五种最基本的算术运算：加、减、 乘、除和取模乘、除和取模, , 相应运算符号为相应运算符号为+ +、 -

22、 -、* *、 / /、 modmod。 这五种运算的顺序为：这五种运算的顺序为： * *、/ /、 modmod优先于优先于+ +、 - -。 数学中的算术表达式数学中的算术表达式 PROLOGPROLOG中的算术表达式中的算术表达式 x+yz x+yz X+YX+Y* *Z Z ab-c/d ab-c/d A A* *B-C/DB-C/D u mod v U mod V u mod v U mod V Y=X+5 X=X+1 4.4.关系表达式关系表达式 Turbo PROLOGTurbo PROLOG提供了六种常用的关系运算提供了六种常用的关系运算, , 即小于、即小于、 小于或等于、等

23、于、大于、大于或等于和不等于小于或等于、等于、大于、大于或等于和不等于, , 其运其运算符依次为算符依次为 , , =, , , =, 数学中的关系式数学中的关系式 Turbo PROLOGTurbo PROLOG中的关系式中的关系式 X+1Y X+1Y X+1=YX+1=Y XY XY XY XY brother(Name1, Name2):-brother(Name1, Name2):- person(Name1, man, Age1), person(Name1, man, Age1), person(Name2, man, Age2), person(Name2, man, Age2)

24、, mother(Z, Name1), mother(Z, Name1), mother(Z, Name2), mother(Z, Name2), Age1Age2. Age1Age2. “= =”的用法的用法 ：比较符比较符和和约束符约束符 p(X, Y, Z):-Z=X+Y.p(X, Y, Z):-Z=X+Y.当变量当变量X X、Y Y、Z Z全部被实例化时全部被实例化时, , “= =”就是比较符。就是比较符。 如：如： 对于问题对于问题 Goal: p(3, 5, 8).Goal: p(3, 5, 8).机器回答：机器回答： yesyes。 而对于而对于 Goal: p(3, 5, 7

25、). Goal: p(3, 5, 7). 机器回答：机器回答： nono。 但当但当X, YX, Y被实例化被实例化, , 而而Z Z未被实例化时未被实例化时, , “= =”号就是约束符。号就是约束符。 如：如： Goal: p(3, 5, Z).Goal: p(3, 5, Z).机器回答：机器回答： Z=8Z=8这时这时, , 机器使机器使Z Z实例化为实例化为X+YX+Y的结果。的结果。 2.2.3 2.2.3 输入与输出输入与输出 (1) readln (X) (1) readln (X) (2) readint (X) (2) readint (X) (3) readreal (X)

26、 (3) readreal (X) (4) readchar (X) (4) readchar (X) (5) write (X1, X2, (5) write (X1, X2, ,Xn),Xn) (6) nl (6) nl 例例 用输入输出谓词编写一个简单的成绩用输入输出谓词编写一个简单的成绩 数据库查询程序。数据库查询程序。 PREDICATESPREDICATES student(integer, string, real) student(integer, string, real) grade grade GOAL GOAL grade. grade. CLAUSES CLAUSES

27、 student(1, student(1, 张三张三, 90.2). , 90.2). student(2, student(2, 李四李四, 95.5)., 95.5). student(3, student(3, 王五王五, 96.4). , 96.4). grade: -write( grade: -write(请输入姓名请输入姓名:), readln(Name), :), readln(Name), student(_, Name, Score), student(_, Name, Score), nl, write(Name, nl, write(Name, 的成绩是的成绩是, S

28、core)., Score). grade: -write( grade: -write(对不起对不起, , 找不到这个学生找不到这个学生!).!).2.2.4 2.2.4 分支与循环分支与循环1. 1. 分支分支 将将 IF x0 THEN x:=1IF x0 THEN x:=1 ELSE x:=0 ELSE x:=0用用PROLOGPROLOG实现则可以是实现则可以是 br:-x0, x=1.br:-x0, x=1. br:-x=0. br:-x=0. 2. 2. 循环循环 程序程序1 1： student(1, student(1, 张三张三, 90.2)., 90.2). studen

29、t(2, student(2, 李四李四, 95.5)., 95.5). student(3, student(3, 王五王五, 96.4)., 96.4). print:-student(Number, Name, Score), print:-student(Number, Name, Score), write(Number, Name, Score), write(Number, Name, Score), nl, nl, Number=3. Number=3. 程序程序2 2： student(1, student(1, 张三张三, 90.2)., 90.2). student(2,

30、 student(2, 李四李四, 95.5)., 95.5). student(3, student(3, 王五王五, 96.4)., 96.4). print:-student(Number, Name, Score), print:-student(Number, Name, Score), write(Number, Name, Score), nl, write(Number, Name, Score), nl, fail. fail. print:-. print:-. 2.2.5 2.2.5 动态数据库动态数据库 动态数据库操作谓词动态数据库操作谓词: : asserta( as

31、serta(factfact).). assertz( assertz(factfact).). retract( retract(factfact). ). 例例 asserta(student(20, asserta(student(20, 李明李明, 90.5)., 90.5). retract(student(20,_,_). retract(student(20,_,_).2.2.6 2.2.6 表处理与递归表处理与递归 1.1.表头与表尾表头与表尾 表头是表中的第一个元素；表尾表头是表中的第一个元素；表尾是表中除第一个元是表中除第一个元素外的其余元素按原来顺序组成的表。素外的其余元

32、素按原来顺序组成的表。 表头与表尾示例表头与表尾示例 表表 表头表头 表尾表尾 2. 2. 表的匹配合一表的匹配合一 表的匹配合一示例表的匹配合一示例 表表1 表表2 合一后的变量值合一后的变量值 X=a, Y= X=a, Y= X=a, Y= X=a, Y= a X X=a, Y= 例例 设计一个能判断对象设计一个能判断对象X X是表是表L L的成员的程序。的成员的程序。 分析：分析： (1) (1) 如果如果X X与表与表L L中的第一个元素中的第一个元素( (即表头即表头) )是同一个是同一个对象对象, , 则则X X就是就是L L的成员。的成员。 (2) (2) 如果如果X X是是L

33、L的尾部的成员的尾部的成员, , 则则X X也就是也就是L L的成员。的成员。 程序：程序： member(X, member(X, X|_X|_).). member(X, member(X, _|Tail_|Tail):-member(X, Tail).):-member(X, Tail). Goal: member(a, Goal: member(a, a, b, c, da, b, c, d).). yes yes Goal: member(e, Goal: member(e, a, b, c, da, b, c, d).). no no Goal: member(X, Goal: m

34、ember(X, a, b, c, da, b, c, d).). X=a X=a 例例 表的拼接程序表的拼接程序, , 即把两个表连接成一个表。即把两个表连接成一个表。 append(append(, L, L)., L, L). append( append(H|TH|T, L2, L2,H|TnH|Tn):-append(T,L2, Tn).):-append(T,L2, Tn). Goal: append( Goal: append(1, 2, 31, 2, 3, , 4, 54, 5, L)., L). L= L=1, 2, 3, 4, 51, 2, 3, 4, 5 Goal: ap

35、pend(Goal: append(1,2,31,2,3, ,4,54,5, ,1,2,3,4,51,2,3,4,5).). yes yes Goal: append( Goal: append(1,2,31,2,3, ,4,54,5, ,1,2,3,4,5,61,2,3,4,5,6). ). no no Goal: append(Goal: append(1, 2, 31, 2, 3, Y, , Y, 1, 2, 3, 4, 51, 2, 3, 4, 5).). Y= Y=4, 54, 5 Goal: append(X, Goal: append(X, 4, 54, 5, , 1, 2, 3

36、, 4, 51, 2, 3, 4, 5).). X= X=1, 2, 31, 2, 3 Goal: append(X, Y, Goal: append(X, Y, 1, 2, 3, 4, 51, 2, 3, 4, 5).). X= X=, Y=, Y=1, 2, 3, 4, 51, 2, 3, 4, 5 X=X=1 1, Y=, Y=2, 3, 4, 52, 3, 4, 5 X=X=1, 21, 2, Y=, Y=3, 4, 53, 4, 5 X=X=1, 2, 31, 2, 3, Y=, Y=4, 54, 5 例例 表的输出。表的输出。 print(print().). print( pri

37、nt(H|TH|T):-write(H), print(T).):-write(H), print(T).例例 表的倒置表的倒置, , 即求一个表的逆序表。即求一个表的逆序表。 reverse(reverse(, ,).). reverse( reverse(H|TH|T,L):-reverse(T,L1), ,L):-reverse(T,L1), append(L1, append(L1,H H,L). ,L). 2.2.7 2.2.7 回溯控制回溯控制 截断谓词截断谓词“! !”的语义：的语义： (1) (1) 若将若将“! !”插在子句体内作为一个子目标插在子句体内作为一个子目标, ,

38、它总它总是立即成功。是立即成功。 (2) (2) 若若“! !”位于子句体的最后位于子句体的最后, , 则它就阻止对它所则它就阻止对它所在子句的头谓词的所有子句的回溯访问在子句的头谓词的所有子句的回溯访问, , 而让回溯跳过而让回溯跳过该头谓词该头谓词( (子目标子目标), ), 去访问前一个子目标去访问前一个子目标( (如果有的话如果有的话) )。 (3) (3) 若若“! !”位于其他位置位于其他位置, , 则当其后发生回溯且回则当其后发生回溯且回溯到溯到“! !”处时处时, , 就在此处失败就在此处失败, , 并且并且“! !”还使它所在子还使它所在子句的头谓词句的头谓词( (子目标子目

39、标) )整个失败整个失败( (即阻止再去访问头谓词即阻止再去访问头谓词的其余子句的其余子句( (如果有的话如果有的话), ), 即迫使系统直接回溯到该头即迫使系统直接回溯到该头谓词谓词( (子目标子目标) )的前一个子目标的前一个子目标( (如果有的话如果有的话)。 例例 考虑下面的程序考虑下面的程序： p(a). p(a). (2-1) (2-1) p(b). p(b). (2-2)(2-2) q(b). q(b). (2-3) (2-3) r(X):-p(X), q(X). (2-4) r(X):-p(X), q(X). (2-4) r(c). r(c). 对于目标对于目标: r(Y).:

40、 r(Y). 可有一个解可有一个解 Y=bY=b 但当把式但当把式(2-4)(2-4)改为改为 r(X):-p(X), !, q(X). (2-4)r(X):-p(X), !, q(X). (2-4) 时时, , 却无解。却无解。 为什么呢？为什么呢？ 例例 设有程序：设有程序： g0:-g11, g12, g13. g0:-g11, g12, g13. (2-5) (2-5) g0:-g14. g0:-g14. (2-6) (2-6) g12:-g21, !, g23. g12:-g21, !, g23. (2-7) (2-7) g12:-g24, g25. (2-8)g12:-g24, g

41、25. (2-8) 给出目标给出目标: g0. : g0. 把子句把子句(2-7) (2-7) 改为改为 g12:-g21, g23, !. (2-9) g12:-g21, g23, !. (2-9) 2.2.8 2.2.8 程序举例程序举例例例 一个简单的路径查询程序。一个简单的路径查询程序。 predicatespredicates road(symbol, symbol) road(symbol, symbol) path(symbol, symbol) path(symbol, symbol)clausesclauses road(a, b). road(a, b). road(a,

42、c). road(a, c). road(b, d). road(b, d). road(c, d). road(c, d). road(d, e). road(d, e). road(b, e). road(b, e). path(X, Y):-road(X, Y). path(X, Y):-road(X, Y). path(X, Y):-road(X, Z), path(Z, Y). path(X, Y):-road(X, Z), path(Z, Y). Goal: path(a, e).Goal: path(a, e). yesyesGoal :path(e, a).Goal :path

43、(e, a). nonoGoal Goal ： run.run. run:-path(a, X), write(X=, X), nl, fail. run:-path(a, X), write(X=, X), nl, fail. run. run. X=bX=b X=cX=c X=dX=d X=eX=e X=dX=d X=eX=e X=eX=e 例例 下面是一个求阶乘程序下面是一个求阶乘程序, , 程序中使用了递归。程序中使用了递归。 domains n, f = integer predicates factorial(n, f) goal readint(I), factorial(I, F), write(I, !=, F). clauses factorial(1, 1). factorial(N, Res):- N0, N1=N-1, factorial(N1, FacN1), Res=N*FacN1.