知识卡片
局部约束借真值表转成CNF
每个局部门约束只涉及少数变量,可列出使其为假的赋值;这些假赋值构成其否定的析取范式,再取反并用德摩根律得到等价CNF。
此时子句至多三文字,恰好三文字的补齐步骤留到后续单元。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
The second step of the reduction converts each clause into conjunctive normal form. Construct a truth table for by evaluating all possible assignments to its variables. Each row of the truth table consists of a possible assignment of the variables of the clause, together with the value of the clause under that assignment. Using the truth-table entries that evaluate to 0, build a formula in disjunctive normal form (or DNF)—an OR of ANDs—that is equivalent to ¬ . Then negate this formula and convert it into a CNF formula by using DeMorgan’s laws for propositional logic, ¬(a ∧ b) = ¬a ∨ ¬b, ¬(a ∨ b) = ¬a ∧ ¬b, to complement all literals, change ORs into ANDs, and change ANDs into ORs.