Topic 16: Canonical Forms & Karnaugh Maps πΊοΈ
Master the art of simplifying Boolean expressions using standard forms and the powerful visual technique of Karnaugh Maps.
1) Canonical Forms of Boolean Expressions π
In Boolean algebra, any logical function can be expressed in a variety of ways. To standardize these expressions, we use Canonical Forms. These are standard formats that allow us to uniquely represent any Boolean function.
There are two primary canonical forms:
- Sum of Products (SOP): A sum (OR) of product (AND) terms. Also known as Disjunctive Normal Form (DNF).
- Product of Sums (POS): A product (AND) of sum (OR) terms. Also known as Conjunctive Normal Form (CNF).
To understand these, we first need to define Minterms and Maxterms.
Minterms and Maxterms
For a Boolean function of \(n\) variables, there are \(2^n\) possible input combinations.
- A Minterm is a product term containing all \(n\) variables (in either true or complemented form) that evaluates to 1 for exactly one combination of inputs. It corresponds to a row in the truth table.
- A Maxterm is a sum term containing all \(n\) variables (in either true or complemented form) that evaluates to 0 for exactly one combination of inputs.
Example 1: Minterms and Maxterms for 3 Variables (X, Y, Z)
| X | Y | Z | Minterm (\(m_i\)) | Maxterm (\(M_i\)) |
|---|---|---|---|---|
| 0 | 0 | 0 | \(m_0 = \overline{X}\overline{Y}\overline{Z}\) | \(M_0 = X + Y + Z\) |
| 0 | 0 | 1 | \(m_1 = \overline{X}\overline{Y}Z\) | \(M_1 = X + Y + \overline{Z}\) |
| 0 | 1 | 0 | \(m_2 = \overline{X}Y\overline{Z}\) | \(M_2 = X + \overline{Y} + Z\) |
| 1 | 1 | 1 | \(m_7 = XYZ\) | \(M_7 = \overline{X} + \overline{Y} + \overline{Z}\) |
(Table shows selected rows. Note: Minterm is 1 for that row, Maxterm is 0 for that row. \(m_i = \overline{M_i}\)).
2) Sum of Products (SOP) Form β
Any Boolean function can be expressed as a sum of minterms for which the function evaluates to 1. This is the Canonical Sum of Products (SOP) form.
Notation: \( F = \sum m(i, j, k, ...) \)
Where \(i, j, k...\) are the decimal indices of the minterms for which \(F=1\).
Example 2: SOP Form
Consider a function \( F(X, Y, Z) \) that is 1 when inputs are 001, 011, and 111.
Indices: 1 (001), 3 (011), 7 (111).
SOP Expression: \( F = m_1 + m_3 + m_7 = \overline{X}\overline{Y}Z + \overline{X}YZ + XYZ \).
Compact Notation: \( F = \sum m(1, 3, 7) \).
3) Product of Sums (POS) Form βοΈ
Any Boolean function can be expressed as a product of maxterms for which the function evaluates to 0. This is the Canonical Product of Sums (POS) form.
Notation: \( F = \prod M(a, b, c, ...) \)
Where \(a, b, c...\) are the decimal indices of the maxterms for which \(F=0\).
Note: SOP and POS forms for the same function are equivalent, but they look different. One might be simpler than the other depending on the function.
4) Karnaugh Maps (K-Maps) πΊοΈ
Algebraic simplification using Boolean laws can be tedious and error-prone. Karnaugh Maps (K-Maps) provide a visual method to simplify Boolean expressions.
A K-Map is a grid where each cell corresponds to a minterm. The cells are arranged in Gray Code order (only one bit changes between adjacent cells) so that physically adjacent cells represent minterms that differ by only one variable.
2-Variable K-Map
For 2 variables (X, Y), we have \(2^2 = 4\) cells.
2-Variable K-Map Structure
Example 5: Simplifying with 2-Variable K-Map
Function \( F(X, Y) = \Sigma m(0, 1, 2) \).
1. Fill 1s in cells 0, 1, 2.
2. Group adjacent 1s.
- Group 1: Cells 0 and 1 (Row 0). Covers \( \overline{X} \).
- Group 2: Cells 0 and 2 (Column 0). Covers \( \overline{Y} \).
3. Sum the terms: \( F = \overline{X} + \overline{Y} \). (Algebraically: \( \overline{X}\overline{Y} + \overline{X}Y + X\overline{Y} = \overline{X}(\overline{Y}+Y) + \overline{Y}(\overline{X}+X) = \overline{X} + \overline{Y} \)).
3-Variable K-Map
For 3 variables (X, Y, Z), we have \(2^3 = 8\) cells. Usually arranged as 2 rows x 4 columns.
3-Variable K-Map Structure
Note the column order: 00, 01, 11, 10 (Gray Code). m3 comes before m2!
Example 6: Simplifying with 3-Variable K-Map
Function \( F(X, Y, Z) = \Sigma m(0, 1, 4, 5, 6) \).
K-Map for F
Grouping:
- Group 1 (Purple): Quad (Group of 4). m0, m1, m4, m5.
Row 0 & 1 (X changes). Columns 00 & 01 (Y is 0, Z changes).
Term: \( \overline{Y} \). - Group 2 (Blue): Pair (Group of 2). m4, m6. (Note: m4 and m6 are
adjacent due to wrapping).
Row 1 (X is 1). Columns 00 & 10 (Y changes, Z is 0).
Term: \( X\overline{Z} \).
Simplified Expression: \( F = \overline{Y} + X\overline{Z} \).
5) Practice Questions π―
5.1 Fundamental β Build Skills
1. Convert the Boolean expression \( F = (X + Y) \cdot \overline{Z} + XY\overline{Z} \) to Sum of Products (SOP) form.
2. Convert the Boolean expression \( G = XY + \overline{X}Z \) to Product of Sums (POS) form.
3. Express the Boolean function \( H = \Sigma m(1, 3, 5, 7) \) in algebraic form (simplified if possible).
4. Express the Boolean function \( K = \Pi M(0, 2, 4, 6) \) in algebraic form (simplified if possible).
5. Use a 2-variable Karnaugh Map to simplify the Boolean function given by the truth table in Example 5. Verify your simplified expression matches \( X + Y \).
6. Use a 3-variable Karnaugh Map to simplify the Boolean function \( L = \Sigma m(0, 2, 4, 5, 6, 7) \). Find the minimal SOP form.
7. Use a 3-variable Karnaugh Map to simplify the Boolean function \( M = \Sigma m(0, 1, 2, 3, 4) \). Find the minimal SOP form.
8. Convert the simplified SOP expression from question 7 to POS form using De Morgan's Laws.
9. Design a two-level AND-OR circuit for the simplified SOP expression from question 6.
10. Design a two-level OR-AND circuit for the POS form of the function from question 2.
5.2 Challenging β Push Limits πͺπ
1. Simplify the Boolean expression \( R = (A + B) \cdot (\overline{A} + C) \cdot (B + C) \) using a Karnaugh Map.
2. Simplify \( S = \Sigma m(0, 2, 3, 4, 6) \) using a 3-variable Karnaugh Map. Find both minimal SOP and POS forms using the K-Map (for POS, group the 0s).
3. Consider the Boolean function \( T(X, Y, Z) \) that is 1 if the binary number XYZ represents a number greater than 2, and 0 otherwise. Express \(T\) in SOP canonical form and simplify using a 3-variable K-Map.
4. (Conceptual) Explain the advantages and disadvantages of using Karnaugh Maps for Boolean expression simplification compared to algebraic simplification methods. When is a K-Map particularly useful?
5. (Advanced Topic - Briefly Research) Look up "4-variable Karnaugh Maps". Briefly describe how 4-variable K-Maps are structured and how grouping is done. What are the limitations of K-Maps for simplifying expressions with a large number of variables? (Hint: Consider algorithmic methods like Quine-McCluskey for more variables).
6) Summary π
- Canonical Forms: Standard ways to represent Boolean functions: Sum of Products (SOP) and Product of Sums (POS).
- Minterms & Maxterms: Building blocks for SOP and POS forms respectively. Minterms are AND terms, Maxterms are OR terms.
- SOP Form (Ξ£m): OR of minterms for which the function is 1.
- POS Form (Ξ M): AND of maxterms for which the function is 0.
- Karnaugh Maps (K-Maps): Graphical tool for simplifying Boolean expressions, especially effective for up to 4 variables.
- K-Map Simplification Process: Fill K-Map from truth table or minterm list, group adjacent 1s (for SOP) or 0s (for POS), derive simplified terms from groups.
- Advantages of K-Maps: Visual, systematic simplification, often more efficient than algebra for complex expressions.
Excellent work in mastering canonical forms and Karnaugh Maps! You now have powerful tools for systematically representing and simplifying Boolean functions, essential for efficient digital circuit design. Karnaugh Maps will be your best friend in logic design! π§©β¨