The Periodic Table of 2-Input Logic Gates

For a two-input, one-output digital logic gate (assuming no state memory or feedback), there are a total of sixteen possible behaviors, since for each combination of inputs (00, 01, 10, and 11), the gate must output either a zero or a one. Combining these four behaviors allows description of the gate with four bits, meaning there are sixteen possibilities (0000 through 1111).

Not all of these “gate types” are interesting, however. For example, the “Type 0” gate (whose descriptor is 0000) always outputs a zero, no matter what the inputs are. Similarly, the “Type 15” gate (descriptor 1111) will always output a one.

Some interesting properties that some of the gates have are:

  • Symmetry: If you swap inputs A and B, will the gate act the same way?
  • Triviality: Is the “gate” so trivial that a simple wire will suffice?
  • Commonality: Is the gate a “standard” or commonly-used gate?
  • Inversion: Can the gate invert one or both inputs in at least some cases?
  • Two-input: Do both inputs affect the gate’s output?
  • Universality: Can several of this gate be used to emulate any other gate?

Here is a chart showing the properties of all of the possible behaviors a simple two-input-one-output digital logic gate could exhibit. Some of these are not true “gates”; others are, but lack universality. Interestingly, six of the gate types are universal — meaning that given a sufficient number of them, any other gate type could be created. An entire computer could be created using nothing but NOR gates, for instance.

A chart of all possible simple two-input logic gates. (Click for larger.)

Logic gates of various types can sometimes show up in unexpected places. The humble 555 timer IC, for example, turns out to be capable of functioning as a Type 2 (or Type 4) gate. Since these are universal, a computer using only 555s as active logic is possible!

 

 

This entry was posted in Digital, EET205, Electronics, Fundamentals, Math. Bookmark the permalink.

Leave a Reply