Related Concepts: 08 Boolean Algebra Significance & Circuit Minimization | 09 XOR Gate Properties, Parity Generator & Error Checking | 11 SOP, POS, Canonical & Standard Forms

07 Boolean Algebra Foundations & Duality Principle

Statement of the Duality Principle

The Duality Principle is a fundamental postulate of Boolean algebra which 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.

In formal terms, if an identity $f(x_1,x_2,\dots ,x_n,+,\cdot ,0,1)=g(x_1,x_2,\dots ,x_n,+,\cdot ,0,1)$ is true, then its dual identity $f(x_1,x_2,\dots ,x_n,\cdot ,+,1,0)=g(x_1,x_2,\dots ,x_n,\cdot ,+,1,0)$ is also identically true.

---

1. Rules for Deriving the Dual of an Expression

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

To construct the Dual of any Boolean expression, execute these four rules:

1. Replace every OR ($+$) operator with an AND ($\cdot$) operator.
2. Replace every AND ($\cdot$) operator with an OR ($+$) operator.
3. Replace every binary constant 0 with 1, and every 1 with 0.
4. DO NOT complement any literal or variable {e.g., $x$ remains $x$, and $x^{\prime }$ remains $x^{\prime }$}.

Crucial Exam Distinction: Dual vs. Complement

Students frequently confuse the Dual of a function with the Complement of a function:

• 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 the Boolean absorption identity $A+AB=A$ and its dual $A\cdot (A+B)=A$.

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

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

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

First, apply duality rules to $A+AB=A⟹A\cdot (A+B)=A$. $\text{L.H.S}=A\cdot (A+B)$ $=A\cdot A+A\cdot B\text{(Distributive Law)}$ $=A+AB\text{(Idempotent Law: }A\cdot A=A\text{)}$ $=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).

Step-by-Step Proof:

Let the Exclusive-OR (XOR) Boolean function be defined as: $F=A\oplus B=A^{\prime }B+A{B}^{\prime }$

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

Apply duality rules to $F=(A^{\prime }\cdot B)+(A\cdot B^{\prime })$:

• Replace outer $+$ with $\cdot$
• Replace inner $\cdot$ with $+$
• Keep literals $A^{\prime },B,A,B^{\prime }$ unchanged:

$Dual(F)=(A^{\prime }+B)\cdot (A+B^{\prime })$

Expand the product using algebraic distribution: $Dual(F)=A^{\prime }A+A^{\prime }{B}^{\prime }+BA+B{B}^{\prime }$

Apply Complement Laws ($A^{\prime }A=0$ and $B{B}^{\prime }=0$): $Dual(F)=0+A^{\prime }{B}^{\prime }+AB+0$ $Dual(F)=AB+A^{\prime }{B}^{\prime }\text{— (Equation 1)}$ (Note: $AB+A^{\prime }{B}^{\prime }=A\odot B$, which is the XNOR function).

Step 2: Compute the 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 }$ $F^{\prime }=(A^{\prime }B{)}^{\prime }\cdot (A{B}^{\prime }{)}^{\prime }\text{(De Morgan’s Theorem)}$ $F^{\prime }=(A^{\prime \prime }+B^{\prime })\cdot (A^{\prime }+B^{\prime \prime })\text{(De Morgan’s Theorem)}$

Since double negation $A^{\prime \prime }=A$ and $B^{\prime \prime }=B$: $F^{\prime }=(A+B^{\prime })\cdot (A^{\prime }+B)$

Expand the product: $F^{\prime }=A{A}^{\prime }+AB+B^{\prime }{A}^{\prime }+B^{\prime }B$ Since $A{A}^{\prime }=0$ and $B^{\prime }B=0$: $F^{\prime }=0+AB+A^{\prime }{B}^{\prime }+0$ $F^{\prime }=AB+A^{\prime }{B}^{\prime }\text{— (Equation 2)}$

Conclusion:

Comparing Equation (1) and Equation (2): $Dual(F)=AB+A^{\prime }{B}^{\prime }=F^{\prime }$ $\therefore \mathbf{Dual}(\text{XOR})=(\text{XOR}{)}^{\prime }=\text{XNOR}■$

---

Past Year Questions (PYQs)

1. Definition of Duality Principle

• 2015, 2016, 2018 (10 Marks), 2019 (8 Marks), 2022 (6 Marks): Define Duality principle.
  • Solution: Write the formal statement from the top abstract block along with the 4 rules for finding a dual.

2. XOR Duality Proof

• 2015 (12 Marks), 2018 (10 Marks): Show that the Dual of the exclusive-OR is equal to its complement.
  • Solution: Write out the complete 2-step algebraic expansion for $Dual(F)$ and $F^{\prime }$ detailed in Proof 2.