(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.
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).$$
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.
