人工智能第六章2014ppt课件.ppt

《人工智能第六章2014ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第六章2014ppt课件.ppt（127页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、8/5/20221第六章第六章 归结原理归结原理6.1 子句集的子句集的Herbrand域域 一、一、 Herbrand域与域与 Herbrand解释解释l定义（定义（Herbrand域）设域）设S为子句集，令为子句集，令H0是出现于是出现于子句集子句集S的常量符号集。如果的常量符号集。如果S中无常量符号出现，中无常量符号出现，则则H0由一个常量符号由一个常量符号a组成。组成。 对于对于i1，2，令，令 Hi = Hi-1 所有形如所有形如f(t1，tn)的项的项 其中其中f(t1，tn)是出现在是出现在S中的所有中的所有n元函数符号，元函数符号， tj Hi-1，j1，n 称称Hi为为S的的

2、i级常量集，级常量集，H 称为称为S的的Herbrand域，域， 简称简称S的的H域。域。8/5/20222l例例 SP(f(x)，a，g(y)，b) H0 =a, b H1 =a, b, f(a), f(b), g(a), g(b) H2a, b, f(a), f(b), g(a), g(b), f(f(a), f(f(b), f(g(a), f(g(b), g(f(a), g(f(b), g(g(a), g(g(b) 8/5/20223练习练习: 求S的Herbrand域lSP(x) Q(y)，R(z) lSQ(a) P(f(x)， Q(b) P(g(x,y) 8/5/20224原子集原子

3、集 基例基例l基：把对象中的变量用常量代替后得到的无变量符号出现的对象。基：把对象中的变量用常量代替后得到的无变量符号出现的对象。 基项、基项集、基原子、基原子集合、基文字、基子句、基项、基项集、基原子、基原子集合、基文字、基子句、基子句集基子句集 l定义定义 (原子集、原子集、Herbrand底底) 设设S是子句集，形是子句集，形如如P(t1,tn)的基原子集合，称为的基原子集合，称为S的的Herbrand底底或或S的原子集的原子集 其中其中P(x1，xn)是出现于是出现于S的所有的所有n元谓词符号，元谓词符号，t1，tn是是S的的H域中的元素域中的元素l定义（基例）定义（基例） 设设S是子

4、句集，是子句集，C是是S中的一个子中的一个子句用句用S的的H域中元素代替域中元素代替C中所有变量所得到的中所有变量所得到的基子句称为子句基子句称为子句C的基例。的基例。8/5/20225练习练习l已知已知SP(f(x)，a，g(y)，b)，求，求S的原子集，的原子集， 给给出出P(f(x)，a，g(y)，b)的一个基例。的一个基例。l已知已知SP(x) Q(y)，R(z) ，求求S的原子集，的原子集， 分别给分别给出出P(x) Q(y)， R(z)的所有基例。的所有基例。l已知已知S Q(a) P(f(x)，Q(b) P(g(x,y)， 求求S的的原子集，原子集， 分别给出分别给出Q(a) P

5、(f(x) ， Q(b) P(g(x,y)的一个基例。的一个基例。l设设SP(x), Q(f(y) R(y) ，求，求S的的H域，域， S的原子集，的原子集， P(x)的基例的基例, Q(f(y) R(y) 的基例。的基例。8/5/20226H解释解释定义（子句集的定义（子句集的H解释）解释） 设设S是子句集，是子句集，H是是S的的H域，域，I*是是S在在H上上的一个解释称的一个解释称I*为为S的一个的一个H解释，如果解释，如果I*满足如下条件：满足如下条件： 1） I*映射映射S中的所有常量符号到自身。中的所有常量符号到自身。 2）若）若f是是S中中n元函数符号，元函数符号，h1，hn是是H

6、中元素，则中元素，则I*指定映射：指定映射： (h1，hn) f (h1，hn) 设设A=A1，A2，An， 是是S的原子集。于是的原子集。于是S的一个的一个H解释解释I可方便地表示为如下一个集合：可方便地表示为如下一个集合： I* m1，m2，mn，其中其中, mi =,T i1,2,. ,FiiiiAAIAAI当 被 指定为当 被 指定为8/5/20227H解释的例子例例 S=P(x)Q(x), R(f(y) S的H域=a, f(a), f(f(a), S的原子集： A=P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), S的H解释： I1* = P(a),

7、 Q(a), R(a), P(f(a), Q(f(a), R(f(a), I2* = P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), 8/5/20228练习练习S=P(x)Q(x), P(a), Q(b) ，求S的所有H解释。8/5/20229二、二、Herbrand解释与普通解释的关系解释与普通解释的关系l子句集子句集S的的H解释是解释是S的普通解释。的普通解释。lS的普通解释不一定是的普通解释不一定是S的的H解释：普通解释不解释：普通解释不是必须定义在是必须定义在H域上，即使定义在域上，即使定义在H域上，也域上，也不一定是一个不一定是一个H解释。解释。l

8、任取普通解释任取普通解释I，依照，依照I，可以按如下方法构造，可以按如下方法构造S的一个的一个H解释解释I*，使得若，使得若 S在在 I下为真则下为真则 S在在I*下也为真。下也为真。 8/5/202210例.SP(x), Q(y,f(y,a)令令S的一个解释的一个解释I如下：如下： D1，2 a f(1, 1) f(1, 2) f(2, 1) f(2, 2) 2 1 2 2 1 P(1) P(2) Q(1, 1) Q(1, 2) Q(2, 1) Q(2, 2) T F F T F T对应于对应于I的的H解释解释I*： I*P(a), Q(a, a), P(f(a, a), Q(a, f(a,

9、 a), Q(f(a, a), a), Q(f(a, a), f(a, a), 8/5/202211例例S=P(x), Q(y, f(y, z)令令S的一个解释的一个解释I如下如下: D=1, 2 f(1, 1) f(1, 2) f(2, 1) f(2, 2) 1 2 2 1 P(1) P(2) Q(1, 1) Q(1, 2) Q(2, 1) Q(2, 2) T F F T F T指定指定 a对应对应1得得H解释：解释：I1*P(a), Q(a, a), P(f(a, a), Q(a, f(a, a), Q(f(a, a), a), Q(f(a, a), f(a, a), 指定指定 a对应对应

10、2得得H解释：解释： I2*P(a), Q(a, a), P(f(a, a), Q(a, f(a, a), Q(f(a, a), a), Q(f(a, a), f(a, a), 8/5/202212对应于对应于I的的H解释解释I*定义（对应于定义（对应于I的的H解释解释I*） 设I是子句集S在区域D上的解释。H是S的H域。l 是如下递归定义的H到D的映射： 1） 若S中有常量符号,H0是出现在S中所有常量符号的集合。 对任意aH0，规定 (a)=I(a) 若S中无常量符号,H0=a。 规定 (a)=d,dD。 2）对任意(h1,hn)Hin,及S中任意n元函数符号f(x1,xn) , 规定(f

11、(h1，hn) =I(f(h1，hn) 。8/5/202213对应于对应于I的的H解释解释I*l对应于对应于I的的H解释解释I*是如下的一个是如下的一个H解释：解释： 任取任取S中中n元谓词符号元谓词符号P(x1,xn)， 任取任取(h1,hn) Hn，规定，规定 TI*(P(h1，hn)=TI(P(h1 ，hn ) 8/5/202214引理引理 如果某区域如果某区域D上的解释上的解释I满足子句集满足子句集S， 则对应于则对应于I的任意一个的任意一个H解释解释I*也满足也满足S。证明：证明：令令S= x1 xn (C1 Cm)，其中，其中Ci为子句为子句（i=1, ,m）。由已知）。由已知TI

12、(S)=T，即，即对任意（对任意（x1，xn） Dn，都有，都有TI(Ci（x1，xn）)=T, i=1, ,m8/5/202215因为对因为对S中任意中任意r元谓词符号元谓词符号P（x1，xr）和任意（）和任意（h1，hr） Hr，都有，都有TI*( P（h1，hr）)=TI(P（h1 ，hr ）)其中（其中（h1 ，hr ） Dr。所以，对任意（所以，对任意（h1，hn） Hn，都有，都有TI*( Ci（h1，hn）)=TI(Ci（h1 ，hn ）) 其中（其中（h1 ，hn ） Dn。 i=1, ,m。 故对任意（故对任意（h1，hn） Hn ，都有，都有 TI*(Ci（h1，hn）)=

13、T, 故故TI*(S)=T，即，即I*满足满足S。8/5/202216只考虑子句集的只考虑子句集的H解释是否够用？解释是否够用？定理定理 子句集子句集S恒假当且仅当恒假当且仅当S被其所有被其所有H解释弄假。解释弄假。证明证明: 必要性显然。必要性显然。充分性。假设充分性。假设S被其所有被其所有H解释弄假，而解释弄假，而S又是可满足的。又是可满足的。设解释设解释I满足满足S，于是由引理知，对应于，于是由引理知，对应于I的的H解释解释I*也满也满足足S，矛盾故，矛盾故S是不可满足的是不可满足的从现在起，如不特别指出，提到的解释都是指从现在起，如不特别指出，提到的解释都是指H解释解释 8/5/202

14、217结论结论l）子句）子句 C的基例的基例 C被解释被解释 I满足，当且仅当满足，当且仅当 C中的一个基文字中的一个基文字L出现在出现在 I中中C= P(x) Q(f(y),a) R(z)C= P(a) Q(f(a),a) R(f(a)8/5/2022182）子句）子句C被解释被解释I满足，当且仅当满足，当且仅当 C的每一个基例都被的每一个基例都被I满足满足3）子句）子句 C被解释被解释 I弄假，当且仅当弄假，当且仅当 至少有一个至少有一个C的基例的基例C被被I弄假。弄假。8/5/202219例例.C=P(x) Q(f(x)I1=P(a),Q(a),P(f(a),Q(f(a),P(f(f(a

15、),Q(f(f(a),I2=P(a),Q(a),P(f(a),Q(f(a),P(f(f(a),Q(f(f(a),I3=P(a),Q(a),P(f(a),Q(f(a),P(f(f(a),Q(f(f(a), 显然，显然，I1，I2满足满足C，I3弄假弄假C。 8/5/2022204）子句集）子句集S不可满足，当且仅当不可满足，当且仅当 对每个解释对每个解释I，至少有一个，至少有一个S中某个子句中某个子句C的的基例基例C被被I弄假。弄假。8/5/2022216.2 Herbrand定理定理 Herbrand定理是符号逻辑中一个很重要的定理Herbrand定理就是使用语义树的方法，把需要考虑无穷个H解

16、释的问题，变成只考虑有限个解释的问题8/5/202222一、语义树l定义定义(互补对互补对) 设设 A是原子，两个文字是原子，两个文字A和和A都是另一个的补，集合都是另一个的补，集合A，A称为一个互称为一个互补对补对l定义定义(Tautology,重言式重言式) 含有互补对的子句含有互补对的子句8/5/202223l定义定义 （语义树）（语义树） 设设S是子句集，是子句集，A是是S的原子集关于的原子集关于S的语义树是一棵向下生长的树的语义树是一棵向下生长的树T在树的每一节上都以如下在树的每一节上都以如下方式附着方式附着A中有限个原子或原子的否定：中有限个原子或原子的否定： 1）对于树中每一个节

17、点）对于树中每一个节点N，只能向下引出有限的直接的节，只能向下引出有限的直接的节 L1，Ln 设设Qi是附着在是附着在Li上所有文字的合取，上所有文字的合取，i=1, ,n， 则则Q1 Qn是一个恒真的命题公式是一个恒真的命题公式2）对树中每一个节点）对树中每一个节点 N，设，设 I（N）是树）是树T由根向下到节点由根向下到节点 N 的所有节上附着文字的并集，的所有节上附着文字的并集， 则则I（N）不含任何互补对）不含任何互补对语义树8/5/202224完全语义树定义（完全语义树）定义（完全语义树） 设设A=A1,An,是子句集是子句集S的原子集的原子集 S的一个语义树是完全的，当且仅当的一个

18、语义树是完全的，当且仅当 对于语义树中每一个尖端节点对于语义树中每一个尖端节点N（即从（即从N不再不再 生出节的那种节点），都有生出节的那种节点），都有 Ai或或Ai有且仅有一个属于有且仅有一个属于I(N),i=1,k,8/5/202225例例. 设A=P，Q，R是子句集S的原子集，完全语义树完全语义树(正规完全语义树正规完全语义树 )RRRRRRRRQQQQPP8/5/202226Q,RRRQQRRRRRRPPRQP,QQP8/5/202227例. 设设 S=P(x), Q(f(x)S的原子集为A=P(a), Q(a), P(f(a), Q(f(a), P(f(f(a), Q(f(f(a),

19、 P(a)P(a)Q(a)Q(a)P(f(a)Q(a)Q(a)P(f(a)Q(f(a)Q(f(a)8/5/202228语义树与解释语义树与解释lS的完全语义树的每一个分枝都对应着的完全语义树的每一个分枝都对应着S的一个解释；的一个解释；定义（部分解释）定义（部分解释）对于子句集对于子句集S的语义树中的每一个节点的语义树中的每一个节点N,I(N)是是S的某个解释的子集，称的某个解释的子集，称I(N)为为S的部分解释。的部分解释。lS的任意解释都对应着的任意解释都对应着S的完全语义树中的一条分枝？的完全语义树中的一条分枝？综合：综合： 子句集子句集S的一棵完全语义树对应着的一棵完全语义树对应着S的

20、所有解释。的所有解释。8/5/202229证明证明: 若不然，设若不然，设T中节点中节点N向下生出的向下生出的n个节个节L1，Ln的每个节的每个节Li上，都至少有一个文字上，都至少有一个文字Ai不在不在I中中由语义树的定义知：由语义树的定义知：Q1 Qn是恒真公式是恒真公式,其中其中Qi表示表示Li上所有文字的合取，上所有文字的合取，i=1, , n。将。将Q1 Qn化为合取范式：化为合取范式：Q1 Qn（A1 A2 An） () ()因为每一个析取式中都必须有一个互补对。不妨设因为每一个析取式中都必须有一个互补对。不妨设A1A2,于是于是A2,A2都不在都不在I中中,这与这与I是一个解释矛盾

21、。是一个解释矛盾。结论：对结论：对S的任意解释的任意解释I，都可以从，都可以从S的完全语义树的根点出的完全语义树的根点出发，向下找出一条分枝，使该分枝对应着解释发，向下找出一条分枝，使该分枝对应着解释I。引理引理 设设T是子句集是子句集S的完全语义树，的完全语义树，I是是S的一个解的一个解释。于是释。于是T中任意节点向下生出的直接节中，必中任意节点向下生出的直接节中，必有一节，其上所有文字都在有一节，其上所有文字都在I中。中。8/5/202230子句集的封闭语义树子句集的封闭语义树l定义（失效点）定义（失效点） 称语义树称语义树T中的节点中的节点N为失效为失效点，如果点，如果(1)I(N)弄假

22、弄假S中某个子句的某个基例；中某个子句的某个基例；(2)I(N)不弄假不弄假S中任意子句的任意基例，其中中任意子句的任意基例，其中N是是 N的任意祖先节点。的任意祖先节点。l定义（封闭语义树）定义（封闭语义树） 语义树语义树T是封闭的，当是封闭的，当且仅当且仅当T的每的每个分枝的终点都是失效点。个分枝的终点都是失效点。l定义（推理点）定义（推理点）称封闭语义树的节点称封闭语义树的节点 N为推理为推理点，如果点，如果N的所有直接下降节点都是失效点的所有直接下降节点都是失效点8/5/202231例例. 设设S=P, P R, P Q, P R。S的原子集 A=P, Q, RPPQQQQRRRRRR

23、RRPPQQRR8/5/202232练习练习l设子句集S=P(x)Q(x),P(f(x), Q(f(x)分别画出S的完全语义树与 封闭语义树。8/5/202233二、二、Herbrand定理定理Herbrand定理定理I子句集S是不可满足的，当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树证明证明: 必要性：若S是不可满足的，设T是S的完全语义树 对T的每一个分枝B,令IB是附着在B上所有文字的集合，则IB是S的一个解释,故IB弄假S中某子句C的某个基例C由于C是有限的，所以B上存在一个节点NB使得部分解释I（NB）弄假C，于是分枝B上存在失效点因此，对T中每一分枝都存在一个失效点

24、，于是从T得到S的一个封闭语义树T。8/5/202234Herbrand定理定理I子句集S是不可满足的，当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树(有限性) 因为封闭语义树T中每一个节点只能向下生长有限个节,故T必有有限个节点.否则,由Konig无限性引理,T中必有一条无穷的分枝,此无穷分枝上当然没有失效点,矛盾。（Konig无限性引理：在一个其点之次数有限的无限有向树中，必有一源于根的无限路。 ）充分性：若S的每一个完全语义树T都对应着一个有限封闭语义树T，则T的每条分枝上都有一个失效点。因为S的任一解释都对应T的某一条分枝，所以每一个解释都弄假S， 故S是不可满足的。8/

25、5/202235Herbrand定理定理II 子句集S是不可满足的，当且仅当存在S的一个有限不可满足的S的基例集S。证明证明: 必要性：必要性：若若S恒假，设恒假，设T是是S的完全语义树，由的完全语义树，由Herbrand定理定理I知，有一个有限封闭知，有一个有限封闭语义树语义树 T对应着对应着T。令令S是被是被 T中所有失效点弄假的所中所有失效点弄假的所有有基例（基例（S中某些子句的基例）的集合。中某些子句的基例）的集合。因为因为T中失效点的个数有限，所以中失效点的个数有限，所以S是有限集合。是有限集合。任取任取S的一解释的一解释I，则，则I是是S的某个解的某个解释释I的子集，而解释的子集，

26、而解释I是是T中一个分中一个分枝，所以，枝，所以，I弄假弄假S中子句中子句C，故，故I弄假弄假S。因为。因为I I,且且I是是S的解释的解释,故故I弄假弄假S由由I的任意性知的任意性知S不可满不可满足。足。 S=P(x), P(a)P(b), Q(f(x)H=a,b,f(a),f(b),f(f(a),f(f(b),A=P(a),P(b),Q(a),Q(b),S=P(a), P(b), P(a)P(b)8/5/202236Herbrand定理定理II 子句集S是不可满足的，当且仅当存在S的一个有限不可满足的S的基例集S。充分性：充分性：假设假设S有一个有限的不可满足的基例集有一个有限的不可满足的

27、基例集S。 任取任取S的解释的解释I， 因为因为S的每一个解释的每一个解释I都包含着都包含着S的一个解释的一个解释I，而而S是不可满足的，所以是不可满足的，所以S的任一解释的任一解释I都弄假都弄假S，故，故I弄假弄假S中至少一个子句，即中至少一个子句，即I弄假弄假S中至中至少一个子句的基例，亦即少一个子句的基例，亦即I弄假弄假S。 由由I的任意性，知的任意性，知S是不可满足的。是不可满足的。8/5/202237 Herbrand定理II提出了一种证明子句集S的不可满足性的方法：如果存在这样一个机械程序，它可以逐次生成S中子句的基例集 S0，Sn，并逐次地检查S0，Sn，的不可满足性，那么根据

28、Herbrand定理，如果 S是不可满足的，则这个程序一定可以找到一个有限数N，使SN是不可满足的。 8/5/202238使用使用Herbrand定理的机器证明过程定理的机器证明过程lGilmore过程lD-P过程8/5/202239Gilmore过程（过程（1960年）年）l逐次地生成逐次地生成S0， S1，Sn，其中，其中Si是用是用S的的i级常量集合级常量集合Hi中的常量，代替中的常量，代替S中子句的变量，中子句的变量，而得到的而得到的S的所有基例之集合。的所有基例之集合。l对于每一个对于每一个Si，可以使用命题逻辑中的任意的，可以使用命题逻辑中的任意的方法去检查方法去检查Si的不可满足

29、性。的不可满足性。 Gilmore使用了所谓乘法方法：即将使用了所谓乘法方法：即将Si化为析取化为析取范式。如果其中任意一个合取项包含一个互补范式。如果其中任意一个合取项包含一个互补对，则可以删除这个合取项，最后，如果某个对，则可以删除这个合取项，最后，如果某个Si是空的，则是空的，则Si是不可满足的。是不可满足的。l当当S不可满足时，该算法一定结束不可满足时，该算法一定结束(半可判定半可判定)。8/5/202240例例. S=P(a), P(x) Q(f(x), Q(f(a) H0=a S0=P(a) (P(a) Q(f(a) Q(f(a) =(P(a)P(a)Q(f(a)(P(a) Q(f

30、(a)Q(f(a) = =所以，S是不可满足的。l该算法具有指数复杂性，为此提出了改进规则，称为该算法具有指数复杂性，为此提出了改进规则，称为Davis-Putnam预处理预处理-检验基子句集不可满足性。检验基子句集不可满足性。8/5/202241D-P过程过程设设S是基子句集是基子句集lTautology删除规则删除规则 设设S为删去为删去S中所有的中所有的Tautology所剩子句集，所剩子句集， 则则 S恒假恒假 iff S恒假。恒假。 8/5/202242l单文字规则单文字规则 若若S中有一个单元基子句中有一个单元基子句L，令令S为删除为删除S中包含中包含L的所有基子句所剩子句集，的所

31、有基子句所剩子句集，则：则：(1) 若若S为空集，则为空集，则S可满足。可满足。(2) 否则，否则， 令令S为删除为删除S中所有文字中所有文字L所得子句集所得子句集 （若（若S 中有单元基子句中有单元基子句L，则删文字，则删文字L 得空子句），得空子句）， 于是，于是， S恒假恒假 iff S恒假。恒假。S=L(LC1) (LCi) (LCi+1) (LCj) Cj+1 Cn8/5/202243定义（纯文字）：称定义（纯文字）：称S的基子句中文字的基子句中文字L是纯的，如果是纯的，如果L不出现在不出现在S中。中。l纯文字规则纯文字规则设设L是是S中纯文字，且中纯文字，且S为删除为删除S中所有包

32、含中所有包含L的基子句所的基子句所剩子句集，则剩子句集，则(1)若若S为空集，则为空集，则S可满足。可满足。(2) 否则，否则，S恒假恒假 iff S恒假。恒假。S=(LC1) (LCi) Ci+1 Cn8/5/202244l分裂规则分裂规则若若S=(A1 L) (Am L) (B1 L) (Bn L) R 其中其中A i , Bi ,R都不含都不含L或或L，令，令 S1 =A1 Am RS2= B1 Bn R 则则S恒假恒假 iff S1 ， S2同时恒假。同时恒假。 8/5/202245Davis-Putnam方法练习方法练习lS= (P Q R) (P Q) P R UlS= (P Q)

33、 (P Q) (Q R) (Q R) lS= (P Q) (P Q) (R Q) (R Q) 8/5/202246Herbrand定理的主要障碍定理的主要障碍l要求生成关于子句集要求生成关于子句集S的基例集的基例集 S1, S2, 。在多数情。在多数情况下，这些集合的元数是以指数方式增加的：况下，这些集合的元数是以指数方式增加的：例例.S=P(x,g(x),y,h(x,y),z,k(x,y,z),P(u,v,e(v),w,f(v,w),x) H0=a H1=a, g(a), h(a, a), k(a, a, a), e(a), f(a, a) S0=P(a,g(a),a,h(a,a),a,k(

34、a,a,a),P(a,a,e(a),a,f(a,a),a) S1=(6 6 6)+(6 6 6 6)=216+1296=1512个元素个元素 S5是不可满足的，但是是不可满足的，但是H5是是1065数量级个元素，而数量级个元素，而S5有有10260数量级的元素。想将数量级的元素。想将S5存储起来都是不可能的，存储起来都是不可能的，更不要说是检查它的不可满足性了。更不要说是检查它的不可满足性了。8/5/202247l为了避免像Herbrand定理所要求的那样去生成子句的基例集，J.A.Robinson于1965年提出了归结原理，归结原理可以直接应用到任意子句集S上（不一定是基子句集），去检查S的

35、不可满足性。l归结原理的本质思想是去检查子句集S是否包含一个空子句: 如果S包含，则S是不可满足的。 如果S不包含，则去检查是否可由S推导出来。 当然这个推理规则必须保证推出的子句是原亲本子句的逻辑结果。归结原理就是具有这种性质的一种推理规则。 归结原理思想归结原理思想8/5/202248命题逻辑中的归结原理命题逻辑中的归结原理8/5/202249归结式归结式l定义（定义（归结式） 对任意两个基子句C1和C2。如果C1中存在文字L1，C2中存在文字L2，且L1L2， 则从C1和C2中分别删除L1和L2，将C1和C2的剩余部分析取起来构成的子句，称为C1和C2的归结式，记为R(C1, C2)。

36、C1和C2称为亲本子句。8/5/202250练习练习:求下述各子句对的归结式求下述各子句对的归结式 lC1= PQR, C2=QSlC1= PQR, C2=P RQ8/5/202251定理定理 设C1和C2是两个基子句， R(C1, C2) 是C1，C2的归结式，则R(C1, C2)是C1和C2的逻辑结果。证明：证明： 设 C1=L C1, C2=LC2。于是 R(C1, C2) C1 C2 设I是C1和C2的一个解释，且满足C1也满足C2。因为L和L中有一个在I下为假，不妨设为L。于是C1非空，且在I下为真。故R(C1, C2)在I下为真。 命题逻辑归结方法的可靠性命题逻辑归结方法的可靠性8

37、/5/202252归结演绎归结演绎l定义（归结演绎）定义（归结演绎） 设设S是子句集。从是子句集。从S推出子句推出子句C的一个归的一个归结演绎是如下一个有限子句序列：结演绎是如下一个有限子句序列： C1，C2，Ck其中其中Ci或者是或者是S中子句，或者是中子句，或者是Cj和和Cr的归结式的归结式 (j i, r i)；并且并且CkC。 称从子句集称从子句集S演绎出子句演绎出子句C，是指存在一个从，是指存在一个从S推出推出C的演绎。的演绎。l定理定理 若从子句集若从子句集S可以演绎出子句可以演绎出子句C，则，则C是是S的逻辑结果。的逻辑结果。l推论推论 若子句集若子句集S是可满足的，是可满足的，

38、 则则S推出的任意子句也是可满足的。推出的任意子句也是可满足的。 8/5/202253定义定义 从从S推出空子句的演绎称为一个推出空子句的演绎称为一个反驳（反驳（反反证证） ，或称为，或称为S的一个证明。的一个证明。结论结论：若从基子句集：若从基子句集S可演绎出空子句，则可演绎出空子句，则S是是不可满足的。不可满足的。演绎树：演绎树：从子句集从子句集S出发，通过归结原理可得到出发，通过归结原理可得到一个向下的演绎树，其每个初始节点上附着一一个向下的演绎树，其每个初始节点上附着一个个S中子句，每个非初始节点上附着一个其前中子句，每个非初始节点上附着一个其前任节点上子句的归结式。任节点上子句的归结

39、式。8/5/202254例. S=P Q, P Q, P Q, P Q 归结演绎： (1) PQ (2) PQ (3) PQ (4) PQ (5) Q 由(1)、(2) (6) Q 由(3)、(4) (7) 由(5)、(6)8/5/202255归结原理归结原理一般过程一般过程:1)建立子句集S。2)如果S含空子句，则结束。3)从子句集S出发,仅对S的子句间使用归结推理规则。4)如果得出空子句，则结束。5)将所得归结式仍放入S中。6)对新的子句集使用归结推理规则。转4)。8/5/202256例例.证明证明(P Q) Q p首先建立子句集:S=PQ, Q , P归结演绎:(1) P Q(2) Q(

40、3) P(4) P (1)(2)归结(5) (3)(4)归结8/5/202257命题逻辑归结原理的完备性命题逻辑归结原理的完备性l定理 如果基子句集如果基子句集S是不可满足的，是不可满足的， 则存在从则存在从S推出空子句的归结演绎。推出空子句的归结演绎。证明： 设M是S的原子集，对M的元素数|M|用归纳法。 当|M|=1时，设原子为P。 若S ，得证。 否则，因为S是不可满足的，于是，S中必包含单元子句P和P，而P和P的归结式是，所以存在从S推出的归结演绎。 假设|M|n (n2) 时，定理成立。往证 |M|n时定理成立。 8/5/202258取取M中任意一原子中任意一原子P，做如下两个子句集

41、：，做如下两个子句集：S：将将S中所有含中所有含P的子句删除，然后在剩下的子的子句删除，然后在剩下的子 句中删除文字句中删除文字P；S”：将：将S中所有含中所有含P的子句删除，然后在剩下的的子句删除，然后在剩下的 子句中删除文字子句中删除文字P。显然，显然，S和和S”都不可满足，且它们的原子集的元都不可满足，且它们的原子集的元素数都小于素数都小于n。根据归纳假设，存在从。根据归纳假设，存在从S推出推出 的的归结演绎归结演绎D1，从，从S”推出推出的归结演绎的归结演绎D2。8/5/202259lS=PC1, ,PCi , PCi+1, ,PCj, Cj+1 , , CnS=Ci+1, ,Cj,C

42、j+1 , , CnS=C1, ,Ci , Cj+1 , , Cnl例：S=P Q, P Q, P R, RM=P,Q,R8/5/202260 在在D1中，将中，将S中所有不是中所有不是S中的子句，通过中的子句，通过添加文字添加文字P而恢复成而恢复成S中子句，于是，得到从中子句，于是，得到从S推出推出 或者或者P的归结演绎的归结演绎D1。 用同样方法从用同样方法从D2可得一个从可得一个从S推出推出 或者或者P的的归结演绎归结演绎D2。 显然，从显然，从D1和和D2就不难得到一个从就不难得到一个从S推出推出 的的归结演绎归结演绎D。归纳法完成。归纳法完成。8/5/202261Resolution

43、 Principle 两种译法：归结原理：从内部看 刘叙华，一种新的语义归结原理，吉林大学学报，1978。消解原理：从外部看 马希文，机器证明及其应用，计算机应用， 1978。8/5/2022626.3 合一算法合一算法8/5/202263例例1 C1：P(x) Q(y) C2：P(a) R(z)例例2 C1：P(x) Q(x) C2：P(f(x) R(x)l替换和合一是为了处理谓词逻辑中子句之间的模式匹配而引进.8/5/202264一、替换与最一般合一替换一、替换与最一般合一替换l定义定义(替换替换)一个替换是形如一个替换是形如t1/v1, , tn/vn 的一个有限集合，其中的一个有限集合

44、，其中vi是变量符号，是变量符号，ti是不是不同于同于vi的项。并且在此集合中没有在斜线符的项。并且在此集合中没有在斜线符号后面有相同变量符号的两个元素，称号后面有相同变量符号的两个元素，称ti为为替换的分子，替换的分子，vi为替换的分母。为替换的分母。例例. a/x, g(y)/y, f(g(b)/z是是替换替换; x/x, y/f(x), a/x, g(y)/y, f(g(b)/y不是不是替换替换;基替换基替换:当当t1,tn是基项时，称此替换为基替换。是基项时，称此替换为基替换。空替换：空替换：没有元素的替换称为空替换，记为没有元素的替换称为空替换，记为 。8/5/202265替换定义（

45、改名）定义（改名） 设替换设替换 = t1/x1, , tn/xn 如果如果t1, , tn是不同的变量符号，则称是不同的变量符号，则称 为一个改为一个改名替换，简称改名。名替换，简称改名。替换作用对象：替换作用对象：表达式表达式（项、项集、原子、原子集、（项、项集、原子、原子集、 文字、子句、子句集）文字、子句、子句集）基表达式：基表达式：没有变量符号的表达式。没有变量符号的表达式。子表达式：子表达式：出现在表达式出现在表达式E中的表达式称为中的表达式称为E的子的子 表达式。表达式。8/5/202266E的例l 定义（定义（E的例）的例） 设设 = t1/v1, , tn/vn 是一个是一个

46、替换，替换，E是一个表达式。将是一个表达式。将E中出现的每一个中出现的每一个变量符号，变量符号，vi (1 i n) ，都用项，都用项ti替换，这样替换，这样得到的表达式记为得到的表达式记为E 。称。称E 为为E的例。的例。 若若E 不含变量，则不含变量，则E 为为E的基例。的基例。例例. 令令 = a/x, f(b)/y, c/z，E=P(x, y, z)于是于是E的例（也是的例（也是E的基例）为的基例）为 E = P(a, f(b), c)8/5/202267练习：l E=P(x, g(y), h(x,z), =a/x, f(b)/y, g(w)/zE=P(a, g(f(b), h(a,g

47、(w)l E=P(x, y, z), =y/x, z/y E=P(y, z, z). EP(z, z, z). 8/5/202268替换的乘积替换的乘积 l定义（替换的乘积）定义（替换的乘积）设设 = t1/x1, , tn/xn ， = u1/y1, , um/ym 是两个替换。将下面集合是两个替换。将下面集合 t1 /x1, , tn /xn , u1/y1, , um/ym 中任意符合下面条件的元素删除：中任意符合下面条件的元素删除： 1）ui/yi，当，当yi x1, , xn 时；时； 2）ti /xi，当，当ti = xi 时。时。如此得到一个替换，称为如此得到一个替换，称为 与与

48、 的乘积，记为的乘积，记为 。l例例. 令令 =f(y)/x, z/y =a/x, b/y, y/z 于是得集合于是得集合 t1 /x1, t2 /x2 , u1/y1, u2/y2 , u3/y3 = f(b)/x, y/y, a/x, b/y, y/z 与与 的乘积为的乘积为 = f(b)/x, y/z 8/5/202269=a/x, =b/x =a/x =b/x可见： 8/5/202270 例子例子: E=P(x, y, z) =a/x, f(z)/y, w/z E =P(a, f(z), w) =t/z, g(b)/w (E ) =P(a, f(t), g(b) =a/x, f(t)/

49、y, g(b)/z,g(b)/w E=P(a, f(t), g(b)8/5/202271引理引理 若若E是表达式，是表达式， ， 是两个替换，是两个替换， 则则E ( ) = (E ) 证明：证明： 设设vi是是E中任意一个变量符号，而中任意一个变量符号，而 = t1/x1, , tn/xn ， = u1/y1, , um/ym l若若vi既不在既不在 x1, , xn 中，也不在中，也不在 y1, , ym 中，则中，则vi在在E ( )中和在中和在(E ) 中都不变。中都不变。l若若vi=xj (1 j n)，则，则E中的中的vi，在，在(E ) 中先变成中先变成tj，然后，然后再变成再变

50、成tj ；E中的中的vi在在E()中立即就变成了中立即就变成了tj 。故。故E中中vi在在(E ) 中和在中和在E()中有相同变化。中有相同变化。l若若vi=yj (1 j m)，且，且yj x1,xn ，则，则E中中vi在在(E ) 中中变为变为uj;E中中vi在在E()中也变为中也变为uj(注意注意:yj x1, xn，所，所以以uj/yj），故），故E中中vi在在(E ) 中和在中和在E ()中有相同变中有相同变化。化。 由于由于vi的任意性，故引理得证。的任意性，故引理得证。 8/5/202272引理引理 设设 ， ， 是三个替换，是三个替换， 于是于是() ()证明：证明： 设设E是