爱华网
第 3 章 确定性推理方法
基本内容：
3.1 推理的基本概念
3.2 自然演绎推理
3.3 谓词公式化为子句集的方法
3.4 鲁宾逊归结原理
3.5 归结反演
3.6 应用归结原理求解问题
重点考查知识点：
（1） 推理的基本概念、分类
（2） 自然演绎推理的基本过程及优缺点
（3） 鲁宾逊归结原理、过程及应用
（4） 归结反演、过程及应用
（5） 应用归结原理求解问题
复习题及参考答案：
1.谓词逻辑和命题逻辑的关系如何？有何异同？
解：谓词逻辑是命题逻辑的扩充与发展，它将一个原子命题分解成谓词与个体两部分。命题逻辑是谓词逻辑的基础，是谓词逻辑的一种特殊形式。
不同点：命题逻辑不能描述不同事物的共同特征，而谓词逻辑可以。命题逻辑中可以直接通过真值指派给出解释，而谓词逻辑不行。
相同点：归结原理都是完备的，都可以用来表示事实性知识。
2.什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。
解：项是个体常数、变量和函数的统称。若谓词个体是常量、变元或函数，则为一阶谓词，若谓词个体是一阶谓词，则为二阶谓词，依此类推是为谓词的阶。
谓词的一般形式：P（x1，x2，…，xn），其中P是谓词，x1，x2，…，xn是个体。
3． 请写出用一阶谓词逻辑表示法表示知识的步骤。
步骤：（1）定义谓词及个体，确定每个谓词及个体的确切含义；（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。
4．对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。
（1）("x)(P(x,y)Ú($y)(Q(x,y)ÙR(x,y)))
解：("x)的辖域是(P(x,y)Ú($y)(Q(x,y)ÙR(x,y)))，x是受("x)约束的变元；($y)的辖域的(Q(x,y)ÙR(x,y))，y是受($y)约束的变元；没有自由变元。
（2）($z)("y)(P(z,y)ÚQ(z,x))ÚR(u,v)
解：($z)的辖域是("y)(P(z,y)ÚQ(z,x))，z是受($z)约束的变元；("y)的辖域是(P(z,y)ÚQ(z,x))，y是受("y)约束的变元；u、v是自由变元。
（3）("x)(~P(x,f(x))Ú($z)(Q(x,z)Ù~R(x,z)))
解：("x)的辖域是(~P(x,f(x))Ú($z)(Q(x,z)Ù~R(x,z)))，x是受("x)约束的变元；($z)的辖域是(Q(x,z)Ù~R(x,z))，z是受($z)约束的变元；没有自由变元。
5． 谓词的永假性和不可满足性等价吗？
解：根据永假性和不可满足性的定义可知，两者是等价的。
6． 什么是置换？什么是合一？什么是最一般的合一？
解：置换是形如｛t1/x1，t2/x2，…，tn/xn｝的一个有限集。其中xi是变量，ti是不同于xi的项（常量，变量，函数），且xi¹xj（i¹j），i，j=1，2，…，n。
设有公式集｛E1，E2，…，En｝和置换q，使E1q＝E2q＝…＝Enq，便称E1，E2，…，En是可合一的，用称q为合一置换。
若E1，E2，…，En有合一置换s，且对E1，E2，…，En的任一置换q都存在一个置换l，使得q＝s×l，则称s是E1，E2，…，En的最一般合一置换。
7． 什么是范式？请写出前束范式与SKOLEM范式的形式。
答：定义：量词按照一定的规则出现的谓词公式。
前束范式形式：("x)($y)("z)(P(x)ÙF(y,z)ÙQ(y,z))
SKOLEM范式形式：("x1) ("x2)… ("xn)M(x1，x2，…，xn）
8．什么是子句？什么是子句集？请写出谓词公式子句集的步骤。
解：子句就是由一些文字组成的析取式。由子句构成的集合称为子句集。
步骤：（1）消去谓词公式中的蕴涵和等值符号，以~AÚB代替A®B，以(~AÚB) Ù (AÚ~B)替换A«B。
（2）减少否定符号的辖域，使否定符号最多只作用到一个谓词上。
（3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。
（4）消去存在量词。
（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。
（6）公式化为合取范式，得到与其对应的子句集。
9．谓词公式与它的子句集等值吗？在什么情况下它们才会等价？
解：不等值。在不可满足的意义下是等价的。
10．引入Robinson的归结原理有何意义？什么是归结推理？什么是归结式？请写出它的推理规则。
解：Robinson归结原理是一种证明子句集不可满足性，从而实现定理证明的方法，是对自动推理的重大突破，使机器定理证明变为现实。
设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，则从C1和C2中可以分别消去L1和L2，并将二子句中余下的部分做析取构成一个新的子句C12，这一过程称为归结，所得到的子句C12称为C1和C2的归结式。
推理规则：消去互补对。
11．请写出应用归结原理进行定理证明的步骤。
解：（略）
12．什么是完备的归结控制策略？有哪些归结控制策略是完备的？
解：若子句集是不可满足的，则必存在一个从该子句集到空子句的归结推理过程的归结控制策略是完备的归结控制策略。
完备的归结控制策略有：删除策略、线性归结策略、支持集策略，祖先过滤形策略。
13. 把下列谓词公式分别化为相应的子句集：
（1）("z)("y)(P(z,y)ÙQ(z,y))
解：所求子句集为S={P(z,y)，(z,y)}
（2）("x)("y)(P(x,y)®Q(x,y))
解：原式Þ("x)("y)(~P(x,y)ÚQ(x,y))
所求子句集为S={~P(x,y)ÚQ(x,y)}
（3）("x)($y)(P(x,y)Ú(Q(x,y)®R(x,y)))
解：原式Þ("x)($y)(P(x,y)Ú(~Q(x,y)ÚR(x,y)))
Þ("x)(P(x,f(x))Ú(~Q(x,f(x))ÚR(x,f(x))))
所求子句集为S={P(x,f(x))Ú(~Q(x,f(x))ÚR(x,f(x)))}
14．设有下列语句，请用相应的谓词公式把它们表示出来：
（1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。
解：定义谓词如下：
Like(x,y)：x喜欢y。 Club(x)：x是梅花。
Human(x)：x是人。 Mum(x)：x是菊花。
“有的人喜欢梅花”可表达为：($x)(Human(x)ÙLike(x,Club(x)))
“有的人喜欢菊花”可表达为：($x)(Human(x)ÙLike(x,Mum(x)))
“有的人既喜欢梅花又喜欢菊花”可表达为：
($x)(Human(x)ÙLike(x,Club(x))Ù Like(x,Mum(x)))
（2）他每天下午都去玩足球。
解：定义谓词如下：
PlayFootball(x)：x玩足球。 Day(x)：x是某一天。
则语句可表达为：("x)(D(x)®PlayFootball(Ta))
（3）太原市的夏天既干燥又炎热。
解：定义谓词如下：
Summer(x)：x的夏天。 Dry(x)：x是干燥的。Hot(x)：x是炎热的。
则语句可表达为：Dry(Summer(Taiyuan))ÙHot(Summer(Taiyuan))
15．判断下列子句集中哪些是不可满足的：
（1）S={~PÚQ, ~Q,P, ~P }
解：使用归结推理：
(1)~PÚQ (2) ~Q(3)P(4) ~P
(3)与(4)归结得到NIL，因此S是不可满足的。
（2）S={PÚQ, ~PÚQ,PÚ~Q, ~PÚ~Q }
解：使用归结推理：
(1)PÚQ (2)~PÚQ (3)PÚ~Q (4)~PÚ~Q
(1)与(2)归结得(5)Q
(3)与(5)归结得(6)P
(4)与(6)归结得(7) ~Q
(5)与(7)归结得NIL，因此S是不可满足的。
（3）S={P(y)ÚQ(y), ~P(f(x)) ÚR(a) }
解：使用归结推理：
设C1=P(y)ÚQ(y)，C2=~P(f(x)) ÚR(a)，选L1= P(y)，L2=~P(f(x))，则
L1与L2的mgu是s={f(x)/y}，C1与C2的二元归结式C12=Q(f(x))ÚR(a)，因此S是可满足的。
（4）S={~P(x)ÚQ(x), ~P(y)ÚR(y),P(a), S(a),~S(z)Ú~R(z) }
解：使用归结推理：
(1)~P(x)ÚQ(x)(2)~P(y)ÚR(y)(3) P(a) (4)S(a) (5)~S(z)Ú~R(z)
(2)与(3)归结得到(6)R(a)
(4)与(5)归结得到(7) ~R(a)
(6)与(7)归结得到NIL，因此S是不可满足的。
（5）S={~P(x)Ú ~Q(y) Ú ~L(x,y), P(a), ~R(z) Ú L(a,z),R(b),Q(b) }
解：使用归结推理：
(1) ~P(x)Ú~Q(y) Ú~L(x,y)
(2)P(a)
(3) ~R(z) ÚL(a,z)
(4)R(b)
(5) Q(b)
(1)与(2)归结得到(6) ~Q(y) Ú ~L(a,y)
(5)与(6)归结得到(7) ~L(a,b)
(3)与(4)归结得到(8) L(a,b)
(7)与(8)归结得到NIL，
因此S是不可满足的。
（6）S={~P(x)ÚQ(f(x),a),~P(h(y))ÚQ(f(h(y),a)) Ú~P(z) }
解：使用归结推理：
令C1=~P(x)ÚQ(f(x),a)，
C2= ~P(h(y))ÚQ(f(h(y),a))Ú~P(z) 则：
C2内部的mgu是s={h(y)/z}，合一后C2’=~P(h(y))ÚQ(f(h(y)),a)
选L1=~P(x)，L2=~P(h(y)) 则
L1与L2的mgu是s={h(y)/x}，
C1与C2’的二元归结式C12=~P(h(y))ÚQ(f(h(y)),a)，因此S是可满足的。
（7）S={P(x)Ú Q(x) Ú R(x), ~P(y) Ú R(y) , ~Q(a),~R(b) }
解：使用归结推理：
(1) P(x)Ú Q(x) ÚR(x) (2)~P(y) Ú R(y)(3)~Q(a) (4)~R(b)
(1)与(3)归结得到 (5) P(a) Ú R(a)
(2)与(4)归结得到 (6) ~P(b)
(5)与(6)归结得到 (7) R(b)
(4)与(7)归结得到NIL，因此S是不可满足的。
（8）S={P(x)ÚQ(x), ~Q(y)ÚR(y), ~P(z)ÚQ(z) ,~R(u)}
解：使用归结推理：
(1)P(x)ÚQ(x) (2)~Q(y)ÚR(y)(3)~P(z)ÚQ(z)(4) ~R(u)
(2)与(4)归结得到 (5) ~Q(u)
(1)与(5)归结得到 (6) P(u)
(3)与(6)归结得到 (7)Q(u)
(5)与(7)归结得到NIL，因此S是不可满足的。
16．对下列各题分别证明G是否为F1，F2，…，Fn的逻辑结论。
（1）F1：($x)($y)P(x,y)G：("y)($x)P(x,y)
解：首先将F1和~G化为子句集：
(1)P(a,b)(2)~P(x,b)
(1)与(2)归结得到NIL，s={a/x}，
因此G是F1的逻辑结论。
（2）F1：("x)(P(x)Ù(Q(a)ÚQ(b))) G：($x)(P(x)ÙQ(x))
解：首先将F1和~G化为子句集：
(1)P(x)(2)Q(a)ÚQ(b)(3) ~P(x)Ú ~Q(x)
(2)自身合一得到(4)Q(a)，s={a/b}
(1)与(3)归结得到(5) ~Q(x)
(4)与(5)归结得到NIL，s={a/ x}，
因此G是F1的逻辑结论。
（3）F1：($x)($y)(P(f(x))ÙQ(f(b))) G：P(f(a))ÙP(y)ÙQ(y)
解：首先将F1和~G化为子句集：
(1)P(f(a))(2)Q(f(b))(3)~P(f(a))Ú~P(y)Ú~Q(y)
(3)自身合一得到(4) ~P(f(a))Ú~Q(f(a))，s={f(a)/y}
(1)与(4)归结得到(5) ~Q(f(a))
(2)与(5)归结得到NIL，s={f(a)/ f(b)}，
因此G是F1的逻辑结论。
（4）F1：("x)(P(x)®("y)(Q(y)®~L(x,y)))F2：($x)(P(x)Ù("y)(R(y)®L(x,y)))
G：("x)(R(x)®~Q(x))
解：首先将F1、F2和~G化为子句集：
(1) ~P(x)Ú~Q(y)Ú~L(x,y)
(2)P(a)
(3)~R(y)ÚL(a,y)
(4)R(a)
(5)Q(a)
(1)与(2)归结得到(6) ~Q(y)Ú~L(a,y)，s={a/ x}
(3)与(6)归结得到(7) ~R(y)Ú ~Q(y)
(4)与(7)归结得到(8) ~Q(a)，s={a/ y}
(5)与(8)归结得到NIL，
因此G是F1、F2的逻辑结论。
17．证明：("y)(Q(y)®(B(y)ÙC(y)))Ù($y)(Q(y)ÙD(y))®($y)(D(y)ÙC(y))
解：对结论否定并与前提合并得谓词公式G：
G=("y)(Q(y)®(B(y)ÙC(y)))Ù($y)(Q(y)ÙD(y))Ù~($y)(D(y)ÙC(y))
将谓词公式G化为子句集：
(1)~Q(y)ÚB(y)
(2)~Q(y)ÚC(y)
(3)Q(a)
(4)D(a)
(5) ~D(y)Ú~C(y)
使用归结推理：
(2)与(3)归结得到(6)C(a)，s={a/ y}
(4)与(5)归结得到(7) ~C(a)，s={a/ y}
(6)与(7)归结得到NIL，因此G是不可满足的，从而命题得证。
18．设已知：
(1)凡是清洁的东西就有人喜欢；
(2)人们都不喜欢苍蝇；
试证明：苍蝇是不清洁的
解:
所以原命题成立
