Conjunctive Normal Form

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

(A v B) ^ (!A v C)
A v B
A ^ (B v C),

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


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 Web Resource.

Subject classifications