Well I was hoping to read an article about why or how the NAND gate is so important but the most I've been able to gather from this article is that the author doesn't know either and is unable to interpret any of the relevant literature.
Since both AND and XOR can be obtained from NAND, any polynomial can be constructed. It also becomes obvious that you can't get x*y from x+y and vice-versa, so neither XOR nor AND can be universal gates on their own.
NOR's algebraic form is x*y + x + y + 1, from which you can similarly derive AND and XOR. XNOR is x + y + 1, from which AND cannot be obtained.
Ah yes, this is probably a more intuitive way of doing things than in my comment (though of course we prove different things).⁰ I should add that for those interested, the SEP page on algebraic propositional logic is quite interesting, although I regrettably have not actually gotten round to working through it.¹
You need a function of more inputs than outputs in order to compose into a function of multiple inputs and a single output. This rules out NOT.
Then, we just need to rule out all functions that can't build NOT (i.e. invert one of their inputs). AND and OR obviously can't do this. XOR and XNOR can, but only if you can guarantee a consistent synthetic input, which is not a good requirement from either a theoretical or practical perspective. NAND and NOR can implement NOT by just repeating the same input twice.
This is the topic of "clone theory": the study of which (multivariable) operations can be created by composing together a starting collection of operations. Post's lattice is a complete description of which gates can be generated from which other gates in two-valued logic, but the subject becomes much more difficult in multivalued logic.
If you are just interested in whether a given gate would allow you to generate all possible operations in a multivalued logic, then there is a nice result called the Rosenberg Completeness Theorem that says, roughly speaking, that any operation which doesn't have a nice property (from a certain explicit list of nice properties, such as monotonicity, linearity, etc.) will generate all other operations. To answer your question, NAND is special because it isn't monotone, isn't linear (in the sense of not being a linear function modulo 2), isn't self-dual, doesn't send all-0s to 0, and doesn't send all-1s to 1.
The important quality of NAND and NOR gates is they can be used as inverters. Send the same value to both inputs and the output will be the inverse. Without an inverter you can't really get anywhere.
There are 8 possible truth tables for two inputs, so we have 8 possible gates. But two of them are obviously useless, the one which yield true for any input and one which yield false for any input. So we have 6 useful gates.
These are AND, OR, XOR, NAND, NOR and XNOR.
Of these, only NAND and NOR can be used as inverters.
Given an inverter and any of the gates you can build any other. E.g AND with an inverted output is NAND, NAND with inverted inputs are OR, OR with inverted output is NOR. XOR can be build by combining NAND and OR.
NAND-gates are important because every other boolean operation can be made with a combination of them. This means that you can construct a computer out of nothing but them.
Using only NAND-gates, you can implement any other logic gates which means you can build an entire programmable computer using only NAND-gates.
For example, if you send the same signal to both inputs of a NAND gate, you have an inverter, i.e. a NOT-gate. If you place a NOT gate after a NAND-gate then the combination is an AND gate. If you invert both inputs you have an OR gate. Binary addition can be built from AND + XOR, subtraction from addition and so forth.
If you pipe the output of an OR-gate back to one of the inputs, then you have a latch which can remember one bit of information. Combine two latches you have flip-flop which can be driven by a clock signal. (The clock signal can be generated by a loop of NOT-gates.) Place flip-flops in parallel you have RAM.
> the most I've been able to gather from this article is that the author doesn't know either and is unable to interpret any of the relevant literature.
I got the impression that the author is very familiar with the topic and wrote this for shits'n giggles. The "article" is a string of entertaining nonsense that doesn't go anywhere and seems to purely mock some of the typical philosophical musings filled pseudo-tutorial articles that crop up on HN from time to time. Especially comparing it some other stuff on that site[1].
The witty writing style, completely silly analogies and puns somehow remind me of a certain Unix-grey-beard that I had as a high school teacher (the "FerdiNAND" line would be spot on for the guy).
And yes, I have read the response from the author below yours[2], and I believe there's some brilliant trolling going on here at the moment. ("oh yes, you're right! I actually am utterly clueless.")
Author here. You are correct about everything. I appreciate that you took the time to write this.
The only exception is that, honestly, I'm not very familiar with the topic. I did try to mock the typical pseudo-tutorial articles, but I don't claim that I can do any better.
In standard NMOS or PMOS circuitry, both a NAND gate and a NOR gate require two transistors each (and a resistor, which is usually actually a transistor as well). CMOS requires four transistors for both a NAND gate or a NOR gate. It's only in TTL logic, where you can have a single transistor with multiple emitters that a NAND gate uses fewer transistors.
If you are building a CMOS 2-input gate then both NAND and NOR use 4 transistors. (2 NMOS and 2 PMOS each)
The reason NAND is preferred is that NMOS transistors have roughly half the resistance of a PMOS transistor of the same size. This means that to get a gate with pull-up and pull-down networks of equal strength (which is usually desirable), the NOR gate needs very large PMOS transistors and tiny NMOS while the NAND gate has all of its' transistors equally sized and relatively small.
The result is that NAND gates are smaller in size and slightly quicker than an equivalent NOR gate.
That's pass-transistor logic, which is used in lots of processors. The problem is that your voltage levels drop through each gate, so you can't chain many gates together. You need to have "normal" gates in between.
A "normal" gate amplifies and restores the voltage level so what you get out is better than what you put in. But in most technologies, the amplification stage also inverts, so you end up with basic gates such as NAND/NOR/AND-OR-INVERT, rather than AND/OR.
In all fairness, the previous versions didn't post correctly; they were never visible (you can verify this). I think it was an issue caused by the temporary outage yesterday.
The article doesn’t really explain very much (not that it ought to explain everything, but there’s very little).
The proof of the standard claims about ‘expressive adequacy’ (=functional completeness) in propositional logic is given in cap. 4 of Button’s Metatheory; forallx:Cambridge uses the same notation and gives a fairly easy (from a skim) introduction to propositional logic.¹
Briefly, however, a simple method of dealing with at least some of the cases is as follows.
Consider the connectives of propositional logic (e.g., ¬, ∧, ∨—add more symbols to taste to represent every other possible connective given by a truth table on two variables).
A sentence contains various sentence letters (P, Q, R, P₁, Q₁, R₁, P₂…—adjust to taste) and connectives; we define them inductively, with the base ‘atomic’ cases as the sentence letters and the inductive cases
- ¬φ where φ is a sentence,
- (φ · ψ) where φ and ψ are sentences, and · is some ‘binary connective’ (i.e., it corresponds to a function given by a truth table with two variables: it could be ∧ or ∨ or even the Quine dagger.)
Now, let the complexity of a sentence be the number of connectives appearing within it, which is equal to the number of invocations of one of the inductive rules above required to obtain a sentence (one can also think of sentences as trees).
We use induction on the complexity of a sentence to prove statements about all sentences. Let us consider, by way of example, or (∨). We can prove that ∨ alone is not expressively adequate.
Consider an assignment of truth values such that the truth value of any sentence letter is T(rue). Now, it should be possible to write some sentence the truth value of which is F(alse) solely using ∨, if ∨ is expressively adequate.
The difficulty is that one can’t. Informally, ∨ cannot take two true statements and give a false one, but it only has (under this assignment of truth values) true statements. It is easy to fill in the base and inductive cases because propositional logic is truth-functional (i.e., it does not matter what a proposition says, merely whether it is true or false.)
Similar strategies to find properties invariant under the use of inductive rules may be used to prove all sorts of metalogical statements, as shown in Button’s book.
I seem to have learned this shit before there were (affordable) logic circuits. NAND was simply a transistor (or relay (or tube)) with punch of diodes pulling the gate or base down. We learned to use "Karnaugh Maps" to simplify the logic circutry to these bare NANDs. https://en.wikipedia.org/wiki/Karnaugh_map
That would have been a good while ago. You didn't build digital stuff out of TTL on breadboards? Now that I'm typing this, I am getting a hint from the parenthetical "(or relay (or tube))" :)
edit: I was personally an innovator of the "WAS" gate. They're made of smoke.
There were American SN7400s in 1974 of course, but they were expensive compared to single transistors. I also remember the Finnish Parliament voting machine, made with transistors and relays around 1968. It was huge incomprehensible mess on hand-wired breadboards. It was easier to make totally new one with microprocessors and printed circuits.
Back in the 1990s I did the UC Berkeley computer hardware qualifying exam, which required building an entire pipelined RISC processor bottom-up out of nothing but NAND gates. We had three hours. Of course you build latches and D-flops out of NAND gates with feedback, and we could assume an external source for the clock. It was fun but I wouldn't want to do it again.
53 comments
[ 3.7 ms ] story [ 109 ms ] threadhttps://en.wikipedia.org/wiki/NAND_logic
https://www.nand2tetris.org/
Modulo 2, AND is multiplication and XOR is addition. We also have the useful properties 1+1=0, x+x=0, and x^2 = x. Thus:
Since both AND and XOR can be obtained from NAND, any polynomial can be constructed. It also becomes obvious that you can't get x*y from x+y and vice-versa, so neither XOR nor AND can be universal gates on their own.NOR's algebraic form is x*y + x + y + 1, from which you can similarly derive AND and XOR. XNOR is x + y + 1, from which AND cannot be obtained.
0: https://news.ycombinator.com/item?id=28756727
1: https://plato.stanford.edu/entries/logic-algebraic-propositi...
i.e. Why can NAND and NOR be used to form all other gates? And why not AND, say?
Then, we just need to rule out all functions that can't build NOT (i.e. invert one of their inputs). AND and OR obviously can't do this. XOR and XNOR can, but only if you can guarantee a consistent synthetic input, which is not a good requirement from either a theoretical or practical perspective. NAND and NOR can implement NOT by just repeating the same input twice.
If you are just interested in whether a given gate would allow you to generate all possible operations in a multivalued logic, then there is a nice result called the Rosenberg Completeness Theorem that says, roughly speaking, that any operation which doesn't have a nice property (from a certain explicit list of nice properties, such as monotonicity, linearity, etc.) will generate all other operations. To answer your question, NAND is special because it isn't monotone, isn't linear (in the sense of not being a linear function modulo 2), isn't self-dual, doesn't send all-0s to 0, and doesn't send all-1s to 1.
There are 8 possible truth tables for two inputs, so we have 8 possible gates. But two of them are obviously useless, the one which yield true for any input and one which yield false for any input. So we have 6 useful gates.
These are AND, OR, XOR, NAND, NOR and XNOR.
Of these, only NAND and NOR can be used as inverters.
Given an inverter and any of the gates you can build any other. E.g AND with an inverted output is NAND, NAND with inverted inputs are OR, OR with inverted output is NOR. XOR can be build by combining NAND and OR.
If you want to see it in action try this https://nandgame.com/
I guess I was trying to express the "saudade" of finding a new topic but not having the time to learn it properly.
For example, if you send the same signal to both inputs of a NAND gate, you have an inverter, i.e. a NOT-gate. If you place a NOT gate after a NAND-gate then the combination is an AND gate. If you invert both inputs you have an OR gate. Binary addition can be built from AND + XOR, subtraction from addition and so forth.
If you pipe the output of an OR-gate back to one of the inputs, then you have a latch which can remember one bit of information. Combine two latches you have flip-flop which can be driven by a clock signal. (The clock signal can be generated by a loop of NOT-gates.) Place flip-flops in parallel you have RAM.
See http://nandgame.com if you want to try it for yourself.
I got the impression that the author is very familiar with the topic and wrote this for shits'n giggles. The "article" is a string of entertaining nonsense that doesn't go anywhere and seems to purely mock some of the typical philosophical musings filled pseudo-tutorial articles that crop up on HN from time to time. Especially comparing it some other stuff on that site[1].
The witty writing style, completely silly analogies and puns somehow remind me of a certain Unix-grey-beard that I had as a high school teacher (the "FerdiNAND" line would be spot on for the guy).
And yes, I have read the response from the author below yours[2], and I believe there's some brilliant trolling going on here at the moment. ("oh yes, you're right! I actually am utterly clueless.")
[1] https://sebastiancarlos.medium.com/from-ai-to-zi-an-encyclop...
[2] https://news.ycombinator.com/item?id=28757743
The only exception is that, honestly, I'm not very familiar with the topic. I did try to mock the typical pseudo-tutorial articles, but I don't claim that I can do any better.
I would add that the NOR gate is also functionally complete.
The reason NAND is preferred is that NMOS transistors have roughly half the resistance of a PMOS transistor of the same size. This means that to get a gate with pull-up and pull-down networks of equal strength (which is usually desirable), the NOR gate needs very large PMOS transistors and tiny NMOS while the NAND gate has all of its' transistors equally sized and relatively small.
The result is that NAND gates are smaller in size and slightly quicker than an equivalent NOR gate.
Yes, one good example being the Apollo Guidance Computer [0], which was constructed wholly using NOR gates.
[0] https://en.wikipedia.org/wiki/Apollo_Guidance_Computer#Desig...
[1] https://www.nand2tetris.org/
https://www.allaboutcircuits.com/uploads/articles/CMOS-AND-g...
A "normal" gate amplifies and restores the voltage level so what you get out is better than what you put in. But in most technologies, the amplification stage also inverts, so you end up with basic gates such as NAND/NOR/AND-OR-INVERT, rather than AND/OR.
https://en.wikipedia.org/wiki/Pass_transistor_logic
The proof of the standard claims about ‘expressive adequacy’ (=functional completeness) in propositional logic is given in cap. 4 of Button’s Metatheory; forallx:Cambridge uses the same notation and gives a fairly easy (from a skim) introduction to propositional logic.¹
Briefly, however, a simple method of dealing with at least some of the cases is as follows.
Consider the connectives of propositional logic (e.g., ¬, ∧, ∨—add more symbols to taste to represent every other possible connective given by a truth table on two variables).
A sentence contains various sentence letters (P, Q, R, P₁, Q₁, R₁, P₂…—adjust to taste) and connectives; we define them inductively, with the base ‘atomic’ cases as the sentence letters and the inductive cases
- ¬φ where φ is a sentence,
- (φ · ψ) where φ and ψ are sentences, and · is some ‘binary connective’ (i.e., it corresponds to a function given by a truth table with two variables: it could be ∧ or ∨ or even the Quine dagger.)
Now, let the complexity of a sentence be the number of connectives appearing within it, which is equal to the number of invocations of one of the inductive rules above required to obtain a sentence (one can also think of sentences as trees).
We use induction on the complexity of a sentence to prove statements about all sentences. Let us consider, by way of example, or (∨). We can prove that ∨ alone is not expressively adequate.
Consider an assignment of truth values such that the truth value of any sentence letter is T(rue). Now, it should be possible to write some sentence the truth value of which is F(alse) solely using ∨, if ∨ is expressively adequate.
The difficulty is that one can’t. Informally, ∨ cannot take two true statements and give a false one, but it only has (under this assignment of truth values) true statements. It is easy to fill in the base and inductive cases because propositional logic is truth-functional (i.e., it does not matter what a proposition says, merely whether it is true or false.)
Similar strategies to find properties invariant under the use of inductive rules may be used to prove all sorts of metalogical statements, as shown in Button’s book.
0: available at http://www.homepages.ucl.ac.uk/~uctytbu/Metatheory.pdf
1: http://www.homepages.ucl.ac.uk/~uctytbu/OERs.html
The signal from input A to the output is either inverted or not inverted depending on the state of input B.
That would have been a good while ago. You didn't build digital stuff out of TTL on breadboards? Now that I'm typing this, I am getting a hint from the parenthetical "(or relay (or tube))" :)
edit: I was personally an innovator of the "WAS" gate. They're made of smoke.
;)
Also, glad to know that, according to Wikipedia, Mr. Karnaugh is alive.
https://www.youtube.com/watch?v=JIruJ8edYYM https://www.cs.cmu.edu/~odonnell/boolean-analysis/
And his book: http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-...
Some recent progress in the field includes the amazingly simple proof of the Sensitivity Theorem by Hao Huang: https://arxiv.org/abs/1907.00847
Here's Knuth's one-page proof: https://www.cs.stanford.edu/~knuth/papers/huang.pdf