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