Circuit Equivalence

Introduction to Circuit Equivalence

Two circuits are equivalent if they produce the same output for every possible input combination.

Why equivalence matters:

• Verify that simplification preserved function
• Check that different implementations match specification
• Prove optimizations are correct
• Debug circuit designs

Methods to prove equivalence:

1. Compare truth tables
2. Algebraic manipulation
3. Convert both to canonical form
4. Use Boolean algebra laws

Truth Table Equivalence Method

Truth table method:

1. Build truth table for expression/circuit 1
2. Build truth table for expression/circuit 2
3. Compare output columns row by row
4. If all rows match $\to$ equivalent If any row differs $\to$ not equivalent

Advantages:

• Always works (definitive answer)
• Simple and mechanical

Disadvantages:

• 2^n rows for n variables
• Impractical for many variables (exponential growth)

Algebraic Equivalence Method

Algebraic method:

1. Start with one expression
2. Apply Boolean algebra laws step by step
3. Transform into the other expression
4. If successful $\to$ equivalent

Common laws used:

• Commutativity: A $\land$ B = B $\land$ A
• Associativity: (A $\land$ B) $\land$ C = A $\land$ (B $\land$ C)
• Distribution: A $\land$ (B $\lor$ C) = (A $\land$ B) $\lor$ (A $\land$ C)
• De Morgan: $\neg$(A $\land$ B) = $\neg$A $\lor$ $\neg$B
• Absorption: A $\lor$ (A $\land$ B) = A

Requires finding the right sequence of transformations.

Canonical Form Method

Canonical form method:

1. Convert expression 1 to canonical DNF (or CNF)
2. Convert expression 2 to canonical DNF (or CNF)
3. Compare the canonical forms
4. If identical $\to$ equivalent

Why this works:

• Canonical form is unique for each function
• Two functions are equal iff they have the same canonical form
• Same set of minterms = same function

This combines the definitiveness of truth tables with algebraic manipulation.

Circuit Equivalence Practice

Equivalence checking methods summary:

Choose the method based on the problem at hand!

Proving Non-Equivalence

To prove expressions are NOT equivalent:

Find a counterexample - one input where outputs differ.

Method:

1. Try some input values
2. Evaluate both expressions
3. If outputs differ $\to$ NOT equivalent
4. One counterexample is sufficient proof

Example: Are A $\lor$ B and A $\land$ B equivalent?

Try A=1, B=0: A $\lor$ B = 1, A $\land$ B = 0. Different! Not equivalent.

Unlike proving equivalence, disproving requires only ONE example.

Comparing Three Equivalence Methods

Three methods to prove equivalence:

All methods are valid - choose based on the situation!

Selecting the Best Method

Method selection guide:

Use Truth Table when:

• 2-3 variables (small tables)
• Need visual confirmation
• Expressions are already evaluated

Use Algebraic when:

• Recognizable patterns (De Morgan, absorption)
• Expressions are structurally similar
• Want to understand WHY equivalent

Use Canonical Form when:

• Expressions look very different
• Need systematic proof
• Other methods are unclear

Strategies for Proving Non-Equivalence

Finding counterexamples efficiently:

Strategic test cases:

1. All zeros: (0, 0, 0...)
2. All ones: (1, 1, 1...)
3. Single variable true: (1, 0, 0...), (0, 1, 0...), etc.
4. Alternating: (1, 0, 1, 0...)

Why these work:

• Simple to evaluate
• Often expose differences
• Cover extreme cases

Remember: ONE counterexample disproves equivalence!

Optimize Then Verify

Optimize then verify workflow:

1. Original: Complex expression F
2. Simplify: Apply laws/K-map to get G
3. Verify: Prove F = G using equivalence method

Why verify?

• Simplification errors are common
• Skipped steps may be wrong
• Builds confidence in the result

Best practice: Always verify after simplification!

Real Circuit Simplification Examples

Real circuit equivalence examples:

Example 1: Alarm system

• Original: (door $\land$ $\neg$armed) $\lor$ (window $\land$ $\neg$armed) $\lor$ (motion $\land$ $\neg$armed)
• Simplified: $\neg$armed $\land$ (door $\lor$ window $\lor$ motion)

Example 2: Access control

• Original: (admin $\land$ logged_in) $\lor$ (admin $\land$ local)
• Simplified: admin $\land$ (logged_in $\lor$ local)

Simpler = fewer gates = less cost, power, delay!

Circuit Equivalence Synthesis

Equivalence Summary:

Workflow: Simplify $\to$ Verify $\to$ Deploy

Boolean Logic Applications Challenge

This challenge integrates all Applications concepts:

• Truth table construction
• Expression evaluation
• Circuit equivalence
• Simplification verification
• Counterexample finding

Boolean Logic Capstone

Boolean Logic Complete Review:

This capstone covers ALL Boolean Logic topics:

• Core Operations (NOT, AND, OR)
• Building Blocks (compound expressions, gates, XOR)
• Boolean Algebra (all laws)
• Normal Forms (DNF, CNF, minterms, maxterms)
• Simplification (algebraic, K-maps, don't-cares)
• Applications (truth tables, equivalence)

Demonstrate your complete understanding!

SAT Solver Applications

SAT solver applications:

• Hardware verification: "Does this circuit ever produce wrong output?" Encode the circuit as a formula, assert incorrect output, check satisfiability.
• Software testing: "Is there an input that crashes this function?"
• Scheduling: "Can we assign classrooms and timeslots satisfying all constraints?"
• Configuration: "Which package versions satisfy all dependencies?"
• Cryptanalysis: "Find an input producing this hash output."
• Planning: "Is there a sequence of actions reaching the goal state?"

Key insight: A SAT result of UNSAT is often more useful than SAT—it proves that no assignment can satisfy the constraints, meaning the system is correct (verification) or the constraints are contradictory (debugging).

XOR in Real Systems

XOR in real systems:

• RAID 5: XOR all data blocks to create a parity block. If any single drive fails, its data is recovered by XOR'ing the remaining blocks and parity.
• Network checksums: XOR bytes together for quick error detection.
• Toggle operations: XOR with a mask flips specific bits. Used in graphics, hardware registers, and state machines.
• Bit comparison: XOR two values; the result bits show where they differ. A result of 0 means the values are identical.

The key property: XOR is self-inverse (A $\oplus$ B $\oplus$ B = A). Applying the same operation twice returns the original. This is why RAID recovery works, why toggle operations are reversible, and why XOR is useful anywhere you need to undo what you did.

Boolean Logic in the Real World

Boolean logic in practice:

• Digital circuits: Gates implement AND, OR, NOT physically in silicon.
• Programming: Every conditional, loop guard, and assertion.
• Databases: SQL WHERE clauses and query optimization.
• Networking: Access control lists and packet filtering rules.
• AI/ML: Decision trees, feature selection, logical constraints.
• Hardware design: Chip verification and timing analysis.
• Formal methods: Proving software correctness mathematically.

The unifying thread: All digital computation reduces to Boolean operations on bits. Arithmetic, logic, control flow, and memory addressing all decompose into AND, OR, and NOT applied to binary values.