┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
1 实验概述
1.1实验目的
熟悉和掌握归结原理的基本思想和基本方法，通过实验培养利用逻辑方法表示知识的能力，
并掌握采用机器推理来进行问题求解的基本方法。
1.2实验内容
（1）对所给问题进行知识的逻辑表示，转换为子句，对子句进行归结求解。
（2）选用一种编程语言，在逻辑框架中实现 Horn 子句的归结求解。
（3）对下列问题用逻辑推理的归结原理进行求解，要求界面显示每一步的求解过程。
破案问题：在一栋房子里发生了一件神秘的谋杀案，现在可以肯定以下几点事实：
(a)在这栋房子里仅住有A,B,C三人；
(b)是住在这栋房子里的人杀了A；
(c)谋杀者非常恨受害者；
(d)A所恨的人，C一定不恨；
(e)除了B以外，A恨所有的人；
(f)B恨所有不比A富有的人；
(g)A所恨的人，B也恨；
(h)没有一个人恨所有的人；
(i)杀人嫌疑犯一定不会比受害者富有。
为了推理需要，增加如下常识：
(j)A不等于B。
问：谋杀者是谁？
ADADADAFAFAFAF
FAFAFDASDSADSADSADSADSADSADSADSADSADSADAFAFAFAF
AFAFAFAF
该文档是极速PDF编辑器生成，
如果想去掉该提示,请访问并下载：
http://www.jisupdfeditor.com/
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
2 实验方案设计
2.1总体思路与总体架构
本实验要求根据已知条件求解问题的答案，首先把已知条件用谓词公式表示出来，并化成相
应的子句集，设该子句集的名字为 S 0 。把待求解的问题也用谓词公式表示出来，然后将其否定，
并与一谓词 ANSWER 构成析取式。谓词 ANSWER 是一个专为求解问题而设置的谓词，其变量
必须与问题公式的变量完全一致，在本实验“杀人问题”中，析取式为~Kill(u,A)∨ ANSWER(u)。
将该析取式并入子句集，合并后的子句集记为 S。接下来开始归结过程，将子句集 S 中的子句两
两配对，判断选择的两子句是否能够互相归结。若两子句能够归结且归结出的新子句不在子句集
中，则将新子句加入子句集中；若新子句正好是 ANSWER(X)的形式，其中 X 是本问题中任意常
量，则代表已经归结出了结果，输出结果；若新子句不是该形式，则继续寻找可归结的子句进行
归结。若子句集中不能再通过归结产生更多新的语句，说明该问题无解，输出提示即可。求解出
问题答案后，可以通过回溯的方法寻找归结的关键路径，以演绎树的形式展示结果。
附加流程图描述如下：
图 2.1实验总体架构图
DADADADAFAFAFA
FAFAFAFAFFAWW
该文档 是极速PDF 编辑器生成 ，
如果想去掉该提示,请 访问并下载 ：
http:// ww w.jisupdfeditor.com/
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
2.2核心算法及基本原理
2 . 2 . 1 一阶逻辑化为子句
在命题逻辑中，命题之间的内在联系和数量关系并没有表达清楚，为了进一步反映这些联系，
需要对命题逻辑进一步分析，分析出其中的个体词、谓词和量词，进一步研究命题之间的逻辑关
系。一阶逻辑中，任何一个一阶逻辑公式都能够化成一个子句集，将初始公式化为子句集的好处
是更容易利用归结原理得出目标子句。将一阶逻辑化为子句集需要遵循以下步骤：
（1）消除蕴含等价。消去蕴含符和双条件符；
（2）否定内移。将否定符号移到紧靠谓词的位置上；
（3）变量标准化。使每个量词采用不同的变量；
（4）消除存在量词。如果该存在量词不依赖于任何其它的变量，可用一个新的个体常量代
替；如果存在量词是在全称量词的辖域内（如在公式(∀y ) （(∃x ) P （ x， y））中，变量 x 的 取 值
依赖于变量 y 的取值）；
（5）将公式化为前束形。把所有全称量词移到公式的左边，并使每个量词的辖域包含这个
量词后面的整个部分；
（6）化为合取范式；
（7）略去全称量词；
（8）消去合取符号；
（9）子句变量标准化。重新命名变量，使每个子句中的变量符号不同。
经过上述五个步骤，可以将初始公式化成标准的子句集形式，便于后续进行归结。
2 . 2 . 2 归结原理
归结原理又称为消解原理，由谓词公式转化为子句集的过程中可以看出，在子句集中子句之
间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。若一个子句集中包含空子
句，则这个子句集就是不可满足的。归结原理就是基于这一认识提出来的，通过两两子句的归结
导出空子句，从而证明子句集的不可满足性。
对于命题逻辑中的任意两个子句 C
1
和 C
2
。如果 C
1
中含有文字 L
1
，C
2
中含有文字 L
2
，并且
L
1
=~L
2
，那么可以从 C
1
和 C
2
中分别消去 L
1
和 L
2
，并将余下的子句析取以构成一个新的子句 C
12
，
则 C
1 2
成 为 C
1
和 C
2
的归结式。即 C
12
= ( C
1
-{L
1
})∨ (C
2
-{L
2
})，C
1
和 C
2
称 为 C
12
的亲本语句。
一阶逻辑中的归结原理与命题逻辑一致，但由于一阶逻辑将命题分为更细致的量词、谓词、
变量和常量等，在一阶逻辑中应用归结原理，常常需要对个体变元进行置换，将该置换作用于给
定的两个子句，使它们包含互补的文字，然后才能进行归结。举例来说，对于子句集 S = { P ( x ) ∨
Q(x)，¬P(A)∨R(y)}，其中的两个子句不能直接归结，但若对子句集先进行置换 s={A/x}，则两
个子句分别为 P ( A ) ∨ Q(A)和 ¬ P ( A ) ∨ R(y)，这时再进行归结，归结结果为 Q(A)∨ R(y)。
利用归结反演可以实现定理的证明，在归结反演过程中，先设置目标子句，将目标子句取反
放入子句集 S 中，应用归结原理对子句集中的子句进行归结，并把每次归结得到的归结式并入 S。
DAFAFAFASFSDAWW
ADAFAFAFAFAF
FAFAFAFA
该文档是极速PDF编辑器生成，
如果想去掉该提示,请访问并下载：
http://www.jisupdfeditor.com/
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
装
┊
┊
┊
┊
┊
订
┊
┊
┊
┊
┊
线
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
┊
如此反复进行，若归结出空子句，则停止归结并证明了目标子句为真。尽管在本实验“杀人问题”
中为了求出杀害 A 的凶手，我们可以依次将 Kill(A,A)，Kill(B,A)和 Kill(C,A)作为目标子句，利
用归结原理进行求解，但当结论错误时，可能会由于算法始终归结不出空子句而不断运行，运行
时间过长，难以得到理想的结果。所以，对于本实验的“杀人问题”，还是可以看作问题求解而
不是问题证明。引入一个特殊的谓词 ANSWER，把待求解的问题用谓词公式表示出来后，将其
否 定 与 ANSWER 构成析取式放入子句集中。如本问题要求杀害 A 的凶手，可以将该凶手记作标
量 u，依照上述方法得到的析取式即为~Kill(u,A)∨ ANSWER(u)。对子句集利用归结原理进行归
结，在归结过程中，通过合一，改变 ANSWER 中的变元。如果得到归结式为 ANSWER(X)的形
式，其中 X 是本问题中任意常量，则该问题的答案即为 X。
2.3模块设计
2 . 3 . 1 一阶逻辑化为子句集
这一部分由依照 2.2.1 中提到的一阶逻辑化为子句集的方式人工进行处理，以本实验“杀人
问题”为例，将已知前提用一阶逻辑表示并将一阶逻辑化为子句集的过程如下所示：
知识表示：令 Kill(x,y)：x 谋 杀 了 y； Hate(x,y)：x 恨 y ；Richer(x,y)： x 比 y 富 有 。
将已知事实用谓词公式表示出来：
F 1 ：Kill(A,A)∨ Kill(B,A)∨ Kill(C,A)
F 2 ：Kill(x,A)→Hate(x,A) = ~Kill(x,A)∨Hate(x,A)
F 3 ：Hate(A,x)→~Hate(C,x) = ~Hate(A,x)∨~Hate(C,x)
F 4 ：Hate(A,A)∧Hate(A,C)
F 5 ：∀ x(~Richer(x,A)→Hate(B,x)) = Richer(x,A)∨Hate(B,x)
F 6 ：∀ x(Hate(A,x)→Hate(B,x)) = ~Hate(A,x)∨Hate(B,x)
F 7 ：~ ∃x ∀y Hate(x,y) =
(~Hate(A,A)∨ ~Hate(A,B)∨ ~Hate(A,C))∧(~Hate(B,A)∨~Hate(B,B)∨~Hate(B,C))∧(~Ha
t e ( C , A ) ∨ ~Hate(C,B)∨ ~Hate(C,C))
F 8 ：Kill(x,A)→~Richer(x,A) = ~Kill(x,A)∨ ~Richer(x,A)
最终的子句集：
S = {
Kill(A,A)∨Kill(B,A)∨Kill(C,A)；
~Kill(x,A)∨ Hate(x,A)；
~Hate(A,x)∨~Hate(C,x)；
Hate(A,A)；
Hate(A,C)；
Richer(x,A)∨ Hate(B,x)；
~Hate(A,x)∨Hate(B,x)；
~Hate(A,A)∨~Hate(A,B)∨ ~Hate(A,C)；
DAFAFADADADADADAFAFAFADAF
FAFAF
该文档是极速PDF编辑器生成，
如果想去掉该提示,请访问并下载：
http://www.jisupdfeditor.com/
