Conjunctive Normal Form (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). Examples of conjunctive normal forms include
where 
denotes OR, 
denotes AND, and 
denotes NOT (Mendelson 1997, p. 30).
Every statement in logic consisting of a combination of multiple 
, 
, and 
s can be written in conjunctive normal form.
An expression can be put in conjunctive normal form using the Wolfram Language using the following code:
ConjunctiveNormalForm[f_] := Not[LogicalExpand[Not[f]]] //. { Not[a_Or] :> And @@ (Not /@ List @@ a), Not[a_And] :> Or @@ (Not /@ List @@ a) }
See also
AND, Disjunctive Normal Form, Literal, Negation,Normal Form, OR, Statement Letter
Explore with Wolfram|Alpha
References
Mendelson, E. Introduction to Mathematical Logic, 4th ed. London: Chapman & Hall, p. 30, 1997.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Conjunctive Normal Form." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConjunctiveNormalForm.html