谓词演算的推理理论

1、第四章 谓词演算的推理理论4.1 谓词演算的永真推理系统谓词演算的永真推理系统4.2谓词演算的假设推理系统谓词演算的假设推理系统4.3谓词演算的归结推理系统谓词演算的归结推理系统 4.3.1 置换置换 4.2.2 归结反演系统归结反演系统 4.3.3 霍恩子句逻辑程序霍恩子句逻辑程序4.3 谓词演算的归结推理系统谓词演算的归结推理系统问题：从公式集问题：从公式集S出发，证明目标公式出发，证明目标公式T。在归结系统中在归结系统中:l 首先首先否定目标公式否定目标公式，l 然后将这个公式加到公式集然后将这个公式加到公式集S中，中，l 再将该公式化成子句集，再将该公式化成子句集，l 若能归结成空子句

2、若能归结成空子句(用表示用表示)，则认为证明了该公式则认为证明了该公式T。引例(p45)设有语句串及它的符号表示如下：设有语句串及它的符号表示如下：(1)(1)无论谁能读就有知识；无论谁能读就有知识； x x(R(x(R(x) ) L(xL(x)(2)(2)所有的海豚均没有知识；所有的海豚均没有知识； x x(H(x(H(x) ) L L(x(x)(3)(3)有些海豚有智慧。有些海豚有智慧。 x x(H(x)(H(x) I I(x(x)从这些语句出发，证明语句：从这些语句出发，证明语句：(4)(4)一些有智慧的个体不能读。一些有智慧的个体不能读。 x x(I(x)(I(x)R R(x(x)引例

3、 (p45，提取子句)对应语句对应语句(1)至至(3)的子句集为：的子句集为：(1) R(x1) L(x1)(2) H(x2) L(x2)(3) H(a)(4) I(a)其中子句其中子句(3)(4)为对为对(3)式式SKOLEM化而得，化而得，a为为SKOLEM常量。常量。要证明的定理的否定式为：要证明的定理的否定式为： x(I(x)R(x), 即即 x( I(x) R(x)化为子句形式为化为子句形式为(5)：(5) I(x3) R(x3)引例 (p45，归结)(1) R(x1) L(x1)(2) H(x2) L(x2)(3) H(a)(4) I(a)(5) I(x3) R(x3)(6) R(

4、a) a/ x3(4)(5)归结归结(7) L(a) a/ x1(6)(1)归结归结(8) H(a) a/ x2(7)(2)归结归结(9) (8)(3)归结归结注意：归结时使用了未讨论过的注意：归结时使用了未讨论过的置换置换的概念。的概念。4.3.1 置换置换项对变量的替换。项对变量的替换。置换准则为：置换准则为：(1)置换必须处处进行。置换必须处处进行。(2)要求没有变量被含有同一变量的项来代替。要求没有变量被含有同一变量的项来代替。 如表达式如表达式P(x,g(x),b)中的中的x不能用含有不能用含有x的的项项f(x)来置换，即来置换，即P(f(x),g(f(x),b)是错误的是错误的置换

5、。置换。例例 已知表达式已知表达式 P(x，g(y)，b)，考察置换，考察置换: P(x，g(a)，b) a/y P(a，g(b)，b) a/x，b/y P(f(y)，g(a)，b) f(y)/x，a/y 一般地，置换可通过有序对的集合一般地，置换可通过有序对的集合t1/v1，t2/v2，tn/vn来表达，其中来表达，其中ti/vi表示变量表示变量vi处处以项处处以项ti来代替来代替。4.3.2 归结反演系统归结反演系统一、谓词演算公式子句的形成一、谓词演算公式子句的形成二、一般归结一般归结三、归结反演算系统的应用三、归结反演算系统的应用一、谓词演算公式子句的形成一、谓词演算公式子句的形成一般

6、步骤一般步骤:(1)消去蕴含词和等价词消去蕴含词和等价词(2)否定深入否定深入(3)约束变元改名约束变元改名(4)化为前束范式化为前束范式(5)消去存在量词消去存在量词(按按Skolem标准形标准形)(6)消去全称量词消去全称量词(直接去掉直接去掉)(7)化为合取范式化为合取范式(8)消去合取词得子句集消去合取词得子句集，(9)改变变量的名称改变变量的名称 (变量符号不重复使用变量符号不重复使用)例例(p46-47) xP(x)x(A(x)y(B(y) W(x，y)解解:(1)消去蕴含词消去蕴含词 xP(x)x( A(x)y(B(y) W(x，y)(2)约束变元改名约束变元改名： 利用改名方法

7、对上式施行改名，以保证每一个量词利用改名方法对上式施行改名，以保证每一个量词约束的变元不同名。约束的变元不同名。 xP(x)z( A(z)y(B(y) W(z，y)(3)化为前束范式化为前束范式 x z y(P(x) ( A(z) (B(y) W(z，y)(4)消去存在量词消去存在量词(按按Skolem标准形标准形) 原式原式z(P(a) ( A(z) (B(f(z) W(z，f(z)例例 (p47)(5)消去全称量词消去全称量词(直接去掉直接去掉) 原式原式 P(a) ( A(z) (B(f(z) W(z，f(z)(6)利用分配律化为合取范式利用分配律化为合取范式 原式原式 P(a) ( A

8、(z) B(f(z) ( A(z) W(z，f(z)(7)消去合取词得子句集消去合取词得子句集 此时公式中只含有一些文字的析取此时公式中只含有一些文字的析取 P(a), A(z) B(f(z), A(z) W(z，f(z)(8)改变变量的名称改变变量的名称： 改名使得每个变量符号不出现在一个以上的子句中改名使得每个变量符号不出现在一个以上的子句中 P(a), A(z1) B(f(z1), A(z2) W(z2，f(z2)二、一般归结只需寻找一个置换，把它们作用到母体子句上只需寻找一个置换，把它们作用到母体子句上使它们含有互补的文字对使它们含有互补的文字对(如如P和和 P) 。例例 设有设有 P

9、(x，g(a) Q(y) P(z，g(a)Q(z) 可得归结式如下：可得归结式如下： Q(y) Q(z) z/x Q(y) Q(x) x/z P(x，g(a)P(z，g(a) z/y 归结反演系统归结反演系统产生式系统产生式系统l 子句集看作为一个综合数据库，子句集看作为一个综合数据库，l 而规则表就是归结，表中的规则用到数据库中的而规则表就是归结，表中的规则用到数据库中的子句对，产生一个新的子句，把新子句加入数据子句对，产生一个新的子句，把新子句加入数据库中产生新的数据库，形成新的归结，重复此过库中产生新的数据库，形成新的归结，重复此过程，观察数据库中是否含有空子句。程，观察数据库中是否含有

10、空子句。 例例 (p47)已知知识：已知知识： (1)每个作家均写过作品；每个作家均写过作品； (2)有些作家没写过小说；有些作家没写过小说；结论：有些作品不是小说。结论：有些作品不是小说。证明：令证明：令 A(e)表示表示“e为作家为作家”； B(e)表示表示“e为作品为作品”； N(e)表示表示“e为小说为小说”； W(e1，e2)表示表示“e1 写了写了 e2” 知识可以符号化如下：知识可以符号化如下： (1) x(A(x)y(B(y) W(x，y) (2) x(A(x)y(N(y)W(x，y)例例 (p47, 求子句求子句) (1) x(A(x)y(B(y) W(x，y) = x( A

11、(x) y(B(y) W(x，y) = x y ( A(x) (B(y) W(x，y) x ( A(x) (B(f(x) W(x，f(x) A(x) (B(f(x) W(x，f(x) = ( A(x) B(f(x) ( A(x) W(x，f(x) 得到子句：得到子句： A(x1) B(f(x1)， A(x2) W(x2，f(x2) 例例 (p47,续续)(2) x(A(x)y(N(y)W(x，y) = x(A(x)y( N(y) W(x，y) = x y (A(x) ( N(y) W(x，y) y (A(a) ( N(y) W(a，y) A(a) ( N(y) W(a，y)得到子句：得到子句：

12、 A(a), N(y) W(a，y)例例 (p47,续续) 要证明的结论为：有些作品不是小说。要证明的结论为：有些作品不是小说。 x(B(x)N(x) 否定结论得到：否定结论得到： x(B(x)N(x) = x( B(x) N(x) B(x) N(x) 得到子句：得到子句： B(x) N(x)例例 (p47, 归结归结)(1) A(x1) B(f(x1)(2) A(x2) W(x2，f(x2)(3) A(a)(4) N(y)W(a，y)(5) B(x) N(x)(6) A(x1) N(f(x1) f(x1)/x (5)(1)归结归结(7) N(f(a) a/x1 (6)(3)归结归结(8) W

13、(a，f(a) f(a)/y (7)(4)归结归结 (9) A(a) a/x2 (8)(2)归结归结(10) 口口 (9)(3)归结归结补充习题任何人如果喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车，或者喜欢骑自行车；有的人不喜欢骑自行车，因而有的人不爱步行。试用归结原理证明之。证明：令证明：令 P(e)表示表示“e为人为人”； W(e)表示表示“e喜欢步行喜欢步行”； D(e)表示表示“e喜欢乘汽车喜欢乘汽车”； R(e)表示表示“e喜欢骑自行车喜欢骑自行车”证明(续)则已知知识可以翻译为：则已知知识可以翻译为：（1） x(P(x) (W(x) D(x)（2） x(P(x) (D(x)

14、R(x)（3） x(P(x) R(x) 结论为：结论为： x(P(x) W(x) )结论的否定为：结论的否定为： x( P(x) W(x)证明证明(续续)(1) P(x1)W(x1) D(x1)(2) P(x2) D(x2) R(x2)(3) P(a)(4) R(a)(5) P(x) W(x)(6) W(a) D(a) a/x1 (3)(1)归结归结(7) P(a) D(a) a/x2 (4)(2)归结归结(8) P(a) D(a) a/y (5)(6)归结归结 (9) P(a) (8)(7)归结归结(10) 口口 (9)(3)归结归结例例 用归结方法证明下列公式用归结方法证明下列公式 x(P

15、(f(x)(P(f(a) P(x)证证: 目标的否定为目标的否定为 x(P(f(x)(P(f(a) P(x) = x (P(f(x)(P(f(a) P(x) = x (P(f(x) ( P(f(a) P(x) 子句集为子句集为 (1) P(f(x1) (2) P(f(a) P(x2) (3) P(x2) a/x1 (1)(2)归结归结 (4)口口 f(x1)/x2(1)(3)归结归结直观解释: 显然，如果存在x, 使得P(f(x)为假，则公式为真。反之，如果对于任意t, P(f(t)皆为真，则取x=f(t)即可。三、归结反演算系统的应用在人工智能领域中的规划生成问题。在人工智能领域中的规划生成

16、问题。例例(p48)给机器人给机器人r 编制一程序，使它能够登编制一程序，使它能够登上一只椅子上一只椅子c以取下挂在房顶的香蕉以取下挂在房顶的香蕉b。4.3.3 霍恩子句逻辑程序霍恩子句逻辑程序一、子句的蕴含表示形式二、霍恩子句逻辑程序超逻辑的控制信息超逻辑的控制信息许多人工智能系统中使用的知识是由一般的蕴许多人工智能系统中使用的知识是由一般的蕴含表达式来表示的。如果把蕴含式含表达式来表示的。如果把蕴含式(P Q)R化为等价的析取式化为等价的析取式 P Q R ，往往会丢失可能包含在蕴含式中的重要的往往会丢失可能包含在蕴含式中的重要的超逻超逻辑的控制辑的控制信息。信息。基于规则的演绎系统将知识

17、分为两类：将知识分为两类：l一类是规则，其由蕴含式表示，它表达了有关领一类是规则，其由蕴含式表示，它表达了有关领域的一般知识，且可作为产生式规则来使用；域的一般知识，且可作为产生式规则来使用；l另一类是事实，其由不包含蕴含式的陈述组成，另一类是事实，其由不包含蕴含式的陈述组成，它们用来表达某一领域专门的知识。它们用来表达某一领域专门的知识。基于规则的演绎系统基于规则的演绎系统(产生式系统产生式系统)根据这些事根据这些事实和规则来证明目标公式，这种推理强调使用规则实和规则来证明目标公式，这种推理强调使用规则进行演绎，直观易于理解。进行演绎，直观易于理解。正向演绎系统、逆向演绎系统事实表达式目标表

18、达式推理事实表达式目标表达式推理关于规则的约定约定作为规则的一些公式限制为如下形式的公式：约定作为规则的一些公式限制为如下形式的公式： W WL L这些产生式规则和事实应满足下列条件：这些产生式规则和事实应满足下列条件：(1)(1)L L是是单文字单文字（原子公式或原子公式的否定）原子公式或原子公式的否定）， 事实上即使事实上即使L L不是单文字，也可把该蕴含式化为多重规不是单文字，也可把该蕴含式化为多重规则。则。 如：如：W W(L1(L1 L2)L2)等价于规则对等价于规则对W WL1L1和和W WL2L2；(2)W(2)W是任一公式是任一公式( (假设是与或形公式假设是与或形公式, ,本

19、书限为合取式本书限为合取式) )。一、子句的蕴含表示形式一个子句是若干文字的析取，一般地，一个子句是若干文字的析取，一般地， C = C = P P1 1P P2 2 P Pn n Q Q1 1 Q Q2 2 Q Qm m其中，其中，PiPi和和QiQi为谓词，变元被省略。为谓词，变元被省略。可以表示为：可以表示为： (P(P1 1 P P2 2 P Pn n) )(Q(Q1 1 Q Q2 2 Q Qm m) )如果约定蕴含前件的文字之间恒为合取，而蕴含后件的如果约定蕴含前件的文字之间恒为合取，而蕴含后件的文字之间恒为析取，那么上式可改写为如下形式：文字之间恒为析取，那么上式可改写为如下形式：

20、 P P1 1，P P2 2，P Pn nQ Q1 1，Q Q2 2，Q Qm m子句的性质 (1) Q1(1) Q1，Q2Q2，QmQm，等价于，等价于Q1Q1 Q2Q2 QmQm； 而而 P1P1，P2P2，PnPn等价于等价于 P1P1P2P2 PnPn。 当当m=n=0m=n=0时，表示空子句。时，表示空子句。(2)(2)当子句当子句C C： Q1Q1，Q2Q2，QmQm P1 P1，P2P2，PnPn 和子句和子句C C ： Q1 Q1 ，Q2 Q2 ，Qs Qs P1 P1 ，P2 P2 ，Pt Pt 中有中有QiQi和和PjPj ，( (或或PiPi和和QjQj ) )相同，则相

21、同，则C C和和C C 可进行归结可进行归结。(3)(3)要证明定理要证明定理 A1A1 A2A2 AnAnB B， 只要将只要将 A1A1 A2A2 AnAnB B 化为子句集，并证明其不可满足，即用以上方式归结出空子句。化为子句集，并证明其不可满足，即用以上方式归结出空子句。二、霍恩子句逻辑程序 定义定义1：子句：子句 L1 L2 Ln 中，如果至多只含有一个正文字，那么该子句称中，如果至多只含有一个正文字，那么该子句称为霍恩子句。为霍恩子句。 霍恩子句霍恩子句PQ1Q2 Qn通常表示为：通常表示为： PQ1，Q2，Qn霍恩子句必为下列四种形式之一：霍恩子句必为下列四种形式之一：(1)PQ

22、1，Q2，Qn n 0(2)P n=0(3)Q1，Q2，Qn n 0(4)口口(空子句空子句) 上式上式n=0(1) P Q1，Q2，Qn n 0 (2) P n=0(3) Q1，Q2，Qn n 0(4) 口口 上式上式n=0形如形如PQ1，Q2，Qn的霍恩子句称为一个的霍恩子句称为一个过程过程，P称为过程名，称为过程名，Q1，Q2，Qn称为过程体，称为过程体，诸诸Qi解释为解释为过程调用过程调用；形如形如P的霍恩子句称为一个的霍恩子句称为一个事实事实；形如形如Q1，Q2，Qn的霍恩子句称为的霍恩子句称为目标目标，目标，目标全部由全部由过程调用过程调用所组成，常用来表示一个询问。所组成，常用来

23、表示一个询问。形如口形如口(空子句空子句)称为称为停机语句停机语句，表示执行成功。，表示执行成功。霍恩子句逻辑霍恩子句逻辑定义定义2：霍恩子句逻辑就是由：霍恩子句逻辑就是由霍恩子句霍恩子句构成的构成的一阶谓词演算系统的子系统。一阶谓词演算系统的子系统。定义定义3：霍恩子句逻辑程序就是指由被称为过：霍恩子句逻辑程序就是指由被称为过程、事实和目标的霍恩子句程、事实和目标的霍恩子句所组成所组成的的集合。集合。霍恩霍恩逻辑程序的执行算法逻辑程序的执行算法(1) 给定一个霍恩子句逻辑程序，它由目标中的一个给定一个霍恩子句逻辑程序，它由目标中的一个过过程调用程调用与事实或与一个过程的过程名匹配启动，当与事

24、实或与一个过程的过程名匹配启动，当匹配成功后，匹配成功后，形成新的目标形成新的目标，完成一次匹配。，完成一次匹配。(2) 再由目标中的另一个再由目标中的另一个过程调用过程调用重新启动程序，直至重新启动程序，直至目标中全部过程调用匹配成功目标中全部过程调用匹配成功(即即归结为空子句归结为空子句)，或者某一过程调用不能与事实或过程名相匹配。或者某一过程调用不能与事实或过程名相匹配。两个霍恩子句的归结是一个霍恩子句。在自动定理证明中，两个霍恩子句的归结是一个霍恩子句。在自动定理证明中，这能导致子句的在计算机上表示得更加高效。实际上，这能导致子句的在计算机上表示得更加高效。实际上，Prolog 就是完

25、全在霍恩子句上构造的编程语言。就是完全在霍恩子句上构造的编程语言。 例例 已知前提已知前提 (1) TOM在何处，在何处， MARY在何处在何处 (2) MARY在何处，她的在何处，她的COMPUTER在何处在何处 (3) TOM在图书馆在图书馆 询问询问“MARY的的COMPUTER是否在图书馆？是否在图书馆？”。 试给出它的证明程序。试给出它的证明程序。解：霍恩子句为解：霍恩子句为 (1) At(MARY,x) At(TOM,x) 过程过程 (2) At(COMPUTER,y) At(MARY,y) 过程过程 (3) At(TOM, Library) 事实事实 (4) At(COMPUTE

26、R, Library) 目标目标例例 MARY的的COMPUTER是否在图书馆？是否在图书馆？解：霍恩子句逻辑程序为解：霍恩子句逻辑程序为 (1) At(MARY,x) At(TOM,x) 过程过程 (2) At(COMPUTER,y) At(MARY,y) 过程过程 (3) At(TOM, Library) 事实事实 (4) At(COMPUTER, Library) 目标目标 (5) At(MARY, Library) Library/y (2)(4)匹配匹配 (6) At(TOM, Library) ) Library/x (1)(5)匹配匹配 (7) 口口 (3)(6)匹配匹配 此程序

27、证明了此程序证明了MARY的的COMPUTER在图书馆。在图书馆。例 所有羊都吃草所有羊都吃草,所有死羊都不吃草所有死羊都不吃草. 所以所以,所有死羊都不是羊所有死羊都不是羊.解解: 知识翻译为知识翻译为 x(羊羊(x) 吃草吃草(x) x(死羊死羊(x) 吃草吃草(x) x(死羊死羊(x) 羊羊(x), 其否定为其否定为 x(死羊死羊(x) 羊羊(x) 霍恩子句逻辑程序及执行过程如下：霍恩子句逻辑程序及执行过程如下： (1) 吃草吃草(x)羊羊(x) 过程过程 (2) 死羊死羊(x1), 吃草吃草(x1) 目标目标 (3) 死羊死羊(a) 事实事实 (4) 羊羊(a) 事实事实 (5) 死羊

28、死羊(x), 羊羊(x) x/x1(2)(1)归结归结 (6) 羊羊(a) a/x(5)(3)归结归结 (7) 口口 (6)(4)归结归结例例 (原题原题p44) 已知知识：已知知识： (1)有些病人喜欢所有的医生；有些病人喜欢所有的医生； (2)所有的病人均不喜欢庸医；所有的病人均不喜欢庸医；试证明结论：所有的医生均不是庸医。试证明结论：所有的医生均不是庸医。证明：已知知识翻译为：证明：已知知识翻译为： (1) x(P(x)y(D(y)L(x，y) (2) x(P(x)y(Q(y) L(x，y) 结论翻译为：结论翻译为： x(D(x) Q(x)结论的否定为结论的否定为: x(D(x) Q(x

29、)霍恩子句逻辑程序及执行过程如下：霍恩子句逻辑程序及执行过程如下：(1) P(a) 事实事实(2) L(a,y) D(y) 过程过程(3) P(x1), Q(y1), L(x1,y1） 目标目标(4) D(b) 事实事实(5) Q(b) 事实事实(6) Q(y1), L(a，y1) a/x1(3)(1)归结归结(7) Q(y)， D(y) y/y1(6)(2)归结归结(8) Q(b) b/y(7)(4)归结归结(9) 口口 (8)(5)归结归结例例 (p50-51) 已知知识：已知知识： (1)桌子上的每一本书均是杰作；桌子上的每一本书均是杰作； (2)写出杰作的人是天才；写出杰作的人是天才；

30、 (3)某个不出名的人写了桌上某本书；某个不出名的人写了桌上某本书； 结论：某个不出名的人是天才。结论：某个不出名的人是天才。解：令解：令 A(e)表示表示“e为桌上的书为桌上的书”； B(e)表示表示“e为杰作为杰作”； C(e)表示表示“e为天才为天才”； D(e)表示表示“e出名出名”； P(e)表示表示“e为人为人”； W(e1，e2)表示表示“e1 写了写了 e2”.例例 (续，续，p51)(1) x(A(x)B(x)(2) x y(P(x) B(y) W(x，y)C(x) (P(x) B(y) W(x，y)C(x)(3) x y(P(x) A(y) D(x) W(x，y) P(a)

31、 A(b) D(a) W(a，b)结论：结论： x(P(x) D(x) C(x)否定结论得到否定结论得到 x(P(xx(P(x) ) D(xD(x) ) C(xC(x) = = x ( x ( P(xP(x) ) D(xD(x) ) C(xC(x)解：解：(7)D(x3)(7)D(x3) P(x3) P(x3)，C(x3) C(x3) 过程过程 (8)(8) P(aP(a) )，C(aC(a) ) a/x3(5)(7)a/x3(5)(7)归结归结(9)(9) C(aC(a) ) (8)(3)(8)(3)归结归结(10)(10) P(a),B(yP(a),B(y), ), W(aW(a，y) y

32、) a/x2(9)(2)a/x2(9)(2)归结归结(11)(11) B(yB(y) )， W(aW(a，y) y) (10)(3)(10)(3)归结归结(12)(12) A(yA(y) )，W(aW(a，y) y) y/x1(11)(1)y/x1(11)(1)归结归结(13)(13) W(aW(a，b) b) b/y(12)(4)b/y(12)(4)归结归结(14)(14)口口 (13)(6)(13)(6)归结归结(1)B(x1)(1)B(x1)A A(x1) (x1) 过程过程(2)C(x2)(2)C(x2) P P(x2)(x2)，B(yB(y) )， W(x2W(x2，y) y) 过程

33、过程(3)P(a)(3)P(a) 事实事实(4)A(b)(4)A(b) 事实事实(5)(5) D D(a(a) ) 目标目标(6)W(a(6)W(a，b)b) 事实事实例例 已知知识如下：已知知识如下： (1)每个程序员均写过程序；每个程序员均写过程序； (2)病毒是一种程序病毒是一种程序 (3)有些程序员没写过病毒；有些程序员没写过病毒； 结论：有些程序不是病毒。结论：有些程序不是病毒。 试用霍恩子句逻辑程序证明之。试用霍恩子句逻辑程序证明之。证明：证明： 令令 P(e)表示表示 e为程序员；为程序员； A(e)表示表示 e为程序；为程序； B(e)表示表示 e为病毒；为病毒； W(e1,e2)表示表示 e1写了写了 e2.例例 证明（续）则已知知识可以翻译为：则已知知识可以翻译为：（1） x(P(x) y(A(y) W(x,y) x y (P(x) (A(y) W(x,y)（2）