Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site trwspp.UUCP
Path: utzoo!watmath!clyde!akgua!sdcsvax!sdcrdcf!trwrb!trwspp!hasiuk
From: hasiuk@trwspp.UUCP
Newsgroups: net.puzzle,net.math
Subject: Three Inverter Problem
Message-ID: <426@trwspp.UUCP>
Date: Fri, 18-May-84 22:42:06 EDT
Article-I.D.: trwspp.426
Posted: Fri May 18 22:42:06 1984
Date-Received: Sun, 20-May-84 00:21:59 EDT
Organization: T R W, Redondo Beach, CA
Lines: 28
Xref: 108 205

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!hasiuk