文档介绍：文档名
第三章 确定性推理
冲突消解策略
基本思想：对可用知识排序
特殊知识优先
新鲜知识优先
差异性大的知识优先
领域特点优先
上下文关系优先
前提条件少者优先
第三章 确定性推理
二、推理的
最一般(通用)合一者(mgu)：置换最少的变量以使表达式一致。
分歧集：
例：F={P(x,y,z),P(x,f(a),h(b))}的分歧集
D1={y,f(a)}
D2={z,h(b)}
第三章 确定性推理
合一算法(p89)
例：
F={P(a,x,f(g(y))),P(z,h(z,u),f(u))}
第三章 确定性推理
三、自然演绎推理
已知事实 结论
注意肯定前件、否定后件的错误
：
定义谓词：Prog(x) Like(x,y) Lang(x)
事实：Prog(x) → Like(Wang,x)
( x) (Lang(x) → Prog(x) )
Lang(C)
结论：Like(Wang,C)
经典逻辑推理规则
第三章 确定性推理
四、归结演绎推理（Robinson消解原理）
对前提P，结论Q，证明P → Q永真
P → Q与﹁P∨Q等价
只需证明﹁ （﹁P∨Q）即P∧ ﹁ Q不可满足。
第三章 确定性推理
子句集
概念
文字：原子谓词公式及其否定
子句：任何文字的析取式
空子句NIL：永假、不可满足
化为子句集
消去蕴涵和等价符号
减少否定符号的辖域
对变量标准化，保证每个量词有其唯一的哑元
消去存在量词 skolem函数
第三章 确定性推理
化为前束形 前缀（全称量词串） ＋母式（元量词公式）
把母式化为合取范式
消去全称量词
消去连词符号
更换变量名称
第三章 确定性推理
例（ x）{P(x) →{( y)[P(y)→P(f(x,y))]∧﹁( y)[Q(x,y)→P(y)]}}
第三章 确定性推理
二、p93~98:
只要求记住两条有用的结论：
原谓词公式不可满足，其标准子句集则一定不可满足。
Herbrand(海伯伦)定理：子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S’。
第三章 确定性推理
三、鲁宾逊（ Robinson ）归结原理
基本思想
否定结论，加入前提子句集，应用归结原理，是否能导出空子句，若存在，证明否定结论错误，即原结论得证。（反证法）
实际上归结原理不仅应用在定理证明，还可应用于问题求解过程。
归结原理
互补文字：P、 ﹁ P
归结式：分为命题逻辑归结和谓词逻辑归结.
第三章 确定性推理
命题逻辑归结
定义：
L1、L2分别是子句C1、C2中的文字， 并且L1、L2 互补，即L1＝ ﹁ L2 ，将它们从C1、C2中消去，并将两子句余下部分按析取关系组成新子句C12，即归结式。 C1、C2叫做亲本子句。
例：p99 、、
第三章 确定性推理
定理：归结式C12是亲本子句C1和C2的逻辑结论。
定理：子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。
第三章 确定性推理
归结反演定理证明过程：
公式集S，目标公式G
否定G，得到﹁ G
把﹁ G添加到S中去
新产生{﹁ G，S}化为子句集
应用归结原理，力图推导出一个矛盾空子句
例：p101
第三章 确定性推理
谓词逻辑归结
定义：对含有变元的子句C1、C2中文字L1、L2，如果L1、 ﹁ L2存在最一般合一者ɑ，则有归结式
C12＝{C1－L1} ɑ ∨ {C2-L2} ɑ
二元归结式不作要求
例：p102
谓词逻辑归结反演定理证明
例：p103～105
第三章 确定性推理
谓词逻辑归结反演问题求解
答案求取涉及到把一棵根部有空子句的反演树变换为在根部带有可用作答案的某个语句的一棵证明树
把由目标公式的否定产生的每个子句添加到目标公式否定的否定