14
$\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.

Improve this question
$\endgroup$
10
  • $\begingroup$ How fast is each component/are timing based circuits allowed? $\endgroup$
    – fibonatic
    Feb 22, 2015 at 15:04
  • 4
    $\begingroup$ See the discussion at electronics.stackexchange.com/questions/98308/… $\endgroup$
    – Gamow
    Feb 22, 2015 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, 2015 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, 2015 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, 2015 at 16:27

3 Answers 3

Reset to default
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

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ amazing. 10x more useful than the text imho. $\endgroup$
    – d'alar'cop
    Feb 22, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 16:15
5
$\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$

Improve this answer
$\endgroup$
3
  • $\begingroup$ You can add a spoiler with the >! spoiler tag. I will edit it in for you. $\endgroup$
    – wythagoras
    Jan 30, 2016 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, 2016 at 12:29
  • 1
    $\begingroup$ Beautifully done! $\endgroup$
    – Mike Earnest
    Jan 30, 2016 at 16:45
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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