Conjunctive normal form
A propositional formula of the form
where each , ; , is either an atomic formula (a variable or constant) or the negation of an atomic formula. The conjunctive normal form (*) is a tautology if and only if for any one can find both formulas and among the , for some atomic formula . Given any propositional formula , one can construct a conjunctive normal form equivalent to it and containing the same variables and constants as . This is called the conjunctive normal form of .
Conjunctive normal form. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Conjunctive_normal_form&oldid=13117