5 ms·

Personally, I don't find them that interesting. AND, OR, NAND, and NOR are all non-linear. However, you can implement any logic function with XOR and AND, whi

Personally, I don't find them that interesting. AND, OR, NAND, and NOR are all non-linear. However, you can implement any logic function with XOR and AND, which is essentially modulo-2 addition and multiply. So the whole world of GF(2) algebra applies, and that is how error correction and encryption are analyzed. Goest thou, and study GF(2).

javajuice 7y ago
Xors are slow and expensive . That’s why all you see is nand and nor. This article doesn’t really make much sense. Nobody designs at this level except for understanding and abstraction.
- analognoise 7y ago
  That isn't correct at all; the reason you see NAND/NOR is because they're all that's needed (they are universal). GP was incorrect.
- adrian_b 7y ago
  In most kinds of logic circuit families, a XOR is slightly slower and more expensive than a NAND or a NOR, but it has about the same cost as an AND or an OR, so it does not seem appropriate to call it slow and expensive. Even if in theory you can make any logic gate from a combination of NAND or NOR gates, the XOR gate is almost never done so. In most logic circuit families, including in the most popular families, i.e. TTL and CMOS, there are special circuits for implementing XOR, which are better than a NAND or NOR combination. Also, in most logic circuit families, including in the most popular families, i.e. TTL and CMOS, even if you can implement NAND with NOR and NOR with NAND, this is not done so, but there are distinct circuits for NAND and NOR. In conclusion, in most logic circuit families you do not implement everything with a single kind of universal gate, but you have 3 kinds of basic blocks, NAND, NOR and XOR. In certain logic families you have extra basic blocks, which can be implemented in a better way than the equivalent schematic made of universal gates. Moreover, even if TTL circuits are usually presented as being composed of NAND gates, it is more useful to view the NAND TTL or DTL gate as an AND gate (a minimum-computing circuit made with diodes) followed by an inverter made with a transistor (which can be expanded to a NOR gate by adding parallel transistors). So the real basic blocks of TTL circuits are AND, NOR and XOR (the NOR being not the same as the NOR from the NAND+NOR+XOR description, but a sub-circuit of that), but these simpler AND and NOR blocks cannot be used by themselves, because the AND does not have TTL output levels and the NOR does not have TTL input levels, so you always must have an AND (possibly reduced to a repeater) followed by a NOR (possibly reduced to an inverter), to make a complete TTL gate. My point is that while it is useful to know that any gate can be implemented using only a single kind of universal gate, such implementations are not efficient and you must use a small number of basic blocks, not only one. On the other hand, when you want to understand the theory of logic gates, basing them on one kind of universal gate is also no useful. You can better understand logic operations when you see them as based on minimum (or the equivalent maximum) and on inversion (for values between 0 and 1 inversion is 1-x, for values between -1 and 1 inversion is -x). These 2 operations are also valid when applied to non-binary logic values. The physical implementation of these 2 operations can actually work with real-valued inputs and outputs. An alternative view for the binary logic case is that mentioned by someone above, of having addition & multiplication modulo 2 as the basic operations. Either the minimum/inversion view or the addition/multiplication view give much more insight than reasoning about NAND or NOR, which just combine the 2 basic operations in such a way that a cascade of the combinations can recover each of the basic operations, so they provide an alternative.
analognoise 7y ago
You don't need XOR and AND. You ONLY need NAND (or NOR). NAND/NOR are universal in that they can single handedly construct all other gates. XOR and AND is not a minimal construction. This is well below the level of understanding to get to GF(2).
- adrian_b 7y ago
  See my answer above. Even if a single universal gate is enough if you disregard speed and cost (area and power consumption) when you implement physical logic circuits speed and cost are essential so you cannot use a single type of universal gate but you must use a small number of basic gates, because each of them has a better implementation from diodes and transistors than an implementation made as a cascade of a single type of universal gates.
  - analognoise 7y ago
    Boolean logic says nothing about implementation. They're entirely different levels of abstraction. https://en.wikipedia.org/wiki/Functional_completeness https://en.wikipedia.org/wiki/Functional_completeness This line in particular: "In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal logic gates." Saying that insight isn't useful (that you can reduce any Boolean equation to a single universal gate) - when it is a cornerstone in modern equivalence checking, Boolean SAT solving, and minimization of combinatorial equations) is really, really missing some very key things... It is the kind of fundamental cornerstone that allows modern digital computers to even exist.
    - kragen 7y ago
      Doesn't equivalence checking normally use BDDs, and SAT solving normally use separate AND, OR, and NOT? I mean the algorithm to reduce an expression to CNF is a pretty simple set of local rewrite rules with AND, OR, and NOT; I could be wrong but I feel like the NAND-based equivalent of CNF is quite a bit hairier. As for minimizing combinational logic, don't you want to use the full set of gates available to you in that case, taking into account their cost, and maybe trying to minimize or at least limit circuit depth? It seems like just using NAND would be kind of a step backwards in that case. Karnaugh maps give you DNF; PALs/GALs want DNF; the fact that your DNF PAL circuit might just be two layers of NAND (equivalent to a layer of AND feeding into an OR layer) is kind of an implementation detail, isn't it? I mean you would configure the circuit in the exact same way if it were made out of physical AND and OR gates.

javajuice 7y ago

Xors are slow and expensive . That’s why all you see is nand and nor. This article doesn’t really make much sense. Nobody designs at this level except for understanding and abstraction.

analognoise 7y ago
That isn't correct at all; the reason you see NAND/NOR is because they're all that's needed (they are universal). GP was incorrect.
adrian_b 7y ago
In most kinds of logic circuit families, a XOR is slightly slower and more expensive than a NAND or a NOR, but it has about the same cost as an AND or an OR, so it does not seem appropriate to call it slow and expensive. Even if in theory you can make any logic gate from a combination of NAND or NOR gates, the XOR gate is almost never done so. In most logic circuit families, including in the most popular families, i.e. TTL and CMOS, there are special circuits for implementing XOR, which are better than a NAND or NOR combination. Also, in most logic circuit families, including in the most popular families, i.e. TTL and CMOS, even if you can implement NAND with NOR and NOR with NAND, this is not done so, but there are distinct circuits for NAND and NOR. In conclusion, in most logic circuit families you do not implement everything with a single kind of universal gate, but you have 3 kinds of basic blocks, NAND, NOR and XOR. In certain logic families you have extra basic blocks, which can be implemented in a better way than the equivalent schematic made of universal gates. Moreover, even if TTL circuits are usually presented as being composed of NAND gates, it is more useful to view the NAND TTL or DTL gate as an AND gate (a minimum-computing circuit made with diodes) followed by an inverter made with a transistor (which can be expanded to a NOR gate by adding parallel transistors). So the real basic blocks of TTL circuits are AND, NOR and XOR (the NOR being not the same as the NOR from the NAND+NOR+XOR description, but a sub-circuit of that), but these simpler AND and NOR blocks cannot be used by themselves, because the AND does not have TTL output levels and the NOR does not have TTL input levels, so you always must have an AND (possibly reduced to a repeater) followed by a NOR (possibly reduced to an inverter), to make a complete TTL gate. My point is that while it is useful to know that any gate can be implemented using only a single kind of universal gate, such implementations are not efficient and you must use a small number of basic blocks, not only one. On the other hand, when you want to understand the theory of logic gates, basing them on one kind of universal gate is also no useful. You can better understand logic operations when you see them as based on minimum (or the equivalent maximum) and on inversion (for values between 0 and 1 inversion is 1-x, for values between -1 and 1 inversion is -x). These 2 operations are also valid when applied to non-binary logic values. The physical implementation of these 2 operations can actually work with real-valued inputs and outputs. An alternative view for the binary logic case is that mentioned by someone above, of having addition & multiplication modulo 2 as the basic operations. Either the minimum/inversion view or the addition/multiplication view give much more insight than reasoning about NAND or NOR, which just combine the 2 basic operations in such a way that a cascade of the combinations can recover each of the basic operations, so they provide an alternative.

analognoise 7y ago

You don't need XOR and AND. You ONLY need NAND (or NOR). NAND/NOR are universal in that they can single handedly construct all other gates. XOR and AND is not a minimal construction. This is well below the level of understanding to get to GF(2).

adrian_b 7y ago
See my answer above. Even if a single universal gate is enough if you disregard speed and cost (area and power consumption) when you implement physical logic circuits speed and cost are essential so you cannot use a single type of universal gate but you must use a small number of basic gates, because each of them has a better implementation from diodes and transistors than an implementation made as a cascade of a single type of universal gates.
- analognoise 7y ago
  Boolean logic says nothing about implementation. They're entirely different levels of abstraction. https://en.wikipedia.org/wiki/Functional_completeness https://en.wikipedia.org/wiki/Functional_completeness This line in particular: "In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal logic gates." Saying that insight isn't useful (that you can reduce any Boolean equation to a single universal gate) - when it is a cornerstone in modern equivalence checking, Boolean SAT solving, and minimization of combinatorial equations) is really, really missing some very key things... It is the kind of fundamental cornerstone that allows modern digital computers to even exist.
  - kragen 7y ago
    Doesn't equivalence checking normally use BDDs, and SAT solving normally use separate AND, OR, and NOT? I mean the algorithm to reduce an expression to CNF is a pretty simple set of local rewrite rules with AND, OR, and NOT; I could be wrong but I feel like the NAND-based equivalent of CNF is quite a bit hairier. As for minimizing combinational logic, don't you want to use the full set of gates available to you in that case, taking into account their cost, and maybe trying to minimize or at least limit circuit depth? It seems like just using NAND would be kind of a step backwards in that case. Karnaugh maps give you DNF; PALs/GALs want DNF; the fact that your DNF PAL circuit might just be two layers of NAND (equivalent to a layer of AND feeding into an OR layer) is kind of an implementation detail, isn't it? I mean you would configure the circuit in the exact same way if it were made out of physical AND and OR gates.