Lesson 04: Simplification of Boolean Expressions

4.1 Boolean Algebra

4.2 Karnaugh Maps (K-Maps)

Karnaugh map (K-map) is a graphical tool that is used to simplify Boolean expressions and minimize logic circuits. They offer a visual representation of minterms and prime implicants, making it easier to identify redundancies and optimize logic functions. K-maps are especially useful for functions with three or four variables but can also be applied to larger functions with careful manipulation.

Constructing Karnaugh Maps

Draw the Grid: The number of rows and columns in a K-map is determined by the number of variables.
- For 2 variables, there's a 2x2 K-map (4 cells).
- For 3 variables, there's a 4x2 or 2x4 K-map (8 cells).
- For 4 variables, there's a 4x4 K-map (16 cells).
Label the Grid: Label the rows and columns with Gray code (a sequence of binary numbers where only one bit changes at a time) to represent all possible combinations of the input variables.
Fill the Grid: Fill the K-map cells with 1s and 0s based on the function's truth table.
- 1s represent minterms where the function outputs 1 (true).
- 0s represent minterms where the function outputs 0 (false).

Two Variables K-Map
F(x, y)
K map 2Var

Three variables K-Map
F(x, y, z)
K map 3Var

Four Variables K-Map
F(w, x, y, z)
K map 4Var

Simplifying Boolean Functions with K-Maps

Identify Groups:
- Look for adjacent groups of 1s (for SOP form) or 0s (for POS form) in the map. Make each rectangle groups as large as possible and must contain a number of cells that have a power of 2 (e.g., 1, 2, 4, 8, ...) to minimize the number of literals in each term.
- Make as few rectangle groups as possible to minimize the number of terms in the final expression.
Form Groups: Groups can wrap around the edges of the map. The aim is to cover all the 1s (or 0s) in the map with the minimum number of groups.
Write the Simplified Expression: For each group, determine the common variables (the variables that don't change within the group). Write these variables as a product term for SOP (or sum term for POS). The simplified function is the sum of these product terms (or the product of these sum terms).

Example of K-maps with 4 variables for SoP Forms

Example of K-maps with 4 variables for PoS Forms

Don't Care (Logic X)

4.3 Tabulation Method

Tabulation Method

The Tabulation Method, also known as the Quine-McCluskey algorithm, is a systematic approach for simplifying Boolean algebra expressions in Digital Logic Design. It is particularly useful for minimizing complex Boolean functions to their simplest form, making it easier to design efficient digital circuits. This method is especially effective for functions with many variables, where Karnaugh maps (K-maps) become cumbersome.

Steps to Apply the Tabulation Method:

List the Minterms: Start by listing all the minterms (combinations of variables that yield a true result) of the function in binary form.
Group the Minterms: Group the minterms based on the number of 1s they contain. This is because minterms with a similar number of 1s can potentially be combined.
Combine Minterms: Compare minterms within adjacent groups. If two minterms differ by only one bit, they can be combined into a term with a dash (-) in the differing position, indicating that the particular bit can be either 0 or 1. This process of combination reduces the complexity of the expression.
Repeat the Combination Step: Continue combining terms until no further combinations are possible. The resulting terms are known as prime implicants.
Identify Essential Prime Implicants: Determine which prime implicants are essential. An essential prime implicant covers a minterm that no other prime implicant covers.
Construct the Prime Implicant Chart: If there are non-essential prime implicants, construct a chart with prime implicants on one axis and the minterms they cover on the other. This helps in selecting the minimum number of prime implicants needed to cover all minterms.
Select the Minimum Cover: Choose a set of prime implicants that covers all the minterms of the function with the smallest number of terms.

Example: Simplifying a Boolean Function

Consider a Boolean function F(w, x, y,z) = Σ m(0, 2, 5, 7, 10, 13, 14, 15)

Step1: List the Minterms in Binary Form

m₀ = 0000
m₂ = 0010
m₅ = 0101
m₇ = 0111
m₁₀ = 1010
m₁₃ = 1101
m₁₄ = 1110
m₁₅ = 1111

Step2: Group by Number of 1s

Group 0: 0000
Group 1: 0010
Group 2: 0101, 1010
Group 3: 0111, 1101, 1110
Group 4: 1111

Step 3: Combine Minterms and Identify Prime Implicants

Combine 0000 and 0010 to 00-0
Combine 0010 and 1010 to -010
Combine 0101 and 0111 to 01-1
Combine 0101 and 1101 to -101
Combine 1010 and 1110 to 1-10
Combine 0111 and 1111 to -111
Combine 1101 and 1111 to 11-1
Combine 1110 and 1111 to 111-

Step 4: Continue to Combine Minterms and Identify Prime Implicants

Combine 01-1 and 11-1 to -1-1
Combine -101 and -111 to -1-1
No further combinations are possible, so we have prime applicants: 00-0, -010, -1-1, 1-10, and 111-

Step 5: Identify Essential Prime Implicants

For this example, assume all are essential for simplicity.

Step 6 & 7: Select the Minimum Cover

Since all prime implicants are considered essential, our minimal expression includes them all:
F_min(w, x, y, z) = w x z + x y z + x z + w y z + w x y

Using the Tabulation Method, this example simplifies the Boolean function to its minimal form. In practice, the prime implicant chart in Step 6 is crucial for identifying essential prime implicants when dealing with non-trivial functions, ensuring the most efficient combination of terms for the minimal expression.

Benefits of the Tabulation Method:

A systematic approach for identifying prime implicants.
Offers various minimization techniques to find optimal solutions.
Applicable to functions with a large number of variables.

Questions

When a Karnaugh map has four rows or columns, they are numbered 00, 01, 11, 10 instead of 00, 01, 10, 11. Why?
Simplify the following Boolean functions using three-variable K-maps:
1. \(F(x,y,z) = x\,y + \overline x \,\overline y \,\overline z + \overline x \,y\,\overline z \)
2. \(F(x,y,z) = \overline x \,\overline y + y\,z + \overline x \,y\,\overline z \)
3. \(F(x,y,z) = \overline x \,y + y\,\overline z + \overline y \,\overline z \)
Simplify the following Boolean functions:
1. F(x, y, z) = Σ m(0, 1, 5, 7)
2. F(x, y, z) = Σ m(1, 2, 3, 6, 7)
3. F(w, x, y, z) = Σ m(1, 3, 7, 11, 15) + d(0, 2, 5)
4. F(w, x, y, z) = Σ m(4, 5, 6, 7, 12) + d(0, 8, 13)
5. F(w, x, y, z) = Σ m(1, 6, 10, 11, 12, 13, 15) + d(4, 5, 7, 8, 14)
Simplify the following Boolean functions:
1. F(A, B, C, D) = ∏ M(1, 3, 5, 7, 13, 15)
2. F(A, B, C, D) = ∏ M(1, 3, 6, 9, 11, 12, 14)
Simplify the following expression to (1) SoP and (2) PoS:
1. \(\overline A \,\overline C + \overline B \,\overline C + B\,\overline C + A\,B\)
2. \((\overline A + B + \overline D ) \cdot (\overline A + \overline B + \overline C ) \cdot (\overline A + \overline B + C) \cdot (\overline B + C + \overline D )\)
Implement the following Boolean expression with XOR and AND gates:
\[F = A\,\overline B \,C\,\overline D + \overline A \,B\,C\,\overline D + A\,\overline B \,\overline C \,D + \overline A \,B\,\overline C \,D\]