prolog语言.ppt

1、PROLOG 语言,Prolog在英语中的意思就是Programming in LOGic（逻辑编程）。 它是建立在逻辑学的理论基础之上的， 最初是运用于自然语言的研究领域。然而现在它被广泛的应用在人工智能的研究中，它可以用来建造专家系统、自然语言理解、智能知识库等。 它对一些通常的应用程序的编写也很有帮助。使用它能够比其他的语言更快速地开发程序，因为它的编程方法更象是使用逻辑的语言来描述程序。,PROLOG特点,超高级语言 说明性语言 (对于某些问题)只要告诉计算机做什么 表达力强 坚实的数学基础 一阶谓词逻辑 自动回溯 支持递归归调用 广泛应用于AI领域,PROLOG要点,DOMAINS(

2、论域段） PREDICATES（谓词定义） CLAUSES（事实及规则段） GOAL（目标）,predicates thief(symbol) likes(symbol,symbol) may_steal(symbol,symbol) clauses thief(john). likes(tom,food). likes(john,wine). likes(john,X):- likes(tom,X). may_steal(X,Y):- thief(X),likes(X,Y).,Dialog Goal : may_steal(john,What) What=food What=wine 2 S

3、olutions,运行,表（List） ,表由方括号与元素组成，元素又可是一个表。非空表可用x|y表示，x表头 y表尾 例: a,b,c a | b,c b,c b | c c c | 空表无表头！,表头 a 表尾 b,c,表头 b 表尾 c,表头 c 表尾 ,匹配与回溯,自动实现的搜索算法之一匹配,Prolog语言能自动将目标与知识库子句集中的事实、规则的结论部分（从第一句开始到最后一句为止）逐句进行匹配。下述三种情况之一者匹配成功： （1） 完全相同 例：thief(john) 与 thief(john) （2）谓词相同，相应项一为变量，一为常量 变量实例化 例：thief(Y)与thie

4、f(john) 匹配结果：Y 被实例化为john john/Y （3）谓词相同，相应项均为变量 变量一致化,clauses likes(tom,talk). /*1*/ likes(bill,swim). /*2*/ likes(bill,talk). /*3*/ likes(mary,wine). /*4*/ likes(tom,X):- likes(mary,X). /*5*/ 如果Goal：likes(bill,talk) 与第3句匹配一致 如果Goal： likes(tom,wine) 与第5句左部匹配wine/ X 任务转化为likes(mary,wine) 与第3句匹配一致,例1,

5、Dialog Goal:likes(bill,talk) True,Dialog Goal:likes(tom,wine) True,运行,运行,clauses likes(tom,talk). /*1*/ likes(bill,swim). /*2*/ likes(bill,talk). /*3*/ likes(mary,wine). /*4*/ likes(tom,X):- likes(mary,X). /*5*/ 如果Goal：likes(tom,swim) 与第5句左部匹配swim / X 任务转化为likes(mary,swim) 与15匹配均失败,Dialog Goal: like

6、s(tom,swim) False,运行,clauses fact(1,1 ) . /*1*/ fact(X,Y):- X1 =X-1, fact(X1,Y1), Y=X*Y1 . /*2*/ 设Goal：fact(2,N) 与1匹配失败 与2左部匹配成功 2/X , N/Y 产生三个子目标： (1) X1=2-1 (2) fact(X1,Y1) (3) N=2*Y1 (1) X1=1 立即成功 (2) fact(1,Y1) 与/*1*/ 匹配成功 1/Y1 (3) N=2*1=2 成功,例2,Dialog Goal:fact(2,N) N=2 1 Solutions,运行,自动实现的搜索算法

7、之二回溯,例: clauses likes(tom,talk). /*1*/ likes(bill,swim). /*2*/ likes(bill,talk). /*3*/ friend(john,X):-likes(X,talk),likes(X,swim) /*4*/ 设Goal:friend(john,Who) 搜索指针 P1=13失败，p1=4成功，Who/X 变量一致化，产生两个子目标： (1) likes(Who,talk) P2-1=1 成功, 变量实例化 tom/ Who (2) likes(tom,swim) P2-2=14均失败, Who 与tom 脱解, 回溯试图重新满足

8、子目标(1),重作： (1) likes(Who,talk) P2-1=2失败, P2-1=3成功 bill/ Who (2) likes(bill,swim) P2-2=1失败, P2-2=2成功 子目标(1) (2)都成功，所以目标成功,运行,Dialog Goal:friend(john,Who) Whobill 1 Solutions,DOMAINS child=symbol age=integer PREDICATES player(peter,9) player(paul,10) player(chris,9) player(susan,9) goal player(Person1

9、,9), player(Person2,9), PersonPerson2,PROLOG自动搜索机制,为满足一目标，从知识库顶起以遍历方式逐一匹配。如与一事实匹配成功，则将代换表作用于右邻；如与一规则左部匹配成功，则将代换表作用于规则右部化为一系列子目标。 为满足一个子目标，从知识库顶起逐一匹配。如匹配成功，则返回代换表，并继续试图满足其右邻子目标；如匹配失败（指针到了库底仍不成功），则设法重新满足其左邻子目标回溯。回溯时变量脱解。,3、影响回溯的手段fail和cut,注意：Turbo Prolog “外Goal” 和“程序内goal” 有“勤” “懒”之分 * 对话框中输入的外Goal主动找

10、出全部解并报告有几个Solutions 例：predicates likes(symbol,symbol) clauses likes(tom,food). likes(tom,wine). likes(tom,book).,Dialog Goal:likes(tom,What) What=food What=wine What=book 3 Solutions,外Goal运行情况,常识：“外Goal” 和“程序内goal” 有“勤” “懒”之分,* 程序内goal则是找到一个解就停止搜索了 例：predicates likes(symbol,symbol) goal likes(tom,W)

11、,write(“tom likes ”,W,”n”). clauses likes(tom,food). likes(tom,wine). likes(tom,book). 显然，此结果不完备,Dialog Tom likes food,Dialog tom likes food Press the SPACE bar,程序内goal 运行结果,影响回溯的手段之一fail,fail无条件失败，引起回溯 例： predicates likes(symbol,symbol) goal likes(tom,W),write(“tom likes ”,W,”n”),fail. clauses like

12、s(tom,food). likes(tom,wine). likes(tom,book). fail的作用是引起回溯，以得到全部解 （此例如采用外Goal，不加fail 就能得到全部解 ）,运行结果,Dialog tom likes food. tom likes wine. tom likes book. Press the SPACE bar,影响回溯的手段之二cut (截断),cut无条件成功，并截断回溯 (也可以用! 表示),影响回溯的手段之二cut,例：p:- q1,q2,r1,r2. p:- s1,s2. 逻辑关系是 if q1 q2r1 r2 or s1 s2 then p,如

13、果加入 cut p:- q1,q2,!,r1,r2. p:- s1,s2. 逻辑关系变为 if (if q1 q2 then r1 r2 else s1 s2 ) then p,q1,P,P,P2,P1,r1,q2,r2,s1,s2,可以回溯,P,P,P2,P1,r1,q2,r2,s1,s2,q1,！,回溯,回溯,截断,影响回溯的手段之二cut,单解问题（外Goal） cut 放在产生器与测试器之后，一旦产生一个合适解，立即停止递归。 例1：用加法、乘法定义整除（为了观察过程加 trace，F10单步运行） trace predicates div(real, real, real) int(

14、real) clauses div(A,B,R):- int(R), R*BA, ! . int(0). int(X):- int(Y), X=Y+1.,Dialog Goal : div(5,3,Z) Z=1 1 Solution,运行示例,影响回溯的手段之二cut,如不加cut ，则无休止地产生与测试，白费机时，直到堆栈满 若在程序内加goal goal div(5,3,Z), write(“5/3=”,Z,”n”). 由于内goal的特性，子句中不必加cut，一旦得到一个解，自动停止,影响回溯的手段之二cut,单选问题 情况1 动作1 情况n 动作n 例1：sample(case1,X)

15、:-!,action1(X). sample(casen,X):-!,actionn(X). 比不用！省机时，一旦action1(X)立即停止搜索。,影响回溯的手段之二cut,例2： predicates sum_to(integer,integer) clauses sum_to(1,1):-! sum_to(N,Res):-N1=N-1, sum_to(N1,Res1),Res=Res+N. 如无cut，则stack overflow,Dialog Goal:sum_to(3,X) X=6 1 Solutions,影响回溯的手段之二cut,排除型选择 !与fail配合，使其父结点立即彻底失败 例：clauses super_speed(tom). drunk_drive(tom). legal(X):- super_speed(X),fail. legal(X):- drunk_drive(X),fail. legal(X). 这个