人工智能与专家系统第四章 智能程序设计

第四章PROLOG语言与智能程序设计第一节PROLOG语言的基本知识第二节PROLOG程序设计基础第三节对回溯的控制第四节PROLOG的基本程序段第一节PROLOG语言的基本知识一、PROLOG语言简介二、PROLOG语言的特点1、PROLOG语言是一种描述型语言2、数据和程序是统一的3、自动实现模式匹配和回溯4、程序易于编写和阅读5、语句类型少，语法简明第一节PROLOG语言的基本知识三、PROLOG语言的三种基本语句1、事实•含义——表示对象具有某种性质，或某几个对象之间的关系•形式谓词（对象1，对象2，…，对象n），n为任意正整数裸谓词•注意：对象之间用逗号分开全部对象用括号括住谓词必须以小写字母开头每个事实都用一个实心句点结束第一节PROLOG语言的基本知识•示例man(zhangsan).is(sun,big).on(book,table).on(f,c).on(c,b).on(b,a).on(e,d).block(a).block(b).abcfde第一节PROLOG语言的基本知识•最简单的PROLOG程序由两部分组成谓词部分——定义谓词predicatesname(symbol,symbol,…)字句部分——列出所有事实clausesname(对象1,对象2,…).第一节PROLOG语言的基本知识•一个简单的程序predicatesis(symbol,symbol)has(symbol,symbol)clausesis(“王”,”年龄小”).is(“刘”,”个头高”).is(“李”,”有音乐天才”).has(“张”,”书”).goal:is(“刘”,”个头高”)yesgoal:is(“王”,”有音乐天才”)nogoal:has(“张”,”书”)yesgoal:has(“书”,”张”)no第一节PROLOG语言的基本知识2、规则•含义——表示事物成立所要遵循的法则，即事物之间的新关系•形式事实Dif事实A，事实B，事实C，…事实D:-事实A，事实B，事实C，…•注意：规则头只能有一个事实规则体部可有多个事实规则体中各个事实之间用逗号连接表示“与”关系每个规则都用一个实心句点结束第一节PROLOG语言的基本知识•示例predicatesmother(symbol,symbol)grandmother(symbol,symbol)clausesmother(“钱”,”孙”).mother(“孙”,”李”).mother(“王”,”张”).grandmother(X,Y)ifmother(X,Z),mother(Z,Y)goal:grandmother(“钱”,”李”)yesgoal:grandmother(“孙”,”张”)no第一节PROLOG语言的基本知识3、询问•含义——询问对象之间某种关系是否成立的疑问句•形式goal:事实1，事实2，事实3，…，事实nn为任意正整数•注意：各个事实之间用逗号连接表示“与”关系表示：“事实1，事实2，事实3，…，事实n”同时成立吗？第一节PROLOG语言的基本知识四、项1、项的定义•项∷=常量∣变量∣结构•常量原子：对象的名字、谓词函数名（小写字母开头）数字•变量暂时不能命名或不需要命名的对象以大写字母开头匿名变量：on(_,a);mother(_,”李”）自由变量和约束变量第一节PROLOG语言的基本知识•结构又称复合项，是由一组其他对象组成的单个对象包括：函数项：readchar(X)、mother(“李”,“孙”）表：[a,b,c]表达式：2*3+17结构的嵌套accident(date(year,month,day),who,place)第一节PROLOG语言的基本知识2、项的匹配规则（1）若A、B是项，A是自由变量，则B无论是何值，A可以被B匹配（2）常量与自身匹配成功（3）结构的每一对应成分匹配，则匹配成功第一节PROLOG语言的基本知识五、表1、概念•表是具有相同类型对象的有序集合•如：[1,2,3]、[a,b,c]、[a,b(f,c),d]、[]2、表头、表尾•表头——表中第一个元素•表尾——表中的其余部分，可以是另一张表3、表的匹配•表中的常量完全相同才匹配•表中的变量可与任何对象匹配•表头只与一个分量匹配，表尾可与一个表匹配第二节PROLOG程序设计基础一、PROLOG程序的组成1、前提部分（条件）——包括有关的事实和规则2、问题部分（目标）——问题求解的目标结果二、PROLOG程序的设计步骤1、说明事实2、定义规则3、明确目标第二节PROLOG程序设计基础三、判定规则中变量值的原则1、在同一条规则中，所有相同名字的变量具有相同的内容2、如果规则头中的变量被约束了，则规则体中的同名变量也被约束为相同的内容3、当规则头中的变量未被约束时，如果规则体中的同名变量被约束了，则规则头中的同名变量和规则体中的其他同名变量也被约束为相同的内容4、如果多条规则中有相同名字的变量，则这些同名变量不相关5、只有规则在使用时，规则中的变量才被约束第二节PROLOG程序设计基础四、PROLOG程序的目标求解过程1、匹配与回溯predicatesperson(symbol,symbol)clausesperson(z,m).person(y,w).person(c,w).person(l,m).goal:person(X,m)X=zX=l第二节PROLOG程序设计基础predicateslikes(symbol,symbol)clauseslikes(zhang,flower).likes(zhang,wine).likes(wang,wine).likes(wang,zhang).goal:likes(wang,X)X=wineX=zhanggoal:likes(zhang,X),likes(wang,X)X=wine第二节PROLOG程序设计基础2、包含多个子目标的问题求解过程goal:事实1，事实2，…，事实n3、示例dish(pork).dish(fish).main(rice).main(bread).fruit(apple).fruit(orange).meal(D,M,F)ifdish(D),main(M),fruit(F).goal:meal(D,M,F)第二节PROLOG程序设计基础五、规则的递归描述1、概念•在规则中，将自身作为一个成份，则称此规则是递归的•如：on(a4,a3).on(a3,a2).on(a2,a1).top(An,A1)ifon(An,A1).top(An,A1)ifon(A2,A1),top(An,A2).goal:top(a4,a1)a1a2a3a4第二节PROLOG程序设计基础2、示例（1）求0n1)1(01!nnnnpower(0,1).power(N,Y)ifN1=N-1,power(N1,Y1),Y=N*Y1goal:power(2,Y)Y=2(2)求表的长度length([],0).length([H︱T],X)iflength(T,X1),X=X1+1goal:length([a,b,c],X)X=3第二节PROLOG程序设计基础（3）x是否是表中的一个member(X,[X︱_]).member(X,[_︱Y])ifmember(X,Y).goal:member(b,[a,b,c])yes(4)求表中最后一个元素last([X︱[]],X).last([Y︱Z],P)iflast(Z,P).goal:last([a,b,c],Y)Y=c第二节PROLOG程序设计基础（5）表的连接append([],L,L).append([H︱L1],L2,[H︱L3],)ifappend(L1,L2,L3)goal:append(L1,L2,[a,b,c])第三节对回溯的控制一、截断1、示例predicatesperson(symbol,symbol)clausesperson(z,m).person(y,w).person(c,w).person(l,m).goal:person(A,_),person(B,_),ABgoal:person(A,_),person(B,_),AB,!A=z,B=yA=z,B=yA=z,B=cA=z,B=lA=y,B=zA=y,B=cA=y,B=lA=c,B=zA=c,B=yA=c,B=lA=l,B=zA=l,B=yA=l,B=c第三节对回溯的控制2、“!”的概念•“!”表示截断，系统内部谓词，不带任何变元•作为目标，求解立即成功，即该谓词总是取真值•成功后，不能回溯，即穿过!的回溯是不可能的•goal:h1,h2,!,h3,h4第三节对回溯的控制predicatesperson(symbol,symbol)clausesperson(z,m).person(y,w).person(c,w).person(l,m).goal:person(A,_),person(B,_),ABgoal:person(A,_),person(B,_),AB,!goal:person(A,_),!,person(B,_),ABgoal:person(A,_),person(B,_),!,ABgoal:!,person(A,_),person(B,_),AB12个解1个解3个解无解12个解第三节对回溯的控制二、失败1、示例predicatesperson(symbol,symbol)outputclausesperson(z,m).person(y,w).person(c,w).person(l,m).outputifperson(X,_),write(“姓名:”,X),nlgoal:output姓名：zyesgoal:person(X,_),write(“姓名：”），nl姓名：z姓名：y姓名：c姓名：l第三节对回溯的控制predicatesperson(symbol,symbol)outputclausesperson(z,m).person(y,w).person(c,w).person(l,m).outputifperson(X,_),write(“姓名:”,X),nl,failgoal:output姓名：z姓名：y姓名：c姓名：lno第三节对回溯的控制2、”fail”的概念•是系统内部谓词，不带任何变元，表示失败•作为目标，求解立即失败，引起回溯•goal:h1,h2,fail,h33、!与fail相结合的例子not-equal(X,Y)ifequal(X,Y),!,fail.not-equal(X,Y).equal(X,X).goal:not-equal(6,7)yesgoal:not-equal(6,6)no第四节PROLOG的基本程序段一、常量段•用来说明符号常量•由“constant”标识•在常量说明中，系统不区分大小写•可有多个常量段•每个常量要先定义后使用•例如：constantpi=3.14159zero=0num=50第四节PROLOG的基本程序段二、域段——由domains标识1、标准域•char——标准ASCII码中任意一个字符，被单引号括起来•integer•real•string——由双引号括起来的字符序列•symbol以小写字母开始，由若干字母、数字、下划线组成的序列双引号括起来的字符序列•若谓词参数采用标准域，则域段可省略•若谓词参数采用非标准域，则需在域段中说明第四节PROLOG的基本程序段2、表域•表域名=域名*•例如：domainsmyint=integermylist=myint*predicatesmember(myint,mylist)clausesmember(X,[X︱_]).member(X,[_︱Y])ifmember(X,Y)domainsmylist=integer*predicatesmember(integer,mylist