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?