知识卡片

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

三合取范式每子句恰有三文字

理解等级:初级
  • 文字是变量或其否定;
  • 子句是若干文字的或;
  • CNF是子句的与。

书中3-CNF进一步要求每个子句恰含三个不同文字,允许同一变量以正、负两种文字出现。

3-CNF-SAT只接收这类可满足公式的编码。

这张卡片看不懂?

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