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
(1)
| |
(2)
| |
(3)
| |
(4)
|
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) }