知识卡片
三合取范式每子句恰有三文字
- 文字是变量或其否定;
- 子句是若干文字的或;
- CNF是子句的与。
书中3-CNF进一步要求每个子句恰含三个不同文字,允许同一变量以正、负两种文字出现。
3-CNF-SAT只接收这类可满足公式的编码。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
A literal in a boolean formula is an occurrence of a variable (such as x1) or its negation (¬x1). A clause is the OR of one or more literals, such as x1 ∨ ¬x2 ∨ ¬x3. A boolean formula is in conjunctive normal form, or CNF, if it is expressed as an AND of clauses, and it’s in 3-conjunctive normal form, or 3-CNF, if each clause contains exactly three distinct literals.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[75000,80000))。
- 结论依据:原文§34.3–34.4证明梗概与公式归约;图表或XHTML已核对,不补造省略的形式化细节。
- 原始内容:A literal in a boolean formula is an occurrence of a variable (such as x 1 ) or its negation (¬ x 1 ). A clause is the OR of one or more literals, such as x 1 ∨ ¬ x 2 ∨ ¬ x 3 . A boolean formula is in conjunctive normal form , or CNF , if it is expressed as an AND of clauses, and it’s in 3-conjunctive normal form , or 3-CNF , if each clause contains exactly three distinct literals.