第四章 确定性推理方法

第四章确定性推理方法第一页，共七十一页，编辑于2023年，星期五单调推理、非单调推理按照推理过程中推出的结论是否越来越接近最终目标来划分，推理又分为单调推理和非单调推理。单调推理是在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。非单调推理是在推理过程中有新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的一步，然后重新开始。（知识不完全情况下发生。）X是鸟，会飞，X是企鹅，不会飞。第二页，共七十一页，编辑于2023年，星期五命题逻辑命题：能判断真假的陈述句为命题。命题公式：单个常量或变量的命题称作合式公式。合式公式有限次组合所构成的字符串称为命题公式。命题逻辑的基本联接词有：~，，，，等价，当且仅当，双条件第三页，共七十一页，编辑于2023年，星期五命题公式的解释：设A为一个命题公式，P1P2P3,…,Pn是出现在A中的全部命题变量，给P1P2P3,…,Pn各指定一个真值（0或1），称为对A的一个赋值或解释。第四页，共七十一页，编辑于2023年，星期五公式的分类永真式：若A无成假赋值，则称A为重言式。或永真式。永假式可满足式：若A至少有一个成真赋值，则称A为可满足式。非重言式的可满足式：若A至少有一个成真赋值，又至少有一个成假赋值，则称A为非重言式的可满足式。第五页，共七十一页，编辑于2023年，星期五范式（公式的标准型式）简单合取式：仅由有限个命题变量或其否定构成的合取式成为简单合取式。简单析取式：仅由有限个命题变量或其否定构成的析取式称为简单析取式。合取范式：仅由有限个简单析取式构成的合取式称为合取范式。P(PQ)(~PQ)析取范式：仅由有限个简单合取式构成的析取式称为析取范式。P(PQ)(~PQ)析取范式是矛盾式，每个简单合取式都是矛盾式。合取范式是重言式，每个简单析取式都是重言式。第六页，共七十一页，编辑于2023年，星期五谓词逻辑是一种形式语言，具有严密的理论体系是一种常用的知识表示方法例：City（北京）City（上海）Age（张三，23）(x)(y)(z)(F(x,y)F(y,z)GF(x,z)第七页，共七十一页，编辑于2023年，星期五谓词逻辑原子谓词公式：是一个不能再分解的命题。原子谓词公式及其否定，统称为文字。P与~P为互补文字。任何文字的析取称为子句。由子句构成的集合成为子句集。不包含任何文字的子句称为空子句，表示为NIL。由于空子句不包含任何文字，不能被任何解释满足，所以，空子句是永假的，不可满足的。第八页，共七十一页，编辑于2023年，星期五4.1归结原理归结原理是一种定理证明方法，1965年由Robinson提出，从理论上解决了定理证明问题。子句集无量词约束元素只是文字的析取否定符只作用于单个文字元素间默认为和取例：{~I(z)R(z),I(A),~R(x)L(x),~D(y)}第九页，共七十一页，编辑于2023年，星期五谓词公式化子句集的方法例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消蕴涵符 理论根据：ab=>~abp

Q=>(PQ)(~P~Q) (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,移动否定符（把否定符移动到紧靠谓词的位置上） 理论根据：~(ab)=>~a~b ~(ab)=>~a~b ~(x)P(x)=>(x)~P(x) ~(x)P(x)=>(x)~P(x)

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}第十页，共七十一页，编辑于2023年，星期五化子句集的方法（续1）3,变量标准化 即：对于不同的约束，对应于不同的变量 (x)A(x)(x)B(x)=>(x)A(x)(y)B(y)4,量词左移

(x)A(x)(y)B(y)=>(x)(y){A(x)B(y)}5,消存在量词(skolem化） 原则：对于一个受存在量词约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，如果他受全程量词约束，则该变量用一个函数代替。

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}=>(x){[(~P(x)~Q(x))R(f(x))]U(a)}第十一页，共七十一页，编辑于2023年，星期五化子句集的方法（续2）6,化为合取范式 即(ab)(cd)(ef)的形式

(x){[(~P(x)~Q(x))R(f(x))]U(a)}=>(x){(~P(x)~Q(x))R(f(x))U(a)}=>(x){[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}7,隐去全程量词 {[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}第十二页，共七十一页，编辑于2023年，星期五化子句集的方法（续3）8,表示为子句集{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}9,变量标准化（变量换名）{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}第十三页，共七十一页，编辑于2023年，星期五化下列公式成子句形式：（1）(x)[P（x）→P（x）]（2）{~{(x)P（x）}}→(x)[~P（x）]第十四页，共七十一页，编辑于2023年，星期五化下列逻辑表达式为合取范式

化下列逻辑表达式为合取范式:

第十五页，共七十一页，编辑于2023年，星期五第十六页，共七十一页，编辑于2023年，星期五定理： 若S是合式公式F的子句集，则F永假的充要条件是S不可满足。S不可满足：若nilS，则S不可满足。证明的思路： 目标的否定连同已知条件一起，化为子句集，并给出一种变换的方法，使得S

S1S2...Sn，同时保证当Sn不可满足时，有S不可满足。

第十七页，共七十一页，编辑于2023年，星期五4.2归结方法（命题逻辑）设子句： C1=LC1’

C2=(~L)C2’ 则归结式C为： C=C1’C2’定理： 子句集S={C1,C2,…,Cn}与子句集 S1={C,C1,C2,…,Cn}的不可满足性是等价的。其中，C是C1和C2的归结式。第十八页，共七十一页，编辑于2023年，星期五证明归结式C是C1和C2的逻辑结论即C1C2→C(1)也就是要证明使C1和C2为真的解释I，也必然可以使C为真。C1=LC1’，C2=(~L)C2’(2)设I是使C1和C2为真的任一解释，若I下的L为真，从而~L为假。由C2为真的假设可以推出必有在I下的C2’为真，故在I下，由于C=C1’C2’，所以C也为真。若在解释I下L为假，从而由于假设C1为真，必有C1’为真，故在解释I下C=C1’

C2’也必为真。(3)归结式C是其亲本子句C1和C2的逻辑结论。第十九页，共七十一页，编辑于2023年，星期五推论：设C1和C2是子句集S上的子句，C是C1和C2的归结式。如果把C加入子句集S后得到新子句集S1，则S1和S在不可满足的意义下是等价的。S是不可满足的等价于S1是不可满足的第二十页，共七十一页，编辑于2023年，星期五归结推理过程：证明子句集S的不可满足性过程：（1）对子句集S中的各子句间使用归结推理规则。（2）将归结所得到的归结式放入子句集S中，得到新子句集S’。（3）检查子句集S’中是否有空子句(NIL)，若有，则停止推理，否则，转步骤（4）（4）置S=S’，转步骤（1）。第二十一页，共七十一页，编辑于2023年，星期五归结的例子设公理集： P, (PQ)R, (ST)Q, T求证：R子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目标求反）

化子句集： (PQ)R=>~(PQ)R=>~P~QR (ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ)=>{~SQ,~TQ}第二十二页，共七十一页，编辑于2023年，星期五子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目标求反）归结： (7)~P~Q(2,6) (8)~Q (1,7)(9)~T(4,8)(10)nil(5,9)第二十三页，共七十一页，编辑于2023年，星期五证明子句集S={~PQ,~Q,P}不可满足第二十四页，共七十一页，编辑于2023年，星期五4.3谓词逻辑的归结原理问题：如何找归结对 例：P(x)Q(y),~P(f(y))R(y)

P(A)Q(y),~P(f(y))R(y)基本概念置换s={t1/v1,t2/v2,…,tn/vn}(ti项，Vi是变量) 对公式E实施置换s后得到的公式称为E的例，记作Es。例：s1={z/x,A/y},则： P[x,f(y),B]s=P[z,f(A),B]第二十五页，共七十一页，编辑于2023年，星期五合一 如果存在一个S置换，使得{Ei}中 E1s=E2s=E3s=…=Ens，则称{Ei}是可合一的。S为{Ei}的合一者。例：{P(x,f(y),B),P(z,f(B),B)}置换s={A/x,B/y,A/z}是一个合一者,因为： P(x,f(y),B)s=P(A,f(B),B) P(z,f(B),B)s=P(A,f(B),B) 置换s={z/x,B/y}和置换s={x/z,B/y}也都是合一者。结论：合一者不唯一。第二十六页，共七十一页，编辑于2023年，星期五最一般合一者（mgu） 置换最少，限制最少，产生的例最具一般性。 如前面的例子： {P(x,f(y),B),P(z,f(B),B)} 对于置换{A/x,B/y,A/z}，产生的例是： P(A,f(B),B) 对于置换={z/x,B/y}，产生的例是： P(z,f(B),B)mgu也不是唯一的。第二十七页，共七十一页，编辑于2023年，星期五合一算法例：{P(x,x,Z),P(f(y),f(B),y)} 前缀表示： (Pxxz) (P(fy)(fB)y)

置换：{(fy)/x} (P(fy)(fy)z) (P(fy)(fB)y)

置换：{B/y},并使得{(fB)/x} (P(fB)(fB)z) (P(fB)(fB)B)

置换：{B/z} 得到置换：{(fB)/x，B/y，B/z} 置换后的结果：(P(fB)(fB)B)第二十八页，共七十一页，编辑于2023年，星期五谓词逻辑的归结方法对于子句C1L1和C2L2，如果L1与~L2可合一，且s是其合一者，则(C1C2)s是其归结式。例：P(x)Q(y),~P(f(z))R(z) =>Q(y)R(z)第二十九页，共七十一页，编辑于2023年，星期五归结举例设公理集： (x)(R(x)L(x)) (x)(D(x)~L(x)) (x)(D(x)I(x))求证：(x)(I(x)~R(x))化子句集：

(x)(R(x)L(x))=>(x)(~R(x)L(x))=>~R(x)L(x)(1)第三十页，共七十一页，编辑于2023年，星期五 (x)(D(x)~L(x))=>(x)(~D(x)~L(x))=>~D(x)~L(x)(2) (x)(D(x)I(x))=>D(A)I(A)=>D(A)(3) I(A)(4)第三十一页，共七十一页，编辑于2023年，星期五目标求反： ~(x)(I(x)~R(x))=>(x)~(I(x)~R(x))=>(x)(~I(x)R(x))=>~I(x)R(x)(5)换名后得字句集： ~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)第三十二页，共七十一页，编辑于2023年，星期五例题得归结树 ~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)I(A)

~I(x5)R(x5)

R(A){A/x5}

~R(x1)L(x1)

L(A){A/x1}~D(x2)~L(x2)~D(A){A/x2}D(A)nil第三十三页，共七十一页，编辑于2023年，星期五归结方法的特点是简单，易于程序实现。其不足是效率低，不直观，人难于理解其"证明"过程。第三十四页，共七十一页，编辑于2023年，星期五1、在命题逻辑下，可以归结的子句C1和C2，在某种模型下C1和C2为真。则其归结式C在该模型下（）A.必真B.必假

C.真假不能断言

第三十五页，共七十一页，编辑于2023年，星期五2、归结证明定理时，若当前归结式是（）,则可删除。A.永假式B.重言式C.空子句D.可满足式第三十六页，共七十一页，编辑于2023年，星期五3、什么是置换？{g(y)/z,f(z)/y}是一个置换么？置换是形如{t1/x1,t1/x2,…,tn/xn}的一个有限集。其中，xi是变量，ti是不同于xi的项（常量、变量、函数），且xi≠xj（i≠j），i,j=1,2,…,n。{g(y)/z,f(z)/y}不是一个置换，原因是它在x和y之间出现了循环置换现象。第三十七页，共七十一页，编辑于2023年，星期五应用归结原理进行问题求解（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设置的谓词，其变量必须与问题公式的变量完全一致。（3）把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S1合并构成子句集S。（4）对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一置换，改变ANSWER中的变元。（5）如果得到归结式ANSWER，问题的答案即在ANSWER中第三十八页，共七十一页，编辑于2023年，星期五例题:某单位招聘工作人员，张三、李四、王五三人应试，经面试后单位有如下的想法：（1）

如果录取张三而不录取李四，则一定录取王五。（2）

如果录取李四，则一定录取王五。（3）

三人中至少要录取一个人。求证：王五一定会被单位录取。（提示）定义谓词和常量：谓词Matr(x)表示x被录取。Z表示张三，L表示李四，W表示王五。第三十九页，共七十一页，编辑于2023年，星期五第四十页，共七十一页，编辑于2023年，星期五例题:任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？第一步：将已知条件用谓词表示出来，并化成字句集。那么，要先定义谓词。（1）定义谓词：设Father(x,y)表示x是y的父亲。设Brother(x,y)表示x和y是兄弟。第四十一页，共七十一页，编辑于2023年，星期五（2）将已知事实用谓词公式表示出来：F1:任何兄弟都有同一个父亲。

第四十二页，共七十一页，编辑于2023年，星期五第四十三页，共七十一页，编辑于2023年，星期五归结控制策略盲目归结策略，产生了大量的无用的归结式。研究以少量的归结尽快导出空子句。第四十四页，共七十一页，编辑于2023年，星期五归结的一般策略S={C1,C2,C3,C4}(1)C1开始，逐个和C2,C3,C4比较，看哪两个子句可以进行归结。C2与C3,C4进行比较，C3与C4比较。得到一组归结式，称为第一级归结式。(2)再从C1开始，用S中的子句分别与第一级归结式中的子句逐个进行比较、归结，得到第二级归结式。(3)仍然从C1开始，用S中的子句及第一级归结式中的子句逐个地与第二级归结式中的子句逐个进行比较，得到第三级归结式。如此继续下去，知道出现了空子句或者不能再继续归结时为止。只要子句集是不可满足的，上述归结过程一定会归结出空子句而终止。第四十五页，共七十一页，编辑于2023年，星期五S={P,~R,~PQ,~QR}S:(1)P(2)~R (3)~PQ (4)~QR(5)Q(1)(3)归结(6)~Q(2)(4)归结第一级归结式(7)~PR(3)(4)归结(8)R(1)(7)归结(9)~P(2)(7)归结第二级归结式(10)~P(3)(6)归结(11)R(4)(5)归结(13)NIL(1)(9)归结第三级归结式第四十六页，共七十一页，编辑于2023年，星期五控制策略的分类删除策略限制策略第四十七页，共七十一页，编辑于2023年，星期五删除策略删除某些无用的子句来缩小归结的范围，从而提高归结效率。包括：纯文字删除法、重言式删除法、包孕删除法。第四十八页，共七十一页，编辑于2023年，星期五限制策略主要是对参加归结的子句进行种种限制，尽可能地减小归结的盲目性。以使其尽快归结出空子句。控制策略包括：线性归结策略、单文字归结策略、输入归结策略、支撑集策略等。第四十九页，共七十一页，编辑于2023年，星期五删除策略之纯文字删除法如果某文字L在子句集中不存在可与之互补的文字~L，则称该文字为纯文字。纯文字不可能被消去，因而用包含它的子句进行归结时不可能得到空子句。这样的子句对归结是无意义的，所以可以把它所在的子句从子句集中删去。S={PQR,

~QR,Q,~R}P是纯文字，可将子句PQR从R中删除。第五十页，共七十一页，编辑于2023年，星期五删除策略之重言式删除法~P(X)P(X),~P(X)Q(X)P(X)都是重言式。重言式是真值为真的子句。不管P(X)为真还是为假，

~P(X)P(X)和~P(X)Q(X)P(X)结果都为真。对于一个子句集来说，不管是增加或者删去一个真值为真的子句都不会影响它的不可满足性。第五十一页，共七十一页，编辑于2023年，星期五删除策略之包孕删除法如果子句C1和C2，如果存在一个代换S,使得C1s包含于C2中，则称C1包孕于C2。P(x)包孕于P(y)Q(z)s={y/x}P(x)包孕于P(a)s={a/x}P(x)包孕于P(a)Q(z)s={a/x}P(x)Q(a)包孕于P(f(a))Q(a)R(y)s={f(a)/x}P(x)Q(y)包孕于P(a)Q(u)R(w)s={a/x,u/y}

把子句集中包孕的子句删去后，不会影响子句集的不可满足性，因而可以从子句集中删去。第五十二页，共七十一页，编辑于2023年，星期五支持集策略支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则称T是S的支撑集。采用支撑集策略时，选取不同时属于S-T的子句对，在其间进行归结。至少有一个子句来自于支撑集T或者由T导出的归结式。参加归结的子句有一个是目标公式的否定所得到的子句或者他们的后裔。思想：尽量避免在可满足的子句集中进行归结。第五十三页，共七十一页，编辑于2023年，星期五S={PQ,~PR,~QR,~R}取T={~R}支撑集归结过程通常为：PQ~PR~QR~R~P(2)(4)~Q(3)(4)Q(1)(5)P(1)(6)R(3)(7)Nil(4)(9)第五十四页，共七十一页，编辑于2023年，星期五线性归结策略线性归结策略首先从子句集中选取一个称作顶子句的C0开始进行归结。归结过程中所得到地归结式Ci立即同另一子句Bi进行归结，得归结式Ci+1，而Bi属于S或者已经出现得归结式Cj(j<i)。简而言之，每次归结得到的新子句立即参加归结，而后再加入子句集等待再次参加归结。第五十五页，共七十一页，编辑于2023年，星期五C0B0B1BnC1C2空较好的顶子句,就可以使归结顺利进行.第五十六页，共七十一页，编辑于2023年，星期五输入归结策略对参加归结的子句提出了如下限制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。初始子句集就是由已知前提及结论的否定化来的子句。可以避免归结出不必要的新子句加入归结而造成恶性循环，可以减少不必要地归结次数。原始子句集中没有单元子句一定不能采用输入归结策略。第五十七页，共七十一页，编辑于2023年，星期五~I(x)R(x)I(a)~R(y)~L(y)L(a)R(a)(1)(2)~I(x)~L(x)(1)(3)~R(a)(3)(4)~I(a)(1)(7)~L(a)(2)(6)~L(a)(3)(5)~I(a)(4)(6)NIL(2)(8)第五十八页，共七十一页，编辑于2023年，星期五~I(x)R(x)I(a)~R(y)~L(y)L(a)R(a)~I(x)~L(x)~R(a)~I(a)~L(a)~L(a)~I(a)NIL第五十九页，共七十一页，编辑于2023年，星期五输入归结策略可限制生成归结式的数量，具有简单、高效的优点。例如：S={P(x)Q(x),~P(y)Q(y),P(u)~Q(u),~P(t)~Q(t)}它是不可满足的，用输入归结策略却归结不出空子句。第六十页，共七十一页，编辑于2023年，星期五单文字子句策略如果一个子句只包含一个文字，则称它为单文字子句。单文字子句策略要求参加归结的两个子句中必须有一个单文字子句。第六十一页，共七十一页，编辑于2023年，星期五S:(1)~I(x)

R(x)(2)I(a)(3)~R(y)~L(y)(4)L(a)S1:(5)R(a)(1)(2)(6)~R(a)(3)(4)S2:(7)~I(a)(1)(6)(8)~L(a)(3)(5)S3:NIL(2)(7)第六十二页，共七十一页，编辑于2023年，星期五祖先过滤策略该策略与线性输入策略比较相似，但放宽了限制。当两个子句C1和C2进行归结时，只要它们满足下述两个条件中的任意一个就可以进行归结：（1）C1与C2中至少有一个是初始子句集中的子句。（2）如果两个子句都不是初始子句集中的子句，则一个应是另一个祖先（C2是由C1与别的子句归结后得到的归结式，C1是C2的祖先）第六十三页，共七十一页，编辑于2023年，星期五归结演绎推理

归结演绎推理比较简单又便于在计算机上实现。但是由于把逻辑公式化成子句集，带来如下问题：（1）不便于阅读与理解。(x)(Bird(x)Canfly(x))~Bird(x)Canfly(x)第六十四页，共七十一页，编辑于2023年，星期五（2）有可能丢失一些重要的控制信息(~A~B)C(~A~C)B(~B~C)A~A(BC)~B(AC)~C(AB)具有不同的逻辑控制信息，却得到相同的子句。第六十五页，共七十一页，编辑于2023年，星期五对子句集S={P(x)Q(x),~P(x)R(x),~Q(x)R(x),~R(x)}使用单文字归结策略对其进行归结推理。第六十六页，共七十一页，编辑于2023年，星期五解：单文字归结过程如下：(1)P(x)Q(x)(2)~P(x)VR(x)(3)~Q(x)