归结反演介绍

69 阅读 0 评论 46 点赞

我是靠谱客的博主舒服羊，最近开发中收集的这篇文章主要介绍归结反演介绍，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

归结原理给出了证明子句集不可满足性的方法。
如欲证明Q为P1,P2,…,Pn的逻辑结论，只需证 (P1∧P2∧…∧Pn)∧¬Q 是不可满足的。
应用归结原理证明定理的过程称为归结反演。设F为已知前提的公式集，Q为目标公式(结论)，用归结反演证明Q为真的步骤是：
1.否定Q，得到¬Q；
2.把¬Q并入到公式集F中，得到{F, ¬Q};
3.把公式集{F, ¬Q}化为子句集S；
4.应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结（不论是否还剩余子句集），此时就证明了Q为真。

注意：此时归结完成后（2）并没有进行归结，但是已经出现了空子句，那么就应停止归结。