Karnaugh Map Basics

Karnaugh Map

• A Karnaugh map (K-map) is a method for simplifying Boolean expressions.
• K-maps produce the simplest SOP or POS expression possible, also known as the minimal expression.
• Similar to a truth table, a K-map shows all possible input variable values and their corresponding output.
• Instead of columns and rows, a K-map arranges cells representing binary input values.
• Cells are organized to simplify expressions by grouping them.
• In a three-variable K-map, the cells are arranged in a 2x4 matrix.
• Each cell represents a unique combination of input variables.
• The rows and columns of the map are labeled with the input variables.
• The order of the rows and columns is chosen to ensure that adjacent cells differ by only one input variable.

Rules of Simplification

• No zeros allowed: Groups must only contain 1s.
• No diagonals: Groups can't be formed diagonally.
• Power of two cells: Each group must have a number of cells that is a power of two (1, 2, 4, 8, etc.).
• Largest groups possible: Groups should be as large as possible.
• Every one included: Each 1 in the map must be included in at least one group.
• Overlapping allowed: Groups can overlap.
• Wrap around allowed: Groups can wrap around the edges of the map.
• Fewest groups: Use the fewest number of groups possible.

Grouping and Simplification

• Quad grouping: When a group of four cells is combined (a quad), the resultant term contains only the variables that remain constant throughout the quad.

Solving Examples

• Example 1: The K-map for the expression F(A,B,C) = Σ(0,1,2,3,4,5) shows that all the 1s can be grouped into a single quad, resulting in the simplified expression F(A,B,C) = 1 (meaning the output is always 1).

• Example 2: The K-map for the expression F(A,B,C) = Σ(0,2,4,6) shows two pairs of 1s that can be grouped, resulting in the simplified expression F(A,B,C) = BC' + AC'.

• Example 3: The K-map for the expression F(A,B,C) = Σ(1,3,5,7) shows two pairs of 1s that can be grouped, resulting in the simplified expression F(A,B,C) = A'C + AB.