Algebraic Simplification

Why Simplify Boolean Expressions

Why simplify Boolean expressions?

1. Fewer gates = Less hardware cost
2. Fewer gates = Less power consumption
3. Fewer levels = Faster circuits (less delay)
4. Simpler = Easier to understand and verify

Example: A $\land$ B $\land$ C $\lor$ A $\land$ B $\land$ $\neg$C = A $\land$ B

• Original: 7 literals, multiple gates
• Simplified: 2 literals, one AND gate

Simplification doesn't change function behavior - same truth table!

Simplification Strategies

Key simplification techniques:

1. Look for complements: A $\lor$ $\neg$A = 1, A $\land$ $\neg$A = 0
2. Look for adjacency: (A $\land$ B) $\lor$ (A $\land$ $\neg$B) = A
3. Apply absorption: A $\lor$ (A $\land$ B) = A
4. Factor common terms: (A $\land$ B) $\lor$ (A $\land$ C) = A $\land$ (B $\lor$ C)
5. Use consensus: (A$\land$B) $\lor$ ($\neg$A$\land$C) $\lor$ (B$\land$C) $\to$ can drop (B$\land$C)

Strategy: Start with obvious simplifications, then look for patterns. Verify by checking truth tables if unsure.

The Adjacency Rule

Adjacency Rule (also called "combining"):

When two AND terms differ in exactly one variable:

(A $\land$ X) $\lor$ (A $\land$ $\neg$X) = A

The variable X and its complement cancel out!

Examples:

• (A $\land$ B) $\lor$ (A $\land$ $\neg$B) = A
• (P $\land$ Q $\land$ R) $\lor$ (P $\land$ $\neg$Q $\land$ R) = P $\land$ R
• ($\neg$X $\land$ Y) $\lor$ ($\neg$X $\land$ $\neg$Y) = $\neg$X

This is the key technique used in Karnaugh maps!

Absorption in Simplification

Absorption laws for simplification:

• A $\lor$ (A $\land$ B) = A (B is absorbed)
• A $\land$ (A $\lor$ B) = A (B is absorbed)

Why it works: If A is true, the compound term doesn't add anything.

If A is false, the compound term is also false (for $\land$) or we rely on A (for $\lor$).

Watch for disguised absorption:

• (A $\land$ B) $\lor$ (A $\land$ B $\land$ C) = A $\land$ B (the C term is absorbed)
• A $\lor$ ($\neg$A $\land$ B) = A $\lor$ B (special case!)

Factoring Common Terms

Factoring extracts common subexpressions:

(A $\land$ B) $\lor$ (A $\land$ C) = A $\land$ (B $\lor$ C)

Why factor?

1. May reveal complement: A $\land$ (B $\lor$ $\neg$B) = A $\land$ 1 = A
2. May enable absorption
3. May reduce total operations

Reverse factoring (distribution) can also help:

A $\land$ (B $\lor$ C) = (A $\land$ B) $\lor$ (A $\land$ C)

Sometimes one direction reveals more than the other!

The Consensus Theorem

Consensus Theorem:

(A $\land$ B) $\lor$ ($\neg$A $\land$ C) $\lor$ (B $\land$ C) = (A $\land$ B) $\lor$ ($\neg$A $\land$ C)

The term (B $\land$ C) is redundant - it's the "consensus" of the first two terms.

Why? When A is true, (A $\land$ B) covers B$\land$C cases. When A is false, ($\neg$A $\land$ C) covers B$\land$C cases.

Pattern: If you have (X $\land$ Y) $\lor$ ($\neg$X $\land$ Z), then (Y $\land$ Z) can be removed.

Dual form: (A $\lor$ B) $\land$ ($\neg$A $\lor$ C) $\land$ (B $\lor$ C) = (A $\lor$ B) $\land$ ($\neg$A $\lor$ C)

Step-by-Step Simplification

Systematic simplification approach:

1. Expand if needed (remove parentheses)
2. Identify complements (A $\land$ $\neg$A = 0, A $\lor$ $\neg$A = 1)
3. Remove zeros/ones (A $\lor$ 0 = A, A $\land$ 1 = A)
4. Apply absorption (A $\lor$ A$\land$B = A)
5. Look for adjacency ((A$\land$B) $\lor$ (A$\land$$\neg$B) = A)
6. Factor if helpful
7. Check for consensus

Repeat until no more simplification is possible.

Common Simplification Mistakes

Common mistakes to avoid:

1. Wrong distribution: A $\land$ (B $\lor$ C) $\neq$ (A $\land$ B) $\lor$ C Correct: A $\land$ (B $\lor$ C) = (A $\land$ B) $\lor$ (A $\land$ C)

2. Wrong De Morgan: $\neg$(A $\land$ B) $\neq$ $\neg$A $\land$ $\neg$B Correct: $\neg$(A $\land$ B) = $\neg$A $\lor$ $\neg$B

3. Invalid cancellation: A $\lor$ ($\neg$A $\land$ B) $\neq$ B Correct: A $\lor$ ($\neg$A $\land$ B) = A $\lor$ B

4. Assuming adjacency: (A $\land$ B) $\lor$ (C $\land$ D) can't be combined (no common factors, differ in multiple variables)

Always verify with truth tables when unsure!

Simplification Practice

Practice simplifying these expressions!

Remember the key techniques:

• Complements: A $\lor$ $\neg$A = 1, A $\land$ $\neg$A = 0
• Identity: A $\lor$ 0 = A, A $\land$ 1 = A
• Adjacency: (A$\land$B) $\lor$ (A$\land$$\neg$B) = A
• Absorption: A $\lor$ (A$\land$B) = A
• Factoring: (A$\land$B) $\lor$ (A$\land$C) = A$\land$(B$\lor$C)
• Consensus: (A$\land$B) $\lor$ ($\neg$A$\land$C) $\lor$ (B$\land$C) $\to$ remove B$\land$C

Systematic Simplification Strategy

Systematic simplification strategy:

1. Look for complements: A $\land$ $\neg$A = 0, A $\lor$ $\neg$A = 1
2. Apply identities: Remove 0s and 1s
3. Factor common terms: (A$\land$B) $\lor$ (A$\land$C) = A$\land$(B$\lor$C)
4. Apply absorption: A $\lor$ (A$\land$B) = A
5. Check for adjacency: (A$\land$B) $\lor$ (A$\land$$\neg$B) = A
6. Verify result: Simpler than original?

Work systematically - don't jump around randomly!

Recognizing Which Law Applies

Quick pattern recognition:

Pattern recognition speeds up simplification!

Multi-Step Simplification with Justification

Justifying each step:

Each simplification step should identify the law used:

1. (A $\land$ B) $\lor$ (A $\land$ $\neg$B) $\lor$ C
2. = A $\lor$ C [Adjacency on first two terms]

Or more detailed:

1. A $\lor$ (A $\land$ B) $\lor$ $\neg$A
2. = A $\lor$ $\neg$A [Absorption: A absorbs A$\land$B]
3. = 1 [Complement: A $\lor$ $\neg$A = 1]

This helps verify correctness and find errors!

Simplify to Minimal Form Challenge

Finding minimal form:

A minimal form has:

• Fewest possible terms
• Fewest possible literals (variables)
• No redundant parts

Multiple techniques may be needed:

• Factor, then simplify
• Expand, then recombine
• Apply multiple laws in sequence

The goal: simplest equivalent expression!

Verify Simplification by Truth Table

Verification by truth table:

To verify F = G (original = simplified):

1. Build truth table for both expressions
2. Compare outputs for ALL input combinations
3. If any row differs, simplification is WRONG

This is foolproof but can be slow for many variables.

For 2-3 variables, it's quick and definitive.

Spot check alternative: Test a few key values.