知识卡片
短子句可用辅助变量补到三文字
- 对二文字子句a∨b,用(a∨b∨p)∧(a∨b∨¬p)替代;
- 对单文字a,用p、q的四种正负组合形成四个三文字子句。
无论辅助变量取值如何,合取结果都与原子句等价,并满足书中3-CNF的句长要求。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
If Ci contains exactly two distinct literals, that is, if Ci = (l1 ∨ l2), where l1 and l2 are literals, then include (l1 ∨ l2 ∨ p) ∧ (l1 ∨ l2 ∨ ¬p) as clauses of ϕ‴. The literals p and ¬p merely fulfill the syntactic requirement that each clause of ϕ‴ contain exactly three distinct literals. Whether p = 0 or p = 1, one of the clauses is equivalent to l1 ∨ l2, and the other evaluates to 1, which is the identity for AND. If Ci contains just one distinct literal l, then include (l ∨p ∨q)∧(l ∨ p ∨ ¬q) ∧ (l ∨ ¬p ∨ q) ∧ (l ∨ ¬p ∨ ¬q) as clauses of ϕ‴. Regardless of the values of p and q, one of the four clauses is equivalent to l, and the other three evaluate to 1.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[80000,85000))。
- 结论依据:原文§34.4–34.5的3-CNF、团、顶点覆盖和哈密顿环归约;图已核对,跨单元证明留待续读。
- 原始内容:If C i contains exactly two distinct literals, that is, if C i = ( l 1 ∨ l 2 ), where l 1 and l 2 are literals, then include ( l 1 ∨ l 2 ∨ p ) ∧ ( l 1 ∨ l 2 ∨ ¬ p ) as clauses of ϕ ‴ . The literals p and ¬ p merely fulfill the syntactic requirement that each clause of ϕ ‴ contain exactly three distinct literals. Whether p = 0 or p = 1, one of the clauses is equivalent to l 1 ∨ l 2 , and the other evaluates to 1, which is the identity for AND. If C i contains just one distinct literal l , then include ( l ∨ p ∨ q )∧( l ∨ p ∨ ¬ q ) ∧ ( l ∨ ¬ p ∨ q ) ∧ ( l ∨ ¬ p ∨ ¬ q ) as clauses of ϕ ‴ . Regardless of the values of p and q , one of the four clauses is equivalent to l , and the other three evaluate to 1.