夏季防暑小常识-文明网向国旗敬礼

第三章 演绎推理

自动定理证明是人工智能一个重要的 研究领域，是早期取得较大成果的研
究课题之一，在发展人工智能方法上起过重大作用。
1956，美国，Newell, Simon, Shaw编制逻辑理论机：The Logic Theory
Machine 简称 LT. 证明了《数学原理》（罗素）第二章中38个定理, 改进
后证明了全部52个定理。是对人的思维活动 进行研究的重大成果，是人工智
能研究的真正开端。在此之后，发展了一些机械化推理算法，很成功地用 到
人工智能系统中。
个人收集整理 勿做商业用途

第一节 鲁滨逊归结原理

一、命题逻辑中归结推理
1.归结： 消去子句中互补对的过程：
子句： 任何文字的析取式C称为子句，C=P

Q

7R={P,Q,7R}
如：C1=LVC1`={L,C1`}
C2=7LVC2`={7L,C2`}
可以证明C12=C1`VC2`={C1`,C2`}是C1,C2的逻辑结论：
即：C1

C2C12
证明：C1=LVC1`=77C1`VL=7C1`L
C2=7LVC2`=LC2`
所以7C1`C2`=77C1`VC2`=C1`VC2`
实际上是PQ, Q  PPR的应用
即前提成立结论成立，也即结论不成立前提不成立

S子句集：其中有C1,C2归结式
S`子句集：C12代替C1,C2
则： S`不可满足S不可满足

2.归结推理步骤
要证AB成立(或证AB重言、永真)，
只要证A

7B不可满足(永假)
①化A

7B为合取范式C1

C2

… …

Cm
②子句集S={C1,C2,…, Cm}
③归结规则用于S，归结式入S中.
④重复③，直到S中出现空子句。

证明：SVR是P

Q , P R，QS的逻辑结论。
（P

Q)

(P R)

(QS)

7(S

R)
=（P

Q）

(7P

R)

(7Q

S)

7S

7R
1 7

所以S={P

Q,7P

R,7Q

S,7S,7R}

(1)P

Q
(2)7P

R
(3)7Q

S
(4)7S
(5)7R
(6)Q

R (1)(2) 归结
(7)7Q (3)(4) 归结
(8)Q (5)(6) 归结
(9)F (7)(8) 归结
命题逻辑 中不可满足的子句集S，使用归结原理，总能在有限步内得到一个空
子句归结原理是完备的。

二、谓词逻辑中的归结原理
谓词和子句中含有个体变元，同一谓词含有不同的个体变元。所以寻找互
补对更困难。
例：C1=P(y)

Q(y)
C2=7P(f(a))

R(a)

1. 置换
定义：形如{t1a1，t2a2，…，tnan}的有限集合，
表示ti代换ai，其中ti是项，变量，常量，函数。
ai是变量，且ti不同于ai。
置换的目的是使得S中有相同互补文字的子句中谓词各对应项变得一致，以
便于归结。
θ,,表示置换。
Fθ=G，则Fθ是F的逻辑推论。
例如，F={P(x, f(x),y), P(a,z,g(z))}
做置换1={ax}之后得:
G1=F1 ={P(a,f(a),y)， P(a,z,g(z))}
2 ={f(a)z}
G2=G12 ={P(a,f(a),y)， P(a, f(a),g(f(a)))}
3 ={g(f(a))y}
G3=G2 3 ={P(a,f(a),g(f(a))), P(a, f(a),g(f(a)))}
θ= 1 ·2·3={ax, f(a)z, g(f(a))y}是一个置换.

2.合一
定义：设有公式集F={F1, F2, …, Fn}，若存在一个置换θ，可使F1θ=F2
θ=…=Fnθ, 则称θ为F的合一置换。称F是可合一的。
个人收集整理 勿做商业用
途
如上面“置换”一节中的例子。
很明显，很多F是不可合一的，而且一个公式集合的合一置换不唯一（如
上例中， 2 ={ g(a)y}。
个人收集整理 勿做商业用途
2 7

定义：如果是公式集F的一个合一置换，且对F的任何一个合一θi，都
存在一个置换i，使得θi =· i，则称为F的最一般合一.（Most General
Unifier简记为 MGU）
个人收集整理 勿做商业用途
最一般合一是最简单的合一置换。求F的最一般 合一方法：从左到右比较
F中公式的对应项，若不同则作置换，直到对应项完全相同为止。
个人 收集整理 勿
做商业用途

3.斯柯林范式：
不含存在量词和母式为合取范式的前束范式为斯柯林范式
(

x)(

y)(

z)P(x,y,z)化为: (

y)P(a,y,f(y))
(

x)(

y)(

z)Q(x,y,z)化为： (

x)Q(x,f(x),g(x))
(

x)(
< br>y)(

z)(

u)R(x,y,z.u)化为： (

y)(

z)R(a,y,z,f(y,z))

4.归结推理过程
例：C1=P(x)

Q(x)
C2=7P(a)

R(y)
令θ={ax}
C1`=C1θ=P(a)

Q(a)
C2`=7P(a)

R(y)
C12=Q(a)

R(y)是C1,C2的逻辑推论
定义：设C1和C 2是两个子句，L1，L2分别是C1和C2中的文字，如
果θ是L1与7L2的最一般合一，那么个人收集整理 勿做商业用途
C12＝(C1θ-{L1θ})

{C2θ-{C2θ}}
为C1，C2的双归结式。
如上例：L1= P(x)，L2=7P(a)

在一阶谓词中, 对于不可满足的子句集S，一定可以在有限步内推出空子
句。所以谓 词逻辑中的归结原理也是完备的。
个人收集整理 勿做商业用途
并非所有符号相同但变元不同的谓词公式都可合一，如
C1= P(x)

Q(x)C1= P(z)

Q(z)
C2=7 P(f(x))

R(y)
所以要易名

例：F1=(

x)( P(x)( Q(x)

R(x))
F2=(

x)( P(x)

S(x))
G=(

x)(S(x)

R(x))
证明G是F1

F2的逻辑推论
证明:F1

F2

7G
=(

x) (7P(x)

(Q(x)

(R(x)))

(

x)(P(x)

S(x))

(

x)(7S (x)

7R(x))
(7P(x)

Q(x))

( 7P(x)

R(x))

P(a)

S(a)

(7S(x)

7R(x))
S={7P(x)

Q(x), 7P(y)

R(y), P(a), S(a), 7S(z)

7R(z)}
归结树如下：


3 7

7P(x)

Q(x) 7P(y)

R(y) P(a) S(a) 7S(z)

7R(z)
============ =============
|| {ay} || {az}
R(a) 7R(a)
====================
||
F
所以G是F1,F2的逻辑推论。
例2：证明G是F1, F2的逻辑推论，其中：
F1=(

x)(P(x)(

y)(Q(y) 7L(x,y)))
F2=(

x)(P(x)

(

y)(R(y) L(x,y)))
G=(

x)(R(x) 7Q(x))
解：
对F1: (

x)(7P(x)

(

y)(7Q(y))

7L(x,y)))
S1={7P(x)

7Q(y)

7L(x,y)}
对F2: (P(a)

(

y)(7R(y)

L(a,y))
S2={P(a), 7R(z)

L(a,z)}
对7G : (

x)(77R(x)

77Q(x))
S3={R(b), Q(b)}
7P(x)

7Q(y)

7L(x,y) P(a) 7R(z)

L(a,z) R(b) Q(b)
====================== =============
|| {ax} || {bz}
7Q(y)

7L(a,y) L(a,b)
==============================
|| {by}
7Q(b)
==========================================
||
F

5.归结策略
用归结推理方法可以证明S的子句不可满足性. 由于该过程不断产生新
子句，因此， 子句会越来越多，同样会出现组合爆炸问题。并且会产生大量
的无用子句。因此在归结中选择哪两个子句 （含有互补对）进行归结，是一
个控制策略问题。
个人收集整理 勿做商业用途
如果用树来表示推理过程，就容易理解控制策略。
演绎树（倒长的树）
例如证S={7A

B, A, D, 7D

7B}不可满足。
7A

B A D 7D

7B
======== ========
|| ||
B 7B
=============
||
4 7

F

1)宽度优先策略∩
第一级归结： 生成可能生成的全部归结式S1, S1’=S1∪S0
第二级归结： 生成可能生成的全部归结式S2, S2’=S2∪S1`
(这时已进行归结的子句对不再归结)
……
直到生成空子句
该方法效率低，但它是完备的。即只要子句集不可满足，则一定能在有限步内
归结得到空子句。
例如证S={7A

B, A, D, 7D

7B}不可满足。

2)支持集优先策略
每次归 结时，要归结的两个子句(亲本子句)至少有一个是与目标公式的否定式
有关的子句（目标公式的否定式 化成的子句本身或它的有关后商）该策略完
备？且效率高(相当于在宽度优是策略中有了启发式信息)< br>个人收集整理 勿做商业用
途
例如证D

B 是7A

B，A, D的逻辑推论


3）单元子句优先策略
每次归结时，优先选择单文字子句作归结（至少一个是原文字子句）。这样
5 7

得出的归结式简单，可能会提高效率。
很显然，这种归结策略不完备。

4)删除策略
删除在归结时产生的无用子句，从而减少了中子句数量。
可以删除下面子句：
a.永真式：P

7P，Q

7Q
b.重复出现的子句
c.被归类的子句：子句C把D归类，当且仅当存在一个置换，使得C

D ,
称D为被归类子句。

5)线性归结
首先选择一个子句C0，与其它式作归结产生C1，然后，对于新生成的
Ci， i=1,2,…,n立刻被选中与其它子句Bi或Cj归结，生成C i+1。
个人收集整理
勿做商业用途
如果初始子句选择得正确，线性归结是完备的。
类似深度优先搜索方法。
其中C0选择是重要的，要选择的是关键子句，即缺了C0剩余子句集可满足 ，
这是在支持集优先策略上的改进。

6)组合策略：
组合以上几种方法。

6.应用
用于证明定理，如果x=A，W(x)真否?
即x=A W(x)取真？
但x=? 时,W(x)取真
例1：事实：John likes everything that mary likes.
Mary likes reading.
问: What does John like?
形式化：(

x)(L(Mary,x)L(John,x))
L(Mary,reading)
结论：(

x)L(John,x) 取非(

x)7L(John,x)
先证明：
6 7

找答案：

7 7