1.3 Advanced Theorems: Consensus Theorem, Transposition & Redundancy

Back to Digital Logic Notes

📚Module 01: Understanding Digital Electronics & Boolean LawsTopic 1.3⏱️14 min read

🎯High-Yield For:University Semester Exams • Hardware Engineering Rounds • Foundational Computing

💡 Core Intuition: The Useless Redundant Safety Net

Imagine an aerial acrobatics performance where an acrobat is catching teammates.

🍳 The Everyday Analogy: The Backup Spotter

Suppose two safety protocols guard the acrobat:

• Protocol 1 (Active when Spotter A is on duty): "If Spotter A is standing, Guard B catches the acrobat ($AB$)."
• Protocol 2 (Active when Spotter A is resting): "If Spotter A is absent ($\bar{A}$), Guard C catches the acrobat ($\bar{A}C$)."
• Protocol 3 (The redundant committee rule): "If both Guard B and Guard C are in the building, one of them will catch the acrobat ($BC$)."

Is Protocol 3 ever strictly needed?
At any instant in time, Spotter A is either standing ($A = 1$) or absent ($A = 0$). If $A = 1$, Protocol 1 is active. If $A = 0$, Protocol 2 is active. Protocol 3 ($BC$) never provides any protection that is not already 100% guaranteed by the first two rules! It is a redundant consensus rule that wastes payroll.

💻 Bridging to Computer Science

In digital circuit engineering, adding unneeded product or sum terms consumes physical silicon area, increases parasitic gate capacitance, burns dynamic switching power, and slows down clock frequencies.

The Consensus Theorem (also known as the Theorem of Redundancy) provides an algebraic test to instantly detect and eliminate redundant terms from Boolean expressions without drawing large Karnaugh maps: $AB + \bar{A}C + BC = AB + \bar{A}C$

Here, the term $BC$ is the consensus of $AB$ and $\bar{A}C$. Because it is covered under every possible state of variable $A$, it can be eliminated with zero change to the circuit's truth table.

---

📑Table of Contents

• 🔬 The Consensus Theorem: Derivation & Structural Rules
  • 1. The "Rule of Three" Identification Checklist
• ⚡ The Transposition Theorem
• 🧮 Summary of Redundancy Elimination Theorems
• 🏭 Real-World Production Context: Glitch-Free Hazard Elimination
  • The Physical Problem: Unequal Transistor Propagation Delays
  • The Production Solution: Re-Inserting the Consensus Term!
• 📐 Numerical Applications & Worked Examples
  • Example 1: Multi-Variable Extended Consensus Elimination
  • Example 2: POS Dual Consensus Simplification
  • Example 3: Complex Multi-Term Redundancy Elimination
• 🎯 Exam & Interview Pitfall Check

---

🔬 The Consensus Theorem: Derivation & Structural Rules

The Consensus Theorem exists in two dual formulations: the Sum of Products (SOP) form and the Product of Sums (POS) form.

📐Theorem 1.3A: SOP Consensus Theoremtheorem

$$AB + \bar{A}C + BC = AB + \bar{A}C$$

🔍Formal First-Principles Proof of SOP Consensusproof

$$\begin{aligned} \text{LHS} &= AB + \bar{A}C + BC \\ &= AB + \bar{A}C + BC(1) \quad &&\text{[Identity Law: } X \cdot 1 = X\text{]} \\ &= AB + \bar{A}C + BC(A + \bar{A}) \quad &&\text{[Complementation Law: } A + \bar{A} = 1\text{]} \\ &= AB + \bar{A}C + ABC + \bar{A}BC \quad &&\text{[Distributive Expansion]} \\ &= (AB + ABC) + (\bar{A}C + \bar{A}BC) \quad &&\text{[Associative and Commutative Regrouping]} \\ &= AB(1 + C) + \bar{A}C(1 + B) \quad &&\text{[Distributive Factoring]} \\ &= AB(1) + \bar{A}C(1) \quad &&\text{[Dominance Law: } 1 + X = 1\text{]} \\ &= AB + \bar{A}C = \text{RHS} \quad \blacksquare \end{aligned}$$

📐Theorem 1.3B: POS Dual Consensus Theoremtheorem

$$(A + B)(\bar{A} + C)(B + C) = (A + B)(\bar{A} + C)$$

1. The "Rule of Three" Identification Checklist

To rapidly detect a consensus term in any algebraic expression:

1. Three Terms: The expression contains exactly three terms.
2. Three Variables: Exactly three distinct variables ($A, B, C$) are involved, each appearing exactly twice.
3. One Complemented Variable: Exactly one variable appears complemented in one term and uncomplemented in the other ($A$ and $\bar{A}$).
4. The Consensus Term: The product (or sum in POS) of the remaining non-opposing literals is the consensus term ($BC$), which can be safely pruned.

Consensus Theorem: SOP vs. POS Dual Formulations

Comparing the algebraic reduction rules across two-level AND-OR vs OR-AND circuits

SOP Form

Sum-of-Products Consensus

➕

Dominant Architecture / DomainAND-OR Logic & Minterm Simplification

• •Expression: AB + A'C + BC = AB + A'C
• •Opposing variable: A appears true in term 1, complemented in term 2
• •Consensus product: BC is absorbed into the primary terms
• •Eliminates one complete AND gate from physical hardware

"Product of non-opposing literals is redundant."

POS Form

Product-of-Sums Consensus

✖️

Dominant Architecture / DomainOR-AND Logic & Maxterm Simplification

• •Expression: (A + B)(A' + C)(B + C) = (A + B)(A' + C)
• •Opposing variable: A appears true in term 1, complemented in term 2
• •Consensus sum: (B + C) is absorbed into the primary sum terms
• •Eliminates one complete OR gate from physical hardware

"Sum of non-opposing literals is redundant."

---

⚡ The Transposition Theorem

The Transposition Theorem is an advanced factoring identity that allows immediate conversion between product-of-sums and sum-of-products forms:

📐Theorem 1: Standard Transposition Identitytheorem

$$(A + B)(A + C) = A + BC$$

📐Theorem 2: Complement Transposition (Circuit Conversion Tool)theorem

$$(A + B)(\bar{A} + C) = AC + \bar{A}B$$

🔍Proof of Complement Transpositionproof

$$\begin{aligned} (A + B)(\bar{A} + C) &= A\bar{A} + AC + B\bar{A} + BC \\ &= 0 + AC + \bar{A}B + BC \quad &&\text{[Complementation Law: } A\bar{A} = 0\text{]} \\ &= AC + \bar{A}B + BC \\ &= AC + \bar{A}B \quad &&\text{[By Consensus Theorem on } AC + \bar{A}B + BC\text{]} \quad \blacksquare \end{aligned}$$

📐Dual of Complement Transpositiontheorem

$$AB + \bar{A}C = (A + C)(\bar{A} + B)$$

This allows hardware designers to convert directly between two-level AND-OR and OR-AND circuits with zero algebraic intermediate expansions.

---

🧮 Summary of Redundancy Elimination Theorems

Beyond the 3-variable consensus theorem, three auxiliary redundancy rules are used extensively in circuit minimization:

Rule Name	Boolean Algebraic Identity	Operational Mechanics
Rule 1: Simple Absorption	$A + AB = A$	The term $AB$ is completely absorbed by literal $A$.
Rule 2: Complementary Absorption	$A + \bar{A}B = A + B$	The complemented literal $\bar{A}$ is cancelled by the isolated $A$.
Rule 3: Dual Complementary Absorption	$A(\bar{A} + B) = AB$	Expanding yields $A\bar{A} + AB = 0 + AB = AB$.
Rule 4: Common Factor Cancellation	$(A + B)(A + \bar{B}) = A$	Expands to $A + B\bar{B} = A + 0 = A$.

Verify gate behaviors and circuit outputs in the interactive tool below:

Digital Logic SimulatorY = A + B

Interactive Gate Synthesis & Equivalence Verification

Test how reduced algebraic expressions compute identical outputs to larger unminimized networks

Output Y =0(LOW / 0V)

📊 Live Truth Table

Input A	Input B	Output Y
0	0	0
0	1	1
1	0	1
1	1	1

💡 Physics & Switch Analogy:

Switches in Parallel: Current flows if Switch A OR Switch B (or both) are closed.

---

🏭 Real-World Production Context: Glitch-Free Hazard Elimination

In pure mathematical logic, the consensus term is 100% redundant and should always be removed to minimize silicon area.

However, in high-speed asynchronous hardware design, the consensus term serves a vital physical purpose: preventing static-1 dynamic hazards (glitches)!

The Physical Problem: Unequal Transistor Propagation Delays

Consider the physical circuit implementing $F = AB + \bar{A}C$: Suppose $B = 1$ and $C = 1$. The theoretical output is: $F = A(1) + \bar{A}(1) = A + \bar{A} = 1$ The output should remain continuously HIGH ($1$) regardless of the value of $A$.

However, in real silicon:

• The signal $A$ feeds directly into Gate 1 ($AB$).
• The complemented signal $\bar{A}$ must pass through an inverter before reaching Gate 2 ($\bar{A}C$).
• The inverter introduces a physical propagation delay $t_{pd} \approx 15\text{ ps}$.

When input $A$ transitions from $1 \to 0$:

1. $A$ becomes $0$ immediately $\implies$ Gate 1 output drops to $0$.
2. For $15\text{ ps}$, the inverter output has not yet transitioned to $1$!
3. During this $15\text{ ps}$ window, both inputs to the OR gate are simultaneously $0$!
4. The output $F$ momentarily drops from $1 \to 0 \to 1$, generating an erroneous glitch pulse (static-1 hazard) that can falsely trigger a downstream register or clock line!

Time Instant	Primary Input $A$	Inverter Output $\bar{A}$ ($t_{pd}$ delay)	Product $AB$ ($B=1$)	Product $\bar{A}C$ ($C=1$)	Net Output $F = AB + \bar{A}C$
Initial State ($t < 0$)	1	0	1	0	1 (Stable High)
Transient Glitch ($0 < t < t_{pd}$)	0 (Dropped)	0 (Delayed)	0	0	0 (HAZARD GLITCH!)
Final State ($t > t_{pd}$)	0	1 (Arrived)	0	1	1 (Restored High)

The Production Solution: Re-Inserting the Consensus Term!

By intentionally adding the consensus term $BC$ back into the circuit ($F = AB + \bar{A}C + BC$):

• When $B = 1$ and $C = 1$, the term $BC = 1 \cdot 1 = 1$ independently holds the output HIGH throughout the entire $A \to 0$ transition.
• The hazard glitch is completely eliminated!

[!TIP] In combinational logic minimization, eliminate the consensus term to save area. In asynchronous state machine design, intentionally retain the consensus term to guarantee hazard-free transitions.

---

📐 Numerical Applications & Worked Examples

Example 1: Multi-Variable Extended Consensus Elimination

Problem Statement:
Simplify the 4-variable Boolean function by detecting and eliminating redundant consensus terms:

$$F(A, B, C, D) = AB + \bar{A}CD + BCD$$

Step-by-Step Solution:

1. Analyze the Terms for the Consensus Pattern:

   • Term 1: $AB$ (Contains $A$ and $B$).
   • Term 2: $\bar{A}CD$ (Contains $\bar{A}$ and $CD$).
   • Term 3: $BCD$ (Contains $B$ and $CD$).

2. Evaluate the Three Conditions:

   • Variable $A$ appears in true form in Term 1 ($A$) and in complemented form in Term 2 ($\bar{A}$).
   • The remaining literals in Term 1 are $B$.
   • The remaining literals in Term 2 are $CD$.
   • Multiplying the remaining literals yields $B \cdot (CD) = BCD$.

3. Eliminate the Consensus Term:
   Because Term 3 is the exact consensus product of Term 1 and Term 2, it is redundant:

   $$F = AB + \bar{A}CD + \cancel{BCD} = AB + \bar{A}CD$$

4. Final Minimized Expression:

   $$F = AB + \bar{A}CD$$

---

Example 2: POS Dual Consensus Simplification

Problem Statement:
Minimize the following product-of-sums expression using the dual consensus theorem:

$$F = (A + \bar{B})(B + C)(A + C)$$

Step-by-Step Solution:

1. Examine the Three Sum Terms:

   • Term 1: $(A + \bar{B})$
   • Term 2: $(B + C)$
   • Term 3: $(A + C)$

2. Check for Opposing Literals:

   • Variable $B$ appears complemented ($\bar{B}$) in Term 1 and true ($B$) in Term 2.
   • The non-opposing literal in Term 1 is $A$.
   • The non-opposing literal in Term 2 is $C$.

3. Form the Consensus Sum:
   Combining the non-opposing literals gives $(A + C)$.

4. Eliminate the Redundant Consensus Sum Term:
   Term 3 ($(A + C)$) is the exact consensus sum of Term 1 and Term 2:

   $$F = (A + \bar{B})(B + C)\cancel{(A + C)} = (A + \bar{B})(B + C)$$

---

Example 3: Complex Multi-Term Redundancy Elimination

Problem Statement:
A digital logic network implements the Boolean function:

$$F(A, B, C, D) = AB + \bar{A}C + BC + \bar{C}D + \bar{B}D$$

Simplify the expression to its minimal sum-of-products representation using algebraic reduction rules.

Step-by-Step Solution:

1. First Pass: Apply Consensus on Terms 1, 2, and 3:
   Look at $AB + \bar{A}C + BC$:

   • $A$ and $\bar{A}$ are opposing.
   • $BC$ is the consensus term.
   $$F = AB + \bar{A}C + \cancel{BC} + \bar{C}D + \bar{B}D = AB + \bar{A}C + \bar{C}D + \bar{B}D$$

2. Second Pass: Look for Consensus between $\bar{A}C$ and $\bar{C}D$:
   Look at $\bar{A}C + \bar{C}D$:

   • $C$ and $\bar{C}$ are opposing literals.
   • The remaining literals are $\bar{A}$ and $D$, forming the potential consensus term $\bar{A}D$. (This term is not present, so no elimination here).

3. Third Pass: Group $AB$ with $\bar{B}D$:
   Look at $AB + \bar{B}D$:

   • $B$ and $\bar{B}$ are opposing literals.
   • The consensus product is $AD$. (Not present).

4. Fourth Pass: Apply Complementary Absorption ($X + \bar{X}Y = X + Y$):
   Regroup terms by factoring $D$:

   $$F = AB + \bar{A}C + D(\bar{C} + \bar{B})$$

   Using De Morgan's on $(\bar{C} + \bar{B}) = \overline{BC}$:

   $$F = AB + \bar{A}C + D\overline{BC}$$

   Notice that when $AB + \bar{A}C = 1$, the function is already satisfied. Let us test if $D\overline{BC}$ can be simplified: Recall that from consensus, $AB + \bar{A}C$ covers all states of $BC$ except when $B=C=0$ or one is $0$. Therefore, the minimal irredundant representation is:

   $$F = AB + \bar{A}C + \bar{C}D + \bar{B}D$$

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• How can you distinguish between an absorption law application and a consensus theorem application?
  Absorption involves terms with subset relationships: one term contains a subset of the literals of the other term (e.g., $A + AB = A$, where $A \subseteq AB$). Consensus involves terms where no term is a subset of another; instead, two terms contain complementary instances of a variable ($A$ and $\bar{A}$), and the third term consists of the cross-product of the remaining literals ($AB + \bar{A}C + BC$).

• Does eliminating a consensus term ever change the circuit's static truth table?
  Never. A consensus term is algebraically equivalent to adding $0$ in SOP form or multiplying by $1$ in POS form. The truth table output remains 100% identical for all $2^n$ binary input combinations.

Common Interview Traps

• Trap: Prematurely eliminating the wrong term in a consensus triplet.
  In $AB + \bar{A}C + BC$, students sometimes mistakenly cancel $AB$ or $\bar{A}C$. Remember: you can ONLY eliminate the term composed of the non-opposing literals ($BC$). The terms containing the complemented pair ($A$ and $\bar{A}$) MUST be retained!

• Trap: Overlooking consensus when terms have additional variables.
  Consensus applies even if the terms have extra literals. For example, in $AB + \bar{A}CDE + BCDE$, the opposing variable is $A / \bar{A}$. The consensus of $B$ and $CDE$ is $BCDE$, so $BCDE$ is completely redundant!

---

🗺️View Complete Digital Logic Roadmap & Syllabus

← Previous Topic1.2 Postulates & Fundamental Laws of Boolean AlgebraNext Topic →2.1 Basic Logic Gates: Operations, Truth Tables & Switch Models