Xref: utzoo sci.math:5770 rec.puzzles:2877 comp.lsi:650 sci.electronics:5280
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!watmath!watcgl!jdchrist
From: jdchrist@watcgl.waterloo.edu (Dan Christensen)
Newsgroups: sci.math,rec.puzzles,comp.lsi,sci.electronics
Subject: Re: The 3 inverter problem
Message-ID: <8216@watcgl.waterloo.edu>
Date: 21 Feb 89 17:00:47 GMT
References: <13619@obiwan.mips.COM>
Reply-To: jdchrist@watcgl.waterloo.edu (Dan Christensen)
Organization: U. of Waterloo, Ontario
Lines: 20

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".

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?

----
Dan Christensen, Computer Graphics Lab,	         jdchrist@watcgl.uwaterloo.ca
University of Waterloo, Waterloo, Ont.	         jdchrist@watcgl.waterloo.edu