3 ms·

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.
- occamrazor 5y ago
  There are 2^(2x2)=16 possible truth tables with two inputs. The 8 above are the _symmetric_ ones.

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.

occamrazor 5y ago
There are 2^(2x2)=16 possible truth tables with two inputs. The 8 above are the _symmetric_ ones.