Prolog语言(耐心看完,你就入门了)

2020/1/24人工智能ArtificialIntelligence(AI)2020/1/24Prolog语言简介Prolog语言是一种以一阶谓词为基础的逻辑性语言（ProgramminginLogic）2020/1/24Prolog语言的特点Prolog语言的基本内容简单的例子2020/1/24Prolog语言（或者系统）是以一阶谓词逻辑的Horn子句集为语法，以Robinson的消解原理为工具，加上深度优先的控制策略而形成的人工智能通用程序设计语言Prolog语言的特点2020/1/24Horn子句集消解原理深度优先Prolog系统2020/1/24Prolog具有下列特点：①是一种描述性语言。只需要告诉“系统做什么”，不要告诉系统“如何做”②数据与程序的统一表达。提供一种统一的符号结构“项”，数据与程序都是由项组成2020/1/24③自动实现模式匹配与回溯。这是人工智能中最常用的两项操作，Prolog自动实现这些操作④程序易于编写与阅读。它是面向人的自然语言⑤语句句型少，语法简明。只有三种句型2020/1/24参考资料：1雷英杰，张雷，邢清华，孙金萍。VisualProlog语言教程。西安：陕西科学技术出版社，2002年2月（380页，35元）2雷英杰，邢清华，孙金萍，张雷。VisualProlog编程、环境及接口。北京：国防工业出版社，2004年1月（412页，36元）2020/1/24Prolog语言的基本内容1项2Prolog中的语句3表结构4Prolog程序的结构5常用内部谓词6Prolog程序设计步骤2020/1/24符号说明：“::=”表示“定义为”“|”表示“或”，可选“{}”表示“重复或者出现多个”1项2020/1/24项的定义：项::=常量|变量|复合项2020/1/24常量::=原子|数原子::=标识符原子|字符串原子|特殊原子项::=常量|变量|复合项2020/1/24命名：用小写字母或者小写字母开头的小写字母数字串用途：用于标识对象的名字、谓词（对象间的关系）或函数名标识符原子例：john,marry,classmate,teacher2020/1/24字符串原子是用引号括起来的符号串特殊原子指一些特殊符号，如+、-、*、/等2020/1/24变量：用于表示暂时不能命名或者不需要命名的对象，用大写字母开头项::=常量|变量|复合项2020/1/24特殊变量：空变量，记作：“_”含义：我们对问题的某一个变量的值不关心2020/1/24复合项::=原子（项{,项}）|项原子项{原子项}项::=常量|变量|复合项2020/1/24复合项：由一组其它对象组成的单个对象例：函数项：like(john,apple)表：[sa,sb],[1,2,3]表达式：(12+59)*49-962020/1/24项常量变量复合项原子数标识符原子字符串原子特殊原子原子（项{,项}）项原子项{原子项}2020/1/242Prolog中的语句①事实：P.含义：无条件成立，恒为真例：like(monkey,banana)Prolog中的语句分成三种形式：2020/1/24②规则：P:-P1,P2,…,Pn.“:-”表示“蕴涵”“，”表示“合取”含义：若P1,…,Pn均为真时，P为真2020/1/24③问题（目标）GoalQ1,Q2,…,Qm.含义：待回答的问题,即Q1,…,Qm同时为真吗？2020/1/24从消解角度来看：①（事实）中，P是Horn子句2020/1/24②（规则）可以表示为P1∧P2∧…∧PnP可以转化为～P1∨～P2∨…∨～Pn∨P也是Horn子句，并受全称量词约束2020/1/24③（问题）是Q1∧…∧Qm受存在量词约束，取非后～Q1∨…∨～Qm受全称量词约束，是Horn子句2020/1/24Prolog三种形式的语言都是Horn子句问题求解就是Horn子句集消解2020/1/243表结构表：若干个元素的有序序列表中的元素：常量、变量、项、表表用“[]”来表示，元素之间用逗号或者空格分开2020/1/24例：[1,2,3][a,b,c,d]2020/1/24用符号“|”来划分表头（第一个元素）和表尾（其余元素）特例：当只用一个元素时，表尾为空空表（无元素），既无表头又无表尾2020/1/24例：P（[the,cat,sat,down]）.?-P([X|Y]).答案：X=the,Y=[cat,sat,down]?-P([X,Y|Z]).答案：X=the,Y=cat，Z＝[sat,down]2020/1/244Prolog程序的结构Prolog的程序分为两部分：前提部分：所有事实和规则问题部分：目标子句序列2020/1/24注意：这两部分不能颠倒。必须前提部分写在前面，问题部分写在后面2020/1/24likes(m,f).likes(m,w).(事实)likes(j,w).likes(j,s).goallikes(m,X),likes(j,X).(问题)问题：是否m和j都喜欢什么东西？(X=?)fwsmj2020/1/24Prolog的求解过程现在有两个问题：likes(m,X)和likes(j,X)）第一步：第一个问题likes(m,X)去与事实匹配（置换与合一），按顺序得到{f/X}likes(m,f).likes(m,w).likes(j,w).likes(j,s).2020/1/24第二步：f代替第二个问题likes(j,X)中的X，则得likes(j,f)。再与事实匹配，不能匹配，失败，则回溯，忘掉刚才的匹配likes(m,f).likes(m,w).likes(j,w).likes(j,s).likes(m,X)likes(j,X)2020/1/24第三步：回到第一个问题likes(m,X)，重新匹配，得到{w/X}第四步：第二个问题变成likes(j,w)。再与事实匹配，成功第五步：答案就是X=wlikes(m,f).likes(m,w).likes(j,w).likes(j,s).likes(m,X)likes(j,X)2020/1/24说明：实际运行中，要逐个试探（搜索），失败则要回溯，成功也要回溯（求出所有解）2020/1/24例：father(a,b).a是b的父亲father(c,d).brother(a,c).a与c是兄弟关系uncle(X,Y):-brother(X,Z),father(Z,Y).?-uncle(a,U).问题：a是谁的叔叔？（U=?）2020/1/24第一步：问题uncle(a，U)与事实逐个匹配，不成功Prolog的求解过程：father(a,b).father(c,d).brother(a,c).2020/1/24第二步：与规则头（左部）匹配，即寻找合一者，有{a/X,U/Y}转化为两个子问题：brother(a,Z)和father（Z,U）uncle(X,Y):-brother(X,Z),father(Z,Y).uncle(a，U)2020/1/24第一个子问题brother(a,Z)与事实匹配，得到{c/Z}代人第二个子问题，有father(c,U)。与事实匹配，得到{d/U}，即U=d，解是：a是d的叔叔father(a,b).father(c,d).brother(a,c).brother(a,Z)father（Z,U）2020/1/24Prolog的实现方法主要是：匹配与回溯匹配：合一过程、消解过程回溯：搜索，而且是深度优先搜索2020/1/24关于匹配的几点说明：第一、一个变量被置换后，代入了另一个项，则称该变量为实例化的变量2020/1/24①若与另一个未实例化的变量匹配，则视为同一变量，两者共享②若与另一个实例化的变量匹配，也变成了实例化的变量，且两者同值③若与常量匹配，也变成了实例化变量，并取常量的值第二、一个未实例化的变量可以与任何项匹配：2020/1/24第三、常量只能与相同的常量匹配第四、实例化的变量与另一个实例化的值相同的变量匹配，也可以与另一个未实例化的变量匹配，使另一个变量实例化，且约束值相同2020/1/245常用的内部谓词内部谓词：Prolog系统本身定义的一些基本谓词注意：可以直接使用，用户不能修改2020/1/24①算术运算算术表达式由操作数（数、变量）、操作符和括号组成算术运算符号：“+、-、*、/”（加减乘除）2020/1/24优先级：与通常的数学运算一致形式：中缀：X+Y*Z前缀：+(X,*(Y,Z))2020/1/24②比较谓词eq(X,Y)X=Yne(X,Y)XYgt(X,Y)XYls(X,Y)XY2020/1/24对于“＝、”，X,Y可以取常量变量谓词表2020/1/24第一、当一个变量已经实例化，则可以与任意未实例化的变量相等，且将其实例化（赋值功能）第二、两者均未实例化，eq(X,Y)恒为真，并视为同一变量对于“＝”（赋值与比较）的几点说明：2020/1/24第三、均以实例化，由当前值来决定第四、如果为表，要求对应的元素相等，才为真第五、如果是谓词，谓词同名，变元个数相等，对应的变元相等2020/1/24③输入输出谓词第一、write(X)：向输出设备输出实例化结果第二、read(X)：当X未实例化时，输入一个项当X在输入前已经实例化，则读入项将与X匹配，根据匹配的成功与否，决定其真假值2020/1/24④谓词cut与fail（特殊谓词）：cut(!)：禁止回溯fail：强迫回溯2020/1/24第一、只允许作为一个子目标出现在程序中第二、第一次遇到它时，总是立刻被满足，但是不能被重新满足第三、用户可以使用它来控制回溯方式，切断一些不必要的回溯，提高程序运行效率关于cut的几点说明：2020/1/24关于fail的说明：作为一个子目标，使Prolog程序运行到fail，必定引起回溯2020/1/24例：求1到n之间的和定义一个二元谓词sum(N,X)，其中X表示和答案是：X=21去掉“！”，会发生什么？sum(1,1):-!.sum(N,R):-N1=N-1,sum(N1,R1),R=R1+N.?-sum(6,X).2020/1/246Prolog程序设计步骤第一、说明事实：说明与待求解的问题有关的事实。例如，人物事及相互关系，对应于叙述性知识对应于Prolog程序的组成部分，设计步骤分为：2020/1/24第二、定义规则：定义个体及其相互关系的推理规则，反映与待求解问题有关的过程性知识第三：确定目标（问题）：提出待求解的问题或者确定逻辑推理的目标2020/1/24程序的一般结构（组成部分）VisualProlog程序包括三到四个基本程序段：第一、域段：说明谓词变量的域（类型）第二、谓词段：说明非标准谓词（用户自己的谓词）2020/1/24第三、子句段：核心部分，可以写出事实与规则第四、目标段：设置内部目标2020/1/24域段（domains)Prolog语言中的域用于区分不同变量类型的数据相当于其它高级语言中的数据类型2020/1/24基本标准域有：char：用单引号括起来的单个字符，例如，’a’integer：整数，范围为32767到-32768real：实数，例如，86.72，5.1e+212020/1/24string：用双引号括起来的字符序列例：“IamfromNanjing”2020/1/24symbol：有两种形式：以小写字母开头的字母、数字和下划线组成的序列用双引号括起来的字符串序列2020/1/24Prolog中表示成下列形式：integerlist=integer*“integer”说明表中元素的类型“*”告诉编译系统，这是一张表表：2020/1/24例domainstitle,author=symbolpages=integer注：每一个说明的最后无句号“.”2020/1/24谓词段（pr