知识工程TPROLOG.docx
《知识工程TPROLOG.docx》由会员分享，可在线阅读，更多相关《知识工程TPROLOG.docx（96页珍藏版）》请在冰点文库上搜索。
知识工程TPROLOG
PROLOG语言
PROLOG是英文“PROgramminginLOG”的缩写，意思为逻辑程序设计，它最早由R·Knowalski首先提出。
世界上第一个PROLOG系统于1972年由A·Colmerauer及其研究小组在法国马赛研制成功。
PROLOG以逻辑程序设计为基础，最初设计PROLOG的目的是作为处理逻辑推理问题的会话式语言，并以处理一阶谓词演算为背景。
后来，由于PROLOG具有简洁的文法，丰富的表达力和独特的非过程型等特点，从而日益受到了计算机界的重视，引起了越来越多的人的注意，现在PROLOG语言已被广泛应用于关系数据库、抽象问题求解、数理逻辑、公式处理、自然语言理解、专家系统以及人工智能的许多领域。
PROLOG是一种人工智能语言，它同其它大多数程序设计语言一样，也有许多不同的实现系统，它们具有各自的语义语法特色。
本章主要介绍一种称为“核心PROLOG”的标准文本，目前，多数PROLOG系统基本上遵从这个标准文本的规定。
一、PROLOG的基本内容
1．PROLOG的特点
作为一种程序设计语言，PROLOG具有两方面的特性：
一是它描述求解问题的方式；二是语言本身的特点。
如众所周知，用通常程序设计语言（如FORTRAN，PASCAL）来解问题时需指明算法，即对一给定的问题指明一系列计算机要执行的计算步骤，告诉计算机“如何做”。
与这些通常的程序设计语言不同，PROLOG语言求解问题时，要求程序员描述所解问题中的对象和反映它们之间关系的某些已知事实，描述和定义诸对象和它们之间关系的某些规则。
它强调描述对象（和事实）之间的逻辑关系，程序员一般不必告诉计算机运行执行的先后次序。
因此，从能够描述问题本身，而不必描述求解问题的详细计算步骤这一点讲，PROLOG是更高级的语言，它可看作为一种描述性语言。
目前，人们往往把语言分为函数型语言、逻辑型语言和其它语言，这是因为这三类语言在性质上和描述问题的方式上有着很大的差异。
PROLOG语言除了上述的特性外，还有下面一些特点：
①PROLOG的数据和程序结构统一，PROLOG提供一种一致的数据结构，称为项（term）。
所有数据和程序都由项构造而成的。
在智能程序中常需要将一段程序的输出数据作为新产生的程序来执行，因此人工智能语言就具有数据和程序结构一致的特性，LISP在这方面是当之无愧的，它的程序和数据都是S—表达式。
而PROLOG也不逊色，它的程序和数据都是以项为基本单位，并且都是树型结构。
②PROLOG能够自动实现模式匹配和回溯，这些是人工智能系统中最常使用的，最基本的操作。
由于PROLOG系统提供了自动完成这些操作的功能，使用户在PROLOG语言这一级上不必考虑这些问题。
③与LISP语言一样，递归是PROLOG语言的重要特点，它反映在程序和数据结构中，由于这一特性，一个大的数据结构常常能够由一个小的程序来处理。
PROLOG的所有这些特性，使得PROLOG语言特别适用于描述智能程序，因此人们习惯把PROLOG称为人工智能程序设计语言，并将它作为进行人工智能系统设计的工具。
2、PROLOG的简单实例
我们从一个简单例子开始介绍PROLOG程序，设有一有向图，如图6-8所示，现用PROLOG来描述图中的两点之间的关系。
图6-8一个简单的有向图例子
若用connected（X，Y）表示从X到Y有一条有向边，则图6-8可用下面的PROLOG事实来描述：
connected（e，b）.
connected（c，d）.
connected（d，e）.
现在定义两点有通路的概念，点X到Y有通路是指：
①X到Y有一条有向边。
②存在一点Z，X到Z有一条有向边，并且Z到Y有一通路。
上面这个通路的定义，可以用PROLOG的规则来描述：
path（X，Y）：
—connected（X，Y）.
path（X，Y）：
—connected（X，Z），path（Z，Y）.
这path（X,Y）表示X到Y有一通路，符号“：
—”表示“如果”，逗号“，”表示“并且”。
因此上面第一条规则的含义是：
如果X到Y有一条有向边，则X到Y有通路。
第二条规则的含义是：
如果X到Z有一条有向边，并且Z到Y有通路，则X到Y有通路。
输入了上述事实的规则之后，就可以向机器询问图中各点之间的关系。
？
—path（a,b）.a到b有通路吗？
yes
？
—path（b,a）.b到a有通路吗？
no
？
—path（d,Y）.d到哪一点有通路？
Y=e（Y代表变量）
？
—path（b,X），path（c,X）.
x=d
以上就是一个简单的PROLOG程序，以及一旦这个程序进入机器后，用户以会话方式运行这个程序的情况：
从这个实例中，我们可以看出，PROLOG语言提供了三种基本语句：
①事实：
它说明一个问题中的对象和它们之间的关系的一些已知事实。
②规则：
它用来定义对象和它们之间的关系，用来描述一个事实依赖于其它一组事实。
③用来询问有关对象和它们之间的关系。
3．事实
从上一节看到，为了表达从点a到b有一条有向边这一事实，写了connected（a,b）。
这个事实由两个对象（a和b）以及一个关系（connected）所组成。
在PROLOG中事实一般形式是：
①首先写关系，接着是括在一对圆括号内的若干对象，对象间用逗号隔开。
②对象和关系名必须以小写字母开头。
③在事实的末尾名必须写上实心点“·”。
在PROLOG中，关系connected被称为谓词，括号中的（a,b）被称为变元，谓词名是任意的，变元的个数也是任意的，但应注意在圆括号中的诸变元的书写次序。
实际上，这种次序是任意的，但在书写事实时必须确定某种次序，一旦确定后，在以后这一事实的使用时要保持这种次序的一致性，例如事实connected（a,b）是指从点a到b有一条有向边，下面是一些事实例子以及解释：
on（book,desk）.书在桌子上面
owns（john,book）.john有书
valuable（gold）.金是值钱的
father（john,mary）.joho是mary的父亲
play（jane,jin,badminton）.jane和jin打羽毛球
4．规则
假设我们要叙述这样的事实：
john喜欢所有的人，表示这一事实的一种方法是写出下列所有各个事实：
likes（john,david）.
likes（john,tom）.
likes（john,jane）.
…
显然这种表示法是不方便的。
因此表示john喜欢所有人的另一种方法是把它说成：
“john喜欢任一对象，只要这一对象是人。
”于是，便可以用下面的规则来表示：
likes（john,X）：
—person（X）.
它的含义是：
如果X是人，则john就喜欢这个X所指的人。
注意，这里X是大写字母代表变量。
在PROLOG中，当你要描述一个事实依赖于其它一组事实时，则用规则来表示。
我们用“如果”、“则”来表示一个规则，例如：
“如果某人有钱，则他就买汽车。
”
用规则描述为：
buy（X,car）:
-have（X,money）.
规则可用来表示定义，例如：
如果X是一动物，并且X有羽毛，则X是鸟。
bird（X）:
-animal（X）,feather（X）.
从上面例子可以看出：
规则是诸对象和它们的关系的一般陈述。
一个规则由头和体组成。
头是：
—符号的左部，体是“：
—”符号的右部。
“：
—”的意思是如果，规则以“.”结尾。
规则的头描述了这条规则企图定义的事实。
规则的体描述了一些目标的连结。
为使头成为真的，这些目标必须逐个被满足。
体中目标一个接着一个写，中间用逗号“，”分开，逗号的意思是并且，它们把体中目标连结起来。
现把规则的各部分形象地描述如下：
bird（X）:
-animal（X）,feathers（X）.
头如果并且体
这里的“：
—”也读作“只要”。
显然规则的这种形式类似于Horn子句。
通常一个谓词能用事实和规则的混合来定义。
例：
likes（john,food）.
likes（john,X）:
-person（X）.
我们再举出规则的几个例子：
John喜欢任何喜欢讲话的人。
换句话说，John喜欢某个人，如果这个喜欢讲话。
用规则表示：
like（john,X）:
-person（X）,likes（X,talk）.
如果我们希望表示，John喜欢任何喜欢讲话和游泳的人，则只要简单地加一目标到上面体中，并用逗号隔开。
likes（john,X）:
-person（X）,likes（X,talk）,likes（X,swim）.
若要表示父母和（外）祖父母等关系，可用下列规则：
parent（X,Y）：
—mother（X,Y）.
parent（X,Y）：
—father（X,Y）.
grandparent（X,Y）：
—parent（X,Z）,parent（Z,Y）.
5．询问
我们可以对一些事实询问，在PROLOG中一个问题很象一个事实，只要在它前面加一特殊符号“？
—”。
例如：
？
—owns（mary,book）
其意思是Mary有这本书吗？
或Mary有这本书是真的吗？
但不能问她是否有所有的书。
当询问时，PROLOG要搜索事先输入的事实组成的数据库，看是否有事实与问题相匹配。
当事实与询问的关系相同且相应的自变时也相同时，我们说二者相匹配。
如果PROLOG找到一个事实与问题相匹配，则回答“是”；否则，数据库里无此事实则回答“否”，上面询问中的owns（mary,book）,又称为目标，或者说询问自由目标组成。
假设已有如下事实。
on（book,desk）.
owns（john,book）.
female（jane）.
play（jane,jin,badminton）.
valuable（gold）
则可以问：
？
—female（jane）.
yes
？
—owns（john,moon）.
no
这里下划线的部分表示PROLOG回答的信息（以下同）。
？
—male（tom）.
no
对前面两个问题的回答是清楚的。
对第三个问题，PROLOG也回答no，这是因为数据库中没有这样的事实，这个no意味着“就我所知，这是不对的。
”因此系统回答no有两种意思：
不或者不知道。
显然，仅仅询问这样的问题。
获得yes和no的回答是不够的。
询问象“John有什么东西？
”，“谁与谁打羽毛球？
”也是用户常提出的问题，但这些问题必须借助变量来提出。
如下所示：
？
—owns（john,X）
X=book
？
—play（X,Y,badminton）
X=jane,Y=jin
?
—owns（X,book）.
X=john
在介绍规则时，我们曾引入“连结”的概念，即用逗号“，”把一规则体中的多个目标连结在一起，这里“，”表示“并且”。
同样，在询问中也可以将几个目标用“，”连续起来放在“？
—”的后面，以便我们问更复杂关系的问题，如：
？
—play（X,jin,badminton）,female（X）.
X=jane.
至此，我们已经介绍了PROLOG基本的核心内容，主要是：
①说明有关对象的事实。
②用规则的形式表示关系。
③问有关事实和规则的问题。
④用大写字母开关的字符串表示变量。
⑤用连结符号“，”表示并且。
二、数据结构和递归
1．项
PROLOG提供一个一致的数据结构称为项，所有的数据和PROLOG程序都是由项构造而成的。
PROLOG中项的定义用BNF形式可写成；
<项>∷=<常量>|<变量>|<结构>|<（项）>|
项可以是常量、变量、结构或者括在括号里的项。
在前面，所有这些项我们都已经碰到，只是不熟悉它们的名称。
（1）常量
原子或者是整数，即<常量>∷=<原子>|<整数>。
原子用来标识对象的名字、谓词（对象间关系）等。
原子是以小写字母开头的字母数字串，中间可插有下划线符号“—”或仅由符号组成。
整数用来表示数，使得PROLOG能执行算术运算。
整数由数字组成，不包含小数点。
（2）变量
用来表示暂时不能命名或不需要命名的对象，变量是以大写字母或下划线符号“—”开头的字母数字串，中间可插有“—”。
无名变量表示为“—”，因它的名字从来不会被使用。
、
在同一个子句中的几个无名变量，不需要给出一致的解释。
这是无名变量的特有性质，它与在同一个子句中，一个有名变量的多次出现要有一致的解释不同。
（3）结构
或称复合项。
它是由一组其它对象（也可为结构）组成的单个对象，这些其它对象称为它的成分，把几个成分组合成一个结构作为单个对象是很有用处的，结构的定义的；
<结构>∷=<函数符>（<项>{，<项>}）
<函数符>∷=<原子>
下面是一些结构的例子：
owns（john,book）
owns（john,book（prolog,author（clocksin,Melish））
a（b,c,d）
3+5*2
gcd（X,f（X））
其中第四个例子是结构+（3，*（5，2））的另一种表示。
为对应这种形式，有人在结构定义中加入<项><原子><项>{<原子><项>}，这样第四个例子中3是项，+是原子，5是项，*是原子，2是项，其它四个例子均符合定义中的<函数符>（<项>{，<项>}）。
若把一个复杂的结构表示成一棵树将更容易理解。
例如，把上面例子中每一个函数符（如owns,author等）看作为根（或子根），它的变元为分枝，而每一个分枝又可指向另一个结构，这样就有图6-9的树形结构。
2．表和它的递归性
表是非数值程序设计中一种最常用的数据结构。
LISP与PROLOG都以此作为它们的数据结构。
所不同的是，在PROLOG中表仅为一特殊类的结构；而在LISP中表是唯一的数据结构。
表是元素的有序序列，有序指序列中元素的次序是重要的。
PROLOG中，一个表的元素可以是原子，结构或任何其它项包括其它表，因此表是递归定义的。
事实上，表能够表示人们在符号处理中希望使用的任一类结构。
PROLOG中的表或者是一个没有元素的空表，或者是一个结构，它包括头和尾两个成分，空表写成[]，非空表写·（头，尾），这里“·”是一个函数符。
表的头和尾是它的两个成分（变元）。
当尾没有元素时，尾写为空表。
例如由元素a组成的表为：
·（a,[]）。
同样，由原子a,b,c组成的表：
·（a,·（b,·（c,[]）））
由此可见，表能表示成二元树。
用点表示法写复杂的表极不方便，而且难看，因此PROLOG也用称为表表示法的方法未写表。
表表示法是用逗号把表的诸元素分开，并且把所有元素括在方括号内，例如上面两个表用表表示法可写成为[a]和[a,b,c]。
根据表表示法和点表示的意义，[a,b,c]可写成·（a,[b,c]），进一步写成·（a,·（b,[c]））以及·（a,·（b,·（c,[]）））。
在表中包含其它表或变量是十分有用的。
例如下面的表在PROLOG中最合法的：
[]空表
[a,b,c,[d,e,f],g]
[a,V1,b,[X,Y]]
表表示法是PROLOG实际使用的表示形式、表的大小是最外层元素的个数。
因此上面三个表的大小分别为0，5，4。
对表的操作是通过把表分成头和尾来进行的，在表表示法中，头是表中最外层的第一个元素，表的尾是一个表，这个表由原来表的除了第一个元素外的所有元素组成。
为了对表进行取表头和取表尾的操作，在PROLOG中有一种专门表示法来表示一个分明头X和尾Y的表，它写成[X|Y]，这里分隔X和Y的符号是垂杠“|”。
当这个模式匹配任一表时，PROLOG将把X实例化为匹配的表的头，Y实例化为该表的尾，例如，表[a,b,c.d]的[X|Y]形式为[a|[b,c,d]]，所以X=a,Y=[b,c,d]因为[a,b,c,d]的表头为a，表尾为[b,c,d]，同样，表[a]的[X|Y]形式为[a|[]]，所以X=a，Y=[]，再看下面一些例子。
若有p（[1,2,3]）.
p（[the,cat,sat,[on,the,mat]]）.
于是？
—p（[X|Y]）
X=1,Y=[2,3]；/*打；号*/
––––––––––––––
X=the,Y=[cat,sat,[on,the,mat]]
–––––––––––––––––––––––––
？
—p（[_,_,_,[_|X]].
X=[the,mat]
––––––––––––
？
—p（[X,Y|Z]）.
X=1,Y=2,Z=[3];
––––––––––––––
X=the,Y=cat,Z=[sat,[on,the,mat]]
––––––––––––––––––––
3.美术运算
LISP和PROLOG均不得以数值计算为其目标的，它们主要用于非数值程序设计。
因此，在算术运算方面它们不能与传统的FORTRAN，PASCAL相比拟，它们只提供了一些基本的运算，PROLOG提供的五种最基本的算术运算是：
加、减、乘、除和取模，写成一般的中级形式为XopY，其中OP是算术运算符，可为+，－，*，/，mod，/是指整数除，即X、Y为整数，X/Y是X除以Y的商（整数）。
XmodY是X除以Y的余数。
算术运算符的优先级与通常数学上的规定相同，即*，/，mod高于+，－。
所以：
X+Y*ZX＋（Y*Z）两者一样
A-B/CA-（B/C）两者一样
X＋Y/B-C（X＋（Y/B））-C两者一样
在PROLOG中，上面的算术表达式也可写为如下结构形式：
＋（X，*（Y，Z））
-（A，/（B，C））
-（＋（X，/（Y，B）），C）
上述中算术运算符是作为函数符出现的。
一般形式为：
算术运算符（变元，变元）。
＋（X，*（Y，Z））中乘法比加法先做，因为*结构是+结构中的一个变元。
对于＋结构，为了＋结构，为了知道它的两个变元，必须先做乘法。
到底使用哪种形式表示算术表达式，由用户决定。
对于相同优先级的运算符，PROLOG采用通常的左结合规则，即A+B-C意味着（A+B）-C，8/2/2意味着（8/2）/2，算术表达式中可按需要使用圆括号。
在PROLOG中，需要使用一特殊运算符“is”来告诉PROLFOG求值算术表达式。
运算符is是中级运算符，通常它取一个变量在左边，一个算术表达式在右边。
is意味着对后面的算术表达式求值，因此算术表达式中的所有变量的值在求值时必须都是已知的。
使用is对算术表达式求值的一般形式为：
变量is算术表达式。
例如，XisA+B表示对A+B求值，若X原先是未实例化的，则现在被实例化为A+B的值。
之所以用is，因为A+B也是一个普通的PROLOG结构，而PROLOG对结构一般是不求值的。
例如对结构likes（john,wine）不可能求值，因为like不是一个算术运算符，因此为了对算术表达式求值，必须用求值运算is来指明。
记住，A+B这样的成分只是一个通常的PROLOG结构，好象likes（john,wine）结构一样，后面将说明这一点。
下面给出两个简单的例子说明算术表达式的使用。
例1计算国家的人口密度
1997年一些国家的人口数和面积用PROLOG表示有：
pop（usa,212）.
pop（china,825）.
pop（india,586）.
area（usa,3609）.
area（china,3707）.
area（india,1139）.
因一些PROLOG系统中只能使用不太大的整数，所以用百万表示人口数的单位，即pop（C，P）表示国家C有P百万人口，用千平方英里为面积单位，即area（C，A）表示国家C有A千平方英里面积，于是，表示人口密度的规则是（人/平方英里）：
density（X,Y）:
-pop（X，P），area（X,A），YisP*1000/A.
规则的意思为：
“如果国家X的人口数为P百万人，且国家X的面积为A千平方英里，并且Y是P乘以1000除以A，则国家X的人口密度是Y人/平方英里。
”
上例中当PROLOG做到is时，若Y是未知的，则在求值P*1000/A后让Y代表这个值（即Y被实例化这个值）。
这意味在is右边的变量必须是已知的。
例如：
当打入?
-density（china,X）.
X=222
例2add（X,Y,Z）:
-ZisX+Y
这是一个加法规则，意味着Z是X加Y。
因此当你问：
？
—add（2,3,4）.
no
？
—add（2,3,5）
yes
第一个询问因为4不是2+3，所以回答no，第二个问题5=2+3，所以回答yes，若问：
？
—add（2,3,X）
X=5
从这个实例可以看出，is的作用解释为当它的左边是一个未实例化的变量时，则is的作用是把该变量实例化为is右边代表的值。
若它的左边是一个已知数（包括实例化的变量），则is的作用好象等号“=”，作相等检查。
统一这两种情况，is的含义是“是”。
注意，若询问？
—add（X,3.5），不可期望得到X=2，因为is右边的X值未知，PROLOG将用完自由空间而告出错（Nospaceleft）。
习惯于传统程序设计语言的程序员必须清楚地知道，is决不是赋值。
假设X已实例化为8，如果写XisX－1,由X决不会取7，XisX－1作为目标永远失败，因为8不是7，所以8is7失败，同样，假设Y未实例化，若连续写Yis5,Yis4,则Y为实例化为5，不可能是4，第二个目标Yis4失败。
4．比较运算
在程序中经常会出现数的比较，PROLOG提供了六种常用的比较运算，并以中缀形式表示：
X=Y（X和Y代表相同数）
X\=Y（X和Y代表不同数）
X＜Y（X小于Y）
X＞Y（X大于Y）
X=＜Y（X小于等于Y）
X＞=Y（X大于等于Y）
这里X，Y可以是整数，或者是被实例化为整数的变量。
XopY可以作为目标出现在询问和（或）规则中，此时，如果A大于B，则目标A＞B成功。
例如若询问？
—2*3＞2*4，则回答no；若问？
—2*3＜2*4,则回答yes。
XopY也可作为变元出现在结构中。
例3，判断给定的3条边是否构成等边三角形。
equilateral（X,Y,Z）:
-X＞0,X=Y,Y=Z.
于是？
—equilateral（8,8,8）.
yes
––
？
—equilateral（8,7,9）
no
––
如果问？
—equilateral（8,8,6+2）.将回答什么？
回答no。
六个比较运算符在PROLOG中是作为内部谓词的，其中“=”和“\=”不仅能用于整数间比较，也能用于其它对象的比较。
对目标X=Y（其中X和Y是任意两个项），决定X和Y是否相等的规则是：
①原子和数总是等于自身，例
atom=atom，9=9成功
atom=atoml，1984=1985失败。
②若X是未实例化的变量，Y是任一对象，则X=Y，总是相等，其副作用是X被实例化为Y代表的对象。
例：
？
—rides（john,bike）=X成功，且X被实例化为项rides（john,bike）。
③两个结构相等，并且仅当它们有相同的函数符和变元个数，且对应的变元都相等，例如，下面的目标成功并且X被实例化为bike。
rides（john,bike
升级会员 