Spark & Anvil Privacy

Reference

The logic gates

A gate takes one or two inputs, each on (1) or off (0), and gives one output. Six gates build everything a computer does. The little table under each gate is its truth table — it shows the output for every possible input. Back to the lab anytime: Open the circuit lab →

  • AND &

    On only when BOTH inputs are on. Think "a and b are both true".

    about
    000
    100
    010
    111
  • OR ≥1

    On when AT LEAST ONE input is on. Off only when both are off.

    about
    000
    101
    011
    111
  • NOT ¬

    Flips one input: on becomes off, off becomes on. The only one-input gate.

    about
    0—1
    1—0
  • XOR =1

    On when the two inputs are DIFFERENT (exactly one is on). This is the "sum" bit of adding.

    about
    000
    101
    011
    110
  • NAND &̄

    AND, then flipped — off only when both inputs are on. Every other gate can be built from just NAND.

    about
    001
    101
    011
    110
  • NOR ≥1̄

    OR, then flipped — on only when both inputs are off.

    about
    001
    100
    010
    110
Where this idea comes from

Truth tables and switches

In 1854 the English mathematician George Boole published The Laws of Thought, which writes logic as algebra with only two values. In 1937 Claude Shannon, a student at MIT, showed that Boole’s algebra describes circuits of electrical switches.

One thing to hold: A light switch: on is true, off is false.

Why it matters: Every chip in a phone or computer is built from tiny switches that follow Boole’s rules.

Dates:

  1. 1854 Boole publishes The Laws of Thought.
  2. 1921 Ludwig Wittgenstein (in the Tractatus) and Emil Post (in the American Journal of Mathematics) each publish truth tables.
  3. 1937 Shannon’s master’s thesis links Boole’s algebra to switching circuits.

Sources: George Boole, An Investigation of the Laws of Thought (1854) · Emil L. Post, “Introduction to a General Theory of Elementary Propositions”, American Journal of Mathematics 43 (1921) · Claude E. Shannon, “A Symbolic Analysis of Relay and Switching Circuits” (MIT thesis, 1937) · Stanford Encyclopedia of Philosophy, “The Algebra of Logic Tradition”

One gate to make them all

NAND ("not and") gives 0 only when both its inputs are 1. Join enough NAND gates and you can build NOT, AND, OR, XOR — every other gate — which is why GateForge has NAND-only levels. Its twin, NOR ("neither…nor"), can do the same.

One thing to hold: A short note by the American logician Charles Sanders Peirce, written around 1880, showing that one operation — "neither…nor", or its twin "not both" — is enough for all of logic. He never published it.

Why it matters: If one kind of gate can build every other, a chip can be made from millions of copies of the same tiny part.

What we don’t know: Who found it first is tangled. After Peirce, Edward Stamm printed both operations in 1911 and Henry Sheffer in 1913. Sheffer’s stroke meant "neither…nor"; Jean Nicod read it as "not both" in 1917, and that is what "Sheffer stroke" means today.

Dates:

  1. 1880 About now, Peirce shows one operation is enough, in a note he never publishes.
  2. 1911 Edward Stamm prints both operations.
  3. 1913 Sheffer publishes his stroke, meaning "neither…nor".
  4. 1917 Jean Nicod reads the stroke as "not both", the meaning it has today.

Sources: Charles S. Peirce, "A Boolian Algebra with One Constant" (c. 1880), in Collected Papers, vol. 4 (Harvard University Press, 1933) · Edward Stamm, "Beitrag zur Algebra der Logik", Monatshefte für Mathematik und Physik 22 (1911) · Henry M. Sheffer, "A Set of Five Independent Postulates for Boolean Algebras", Transactions of the American Mathematical Society 14(4), 1913 · Jean Nicod, "A Reduction in the Number of the Primitive Propositions of Logic", Proceedings of the Cambridge Philosophical Society 19 (1917)

Adding two bits needs just two gates: the sum is a XOR b and the carry is a AND b. Chain those and you have built an adder — the heart of a CPU. Try a challenge →