Example: Examples of Canonical Normal Forms

(related to Chapter: Normal Forms in $PL0$)

After we learned in the "proof of the corresponding lemma":https://www.bookofproofs.org/branches/construction-of-conjunctive-and-disjunctive-canonical-normal-forms/proof/ how to construct canonical normal forms of any proposition $\phi,$ we are now prepared to apply the approach in practice. In any case, we will use the truth table of the corresponding Boolean function $f_\phi$ as a starting point.

Example 1

Our first example is a special case. Suppose, we have a proposition containing two Boolean variables $x,y,$ which is always valid $\models \phi.$ Then, by definition of validity, for every valuation of the two variables, the function $f_\phi=[[\phi]]_I$ will be valued true. Because there is no row for which $[[\phi]]_I=0$, we can construct only minterms and therefore there is only a disjunctive, but no conjunctive canonical normal form. The corresponding truth table and minterms are shown below:

$[[x]]_I$ $[[y]]_I$ $[[\phi]]_I$ Minterms
$1$ $1$ $1$ $x\wedge y$
$1$ $0$ $1$ $x\wedge \neg y$
$0$ $1$ $1$ $\neg x\wedge y$
$0$ $0$ $1$ $\neg x\wedge \neg y$

Connecting all minterms with a disjunction gives us the disjunctive canonical normal form:

$$\operatorname{dcnm}(\phi)=(x\wedge y) \vee (x\wedge \neg y) \vee (\neg x\wedge y) \vee (\neg x\wedge \neg y).$$

Example 2

Let us take a more complex example. Suppose that we are given a proposition $\psi$ with three variables $a,b,c$ connected as follows: $$\psi:=a\wedge((b\vee c)\wedge \neg a\Rightarrow c)\Leftrightarrow b.$$

Again, we calculate the truth table as well as the minterms and the maxterms, whenever it is possible: $[[a]]_I$| $[[b]]_I$| $[[c]]_I$| $[[\psi]]_I$| Minterms| Maxterms $0$ | $0$| $0$| $1$| $\neg a\wedge\neg b\wedge \neg c$| | $0$| $0$| $1$| $1$ | $\neg a\wedge \neg b\wedge c$| | $0$| $1$| $0$| $0$| | $a\vee \neg b\vee c$ | $0$| $1$| $1$| $0$| | $a\vee \neg b\vee \neg c$| $1$| $0$| $0$| $0$| | $\neg a\vee b\vee c$ $1$| $0$| $1$| $0$| | $\neg a\vee b\vee \neg c$ $1$| $1$| $0$| $1$| $a\wedge b\wedge \neg c$| $1$| $1$ | $1$| $1$| $a\wedge b\wedge c$|

Now, we connect the minterms and maxterms by disjunction and conjunction, respectively, and form the disjunctive (resp. the conjunctive) canonical normal forms:

$$\begin{array}{rcl}\operatorname{dcnm}(\psi)&=&(\neg a\wedge\neg b\wedge \neg c)\vee (\neg a\wedge \neg b\wedge c) \vee (a\wedge b\wedge \neg c) \vee (a\wedge b\wedge c)\\ \operatorname{ccnm}(\psi)&=&(a\vee \neg b\vee c) \wedge (a\vee \neg b\vee \neg c) \wedge(\neg a\vee b\vee c) \wedge (\neg a\vee b\vee \neg c).\end{array}$$

This example also demonstrates that the connectives implication "$\Rightarrow$" and equivalence "$\Leftrightarrow$" which were contained in $\psi$ could be replaced by the three "standard" connectives conjunction "$\wedge$", disjunction "$\vee$", and negation "$\neg$", without changing the corresponding Boolean function.

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