Chapter: Normal Forms in $PL0$

We have seen that for each proposition $\phi$ there is a Boolean function $f_\phi$ such that $f_\phi=1$ if and only if $\models \phi$. But do propositions and Boolean functions form a one-to-one relationship? The answer to that question is '"no". We will now provide some examples.

Examples: 1

  1. Section: Examples of Propositions With Different Syntactic Forms but the Same Boolean Function
  2. Definition: Canonical Normal Form
  3. Definition: Literals, Minterms, and Maxterms
  4. Lemma: Unique Valuation of Minterms and Maxterms
  5. Definition: Conjunctive and Disjunctive Canonical Normal Forms
  6. Lemma: Construction of Conjunctive and Disjunctive Canonical Normal Forms

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