原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
in ϕ‴: If Ci contains three distinct literals, then simply include Ci as a clause of ϕ‴.
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.
We can see that the 3-CNF formula ϕ‴ is satisfiable if and only if ϕ is satisfiable by in
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea