◀ ▲ ▶Branches / Logic / Proof

Proof

(related to Lemma: Construction of Conjunctive and Disjunctive Canonical Normal Forms)

Context

• Let $\phi$ be a proposition with a Boolean function $f_\phi.$
• Without loss of generality, we can assume that $\phi$ contains exactly $n\ge 1$ prime propositions $x_1,\ldots,x_n.$¹
• Let $T$ be the corresponding truth table of $f_\phi$. Note that
  • $T$ contains $n+1$ colums: $n$ columns for the valuations of each prime proposition $[[p_i]]_I$ and one column for the valuation $[[\phi]]_I.$
  • $T$ has either rows with $[[\phi]]_I=0$ only or with $[[\phi]]_I=1$ only, or both types of rows.

Existence of $\operatorname{dcnf}(\phi)$, respectively $\operatorname{ccnf}(\phi)$

1. Assume that there are only rows with $[[\phi]]_I=1$, then continue with step 3.
2. Assume that there are only rows with $[[\phi]]_I=0$, then continue with step 4.
3. If we have $d\ge 1$ rows with $[[\phi]]_I=1,$ then we construct the minterms $m_1,\ldots,m_d,$ as follows:
   • For the $j$-th row with the valuation $[[\phi]]_I=1$, $j=1,\ldots,d$: * If $[[p_i]]_I=0$ in the $j$-th row, then take the literal $\neg p_i$, otherwise take the literal $p_i$. * Form the conjunction of these literals to form the minterm $m_j:=(\neg)p_1\wedge\ldots\wedge(\neg)p_n$ of the $j$-th row.
   • Form the disjunction of all minterms to form the disjunctive canonical normal form $\operatorname{dcnf}(\phi):=m_1\vee \ldots\vee m_d.$
4. If we have $c\ge 1$ rows with $[[\phi]]_I=0,$ then we construct the maxterms $M_1,\ldots,M_c,$ as follows:
   • For the $j$-th row with the valuation $[[\phi]]_I=0$, $j=1,\ldots,c$: * If $[[p_i]]_I=0$ in the $j$-th row, then take the literal $p_i$, otherwise take the literal $\neg p_i$. * Form the disjunction of these literals to form the maxterm $M_j:=(\neg)p_1\vee\ldots\vee(\neg)p_n$ of the $j$-th row.
   • Form the conjunction of all maxterms to form the conjunctive canonical normal form $\operatorname{ccnf}(\phi):=M_1\wedge \ldots\wedge M_c.$

It follows that there is either the disjunctive canonical normal form $\operatorname{dcnf}(\phi)$, or the conjunctive canonical normal form $\operatorname{ccnf}(\phi)$, or both simultaneously, depending on the cases 1 to 4.

Uniqueness of $\operatorname{dcnf}(\phi)$, respectively $\operatorname{ccnf}(\phi)$

• First of all, note that each literal of all minterms and maxterms is clearly defined by above construction and depends on the valuations $[[\phi]]_I$ in $j$-th row and $[[p_i]]_I$ in $i$-th column of the truth table.
• Next, the semantics of each minterm $m_j=(\neg)p_1\wedge\ldots\wedge(\neg)p_n$ does not change with the order of literals because of the commutativity and associativity of conjunction "$\wedge$".
• The same holds for each maxterm $M_j=(\neg)p_1\vee\ldots\vee(\neg)p_n$ due of the commutativity and associativity of disjunction "$\vee$".
• By the same argument, the semantics of the $\operatorname{dcnf}(\phi)=m_1\vee \ldots\vee m_d$, respectively $\operatorname{dcnf}(\phi)=M_1\wedge \ldots\wedge M_c$ does not change with the order of the minterms $m_j$, respectively maxterms $M_j.$

It follows that the constructed $\operatorname{dcnf}(\phi)$ respectively $\operatorname{ccnf}(\phi)$ are unique except for the order of minterms resp. maxterms and literals in each minterm, respectively maxterms.

Correctness of $\operatorname{dcnf}(\phi)$, respectively $\operatorname{ccnf}(\phi)$

We want to verify, that $\phi$, $\operatorname{dcnf}(\phi)$ and $\operatorname{ccnf}(\phi)$ indeed represent the same Boolean function. * If $\operatorname{dcnf}(\phi)$ exists, then: * According to the definition of conjunction, each minterm $m_j=(\neg)p_1\wedge\ldots\wedge(\neg)p_n$ is valued true, if and only if each of its literals $(\neg)p_i$ is valued true. * According to the lemma about the unique valuation of minterms, there is exactly one $n$-tuple of truth values assigned to $p_1,\ldots,p_n$, for which $m_j$ is true. * Therefore, $m_j$ is by its construction true, if and only if $\phi$ is true for the same $n$-tuple of truth values assigned to $p_1,\ldots,p_n$. * The disjunction $m_1\vee\ldots\vee m_d$ iterates through all and only such tuples for which $m_j$ and $\phi$ are valued true, and connects them by the logical "or". * By definition of disjunction, the whole $\operatorname{dcnf}(\phi)$ is true if and only if at least one minterm is true. * Thus, $\operatorname{dcnf}(\phi)$ is true if and only if $\phi$ is true. * Thus, $\operatorname{dcnf}(\phi)$ represents the same Boolean function as $\phi$, formally $f_\phi=f_{\operatorname{dcnf}(\phi)}.$ * If $\operatorname{ccnf}(\phi)$ exists, then: * According to the definition of disjunction, each maxterm $M_j=(\neg)p_1\vee\ldots\vee(\neg)p_n$ is valued false, if and only if each of its literals $(\neg)p_i$ is valued false. * According to the lemma about the unique valuation of maxterms, there is exactly one $n$-tuple of truth values assigned to $p_1,\ldots,p_n$, for which $M_j$ is false. * Therefore, $M_j$ is by its construction false, if and only if $\phi$ is false for the same $n$-tuple of truth values assigned to $p_1,\ldots,p_n$. * The conjunction $M_1\wedge\ldots\wedge M_c$ iterates through all and only such tuples and connects them by the logical "and". * By definition of conjunction, the whole $\operatorname{ccnf}(\phi)$ is false if and only if at least one maxterm is false. * Thus, $\operatorname{ccnf}(\phi)$ is false if and only if $\phi$ is false. * Thus $\operatorname{ccnf}(\phi)$ represents the same Boolean function as $\phi$, formally $f_\phi=f_{\operatorname{ccnf}(\phi)}.$

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

Github:

References

Bibliography

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

Footnotes