Conjunctive Normal Form

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

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 👁 v
denotes OR, 👁 ^
denotes AND, and 👁 !
denotes NOT (Mendelson 1997, p. 30).

Every statement in logic consisting of a combination of multiple 👁 ^
, 👁 v
, 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

Conjunctive Normal Form

Cite this as:

Weisstein, Eric W. "Conjunctive Normal Form." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConjunctiveNormalForm.html

Subject classifications