logicconditional-statementsboolean-logicconjunctive-normal-form

Writing conditions in Conjunctive Normal Form


Conjunctive Normal Form (CNF) is a standardized notation for propositional formulas that dictate that every formula should be written as a conjunction of disjunctions. Every boolean formula can be converted to CNF. So for example:

A | (B & C)

Has a representation in CNF like this:

(A | B) & (A | C)

Is it a best practice in programming to write conditionals in CNF?


Solution

  • No, this is not a good idea. Conjunctive normal form is primarily used in theoretical computer science. There are algorithms to solve formulas in CNF, and proofs about time complexity and NP-hardness.

    From a pragmatic point of view, you should write code using Boolean operators that most "naturally" describe the logic. This means taking full advantage of nested expressions, operators like XOR, negation, and so on. As you exemplified, CNF often contradicts this goal of "naturalness" because the expression is longer and often repeats subexpressions.

    As a theoretical side note, in the worst case, an unrestricted Boolean formula containing n operators can transform into a CNF formula whose length is exponential in n. So CNF can potentially blow up a formula by very large amount. A sequence of examples illustrating this behavior: