Back

Here's a problem I came across that has me stumped---perhaps someone here
can figure it out. (I have no idea how easy or hard it is.)
The problem is to build a combinational logic circuit with 3 inputs (x1,
x2, x3) and 3 outputs (y1, y2, y3), such that
y1 = NOT x1
y2 = NOT x2
y3 = NOT x3.
You can use as many AND gates and OR gates as you want, but at most 2 NOT
gates.

Have you been taught to use k-maps?

I'm familiar with the k-map (Karnaugh map) method of generating logic
equations/circuits, but I don't see how this method could be applied to
this puzzle. (K-maps typically generate minimal AND/OR equations which are
functions of the inputs *and the negations of those inputs*, but in this
problem, we're limited to using just two inverters.) In fact, applying the
k-map method, we'd just get the original equations
y1 = NOT x1,
y2 = NOT x2,
y3 = NOT x3.

Is this even possible? Each of the 3 input/output pairs are completely
independant, so there is no way to group them with k-maps, etc. You might
as well try to build 3 seperate circuits with only 2 not gates. I'm not
sure it can be done?/

Yes, it can be done (a somewhat surprising result to me as well). I had to
write a program to find a solution because it was too laborious to work
through all the possibilities by hand. It turns out there is only 1
solution.
Following convention, denote OR's by addition, AND's by multiplication, and
NOT's by the "/" operator.
INPUTS: a,b,c
Use the 2 inverters to calculate:
d = /(ab+ac+bc)
e = /(abc + d(a+b+c))
Then, calculate the outputs
A = (b+c)d + (bc+d)e
B = (a+c)d + (ac+d)e
C = (a+b)d + (ab+d)e
It is easily verified that A=/a, B=/b, and C=/c, so this is our solution.
I don't know of any to come up with the above equations except through a
brute force search. I find it curious, however, that as part of our
solution we had to implement a full adder, i.e.
/e = a XOR b XOR c = sum bit out when adding a,b,c
/d = ab+ac+bc = carry bit out when adding a,b,c
Coincidence?