This article is from the Puzzles FAQ, by Chris Cole firstname.lastname@example.org and Matthew Daly email@example.com with numerous contributions by others.
Can a digital logic circuit with two inverters invert N independent inputs?
The circuit may contain any number of AND or OR gates.
It can be shown that N inverters can invert 2^N-1 independent inputs,
given an unlimited supply of AND and OR gates. The classic version of
this puzzle is to invert 3 independent inputs using AND gates, OR
gates, and only 2 inverters.
This is solved by:
n1 = not(i1 and i2 or i1 and i3 or i2 and i3); n2 = not((i1 or i2 or i3) and n1 or i1 and i2 and i3); o1 = (i2 or i3 or n2) and n1 or i2 and i3 and n2; o2 = (i1 or i3 or n2) and n1 or i1 and i3 and n2; o3 = (i1 or i2 or n2) and n1 or i1 and i2 and n2;