1.子句
1)文字:原子谓词及其否定
定义1:任何文字的析取式称为子句
定义2:不包含任何文字的子句称为空子句,子句是永假的
2) 由子句构成的集合称为子句集,谓词公式成子句集的步骤
c) 重新命名变元名,使不同量词约束的变元有不同的名字
d) 消去存在量词
e) 把全称量词移到公式左边
f) 利用等价关系
g) 消去全称量词
h) 对变元更名
i) 消去合取词
2.Robinson归结定理(消解原理)
1) 基本思想
检查子句集S中是否包含空子句,若包含则S不可满足;若不包含,就在子句集中选择合适的子句进行归结,一旦通过归结能推出空子句,就说明子句集S是不可满足的。
2) 命题逻辑中的归结原理
定义:设C1与C2是子句集中的任意两个子句,如果C1中的文字L1与C2中的文字L2互补,那么从C1和C2中分别消去L1和L2,并将两个子句中余下的部分析取,构成一个新子句C12,则称这个过程为归结,称C12为C1和C2的归结式,称C1和C2为C12的亲本子句。
3) 谓词逻辑中的归结原理
首先对变元进行代换,然后才能进行归结。
4) 归结反演
应用归结原理证明定理的过程称为归结反演。设F为已知前提的公式集,Q为目标公式(结论),用归结反演证明Q为真的步骤是:
d) 应用归结原理对子句集S中的子句进行归结,并把每次归结得到的归结式都并入S中,反复进行,若出现了空子句,则停止归结,此时证明了Q为真。
归结反演例示
A,B,C三人中有人从来不说真话,也有人从来不说假话,某人向这三人分别提出一个问题:谁是说谎者?A答:“B和C都是说谎者”;B答:“A和C都是说谎者”;C答:“A和B中至少有一个说谎者”求谁是老实人,谁是说谎者。
设用T(X)表示X说真话,已知前提用谓词表示
化成子句集,得到S:
3.归结策略
1) 归结的一般过程
设有子句集S={C1,C2,C3,C4}
(1)从子句C1开始,逐个与C2,C3,C4进行比较,归结。然后用C2与C3和C4进行比较,归结。最后用C3和C4比较,归结。得到第一级归结式。
再从C1开始,用S中的子句分别与第一级归结式中的子句逐个地进行比较,归结,得到第二级归结式。
(2)仍然从C1开始,用S中的子句及第一级归结式中的子句逐个地与第二级归结式中的子句进行比较归结,得到第三级归结式。
(3)继续直到出现空子句或者不能再继续归结为止。
2) 删除策略
(1)纯文字删除法
如果某文字L在子句集中不存在可与之互补的文字L,则称该文字为纯文字。
(2)重言式删除法
如果一个子句中同时包含互补文字对,则称该子句为重言式。
(3)包孕删除法
设有子句C1和C2,如果存在一个代换,使得C1C2,则称C1包孕于C2。
3) 支持集策略
每一次归结时,亲本子句中至少应有一个是由目标公式的否定所得到的子句,或者是它们的后裔。
4) 线性输入策略
参加归结的两个子句中必须至少有一个是初始子句集中的子句。
5) 单文字子句策略
一个子句只包含一个文字,要求参加归结的两个子句中必须至少有一个是单文字子句。
6) 祖先过滤策略
(1)C1和C2至少有一个是初始子句集中的子句。
(2)如果两个子句都不是初始子句集中的子句,则一个应是另一个的祖先,C2是由C1与别的子句归结后得到的归结式。
参考文献:
[1] 王永庆. 人工智能原理与方法. 西安: 西安交通大学出版社
[2] 尹朝庆. 人工智能方法与应用. 武汉: 华中科技大学出版社, 2007.
相关推荐
人工智能作业 鲁滨逊归结原理 java 语言完成
归结原理是一种推理规则。从谓词公式转化为子句集的过程中看出,在子句集中子句之间是合取关系,其中只要有一个子句不可满足,则子句集就不可满足。若一个子句集中包含空子句,则这个子句集一定是不可满足的。归结...
人工智能谓词逻辑归结问题的推理系统是很好的学习资料 ,可以帮助广大学子进一步学习人工智能的相关知识。
推理方式及其分类 模式匹配及其变量代换 ...归结演绎推理 海伯伦理论 鲁宾逊归结原理 归结反演 基于归结反演的问题求解 归结反演策略 与/或形正向演绎推理 与/或形的逆向演绎推理 代换的一致性与剪枝策略
人工智能 基于归结原理的推理系统.rar 人工智能 基于归结原理的推理系统.rar
人工智能原理教案02章 归结推理方法2归结推理方法.pptx
人工智能:归结推理方法.ppt
本项目是同济大学人工智能课程的第三次大作业——子句归结问题,内含工程文件与报告
人工智能 归结算法 cpp 代码 人工智能 归结算法 cpp 代码
人工智能 等式归结.rar 人工智能 等式归结.rar 人工智能 等式归结.rar
实现了命题逻辑的归结推理
广工人工智能归结原理实验,为了让同学们更好的了解归结性原理,请大家参考
人工智能的实验题目。输入一组合适公式,以及一个目标子句,输出归结树。 我奋斗了几乎5天总算弄出来了,放过bin出来show一下^_^。 至于代码,想要的可以联系我。 这里给出一个测试用例吧: ;假设:所有不贫穷且...
基于矩阵运算的基于归结原理的自动推理算法,人工智能程序设计
大数据-算法-基于格值逻辑的准锁语义归结自动推理研究.pdf
这是人工智能方面的一个应用,用归结原理进行逻辑公理的证明!