为什么要搜索真假赋值?
知识库可以包含“至少一个传感器正常”这类析取句。对定言霍恩(Horn)规则进行前向推理,并不能直接表达所有这类选择。有限命题问题可以用穷举真假赋值来判定,但我们往往能一次排除多个赋值:当一个尚未满足的子句只剩下一个选项尚未为假,该选项便必须为真。单子句传播正是利用这个观察;没有选项被迫成立时,仍须搜索。
本节建立一个精确而简单的 DPLL 算法,联系前面的搜索和逻辑推理,补充归结法单元的变量消去方法。下述程序判定有限命题公式,不判定任意一阶公式。
子句、部分赋值与传播
定义 24.1.1
(文字、子句与 CNF)
固定有限个布尔(Boole)原子。文字是原子 或其否定 ;子句是有限个文字的析取,合取范式(CNF)则是子句的合取。把子句看作文字的集合,重复的文字不影响结果。空合取为真,空子句为假。CNF 的模型是使每个子句为真的完整赋值;有模型的 CNF 称为可满足,否则称为不可满足。
定义 24.1.2
(部分赋值与化简)
部分赋值只给一部分原子指定真或假。按赋值化简公式时,删除含有真文字的整个子句,再从其余子句中删去假文字。若出现空子句,当前赋值不可能扩展为模型;若没有子句剩下,当前赋值的任何完整扩展都满足原公式。尚未赋值的原子,其正负文字都还没有确定的真假。
定义 24.1.3
(单子句与单子句传播)
只含一个文字的子句称为单子句。任何满足公式的扩展都必须使它的文字为真。单子句传播就是作出这个赋值并化简,重复直到出现矛盾或不再有单子句。
被迫赋值的先后次序不影响是否存在满足它们的扩展,但程序最先报告的冲突可能不同。含 和 的子句永远为真,可以事先删去;保留它也不影响以下算法的正确性。
对已化简的 CNF 和当前部分赋值,递归执行:
- 反复传播单子句,直到没有单子句或出现空子句。
- 若有空子句,报告此分支不可满足;若没有子句,返回当前赋值,未定原子任意补成完整赋值。
- 否则选一个仍出现在公式中、尚未赋值的原子,先递归试真。若找到模型就返回;若失败,恢复父节点的赋值,再试假。两个分支都失败才报告不可满足。
各递归调用可以有自己的赋值副本;若共用记录,便须撤销失败分支中所有赋值,包括传播得到的赋值。选哪个原子、先试真还是假,影响工作量而不影响最终的可满足性答案。这里没有假设纯文字规则、子句学习或特定选择启发策略。
概念视角几何
把子句看作立方体上的禁区
把 个全赋值看作 维立方体的顶点。含 个文字的子句,恰在使其每个文字为假的赋值上为假,这些赋值构成维数为 的面。CNF 可满足,当且仅当这些禁区不能覆盖所有顶点。单子句禁掉半个立方体,空子句禁掉整个立方体,分支决策则把注意力限制在其中一半。在两个原子上,后文四个子句的例子各禁掉一个顶点,所以没有任何顶点剩下。
定理 24.1.4
(有限 DPLL 的可靠性与完备性)
对有限 CNF,上述程序会终止。若它返回一个赋值,该赋值满足原 CNF;它报告不可满足,当且仅当原 CNF 没有满足赋值。最坏情况下搜索量可以随原子数呈指数增长。
证明
(对未定原子数归纳)
在目前部分赋值下,化简恰好保留满足公式的所有延伸:已为真的子句不再增加要求,而假文字不能满足其子句。任何满足延伸都使单子句中的文字为真,因此传播也保留全部满足延伸。空子句没有满足延伸;没有剩余子句时,任何完整延伸皆可满足。
若两种停止情况都没有出现,选出的原子尚未赋值。每个完整延伸必定在该原子取真或取假的其中一类,两个分支涵盖所有可能。每次分支至少指定一个原本未定的原子,故分支深度不超过原子数。对未定原子数作归纳,每个分支恰在存在模型时返回模型;把两个分支合起来便证明父节点也有此性质,得到可靠性和完备性。每次成功传播都指定一个未定原子,因此传播亦会终止。真假赋值构成的二叉树可能有指数多个节点;定理保证能判定,并不保证多项式时间。
证明透视
分支失败为什么不等于全局矛盾?
证明依靠一个不变量:化简与传播恰好保留当前部分赋值的全部满足扩展。单子句中的文字只是相对于已经作出的赋值才被迫为真,所以传播是在当前分支条件下必须作出的推论。因此冲突只证明没有模型能扩展该分支的选择,不能仅凭它断言原公式没有模型。二分是穷尽的,因为每个完整扩展都给所选原子一个取值;只有排除了所有相关决策的两种真假情形,才能在根节点宣布不可满足。有限性最后才用到:每个分支都给一个原本未赋值的原子赋值,所以搜索会终止。
用反证判定蕴涵
定义 24.1.5
(蕴涵)
若 的每个模型都使 为真,就称公式 蕴涵公式 。
命题 24.1.6
(蕴涵即不可满足)
对同一组原子上的公式 与 , 蕴涵 当且仅当 没有模型。
证明
(展开定义)
的模型,恰好就是使 为假的 的模型。所以 没有模型,当且仅当没有 的模型使 为假,也就是 的每个模型都使 为真。
因此上述搜索也能判定蕴涵:对 的 CNF 形式运行搜索,把“不可满足”读作“蕴涵”。
算例追踪
例题 24.1.7
(蕴涵链与一个模型)
设
起初没有单子句。先试 。第一个子句迫使 ;接着 迫使 ;最后 迫使 。子句 因 为假而早已为真。所有子句均消失,故 是模型。若先试 ,也可以得到模型。找到一个模型足以证明可满足,但不等于列出所有模型。
例题 24.1.8
(以反证检验蕴涵)
同一个 蕴涵 。加入单子句 :传播先得 ,再由 得 。接着两个子句分别迫使 和 ,令 成为空子句。因此 没有模型,按定义即每个 的模型都满足 。对任意命题查询 ,一般方法是检验 是否可满足;转成 CNF 时须保留可满足性。若原合取式可满足,它的模型便是蕴涵的反例。若编码引入辅助变量,仅知两个公式可满足性相同,并不能保证编码所得模型可直接给出反例:应使用其模型投影后必定满足原合取式的转换,或另行重建并验证反模型。
例题 24.1.9
(无需任何决策的反证,与空公式)
设 。子句 是单子句,所以 ,第二个子句变成单子句 。赋值 后,子句 成为空子句。冲突在根节点、尚未作任何决策时就出现,所有扩展都被排除: 不可满足,而且不需要分支。另一个极端是空 CNF:它没有子句,所以第二条停止规则立即适用,任何完整赋值都是模型。这两个边界情形说明,第 2 步的两条停止规则都可以在不作任何决策的情况下到达。
反例模式
没有撤销的分支赋值会改变答案
设 。试 时,第一个子句成为单子句 ,传播令 ,随后第二个子句 变成空子句:此分支失败。恢复父节点后, 使第三个子句成为单子句 ,其余两个子句为真,于是 , 是模型。若错误地保留失败分支的 ,第二分支中第三个子句 就为假, 被误报为不可满足。回溯不但要撤销决策,还要撤销由决策传播出的赋值。
答案代表什么?
返回的模型是可直接检查的证据:把各值代入原来的每个子句。不可满足意味具证明性的搜索已排除所有可能赋值;若另一个程序要验证大型运算,可能还需要另设证明证书格式。可满足的知识库可以蕴涵某个查询,尽管许多变量尚未确定。反过来,一个不完备规则系统未能导出查询,本身并不证明其否定。
若知识库本身不一致,就没有模型,在古典逻辑中因而蕴涵任何查询。这是“每个模型都为真”之定义的后果,不是每个结论都有实用证据。数据可能矛盾时,应另外检查一致性。计算成本取决于表示和搜索选择;一个例子算得快,不代表最坏情况也快。
常见错误
常见错误
(传播悄悄停下并不是判决)
公式 既没有单子句也没有空子句,传播无事可做,也不报告冲突。把这读作“可满足”是错的:对 分支,两个分支都冲突,公式不可满足。仍有子句剩下的不动点,只说明需要作出决策。
常见错误
(检验了查询本身,而不是它的否定)
对 与 ,合取式 可满足,例如取 。 有模型,只说明 与 相容,并不说明 蕴涵 。应当检验 有没有模型:有,取 ,所以 不蕴涵 。
习题
快速检查
(对 执行上述程序,先选 。给出一个模型,并指出所有被迫赋值。)
每次化简后,找出单子句。
解答 · 答案
令 ,第一个子句变为单子句 ,故 ;最后一个子句再迫使 。第二个子句因 为真而满足。所以 满足每个子句。
快速检查
(对 ,对 分支,说明两个分支都会冲突。)
化简每个分支,找出成对的单子句 和 。
解答 · 答案
时,第二和第四个子句分别变为 和 ,传播产生冲突。 时,第一和第三个子句分别变为 和 ,同样冲突。 的两个取值已涵盖全部情形,所以公式不可满足。
快速检查
( 是否蕴涵 ?给出 的反证或一个反模型。)
尝试令 为假,同时保持两个子句为真。
解答 · 答案
不蕴涵。取 ,第一个子句由 满足,第二个子句由 满足,但 为假。这是 的模型,也是蕴涵的反例。
快速检查
( 起初没有单子句。仅因传播停止而没有出现冲突,能否宣布它可满足?它是否蕴涵 ?请说明。)
加入单子句 来检验蕴涵。
解答 · 答案
不能:既没有单子句,也没有发现冲突,并不是可满足的证明,因为仍有子句尚未决定。此例确实蕴涵 :加入 后,原来两个子句分别变为 和 ,产生冲突。原公式也可满足,例如取 ;加入 的反证说明蕴涵成立,而这个模型说明原公式是一致的。