[rec.puzzles] Full solution, inverter problem

mark@mips.COM (Mark G. Johnson) (02/25/89)

The key idea behind the 3-inverters problem is contained in Akers' paper,
Figure 4: count up how many of the inputs are logic-1.  Then note that

A-bar (the inversion of A) is a logic-1  if and only if
	{ zero of the input bits are `1' }
   OR	{ one bit is a `1' and it is either B or C }
   OR	{ exactly 2 input bits are `1' and they are B and C }

So a solution could proceed something like this:
   G = AB + BC + AC		/* two or three of the inputs are `1' */
   H = INVERT(G)		/* zero or one  of the inputs are `1' */
   J = ABC + H(A+B+C)		/* one or three of the inputs are `1' */
   K = INVERT(J)		/* zero or two  of the inputs are `1' */
   A_BAR = KBC + HK + H(B+C)
   B_BAR = KAC + HK + H(A+C)	/* if (HK) then all 3 inputs were `0' */
   C_BAR = KAB + HK + H(A+B)

Here's a C program that will perhaps convince you the above is correct:
============================================================================

#include <stdio.h>
main()		/* Solution to the 3-inverters problem   25 feb 89 mgj */
{	int	a,b,c;
	for(a=0;a<=1;a++){
	 for(b=0;b<=1;b++){
	  for(c=0;c<=1;c++){ inv3(a,b,c); }}}
}

inv3(a,b,c)
	int	a,b,c;
{	int	g, h, j, k, ab, bb, cb ;
	g = (a&b) | (b&c) | (a&c) ;	/* two or more    inputs are true */
	h = (g==0) ? 1 : 0 ;		/* one or fewer   inputs are true */
	j = (a&b&c) | (h&(a|b|c)) ;	/* exactly 3 or 1 inputs are true */
	k = (j==0) ? 1 : 0 ;		/* exactly 2 or 0 inputs are true */

	ab =  (k&b&c) | (h&k) | (h&(b|c)) ;	/* a-bar */
	bb =  (k&a&c) | (h&k) | (h&(a|c)) ;	/* b-bar */
	cb =  (k&a&b) | (h&k) | (h&(a|b)) ;	/* c-bar */
	printf("%2d%2d%2d   inverted becomes %2d%2d%2d\n",a,b,c,ab,bb,cb);
}
-- 
 -- Mark Johnson	
 	MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086
	...!decwrl!mips!mark	(408) 991-0208