Related Concepts: 02 Boolean Algebra Significance & Circuit Minimization | 03 SOP, POS, Canonical & Standard Forms | 06 Boolean Algebra Puzzles & Exam Proofs

3.01 Boolean Algebra Foundations & Duality Principle

Statement of the Duality Principle

The Duality Principle states that every valid Boolean algebraic relation remains mathematically valid if all OR ($+$) and AND ($\cdot$) operators are interchanged, and all identity elements ($0$ and $1$) are interchanged, provided the variables and their complements are left unchanged.

$f(x_1,\dots ,x_n,+,\cdot ,0,1)=g(x_1,\dots ,x_n,+,\cdot ,0,1)⟹f(x_1,\dots ,x_n,\cdot ,+,1,0)=g(x_1,\dots ,x_n,\cdot ,+,1,0)$

---

1. Duality Transformation Rules

graph TD
    subgraph Duality Transformation Rules
        DualIn[Original Expression F] --> Rule1[Swap + and •]
        Rule1 --> Rule2[Swap 0 and 1]
        Rule2 --> Rule3[Keep Literals x and x' UNCHANGED]
        Rule3 --> DualOut[Dual Expression Dual-F]
    end
    
    subgraph Complement Transformation Rules
        CompIn[Original Expression F] --> CRule1[Swap + and •]
        CRule1 --> CRule2[Swap 0 and 1]
        CRule2 --> CRule3[INVERT Literals: x to x', x' to x]
        CRule3 --> CompOut[Complement Expression F']
    end

Dual vs. Complement

• Dual ($Dual(F)$): Swaps operators ($+\leftrightarrow \cdot$) and constants ($0\leftrightarrow 1$) ONLY. Variable complements are untouched ($x\to x,x^{\prime }\to x^{\prime }$).
• Complement ($F^{\prime }$ via De Morgan’s): Swaps operators ($+\leftrightarrow \cdot$), constants ($0\leftrightarrow 1$), AND complements every literal ($x\to x^{\prime },x^{\prime }\to x$).

---

2. Key Mathematical Proofs

Proof 1: Proving Absorption Law & Its Dual

Theorem: Prove $A+AB=A$ and its dual $A\cdot (A+B)=A$.

A. Original Identity ($A+AB=A$):

$\text{L.H.S}=A+AB=A(1+B)=A\cdot 1=A=\text{R.H.S}■$

B. Dual Identity ($A\cdot (A+B)=A$):

$\text{L.H.S}=A\cdot (A+B)=A\cdot A+A\cdot B=A+AB=A(1+B)=A\cdot 1=A=\text{R.H.S}■$

---

Proof 2: Major Exam Theorem — Dual of XOR Equals Its Complement

Major Term PYQ Theorem (2015 - 12 Marks, 2018 - 10 Marks)

Question: Show mathematically that the Dual of the Exclusive-OR (XOR) function is equal to its Complement (XNOR).

Let $F=A\oplus B=A^{\prime }B+A{B}^{\prime }$.

Step 1: Compute Dual of $F$ ($Dual(F)$)

Apply duality rules to $F=(A^{\prime }\cdot B)+(A\cdot B^{\prime })$: $Dual(F)=(A^{\prime }+B)\cdot (A+B^{\prime })$ Expand by distribution: $Dual(F)=A^{\prime }A+A^{\prime }{B}^{\prime }+BA+B{B}^{\prime }$ Since $A^{\prime }A=0$ and $B{B}^{\prime }=0$: $\mathbf{Dual}(\mathbf{F})=\mathbf{AB}+{\mathbf{A}}^{\prime }{\mathbf{B}}^{\prime }\text{— (Equation 1)}$

Step 2: Compute Complement of $F$ ($F^{\prime }$)

Apply De Morgan’s Law to $F=A^{\prime }B+A{B}^{\prime }$: $F^{\prime }=(A^{\prime }B+A{B}^{\prime }{)}^{\prime }=(A^{\prime }B{)}^{\prime }\cdot (A{B}^{\prime }{)}^{\prime }=(A+B^{\prime })\cdot (A^{\prime }+B)$ Expand by distribution: $F^{\prime }=A{A}^{\prime }+AB+B^{\prime }{A}^{\prime }+B^{\prime }B=0+AB+A^{\prime }{B}^{\prime }+0$ ${\mathbf{F}}^{\prime }=\mathbf{AB}+{\mathbf{A}}^{\prime }{\mathbf{B}}^{\prime }\text{— (Equation 2)}$

Conclusion:

$\mathbf{Dual}(\text{XOR})=(\text{XOR}{)}^{\prime }=\text{XNOR}■$

---

3. Huntington Postulates of Boolean Algebra

Syllabus Context: Theoretical Foundation

While less commonly tested in calculation problems, these postulates form the mathematical definition of standard Boolean Algebras.

In 1904, E.V. Huntington formulated a set of postulates to define algebraic structures known as Boolean Algebras:

1. Closure: The system is closed under both binary operators $+$ (OR) and $\cdot$ (AND).
2. Identity Element:
   • There exists an identity element $0$ with respect to $+$: $x+0=x$.
   • There exists an identity element $1$ with respect to $\cdot$: $x\cdot 1=x$.
3. Commutative Law: The operators are commutative:
   • $x+y=y+x$
   • $x\cdot y=y\cdot x$
4. Distributive Law: Each operator distributes over the other:
   • $x\cdot (y+z)=(x\cdot y)+(x\cdot z)$
   • $x+(y\cdot z)=(x+y)\cdot (x+z)$
5. Complement: For every element $x$, there exists a unique complement element $x^{\prime }$ such that:
   • $x+x^{\prime }=1$
   • $x\cdot x^{\prime }=0$
6. Distinct Elements: The set contains at least two distinct elements $x$ and $y$ (where $x\ne y$).

---

4. The Consensus Theorem

Syllabus Context: High-Yield Exam Theorem

State and prove the Consensus Theorem is a common 6-mark theory question in Term Exams.

The Consensus Theorem is an algebraic simplification rule that eliminates redundant terms.

Theorem Statement:

$\mathbf{AB}+{\mathbf{A}}^{\prime }\mathbf{C}+\mathbf{BC}=\mathbf{AB}+{\mathbf{A}}^{\prime }\mathbf{C}$ And its dual form: $(\mathbf{A}+\mathbf{B})({\mathbf{A}}^{\prime }+\mathbf{C})(\mathbf{B}+\mathbf{C})=(\mathbf{A}+\mathbf{B})({\mathbf{A}}^{\prime }+\mathbf{C})$

Step-by-Step Proofs:

A. Original Form ($AB+A^{\prime }C+BC=AB+A^{\prime }C$):

1. Multiply the redundant term $BC$ by $(A+A^{\prime })=1$: $L.H.S=AB+A^{\prime }C+BC(A+A^{\prime })$
2. Distribute: $=AB+A^{\prime }C+ABC+A^{\prime }BC$
3. Group terms and factor: $=AB(1+C)+A^{\prime }C(1+B)$
4. Apply the Identity Law ($1+X=1$): $=AB(1)+A^{\prime }C(1)=AB+A^{\prime }C=R.H.S■$

B. Dual Form ($(A+B)(A^{\prime }+C)(B+C)=(A+B)(A^{\prime }+C)$):

1. Add $A{A}^{\prime }=0$ to the term $(B+C)$: $L.H.S=(A+B)(A^{\prime }+C)(B+C+A{A}^{\prime })$
2. Expand the third term using the Distributive Law ($X+YZ=(X+Y)(X+Z)$): $=(A+B)(A^{\prime }+C)(B+C+A)(B+C+A^{\prime })$
3. Rearrange terms: $=\underset{\text{absorption: }X(X+Y)=X}{\underbrace{(A+B)\cdot (A+B+C)}}\cdot \underset{\text{absorption: }X(X+Y)=X}{\underbrace{(A^{\prime }+C)\cdot (A^{\prime }+C+B)}}$
4. Simplify using the absorption law: $=(A+B)(A^{\prime }+C)=R.H.S■$

---

5. PYQ Master Proof: Duality & Deep Complementation

PYQ Master Proof (2018): Duality & Deep Complementation

Question: What is duality principle? Find the complement of the following Boolean function and reduce this complement function to a minimum number of literals: $F=[(AB{)}^{\prime }A][(AB{)}^{\prime }B]$

Part A: The Duality Principle The Duality Principle states that every valid Boolean algebraic expression remains valid if we mathematically interchange all AND ($\cdot$) operators with OR ($+$) operators, and simultaneously interchange all 0s with 1s, while keeping the variables themselves completely unchanged.

Part B: Simplification and Complementation Before applying De Morgan’s theorem to the whole expression, simplify the original function $F$ first:

$F=[(AB{)}^{\prime }A]\cdot [(AB{)}^{\prime }B]$ Step 1: Apply De Morgan’s to the inner terms. $F=[(A^{\prime }+B^{\prime })A]\cdot [(A^{\prime }+B^{\prime })B]$ Step 2: Apply the Distributive Law. $F=[A{A}^{\prime }+A{B}^{\prime }]\cdot [A^{\prime }B+B{B}^{\prime }]$ Step 3: Apply the Null Law ($X{X}^{\prime }=0$). $F=[0+A{B}^{\prime }]\cdot [A^{\prime }B+0]=(A{B}^{\prime })\cdot (A^{\prime }B)$ Step 4: Rearrange (Commutative Law). $F=A{A}^{\prime }B{B}^{\prime }=0$

The Final Complement: Since the original function perfectly reduces to absolute $0$, its complement $F^{\prime }$ is simply: ${\mathbf{F}}^{\prime }=1$ The minimum number of literals is zero (requires no variables, just a constant HIGH wire). $■$

---

Past Year Questions (PYQs)

• [PYQ 2015, 2016, 2018, 2019, 2022]: Define Duality principle and postulates of Boolean algebra.
• [PYQ 2015, 2018]: Show that the Dual of exclusive-OR is equal to its complement.
• [PYQ 2018]: Find the complement of $F=[(AB{)}^{\prime }A][(AB{)}^{\prime }B]$ and reduce to minimum number of literals. (08 Marks)
• [PYQ 2016, 2023]: State and prove the Consensus Theorem. (06 Marks)