16.4 可满足性问题与消解法
本章目录 · 1 节
本章导读
【16.4 可满足性问题与消解法】SAT问是否存在使给定命题公式为真的赋值。真值表可判定,但变量多时有2ⁿ行;本节使用合取范式上的命题消解。任意公式可先化为等值CNF;这种直接展开也可能增长很大,消解法并不自动保证所有输入都很快。
将CNF看作子句集合S,子句内为析取,子句之间为合取。可删重复文字、重复子句以及含互补对的永真子句。空子句是没有文字的析取,记□(原书λ),值0;空子句集∅是空合取,值1。□与∅必须区分。
文字l的补记lᶜ:p的补为¬p,¬p的补为p。赋值α对文字、子句、整个集合都能求值。S≈S′仅表示两者同可满足或同不可满足,不表示在每个赋值下相同;逻辑等值仍用⇔。
【定义16.4.1 消解规则】C₁=A∨l,C₂=B∨lᶜ,删去这一对互补文字,其余析取,得到。一次只选一对;若还有其他互补对,结果为永真子句,而不是把所有互补对一次删光。例如p∨q与¬p∨¬q在p上消解得到q∨¬q,不能错误推出□。
【定理16.4.1】两个非永真子句C₁、C₂的合取与选定消解式具有相同的可满足性,但未必等值。更强且用于推理的可靠性结论是C₁∧C₂蕴涵A∨B:若l真,C₂为真就必须B真;若l假,C₁为真就必须A真。
当A、B不含消解变量时,任意满足A∨B的赋值都能扩张:A真时取l假,A假而B真时取l真,满足两原子句。如果两个子句有多对互补文字,任一单次消解式都永真,且原来两个非永真、各至少含两个文字的子句合取可满足,因此也同可满足。
不能在任意大CNF内把原来的两个子句直接丢掉,只留一个消解式。一般安全做法是保留原句并追加消解结论,或采用有证明保证的完整变量消去步骤。
具体不等值例子:(p∨q∨r)∧(p∨¬r)在r上消解得p∨q。赋值011满足p∨q,却不满足原合取;010满足原合取。若再加固定赋值约束¬p∧q∧r,原合取不可满足,单留消解式却可满足,正好说明“同可满足”不能当成语境内可随意置换的等值关系。
【定义16.4.2 消解序列及否证】序列中每项是S的原子句,或此前两项按一对互补文字消解的结果。末项为□称S的一个否证。由可靠性,每个S的满足赋值也满足所有导出子句,因此导出□就证明S不可满足。
【引理16.4.1 单位传播】若S含单位子句l,令l为真:删除含l的全部已满足子句,从其他子句删去lᶜ,得S′。则S≈S′。正向任一S模型限制后满足S′;反向S′模型加上l真,补齐其他未出现变量,满足S。新生空子句说明冲突。该操作固定了一个变量,保的是可满足性及模型扩张,而不是任意原赋值的逐点等值。
【定理16.4.2 消解完全性】有限命题子句集不可满足,当且仅当能导出□。证明按变量数归纳:若已经含□则结束,零变量且无□的集合可满足;一变量时,非永真子句只能是p或¬p,不可满足就必须两者都在,可直接消解。
归纳步选p,将p=1与p=0分别代入S并作单位化简,得到变量更少的S₁、S₀。若S不可满足,则两者均不可满足,由归纳各有否证。把S₁证明里由含¬p的子句简化得到的各句补回¬p,可将该否证提升为从S导出¬p(或更早已导出□);另一分支补回p,导出p(或□)。最后p与¬p消解得□。这与原书的两分支提升证明一致,并补上了初始含空子句的边界情形。
【消解算法】输入公式A,求CNF并化为去重子句集合K。若K含□,立即回答不可满足;若K为空,回答可满足。随后反复执行:枚举K中每对子句及每一对互补文字;求每个单步消解式;若为□,回答不可满足并保留推导;若永真则略去;否则把尚未在K中的结论加入新集合N。整轮后N为空,说明已达消解闭包,无否证,依据完全性回答可满足;否则令K=K∪N,继续。
不得只看见一个无法继续的分支就回答可满足,也不能把“至今没找到□”当作已达闭包。n变量上,去掉互补对和重复后每个变量至多取“不出现、正、负”三态,所以只有至多3ⁿ个子句,去重新增过程必终止;这是有限终止性,不是多项式时间保证。
【例16.4.1】(1)S={¬p∨q,p∨q,¬q}。前两句在p上消解得q;再与¬q消解得□,所以不可满足。也可先用¬q把前两句分别化成¬p、p,再消解;两条路线都有效。
(2)S={p,p∨q,p∨¬q,q∨¬r,q∨r}。后两句在r上得到q;另可得到p∨r、p∨¬r。继续消解无新非永真结论、无□,所以可满足。显式模型为p=q=1,r可取0或1;原CNF在p=1时前三句已满足,后两句合起来要求q=1,故恰这两个模型。给模型有助于核实“可满足”的回答,但不能用仅列几个失败赋值证明不可满足。(例完)
