Xref: utzoo sci.math:5772 rec.puzzles:2880 comp.lsi:651
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!rochester!uhura.cc.rochester.edu!ur-valhalla!badri
From: badri@valhalla.ee.rochester.edu (Badri Lokanathan)
Newsgroups: sci.math,rec.puzzles,comp.lsi
Subject: Re: The 3 inverter problem
Summary: Yes, you did!
Message-ID: <1827@valhalla.ee.rochester.edu>
Date: 21 Feb 89 19:09:23 GMT
References: <13619@obiwan.mips.COM> <8216@watcgl.waterloo.edu>
Organization: UR Dept. of Electrical Engg, Rochester NY 14627
Lines: 41

> In article <13619@obiwan.mips.COM> mark@mips.COM (Mark G. Johnson) writes:
> >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".
> 
In article <8216@watcgl.waterloo.edu>,
jdchrist@watcgl.waterloo.edu (Dan Christensen) writes:
> If this is true, then from x inverters we can make any multiple-output
> combinational function of 2^x-1 input variables.
> 
> Thus 2 inverters can generate 2^2-1=3 inverters.  Then couldn't those
> 3 inverters generate 2^3-1=7 inverters.  And then those 7 inverters could
> generate 2^7-1=127 inverters.  And so on.
> 
> So from 2 inverters we can make any multiple-output combinational function
> of _any_ number of variables, right?  Or am I missing something?

Yes, you forgot the extremely generous use of AND/OR logic.
In any case, from the comp.lsi viewpoint, this is really quite a useless 
exercise since in most cases, inverted logic is the norm rather than the
exception.

On a rather risque note, it is about as useful as the reusable condom
puzzle: (Hit n if you are easily offended!)

3 men want to make love to 1 woman. Here are the assumptions:
(1) There should be no direct genital contact to avoid disease transmission.
(2) There is a supply of "reusable" condoms with the restriction that
    a dirtied surface may not be used by a different person.

What is the minimum number of condoms required?
Spoiler hint:

Simultaneous use of multiple condoms.
-- 
"I care about my fellow man              {) badri@ee.rochester.edu
 Being taken for a ride,                //\\ {ames,cmcl2,columbia,cornell,
 I care that things start changing     ///\\\ garp,harvard,ll-xn,rutgers}!
 But there's no one on my side."-UB40   _||_   rochester!ur-valhalla!badri