5 ms·

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 d

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.

deepCelibate 5y ago
Author here, you are correct. I guess I was trying to express the "saudade" of finding a new topic but not having the time to learn it properly.
- djmips 5y ago
  It was entertaining.
  - deepCelibate 5y ago
    Thanks!
Aardwolf 5y ago
These are helpful and show how any gate can be made from NAND: https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NAND_logic https://www.nand2tetris.org/ https://www.nand2tetris.org/
- pbsd 5y ago
  Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form). 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: NAND(0, 0) = 0*0 + 1 = 1 NAND(x, y) = x*y + 1 AND(x, y) = NAND(NAND(x, y), NAND(x, y)) = (x*y + 1)*(x*y + 1) + 1 = x*y + x*y + x*y + 1 + 1 = x*y XOR(x, y) = NAND(NAND(x, NAND(x, y)), NAND(y, NAND(x, y))) = (x * (x*y + 1) + 1) * (y * (x*y + 1) + 1) + 1 = (x*y + x + 1) * (x*y + y + 1) + 1 = x*y + x*y + x*y + x*y + x*y + x + x*y + y + 1 + 1 = x + y 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.
  - eynsham 5y ago
    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.¹ 0: https://news.ycombinator.com/item?id=28756727 https://news.ycombinator.com/item?id=28756727 1: https://plato.stanford.edu/entries/logic-algebraic-propositional https://plato.stanford.edu/entries/logic-algebraic-propositi...
- mynameismon 5y ago
  Is there an explanation as to why can we do this? i.e. Why can NAND and NOR be used to form all other gates? And why not AND, say?
  - goohle 5y ago
    It's not possible to implement inversion using AND or OR.
  - amalcon 5y ago
    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.
  - cevi 5y ago
    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.
  - goto11 5y ago
    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.
gammalost 5y ago
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. If you want to see it in action try this https://nandgame.com/ https://nandgame.com/
- rahen 5y ago
  Many computers were designed entirely out of NAND gates. Most famously the Cray-1.
- deleted 5y ago
  [deleted]
- deleted 5y ago
  [deleted]
- moffkalast 5y ago
  Well I've been thoroughly nerd sniped by that game, so much for a productive Tuesday.
deleted 5y ago
[deleted]
goto11 5y ago
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. See http://nandgame.com http://nandgame.com if you want to try it for yourself.
st_goliath 5y ago
> 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.") [1] https://sebastiancarlos.medium.com/from-ai-to-zi-an-encyclopedia-of-the-i-tier-tech-stack-a8e828a5bd6a?source=user_profile---------1---------------------------- https://sebastiancarlos.medium.com/from-ai-to-zi-an-encyclop... [2] https://news.ycombinator.com/item?id=28757743 https://news.ycombinator.com/item?id=28757743
- deepCelibate 5y ago
  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.

deepCelibate 5y ago

Author here, you are correct. I guess I was trying to express the "saudade" of finding a new topic but not having the time to learn it properly.

djmips 5y ago
It was entertaining.
- deepCelibate 5y ago
  Thanks!

Aardwolf 5y ago

These are helpful and show how any gate can be made from NAND: https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NAND_logic https://www.nand2tetris.org/ https://www.nand2tetris.org/

pbsd 5y ago
Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form). 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: NAND(0, 0) = 0*0 + 1 = 1 NAND(x, y) = x*y + 1 AND(x, y) = NAND(NAND(x, y), NAND(x, y)) = (x*y + 1)*(x*y + 1) + 1 = x*y + x*y + x*y + 1 + 1 = x*y XOR(x, y) = NAND(NAND(x, NAND(x, y)), NAND(y, NAND(x, y))) = (x * (x*y + 1) + 1) * (y * (x*y + 1) + 1) + 1 = (x*y + x + 1) * (x*y + y + 1) + 1 = x*y + x*y + x*y + x*y + x*y + x + x*y + y + 1 + 1 = x + y 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.
- eynsham 5y ago
  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.¹ 0: https://news.ycombinator.com/item?id=28756727 https://news.ycombinator.com/item?id=28756727 1: https://plato.stanford.edu/entries/logic-algebraic-propositional https://plato.stanford.edu/entries/logic-algebraic-propositi...
mynameismon 5y ago
Is there an explanation as to why can we do this? i.e. Why can NAND and NOR be used to form all other gates? And why not AND, say?
- goohle 5y ago
  It's not possible to implement inversion using AND or OR.
- amalcon 5y ago
  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.
- cevi 5y ago
  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.
- goto11 5y ago
  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.

gammalost 5y ago

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. If you want to see it in action try this https://nandgame.com/ https://nandgame.com/

rahen 5y ago
Many computers were designed entirely out of NAND gates. Most famously the Cray-1.
deleted 5y ago
[deleted]
deleted 5y ago
[deleted]
moffkalast 5y ago
Well I've been thoroughly nerd sniped by that game, so much for a productive Tuesday.

deleted 5y ago

[deleted]

goto11 5y ago

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. See http://nandgame.com http://nandgame.com if you want to try it for yourself.

st_goliath 5y ago

> 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.") [1] https://sebastiancarlos.medium.com/from-ai-to-zi-an-encyclopedia-of-the-i-tier-tech-stack-a8e828a5bd6a?source=user_profile---------1---------------------------- https://sebastiancarlos.medium.com/from-ai-to-zi-an-encyclop... [2] https://news.ycombinator.com/item?id=28757743 https://news.ycombinator.com/item?id=28757743

deepCelibate 5y ago
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.