Xref: utzoo sci.math:5768 rec.puzzles:2876 comp.lsi:649 sci.electronics:5275
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!apple!bbn!bbn.com!cosell
From: cosell@bbn.com (Bernie Cosell)
Newsgroups: sci.math,rec.puzzles,comp.lsi,sci.electronics
Subject: Re: The 3 inverter problem
Message-ID: <36205@bbn.COM>
Date: 21 Feb 89 14:45:34 GMT
References: <13619@obiwan.mips.COM>
Sender: news@bbn.COM
Reply-To: cosell@BBN.COM (Bernie Cosell)
Organization: Bolt Beranek and Newman Inc., Cambridge MA
Lines: 47

In article <13619@obiwan.mips.COM> mark@mips.COM (Mark G. Johnson) writes:
}In article <1750003@hprnd.HP.COM>, clw@hprnd.HP.COM (Carl Wuebker) writes
}
} $    Given two inverters and as many AND and OR gates as you need, synthesize
} $    the function F:
} $
} $                           -----------
} $                   A ---> |         | ----> NOT A
} $                          |         |
} $                   B ---> |    F    | ----> NOT B
} $                          |         |
} $                   C ---> |         | ----> NOT C
} $                          -----------
} $
} $     which is usually implemented simply with 3 inverters...
}
}This appeared quite a while ago -- 1968.   The published paper begins:
}"An interesting problem which has recently been making the rounds among
}switching theorists is that of synthesizing the circuit [above] using
}just __two__ inverters".
}
}The author goes on to say that _any_ multiple-output combinational function
}block of  n  input variables can be synthesized using ceil( log2(n+1) )
}inverters (!!).   So, for example, it's possible to invert 100 variables
}using just 7 inverters.  "This dramatic reduction in the number of inverters
}is achieved only through an extremely generous use of AND/OR logic".
}
}Reference:	Sheldon B. Akers, "On Maximum Inversion with Minimum
}		Inverters", IEEE Transactions on Computers, vol. C-17,
}		no. 2, pp. 134-135, February 1968.   {warning: the
}		discussion in the paper makes use of Threshold Logic to
}		simplify the figures}

The problem predates this paper by a bit, since it was given as a problem
while I was at MIT, in '66.  The thing that is amusing was [I think
Minsky's] observation about the followon conclusion -- it is clear that if
you can invert three signals with two inverters, you can invert *ANY*NUMBER*
of signals with just.... TWO inverters.  Spoiler follows....

Build the above box with two inverters.  Use two of its inputs as the inverters to build another such box, use the third input to invert one of your signals.
Continue bootstrapping more three-out-of-two boxes until you've generated
enough "spares" to invert all of your real signals....

   __
  /  )                              Bernie Cosell
 /--<  _  __  __   o _              BBN Sys & Tech, Cambridge, MA 02238
/___/_(<_/ (_/) )_(_(<_             cosell@bbn.com