wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

conjunctive_normal_form (674B)

      1 # Conjunctive normal form (CNF)
      2 
      3 A [boolean_formula] which is a [conjunction] of [clauses]
      4 
      5 Types:
      6 - [monotone_cnf]
      7 - [2cnf]
      8   - [monotone2cnf]
      9 - [3cnf]
     10 - [kcnf]
     11 - [cnf_variable_convex]
     12 - [hitting_cnf]
     13 
     14 lower bound on size of CNF relative to [disjunctive_normal_form]
     15 
     16 Graphs:
     17 - [primal_graph]
     18 - [dual_graph]
     19 - [incidence_graph]
     20 
     21 Parameters:
     22 - [clause_width]
     23 - [primal_treewidth]
     24 - [dual_treewidth]
     25 - [incidence_treewidth]
     26 - [CNF_dimension]
     27 - [variable_clause_difference]
     28 
     29 [conversion]:
     30 - [cnf_to_dnnf]
     31 - [cnf_to_decision_dnnf]
     32 
     33 Notions:
     34 - [Sub_CNF]: a [subset] of the [clauses]
     35 
     36 See also: [disjunctive_normal_form], [dualization]
     37 
     38 Up: [boolean_formula]
     39 
     40 Aliases: CNF, CNFs