The single logical operator that powers every computer processor in the modern world
In short: The Sheffer stroke, or NAND gate, is a logical operation that produces a false output only when both inputs are true. While seemingly simple, this single operator is functionally complete, meaning it can replicate every other logical operation. It is the fundamental building block of modern digital electronics.
In propositional logic, the Sheffer stroke represents non-conjunction, or 'not both.' It returns true if at least one of its two input propositions is false. While Henry Maurice Sheffer is the namesake, the history of this operator is layered with misattributions. Sheffer published a paper in 1913 providing an axiomatization of Boolean algebras using the stroke, but he actually interpreted it as non-disjunction, or NOR. It was Jean Nicod who, in 1917, first used the stroke to represent the NAND operation that bears Sheffer's name today.
The intellectual roots of the operator go back much further. Charles Sanders Peirce discovered the functional completeness of NAND and NOR as early as 1880, calling the concept 'ampheck,' though he never published his findings. Edward Stamm also proved the functional completeness of these operators in 1911, two years before Sheffer. Despite these earlier discoveries, the association with Sheffer became cemented after Whitehead and Russell adopted the notation in the 1927 second edition of Principia Mathematica, suggesting it as a replacement for the standard OR and NOT operators.
The power of the Sheffer stroke lies in its functional completeness. An operator is functionally complete if it can be used alone to construct any other logical operation. NAND achieves this because it lacks five specific properties: truth-preservation, falsity-preservation, linearity, monotonicity, and self-duality. Because it can define the set of connectives required for the Disjunctive Normal Form Theorem, it serves as the essential foundation for digital circuit design. In modern computing, the NAND gate is the primary component used to build the complex processors that drive our digital infrastructure.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Sheffer stroke
To cite this card, link to https://intellectplus.co.uk/app/science-sheffer-stroke.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?