| Conjunctive Normal Form |
Article Index for Conjunctive |
Website Links For Normal |
Information AboutConjunctive Normal Form |
| CATEGORIES ABOUT CONJUNCTIVE NORMAL FORM | |
| logic | |
| boolean algebra | |
|
All conjunctions of literals and all disjunctions of literals are in CNF, as they can be seen as conjunctions of one-literal clauses and conjunctions of a single clause, respectively. As in the Disjunctive Normal Form , the only propositional connectives a formula in CNF can contain are And , Or , and Not . The not operator can only be used as part of a literal, which means that it can only precede a propositional variable. For example, all of the following formulas are in CNF: : : : : But the following are not: : : : The above three formulas are respectively equivalent to the following three formulas that are in conjunctive normal form: : : : Every propositional formula can be converted into an , the De Morgan's Laws , and the Distributive Law . Since all logical formulas can be converted into an equivalent formula in conjunctive normal form, proofs are often based on the assumption that all formulae are CNF. However, in some cases this conversion to CNF can lead to an exponential explosion of the formula. For example, translating the following formula in CNF produces a formula with clauses: : Transformations of formulae in CNF preserving Satisfiability rather than equivalence and not producing an exponential increase of size exist. These transformations are guaranteed to only linearly increase the size of the formula, but introduce new variables. Conjunctive normal form can be taken further to yield the Clausal Normal Form of a logical formula, that is used to perform First-order Resolution . An important set of problems in Computational Complexity involves finding assignments to the variables of a boolean formula expressed in Conjunctive Normal Form, such that the formula is true. The k-SAT problem is the problem of finding a satisfying assignment to a boolean formula expressed in CNF such that each disjunction contains at most k variables. 3-SAT is NP-complete (like any other k-SAT problem with k>2) while 2-SAT can be solved in Polynomial Time . SEE ALSO EXTERNAL LINKS |
|
|