4-2020 第四章-31
需积分: 0 94 浏览量
2022-08-03
16:18:10
上传
评论
收藏 618KB PDF 举报
2020/9/27
1
目
录
1
2
消解原理
子句集的求取
消解原理
• 前面介绍过谓词公式、合式公式性质以及置换、合一等概念。
在此基础上,进一步介绍消解原理。
• 消解原理又称为归结原理。该原理是Robinson提出的一种基
于逻辑的、采用反证法的推理方法。
• 由于其理论上的完备性，归结原理成为机器定理证明的主要
方法。
• 证明的基本思想是：
设F
1
、 F
2
…、F
n
、G为公式，G为F
1
、F
2
…、F
n
的逻辑推论
，当且仅当公式
((F
1
F
2
…F
n
)G)是有效的 。
• 可以采用反证法的思想：
设F
1
、F
2
…、F
n
、G为公式，G为F
1
、F
2
…、F
n
的逻辑推论
，当且仅当公式(F
1
F
2
…F
n
¬ G)是不可满足的 。
消解原理
分析：
• 令C= F
1
F
2
…F
n
• (CG)等价于 ¬ C∨ G
• ¬(CG)等价于 ¬ (¬ C∨ G)，可化为C ¬ G，
• 即(F
1
…F
n
¬ G)
• 归结法的本质上就是一种反证法，它是在归结推理规则的基础上
实现的：为了证明一个命题P恒真，它证明其反命题¬ P恒假，即
不存在使得¬ P为真的解释，从而证明了命题P恒真。
• 只要证明((F
1
…F
n
)G)的否定，即(F
1
…F
n
¬ G)是不可满
足的（找不到一个解释使其为真），则说明原公式成立。
消解原理
文字：一个原子公式和原子公式的否定都叫做文字，如：
P(x)， ¬P(x,f(x))，Q(x, g(x))
互补的文字：形如P和¬ P，Q(x)和¬ Q(x)的文字对称为互补的文
字
子句：由文字的析取组成的公式，如：
P(x)∨Q(x), ¬P(x,f(x))∨Q(x,g(x))
空子句：不包含任何文字的子句。
子句集：由子句构成的集合。
例：{P(x)∨Q(x) , ¬ P(x，f(x))∨Q(x,g(x)) }
基本概念
设C
1
，C
2
，C
3
…，C
n
为n个子句
合取范式：C
1
∧C
2
∧C
3
… ∧C
n
子句集: S= {C
1
,C
2
,C
3
… ,C
n
}
任何谓词公式 F 都可通过等价关系及推理规则化为
相应的子句集S。
基本概念
评论0
最新资源