0
\$\begingroup\$

Now I know the maths and logic to figure out that every boolean function can be expressed using only AND and NOT gates, which in turn can be expressed using only NAND gate and hence every boolean function can be expressed using only combination of NANDs. I know the math, I can easily work out the how.

But, I am looking for a more intuitive (not necessarily non-mathematical, maybe philosophical) reason as to why this has to be true (if there is such a reason at all). For some reason I think that it is not just a mathematical fact that NAND gate is universal, there must be a more "deeper" reason or something in property of NAND gates that has this, if I am able to explain myself.

So, is there really such a reason? Or is the universal nature of NANDs really just a mathematical artificact just discovered by us somehow?

EDIT : Fixed the basic gates. I messed up that.

\$\endgroup\$
  • \$\begingroup\$ You do realize NOR gates are also universal right? Not just NAND gates? \$\endgroup\$ – DKNguyen Aug 1 at 17:47
  • \$\begingroup\$ Well the fact you only ask about NAND indicates that you think a NAND is somehow special. I pointed out NOR to show that it isn't. And the fact they are both universal might point to the simple fact all you need to do is mix a NOT gate into the mix. OR and AND, together, do pretty much everything...except a NOT, and with a NOT available, it doesn't matter whether you choose to use OR or AND since they are just duals of each other. \$\endgroup\$ – DKNguyen Aug 1 at 17:50
  • \$\begingroup\$ My gut feeling is that you should look up conjunctive and disjunctive normal forms and their proofs. But I'm also not sure if that's what you are asking for. \$\endgroup\$ – jonk Aug 1 at 18:37
5
\$\begingroup\$

Now I know the maths and logic to figure out that every boolean function can be expressed using only AND and OR gates

Untrue. You also need inverters.

every boolean function can be expressed using only combination of NANDs.

True. Or you can do it with NOR gates...

But, I am looking for a more intuitive (not necessarily non-mathematical, maybe philosophical) reason as to why this has to be true (if there is such a reason at all)

What both NAND and NOR have in common is that they:

  • Allow you to "recognize" one unique possibility of the four in a two-input logic table.

  • Allow you to build an inverter by feeing the same signal to both inputs

So basically you have a "test" engine and an "transform" engine; you use the "transform" engine as needed to turn the pattern you want to look for into the pattern the "test" engine does look for, and then the "transform" engine to turn the result into what you want.

And if you need to detect multiple patterns, you treat having both of them satisfied (or neither of their anti-patterns satisfied) as the pattern to be detected in another stage.

Or just find a napkin and draw all the other gates as a collection of NAND gates...

\$\endgroup\$
  • \$\begingroup\$ "So basically you have a "test" engine and an "transform" engine; you use the "transform" engine as needed to turn the pattern you want to look for into the pattern the "test" engine does look for, and then the "transform" engine to turn the result into what you want." -- A fantastic explanation. +1! \$\endgroup\$ – Shamtam Aug 1 at 18:32
  • \$\begingroup\$ Interestingly, using n inverters along with a sufficient number of AND and OR gates, one can build a purely-combinatorial circuit with 2ⁿ-1 inputs and 2ⁿ-1 outputs, whose steady-state outputs will be the inverse of the inputs. \$\endgroup\$ – supercat Aug 1 at 20:29
1
\$\begingroup\$

I find De Morgan's laws very intuitive:

If you need A and B to achieve X, than, if you don't have A or B, you don't have X.

enter image description here

And you have the sum of products, intuitively: each AND detects a specific combination with a HIGH output, and you OR them together.

A similar approach applies to NOR gates and the product of sums.

\$\endgroup\$

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.