Razborov gate-by-gate approximation lemma

Suppose the input nodes of a Boolean circuit are represented exactly and each internal logic gate is replaced by an approximate operation. For logic gate $g$ with children $a,b$, letThe set where the approximate output differs from the true output is contained in ${\bigcup }_g{E}_g$. Indeed, at an input outside every $E_g$, induction through the acyclic dependency graph proves equality at every logic gate. Shared subcircuits are charged once per logic gate, rather than once per path.

For any probability measure $\mu$, a union bound yieldsThus $s$ logic gates with local error at most $ϵ$ give total error at most $sϵ$. If every member of the approximating family has error at least $\delta$ against the target Boolean function, then $s\ge \delta /ϵ$. The Razborov approximation method applies this mechanism to carefully chosen positive and negative input distributions.^[ref]