计算引论 推理与计算精选文档.ppt

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

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

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

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

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

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

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

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

8、值：（1 1）为每个个体常量指派）为每个个体常量指派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上的一个解释。上的一个解释。本讲稿第十五页，共六十四页n永真：永真：n如果谓词公式如果谓词公式P，对个体域，对个体域D上的任何一个解释上

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

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

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

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

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

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

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

16、1,Ek的一个的一个合一合一置置换。换。本讲稿第三十页，共六十四页n 例例1：设设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的合一的合一 置置换。换。本讲稿第三十一页，共六十四页n例例2，设，设E1与与E2同上，同上，=a/x,f(z)/y，则，则 E1=g(a,f(z)=E2，所以，所以 也是也是E1与与E2的的合一合一置置换。换。显然显然 比比 简单，易证简单，易证=，其中，其中=h(u)/z本讲稿第三十二页，共六十四页n 最一般合一

17、置换求法最一般合一置换求法：n设有公式：设有公式：E1=P(x,y,z);E2=P(x,f(a),g(b)n从左至右查找不同的项，构成了不一致集：从左至右查找不同的项，构成了不一致集：D1=y,f(a)n继续向右比较又得到一个不一致集：继续向右比较又得到一个不一致集：D2=z,g(b)n置换为置换为 =f(a)/y,g(b)/z本讲稿第三十三页，共六十四页n 求一般置换算法：令求一般置换算法：令W=E1,E2 n令令 k=0,Wk=W,k=;是空置换是空置换,表示不作置换。表示不作置换。n如果如果Wk只有一个表达式，则算法停止，只有一个表达式，则算法停止，k就是所要求的结果就是所要求的结果.n

18、找出找出Wk的不一致集的不一致集Dk。n若若Dk中存在元素中存在元素xk和和tk，其中，其中xk是变元，是变元，tk是项，且是项，且xk不在不在tk中中出现，则：出现，则：k+1=k tk/xk n Wk+1=wktk/xk k=k+1 然后转（然后转（2）。）。n算法终止，算法终止，W的一般合一置换不存在。的一般合一置换不存在。本讲稿第三十四页，共六十四页n可以证明，如果可以证明，如果E1和和E2可合一，则算法必停止于可合一，则算法必停止于第第2步步。本讲稿第三十五页，共六十四页4.2 Horn逻辑程序逻辑程序n人工智能人工智能：n 知识库：用于推理的知识知识库：用于推理的知识n 数据库：事

19、实和论据数据库：事实和论据n 推理：对知识和数据的消解，获得结论推理：对知识和数据的消解，获得结论本讲稿第三十六页，共六十四页4.2 Horn逻辑程序逻辑程序n已知的知识表示方法有已知的知识表示方法有n产生式表示法产生式表示法n语义网络表示法语义网络表示法n逻辑表示法逻辑表示法n产产生生式式表表示示法法是是一一类类很很重重要要的的方方法法，知知识识表表示示成成IF THEN 的的形形式式。采采用用产产生生式式方方法法，可可以以将规则与事实以统一的格式表示，即将规则与事实以统一的格式表示，即Horn子句。子句。本讲稿第三十七页，共六十四页4.2 Horn逻辑程序逻辑程序n如如果果在在一一个个子子

20、句句中中最最多多含含有有一一个个正正文文字字，那么该子句称为那么该子句称为Horn子句子句。n若若一一个个子子句句集集内内的的子子句句个个数数有有限限且且都都是是Horn子子句句，那那么么该该子子句句集集称称为为一一个个Horn逻逻辑辑程程序序。本讲稿第三十八页，共六十四页4.2 Horn逻辑程序逻辑程序nHorn子句可以表示成如下形式：子句可以表示成如下形式：规则体规则体规则头规则头 其其中中规规则则体体一一般般是是n个个原原子子的的合合取取，n=0,1,。规规则则头头可可以以是是单单个个原原子子，也也可可以是空。以是空。本讲稿第三十九页，共六十四页4.2 Horn逻辑程序逻辑程序n规则规则

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

22、此，一个和事实的集合。因此，一个Horn逻辑程序相当于逻辑程序相当于一个知识库。一个知识库。n推理即是通过对一组子句按照一定的方式进行消解最推理即是通过对一组子句按照一定的方式进行消解最终得到新的公式。终得到新的公式。本讲稿第四十一页，共六十四页n自动推理的过程即给定目标子句，机器自动推理的过程即给定目标子句，机器按照一定的顺序对逻辑程序中的子句进按照一定的顺序对逻辑程序中的子句进行消解，最后得到目标子句，或者得出行消解，最后得到目标子句，或者得出目标不可满足的结论。目标不可满足的结论。本讲稿第四十二页，共六十四页n命题命题Horn逻辑的自动推理逻辑的自动推理n谓词谓词Horn逻辑的自动推理逻

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

24、中的每一个原子的体中的每一个原子Ai作为新的目标进行作为新的目标进行求证。求证。A1,An 也称为也称为S的子目标。的子目标。n在以一个原子在以一个原子Ai为目标进行求证时，考察子句集内为目标进行求证时，考察子句集内所有头部是所有头部是Ai的子句，以此子句的体作为新的目标。的子句，以此子句的体作为新的目标。本讲稿第四十五页，共六十四页4.3 命题命题Horn逻辑中的自动推理逻辑中的自动推理n当某个关于当某个关于A的子句体部的所有原子得到满足时，的子句体部的所有原子得到满足时，直接返回直接返回A是正确的，而不用再接着考察头是是正确的，而不用再接着考察头是A的其的其他子句。他子句。n假如对于某个原

25、子假如对于某个原子A，逻辑程序中所有头部是，逻辑程序中所有头部是A的的子句都无法满足，则得出子句都无法满足，则得出A无法满足的结论。无法满足的结论。本讲稿第四十六页，共六十四页原子原子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条规则

26、体内的所有原子条规则体内的所有原子 then return 1;/由由i规则推出原子规则推出原子A的正确的正确 i=i+1;/第第i条规则体内并非所有原子正确，从而需条规则体内并非所有原子正确，从而需 要考察别的规则要考察别的规则 return 0;/考察了所有的规则，都不能推出考察了所有的规则，都不能推出A 本讲稿第四十七页，共六十四页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理 n谓词谓词Horn逻辑的消解要复杂一些。消解方式如下。若逻辑的消解要复杂一些。消解方式如下。若有子句有子句S1：A1,An S2：B1,BmB，并且并且Ai,B具有合一置换具有合一置换，则归结后的子句为

27、则归结后的子句为S3：(A1,Ai-1,B1,Bm,Ai+1,An)n 与命题与命题Horn逻辑相比，需要考虑项的匹配，即合一逻辑相比，需要考虑项的匹配，即合一问题。问题。本讲稿第四十八页，共六十四页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理 基于以上消解方式，求证一个目标基于以上消解方式，求证一个目标S1：A1,An 时，要求得出的结果应该是一个置换的集时，要求得出的结果应该是一个置换的集合。集合内的每一个元素合。集合内的每一个元素 i应该使应该使A1 i,An i 成立。成立。本讲稿第四十九页，共六十四页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理n在以一个原子在

28、以一个原子Ai为目标进行考察时，考为目标进行考察时，考察每一个头部是察每一个头部是Ai的子句，以此子句的的子句，以此子句的体作为新的目标。返回的不是体作为新的目标。返回的不是0（假）或（假）或者者1（真），而应是一个置换的集合（真），而应是一个置换的集合。n为此先要给出置换算法为此先要给出置换算法Substitution以及以及求表达式合一算法求表达式合一算法Unify。本讲稿第五十页，共六十四页 4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理将置换将置换 作用于表达式作用于表达式e的算法如下的算法如下Substitution(e,)if(e是常量符号是常量符号)then retur

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

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

31、titution(s2,);=2;n=Unify(Substitution(tn,)，Substitution(sn,);=n;return ;本讲稿第五十三页，共六十四页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理例例：Horn逻辑程序（知识库）如下，逻辑程序（知识库）如下，father(z,y),father(y,x)grandfather(z,x)，father(John,Peter)，father(Smith,John)。目目标标为为grandfather(Smith,Peter)，即即查查询询Smith是是否是否是Peter的祖父？的祖父？本讲稿第五十四页，共六十四页4.

32、4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理推理过程如下；推理过程如下；1.首先通过合一置换首先通过合一置换=Peter/x,Smith/z，将目标与知，将目标与知识库中第一条规则的规则头匹配，得到新目标识库中第一条规则的规则头匹配，得到新目标 father(Smith,y),father(y,Peter)2.考察知识库中第二条和第三条规则，通过合一置换考察知识库中第二条和第三条规则，通过合一置换=John/y与知识库中的事实匹配与知识库中的事实匹配 father(Smith,John),father(John,Peter)因此查询目标成立，并且返回置换因此查询目标成立，并且返回置换

33、=Peter/x,John/y,Smith/z 本讲稿第五十五页，共六十四页4.4 谓词谓词Horn逻辑中的自动推理逻辑中的自动推理n考察某个原子考察某个原子A的算法的算法TorF(A)如下如下 TorF(A)输入输入A(s1,sn),返回置换数组返回置换数组,其中数组元素其中数组元素i是一个置换。是一个置换。本讲稿第五十六页，共六十四页 TorF(A)i=0；=空集；空集；while(i0 /下面下面i1,i2,im初值均为初值均为1 while(TorF(A1)i1!=NULL)1=TorF(A1)i1;i1=i11;本讲稿第五十七页，共六十四页 while(TorF(A2 1)i2!=N

34、ULL)while(TorF(Am m-1)im!=NULL)m=TorF(A1)im;=1 m;=；im im+1;L1:i=i+1;/考察下一条规则考察下一条规则 return;本讲稿第五十八页，共六十四页ProlognProlog(Programming in logic)语言是以语言是以Horn子句逻子句逻辑为基础的高级程序设计语言。辑为基础的高级程序设计语言。n1972年，法国马赛大学的年，法国马赛大学的Alain.Colmerauer提出了提出了Prolog的雏型。的雏型。n1975年，年，Prolog被用于问题求解系统。被用于问题求解系统。本讲稿第五十九页，共六十四页n事实：事实

35、：关于对象性质和关系的事实语句；关于对象性质和关系的事实语句；student(john)，married(tom,mary)n规则：规则：关于对象性质和关系的定义规则语句；关于对象性质和关系的定义规则语句；B:A“如果如果A则则B”bird(x):animal(x)，has(x,feather)n问题：问题：关于对象性质或关系的询问。关于对象性质或关系的询问。?student(john)?married(mary，x)本讲稿第六十页，共六十四页n执行方式执行方式n搜索：搜索：在程序中自上而下地搜索事实和规则；在程序中自上而下地搜索事实和规则；n匹配：匹配：将目标中的项与事实和规则进行匹配；将目

36、标中的项与事实和规则进行匹配；n回溯：回溯：当目标中一项失败时，如果目标中有已经成当目标中一项失败时，如果目标中有已经成功的的项，就重新调用这些成功项中的一个，谋求功的的项，就重新调用这些成功项中的一个，谋求新的成功。新的成功。本讲稿第六十一页，共六十四页nProlog语言的最基本语言成分是语言的最基本语言成分是项项(term)，一个，一个项或者是：项或者是：n常量：常量：是指对象和对象之间的特定关系的名；是指对象和对象之间的特定关系的名；整数，整数，John，student，likesn变量：变量：表示任意的对象，变元；表示任意的对象，变元；如如X,Y,Answer,_value等。等。n结

37、构：结构：是常量和变量的序列，它由一个函子是常量和变量的序列，它由一个函子(函词函词或谓词或谓词)和该函子的自变量所组成。如：和该函子的自变量所组成。如：likes(john,X)married(mary,jack)本讲稿第六十二页，共六十四页例：例：(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)(问题问题)本讲稿第六十三页，共六十四页(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是朋友是朋友本讲稿第六十四页，共六十四页