A propositional formula is a CNF formulaMathworldPlanetmathPlanetmath, meaning Conjunctive Normal FormMathworldPlanetmath, if it is a conjunctionMathworldPlanetmath of disjunctionMathworldPlanetmath of literalsMathworldPlanetmath (a literal is a propositional variable or its negationMathworldPlanetmath). Hence, a CNF is a formula of the form: K1K2Kn, where each Ki is of the form li1li2lim for literals lij and some m (which can vary for each Ki).

Example: (xy¬z)(y¬w¬u)(xv).

Title CNF
Canonical name CNF
Date of creation 2013-03-22 14:02:35
Last modified on 2013-03-22 14:02:35
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 7
Author rspuzio (6075)
Entry type Definition
Classification msc 03B05
Synonym conjunctive normal form
Related topic DNF
Related topic AtomicFormula