Logic Gate Brain Boggler: The Solution(s)

By Max Maxfield |

Rather than power-up a simulator, an Excel spreadsheet can be used to prove the efficaciously of the solutions to our logical conundrum.

Do you recall the Logic Gate Brain Boggler column I posted a few weeks ago? The idea is that we have a black box with three inputs: A, B, C, and three outputs: !A, !B, and !C.

The outputs are the logical inversions of their corresponding inputs. Just to make sure we're all tap-dancing to the same drum beat (and I know whereof I speak, because my dear old dad was a tap-dancer on the variety hall stage prior to WWII), let's view this problem in the form of a truth table as illustrated below.

Our task is to determine the contents of the black box. The rules were that we can use as many AND and OR gates as we like, but only two NOT gates and no XOR or XNOR gates.

Well, recently I received an email from a member of the EEWeb Community informing me that he was convinced there was no solution to this problem. In fact, he presented me with a multi-page logical proof that purported to take us step-by-step from some initial premises to a formal proof that this puzzle was impossible to solve.

I have to say that I was very impressed by the amount of effort my correspondent had put into this work. I would have been even more impressed had he been right LOL. Sad to relate (for him), I happen to be in the possession of three very clever solutions.

Solution #1 by Yin Shih
The main thing to note here, in addition to the elegance of this solution, of course, is that there are only two inversions (i.e., NOT gates), which we see indicated by the '!' characters associated with the equations for the internal signals P1 and P2.

I tell you, working this out from first principles takes a size-16 supercharged brain with "go-faster stripes" painted on the sides, so my heartiest congratulations to Yin Shih for his solution.

Solution #2 by George Harper

George is an old friend of mine. First, I received an email from him saying: "I don't think it can be done." This was followed a little later by a message saying: "I stand corrected, I have the glimpse of an idea as to how it might be done." And, the following morning, after a sleepless night, a triumphant email arrived saying: "It can be done, and this is how you do it!"

Once again, observe that this solution employs only two inversions (i.e., NOT gates), which we see associated with the equations for the internal signals 0or1ones and 0or2ones.

One reason I really like George's solution is that it's easy to follow for a human being. The names of the internal nodes say what these nodes represent in an exceptionally clear way, and you can follow the logical progression step-by-step. To be honest, out of all the solutions shown here, this is my favorite because the proof is right there before you -- you can be convinced of the efficacy of this solution without ever having to simulate it.

Solution #3 by Hadar Agam

Now, this one does take a bit of effort to wrap one's brain around it. Hadar starts by postulating two internal signals called R and S, where R is 1 if two or three inputs are 1, while S is 1 if only one input is 1 or if all three inputs are 1. This is illustrated below in the main truth table on the left.

In turn, this allows us to derive the meanings associated with different combinations of our R and S signals as illustrated above in the truth table on the right, all of which leads us to the following solution.

The proof of the pudding…

There's an old saying that "The proof of the pudding is in the eating." What this means is that the real value of something can be judged only from practical experience or results, and not from appearance or theory.

Still and all, as the Irish say, I was a tad surprised when I communicated the solutions above to my correspondent, only to hear that he still doesn’t believe they solve the problem. Arrgggh (and I mean that most sincerely).

My next thought was to create Verilog or VHDL representations of the three solutions; then create a Verilog or VHDL test bench; and finally run simulations and present the results as graphical waveforms looking something like the following.

Sad to relate, I'm always running as fast as I can, just to stay in the same place. There are too many fun things to do, but not enough time to do them all in. I was chatting about this to my chum, Jay Dowling, gently hinting that it would be great if he could throw the circuits and test bench and simulations together. A short while later, an email arrived from Jay containing this Excel spreadsheet.

Wow! How capriciously cunning. Rather than creating Verilog or VHDL representations and running simulations, Jay simply coded the equations up into Excel cells. I have to admit that I'm jolly impressed. I would never have thought to do this. Actually, this is my bad, because another friend, Aubrey Kagan (a.k.a. Antedelivian) is constantly extolling the virtues of Excel-based solutions to me.

But wait, there's more…

You can only imagine my delight to be able to email Jay's Excel spreadsheet to my doubting Thomas of a correspondent with an accompanying virtual "Tra-dah!" sound playing in my noggin.

You can only imagine my despondency when he still refused to believe that these circuits work as desired. He is pretty firm that he won’t believe it until he sees Verilog or VHDL representations and simulations.

I feel like giving the same look of haughty derision that Sheldon employed on Howard and Raj just before he first met Amy Farrah Fowler on The Big Bang Theory (check out this video of that moment).

In fact, I did just give this look, but it was wasted because no one was here to observe it. The problem is that I'm up to my armpits in alligators fighting fires without a paddle at the moment (I never metaphor I didn’t like), so I'm afraid that this tale will have to stop here... unless you feel the urge to create the circuits in Verilog or VHDL, simulate the little rascals, capture the graphical waveforms, and send everything to me in a compressed ZIP file for me to upload to my server and share with everyone else.

Meanwhile, I would love to hear your thoughts on the three solutions presented above -- and also on Jay's use of the Excel spreadsheet to prove their functionality. Now I've seen this Excel-based technique, I can easily imagine myself using it in my own designs, not the least that it's self-documenting. What say you?

Join the Conversation!

User must log-in to comment.
• by  D B Brumm (edited)
Max, I believe that in the expected Verilog waveform figure the signals for !A and !C (or their labels; take your pick) are interchanged. Interesting problem. Thanks for posting it.
• by  Max Maxfield (edited)
@D B Brumm: "I believe that in the expected Verilog waveform figure the signals for !A and !C (or their labels; take your pick) are interchanged." Arrggghhh -- you are correct -- I'll try to get the diagram changed ASAP -- thanks for spotting this (I tell you, no matter how many times you check... LOL)
• by  Max Maxfield (edited)
@D B Brumm: "Interesting problem. Thanks for posting it." It was my very great pleasure -- this really is one of my favorite logic problems of all time -- I can't tell you how many hours I spent thinking "maybe ... but no ... but how about ... but no..." I would have given up if a friend hadn't assured me that a solution was possible.
• by  Aubrey Kagan (edited)
Max "(a.k.a. Antedelivian)". Tsk, tsk if you are going to misspell it, you should at least do it my way! I just LOVE it when I see a new application in electronics implemented or verified with Excel. Please pass my compliments to Jay. Just as soon as I get back I am going to download and dissect the worksheet. By the way did you see my latest offering on the use of Excel "Use Excel to set DIP switches" http://www.planetanalog.com/author.asp?section_id=3140
• by  Elizabeth Simon (edited)
I came up with a similar spreadsheet except with more columns for intermediate values. It was easier for me to follow that way...
• by  Max Maxfield (edited)
My chum Jack Grubbs just emailed me to say that he really enjoyed this puzzle and that he's created a schematic of George Harper's solution. Jack kindly sent me a copy of this schematic and also said I could share it, so I just uploaded it to my server for you to download, peruse, and ponder at your leisure: http://www.clivemaxfield.com/area51/do-not-delete/max-0048-eeweb-lpp2-sch01.pdf
• by  Conrad Mannering (edited)
@Max, just putting a PSoC 5 schematic together of this and will run it as soon as I can get in my very hot under the eaves lab. It will be interesting to see if the Verilog exactly uses the diagram or if it refines the terms to achieve a better use of resources.
• by  Max Maxfield (edited)
@Conrad: "...just putting a PSoC 5 schematic together of this and will run it as soon..." Very cool -- I look forward to hearing how you get on.
• by  Conrad Mannering (edited)
At the moment Max the temperature is 40 degrees C in my workshop (British Summer Heatwave ). So it may have to wait for the rain to start next week when I go on my holiday in the caravan.
• by  Max Maxfield (edited)
@Conrad: "...it may have to wait for the rain to start next week when I go on my holiday..." Ah -- now you are reminding me of the summers of my youth LOL
• by  Conrad Mannering (edited)
Went a way two weeks ago to Canterbury in Kent and had one of biggest thunder storms and continuous wet weather I have had for some time, well since last year on Dartmoor 14 days sold rain
• by  Conrad Mannering (edited)
Hi Max I start programming the PSoC with Yin Shih's solution and I have now started on putting Jacks schematic into PSoC Creator.
• by  Max Maxfield (edited)
@Conrad: "Went away two weeks ago [...] and had one of biggest thunder storms and continuous wet weather I have had for some time, well since last year on Dartmoor 14 days solid rain..." Remind me to check with you the next time I'm coming to England -- I'll try to come when you are not on vacation so I have a chance of good weather LOL
• by  Aubrey Kagan (edited)
I was in London over the weekend. It was over 28 degC Friday Saturday and Sunday (Sunday got to over 30) without a cloud in the sky. Everyone said it was magnificent weather. I am North American soft- I wanted A/C!
• by  Conrad Mannering (edited)
Hi Aubrey, Max, Its still exceptionally hot but weather will break for Glastonbury festival (of Mud), if you follow tennis, Wimbledon will normally get rained on, while Queens usually has it hot. Just to let you all know I have programmed a PSoC5 with Yin Shih's solution and Jacks schematic, I can confirm for your doubting Thomas that their logic works as per the expected truth tables. It's too chuffing (as in steam engine) hot at the moment for me to even think about video capture of Leds showing logic sequence to a counter input.
• by  Max Maxfield (edited)
@Conrad: "...I can confirm for your doubting Thomas that their logic works as per the expected truth tables..." I'm performing my happiest of happy dances (avert your gaze -- it's not a pretty sight :-)
• by  Conrad Mannering (edited)
@ Max: I'm performing my happiest of happy dances (avert your gaze -- it's not a pretty sight :-) Mother always told me I would end up as a bad influence on people.