You are here

Notation for DNF, CNF

15 June, 2015 - 17:02
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at

Sometimes you'll see the form of CNF and DNF expressed in a notation with subscripts.

  • DNF is iψi, where each clause φi is j λj , where each λ is a propositional variable (Prop), or a negation of one (¬Prop).
  • CNF is iψi, where each clause ψi is jλj , where each λ is again a propositional variable (Prop), or a negation of one (¬Prop).

For example, in the CNF formula (ab) ∧ (¬abc) ∧ (¬a¬b) we have φ2 = ¬abc within that clause we have λ1 = ¬a.

One question this notation brings up:

  • What is the disjunction of a single clause? Well, it's reasonable to say that ψ ≡ ψ. Note that this is also equivalent to ψfalse.
  • What is the disjunction of zero clauses? Well, if we start with ψ ≡ ψfalse and remove the ψ, that leaves us with false! Alternately, imagine writing a function which takes a list of booleans, and returns the ∨ of all of them the natural base case for this recursive list-processing program turns out to be false. Indeed, this is the accepted defnition of the empty disjunction. It follows from false being the identity element for ∨. Correspondingly, a conjunction of zero clauses is true.

Actually, that subscript notation above isn't quite correct: it forces each clause to be the same length, which isn't actually required for CNF or DNF. For fun, you can think about how to patch it up. (Hint: double-subscripting.)

Note that often one of these forms might be more concise than the other. Here are two equivalently verbose ways of encoding true, in CNF and DNF respectively: (a¬a) ∧ (b¬b) ∧ ... ∧ (z¬z) is equivalent to (abc ∧ ... ∧ yz) ∨ (abc ∧ ... ∧ y¬z) ∨ (abc ∧ ... ∧¬yz) ∨ ... ∨ (¬a¬b ∧ ... ∧¬y¬z). The first version corresponds to enumerating the choices for each location of a WaterWorld board; it has 26 two-variable clauses. This may seem like a lot, but compare it to the second version, which corresponds to enumerating all possible WaterWorld boards explicitly: it has all possible 26-variable clauses; there are 226 ≈ 64 billion of them!