Conference rusure::math

Let the three inputs be x, y, and z.

Let v	= not( xy + yz + zx )
Let w	= not( v(x+y+z) + xyz )
Then
    x'	= v(w+y+z) + w(yz)
    y'	= v(w+z+x) + w(zx)
    z'	= v(w+x+y) + w(xy)

Okay, suppose you have 3 inverters.
What is the maximum number of signals that you can invert?

Article 479 of 481, Tue 01:49.
Subject: Re: Three Inverter Problem
From: ech@spuxll.UUCP (? @ AT&T Information Systems, South Plainfield NJ)
Newsgroups: net.puzzle,net.math

An interesting followup to this problem (typical of candidacy questions!) is:
Can one conclude that NO circuit need contain more than two inverters?
(Since we can make three from two, why not use two of those to make three,
etc.?)

=Ned=

Yes, we CAN conclude no no circuit need require more than two inverters.

Proof by contradiction (this is also constructive):

Assume we have a circuit that requires N inverters, where N > 2.
However, we can replace 3 of those inverters by the 2 inverters that
produce 3 inversions.  Thus, the number of inverters is reduced, and
the assumption is proved false.

					- Gilbert

>Let the three inputs be x, y, and z.
>
>Let v	= not( xy + yz + zx )
>Let w	= not( v(x+y+z) + xyz )
>Then
>    x'	= v(w+y+z) + w(yz)
>    y'	= v(w+z+x) + w(zx)
>    z'	= v(w+x+y) + w(xy)
---------------------------------------------------------------------------
     Would someone please explain this to me?  I interpret the 
definitions of V and W as macros that say what inputs to take, and the
definitions of X', Y', and Z' as instantiating the macros.  I count 6 
instantiations, not three.  And I am completely baffled about W 
appearing in the references to V.  What am I missing?

    Re .5:
    
    v and w are variables, not macros.  In the expressions for x', y', and
    z', substitute _exactly_ the definition for v and w wherever v and w
    appear.
    
    
    				-- edp 

If I understand Peter's notation correctly, the expression
	Let w	= not( v(x+y+z) + xyz )
means
	Let w = not((v and (x or y or z)) or (x and y and z))

There are no functions here, just groups of subexpressions connected by
binary operators (and the unary 'not'). 


Lynn

    
    
    Here's a way to understand why Peter's expressions work.
    
    I'll use concepts such as "1" meaning "exactly one input is true",
    and "~2" meaning "some number of inputs OTHER THAN 2 are true", ">1"
    means more than one input is true.
    
    Peter's expressions are:
    
>Let the three inputs be x, y, and z.
>
>Let v	= not( xy + yz + zx )
>Let w	= not( v(x+y+z) + xyz )
>Then
>    x'	= v(w+y+z) + w(yz)
>    y'	= v(w+z+x) + w(zx)
>    z'	= v(w+x+y) + w(xy)
    
    The xy+yz+zx will be true if >=2 is true, hence the not(...) is ~>=2
    and hence it's <2.  So we have
    
    	v = <2
    
    In other words, v is true if less than 2 signals are true.
    
    Similar analysis on w:
    
    	w = not(v(>=1) + 3)
    	  = not(<2(>=1) + 3)
    	  = not(1 + 3)
    	  = 0 + 2
    
    In other words, w is true if either no signals are true or exactly 2
    signals are true.
    
    So, analyzing x', we have
    
    	x' = v(w+y+z) + w(yz)
    	   = <2(>=1) + (0+2)(yz)
    	   = 1 + 2yz
    	   = "exactly one signal true" or "exactly 2 signals true and y and
    		z"
    
    Hmmm.  Where did I go wrong ?  I would expect x' to look like:
    
    	x' = 0 + 2yz
    
    Help!
    
    /Eric

    
    Ah!  Thanks for pointing out my mistake.  I read "w+y+z" as "x+y+z",
    the latter of which means >=1 inputs is true, but is not what Peter's
    formula says.
    
    Here's my corrected note:
    
    Here's a way to understand why Peter's expressions work.
    
    I'll use concepts such as "1" meaning "exactly one input is true",
    and "~2" meaning "some number of inputs OTHER THAN 2 are true", ">1"
    means more than one input is true.
    
    Peter's expressions are:
    
>Let the three inputs be x, y, and z.
>
>Let v	= not( xy + yz + zx )
>Let w	= not( v(x+y+z) + xyz )
>Then
>    x'	= v(w+y+z) + w(yz)
>    y'	= v(w+z+x) + w(zx)
>    z'	= v(w+x+y) + w(xy)
    
    The xy+yz+zx will be true if >=2 is true, hence the not(...) is ~>=2
    and hence it's <2.  So we have
    
    	v = <2
    
    In other words, v is true if less than 2 signals are true.
    
    Similar analysis on w:
    
    	w = not(v(>=1) + 3)
    	  = not(<2(>=1) + 3)
    	  = not(1 + 3)
    	  = 0 + 2
    
    In other words, w is true if either no signals are true or exactly 2
    signals are true.
    
    So, analyzing x', we have
    
    	x' = v(w+y+z) + w(yz)
    	   = <2(0+2+y+z) + (0+2)(yz)
    	   = <2(0+y+z) + 2yz
    	   = <2*0 + <2*(y+z) + 2yz
    	   = 0 + (0+1)(y+z) + 2yz
    	   = no inputs OR at most 1 and it's y or z OR there's exactly 2
    	     and they're y and z
    
    This last statement clearly describes the conditions that are
    synonomous with x being false.
    
    *whew*
    
    /Eric

    According to someone on puzzle newsgroup, attempting to invert more
    than 3 inputs with just 2 inverters introduces feedback which may
    not settle.
    
    I don't understand this.  It seems to me that Gilbert's generalization
    tells us how to do it without feedback.
    
    Who's right ?
    
    /Eric

The following message is the reference that says that the circuit has
    feedback.  As I mentioned in last reply, I don't understand why ?
    	I mean, Gilbert's proof seems to me to suggest straightforward
    	logic gates.  Where is the feedback ?
    
    	Here's the reference:
    
    
Path: engage.enet.dec.com!shlump.nac.dec.com!decwrl!ucbvax!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!samsung!aplcen!haven!udel!princeton!cs.Princeton.EDU!ddks
From: ddks@cs.Princeton.EDU (Daniel Sleator)
Newsgroups: rec.puzzles
Subject: two inverters make n
Message-ID: <24688@princeton.Princeton.EDU>
Date: 5 Mar 90 23:33:59 GMT
References: <9003051435.AA14994@decwrl.dec.com>
Sender: news@princeton.Princeton.EDU
Reply-To: ddks@cs.Princeton.EDU (Daniel Sleator)
Lines: 7
 
For n>3 the circuit has cycles in it, and it's not guaranteed to 
settle.  This problem is discussed in great excruciating detail in the 
winter 1990 issue of the Mathematical Intelligencer.  The author
actually built the circuit, and found that it doesn't work without judiciously
placed delay elements.
 
				Daniel Sleator