Module 3: Boolean Algebra & Karnaugh Maps
Comprehensive Academic Reference Guide for Computer Engineering (TU / IOE Syllabus)
3.1 Boolean Algebra and Its Laws
Boolean Algebra is the mathematical system used to analyze and simplify digital logic circuits. Formulated by George Boole in 1854, it operates on binary variables that can assume only two discrete logic values: 0 (False) and 1 (True).
3.1.1 Fundamental Postulates and Axioms
Boolean algebra is formally defined on a set $B = \{0, 1\}$ with two primary binary operations: AND ($\cdot$), OR ($+$), and one unary operation: NOT ($\bar{A}$ or $A'$).
| Law / Principle | AND Form ($\cdot$) | OR Form ($+$) | Engineering Explanation |
|---|---|---|---|
| Identity Law | $A \cdot 1 = A$ | $A + 0 = A$ | Operating with identity element leaves variable unchanged. |
| Null (Annihilation) Law | $A \cdot 0 = 0$ | $A + 1 = 1$ | Dominant element forces output regardless of variable $A$. |
| Idempotent Law | $A \cdot A = A$ | $A + A = A$ | Combining a variable with itself yields the same variable. |
| Complement Law | $A \cdot \bar{A} = 0$ | $A + \bar{A} = 1$ | A variable ANDed with its inverse is always 0; ORed is always 1. |
| Commutative Law | $A \cdot B = B \cdot A$ | $A + B = B + A$ | Order of variables does not affect the logical result. |
| Associative Law | $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ | $(A + B) + C = A + (B + C)$ | Grouping of variables does not alter the output. |
| Distributive Law | $A + (B \cdot C) = (A + B)(A + C)$ | $A \cdot (B + C) = A B + A C$ | OR distributes over AND; AND distributes over OR. |
| Absorption Law | $A \cdot (A + B) = A$ | $A + (A \cdot B) = A$ | Redundant term $(A \cdot B)$ or factor $(A + B)$ is absorbed. |
| Redundant Literal Law | $A \cdot (\bar{A} + B) = A B$ | $A + \bar{A} B = A + B$ | Complement of $A$ inside the group is absorbed. |
| Involution (Double Negation) | $\overline{\overline{A}} = A$ | Double complementing a variable restores its original state. | |
| De Morgan's Laws | $\overline{A \cdot B} = \bar{A} + \bar{B}$ | $\overline{A + B} = \bar{A} \cdot \bar{B}$ | Complement of a product is sum of complements; complement of sum is product of complements. |
| Consensus Theorem | $AB + \bar{A}C + BC = AB + \bar{A}C$ | $(A+B)(\bar{A}+C)(B+C) = (A+B)(\bar{A}+C)$ | Third term $BC$ (the consensus) is completely redundant. |
3.1.2 The Principle of Duality
The Duality Principle states that any valid Boolean identity or algebraic expression remains valid if:
- Every AND ($\cdot$) operator is replaced with an OR ($+$) operator, and vice-versa.
- Every identity constant 0 is replaced with 1, and vice-versa.
- The variable states ($A, B, C$) are kept unchanged (do not complement variables).
Original Identity: A + A·B = A (Absorption Law)
Dual Identity: A · (A + B) = A
3.2 Simplification of Boolean Expressions
Simplifying Boolean equations minimizes the number of physical logic gates and gate inputs (literals) required to build a circuit, reducing manufacturing cost, propagation delay, power dissipation, and chip area.
Worked Proof 1: Prove the Consensus Theorem Algebraic Reduction
Minimize $F = A B + \bar{A} C + B C$ to two terms algebraically:
Worked Proof 2: Simplification using De Morgan's Laws
Simplify $Y = \overline{\bar{A} B + A \bar{B}}$ (Invert the XOR expression):
3.3 Minterms and Maxterms
Any arbitrary Boolean function can be expressed systematically using combinations of standard product terms (minterms) or standard sum terms (maxterms).
3.3.1 Minterms ($m_i$)
A Minterm is a product (AND) of all $N$ variables in a function, where each variable appears exactly once either in its uncomplemented form (if variable $= 1$) or complemented form (if variable $= 0$).
- A minterm evaluates to 1 for exactly one specific combination of input variables.
- For $N$ variables, there are $2^N$ possible minterms denoted by $m_0, m_1, \dots, m_{2^N-1}$.
3.3.2 Maxterms ($M_i$)
A Maxterm is a sum (OR) of all $N$ variables in a function, where each variable appears exactly once either in its complemented form (if variable $= 1$) or uncomplemented form (if variable $= 0$).
- A maxterm evaluates to 0 for exactly one specific combination of input variables.
- For $N$ variables, there are $2^N$ possible maxterms denoted by $M_0, M_1, \dots, M_{2^N-1}$.
3.3.3 Comprehensive 3-Variable Minterm & Maxterm Table
| Decimal Index ($i$) | A | B | C | Minterm Term | Minterm Designation | Maxterm Term | Maxterm Designation |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | $\bar{A}\bar{B}\bar{C}$ | m₀ | $A+B+C$ | M₀ |
| 1 | 0 | 0 | 1 | $\bar{A}\bar{B}C$ | m₁ | $A+B+\bar{C}$ | M₁ |
| 2 | 0 | 1 | 0 | $\bar{A}B\bar{C}$ | m₂ | $A+\bar{B}+C$ | M₂ |
| 3 | 0 | 1 | 1 | $\bar{A}BC$ | m₃ | $A+\bar{B}+\bar{C}$ | M₃ |
| 4 | 1 | 0 | 0 | $A\bar{B}\bar{C}$ | m₄ | $\bar{A}+B+C$ | M₄ |
| 5 | 1 | 0 | 1 | $A\bar{B}C$ | m₅ | $\bar{A}+B+\bar{C}$ | M₅ |
| 6 | 1 | 1 | 0 | $AB\bar{C}$ | m₆ | $\bar{A}+\bar{B}+C$ | M₆ |
| 7 | 1 | 1 | 1 | $ABC$ | m₇ | $\bar{A}+\bar{B}+\bar{C}$ | M₇ |
A maxterm $M_i$ is the exact complement of its corresponding minterm $m_i$ for the same index $i$:
$M_i = \overline{m_i} \quad \text{and} \quad m_i = \overline{M_i}$
3.4 Sum-of-Product (SOP) and Product-of-Sum (POS) Methods
3.4.1 Canonical vs. Standard Forms
- Canonical SOP (Sum-of-Minterms): A Boolean expression written strictly as a sum of product terms where every single variable appears in every term.
Example: $F(A, B, C) = \bar{A}\bar{B}C + \bar{A}BC + A B C = \sum m(1, 3, 7)$ - Non-Canonical / Standard SOP: Contains product terms that do not necessarily include all variables.
Example: $F = \bar{A}C + AB$ - Canonical POS (Product-of-Maxterms): A Boolean expression written strictly as a product of sum terms where every single variable appears in every term.
Example: $F(A, B, C) = (A+B+C)(A+\bar{B}+C)(\bar{A}+B+\bar{C}) = \prod M(0, 2, 5)$ - Non-Canonical / Standard POS: Contains sum terms that do not include all variables.
Example: $F = (A+C)(B+\bar{C})$
3.4.2 Inter-Conversion Between Canonical SOP and POS Forms
To convert between canonical SOP and POS forms for a given function, simply list the index numbers missing from the original set:
If $F(A, B, C) = \sum m(1, 4, 5, 6, 7)$, then its canonical POS form is the product of remaining maxterm indices:
F(A, B, C) = ∏ M(0, 2, 3)
3.5 Truth Tables and Karnaugh Maps
Invented by Maurice Karnaugh at Bell Labs in 1953, a Karnaugh Map (K-Map) is a graphical representation of a truth table that allows for rapid, error-free Boolean simplification without algebraic manipulation.
3.5.1 The Gray Code Adjacency Principle
Cells in a K-Map are arranged such that adjacent cells differ by exactly one binary bit. This arrangement relies on **Gray Code ordering** ($00, 01, 11, 10$ instead of binary $00, 01, 10, 11$).
Because adjacent cells differ by only one bit, two adjacent 1s represent an expression $X \cdot Y + X \cdot \bar{Y}$, which simplifies directly to $X(Y + \bar{Y}) = X \cdot 1 = X$. The physical adjacency eliminates the changing variable.
3.5.2 Two-Variable and Three-Variable K-Map Structures
| A\B | 0 | 1 |
|---|---|---|
| 0 | m₀0 | m₁1 |
| 1 | m₂2 | m₃3 |
| A\BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | m₀ | m₁ | m₃ | m₂ |
| 1 | m₄ | m₅ | m⇁ | m₆ |
3.6 Four-Variable K-Maps
A 4-variable K-map accommodates $2^4 = 16$ minterms ($m_0$ to $m_{15}$). Both row and column coordinates follow 2-bit Gray Code sequences ($00, 01, 11, 10$).
| AB\CD | 00 (&bar;C&bar;D) | 01 (&bar;CD) | 11 (CD) | 10 (C&bar;D) |
|---|---|---|---|---|
| 00 (&bar;A&bar;B) | m₀m₀ | m₁m₁ | m₃m₃ | m₂m₂ |
| 01 (&bar;AB) | m₄m₄ | m₅m₅ | m₇m₇ | m₆m₆ |
| 11 (AB) | m₁₂m₁₂ | m₁₃m₁₃ | m₁₅m₁₅ | m₁₄m₁₄ |
| 10 (A&bar;B) | m₈m₈ | m₉m₉ | m₁₁m₁₁ | m₁₀m₁₀ |
Note the swap in sequence! Rows jump from $01 \to 11 \to 10$ (Row 3 is $AB=11$, Row 4 is $AB=10$). Similarly, columns jump from $01 \to 11 \to 10$. Always verify minterm index positions ($m_2, m_6, m_{14}, m_{10}$ are on the far right column; $m_8, m_9, m_{11}, m_{10}$ are on the bottom row!).
3.7 Grouping Structures: Cells, Pairs, Quads, and Octets
Simplification is achieved by combining adjacent cells containing 1s into groups. All group sizes must be exact powers of 2 ($2^k \in \{1, 2, 4, 8, 16\}$).
| Group Name | Group Size ($2^k$) | Variables Eliminated | Resulting Term Structure (4-Var System) |
|---|---|---|---|
| Single Cell | $2^0 = 1$ cell | 0 variables eliminated | 4-literal Product Term (Full Minterm) |
| Pair | $2^1 = 2$ cells | 1 variable eliminated | 3-literal Product Term |
| Quad | $2^2 = 4$ cells | 2 variables eliminated | 2-literal Product Term |
| Octet | $2^3 = 8$ cells | 3 variables eliminated | 1-literal Product Term |
| Entire Map | $2^4 = 16$ cells | 4 variables eliminated | Constant Output $F = 1$ |
Mandatory Grouping Rules
- Groups must contain only 1s (and optional 'Don't Cares'). Never include 0s.
- Group dimensions must be rectangular or square (e.g., $1\times 2, 2\times 1, 2\times 2, 1\times 4, 2\times 4, 4\times 4$). Diagonal grouping is strictly prohibited.
- Groups should be made **as large as possible** to eliminate the maximum number of variables.
- Groups may overlap if overlapping helps enlarge another group.
3.8 Rolling, Envelope Effects, and Redundant Groups
3.8.1 Rolling / Wrap-Around (Envelope) Effect
The K-map is not a flat planar grid—it is a continuous torus (donut topology):
- Top and Bottom Edge Adjacency: Row 0 ($00$) is physically adjacent to Row 3 ($10$).
- Left and Right Edge Adjacency: Column 0 ($00$) is physically adjacent to Column 3 ($10$).
- The Four Corners Quad: Minterms $m_0, m_2, m_8, m_{10}$ form a valid Quad group!
Elimination analysis for $\{m_0, m_2, m_8, m_{10}\}$:
$AB$ changes between $00$ and $10$ $\implies$ $A$ drops out, leaving $\bar{B}$.
$CD$ changes between $00$ and $10$ $\implies$ $C$ drops out, leaving $\bar{D}$.
Simplified Product Term $= \bar{B}\bar{D}$.
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1m₀ | 0m₁ | 0m₃ | 1m₂ |
| 01 | 0m₄ | 0m₅ | 0m₇ | 0m₆ |
| 11 | 0m₁₂ | 0m₁₃ | 0m₁₅ | 0m₁₄ |
| 10 | 1m₈ | 0m₉ | 0m₁₁ | 1m₁₀ |
3.8.2 Prime Implicants vs. Redundant Groups
- Implicant: Any single minterm or group of minterms covered by a product term.
- Prime Implicant (PI): A rectangle of adjacent 1s that cannot be merged into a larger group.
- Essential Prime Implicant (EPI): A Prime Implicant that contains **at least one '1'** that is NOT covered by any other Prime Implicant. EPIs MUST be included in the final function.
- Redundant Group: A group whose 1s are completely covered by other Essential Prime Implicants. Redundant groups MUST be omitted to maintain a minimal SOP expression.
3.9 Don't Care Conditions ($d$ or $X$)
In certain digital systems, specific input combinations **never occur** during normal operation, or their output state has no impact on system functionality. These states are called Don't Care Conditions, denoted as $d(m_i)$ or $X$.
3.9.1 Leveraging Don't Cares in K-Maps
- You may treat $X$ as a 1 if it enables you to form a significantly larger group (e.g., expanding a Pair into a Quad).
- You may treat $X$ as a 0 if it does not help enlarge any group.
- You are **NEVER obligated** to group isolated $X$ cells.
3.9.2 Worked Master Problem: Minimization with Don't Cares
Problem Statement: Minimize the Boolean function $F(A, B, C, D) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)$
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | Xm₀ | 1m₁ | 1m₃ | Xm₂ |
| 01 | 0m₄ | Xm₅ | 1m₇ | 0m₆ |
| 11 | 0m₁₂ | 0m₁₃ | 1m₁₅ | 0m₁₄ |
| 10 | 0m₈ | 0m₉ | 1m₁₁ | 0m₁₀ |
Step-by-Step Grouping Analysis:
- Group 1 (Vertical Quad - Column CD=11): Minterms $\{m_3, m_7, m_{15}, m_{11}\}$ form a vertical Quad in column $CD=11$.
Variables $A$ and $B$ vary across all four rows and eliminate completely.
Term 1 = $C D$ - Group 2 (Top Row Quad using Don't Cares): Row 0 contains $\{m_0(X), m_1(1), m_3(1), m_2(X)\}$. By treating $m_0$ and $m_2$ as 1s, we form a 4-cell Quad across Row 0 ($AB=00$).
Variables $C$ and $D$ change across columns and cancel out.
Term 2 = $\bar{A}\bar{B}$ - Don't Care $m_5(X)$: Left isolated as 0 because all 1s are already covered by optimal groups.
F(A, B, C, D) = C D + Ā B̄
This reduces an 8-gate logic circuit to just two 2-input logic gates!