As a preliminary notice -- although the formula for S_{a}
you write down in your question may be just a typo -- pay attention that the universal quantification of S w.r.t. variable a
is a product of SDCs for a
and a'
:
$$
V_{a}S = S_{\overline{a}}·S_{a} = p·b + \overline{q}·\overline{b} + q·b·c + \overline{q}·\overline{c}
$$
Also, I cannot mark variables with overlines in text inlines and so will follow your convention of using a single quote character for this purpose.
I've downloaded a copy of "PRINCIPLES OF MODERN DIGITAL DESIGN" and gleaned from the section 3.2 MINIMIZATION OF BOOLEAN EXPRESSIONS that the "minimization" operation 1) reduces the number of terms in the expression and 2) reduces the number of literals in the expression.
The task is: given the circuit of FIGURE 3.52, "minimize" the source expression for the circuit output f
$$
f = p·\overline{b} + \overline{p}·\overline{c} + q·c
$$
We start with adding, rather than eliminating, a term, which will simplify the pb'
term. Being one of the terms that sum up to VaS
, the term pb
is the SDC for the second-level logic block. We can add it to the source expression for f, as we can do with any SDC:
$$
f = p·\overline{b} + \overline{p}·\overline{c} + q·c + p·b = \overline{p}·\overline{c} + p·(\overline{b} + b) + q·c = \overline{p}·\overline{c} + p + q·c
$$
We still have three terms, but we eliminated the dependence on variable b
.
Notice that p
does not depend on c
and so the term p'c'
is irreducible. To reduce the other terms, we consider the negation of p + q·c
:
$$
\overline{(p + q·c)} = \overline{p}·(\overline{q·c}) = \overline{p}·(\overline{q} + \overline{c}) = \overline{p}·\overline{q} + \overline{p}·\overline{c};
$$
If p'c' = true
, then, irrespective to the other term's values, f = true
. Therefore, we can go on to transform the terms p + q·c
, substituting in these terms for the case p'c' = false
$$
\overline{(p + q·c)} = \overline{p}·\overline{q};
$$
Backtracking on the negation of the terms being added to p'c'
, we arrive at the equation, provided p'c' = false
:
$$
(p + q·c) = \overline{(\overline{p}·\overline{q})} = p + q = \overline{a}·\overline{b} + \overline{b} + \overline{c} = \overline{b} + \overline{c} = \overline{b·c} = q
$$
Recall, (p + q·c) = q
only valid iff p'c' = false
. Instead of three terms p'·c' + p + q·c
, we have two terms p'·c' + q
for the case p'c' = false
.
Combining the cases p'c' = true
and p'c' = false
, we arrive at the "minimized" function f
of the book:
$$
f_{minimized} = \overline{p}·\overline{c} + q
$$
I would not put a blame on a student who stuck at the derivation of the minimized function in the section MINIMIZATION OF MULTILEVEL CIRCUITS USING DON’T CARES. The book urgently needs the redaction on many points. For example, the Karnaugh maps' index ordering differs in figures and in text (Figure 3.10, and all the other Karnaugh maps). In the section we discuss, the definition of the universal quantification has a typo:
$$
f(x_1, x_2, ... , x_i, ... , x_n) = f_{\overline{x}_1}·f_{x_i}
$$
instead of
$$
f(x_1, x_2, ... , x_i, ... , x_n) = f_{\overline{x}_i}·f_{x_i}
$$
Let alone these typos, the explanation of minimization algorithms would have greatly benefitted, had the author provided implementation examples in a computer language of their choice or even in pseudocode.