03 Chapter 3 - Boolean Algebra & Logic Simplification (Merged)

Chapter 3: Boolean Algebra & Logic Simplification - Complete Study Notes

NotebookLM Ingestion Compilation

This merged document contains all 7 study notes for Chapter 3: Boolean Algebra & Logic Simplification from ECE 2103 Digital Electronics (Sharif Sir).

---

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$).

⚠️ Warning for Beginners: Boolean vs. Ordinary Algebra

A student transitioning from high-school math to digital electronics will make critical assumptions that break down in digital design. Highlight these five fundamental differences:

• No Associative Law in Postulates: The associative laws—$x+(y+z)=(x+y)+z$ and $x(yz)=(xy)z$—are not part of Huntington’s baseline axioms. However, they can be mathematically proven as theorems using the other postulates.
• The Dual Distributive Law: In ordinary algebra, $x+(y\cdot z)\ne (x+y)(x+z)$. In Boolean algebra, this is completely valid and is used constantly for POS simplification.
• No Inverse Elements: Boolean algebra has no additive inverse ($-x$) and no multiplicative inverse ($1/x$). Consequently, subtraction and division do not exist in Boolean algebra.
• The Complement Operator: There is no equivalent to $x^{\prime }$ in real-number algebra.
• Set Cardinality: Ordinary algebra deals with an infinite set of real numbers; two-valued Boolean algebra is strictly restricted to a set of two discrete values: $\{0,1\}$.

3.1 Comparison: Boolean Algebra vs. Ordinary Algebra

Feature	Boolean Algebra	Ordinary Algebra
Set of Elements	Strictly two discrete elements: $\{0,1\}$.	Infinite set of real numbers ($\mathbb{R}$).
Arithmetic Operators	Logical OR ($+$) and Logical AND ($\cdot$).	Addition ($+$), Subtraction ($-$), Multiplication ($\times$), Division ($÷$).
Inverse Operators	None (no subtraction or division).	Subtraction (additive inverse) and Division (multiplicative inverse).
Dual Distributive Law	Valid: $x+(yz)=(x+y)(x+z)$.	Invalid: $x+(yz)\ne (x+y)(x+z)$ (e.g. $2+(3\times 4)=14\ne 5\times 6=30$).
Complement Operator	Single unary complement ($x^{\prime }$) defined by $x+x^{\prime }=1,x{x}^{\prime }=0$.	No complement operator.
Idempotent Law	Valid: $x+x=x,x\cdot x=x$.	Invalid: $x+x=2x,x\cdot x=x^2$.

---

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■$

Rule of Thumb for Spotting Consensus in Algebraic Expressions

Look for three product terms where each of the three variables ($x,y,z$) appears exactly twice, with one of the variables complemented in one term and uncomplemented in another. The term without the complemented variable (the “consensus” of the other two, $yz$) is completely redundant and can be deleted.

---

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)

---

Related Concepts: 01 Boolean Algebra Foundations & Duality Principle | 03 SOP, POS, Canonical & Standard Forms | 05 Tabular Method (Quine-McCluskey) & Prime Implicants

3.02 Boolean Algebra Significance & Circuit Minimization

What is Boolean Algebra?

Boolean Algebra {Switching Algebra} is the mathematical system used to analyze, model, and simplify binary digital circuits. Variables are strictly restricted to two discrete binary states: 0 (LOW/OFF) and 1 (HIGH/ON).

---

1. Why Do We Simplify Boolean Expressions?

graph TD
    Min[Boolean Expression Minimization] --> C1[1. Reduces Hardware Cost]
    Min --> C2[2. Decreases Gate Fan-in]
    Min --> C3[3. Lowers Power Consumption]
    Min --> C4[4. Reduces Propagation Delay]
    Min --> C5[5. Saves Silicon / PCB Space]
    Min --> C6[6. Improves System Reliability]
    
    C1 --> G1[Fewer Logic Gates]
    C2 --> G2[Fewer Inputs per Gate]
    C3 --> G3[Less Current & Heat]
    C4 --> G4[Fewer Gate Levels = Faster]
    C5 --> G5[Smaller IC Package]
    C6 --> G6[Fewer Wiring Failure Points]

Six Key Engineering Reasons for Simplification:

1. Reduces Hardware Cost: Direct reduction in total logic gate count on ICs.
2. Decreases Gate Fan-in: Reduces input pin requirements per logic gate.
3. Lowers Power Consumption: Reduces dynamic switching current and heat dissipation.
4. Increases Speed (Reduces Propagation Delay): Decreases gate levels {cascading depth}, enabling higher clock frequencies.
5. Saves Silicon Area: Reduces physical PCB footprint and silicon die size.
6. Improves System Reliability: Fewer interconnects directly lower statistical failure rates.

---

2. Summary of Circuit Cost Metrics

Circuit Cost Metric	Definition & Engineering Impact
Gate Count	Total number of physical logic gates required.
Literal Count (Fan-in)	Total number of variable appearances in the expression.
Number of Gate Levels	Depth of the longest path from input to output {propagation delay}.
Interconnection Complexity	Total number of wiring connections between logic gates.

---

Past Year Questions (PYQs)

• [PYQ 2020, 2024, 2025]: Significance of studying digital electronics and Boolean algebra.
• [PYQ 2016, 2018, 2022, 2023]: Why do we simplify Boolean expressions? (06 to 10 Marks)

---

Related Concepts: 04 Mathematical Conversions & Expansion of SOP and POS | 01 Boolean Algebra Foundations & Duality Principle | 02 Boolean Algebra Significance & Circuit Minimization

3.03 SOP, POS, Canonical & Standard Forms

Introduction to Boolean Logic Forms

Any Boolean function can be expressed in two standard algebraic structures: Sum of Products (SOP) or Product of Sums (POS).

graph TD
    BF[Boolean Expressions] --> SOP[Sum of Products SOP]
    BF --> POS[Product of Sums POS]
    
    SOP -->|OR-ing AND terms| CSOP[Canonical SOP / Sum of Minterms Σm]
    SOP -->|Simplified| SSOP[Standard SOP e.g. AB + BC]
    
    POS -->|AND-ing OR terms| CPOS[Canonical POS / Product of Maxterms ΠM]
    POS -->|Simplified| SPOS[Standard POS e.g. A+B B+C]

---

1. Canonical Forms vs. Standard Forms

A. The Canonical Form (Strictly Unique)

Definition: Canonical Form

A Boolean expression is in Canonical Form if every term contains all domain variables of the function exactly once, in either complemented or uncomplemented form. Canonical forms are strictly unique.

• Minterm ($m_j$): An AND product term containing all $n$ domain variables. Evaluates to 1 for exactly one input state. Used in Canonical SOP ($\Sigma m$).
• Maxterm ($M_j$): An OR sum term containing all $n$ domain variables. Evaluates to 0 for exactly one input state. Used in Canonical POS ($\Pi M$).

B. The Standard Form (Simplified / Non-Unique)

Definition: Standard Form

A Boolean expression is in Standard Form if it follows SOP or POS structure, but terms are simplified and do not need to contain all domain variables. Standard forms are non-unique.

C. Comparison: Canonical Forms vs. Standard Forms

Parameter	Canonical Form	Standard Form
Domain Variables	Every term MUST contain all domain variables exactly once.	Terms are simplified and do not need to contain all variables.
Uniqueness	Uniquely represents a Boolean function. (Only one canonical form exists).	Non-unique representation. (Multiple simplified standard forms exist).
Direct Mapping	Directly maps to the truth table rows (minterms = 1, maxterms = 0).	Does not map directly to rows without variable expansion.
Boolean Terms	Minterms (for SOP) and Maxterms (for POS).	Standard product terms and standard sum terms.
Algebraic Length	Usually long and redundant.	Minimized and compact.
Gate Efficiency	Highly inefficient to implement directly.	Optimal for hardware implementation (uses fewer gates).

---

2. Comparison Table: SOP vs. POS

Parameter	Sum of Products (SOP)	Product of Sums (POS)
Basic Structure	Formed by OR-ing multiple AND product terms.	Formed by AND-ing multiple OR sum terms.
Truth Table Source	Derived from rows where output $F=1$.	Derived from rows where output $F=0$.
Canonical Component	Sum of Minterms ($\Sigma m$).	Product of Maxterms ($\Pi M$).
Native Gate Realization	2-level AND-OR or NAND-NAND logic.	2-level OR-AND or NOR-NOR logic.

---

3. PYQ Master Problem: POS Canonical Extraction

PYQ Master Problem (2016): POS Canonical Extraction

Question: Given the function $f(A,B,C)=(A+B+C^{\prime })(A+B^{\prime }+C^{\prime })(A^{\prime }+B+C^{\prime })(A^{\prime }+B^{\prime }+C^{\prime })$, construct the truth table and express the function in maxterm and minterm forms.

Step 1: Identify the Maxterms The function is given in canonical Product of Sums (POS) form. A maxterm evaluates to 0 when its uncomplemented variables are 0 and its complemented variables are 1:

• $(A+B+C^{\prime })\to 001_2\to {\mathbf{M}}_1$
• $(A+B^{\prime }+C^{\prime })\to 011_2\to {\mathbf{M}}_3$
• $(A^{\prime }+B+C^{\prime })\to 101_2\to {\mathbf{M}}_5$
• $(A^{\prime }+B^{\prime }+C^{\prime })\to 111_2\to {\mathbf{M}}_7$

Maxterm Form: $\mathbf{f}(\mathbf{A},\mathbf{B},\mathbf{C})=\mathbf{\Pi M}(1,3,5,7)$

Step 2: Identify the Minterms Minterms are the remaining decimal states (0 through 7) not present in the maxterm list: Minterm Form: $\mathbf{f}(\mathbf{A},\mathbf{B},\mathbf{C})=\mathbf{\Sigma m}(0,2,4,6)$

Step 3: Construct the Truth Table

A B C	f(A,B,C)
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	0
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	0

(Notice $f(A,B,C)$ simplifies to $f=C^{\prime }$). $■$

---

Past Year Questions (PYQs)

• [PYQ 2015, 2016, 2019, 2021, 2022, 2024]: Define Canonical form vs. Standard form.
• [PYQ 2021, 2022]: Distinguish between canonical form and standard form of a Boolean function. (08 to 10 Marks)
• [PYQ 2016]: POS Canonical Extraction, truth table construction, minterm/maxterm forms. (10 Marks)

---

Related Concepts: 03 SOP, POS, Canonical & Standard Forms | 01 Boolean Algebra Foundations & Duality Principle | 05 Tabular Method (Quine-McCluskey) & Prime Implicants

3.04 Mathematical Conversions & Expansion of SOP and POS

Concept Overview

Converting standard Boolean expressions into canonical Sum of Products (SOP) or Product of Sums (POS) form is accomplished algebraically via Missing-Variable Expansion.

graph TD
    Expression[Non-Canonical Expression] --> Type{Expansion Target}
    
    Type -->|Expand to SOP| SOPRule[Multiply term by x + x' = 1]
    SOPRule --> ExpandSOP[Apply Distributive Law: AB x+x' = ABx + ABx']
    ExpandSOP --> ListMinterms[List Sum of Minterms Σm]
    
    Type -->|Expand to POS| POSRule[Add xx' = 0 to sum term]
    POSRule --> ExpandPOS[Apply Distributive Law: X + YZ = X+Y X+Z]
    ExpandPOS --> ListMaxterms[List Product of Maxterms ΠM]

---

1. Algebraic Expansion Rules

• SOP Expansion Rule: Multiply each non-canonical AND product term by $(x+x^{\prime })=1$ for every missing variable $x$.
• POS Expansion Rule: Add $(x\cdot x^{\prime })=0$ to each non-canonical OR sum term for every missing variable $x$, then expand via distribution: $A+BC=(A+B)(A+C)$.

---

2. 4-Variable Canonical Expansion (Major PYQ)

Major PYQ Problem (2015, 2017, 2021 - 12 Marks)

Question: Express $F(A,B,C,D)=(A+B^{\prime }+C)(B+D^{\prime })$ in Product of Maxterms ($\Pi M$) and Sum of Minterms ($\Sigma m$) notation.

Solution:

Part 1: Product of Maxterms ($\Pi M$)

• Term 1 $(A+B^{\prime }+C)$ is missing $D$: $(A+B^{\prime }+C+D{D}^{\prime })=(A+B^{\prime }+C+D)(A+B^{\prime }+C+D^{\prime })$ $\text{Binary: }0100_2=M_4,0101_2=M_5$

• Term 2 $(B+D^{\prime })$ is missing $A$ and $C$: $B+D^{\prime }+A{A}^{\prime }+C{C}^{\prime }$ Expanding via distribution yields 4 maxterms:

  • $(A+B+C+D^{\prime })\to 0001_2=M_1$
  • $(A+B+C^{\prime }+D^{\prime })\to 0011_2=M_3$
  • $(A^{\prime }+B+C+D^{\prime })\to 1001_2=M_9$
  • $(A^{\prime }+B+C^{\prime }+D^{\prime })\to 1011_2=M_{11}$

$\text{Product of Maxterms: }\mathbf{F}(\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D})=\prod \mathbf{M}(1,3,4,5,9,11)$

Part 2: Sum of Minterms ($\Sigma m$)

The minterm indices are the remaining numbers out of $0\dots 15$: $\text{Sum of Minterms: }\mathbf{F}(\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D})=\sum \mathbf{m}(0,2,6,7,8,10,12,13,14,15)■$

---

3. Class Test 01 Master Problem: SOP vs POS Gate Optimization

Class Test 01: SOP vs POS Gate Optimization

Question: Given $F=\Pi M(0,2,5,7,8,10,13,15)$: a) Convert into canonical SOP. b) Which implementation (SOP or POS) requires fewer logic gates?

Part A: Canonical SOP The minterm list is the exact inverse of the given maxterm list for a 4-variable system (0-15):

• Minterms = $1,3,4,6,9,11,12,14$
• Canonical SOP: $\mathbf{F}=\mathbf{\Sigma m}(1,3,4,6,9,11,12,14)$

Part B: Gate Optimization Justification To determine which implementation requires fewer gates, simplify both using K-maps:

• SOP Simplification: Plotting 1s yields a quad $(1,3,9,11)\to B^{\prime }D$ and a quad $(4,6,12,14)\to B{D}^{\prime }$. $F_{\text{SOP}}=B^{\prime }D+B{D}^{\prime }=\mathbf{B}\oplus \mathbf{D}$
• POS Simplification: Plotting 0s yields $F^{\prime }=B^{\prime }{D}^{\prime }+BD=(B\oplus D{)}^{\prime }$. Complementing gives: $F_{\text{POS}}=(B+D)(B^{\prime }+D^{\prime })=\mathbf{B}\oplus \mathbf{D}$
• Conclusion: Both simplified expressions mathematically reduce to the exact same logic (an XOR gate, or 2 ANDs + 1 OR). Therefore, both SOP and POS require the exact same number of logic gates. $■$

---

Past Year Questions (PYQs)

• [PYQ 2015, 2017, 2021, 2024]: Express equations into full SOP (Sum of Minterms) and POS (Product of Maxterms) forms. (10 to 12 Marks)
• [Class Test 01]: Canonical SOP conversion and SOP vs POS gate optimization analysis ($F=\Pi M(0,2,5,7,8,10,13,15)$). (10 Marks)

---

Related Concepts: 03 SOP, POS, Canonical & Standard Forms | 04 Mathematical Conversions & Expansion of SOP and POS | 06 Tabular Method (Quine-McCluskey) & Prime Implicants

3.05 Karnaugh Map (K-Map) Optimization & Don’t Care States

What is a Karnaugh Map?

A Karnaugh Map (K-map) is a graphical method used to simplify Boolean expressions without relying on algebraic manipulation. It organizes minterms or maxterms into a grid where adjacent cells differ by exactly one variable (satisfying the Gray Code adjacency property). This layout allows algebraic simplification ($XY+X{Y}^{\prime }=X$) to be executed visually.

---

1. K-Map Grid Layouts (2, 3, and 4 Variables)

The rows and columns are indexed using Gray Code (00, 01, 11, 10 instead of binary 00, 01, 10, 11) to ensure adjacent cells differ by only one variable.

A. 3-Variable K-Map (8 Cells)

• Map dimensions: $2\times 4$.
• Variables: $A$ (vertical), $BC$ (horizontal).

      BC
  A  \ 00   01   11   10
    +----+----+----+----+
  0 | m0 | m1 | m3 | m2 |
    +----+----+----+----+
  1 | m4 | m5 | m7 | m6 |
    +----+----+----+----+

B. 4-Variable K-Map (16 Cells)

• Map dimensions: $4\times 4$.
• Variables: $AB$ (vertical), $CD$ (horizontal).

       CD
  AB \ 00   01   11   10
    +----+----+----+----+
 00 | m0 | m1 | m3 | m2 |
    +----+----+----+----+
 01 | m4 | m5 | m7 | m6 |
    +----+----+----+----+
 11 | m12| m13| m15| m14|
    +----+----+----+----+
 10 | m8 | m9 | m11| m10|
    +----+----+----+----+

---

2. The Step-by-Step Grouping Rules

To simplify an SOP expression, place 1s in the cells corresponding to the minterms, and 0s for maxterms (for POS). Unused cells are filled with 0 (or 1).

The Adjacency Rules:

1. Power of 2 Rule: Group sizes must be powers of 2 (i.e., loops of 1, 2, 4, 8, or 16 cells). No loops of 3, 5, or 6 cells are allowed.
2. Standard Group Names:
   • Pair (2 cells): Eliminates 1 variable.
   • Quad (4 cells): Eliminates 2 variables.
   • Octet (8 cells): Eliminates 3 variables.
3. Adjacency Wrapping: The edges of the map wrap around.
   • The left-most column is adjacent to the right-most column.
   • The top-most row is adjacent to the bottom-most row.
4. Overlapping Groups: The same 1 can be used in multiple loops to make other loops as large as possible. Larger groups yield fewer literals!
5. Redundant Groups: Avoid loops where all contained 1s are already covered by other essential loops.

---

The 4-Corner Trick

In a 4-variable K-map, the four corner cells ($m_0,m_2,m_8,m_{10}$) are physically adjacent to each other. They can be grouped together into a single Quad that simplifies directly to:

$\text{Corners Quad }(m_0,m_2,m_8,m_{10})={\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }$

---

The Don’t Care ($X$) Rules:

In physical hardware (e.g., BCD decoders), some input combinations can never occur. These invalid states are called Don’t Cares and are marked as X in the grid.

1. You may treat X as a 1 if it helps enlarge a group of 1s.
2. You may treat X as a 0 (leave it uncovered) if it does not help enlarge a group.
3. You never need to loop isolated X cells that do not cover any active 1s.

---

3. Prime Implicants (PI) vs. Essential Prime Implicants (EPI)

When grouping, you must distinguish between candidate loops and mandatory loops:

• Prime Implicant (PI): A product term obtained by combining the maximum possible number of adjacent cells in the map. (It is a loop that cannot be doubled in size).
• Essential Prime Implicant (EPI): A Prime Implicant that contains at least one 1 that is not covered by any other Prime Implicant.
• Redundant Prime Implicant (RPI): A loop containing 1s that are completely covered by other select PIs.

Minimization Strategy

1. Find all Prime Implicants on the map (loop all possible maximum groups).
2. Identify Essential Prime Implicants (look for 1s that are only part of a single loop).
3. Add all EPIs to the final Boolean expression.
4. Cover any remaining uncovered 1s using the largest possible remaining PIs.

3.1 Differences: Prime Implicants (PI) vs. Essential Prime Implicants (EPI)

Feature	Prime Implicant (PI)	Essential Prime Implicant (EPI)
Definition	A maximal group of adjacent cells (cannot be combined into a larger group).	A Prime Implicant that covers at least one 1 not covered by any other PI.
Inclusion in Expression	May or may not be included in the final minimized expression.	MUST be included in the final minimized expression.
Uniqueness of Coverage	All of its 1s can potentially be shared with other groups.	Contains at least one “unique 1” that is only coverable by this specific loop.
Identification Method	Circle the largest possible cell groups ($1,2,4,8\dots$).	Look for circled 1s that are covered by only a single loop.
Role in Logic Minimization	Forms the pool of candidate terms for logic minimization.	Serves as the starting foundation terms for the final logic cover.

---

4. Worked Exam Examples

Example 1: 4-Variable SOP Minimization with Corners

Question: Simplify the Boolean function $F(A,B,C,D)=\sum m(0,2,5,7,8,10,13,15)$.

The K-Map Grid:

       CD
  AB \ 00   01   11   10
    +----+----+----+----+
 00 |  1 |  0 |  0 |  1 |  <- m0, m2 are 1s
    +----+----+----+----+
 01 |  0 |  1 |  1 |  0 |  <- m5, m7 are 1s
    +----+----+----+----+
 11 |  0 |  1 |  1 |  0 |  <- m13, m15 are 1s
    +----+----+----+----+
 10 |  1 |  0 |  0 |  1 |  <- m8, m10 are 1s
    +----+----+----+----+

Grouping Analysis:

1. The Corner Quad: Minterms $\{0,2,8,10\}$ form a 4-corner group.
   • Vertical transition ($AB$): $00$ and $10⟹B^{\prime }$ remains constant.
   • Horizontal transition ($CD$): $00$ and $10⟹D^{\prime }$ remains constant.
   • Term 1: $B^{\prime }{D}^{\prime }$
2. The Center Quad: Minterms $\{5,7,13,15\}$ form a $2\times 2$ center group.
   • Vertical transition ($AB$): $01$ and $11⟹B$ remains constant.
   • Horizontal transition ($CD$): $01$ and $11⟹D$ remains constant.
   • Term 2: $BD$

$\mathbf{F}={\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }+\mathbf{BD}=\mathbf{B}\odot \mathbf{D}\text{(XNOR Gate)}$

---

Example 2: 4-Variable SOP with Don’t Cares

Question: Simplify the Boolean function $F(A,B,C,D)=\sum m(1,3,7,11,15)+\sum d(0,2,5)$.

The K-Map Grid:

       CD
  AB \ 00   01   11   10
    +----+----+----+----+
 00 |  X |  1 |  1 |  X |  <- m0, m2 are Xs; m1, m3 are 1s
    +----+----+----+----+
 01 |  0 |  X |  1 |  0 |  <- m5 is X; m7 is 1
    +----+----+----+----+
 11 |  0 |  0 |  1 |  0 |  <- m15 is 1
    +----+----+----+----+
 10 |  0 |  0 |  1 |  0 |  <- m11 is 1
    +----+----+----+----+

Grouping Analysis:

1. Column Quad: The entire right-middle column $\{3,7,11,15\}$ contains all 1s.
   • Horizontal position is $11⟹CD$ remains constant.
   • Term 1: $CD$
2. Top-Left Quad (using $X$ at 5): The cells $\{1,3,5,7\}$ form a $2\times 2$ quad. Cell $m_5$ is a Don’t Care ($X$), which we treat as a 1 to enlarge the group.
   • Vertical transition ($AB$): $00$ and $01⟹A^{\prime }$ remains constant.
   • Horizontal transition ($CD$): $01$ and $11⟹D$ remains constant.
   • Term 2: $A^{\prime }D$
3. The Unused Don’t Cares: Cells $m_0$ and $m_2$ are left uncovered since all 1s are already covered. Treating them as 1s would only create a redundant term ($A^{\prime }{B}^{\prime }$).

$\mathbf{F}=\mathbf{CD}+{\mathbf{A}}^{\prime }\mathbf{D}=(\mathbf{C}+{\mathbf{A}}^{\prime })\mathbf{D}$

---

Example 3: POS Minimization (Grouping 0s)

Question: Simplify $F(A,B,C,D)=\sum m(1,3,5,7,8,9,12,13,14,15)$ into Product-of-Sums (POS) form.

To find the minimized POS expression, we map the 0s of $F$ on the K-map, simplify for $F^{\prime }$, and then apply De Morgan’s Law.

The K-Map Grid (showing 0s):

       CD
  AB \ 00   01   11   10
    +----+----+----+----+
 00 |  0 |  1 |  1 |  0 |  <- m0, m2 are 0s
    +----+----+----+----+
 01 |  0 |  1 |  1 |  0 |  <- m4, m6 are 0s
    +----+----+----+----+
 11 |  1 |  1 |  1 |  1 |  <- No 0s in this row
    +----+----+----+----+
 10 |  1 |  1 |  0 |  0 |  <- m10, m11 are 0s
    +----+----+----+----+

Grouping 0s for $F^{\prime }$:

1. Vertical Quad of 0s: Cells $\{0,2,4,6\}$ form a vertical quad on the outer columns.
   • Vertical transition ($AB$): $00$ and $01⟹A^{\prime }$ remains constant.
   • Horizontal transition ($CD$): $00$ and $10⟹D^{\prime }$ remains constant.
   • Term 1 ($F^{\prime }$): $A^{\prime }{D}^{\prime }$
2. Horizontal Pair of 0s: Cells $\{10,11\}$ form a horizontal pair.
   • Vertical position is $10⟹A{B}^{\prime }$ remains constant.
   • Horizontal transition ($CD$): $11$ and $10⟹C$ remains constant.
   • Term 2 ($F^{\prime }$): $A{B}^{\prime }C$
3. Vertical Pair of 0s (Wrapping): Cells $\{2,10\}$ wrap from top to bottom.
   • Vertical transition ($AB$): $00$ and $10⟹B^{\prime }$ remains constant.
   • Horizontal position is $10⟹C{D}^{\prime }$ remains constant.
   • Term 3 ($F^{\prime }$): $B^{\prime }C{D}^{\prime }$

Combining for $F^{\prime }$:

$F^{\prime }=A^{\prime }{D}^{\prime }+A{B}^{\prime }C+B^{\prime }C{D}^{\prime }$

Applying De Morgan’s Law ($F=(F^{\prime }{)}^{\prime }$):

$F=(A^{\prime }{D}^{\prime }+A{B}^{\prime }C+B^{\prime }C{D}^{\prime }{)}^{\prime }$ $\mathbf{F}=(\mathbf{A}+\mathbf{D})({\mathbf{A}}^{\prime }+\mathbf{B}+{\mathbf{C}}^{\prime })(\mathbf{B}+{\mathbf{C}}^{\prime }+\mathbf{D})$

---

5. 5-Variable K-Map Minimization (Three-Dimensional Adjacency) [Syllabus Week 5]

Foundational Concept (Outside Direct PYQ Scope)

5-variable K-maps represent a foundational concept in multi-variable logic minimization, but they have never appeared in ECE 2103 past year papers (which strictly test up to 4-variable K-maps). It is included here to provide complete theoretical foundation.

A 5-variable function $F(A,B,C,D,E)$ requires $2^5=32$ minterms. Grouping variables across 32 cells requires a three-dimensional mapping strategy.

5.1 Plane Overlay Concept

Instead of a single 32-cell grid, we construct two standard 4-variable ($4\times 4$) K-maps side-by-side:

• Plane A = 0 (Left Grid): Contains minterms $0\dots 15$ ($BC$ horizontal, $DE$ vertical).
• Plane A = 1 (Right Grid): Contains minterms $16\dots 31$ ($BC$ horizontal, $DE$ vertical).

       A = 0 (m0 - m15)                      A = 1 (m16 - m31)
            BC                                    BC
        00  01  11  10                        00  01  11  10
      +---+---+---+---+                     +---+---+---+---+
   00 | m0| m1| m3| m2|                  00 |m16|m17|m19|m18|
      +---+---+---+---+                     +---+---+---+---+
   01 | m4| m5| m7| m6|                  01 |m20|m21|m23|m22|
DE    +---+---+---+---+                  DE +---+---+---+---+
   11 |m12|m13|m15|m14|                  11 |m28|m29|m31|m30|
      +---+---+---+---+                     +---+---+---+---+
   10 | m8| m9|m11|m10|                  10 |m24|m25|m27|m26|
      +---+---+---+---+                     +---+---+---+---+

5.2 Adjacency & Grouping Rules

1. Grid Adjacency: Standard grouping rules (pairs, quads, octets, wrapping) apply individually to both the $A=0$ plane and the $A=1$ plane.
2. Plane-Overlay Adjacency: Imagine the $A=1$ plane is stacked directly on top of the $A=0$ plane. Cells in the same row/column coordinates on both maps are adjacent.
   • If a group of $2^k$ cells exists in the exact same position on both the $A=0$ and $A=1$ planes, they can be merged into a single $2^{k+1}$ group. The variable $A$ changes state ($0\to 1$) and is eliminated from the term.
   • If a group exists only on the $A=0$ plane, the term must contain $A^{\prime }$.
   • If a group exists only on the $A=1$ plane, the term must contain $A$.

Worked Example: 5-Variable Minimization

Question: Simplify the function $F(A,B,C,D,E)=\sum m(0,2,4,6,9,11,13,15,16,18,20,22,25,27,29,31)$.

Step 1: Plot the Planes

• On $A=0$ plane, plot 1s at: $0,2,4,6,9,11,13,15$.
• On $A=1$ plane, plot 1s at: $16,18,20,22,25,27,29,31$.

Step 2: Grouping Analysis

1. Outer Row Quads (Plane Overlay):
   • On $A=0$ plane, cells $\{0,2,4,6\}$ form a vertical-wrap quad on columns $BC=00,01$ and rows $DE=00,10$. This quad simplifies to $A^{\prime }{B}^{\prime }{E}^{\prime }$.
   • On $A=1$ plane, the same positions $\{16,18,20,22\}$ are also filled with 1s, forming the identical quad $A{B}^{\prime }{E}^{\prime }$.
   • Overlay Merge: Merge these two quads. $A$ is eliminated $⟹$ Term 1: ${\mathbf{B}}^{\prime }{\mathbf{E}}^{\prime }$.
2. Right-Side Quads (Plane Overlay):
   • On $A=0$ plane, cells $\{9,11,13,15\}$ form a quad in columns $BC=10,11$ and rows $DE=01,11$. This quad simplifies to $A^{\prime }BE$.
   • On $A=1$ plane, the same positions $\{25,27,29,31\}$ are also filled with 1s, forming the identical quad $ABE$.
   • Overlay Merge: Merge these two quads. $A$ is eliminated $⟹$ Term 2: $\mathbf{BE}$.

$\mathbf{F}={\mathbf{B}}^{\prime }{\mathbf{E}}^{\prime }+\mathbf{BE}=\mathbf{B}\odot \mathbf{E}\text{(XNOR Gate)}■$

---

6. Past Year Questions (PYQs) [PYQ 2016, 2018, 2022, 2023]

• [PYQ 2022, 2023]: Simplify Boolean function using K-map. (10 Marks)
• [PYQ 2016, 2018]: Simplify functions combining both SOP & POS using K-maps, including “Don’t Care” conditions. (12 Marks)

---

Related Concepts: 3.02 Boolean Algebra Significance & Circuit Minimization | 3.04 Mathematical Conversions & Expansion of SOP and POS | 3.05 Karnaugh Map (K-Map) Optimization & Don’t Care States | 3.07 Boolean Algebra Puzzles & Exam Proofs

3.06 Tabular Method (Quine-McCluskey) & Prime Implicants

Concept Overview: Tabular Method

While Karnaugh maps are ideal for up to 4 variables, they become visually impractical for 6 or more variables. The Tabular Method (Quine-McCluskey) is an algorithmic, tabular minimization method that guarantees the exact minimal standard-form expression for any number of variables.

graph TD
    Minterms[Input Minterms Σm] --> Phase1[Phase 1: Determine Prime Implicants]
    Phase1 --> Group1s[Group Minterms by Count of 1s]
    Group1s --> MatchPairs[Match Adjacent Groups Differing by Power of 2]
    MatchPairs --> MarkUnticked[Unticked Terms = Prime Implicants]
    
    MarkUnticked --> Phase2[Phase 2: Selection Table]
    Phase2 --> FindSingleX[Identify Columns with Single X]
    FindSingleX --> SelectEPI[Select Essential Prime Implicants]
    SelectEPI --> CoverRest[Select Minimum Remaining PIs to Cover All Minterms]
    CoverRest --> MinExpr[Minimal Boolean Function]

---

1. Core Definitions

• Prime Implicant (PI): A product term obtained by combining the maximum possible number of adjacent minterm squares. If a product term cannot be combined with any other term to eliminate a variable, it is a Prime Implicant.
• Essential Prime Implicant (EPI): A prime implicant that covers at least one minterm that is not covered by any other prime implicant. All EPIs must be included in the final minimal expression.

---

2. Step-by-Step Methodology

Phase 1: Determination of Prime Implicants

1. Group Minterms (and Don’t Cares): Convert all decimal minterms and don’t-care conditions to binary. Group them together based on the number of 1s in their binary representation.
2. Compare Adjacent Groups: Compare every term in Group $k$ with every term in Group $k+1$.
3. Power of 2 Rule: Two terms combine if they differ in exactly one bit position (which is a power of 2: $1,2,4,8,\dots$).
4. Record & Check: Write the combined pair in the next column, replacing the differing bit with a dash (-) (e.g., 0,8 (8) or 0,8 (-000)). Place a check ($✓$) next to both combined terms.
5. Iterate: Repeat this matching process for Column 2 to create Column 3, Column 3 to create Column 4, etc. You can only combine terms that have the dash (-) in the exact same position.
6. Identify PIs: Any term that remains unchecked ($✓$) at the end of the entire process is a Prime Implicant (PI).

---

Phase 2: Selection Table (Find Minimal Cover)

1. Selection Table Grid: Construct a grid where:
   • Rows: The list of all identified Prime Implicants.
   • Columns: The original minterms ONLY.

   Don't-Care Column Rule Never include don't-care conditions as columns in the selection table! Don't-cares are only used in Phase 1 to help expand the loops (prime implicants) as much as possible, but we are under no obligation to cover them in the final minimized expression.

2. Mark Intersections: Place an X at the intersection of a PI row and a minterm column if that PI covers that minterm.
3. Identify Essential Prime Implicants (EPIs):
   • Scan each column from left to right.
   • Look for columns containing exactly one X.
   • The PI row associated with that single X is an Essential Prime Implicant. Star ($\star$) or circle this row; it must be included in the final function.
   • Cross out the selected EPI row and all columns covered by this EPI.
4. Select Remaining PIs: For any remaining uncovered minterm columns, choose the minimum number of remaining PIs to complete the coverage.

---

3. PYQ Solution: 4-Variable Tabular Minimization

Major PYQ Problem (2023, 2025 - 10 Marks)

Question: Simplify $F(w,x,y,z)=\sum m(0,1,2,8,10,11,14,15)$ using the Tabular Method.

Solution:

Phase 1: Prime Implicant Determination Table

Group	Column 1 (Minterms)	Column 2 (Pairs)	Column 3 (Quads)
G0	$0✓$	$0,1(1)$	$0,2,8,10(2,8)[x^{\prime }{z}^{\prime }]$
G1	$1✓$	$0,2(2)✓$	$10,11,14,15(1,4)[wy]$
	$2✓$	$0,8(8)✓$
	$8✓$	$2,10(8)✓$
G2	$10✓$	$8,10(2)✓$
G3	$11✓$	$10,11(1)✓$
	$14✓$	$10,14(4)✓$
G4	$15✓$	$11,15(4)✓$
		$14,15(1)✓$

• Un-ticked Prime Implicants:
  1. 0,1 (1) $⟹w^{\prime }{x}^{\prime }{y}^{\prime }$
  2. 0,2,8,10 (2,8) $⟹x^{\prime }{z}^{\prime }$
  3. 10,11,14,15 (1,4) $⟹wy$

Phase 2: Selection Table

Prime Implicant	0	1	2	8	10	11	14	15	Status
$w^{\prime }{x}^{\prime }{y}^{\prime }(0,1)$	X	(X)							EPI (Covers 1)
$x^{\prime }{z}^{\prime }(0,2,8,10)$	X		(X)	(X)	X				EPI (Covers 2, 8)
$wy(10,11,14,15)$					X	(X)	(X)	(X)	EPI (Covers 11, 14, 15)

$\text{Minimal Boolean Function: }\mathbf{F}={\mathbf{w}}^{\prime }{\mathbf{x}}^{\prime }{\mathbf{y}}^{\prime }+{\mathbf{x}}^{\prime }{\mathbf{z}}^{\prime }+\mathbf{wy}■$

---

4. 6-Variable Tabular Setup (Exam Monster)

Major PYQ Monster Problem (2024 - 14 Marks)

Question: Determine prime implicants using Tabular Method for $F(A,B,C,D,E,F)=\sum m(6,9,13,18,19,25,27,29,41,45,57,61)$.

Setup Analysis:

• Variables: $6⟹$ Possible pair differences are powers of 2: $1,2,4,8,16,32$.
• Group 2 (Two 1s): $6(000110_2),9(001001_2),18(010010_2)$
• Group 3 (Three 1s): $13(001101_2),19(010011_2),25(011001_2),41(101001_2)$
• Group 4 (Four 1s): $27(011011_2),29(011101_2),45(101101_2),57(111001_2)$
• Group 5 (Five 1s): $61(111101_2)$

(Note: Minterm 6 cannot combine with any Group 3 term $⟹6$ is an immediate Prime Implicant!)

---

Past Year Questions (PYQs)

• [PYQ 2018]: Define Prime Implicants with example. (03 Marks)
• [PYQ 2023, 2025]: 4-variable Tabular simplification. (10 Marks)
• [PYQ 2024]: 6-variable 14M Tabular prime implicant determination. (14 Marks)

---

Related Concepts: 3.01 Boolean Algebra Foundations & Duality Principle | 3.04 Mathematical Conversions & Expansion of SOP and POS | 3.05 Karnaugh Map (K-Map) Optimization & Don’t Care States | 3.06 Tabular Method (Quine-McCluskey) & Prime Implicants

3.07 Boolean Algebra Puzzles & Exam Proofs

Exam Edge Cases & Mathematical Puzzles

High-yield exam questions often include 9 to 11-mark mathematical “puzzles” testing reverse-engineering, factoring constraints, and multi-variable gate expansions.

---

1. The 5-Variable “Reverse Don’t Care” Puzzle

Major PYQ Problem (2017, 2020 - 11 Marks)

Question: The expression $BE+B^{\prime }D{E}^{\prime }$ is a simplified version of $A^{\prime }BE+BCDE+B{C}^{\prime }{D}^{\prime }E+A^{\prime }{B}^{\prime }D{E}^{\prime }+B^{\prime }{C}^{\prime }D{E}^{\prime }$. Are there any don’t care conditions? If so, what are they?

Solution:

Step 1: Minterms of Unsimplified Expression ($F_{\text{un}}$)

Expand each 5-variable term ($ABCDE$):

• $A^{\prime }BE\to 01XX1⟹m_9,m_{11},m_{13},m_{15}$
• $BCDE\to X1111⟹m_{15},m_{31}$
• $B{C}^{\prime }{D}^{\prime }E\to X1001⟹m_9,m_{25}$
• $A^{\prime }{B}^{\prime }D{E}^{\prime }\to 00X10⟹m_2,m_6$
• $B^{\prime }{C}^{\prime }D{E}^{\prime }\to X0010⟹m_2,m_{18}$ $\text{Unsimplified Minterms: }\{2,6,9,11,13,15,18,25,31\}$

Step 2: Minterms of Simplified Expression ($F_{\text{simp}}$)

• $BE\to X1XX1⟹m_9,m_{11},m_{13},m_{15},m_{25},m_{27},m_{29},m_{31}$
• $B^{\prime }D{E}^{\prime }\to X0X10⟹m_2,m_6,m_{18},m_{22}$ $\text{Simplified Minterms: }\{2,6,9,11,13,15,18,22,25,27,29,31\}$

Step 3: Isolate Don’t Care Minterms

$\text{Don’t Cares }d=F_{\text{simp}}\setminus F_{\text{un}}=\{22,27,29\}$

• $m_{22}(10110_2)=\mathbf{A}{\mathbf{B}}^{\prime }\mathbf{CD}{\mathbf{E}}^{\prime }$
• $m_{27}(11011_2)=\mathbf{AB}{\mathbf{C}}^{\prime }\mathbf{DE}$
• $m_{29}(11101_2)=\mathbf{ABC}{\mathbf{D}}^{\prime }\mathbf{E}■$

---

2. The 8-Literal Limit Factoring Puzzle

Major PYQ Problem (2022 - 9 Marks)

Question: Express $F=B^{\prime }{C}^{\prime }{D}^{\prime }+A{B}^{\prime }C{D}^{\prime }+B{C}^{\prime }D+A^{\prime }BCD$ in three different ways using 8 or fewer literals.

Solution:

Way 1: Group by $B^{\prime }{D}^{\prime }$ and $BD$

$F=B^{\prime }{D}^{\prime }(C^{\prime }+AC)+BD(C^{\prime }+A^{\prime }C)$ Using absorption identity $(X^{\prime }+XY=X^{\prime }+Y)$: $\mathbf{F}={\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }({\mathbf{C}}^{\prime }+\mathbf{A})+\mathbf{BD}({\mathbf{C}}^{\prime }+{\mathbf{A}}^{\prime })\text{(8 literals)}$

Way 2: Group by $C^{\prime }$ and $C$

Expand Way 1: $F=A{B}^{\prime }{D}^{\prime }+B^{\prime }{C}^{\prime }{D}^{\prime }+A^{\prime }BD+B{C}^{\prime }D$ $\mathbf{F}={\mathbf{C}}^{\prime }({\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }+\mathbf{BD})+\mathbf{C}(\mathbf{A}{\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }+{\mathbf{A}}^{\prime }\mathbf{BD})\text{(8 literals)}$

Way 3: Group by $D^{\prime }$ and $D$

$\mathbf{F}={\mathbf{D}}^{\prime }(\mathbf{A}{\mathbf{B}}^{\prime }+{\mathbf{B}}^{\prime }{\mathbf{C}}^{\prime })+\mathbf{D}({\mathbf{A}}^{\prime }\mathbf{B}+\mathbf{B}{\mathbf{C}}^{\prime })\text{(8 literals)}■$

---

3. 4-Variable XNOR Expansion Proof

OCR Exam Scanner Typo Correction

PYQ 2017 text writes $A\oplus B\oplus C\oplus D=\Sigma m(0,3,5,6,9,10,12,15)$. This is an OCR typo. Minterm 0 ($0000$) evaluates to 0 in XOR. The true textbook question (Morris Mano 4-23) uses XNOR ($\odot$).

Major PYQ Proof (2017 - 10 Marks)

Question: Show that $A\odot B\odot C\odot D=\sum m(0,3,5,6,9,10,12,15)$.

Proof Solution:

Let $X=A\odot B=AB+A^{\prime }{B}^{\prime }$ and $Y=C\odot D=CD+C^{\prime }{D}^{\prime }$. $F=X\odot Y=XY+X^{\prime }{Y}^{\prime }$

• $X^{\prime }=(A\odot B{)}^{\prime }=A\oplus B=A^{\prime }B+A{B}^{\prime }$
• $Y^{\prime }=(C\odot D{)}^{\prime }=C\oplus D=C^{\prime }D+C{D}^{\prime }$

Substitute into $F$: $F=(AB+A^{\prime }{B}^{\prime })(CD+C^{\prime }{D}^{\prime })+(A^{\prime }B+A{B}^{\prime })(C^{\prime }D+C{D}^{\prime })$ $=ABCD+AB{C}^{\prime }{D}^{\prime }+A^{\prime }{B}^{\prime }CD+A^{\prime }{B}^{\prime }{C}^{\prime }{D}^{\prime }+A^{\prime }B{C}^{\prime }D+A^{\prime }BC{D}^{\prime }+A{B}^{\prime }{C}^{\prime }D+A{B}^{\prime }C{D}^{\prime }$ Evaluating these 8 product terms: $\mathbf{F}=\sum \mathbf{m}(0,3,5,6,9,10,12,15)■$

---

Past Year Questions (PYQs)

• [PYQ 2017, 2020]: 5-variable Reverse Don’t Care condition puzzle. (11 Marks)
• [PYQ 2022]: Express Boolean function with 8 or fewer literals. (09 Marks)
• [PYQ 2017]: Show that $A\odot B\odot C\odot D=\Sigma m(0,3,5,6,9,10,12,15)$. (10 Marks)

---