Output 3 Complements with 2 Not Gates

I heard this puzzle at lunch today as I ate with Philip T. and Sam. Supposedly Sam figured it out while we were there, but now that I’ve found the solution, I don’t think so. Philip explained it to me, and told me not to tell him the answer because he wants to figure it out on his own. Of course, I looked it up online. Here’s the problem, as stated on this page (answer not given).

The 2-NOTs problem. Give three inputs a, b, and c, design a circuit that outputs a’, b’, and c’. You may use as many AND and OR gates as you like, but at most two NOT gates. Hint: high degree of difficulty.

It was hard to find the answer for this one. It sounds like a simple problem, but no: its not. Easy to explain, difficult to solve. These are the AND, OR, and NOT gates in diagram, if you’re new to this. After lots of searching, I eventually found the answer. It’s extraordinarily complex, and I haven’t even verified the solution. But I did draw it out on paper, and it’s huge!! It filled up an entire page. When I get home, I might scan it for your enjoyment. I wrote it in pencil, though, so who knows how well it will show up. Still, I think you’d be interested. It’s really interesting as well. When I have time someday, I’ll check to see if this solution is right.

Do you have an easier way?

Leave a Reply