wiki_research

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

conjunctive_normal_form (605B)

      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 [variable_clause_difference]
     17 
     18 Graphs:
     19 
     20 - [primal_graph]
     21 - [dual_graph]
     22 - [incidence_graph]
     23 
     24 Parameters:
     25 - [clause_width]
     26 - [primal_treewidth]
     27 - [dual_treewidth]
     28 - [incidence_treewidth]
     29 
     30 [conversion]:
     31 - [cnf_to_dnnf]
     32 - [cnf_to_decision_dnnf]
     33 
     34 See also: [disjunctive_normal_form], [dualization]
     35 
     36 Up: [boolean_formula]
     37 
     38 Aliases: CNF, CNFs