# DNF

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

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

Title DNF DNF 2013-03-22 14:14:08 2013-03-22 14:14:08 rspuzio (6075) rspuzio (6075) 4 rspuzio (6075) Definition msc 03B05 disjunctive normal form CNF AtomicFormula