wiki_research

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

conjunctive_normal_form (589B)

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