```Author: bandsmer (Michael Bandsmer)
Date: 202003-Oct-09 23:27:42

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?
```