**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