Skip to main content
added 4 characters in body
Source Link
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'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' indexationindex 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.

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' 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 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.

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.

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' 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 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 benefitbenefitted, had the author provided implementation examples in a computer language of their choice or even in pseudocode.

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' 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 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 greatly benefit, had the author provided implementation examples in a computer language of their choice or even in pseudocode.

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' 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 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.

added 2 characters in body
Source Link
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'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' 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 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 greatly benefit if, had the author provided implementation examples in a computer language of their choice or even in pseudocode.

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' 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 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 greatly benefit if the author provided implementation examples in a computer language of their choice or even in pseudocode.

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' 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 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 greatly benefit, had the author provided implementation examples in a computer language of their choice or even in pseudocode.

added 2 characters in body
Source Link
V.V.T
  • 4.6k
  • 9
  • 10
Loading
it is a new answer, not an updated version.
Source Link
V.V.T
  • 4.6k
  • 9
  • 10
Loading
it is a new answer, not an updated version.
Source Link
V.V.T
  • 4.6k
  • 9
  • 10
Loading
Source Link
V.V.T
  • 4.6k
  • 9
  • 10
Loading