17.3 消解证明法
18
本章目录 · 1 节
本章导读
【17.3 消解证明法】将给定前提及结论B的否定¬B一起化成CNF,合并所有子句,再按单对互补文字消解。导出空子句□,就证明Γ∧¬B不可满足,因此Γ⊨B。准备之后只需前提引入及消解,不必同时罗列所有自然推理规则。
步骤:先清楚写Γ与B;求Γ∧¬B的子句集;为每个新子句标出两个父子句及消去变量;找到□后说明撤销反面假设、原推理有效。若尚未出现□,不能立刻断言推理无效,需继续至闭包,或直接给满足Γ∧¬B的模型作为反例。
【例17.3.1】前提q→p、q↔s、s↔t、t∧r,结论p∧q∧s。
前提CNF子句为:C₁=¬q∨p;C₂=¬q∨s;C₃=¬s∨q;C₄=¬s∨t;C₅=¬t∨s;C₆=t;C₇=r。结论的否定给C₈=¬p∨¬q∨¬s,注意是一个三文字子句,不是三个单位子句。
消解序列:C₉=s,由C₅、C₆在t上消解;C₁₀=q,由C₃、C₉在s上消解;C₁₁=p,由C₁、C₁₀在q上消解;C₁₂=¬q∨¬s,由C₈、C₁₁在p上消解;C₁₃=¬s,由C₁₂、C₁₀在q上消解;C₁₄=□,由C₁₃、C₉在s上消解。故该推理有效。
这里r这个前提分项没有被实际使用,并不影响证明;不能反过来认为每条前提都必须参与一次消解,才算有效。相反,所有使用的子句必须确实来自前提、结论否定或可靠的先前消解结果。
【与模型检查的联系】Γ⊨B、(∧Γ)→B永真、Γ∧¬B不可满足,是同一件事的三种表达。原前提本身若矛盾,任意B都能在经典逻辑下有效推出,但这并不证明现实中B为真;对学生应同时检查前提是否一致,区分推理形式有效与应用论证可信。
