Boolean algebra, equivalent transformations and implementation cost

Equivalent expressions produce the same output for every input

Simplifying a combinational circuit is not just about shortening an expression. Preserve its function while considering logic depth, fan-in, fan-out and actual library cells. Start by reading $+$ and multiplication in Boolean algebra^{iBoolean algebra Algebra of 0, 1, AND, OR and NOT. The plus sign usually denotes OR here, whose rules differ from integer addition.} as OR and AND.

Verify the second identity by cases: when $A=1$, both sides are 1; when $A=0$, both sides equal $B$. Be able to explain the meaning even after applying a memorized identity.

Read NAND and NOR structures with De Morgan's laws

For example, $Y=AB+AC$ equals $A(B+C)$. The former can use two ANDs and one OR; the latter one OR and one AND. But with different input arrival times or loads, fewer gates do not always mean a faster circuit.

The consensus theorem is also useful:

When $BC=1$, either $A=0$ makes $\overline A C=1$, or $A=1$ makes $AB=1$. Thus $BC$ is redundant for the steady-state function. Removing it can, however, change hazards during transitions. We will address that distinction in the later delay lesson.

Each column below represents one ABC input combination, not elapsed time. Check that the two outputs agree in every column. Gate counts and paths may differ while the function for stable 0/1 inputs remains the same.

What constitutes an equivalence check?

Call the original and optimized outputs y_ref and y_opt. For a small input space, compare every input. Passing one or two examples is not enough to conclude equivalence.

assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

mismatch must be 0 for all eight combinations of 0/1 inputs. Four-state simulation involving X/Z and equivalence of sequential circuits require additional conditions. Stating exactly what has been established is a basic habit in design review.