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?