10 ms·

This article shows more universal gates than the NAND and NOR that are usually discussed. Are any Hacker News users knowledgeable about the topic? Because I wa

This article shows more universal gates than the NAND and NOR that are usually discussed. Are any Hacker News users knowledgeable about the topic? Because I was wondering why I never heard about these universal gates before. Almost always, only NAND and NOR are discussed.

_0ffh 7y ago
I would guess that NAND and NOR might better lend themselves to practical physical implementation. Also: If you don't limit yourself to 2-input/1-output gates, there's loads more universal gates. Many 3-in/3-out reversible gates are universal [1]. I really have a soft spot for the Fredkin, it just seems so elegant. [1] http://www.thefullwiki.org/Three-input_universal_logic_gate http://www.thefullwiki.org/Three-input_universal_logic_gate
- noajshu 7y ago
  The monotone, linear, etc. functions are called clones and the clones form a lattice called Post's Lattice https://en.wikipedia.org/wiki/Post%27s_lattice https://en.wikipedia.org/wiki/Post%27s_lattice Given several logic gates, if their most recent common ancestor in the lattice is the clone of all boolean functions, then that set is universal. This provides a convenient prescription for deciding universality for a new k-input gate.
- dfox 7y ago
  It really is about physical implementation. In TTL "single input NAND" and invertor is the same physical structure and extending it to multiple inputs involves just adding additional emitters to one BJT structure. For CMOS logic, NOR is the smallest two-input "true" gate, because PMOS transistors have to be larger than NMOS and two series connected MOS transistors can be collapsed into one structure with multiple gates that is significantly smaller than two connected transistors.
- mcphage 7y ago
  > I really have a soft spot for the Fredkin, it just seems so elegant. I agree. It’s so simple, yet it easily leads to other seeminly-more-complicated gates, simply by ignoring some of the inputs or outputs. Plus it has the feature that the # of on inputs always equals the # of on outputs. And the feature that it’s reversible. Really a cool gate all around.
beautifulfreak 7y ago
I'd recommend reading Matrix Logic, by August Stern. It's an approach to logic using vectors, aka matrices. This article doesn't answer why the math works out such that some gates are universal, but Matrix Logic does.
dbcurtis 7y ago
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.
deepnotderp 7y ago
There's tons of universal logic gates outside of the 2 -> 1 domain.
petschge 7y ago
NOR and NAND are symmetric in their arguments. The other four universal gates are anti-symmetric. In other words you have to remember and be careful which input is which. Why would anyone chose to deal with that extra complication when they are no more powerful than the two symmetric universal gates?
coupdejarnac 7y ago
This is some basic freshman or sophomore EE stuff, so that's probably part of the reason why it doesn't get brought up. The other universal, or functionally complete, gates in the article don't get mentioned because they aren't standard parts you can buy.
ttctciyf 7y ago
Not especially knowledgeable, but one factor in the relative lack of interest in other gates might be that NAND and NOR are the only two universal gates which treat their inputs equally. The others ("A and not B", "B and not A", "A or not B", "B or not A") behave differently if you swap A and B, whereas NAND and NOR are symmetrical under that operation. Edit to add: Incidentally, I do remember reading one logic text where boolean algebra was defined in terms of, and built up entirely from, the "B or Not A" gate, which the text called "if" or "->" It is only false when A is true and B is false, which matches what logicians expect from a conditional statement, for example: "if it's raining then it's cloudy" is only contradicted by the combination of raining but not cloudy. If it's not raining, then the statement is not falsified whether there's clouds or not.
kragen 7y ago
Although I have a soft spot for abjunction (as discussed in my wall-of-text comment deeper in the thread), my favorite universal gate is the three-input conditional: x if y else z, or y ? x : z in C or JS syntax, the element from which BDDs are built. (Like abjunction, it's falsehood-preserving, and it's also truth-preserving, so unlike NAND and NOR, it is only "universal" if you have access to constants TRUE and FALSE.) As Darius Bacon has pointed out, one way to generalize it to continuous variables, or variables over arbitrary fields, is as the lerp operation commonly provided by GPUs: yx + (1-y)z, or, without using constants, x + y(z-x). In GF(2), subtraction and addition are both XOR, so that ends up being x ^ y & (z ^ x), which is a correct definition of the operation for bits. The universal reversible gates like the Fredkin gate and the Toffoli gate are also really interesting and potentially important. Designing circuits with separate combinational gates and registers is fairly easy, but it treats the temporal separation of cause and effect as a sort of defect in the universe, and consequently we have to be cautious about glitches (when we don't clock) and metastable states resulting from inadequate setup and hold times (when we do clock). Suppose we continue to discretize time with clocks just as in the current RTL paradigm; can we find a finite state machine that is minimal and universal in some NAND-like sense, and also admits a reasonably tractable design methodology? Would it have two binary inputs, one binary output, and one bit of state? Is it just a J-K flip-flop?

_0ffh 7y ago

I would guess that NAND and NOR might better lend themselves to practical physical implementation. Also: If you don't limit yourself to 2-input/1-output gates, there's loads more universal gates. Many 3-in/3-out reversible gates are universal [1]. I really have a soft spot for the Fredkin, it just seems so elegant. [1] http://www.thefullwiki.org/Three-input_universal_logic_gate http://www.thefullwiki.org/Three-input_universal_logic_gate

noajshu 7y ago
The monotone, linear, etc. functions are called clones and the clones form a lattice called Post's Lattice https://en.wikipedia.org/wiki/Post%27s_lattice https://en.wikipedia.org/wiki/Post%27s_lattice Given several logic gates, if their most recent common ancestor in the lattice is the clone of all boolean functions, then that set is universal. This provides a convenient prescription for deciding universality for a new k-input gate.
dfox 7y ago
It really is about physical implementation. In TTL "single input NAND" and invertor is the same physical structure and extending it to multiple inputs involves just adding additional emitters to one BJT structure. For CMOS logic, NOR is the smallest two-input "true" gate, because PMOS transistors have to be larger than NMOS and two series connected MOS transistors can be collapsed into one structure with multiple gates that is significantly smaller than two connected transistors.
mcphage 7y ago
> I really have a soft spot for the Fredkin, it just seems so elegant. I agree. It’s so simple, yet it easily leads to other seeminly-more-complicated gates, simply by ignoring some of the inputs or outputs. Plus it has the feature that the # of on inputs always equals the # of on outputs. And the feature that it’s reversible. Really a cool gate all around.

beautifulfreak 7y ago

I'd recommend reading Matrix Logic, by August Stern. It's an approach to logic using vectors, aka matrices. This article doesn't answer why the math works out such that some gates are universal, but Matrix Logic does.

dbcurtis 7y ago

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.

deepnotderp 7y ago

There's tons of universal logic gates outside of the 2 -> 1 domain.

petschge 7y ago

NOR and NAND are symmetric in their arguments. The other four universal gates are anti-symmetric. In other words you have to remember and be careful which input is which. Why would anyone chose to deal with that extra complication when they are no more powerful than the two symmetric universal gates?

coupdejarnac 7y ago

This is some basic freshman or sophomore EE stuff, so that's probably part of the reason why it doesn't get brought up. The other universal, or functionally complete, gates in the article don't get mentioned because they aren't standard parts you can buy.

ttctciyf 7y ago

Not especially knowledgeable, but one factor in the relative lack of interest in other gates might be that NAND and NOR are the only two universal gates which treat their inputs equally. The others ("A and not B", "B and not A", "A or not B", "B or not A") behave differently if you swap A and B, whereas NAND and NOR are symmetrical under that operation. Edit to add: Incidentally, I do remember reading one logic text where boolean algebra was defined in terms of, and built up entirely from, the "B or Not A" gate, which the text called "if" or "->" It is only false when A is true and B is false, which matches what logicians expect from a conditional statement, for example: "if it's raining then it's cloudy" is only contradicted by the combination of raining but not cloudy. If it's not raining, then the statement is not falsified whether there's clouds or not.

kragen 7y ago

Although I have a soft spot for abjunction (as discussed in my wall-of-text comment deeper in the thread), my favorite universal gate is the three-input conditional: x if y else z, or y ? x : z in C or JS syntax, the element from which BDDs are built. (Like abjunction, it's falsehood-preserving, and it's also truth-preserving, so unlike NAND and NOR, it is only "universal" if you have access to constants TRUE and FALSE.) As Darius Bacon has pointed out, one way to generalize it to continuous variables, or variables over arbitrary fields, is as the lerp operation commonly provided by GPUs: yx + (1-y)z, or, without using constants, x + y(z-x). In GF(2), subtraction and addition are both XOR, so that ends up being x ^ y & (z ^ x), which is a correct definition of the operation for bits. The universal reversible gates like the Fredkin gate and the Toffoli gate are also really interesting and potentially important. Designing circuits with separate combinational gates and registers is fairly easy, but it treats the temporal separation of cause and effect as a sort of defect in the universe, and consequently we have to be cautious about glitches (when we don't clock) and metastable states resulting from inadequate setup and hold times (when we do clock). Suppose we continue to discretize time with clocks just as in the current RTL paradigm; can we find a finite state machine that is minimal and universal in some NAND-like sense, and also admits a reasonably tractable design methodology? Would it have two binary inputs, one binary output, and one bit of state? Is it just a J-K flip-flop?