|
I first heard about this riddle when I was at the third year of Computer Science
Engineering, at Politecnico in Milan. I don't know whether it has some official name;
i just call it the 3not2 problem.
The problem itself is very simple in its formulation, in fact it can be
expressed in just a couple of sentences. At first the problem seems either
impossible or trivial but then, when you actually try to find a solution,
things get really complicated.
This is the text of the problem:
|
Given three logic inputs, A, B and C,
design a logic circuit which gives as an output the three signals
NOT(A), NOT(B) and NOT(C).
Your circuit may contain any number of AND and OR gates,
but no more than 2 NOT gates.
|
This formulation is sufficient to describe the problem. Nevertheless I report
here some additional answers to those questions that people most frequently
ask me when I tell them about this problem personally:
- Can I use feedback in my logic circuit?
No, you must design a combinatorial network. No feedback, no state, no
technological parameters. No flip-flops. Think in terms of ideal logic
gates, not silicon.
- Can I use AND and OR gates with more than 2 inputs ?
Sure. But nothing changes.
Gates with more than 2 inputs can be easily expressed in terms of
simple circuits with gates having 2 inputs.
- ''The problem has no solution!
You cannot negate 3 signals with 2 not gates! It's self-evident!''
No, you are wrong. I have a solution. Moreover, to be more precise
I have all the solutions. I am not going to tell how many distinct
solutions I have because I'm not in the mood for writing an algorithm to
reveal structural differences between circuits.
Sorry, I'm not providing solutions to this problem because I want to
spoil you the opportunity of finding it by yourself.
|
