Skip to main content
1 of 7
V.V.T
  • 4.6k
  • 9
  • 10

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 believe that the intent of the author of the book, in the section MINIMIZATION OF MULTILEVEL CIRCUITS USING DON’T CARES, is to show how one can, given the circuit of FIGURE 3.52, transform the source expression for f $$ f = p·\overline{b} + \overline{p}·\overline{c} + q·c $$ into the minimized function expression f_{minimized} $$ f_{minimized} = \overline{p}·\overline{c} + q $$

But having diligently perused the text, for the moment I'm able only to prove the equivalence of two Boolean expressions, f and f_{minimized}. To be sure, it can be done by direct substitution of source variables a, b, and c into both expressions, but let us use the concepts of the section (SDCs and the universal quantification) to the maximum. Maybe it will lead eventually to mastering these concepts in an instrumental way. I suspect that Boolean/algebraic division of the logical expressions may have something to do with the task, but for now it is only a guess.

This being said, I set out to prove the equivalence of two Boolean expressions hard way, using SDCs and the universal quantification as much as I can.

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 $$ The f and f_{minimized} differ by the terms p + qc and q respectively. If p'c'=true, f is true, and the f_{minimized} is also true. So we examine the case p'c'=false. To prove the identity f = f_{minimized} for the p'c'=false case, we multiply both differing terms by (p'c')', which is true for the case under consideration (p'c'=false): $$ \overline{(\overline{p}·\overline{c})} = (p+c);\\ @f : (p + q·c)·(p+c) = p + q·c;\\ @f_{minimized}: q·(p+c) = p·q + q·c; $$ To cut things short, we express p and q via source variables a, b, and c (but the universal quantification w.r.t. two variables, a and b, can also be used so that we stay at the second level logic blocks with p and q variables): $$ p = \overline{(a+b)} = \overline{a}·\overline{b};\\ p·q = (\overline{a}·\overline{b})·(\overline{b}+\overline{c}) = \overline{a}·\overline{b} + \overline{a}·\overline{b}·\overline{c} = \overline{a}·\overline{b}; $$ This proves that if p'c' = false, p+qc = pq+qc. We arrive at the identity of differing terms in the f and f_{minimized} expressions.

If p'c'=true, both f and f_{minimized} are true due to the term p'c'. For the case p'c'=false we also have proved the identity of f and f_{minimized} expressions.

Maybe it is not our fault that we stuck at the derivation of the minimized function. The book urgently needs the redaction on many points. For example, the Karnaugh maps' indexation 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 typo: $$ f(x_1, x_2, ... , x_i, ... , x_n) = f_{\overline{x}_1}·f_{x_i} $$ Pay attention to indices of the right-hand expression: x_1,x_i.

I would not recommend this book as a textbook.

V.V.T
  • 4.6k
  • 9
  • 10