CNF

A propositional formula is a CNF formula, meaning Conjunctive Normal Form, if it is a conjunction of disjunction of literals (a literal is a propositional variable or its negation). Hence, a CNF is a formula of the form: $K_{1}\wedge K_{2}\wedge\ldots\wedge K_{n}$, where each $K_{i}$ is of the form $l_{i1}\vee l_{i2}\vee\ldots\vee l_{im}$ for literals $l_{ij}$ and some $m$ (which can vary for each $K_{i}$).

Example: $(x\vee y\vee\neg z)\wedge(y\vee\neg w\vee\neg u)\wedge(x\vee v)$.

Title CNF CNF 2013-03-22 14:02:35 2013-03-22 14:02:35 rspuzio (6075) rspuzio (6075) 7 rspuzio (6075) Definition msc 03B05 conjunctive normal form DNF AtomicFormula