知识卡片

普通读书笔记卡 · 3714.b.3.b.4.a.2.a.1

局部约束借真值表转成CNF

理解等级:高级

每个局部门约束只涉及少数变量,可列出使其为假的赋值;这些假赋值构成其否定的析取范式,再取反并用德摩根律得到等价CNF。

此时子句至多三文字,恰好三文字的补齐步骤留到后续单元。

这张卡片看不懂?

已有反馈 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[75000,80000))。 - 结论依据:原文§34.3–34.4证明梗概与公式归约;图表或XHTML已核对,不补造省略的形式化细节。 - 原始内容: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.