13
$\begingroup$

You've just been hired by Widget & Co. to prototype a new electrical circuit for their line of impenetrable puzzle locks. As part of this circuit, your boss asks you to invert three boolean inputs.

"Easy", you say, until you look around the lab for parts. To your dismay you can only find two boolean inverters (NOT) gates. There's a big stash of AND and OR gates, but it seems the interns before you have taken the rest of the NOT gates.

So! Design a circuit which uses at most two NOT gates, and an unlimited number of 2-input AND and OR gates, to successfully invert three inputs.

Diagrammatically:

A ----                ---- NOT A
      \              /
B -----[YOUR CIRCUIT]----- NOT B
      /              \
C ----                ---- NOT C

I guarantee this can be done, and that this doesn't rely on some trick interpretation of the question.

$\endgroup$
  • $\begingroup$ How fast is each component/are timing based circuits allowed? $\endgroup$ – fibonatic Feb 22 '15 at 15:04
  • 4
    $\begingroup$ See the discussion at electronics.stackexchange.com/questions/98308/… $\endgroup$ – Gamow Feb 22 '15 at 15:15
  • $\begingroup$ And do all AND and OR gates always have two inputs, or can they have any number of inputs? $\endgroup$ – fibonatic Feb 22 '15 at 15:23
  • $\begingroup$ @fibonatic: assume zero propagation delay. Timing is not a factor: do not make a circuit with a feedback loop. Given unlimited two-input AND and OR gates, you can make n-input gates, so I clarified it to say the building-blocks are two-input. $\endgroup$ – nneonneo Feb 22 '15 at 16:20
  • 1
    $\begingroup$ @nneonneo I was planning on using a mux/demux with one inverter in between controlled by a clock which contains the other inverter. This circuit could be scaled to any finite number of inputs, but without delay all of this will not be possible. $\endgroup$ – fibonatic Feb 22 '15 at 16:27
13
$\begingroup$

I built a logic gate structure based on supercat's textual explanation (given in user2357112's answer and Gamow's comment); trace it at your leisure. It's a good thing we are given an infinite supply of AND and OR gates.

Edit: Added annotations. Expand the image if they are too small.
Other edit suggestions are welcomed! Three inputs inverted using two NOT gates

$\endgroup$
  • 3
    $\begingroup$ amazing. 10x more useful than the text imho. $\endgroup$ – d'alar'cop Feb 22 '15 at 19:47
  • $\begingroup$ Thanks. I wasn't sure if I wanted to post this as-is, or attempt to compact the lines and clean it up a little first. I might still do that and edit it again later. $\endgroup$ – Bulldogg6404 Feb 22 '15 at 19:53
  • 1
    $\begingroup$ Although it's obvious to most people, I would add a courtesy legend showing which symbol is AND which is OR and which NOT. (Plenty of space for it). Also, for a "full proof" you might want to index the pieces and table their output in all 27 cases.... Otherwise, great. $\endgroup$ – BmyGuest Feb 22 '15 at 21:27
  • 1
    $\begingroup$ If people understand logic gates enough to try solving, I figured they would know what the logic gate looks like. I might provide a legend in a future update, nonetheless. Also, there are only 2^3 = 8 cases, not 27. [000,001...111] $\endgroup$ – Bulldogg6404 Feb 22 '15 at 21:44
  • $\begingroup$ It may be useful to add annotations to the inputs/outputs of the inverters: one of them indicates that at least two/less than two inputs are high, and the reports whether there are an odd/even number of inputs high, which can be true if either all inputs are high, or less than two are high but at least one is. The logic in the output stage then ends up resembling "blue-eyed islanders", e.g. "if less than two inputs are true, but one of the others is true, that means my input must be false, so my output should be high". $\endgroup$ – supercat Feb 23 '15 at 16:15
4
$\begingroup$

Solved over at http://electronics.stackexchange.com in the link provided by Gamow in the comments. This is a direct quote of supercat's excellent answer; go upvote that.

It is possible to construct a purely-combinatorial three-input circuit consisting of a number of AND and OR gates along with exactly two independent inverters, with three outputs whose steady-state condition will be the inverse of the inputs. Note that the input to the second inverter will be affected by the output from the first, and that all three outputs are affected by the signals from both inverters. Consequently, one cannot use two of the inputs and outputs of one such circuit to serve as the "inverters" for another.

Assume the inputs are A, B, C and the outputs are X,Y, Z. Using AND and OR gates, determine whether at least two of the inputs are high. Invert that to get a signal which would indicate that at least two are low. Feeding that signal along with the original signals into AND and OR gates, generate a signal which would indicate that an odd number of inputs are high. Invert that to get a signal saying that an odd number are low.

Once one has generated the aforementioned signals, output X should be high if either all three inputs are low (both inverters outputting true), at least two are low and either B or C is true (which would imply that A must be false), or at least one is low and both B and C are true. Outputs Y and Z should be computed similarly.

The principle can be extended to produce a seven I/O combinatorial circuit using three independent inverters and a lot of AND/OR gates. First determine if there are four or more inputs high. Invert that to say there are four or more low. Then determine if the number is 2, 3, 6, or 7. Invert that to say there are 0, 1, 4, or 5. Then determine if the number is odd, and invert it to say it's even.

After having done all that, each output Q should be high if all three inverters output high (all seven inputs low), or if the first two inverters are high and at least one input not associated with Q is high, or the first and last inverters are high and at least two inputs not associated with Q are high, or the first inverter is high and at least three inputs not associated with Q are high, or at the second and third inverters are high and at least four inputs not associated with Q are high, or the second inverter is high and at least five inputs not associated with Q are high, or the first inverter is high and all six inputs not associated with Q are high.

Theoretically, one could design a circuit for 15 I/O's using four inverters, or 31 using five, or 63 using six, etc. but the number of AND and OR gates required would be mind-blowing.

$\endgroup$
4
$\begingroup$

This is a solution:

First compute $S, T$ as follows:
$S=\overline{AB+BC+CA}$,
$T=\overline{SA+SB+SC+ABC}$
Then we have
$\overline{A} = S(T+B+C)+TBC$
$\overline{B} = S(T+C+A)+TCA$
$\overline{C} = S(T+A+B)+TAB$

$\endgroup$
  • $\begingroup$ You can add a spoiler with the >! spoiler tag. I will edit it in for you. $\endgroup$ – wythagoras Jan 30 '16 at 11:07
  • $\begingroup$ Welcome to Puzzling.SE! This is a great answer, although you may want to edit in the explanation that multiplication represents "AND" and addition represents "OR", because many of us here are unfamiliar with electronics. In any case, I hope to see you around here more! c: $\endgroup$ – Deusovi Jan 30 '16 at 12:29
  • 1
    $\begingroup$ Beautifully done! $\endgroup$ – Mike Earnest Jan 30 '16 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.