Lesson 4

The search becomes much larger with four inputs. Now, we will optimize a simple brute-force by exploring only circuits in the normal form. Call a Boolean function normal, if its value on all zeroes is zero.

We can make every internal (non-output) gate normal without changing the function computed by the circuit as follows. If a gate's output \(g\) is one at \(00… 0\), replace it by \(g'=\lnot g\) and change the function computed of every later gate that uses it. For example, a later operation \(g\land z\) becomes \(\lnot g'\land z\).

If the target function \(f\) is normal, the process will finish with a circuit which computes a normal function at every gate. Otherwise, instead of searching for a circuit for \(f\), search for the normal function \(\neg f\). Since now every gate with inputs \(u, v\) is normal and depends on both inputs, it must be one of the following: \(u \land v\), \(u\land\lnot v\), \(\lnot u\land v\), \(u \oplus v\), or \(u \lor v\).