《人工智能-谓词逻辑.pptx》由会员分享，可在线阅读，更多相关《人工智能-谓词逻辑.pptx（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、谓词逻辑基础谓词逻辑基础一阶逻辑一阶逻辑l基本概念基本概念l个体词：表示主语的词个体词：表示主语的词l谓词：刻画个体性质或个体之间关系的词谓词：刻画个体性质或个体之间关系的词l量词：表示数量的词量词：表示数量的词l小王是个工程师。小王是个工程师。l8是个自然数。是个自然数。l我去买花。我去买花。l小丽和小华是朋友。小丽和小华是朋友。其其中中，“小小王王”、“工工程程师师”、“我我”、“花花”、“8”、“小小丽丽”、“小小华华”都都是是个个体体词词，而而“是是个个工工程程师师”、“是是个个自自然然数数”、“去去买买”、“是是朋朋友友”都都是是谓谓词词。显显然然前前两两个个谓谓词词表表示示的的是是
2、事事物物的的性性质质，第第三三个个谓谓词词“去去买买”表表示示的的一一个个动动作作也也表表示示了了主主、宾宾两两个个个个体体词词的的关关系系，最最后后一一个个谓谓词词“是是朋朋友友”表表示示两两个个个个体体词词之之间间的的关系。关系。谓词逻辑基础谓词逻辑基础谓词逻辑基础谓词逻辑基础l例如：（例如：（1）所有的人都是要死的。）所有的人都是要死的。l（2）有的人活到一百岁以上。有的人活到一百岁以上。在个体域在个体域D为人类集合时，可符号化为：为人类集合时，可符号化为：（1）xPxP(x x)，其中，其中P P(x x)表示表示x x是要死的。是要死的。（2）x Qx Q(x x),),其中其中Q
3、Q(x x)表示表示x x活到一百岁以上。活到一百岁以上。在个体域在个体域D是全总个体域时，是全总个体域时，引入特殊谓词引入特殊谓词R R(x x)表示表示x x是人，可符号化为：是人，可符号化为：（1 1）x x（R R(x x)P P(x x)）,其中，其中，R R(x x)表示表示x x是人；是人；P P(x x)表示表示x x是要死的。是要死的。（2 2）x x（R R(x x)Q Q(x x)），），其中，其中，R R(x x)表示表示x x是人；是人；Q Q(x x)表示表示x x活到一百岁以上。活到一百岁以上。一阶逻辑一阶逻辑l公式及其解释公式及其解释l个体常量：个体常量：a,b
4、,cl个体变量：个体变量：x,y,zl谓词符号：谓词符号：P,Q,Rl量词符号：量词符号：,谓词逻辑基础谓词逻辑基础量词否定等值式：量词否定等值式：l(x x ）P P（x x）（y y ）P P（y y）l(x x ）P P（x x）（y y ）P P（y y）量词分配等值式：量词分配等值式：l(x x ）(P P（x x）Q Q（x x）)()(x x ）P P（x x）(x x ）Q Q（x x）l(x x ）(P P（x x）Q Q（x x）)()(x x ）P P（x x）(x x ）Q Q（x x）消去量词等值式：消去量词等值式：设个体域为有穷集合（设个体域为有穷集合（a a1 1
5、,a,a2 2,a an n）l(x x ）P P（x x）P P（a a1 1 ）P P（a a2 2 ）P P（a an n ）l(x x ）P P（x x）P P（a a1 1 ）P P（a a2 2 ）P P（a an n ）谓词逻辑基础谓词逻辑基础量词辖域收缩与扩张等值式：量词辖域收缩与扩张等值式：l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Ql(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(Q Q P P（x x）)Q Q (
6、x x ）P P（x x）l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Ql(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q l(x x ）(Q Q P P（x x）)Q Q (x x ）P P（x x）谓词逻辑基础谓词逻辑基础谓词逻辑基础谓词逻辑基础SKOLEMSKOLEM标准形标准形l前束范式前束范式定义定义：说公式：说公式A A是一个前束范式，如果是一个前束范式，如果A A中中的一切量词都位于该公式的最左边（不含否的一切量词都位于该公式的最左边（不含否
7、定词），且这些量词的辖域都延伸到公式的定词），且这些量词的辖域都延伸到公式的末端。末端。谓词逻辑归结原理谓词逻辑归结原理即：即：把所有的量词都提到前面去，然后消把所有的量词都提到前面去，然后消掉所有量词掉所有量词(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)(Q(Qn nx xn n)M(x)M(x1 1,x,x2 2,x,xn n)约束变项换名规则：约束变项换名规则：l(Qx(Qx ）MM（x x）（QyQy ）MM（y y）l(Qx(Qx ）MM（x,zx,z）（QyQy ）MM（y,zy,z）谓词逻辑归结原理谓词逻辑归结原理 l量词消去原则：量词消去原则：消去存在量词消去存在
8、量词“”，略去全程量词，略去全程量词“”。注意：注意：左边有全程量词的存在量词，消去左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，时该变量改写成为全程量词的函数；如没有，改写成为常量。改写成为常量。谓词逻辑归结原理谓词逻辑归结原理 lSkolemSkolem定理定理：谓词逻辑的任意公式都可以化为与之等价谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。的前束范式，但其前束范式不唯一。lSKOLEMSKOLEM标准形定义：标准形定义：消去量词后的谓词公式。消去量词后的谓词公式。注意注意：谓词公式：谓词公式G G的的SKOLEMSKOLEM标准形同标准形同
9、G G并并不等值不等值。谓词逻辑归结原理谓词逻辑归结原理例：例：将下式化为将下式化为Skolem标准形：标准形：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)l解：第一步，消去解：第一步，消去号，得：号，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)l第二步，深入到量词内部，得：第二步，深入到量词内部，得：(x)(y)P(a,x,y)(x)x)(y)Q(y,b)R(x)l第三步，变元易名，得第三步，变元易名，得(x)(y)P(a,x,y)(u)(v)(Q(v,b)R(u)l第第四四步步，存存在在量量词词左左移移，直直至至所所有有的的量量词词移移到到前前面面，(x
10、)(y)(u)(v)(P(a,x,y)(Q(v,b)R(u)由此得到前述范式由此得到前述范式l第第五五步步，消消去去“”（存存在在量量词词），略略去去“”全全称称量词量词l消消去去(y)，因因为为它它左左边边只只有有(x)，所所以以使使用用x的的函函数数f(x)代替之，这样得到：代替之，这样得到：(x)(u)(v)(P(a,x,f(x)Q(v,b)R(u)l消去消去(u)，同理使用，同理使用g(x)代替之，这样得到：代替之，这样得到：(x)(v)(P(a,x,f(x)Q(v,b)R(g(x)l则，略去全称变量，原式的则，略去全称变量，原式的Skolem标准形为：标准形为：P(a,x,f(x)Q
11、(v,b)R(g(x)l子句与子句集子句与子句集l文字：不含任何连接词的谓词公式。文字：不含任何连接词的谓词公式。l子句：一些文字的析取（谓词的和）。子句：一些文字的析取（谓词的和）。l子句集子句集S S的求取：的求取：G G SKOLEM SKOLEM标准形标准形 消去存在变量消去存在变量 以以“，”取代取代“”，并表示为集合形式，并表示为集合形式 。谓词逻辑归结原理谓词逻辑归结原理l G是不可满足的是不可满足的S是不可满足的是不可满足的lG与与S不等价，但在不可满足得意义下是一致的。不等价，但在不可满足得意义下是一致的。l定理：定理：若若G是给定的公式，而是给定的公式，而S是相应的子句集，
12、则是相应的子句集，则G是不是不可满足的可满足的S是不可满足的。是不可满足的。注意注意：G真不一定真不一定S真，而真，而S真必有真必有G真。真。即：即：S=G谓词逻辑归结原理谓词逻辑归结原理lG=GG=G1 1 G G2 2 G G3 3 G Gn n的子句形的子句形lG G的字句集可以分解成几个单独处理。的字句集可以分解成几个单独处理。l有有 S SG G=S=S1 1 U SU S2 2 U S U S3 3 U U U SU Sn n则则S SG G 与与 S S1 1 U U S S2 2 U U S S3 3 U U U U S Sn n在在不不可可满满足足得得意意义义上是一致的。上是
13、一致的。即即S SG G 不可满足不可满足 S S1 1 U SU S2 2 U S U S3 3 U U U SU Sn n不可满足不可满足3.3谓词逻辑归结原理谓词逻辑归结原理例例：对对所所有有的的x,y,z来来说说，如如果果y是是x的的父父亲亲，z又又是是y的的父父亲亲，则则z是是x的的祖祖父父。又又知知每每个个人人都都有有父父亲亲，试试问问对对某某个人来说谁是它的祖父？个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：解：这里我们首先引入谓词：lP(x,y)表示表示x是是y的父亲的父亲lQ(x,y)表示表
14、示x是是y的祖父的祖父lANS(x)表示问题的解答表示问题的解答谓词逻辑归结原理谓词逻辑归结原理对对于于第第一一个个条条件件，“如如果果x是是y的的父父亲亲，y又又是是z的的父父亲亲，则则x是是z的祖父的祖父”，一阶逻辑表达式如下：，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)SA1：P(x,y)P(y,z)Q(x,z)对于第二个条件：对于第二个条件：“每个人都有父亲每个人都有父亲”，一阶逻辑表达式：，一阶逻辑表达式：A2：(y)(x)P(x,y)SA2：P(f(y),y)对于结论：某个人是它的祖父对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否定
15、后得到子句：否定后得到子句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：则得到的相应的子句集为：SA1，SA2，SB谓词逻辑归结原理谓词逻辑归结原理l归结原理正确性的根本在于，找到矛盾归结原理正确性的根本在于，找到矛盾可以肯定不真。可以肯定不真。l方法：方法：l和命题逻辑一样。和命题逻辑一样。l但由于有函数，所以要考虑但由于有函数，所以要考虑合一合一和和置换置换。谓词逻辑归结原理谓词逻辑归结原理l置置换换：可可以以简简单单的的理理解解为为是是在在一一个个谓谓词词公公式式中中用用置置换换项项去去置置换换变变量。量。l定义：定义：置置换换是是形形如
16、如t1/x1,t2/x2,tn/xn的的有有限限集集合合。其其中中，x1,x2,xn是是互互不不相相同同的的变变量量，t1,t2,tn是是不不同同于于xi的的项项（常常量量、变变量量、函函数数）；ti/xi表表示示用用ti置置换换xi，并并且且要要求求ti与与xi不不能能相相同同，而而且且xi不不能能循循环地出现在另一个环地出现在另一个ti中。中。例如例如a/x，c/y，f(b)/z是一个置换。是一个置换。g(y)/x，f(x)/y不是一个置换，不是一个置换，谓词逻辑归结原理谓词逻辑归结原理置换置换置换的合成置换的合成l设设 t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/y
17、n，是两个置换。，是两个置换。则则 与与 的合成也是一个置换，记作的合成也是一个置换，记作 。它是从集合。它是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：中删去以下两种元素：li.当当ti=xi时，删去时，删去ti/xi(i=1,2,n);lIi.当当yi x1,x2,xn时，删去时，删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。合成即是对合成即是对ti先做先做 置换然后再做置换然后再做 置换，置换置换，置换xi谓词逻辑归结原理谓词逻辑归结原理l例：例：设：设：f(y)/x,z/y，a/x,b/y,y
18、/z，求，求 与与 的合成。的合成。解：先求出集合解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其其中中，f(b)/x中中的的f(b)是是置置换换 作作用用于于f(y)的的结结果果；y/y中中的的y是是置置换换 作作用用于于z的的结结果果。在在该该集集合合中中，y/y满满足足定定义义中中的的条条件件i，需需要要删删除除；a/x，b/y满满足足定定义义中中的的条条件件ii，也也需需要要删删除除。最后得最后得 f(b)/x，y/z谓词逻辑归结原理谓词逻辑归结原理合一合一l合合一一可可以以简简单单地地理理解解为为“寻寻找找相相对对变
19、变量量的的置置换换，使使两两个个谓谓词词公式一致公式一致”。l定定义义：设设有有公公式式集集FF1，F2，Fn，若若存存在在一一个个置置换换，可可使使F1 F2=Fn，则则称称 是是F的的一一个个合合一一。同同时时称称F1，F2，.，Fn是可合一的。是可合一的。l例：例：设设有有公公式式集集FP(x,y,f(y),P(a,g(x),z)，则则 a/x,g(a)/y,f(g(a)/z是它的一个合一。是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。注意：一般说来，一个公式集的合一不是唯一的。谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理
20、谓词逻辑归结原理谓词逻辑归结原理归结原理归结原理l归结的注意事项：归结的注意事项：1.1.谓词的一致性谓词的一致性，P()P()与与Q()Q()，不可以不可以2.2.常量的一致性，常量的一致性，P(a,P(a,)与与P(b,P(b,.).)，不可以不可以 变量，变量，P(a,P(a,.).)与与P(x,P(x,)，可以可以3.3.变量与函数，变量与函数，P(a,x,P(a,x,.).)与与P(x,f(x),P(x,f(x),)，不可，不可以；以；1.1.是不能同时消去两个互补对，是不能同时消去两个互补对，PQPQ与与PPQ Q的空，的空，不可以不可以2.2.先进行内部简化（置换、合并）先进行内
21、部简化（置换、合并）谓词逻辑归结原理谓词逻辑归结原理l归结的过程归结的过程写出谓词关系公式写出谓词关系公式 用反演法写出谓词表达式用反演法写出谓词表达式 SKOLEMSKOLEM标准形标准形 子句集子句集S S 对对S S中可归结的子句做归结中可归结的子句做归结 归结式仍放入归结式仍放入S S中，反复归结过程中，反复归结过程 得到空子句得到空子句 得证得证谓词逻辑归结原理谓词逻辑归结原理例题例题“快乐学生快乐学生”问题问题l假假设设任任何何通通过过计计算算机机考考试试并并获获奖奖的的人人都都是是快快乐乐的的，任任何何肯肯学学习习或或幸幸运运的的人人都都可可以以通通过过所所有有的的考考试试，张张
22、不不肯肯学学习习但但他他是是幸幸运运的的，任任何何幸幸运运的的人人都都能能获获奖奖。求求证证：张是快乐的。张是快乐的。l解：先将问题用谓词表示如下：解：先将问题用谓词表示如下：lR1:“任何通过计算机考试并获奖的人都是快乐的任何通过计算机考试并获奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)lR2:“任何肯学习或幸运的人都可以通过所有考试任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)lR3:“张不肯学习但他是幸运的张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)
23、lR4:“任何幸运的人都能获奖任何幸运的人都能获奖”(x)(Luck(x)Win(x,prize)l结论：结论：“张是快乐的张是快乐的”的否定的否定Happy(zhang)例题例题“快乐学生快乐学生”问题问题l由由R1及逻辑转换公式及逻辑转换公式:P WH=（P W）H，可得，可得l(1)Pass(x,computer)Win(x,prize)Happy(x)l由由R2：(2)Study(y)Pass(y,z)l(3)Lucky(u)Pass(u,v)l由由R3：(4)Study(zhang)l(5)Lucky(zhang)l由由R4：(6)Lucky(w)Win(w，prize)l由结论：由
24、结论：(7)Happy(zhang)（结论的否定）（结论的否定）l(8)Pass(w,computer)Happy(w)Luck(w)(1)(6)，w/xl(9)Pass(zhang,computer)Lucky(zhang)(8)(7)，zhang/wl(10)Pass(zhang,computer)(9)(5)l(11)Lucky(zhang)(10)(3)，zhang/u,computer/vl(12)(11)(5)l归结法的实质：归结法的实质：l归结法是仅有一条推理规则的推理方法。归结法是仅有一条推理规则的推理方法。l归结的过程是一个语义树倒塌的过程。归结的过程是一个语义树倒塌的过程。
25、l归结法的问题归结法的问题l子句中有等号或不等号时，完备性不成立。子句中有等号或不等号时，完备性不成立。Herbrand Herbrand定理的不实用性引出了可实用的定理的不实用性引出了可实用的归结法。归结法。谓词逻辑归结原理谓词逻辑归结原理归结过程的控制策略归结过程的控制策略l要解决的问题：要解决的问题：l归结方法的知识爆炸。归结方法的知识爆炸。l控制策略的目的控制策略的目的l归结点尽量少归结点尽量少l控制策略的原则控制策略的原则l给给出出控控制制策策略略，以以使使仅仅对对选选择择合合适适的的子子句句间间方方可可做做归归结结。避避免免多多余余的的、不不必必要要的的归归结结式式出出现现。或或者
26、者说说，少少做做些些归归结结仍仍能能导导出出空子句。空子句。谓词逻辑归结原理谓词逻辑归结原理删除策略删除策略=完备完备l名名词词解解释释：归归类类：设设有有两两个个子子句句C C和和D D，若若有有置置换换 使使得得C C D D成立，则称子句成立，则称子句C C把子句把子句D D归类。归类。由于小的可以代表大的，所以小的吃掉大的了。由于小的可以代表大的，所以小的吃掉大的了。l若若对对S S使使用用归归结结推推理理过过程程中中，当当归归结结式式C Cj j是是重重言言式式（永永真真式式）和和C Cj j被被S S中中子子句句和和子子句句集集的的归归结结式式C Ci i(ij)(ij)所所归归类
27、类时时，便便将将C Cj j删删除除。这这样样的的推推理理过过程程便便称做使用了删除策略的归结过程。称做使用了删除策略的归结过程。谓词逻辑归结原理谓词逻辑归结原理l主主要要思思想想：归归结结过过程程在在寻寻找找可可归归结结子子句句时时，子子句句集集中中的的子子句句越越多多，需需要要付付出出的的代代价价就就会会越越大大。如如果果在在归归结结时时能能把把子子句句集集中中无无用用的的子子句句删删除除掉掉，就就会会缩缩小小搜搜索索范范围围，减减少少比比较较次次数数，从从而而提提高高归归结结效效率率。删删除除策策略略对对阻阻止止不不必必要要的的归归结结式式的的产产生生来来缩缩短短归归结结过过程程是是有有
28、效效的的。然然而而要要在在归归结结式式C Cj j产产生生后后方方能能判判别别它它是是否否可可被被删删除除，这这部部分分计计算算量量是是要要花花费费的的，只只是是节节省省了了被被删删除除的的子子句句又又生生成成的的归归结结式式。尽尽管管使使用用删删除除策策略略的的归归结结，少少做做了了归归结结但但不不影影响响产产生生空空子子句句，就就是是说说删删除除策略的归结推理是完备的。策略的归结推理是完备的。谓词逻辑归结原理谓词逻辑归结原理采用支撑集采用支撑集 完备完备 支支撑撑集集：设设有有不不可可满满足足子子句句集集S S的的子子集集T T，如如果果S-TS-T是可满足的，则是可满足的，则T T是支持
29、集。是支持集。采采用用支支撑撑集集策策略略时时，从从开开始始到到得得到到 的的整整个个归归结结过过程程中中，只只选选取取不不同同时时属属于于S-TS-T的的子子句句，在在其其间间进进行行归归结结。就就是是说说，至至少少有有一一个个子子句句来自于支撑集来自于支撑集T T或由或由T T导出的归结式。导出的归结式。谓词逻辑归结原理谓词逻辑归结原理例例如如：A A1 1AA2 2AA3 3B B中中的的B B可可以以作作为为支支撑撑集集使使用用。要要求求每每一一次次参参加加归归结结的的亲亲本本子子句句中中，只只要要应应该该有有一一个个是是有有目标公式的否定（目标公式的否定（B B）所得到的子句或者它们
30、的后裔。）所得到的子句或者它们的后裔。l支撑集策略的归结是完备的，同样，所有可归结的谓词支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即集是目标子句的非，即S SB B。谓词逻辑归结原理谓词逻辑归结原理ST可满足支撑集示意图谓词逻辑归结原理谓词逻辑归结原理 语义归结语义归结 完备完备 语语义义归归结结策策略略是是将将子子句句S S按按照照一一定定的的语语义义分分成成两两部部分分，约
31、约定定每每部部分分内内的的子子句句间间不不允允许许作作归归结结。同同时时还还引引入入了了文文字字次次序序，约约定定归归结结时时其其中中的的一一个个子子句句的的被被归归结结文文字字只只能能是是该该子子句中句中“最大最大”的文字。的文字。语义归结策略的归结是完备的，同样，语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行排序。将子句集两个部分中的子句进行排序。谓
32、词逻辑归结原理谓词逻辑归结原理线性归结线性归结 完备完备 线性归结策略首先从子句集中选取一个称作顶子线性归结策略首先从子句集中选取一个称作顶子句的子句句的子句C C0 0开始作归结。归结过程中所得到的归结开始作归结。归结过程中所得到的归结式式C Ci i立即同另一子句立即同另一子句B Bi i进行归结得归结式进行归结得归结式C Ci+1i+1。而。而B Bi i属于属于S S或是已出现的归结式或是已出现的归结式C Cj j(ji)(j=完备完备 单单元元归归结结策策略略要要求求在在归归结结过过程程中中，每每次次归归结结都都有有一一个个子子句句是是单单元元子子句句（只只含含一一个个文文字字的的子
33、子句句）或或单单元元因因子子。显显而而易易见见，词词中中方方法法可可以以简简单单地地削削去去另另一一个个非非单单子子句句中中的的一一个个因因子子，使使其其长长度度减减少少，构成简单化，归结效率较高。构成简单化，归结效率较高。初始子句集中没有单元子句时，单元归结策略初始子句集中没有单元子句时，单元归结策略无效。所以说无效。所以说“反之不成立反之不成立”，即此问题不能采，即此问题不能采用单元归结策略用单元归结策略。输入归结输入归结 =完备完备 与与单单元元归归结结策策略略相相似似，输输入入归归结结策策略略要要求求在在归归结结过过程程中中，每每一一次次归归结结的的两两个个子子句句中中必必须须有有一一
34、个个是是S S的的原原始始子子句句。这这样样可可以以避避免免归归结结出出的的不不必必要要的的新新子子句句加加入入归归结结，造造成成恶恶性性循循环环。可可以以减减少少不不必必要要的的归归结结次数。次数。如同单元归结策略，不是所有的可归结谓如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集词公式的最后结论都是可以从原始子句集中的得到的。简单的例子，归结结束时，中的得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不子句
35、集中没有单元子句的谓词公式一定不能采用输入归结策略。能采用输入归结策略。演讲完毕，谢谢观看！附录资料：人工智能简介附录资料：人工智能简介AboutTeachingPlan基本要求：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支，是目前迅速发展的一门新兴学科，新思想新方法层出不穷。其基本思想是利用机器来模仿和执行人脑的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。对于培养学生计算机技术的应用能力，开阔思路和视野，有重要意义。AboutTeachingPlan因此，要求学生掌握知识表示知识表示和问题求解问题求解的几种常用方法，尤其是不确定性推
36、理不确定性推理；掌握机器学习机器学习基本概念，了解几种机器学习方法机器学习方法尤其是神经网络学习方法；神经网络学习方法；掌握专家系统的概念，了解专家系统设计方法专家系统设计方法，掌握一些智能控制方法智能控制方法，了解国内外人工智能研究尤其是机器人的最新进展；最新进展；具有一定的人工智能编程设计能力人工智能编程设计能力（利用Lisp或Prolog语言）。AboutTeachingPlan课程内容以及学时分配课程内容以及学时分配人工智能引论(1)人工智能概念及与计算机的关系，研究途径、内容和应用领域概况介绍，其他最新材料其他最新材料。符号主义、连接主义、行为主义三大流派人工智能数学基础(1)知识表
37、示方法（2）状态空间法、问题归约法，谓词逻辑法、产生式表示法（动物识别系统）；CLIPS语言；语义网络法、框架法（这是结构化表示）；剧本、过程、Petri网、面向对象的表示。AboutTeachingPlan搜索技术和策略（3-4）状态空间法，盲目搜索和启发式搜索，A*算法；海伯伦理论、消解原理和策略；与或形推理和搜索策略；其他求解技术。不确定推理技术（3-4）主观Bayes理论；可信度方法和证据理论；系统组织技术；非单调推理；Rete快速算法；模糊推理技术；基于语义网络和框架不确定推理；专家系统（2）专家系统概念、结构和知识获取；黑板模型、知识组织、管理及系统建造和开发工具；专家系统举例及编
38、程。人工智能程序设计人工智能程序设计（1）人工智能语言基本机制：LISP和PROLOG。AboutTeachingPlan模式识别导论（3）模式识别专题：概率模式识别。模式识别专题：结构模式识别机器学习（1）：机械,解释经验,事例,归纳,概念,类比学习等；统计,结构,模糊模式识别。专题讲座（3次）1)神经网络基本理论和应用(史奎凡课程：安排于人工智能理论与应用课程内)；2)智能体（Agent）；3)自然语言处理；4)智能控制和机器人科学智能控制的结构理论和研究领域，智能控制系统及应用示例；机器人规划、机器视觉和自然语言理解等。AboutTeachingPlan实践：1)搜索技术和策略2)不确定
39、推理技术3)专家系统：动物识别系统4)模式识别技术5)调研：搜索技术和策略、不确定推理技术、统计模式识别、机器学习等四个领域进展报告。ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（人工智能（ArtificialIntelligence,AI）是当前科学技发展的一门前是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。现的新兴学科以及正在发展的学科。它是在它是在计算机科学，控制论，信息论，神经
40、心理学，哲学，语言学计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门等多种学科研究的基础发展起来的，因此又可把它看作是一门综综合性的边缘学科合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三世纪的三大科学技术成就。大科学技术成就。Intelligence智能是知识与智力的总合。智能是知识与智力的总合。知识知识智能行为的基础；智能行为的基础；智力智力获取
41、知识并运用知识求解问题的能力。获取知识并运用知识求解问题的能力。智能具有以下特征：智能具有以下特征：(1)具有感知能力具有感知能力指人们通过视觉、听觉、触觉、味觉、嗅觉等感指人们通过视觉、听觉、触觉、味觉、嗅觉等感觉器官感知外部世界的能力；觉器官感知外部世界的能力；(2)具有记忆与思维的能力具有记忆与思维的能力这是人脑最重要的功能，亦是人之所以有这是人脑最重要的功能，亦是人之所以有智能的根本原因；智能的根本原因；(3)具有学习能力及自适应能力；具有学习能力及自适应能力；(4)具有行为能力。具有行为能力。ArtificialIntelligence人工智能人工智能计算机科学的一个分支，是智能计算
42、机系统，即人类智慧计算机科学的一个分支，是智能计算机系统，即人类智慧在机器上的模拟，或者说是人们使机器具有类似于人的智慧（在机器上的模拟，或者说是人们使机器具有类似于人的智慧（对语言对语言能理解、能学习、能推理）。能理解、能学习、能推理）。2.BriefHistoryofAI(1)孕育（孕育（1956年前）年前）古希腊的古希腊的Aristotle（亚里士多德）（前亚里士多德）（前384-322），给出了形式逻辑的），给出了形式逻辑的基本规律。基本规律。英国的哲学家、自然科学家英国的哲学家、自然科学家Bacon（培根）（培根）（1561-1626），系统地给），系统地给 出了归纳法。出了归纳法。
43、“知识就是力量知识就是力量”德国数学家、哲学家德国数学家、哲学家Leibnitz（布莱尼茨）（布莱尼茨）（1646-1716）。提出了关于）。提出了关于数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和推理。做出了能做四则运算的手摇计算机推理。做出了能做四则运算的手摇计算机英国数学家、逻辑学家英国数学家、逻辑学家Boole（布尔）（布尔）（1815-1864）实现了布莱尼茨）实现了布莱尼茨 的思维符号化和数学化的思想，提出了一种崭新的代数系统的思维符号化和数学化的思想，提出了一种崭新的代数系统布尔布尔代数。代数。美籍奥地利数
44、理逻辑学家美籍奥地利数理逻辑学家Godel（哥德尔）（哥德尔）（1906-1978），证明），证明了一阶谓词的完备性定；任何包含初等数论的形式系统，如果它了一阶谓词的完备性定；任何包含初等数论的形式系统，如果它是无矛盾的，那么一定是不完备的。意义在于，人的思维形式化是无矛盾的，那么一定是不完备的。意义在于，人的思维形式化和机械化的某种极限，在理论上证明了有些事是做不到的。和机械化的某种极限，在理论上证明了有些事是做不到的。英国数学家英国数学家Turing(图灵图灵)（1912-1954）,1936年提出了一种理想年提出了一种理想计算机的数学模型（图灵机），计算机的数学模型（图灵机），1950年
45、提出了图灵试验，发表了年提出了图灵试验，发表了“计算机与智能计算机与智能”的论文。图灵奖。的论文。图灵奖。美国数学家美国数学家Mauchly，1946发明了电子数字计算机发明了电子数字计算机ENIAC美国神经生理学家美国神经生理学家McCulloch，建立了第一个神经网络数学模型。建立了第一个神经网络数学模型。美国数学家美国数学家Shannon（香农）香农）,1948年发表了通讯的数学理论，年发表了通讯的数学理论，代表了代表了“信息论信息论”的诞生。的诞生。(2)形成（形成（1956-19691956-1969）1956年提出了年提出了“Artificial Intelligence（人工智能
46、）人工智能）”1956年年夏夏由由麻麻省省理理工工学学院院的的J.McCarthy、M.L.Minsky,IBM公公司司信信息息研研究究中中心心的的 N.Rochester,贝贝尔尔实实验验室室的的 C.E.Shannon共共同同发发起起，邀邀请请了了 Moore,Samuel,Selfridge,Solomonff,Simon,Newell等等人人，10位位数数学学家家、信信息息学学家家、心心理理学学家家、神神经经生生理理学学家家、计计算算机机科科学学家家，在在Dartmouth大大学学召召开开了了一一次次关关于于机机器器智智能能的的研研讨讨会会，会会上上 McCarthy 提提议议正正式式
47、采采用用了了 Artificial Intelligence（人人工工智智能能）这这一一术术语语。这这次次会会议议，标标志志着着人人工工智能作为一门新兴学科正式诞生了。智能作为一门新兴学科正式诞生了。McCarthy（麦卡锡）麦卡锡）人工智能之父人工智能之父。这次会议之后的这次会议之后的10年间，人工智能的研究取得了许多引人瞩目的成就年间，人工智能的研究取得了许多引人瞩目的成就.机器学习方面：机器学习方面：塞缪尔于塞缪尔于1956年研制出了跳棋程序，该程序能从棋谱年研制出了跳棋程序，该程序能从棋谱中学习，也能从下棋实践中提高棋艺；中学习，也能从下棋实践中提高棋艺；在定理证明方面：王浩于在定理证
48、明方面：王浩于1958年在年在IBM机上证明了数学原理中有关机上证明了数学原理中有关命题演算的全部定理（命题演算的全部定理（220条），还证明了谓词演算中条），还证明了谓词演算中150条定理条定理85%；1965年，鲁宾逊（年，鲁宾逊（Robinson）提出了消解原理；提出了消解原理；在模式识别方面：在模式识别方面：1959年塞尔夫里奇推出了一个模式识别程序；年塞尔夫里奇推出了一个模式识别程序；1965年年罗伯特（罗伯特（Robert）编制出可辨别积木构造的程序；编制出可辨别积木构造的程序；在问题求解方面：在问题求解方面：1960年纽厄尔等人通过心理学试验总结出了人们求解年纽厄尔等人通过心理学
49、试验总结出了人们求解问题的思维规律，编制了通用问题求解程序问题的思维规律，编制了通用问题求解程序GPS,可以用来求解可以用来求解11种不同种不同类型的问题；类型的问题；在专家系统方面：斯坦福大学的费根鲍姆（在专家系统方面：斯坦福大学的费根鲍姆（E.A.Feigenbaum）自自1965年年开始进行专家系统开始进行专家系统DENDRAL（化学分析专家系统），化学分析专家系统），1968年完成并投年完成并投入使用；入使用；在人工智能语言方面：在人工智能语言方面：1960年年McCarthy等人建立了人工智能程序设计等人建立了人工智能程序设计语言语言Lisp，该语言至今仍是建造智能系统的重要工具；该
50、语言至今仍是建造智能系统的重要工具；1969年成立了国际人工智能联合会议（年成立了国际人工智能联合会议（International Joint Conferences On Artificial Intelligence）(3)发展（发展（1970年以后）年以后）70年代，开始从理论走向实践，解决一些实际问题。同时很快就发现问年代，开始从理论走向实践，解决一些实际问题。同时很快就发现问题：归结法费时、下棋赢不了全国冠军、机器翻译一团糟。题：归结法费时、下棋赢不了全国冠军、机器翻译一团糟。以以Feigenbaum为首的一批年轻科学家改变了战略思想，为首的一批年轻科学家改变了战略思想，1977年提