人工智能导论IntroductiontoArtificialIntelligence.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 逻辑程序设计语言PROLOG,2.1 基本PROLOG,2.2 Turbo PROLOG程序设计,第1页,2.1 基本PROLOG,2.1.1 PROLOG语句,1.,事实,(fact),格式,谓词名(项表).,student(john).,like(mary,music).,abc.,repeat.,功效,普通表示对象性质或关系。,第2页,2.,规则,(rule),格式,谓词名(项表):-谓词名(项表),谓词名(项表).,bird(X):-animal(X),has(X,feather).,grandfather(X,Y):-,father(X,Z),father(Z,Y).,run:-start,step1(X),step2(X),end.,功效,普通表示对象间因果关系、蕴含关系或对应关系。,第3页,3.,问题,(question),格式,?-谓词名(项表),谓词名(项表).,?-student(john).,?-like(mary,X).,功效,问题表示用户问询,它就是程序运行目标。,第4页,2.1.2 PROLOG程序,PROLOG程序普通由一组事实、规则和问题组成。问题是程序执行起点,称为程序目标。,likes(bell,sports).,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,music).,?-friend(john,Y).,第5页,?-likes(mary,X).,或,?-likes(mary,music).,或,?-friend(X,Y).,或,?-likes(bell,sports),likes(mary,music),friend(john,X).,第6页,2.1.3 PROLOG程序运行机理,1.自由变量与约束变量,2.匹配合一,两个谓词可匹配合一,是指两个谓词名相同,参量项个数相同,参量类型对应相同,而且对应参量项还满足以下条件之一：,(1)假如两个都是常量,则必须完全相同。,(2)假如两个都是约束变量,则两个约束值必须相同。,(3)假如其中一个是常量,一个是约束变量,则约束值与常量必须相同。,(4)最少有一个是自由变量。,第7页,考虑下面各组谓词是否可匹配合一？,pre1(ob1,ob2,Z),pre1(ob1,ob3,Y),pre1(ob1,ob2,Z),pre1(ob1,X,ob3),pre1(ob1,ob2,Z),pre1(ob1,X,Y),第8页,3.回溯,所谓回溯,就是在程序运行期间,当某一个子目标不能满足(即谓词匹配失败)时,控制就返回到前一个已经满足子目标(假如存在话),并撤消其相关变量约束值,然后再使其重新满足。成功后,再继续满足原子目标。假如失败子目标前再无子目标,则控制就返回到该子目标上一级目标(即该子目标谓词所在规则头部)使它重新匹配。回溯也是PROLOG一个主要机制。,第9页,likes(bell,sports).,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,music).,?-friend(john,Y).,则求解目标为,friend(john,Y).,新目标,likes(X,reading),likes(X,music).,第10页,第11页,2.2 Turbo PROLOG程序设计,2.2.1 程序结构,/*注 释 */,编译指令,constants,常量说明,domains,域说明,database,数据库说明,predicates,谓词说明,goal,目口号句,clauses,子句集,第12页,例,假如把上节例子程序作为,Turbo PROLOG程序,则应改写为：,DOMAINS,name=symbol,PREDICATES,likes(name,name).,friend(name,name),GOAL,friend(john,Y),write(Y=,Y).,CLAUSES,likes(bell,sports).,likes(mary,music).,likes(mary,sports).,likes(jane,smith).,friend(john,X):-likes(X,sports),likes(X,music).,friend(john,X):-likes(X,reading),likes(X,music).,第13页,领域段,该段说明程序谓词中全部参量项所属领域。Turbo PROLOG标准领域包含整数、实数、符号、串和符号等,其详细说明以下表所表示。,第14页,谓词段,该段说明程序中用到谓词名和参量项名(但Turbo PROLOG 内部谓词无须说明),子句段,该段是Turbo PROLOG程序关键,程序中全部事实和规则就放在这里,系统在试图满足程序目标时就对它们进行操作。,目标段,该段是放置程序目标地方。目标段能够只有一个目标谓词,比如上面例子中就只有一个目标谓词；也能够含有多个目标谓词,如,goal,readint(X),Y=X+3,write(Y=,Y).,就有三个目标谓词。这种目标称为复合目标。,第15页,2.2.2 数据与表示式,1.领域,1)标准领域,整数、实数、字符、串和符号,2)结构,结构也称复合对象,普通形式为,函子(参量表),likes(Tom,sports(football,basketball,table_tennis),).,reading(王宏,book(人工智能技术导论,西安电子科技大学出版社),).,friend(,father(Li),father(Zhao),).,第16页,复合对象在程序中说明,需分层进行。比如,对于上面谓词,likes(Tom,sports(football,basketball,table_tennis).,在程序中可说明以下：,domains,name=symbol,sy=symbol,sp=sports(sy,sy,sy),predicates,likes(name,sp),第17页,3)表,表普通形式,x1,x2,xn,其中xi(i=1,2,n)为PROLOG项,普通要求同一个表元素必须属于同一领域。不含任何元素表称为空表,记为。,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),第18页,表说明方法是在其组成元素说明符后加一个星号*。如：domains,lists=string*,predicates,pl(lists),比如，谓词,p(name(Liming),age(20),则需这么说明:,domains,rec=seg*,seg=name(string);age(integer),predicates,p(rec),第19页,2.常量与变量,Turbo PROLOG常量有整数、实数、字符、串、符号、结构、表和文件这八种数据类型。同理,Turbo PROLOG变量也就有这八种取值。另外,变量名要求必须是以大写字母或下划线开头字母、数字和下划线序列,或者只有一个下划线。这后一个变量称为无名变量。,第20页,3.算术表示式,Turbo PROLOG提供了五种最基本算术运算：加、减、乘、除和取模,对应运算符号为+、-、*、/、mod。这五种运算次序为：*、/、mod优先于+、-。,数学中算术表示式 PROLOG中算术表示式,x+yz X+Y*Z,ab-c/d A*B-C/D,u mod v U mod V,Y=X+5,X=X+1,第21页,4.,关系表示式,Turbo PROLOG提供了六种惯用关系运算,即小于、小于或等于、等于、大于、大于或等于和不等于,其运算符依次为,=,数学中关系式 Turbo PROLOG中关系式,X+1Y X+1=Y,XY XY,第22页,brother(Name1,Name2):-,person(Name1,man,Age1),person(Name2,man,Age2),mother(Z,Name1),mother(Z,Name2),Age1Age2.,第23页,“=”使用方法,：,比较符,和,约束符,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结果。,第24页,2.2.3 输入与输出,(1)readln(X),(2)readint(X),(3)readreal(X),(4)readchar(X),(5)write(X1,X2,Xn),(6)nl,第25页,例,用输入输出谓词编写一个简单成绩 数据库查询程序。,PREDICATES,student(integer,string,real),grade,GOAL,grade.,CLAUSES,student(1,张三,90.2).,student(2,李四,95.5).,student(3,王五,96.4).,grade:-write(请输入姓名:),readln(Name),student(_,Name,Score),nl,write(Name,成绩是,Score).,grade:-write(对不起,找不到这个学生!).,第26页,2.2.4 分支与循环,1.,分支,将,IF x0 THEN x:=1,ELSE x:=0,用PROLOG实现则能够是,br:-x0,x=1.,br:-x=0.,第27页,2.,循环,程序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.,第28页,程序2：,student(1,张三,90.2).,student(2,李四,95.5).,student(3,王五,96.4).,print:-student(Number,Name,Score),write(Number,Name,Score),nl,fail.,print:-.,第29页,2.2.5 动态数据库,动态数据库操作谓词:,asserta(fact).,assertz(fact).,retract(fact).,例,asserta(student(20,李明,90.5).,retract(student(20,_,_).,第30页,2.2.6 表处理与递归,1.表头与表尾,表头是表中第一个元素；表尾,是表中除第一个元素外其余元素按原来次序组成表。,表头与表尾示例,表 表头 表尾,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 ,无定义 无定义,第31页,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,第32页,例,设计一个能判断对象X是表L组员程序。,分析,：,(1)假如X与表L中第一个元素(即表头)是同一个对象,则X就是L组员。,(2)假如X是L尾部组员,则X也就是L组员。,程序,：,member(X,X|_).,member(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,第33页,例,表拼接程序,即把两个表连接成一个表。,append(,L,L).,append(H|T,L2,H|Tn):-append(T,L2,Tn).,Goal:append(1,2,3,4,5,L).,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,第34页,Goal:append(1,2,3,Y,1,2,3,4,5).,Y=4,5,Goal:append(X,4,5,1,2,3,4,5).,X=1,2,3,Goal: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,X=1,2,3,Y=4,5,第35页,例,表输出。,print().,print(H|T):-write(H),print(T).,例,表倒置,即求一个表逆序表。,reverse(,).,reverse(H|T,L):-reverse(T,L1),append(L1,H,L).,第36页,2.2.7 回溯控制,截断谓词“!”语义：,(1)若将“!”插在子句体内作为一个子目标,它总是马上成功。,(2)若“!”位于子句体最终,则它就阻止对它所在子句头谓词全部子句回溯访问,而让回溯跳过该头谓词(子目标),去访问前一个子目标(假如有话)。,(3)若“!”位于其它位置,则当其后发生回溯且回溯到“!”处时,就在此处失败,而且“!”还使它所在子句头谓词(子目标)整个失败(即阻止再去访问头谓词其余子句(假如有话),即迫使系统直接回溯到该头谓词(子目标)前一个子目标(假如有话)。,第37页,例,考虑下面程序,：,p(a).(2-1),p(b).(2-2),q(b).(2-3),r(X):-p(X),q(X).(2-4),r(c).,对于目标:r(Y).,可有一个解,Y=b,但当把式(2-4)改为,r(X):-p(X),!,q(X).(2-4),时,却无解。为何呢？,第38页,例,设有程序：,g0:-g11,g12,g13.(2-5),g0:-g14.(2-6),g12:-g21,!,g23.(2-7),g12:-g24,g25.(2-8),给出目标:g0.,把子句(2-7)改为,g12:-g21,g23,!.(2-9),第39页,2.2.8 程序举例,例,一个简单路径查询程序。,predicates,road(symbol,symbol),path(symbol,symbol),clauses,road(a,b).,road(a,c).,road(b,d).,road(c,d).,road(d,e).,road(b,e).,path(X,Y):-road(X,Y).,path(X,Y):-road(X,Z),path(Z,Y).,第40页,Goal:path(a,e).,yes,Goal:path(e,a).,no,Goal：,run.,run:-path(a,X),write(X=,X),nl,fail.,run.,X=b,X=c,X=d,X=e,X=d,X=e,X=e,第41页,例,下面是一个求阶乘程序,程序中使用了递归。,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.,第42页,