hasiuk@trwspp.UUCP (05/19/84)
References:
I'm sort of new to these news groups, so I don't know if this problem has
already made the rounds or not.
I saw this one while I was a student at Caltech; it seemed to be the type
of problem they would give a C.S. major on his candidacy orals. I have a
solution for it and if there is sufficient interest I will post it at a
later date.
The problem is simply stated: given two inverters (devices which convert a
logical 1 to a logical 0 and vice versa) and an arbitrary number of AND and
OR gates, design a circuit (or simply write down the boolean equations) which
produces three outputs, A', B', and C', which are the logical inverses of three
inputs A, B, and C. The circuit should not depend on anything like gate
delays to work, but it is OK for the outputs to glitch. This means that a
transition at, say, A, may cause B' to temporarily change state.
Also, don't let the words 'arbitrary number of' fool you, the solution
I've seen takes something like 20 gates excluding the inverters.
Good Luck!
Lee Hasiuk
{decvax, ucbvax} trwrb!trwspp!hasiukech@spuxll.UUCP (05/29/84)
An interesting followup to this problem (typical of candidacy questions!) is: Can one conclude that NO circuit need contain more than two inverters? (Since we can make three from two, why not use two of those to make three, etc.?) =Ned=