We have seen in previous examples that propositions and the corresponding Boolean functions, in general, do not establish a one-to-one relationship. We want to find a syntactic form which establishes a one-to-one relationship with the corresponding Boolean function.

Definition: Canonical Normal Form

Let a $\phi$ be a proposition with a given syntactic form and let $f_\phi$ be corresponding Boolean function. We call a syntax $\operatorname{cnf}(\phi)$ which establishes a one-to-one relationship with $f_\phi$ a canonical normal form of $\phi$.

Definitions: 1 2

Thank you to the contributors under CC BY-SA 4.0!




  1. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015