计算引论 推理与计算优秀课件.ppt

《计算引论 推理与计算优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算引论 推理与计算优秀课件.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算引论 推理与计算第1页，本讲稿共64页主要内容主要内容n逻辑与推理逻辑与推理nHorn逻辑程序逻辑程序n命题命题Horn逻辑中的自动推理逻辑中的自动推理n谓词谓词Horn逻辑中的自动推理逻辑中的自动推理n Prolog逻辑逻辑 程序设计程序设计第2页，本讲稿共64页4.1 逻辑基础知识逻辑基础知识 n符号表示：符号表示：n常量常量：小写字母：小写字母 a,b,c,.。n函数函数：小写字母：小写字母 f,g,h,.。n变量变量：小写字母：小写字母 x,y,z,.。n逻辑算子逻辑算子(或连结词或连结词)：,。n量词量词：,.n谓词谓词：大写字母：大写字母 P,Q,R,.。第3页，本讲稿共64页

2、4.1 逻辑基础知识逻辑基础知识 n命题命题：在一阶逻辑中，命题陈述某个对象的性质，或：在一阶逻辑中，命题陈述某个对象的性质，或是某些对象的关系，是能够分辨真假的语句。是某些对象的关系，是能够分辨真假的语句。n原子命题原子命题：一个语句如果不能再进一步分解成更简：一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子单的语句，并且又是一个命题，则称此命题为原子命题命题第4页，本讲稿共64页n命题公式命题公式：n原子命题是命题公式。原子命题是命题公式。n若若A是命题公式，则是命题公式，则 A也是命题公式。也是命题公式。n若若A和和B都是命题公式，则都是命题公式，则AB、A

3、B、A B、AB是命题公式。是命题公式。第5页，本讲稿共64页n命题公式的缺点：命题公式的缺点：n无法把所描述的客观事物的结构和逻辑特征无法把所描述的客观事物的结构和逻辑特征反映出来反映出来n不能把不同事物的共同特征反映出来不能把不同事物的共同特征反映出来n例如：例如：命题命题P:“P:“张三是李四的老师张三是李四的老师”第6页，本讲稿共64页n谓词逻辑谓词逻辑：在谓词逻辑中，将原子命题分解为谓词在谓词逻辑中，将原子命题分解为谓词与个体两部分。与个体两部分。n个体是指可以独立存在的物体，可以是抽象个体是指可以独立存在的物体，可以是抽象的或具体的。的或具体的。n谓词则是用于刻画个体的性质、状态或

4、个体谓词则是用于刻画个体的性质、状态或个体间的关系的。间的关系的。第7页，本讲稿共64页n 谓词的一般形式：谓词的一般形式：nP(x1,x2,xn)其中其中P是谓词，是谓词，x1,x2,xn是个体。是个体。n例：例：“鸟会飞鸟会飞”可表示为可表示为canfly(bird).其其中中canfly是谓词，是谓词，bird是个体。是个体。第8页，本讲稿共64页n谓词分类谓词分类：n一元谓词：刻画个体的性质一元谓词：刻画个体的性质n多元谓词：刻画个体之间的关系多元谓词：刻画个体之间的关系n一阶谓词：一阶谓词：个体是常量、变元个体是常量、变元n高阶谓词：个体是谓词高阶谓词：个体是谓词第9页，本讲稿共64

5、页n项项定义如下：定义如下：n单个的常量和变量都是项。单个的常量和变量都是项。n如果如果f是函数符是函数符,t1,tn是项，那么是项，那么 f(t1,tn)也是项。也是项。n例如，例如，gcd是表示最大公约数的函数符，是表示最大公约数的函数符，a+b，cd-2是两个项，则是两个项，则gcd(a+b,cd-2)也是项。也是项。第10页，本讲稿共64页n原子原子：若若P是一个是一个n元谓词符号，元谓词符号，t1,tn是项是项,那那么么P(t1,tn)是是原子原子。n例如，例如，father是表示父子关系的二元谓词，则是表示父子关系的二元谓词，则father(John,Peter)是原子，表示是原子

6、，表示John是是Peter的父亲。这里的父亲。这里 father(John,Peter)做为基本二做为基本二元关系。元关系。第11页，本讲稿共64页n谓词公式谓词公式：n 原子是公式原子是公式n 若若P,Q是公式，则是公式，则 PQ,PQ,PQ,PQ,P 是公式。是公式。n 若若P是公式，是公式，x是是P中的变量，则中的变量，则 (x)P，(x)P 是公式。是公式。第12页，本讲稿共64页n文字文字：若若P是是原原子子，则则P,P称称为为文文字字。P称称为为正正文文字字，P称为负文字。称为负文字。n子句子句：公公式式P称称为为子子句句，若若P为为L1 Ln，其其中中L1,Ln是是文文字。字。

7、n基项、基原子、基子句：基项、基原子、基子句：没没有有变变量量符符号号出出现现的的项项、原原子子、子子句句，分分别别称称为为基基项项、基原子、基子句。基原子、基子句。第13页，本讲稿共64页n例例:gcd(45,b)是基项是基项 father(John,Peter)是基原子是基原子 father(John,Peter)uncle(John,Peter)是基子句是基子句第14页，本讲稿共64页n谓词公式的解释谓词公式的解释 设设D D为为谓谓词词公公式式P P的的个个体体域域，若若对对P P中中的的个个体体常常量量、函函数数和和谓谓词词按照如下规定赋值：按照如下规定赋值：（1 1）为每个个体常量

8、指派）为每个个体常量指派D D中的一个元素；中的一个元素；（2 2）为每个）为每个n n元函数指派一个从元函数指派一个从D Dn n到到D D的映射，其中的映射，其中 D Dn n=(x=(x1 1,x,x2 2,x,xn n)|x)|x1 1,x,x2 2,x,xn n DD（3 3）为每个）为每个n n元谓词指派一个从元谓词指派一个从D Dn n到到F,TF,T的映射；的映射；则称这些指派为公式则称这些指派为公式P P在在D D上的一个解释。上的一个解释。第15页，本讲稿共64页n永真：永真：n如果谓词公式如果谓词公式P，对个体域，对个体域D上的任何一个上的任何一个解释都取得真值解释都取得

9、真值T，则称，则称P在在D上是永真的。上是永真的。n如果如果P在每个非空个体域上均永真，则称在每个非空个体域上均永真，则称P永永真。真。第16页，本讲稿共64页n永假（不可满足性）永假（不可满足性）n如果谓词公式如果谓词公式P对于个体域对于个体域D上的所有解释上的所有解释都取得假值都取得假值F，则称，则称P在在D上是永假的；上是永假的；n如果如果P在每个非空个体域上均永假，则称在每个非空个体域上均永假，则称P永永假。假。第17页，本讲稿共64页n可满足的：可满足的：n对于谓词公式对于谓词公式P，如果至少存在一个解释使，如果至少存在一个解释使得公式得公式P在此解释下的真值为在此解释下的真值为T，

10、则称公式，则称公式P是可满足的。是可满足的。n不可满足的：不可满足的：n对谓词公式对谓词公式P，如果不存在任何解释，使得，如果不存在任何解释，使得P的取值为的取值为T，则称公式，则称公式P是不可满足的。是不可满足的。第18页，本讲稿共64页4.2 推理相关知识推理相关知识n推理：推理：指从已知事实出发，运用已掌握的知识，推指从已知事实出发，运用已掌握的知识，推导出其中蕴含的事实性结论或归纳出某些新导出其中蕴含的事实性结论或归纳出某些新的结论的过程。的结论的过程。n推理分类：推理分类：n自然演绎：已知事实自然演绎：已知事实 推理规则推理规则 结论结论n归结：否定结论归结：否定结论 前提条件前提条

11、件 矛盾矛盾第19页，本讲稿共64页nSkolem化化：公式形式是很多样的。这就会给机器的形式化处理公式形式是很多样的。这就会给机器的形式化处理带来很大的麻烦。为了便于机器处理，把公式化成带来很大的麻烦。为了便于机器处理，把公式化成统一的标准形式，即统一的标准形式，即SKOLEM标准型。标准型。第20页，本讲稿共64页nSkolem标准型：标准型：设设P是公式，是公式，P等价于等价于 x1 xnG(x1.xn)，并且，并且GG1 Gm，其中，其中G1,Gm都是子句，则称都是子句，则称G的子句的子句集集S=G1,Gm 为公式为公式P的的Skolem标准型。标准型。第21页，本讲稿共64页n对公式

12、对公式P的的SKOLEM化的步骤如下：化的步骤如下：（1）将）将P化为前束范式化为前束范式（Q1x1）（Qnxn）H(x1.xn)其其中中 Q1Qn是是存存在在量量词词或或者者全全称称量量词词，H为为合合取取范范式的形式式的形式,不含不含,；第22页，本讲稿共64页（2）用如下方法消去存在量词：）用如下方法消去存在量词：i)若若Qi是是一一个个存存在在量量词词，并并且且它它的的左左边边没没有有全全称称量量词词，则则用用一一个个H中中没没有有的的常常量量符符号代替号代替H中所有的中所有的xi，之后消去（之后消去（Qixi）第23页，本讲稿共64页ii)若若Qi是是一一个个存存在在量量词词，并并且

13、且Qj1,Qjk是是Qi左左边边的的全全称称量量词词，则则取取一一个个H中中没没有有的的函函数数k元元符符号号f,用用f(xj1,xjk)代代替替xi,之之后后消去（消去（Qixi）。第24页，本讲稿共64页n公式公式P经过如上处理，可以化为经过如上处理，可以化为 x1 xn(G1 Gm)的形式，其中的形式，其中G1,Gm都是子句。省略全都是子句。省略全称量词，再用称量词，再用“，”取代合取符号，便得取代合取符号，便得到公式到公式P的的Skolem标准型标准型G1,Gm。第25页，本讲稿共64页n任意公式都有与之相对的子句集。任意公式都有与之相对的子句集。n一个公式与它的一个公式与它的Skol

14、em标准型未必等值，标准型未必等值，但在不可满足的意义上是一致的。但在不可满足的意义上是一致的。第26页，本讲稿共64页n置换置换：是形如：是形如t1/x1,tn/xn的一个有限集合。其中的一个有限集合。其中xi（i=1,n）是两两不同的变量符号是两两不同的变量符号,ti是不同于是不同于xi的的项。项。n置换作用于表达式置换作用于表达式：给定置换给定置换=t1/x1,tn/xn和表达式和表达式E，E 表示将表示将E中出现的每一个中出现的每一个xi（i=1,n）都替换成）都替换成ti得到的新表得到的新表达式。达式。第27页，本讲稿共64页n给定两个置换给定两个置换 =t1/x1,tn/xn =u

15、1/y1,um/ym 将集合将集合 t1/x1,tn /xn,u1/y1,um/ym 删去以下元素：删去以下元素：n ui/yi，当，当yi x1,xn n ti /xi，当，当ti =xi 得到的新置换表示为得到的新置换表示为 ，称为，称为 和和 的复合的复合。第28页，本讲稿共64页n 置换满足结合律置换满足结合律n ()=()n 置换不满足交换律置换不满足交换律n n =第29页，本讲稿共64页n合一合一置置换换：给定表达式给定表达式E1,Ek，若存在置换，若存在置换 ，使，使得得E1=Ek ，则称，则称 是是E1,Ek的一个的一个合一合一置置换。换。第30页，本讲稿共64页n 例例1：

16、设设E1=g(x,y)，E2=g(a,f(z)。令。令 =a/x,f(h(u)/y,h(u)/z，则则E1=g(a,f(h(u),E2=g(a,f(h(u)因为因为E1=E2，所以，所以 是是E1与与E2的合一的合一 置置换。换。第31页，本讲稿共64页n例例2，设，设E1与与E2同上，同上，=a/x,f(z)/y，则，则 E1=g(a,f(z)=E2，所以，所以 也是也是E1与与E2的的合一合一置置换。换。显然显然 比比 简单，易证简单，易证=，其中，其中=h(u)/z第32页，本讲稿共64页n 最一般合一置换求法最一般合一置换求法：n设有公式：设有公式：E1=P(x,y,z);E2=P(x

17、,f(a),g(b)n从左至右查找不同的项，构成了不一致集：从左至右查找不同的项，构成了不一致集：D1=y,f(a)n继续向右比较又得到一个不一致集：继续向右比较又得到一个不一致集：D2=z,g(b)n置换为置换为 =f(a)/y,g(b)/z第33页，本讲稿共64页n 求一般置换算法：令求一般置换算法：令W=E1,E2 n令令 k=0,Wk=W,k=;是空置换是空置换,表示不作置换。表示不作置换。n如果如果Wk只有一个表达式，则算法停止，只有一个表达式，则算法停止，k就是所要求的结果就是所要求的结果.n找出找出Wk的不一致集的不一致集Dk。n若若Dk中存在元素中存在元素xk和和tk，其中，其

18、中xk是变元，是变元，tk是项，且是项，且xk不在不在tk中中出现，则：出现，则：k+1=k tk/xk n Wk+1=wktk/xk k=k+1 然后转（然后转（2）。）。n算法终止，算法终止，W的一般合一置换不存在。的一般合一置换不存在。第34页，本讲稿共64页n可以证明，如果可以证明，如果E1和和E2可合一，则算法必停止可合一，则算法必停止于第于第2步步。第35页，本讲稿共64页4.2 Horn逻辑程序逻辑程序n人工智能人工智能：n 知识库：用于推理的知识知识库：用于推理的知识n 数据库：事实和论据数据库：事实和论据n 推理：对知识和数据的消解，获得结论推理：对知识和数据的消解，获得结论

19、第36页，本讲稿共64页4.2 Horn逻辑程序逻辑程序n已知的知识表示方法有已知的知识表示方法有n产生式表示法产生式表示法n语义网络表示法语义网络表示法n逻辑表示法逻辑表示法n产产生生式式表表示示法法是是一一类类很很重重要要的的方方法法，知知识识表表示示成成IF THEN 的的形形式式。采采用用产产生生式式方方法法，可可以以将将规则与事实以统一的格式表示，即规则与事实以统一的格式表示，即Horn子句。子句。第37页，本讲稿共64页4.2 Horn逻辑程序逻辑程序n如如果果在在一一个个子子句句中中最最多多含含有有一一个个正正文文字字，那么该子句称为那么该子句称为Horn子句子句。n若若一一个个

20、子子句句集集内内的的子子句句个个数数有有限限且且都都是是Horn子子句句，那那么么该该子子句句集集称称为为一一个个Horn逻辑程序逻辑程序。第38页，本讲稿共64页4.2 Horn逻辑程序逻辑程序nHorn子句可以表示成如下形式：子句可以表示成如下形式：规则体规则体规则头规则头 其其中中规规则则体体一一般般是是n个个原原子子的的合合取取，n=0,1,。规规则则头头可可以以是是单单个个原原子子，也也可可以是空。以是空。第39页，本讲稿共64页4.2 Horn逻辑程序逻辑程序n规则规则：规则体非空且规则头非空的子句。例如，：规则体非空且规则头非空的子句。例如，father(z,y),father(

21、y,x)grandfather(z,x)n事事实实：规规则则体体空空且且规规则则头头非非空空的的子子句句。例例如如，father(John,Peter)。n目目 标标：无无 规规 则则 头头 的的 子子 句句，例例 如如，grandfather(Smith,Peter)，即即要要查查询询Smith是是否否是是Peter的祖父？的祖父？第40页，本讲稿共64页4.2 Horn逻辑程序逻辑程序n一个一个Horn逻辑程序是逻辑程序是Horn子句的集合，也就是规则子句的集合，也就是规则和事实的集合。因此，一个和事实的集合。因此，一个Horn逻辑程序相当于逻辑程序相当于一个知识库。一个知识库。n推理即是

22、通过对一组子句按照一定的方式进行消解最推理即是通过对一组子句按照一定的方式进行消解最终得到新的公式。终得到新的公式。第41页，本讲稿共64页n自动推理的过程即给定目标子句，机器自动推理的过程即给定目标子句，机器按照一定的顺序对逻辑程序中的子句进按照一定的顺序对逻辑程序中的子句进行消解，最后得到目标子句，或者得出行消解，最后得到目标子句，或者得出目标不可满足的结论。目标不可满足的结论。第42页，本讲稿共64页n命题命题Horn逻辑的自动推理逻辑的自动推理n谓词谓词Horn逻辑的自动推理逻辑的自动推理第43页，本讲稿共64页4.3 命题命题Horn逻辑中的自动推理逻辑中的自动推理 n在在命命题题H

23、orn逻逻辑辑中中，子子句句之之间间可可以以按按照照如如下下的的方方式式消解。若有子句消解。若有子句S1：A1,AnS2：B1,Bm Ai 则归结后的子句为则归结后的子句为 S3：A1,Ai-1,B1,Bm,Ai+1,An 即利用规则即利用规则S2将原目标将原目标S1转化为新目标转化为新目标S3.第44页，本讲稿共64页4.3 命题命题Horn逻辑中的自动推理逻辑中的自动推理n基于上述消解方式，求证一个目标基于上述消解方式，求证一个目标S：A1,An 需要逐一以需要逐一以S的体中的每一个原子的体中的每一个原子Ai作为新的目标进行作为新的目标进行求证。求证。A1,An 也称为也称为S的子目标。的

24、子目标。n在以一个原子在以一个原子Ai为目标进行求证时，考察子句集内为目标进行求证时，考察子句集内所有头部是所有头部是Ai的子句，以此子句的体作为新的目标。的子句，以此子句的体作为新的目标。第45页，本讲稿共64页4.3 命题命题Horn逻辑中的自动推理逻辑中的自动推理n当某个关于当某个关于A的子句体部的所有原子得到满足时，直的子句体部的所有原子得到满足时，直接返回接返回A是正确的，而不用再接着考察头是是正确的，而不用再接着考察头是A的其的其他子句。他子句。n假如对于某个原子假如对于某个原子A，逻辑程序中所有头部是，逻辑程序中所有头部是A的子的子句都无法满足，则得出句都无法满足，则得出A无法满

25、足的结论。无法满足的结论。第46页，本讲稿共64页原子原子A的推理算法的推理算法TorF(A)如下：如下：TorF(A)i=0;while (in)/n是此是此Horn逻辑程序内子句的个数逻辑程序内子句的个数 if (第第i条规则的头部条规则的头部=A)/用第用第i条规则考察条规则考察A if (第第i条规则的体是空的条规则的体是空的)then return 1;/A是是 事实事实 else if (TorF(A1)=TorF(Am)=1)/A1 Am 是第是第i条规则体内的所有原子条规则体内的所有原子 then return 1;/由由i规则推出原子规则推出原子A的正确的正确 i=i+1;/

26、第第i条规则体内并非所有原子正确，从而需条规则体内并非所有原子正确，从而需 要考察别的规则要考察别的规则 return 0;/考察了所有的规则，都不能推出考察了所有的规则，都不能推出A 第47页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理 n谓词谓词Horn逻辑的消解要复杂一些。消解方式如下。逻辑的消解要复杂一些。消解方式如下。若有子句若有子句S1：A1,An S2：B1,BmB，并且并且Ai,B具有合一置换具有合一置换，则归结后的子句为则归结后的子句为S3：(A1,Ai-1,B1,Bm,Ai+1,An)n 与命题与命题Horn逻辑相比，需要考虑项的匹配，即合一逻辑

27、相比，需要考虑项的匹配，即合一问题。问题。第48页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理 基于以上消解方式，求证一个目标基于以上消解方式，求证一个目标S1：A1,An 时，要求得出的结果应该是一个置换的集时，要求得出的结果应该是一个置换的集合。集合内的每一个元素合。集合内的每一个元素 i应该使应该使A1 i,An i 成立。成立。第49页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理n在以一个原子在以一个原子Ai为目标进行考察时，考为目标进行考察时，考察每一个头部是察每一个头部是Ai的子句，以此子句的的子句，以此子句的体作为新的目标。

28、返回的不是体作为新的目标。返回的不是0（假）或（假）或者者1（真），而应是一个置换的集合（真），而应是一个置换的集合。n为此先要给出置换算法为此先要给出置换算法Substitution以及以及求表达式合一算法求表达式合一算法Unify。第50页，本讲稿共64页 4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理将置换将置换 作用于表达式作用于表达式e的算法如下的算法如下Substitution(e,)if(e是常量符号是常量符号)then return e;if(e是变量符号是变量符号x)then if(t/x)then return t else return e;if(e=f(t1,

29、tn)then t1=Substitution(t1,);tn=Substitution(tn,)return f(t1,tn)第51页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理对两个表达式对两个表达式e1，e2作合一的算法如下作合一的算法如下/算法返回一个合一置换或算法返回一个合一置换或“无法合一无法合一”的信息的信息Unify(e1，e2)=空集；空集；if e1是变量符号是变量符号x then =e2/x;else if e2是变量符号是变量符号x then =e1/x;else if(e1是常量而是常量而e2不是，或不是，或e2是常量而是常量而e1不是，不

30、是，或或 e1，e2是两个不同的常量是两个不同的常量)then return “无法合一无法合一”else /此时此时e1，e2形如形如f(t1,tn)和和 g(s1,sm)；f,g为函数符号。为函数符号。第52页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理 if(f g)then return“无法合一无法合一”;else 1=Unify(t1，s1);=1;2=Unify(Substitution(t2,),Substitution(s2,);=2;n=Unify(Substitution(tn,)，Substitution(sn,);=n;return ;第5

31、3页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理例例：Horn逻辑程序（知识库）如下，逻辑程序（知识库）如下，father(z,y),father(y,x)grandfather(z,x)，father(John,Peter)，father(Smith,John)。目目标标为为grandfather(Smith,Peter)，即即查查询询Smith是是否否是是Peter的祖父？的祖父？第54页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理推理过程如下；推理过程如下；1.首先通过合一置换首先通过合一置换=Peter/x,Smith/z，将目标

32、与知识，将目标与知识库中第一条规则的规则头匹配，得到新目标库中第一条规则的规则头匹配，得到新目标 father(Smith,y),father(y,Peter)2.考察知识库中第二条和第三条规则，通过合一置换考察知识库中第二条和第三条规则，通过合一置换=John/y与知识库中的事实匹配与知识库中的事实匹配 father(Smith,John),father(John,Peter)因此查询目标成立，并且返回置换因此查询目标成立，并且返回置换 =Peter/x,John/y,Smith/z 第55页，本讲稿共64页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理n考察某个原子考察某个原子A

33、的算法的算法TorF(A)如下如下 TorF(A)输入输入A(s1,sn),返回置换数组返回置换数组,其中数组元素其中数组元素i是一个置换。是一个置换。第56页，本讲稿共64页 TorF(A)i=0；=空集；空集；while(i0 /下面下面i1,i2,im初值均为初值均为1 while(TorF(A1)i1!=NULL)1=TorF(A1)i1;i1=i11;第57页，本讲稿共64页 while(TorF(A2 1)i2!=NULL)while(TorF(Am m-1)im!=NULL)m=TorF(A1)im;=1 m;=；im im+1;L1:i=i+1;/考察下一条规则考察下一条规则

34、return;第58页，本讲稿共64页ProlognProlog(Programming in logic)语言是以语言是以Horn子句逻子句逻辑为基础的高级程序设计语言。辑为基础的高级程序设计语言。n1972年，法国马赛大学的年，法国马赛大学的Alain.Colmerauer提出了提出了Prolog的雏型。的雏型。n1975年，年，Prolog被用于问题求解系统。被用于问题求解系统。第59页，本讲稿共64页n事实：事实：关于对象性质和关系的事实语句；关于对象性质和关系的事实语句；student(john)，married(tom,mary)n规则：规则：关于对象性质和关系的定义规则语句；关于

35、对象性质和关系的定义规则语句；B:A“如果如果A则则B”bird(x):animal(x)，has(x,feather)n问题：问题：关于对象性质或关系的询问。关于对象性质或关系的询问。?student(john)?married(mary，x)第60页，本讲稿共64页n执行方式执行方式n搜索：搜索：在程序中自上而下地搜索事实和规则；在程序中自上而下地搜索事实和规则；n匹配：匹配：将目标中的项与事实和规则进行匹配；将目标中的项与事实和规则进行匹配；n回溯：回溯：当目标中一项失败时，如果目标中有当目标中一项失败时，如果目标中有已经成功的的项，就重新调用这些成功项中已经成功的的项，就重新调用这些成

36、功项中的一个，谋求新的成功。的一个，谋求新的成功。第61页，本讲稿共64页nProlog语言的最基本语言成分是语言的最基本语言成分是项项(term)，一个，一个项或者是：项或者是：n常量：常量：是指对象和对象之间的特定关系的名；是指对象和对象之间的特定关系的名；整数，整数，John，student，likesn变量：变量：表示任意的对象，变元；表示任意的对象，变元；如如X,Y,Answer,_value等。等。n结构：结构：是常量和变量的序列，它由一个函子是常量和变量的序列，它由一个函子(函词函词或谓词或谓词)和该函子的自变量所组成。如：和该函子的自变量所组成。如：likes(john,X)m

37、arried(mary,jack)第62页，本讲稿共64页例：例：(1)likes(bell,sports)(2)likes(mary,smith)(3)likes(mary,sports)(4)likes(jones,smith)(5)friend(john,X):likes(X,sports),likes(X,smith)(规则规则)(6)?friends(john,Y)(问题问题)第63页，本讲稿共64页(7)?likes(X,sports),likes(X,smith)(8)?likes(bell,smith)(bell/X)(7)?likes(X,sports),likes(X,smith)(8)?likes(mary,smith)(mary/X)Y=mary，John与与Mary是朋友是朋友第64页，本讲稿共64页