Simplification

Overview

Why Simplify?

Simpler Boolean expressions require fewer logic gates, which means cheaper, faster, and more energy-efficient circuits. Simplification is one of the most practical skills in digital design.

Definition

Canonical Forms

Sum of Products (SOP): A Boolean expression written as an OR of AND terms. Example: f = x̄ · y + x · ȳ + x · y

Product of Sums (POS): A Boolean expression written as an AND of OR terms. Example: f = (x + y) · (x̄ + ȳ)

A minterm is an AND term using every variable (or its complement) exactly once. A maxterm is an OR term using every variable exactly once.

Example

Algebraic Simplification

Simplify f = x · y + x · ȳ + x̄ · y.

Step 1: Factor x from the first two terms: f = x · (y + ȳ) + x̄ · y

Step 2: Apply complement law (y + ȳ = 1): f = x · 1 + x̄ · y = x + x̄ · y

Step 3: Apply absorption-like expansion: f = x + x̄ · y = x + y (by the simplification theorem)

Verify with a truth table if needed!

Definition

Karnaugh Map (K-Map)

A Karnaugh map is a visual method for simplifying Boolean expressions. It arranges the truth table values in a grid where adjacent cells differ by exactly one variable. By grouping adjacent 1s into rectangles of size 1, 2, 4, or 8, you can read off the simplified expression.

Rules: • Groups must be rectangular and have size 2ⁿ. • Groups can wrap around edges. • Every 1 must be in at least one group. • Make groups as large as possible.

Example

K-Map Example (2 variables)

Simplify f(x, y) where f = 1 for: (0,1), (1,0), (1,1).

K-Map: y=0 y=1 x=0 | 0 | 1 | x=1 | 1 | 1 |

Group the bottom row (x=1): gives term x. Group the right column (y=1): gives term y.

Simplified: f = x + y.

Note

Don't-Care Conditions

Sometimes certain input combinations can never occur, or we don't care about the output for those inputs. These are marked with "d" or "X" in the K-map and can be treated as either 0 or 1 - whichever helps make larger groups and a simpler expression.