Function Equivalence in Boolean Algebra: Three Proof Methods for GATE

Two Boolean expressions or gate circuits can look different and still implement exactly the same function. The test is not whether they agree on a few convenient inputs. They are equivalent only if their outputs match for every allowed input assignment in the relevant care set. A truth table, Boolean identities, and a K-map prove the central example, while don't-cares require more careful wording.

Related reading: function equivalence MCQs and Boolean minimisation.

What function equivalence actually means

For functions over the same variables, F ≡ G means F(x) = G(x) for every allowed assignment of x. Two equivalent mismatch tests say the same thing:

• F XOR G = 0 on every row.

• F XNOR G = 1 on every row.

Do not merge three different ideas. Identical expressions have the same written form. Logically equivalent expressions can look different but have the same input-output mapping. Equivalent circuit implementations may even use different gates or numbers of product terms while producing that same mapping.

The expressions are:

F(A,B,C) = AB + A'C + BC

G(A,B,C) = AB + A'C

Does BC change an output, or is it only a redundant consensus term?

Method 1: prove equivalence with a complete truth table

With three inputs, there are 2^3 = 8 assignments. Evaluate both functions in binary order and add an XOR column to expose any mismatch.

Work two rows rather than treating the table as magic. At A=0, B=1, C=1, F=0+1+1=1 and G=0+1=1. At A=1, B=0, C=1, every product term in both expressions is 0, so both outputs are 0.

Those two checks alone prove nothing about the other six assignments. Here the complete XOR column is 0,0,0,0,0,0,0,0, so F ≡ G.

Method 2: remove the redundant term by Boolean algebra

Transform F one identity at a time:

F = AB + A'C + BC
  = AB + A'C + BC(A + A')
  = AB + A'C + ABC + A'BC
  = AB(1 + C) + A'C(1 + B)
  = AB + A'C
  = G

The second line inserts A+A'=1. The next line distributes BC, the fourth regroups common factors, and the fifth uses 1+X=1.

This is the consensus theorem XY + X'Z + YZ = XY + X'Z, with X=A, Y=B, and Z=C. Therefore BC is the consensus term. Removing it changes neither the 1-set nor the 0-set. Advanced Boolean Algebra Laws and Logic Optimization treats this same consensus function as an optimisation decision, measuring gate-input cost and the static-1 hazard benefit of retaining BC. Equivalence proof has a different stopping point: once the full table, identity derivation, or K-map establishes the same function, the XOR miter transfers that conclusion to circuits. Remember that ordinary algebra does not transfer blindly: in Boolean algebra, X+X=X, not 2X.

Method 3: compare minterms on a Karnaugh map

The truth table gives the same on-set for both functions:

F = G = Σm(1,3,6,7)

Use rows A=0,1 and Gray-order columns BC=00,01,11,10. The A=0 row is 0,1,1,0; the A=1 row is 0,0,1,1.

The pair {m1,m3} keeps A=0 and C=1, so it gives A'C. The pair {m6,m7} keeps A=1 and B=1, so it gives AB. The vertical pair {m3,m7} gives BC, but both its cells are already covered. The minimal cover is therefore G=AB+A'C.

Matching minimal forms is sufficient to establish equivalence. Merely obtaining the same number of groups is not, because different groups can cover different minterms. The prime implicants and EPI counting guide explains that cover vocabulary in more detail.

Circuit equivalence and the XOR miter test

Implement F with three 2-input AND terms, AB, A'C, and BC, feeding an OR gate. Implement G with only AB and A'C feeding an OR gate. Now send the two circuit outputs into an XOR gate called a miter.

One input that makes the miter output 1 is a counterexample and disproves equivalence. An output that is identically 0 proves equivalence. Our miter produces eight zeroes, so the networks are functionally equivalent even though G uses one fewer product term. If two candidates instead disagree at ABC=101, they are not equivalent even if the other seven rows match.

Don't-cares change the scope of equivalence

Suppose a two-input specification requires 00→0, 01→1, and 10→1, while 11 is a don't-care. Compare these candidates in row order 00,01,10,11:

Both match the care set {00,01,10}, so both are valid implementations of this incomplete specification. They are equivalent over the specified care set, but they are not equivalent as complete Boolean functions because they differ at 11. Never silently treat a don't-care X as both 0 and 1 in the same comparison.

Traps and the ways GATE-style questions test the idea

• Sampling a few rows: agreement on selected cases misses a possible counterexample. Check every row or use another exact proof.

• Counting only the 1s: equal counts do not mean equal on-sets. Compare the actual minterm indices.

• Losing a complement: an incorrect De Morgan step changes the function. Complement every term and swap AND with OR carefully.

• Using diagonal K-map cells: diagonal cells are not adjacent. Group only cells differing in one variable, including valid edge wraparound.

• Trusting gate counts: equal gate counts say nothing about the realised input-output mapping. Compare the functions.

Typical exam-style tasks include simplifying (A+B)(A+C), spotting a redundant consensus term, or counting 1s in an XOR mismatch column. For the first form, distribute and absorb in one line: (A+B)(A+C)=AA+AC+AB+BC=A+BC. For the second, BC is redundant in AB+A'C+BC. For any disproof, one counterexample is enough.

The short version and what to practise next

Use a truth table when the input count is small, Boolean identities when a redundant term is visible, a K-map for a compact visual proof, and an XOR miter for circuit comparison. Always define the care set before declaring equivalence.

As a retrieval exercise, reproduce the eight-row table and the K-map for Σm(1,3,6,7) from memory. Then explain in one sentence why BC is redundant. KnowledgeGate has about 40 questions currently available in its Function Equivalence practice bank for continuing that practice.

Use GATE Guidance by Sanchit Sir for the broader GATE sequence, or Zero to Hero for a full CS foundations route. The CS Fundamentals category leads to neighbouring subject material when you are ready to connect equivalence with the rest of digital logic.