Sheffer stroke

Lore & Background

The Sheffer stroke is named after Henry Maurice Sheffer, who in 1913 published a paper providing an axiomatization of Boolean algebras using the stroke and proved its equivalence to a standard formulation. Sheffer interpreted the stroke as a sign for nondisjunction (NOR) in his paper, mentioning non-conjunction only in a footnote. It was Jean Nicod who first used the stroke as a sign for non-conjunction (NAND) in a 1917 paper, which has since become current practice. Russell and Whitehead used the Sheffer stroke in the 1927 second edition of Principia Mathematica, suggesting it as a replacement for the OR and NOT operations of the first edition.

Charles Sanders Peirce had discovered the functional completeness of NAND or NOR more than 30 years earlier, using the term ampheck, but never published his finding. Two years before Sheffer, Edward Stamm also described the NAND and NOR operators and showed that other Boolean operations could be expressed by them. In 1928, Hilbert and Ackermann described non-conjunction with the operator /. In 1929, Łukasiewicz used D in Dpq for non-conjunction in Polish notation. An alternative notation for non-conjunction is ↑; it is not clear who first introduced this notation, although the corresponding ↓ for non-disjunction was used by Quine in 1940.

Reader's Guide

The Sheffer stroke is significant because it is functionally complete, meaning it can be used by itself, without any other logical operator, to constitute a logical formal system. This property makes the NAND gate crucial to modern digital electronics, including its use in computer processor design. The operator is commutative but not associative. Its dual is the NOR operator (also known as the Peirce arrow, Quine dagger, or Webb operator). The Sheffer stroke's functional completeness can be seen from the fact that NAND does not possess any of the five properties required to be absent from a functionally complete set: truth-preservation, falsity-preservation, linearity, monotonicity, and self-duality. It can also be proved by showing that ¬A is equivalent to A↑A, and that A↑B is equivalent to ¬(A∧B), allowing the definition of the set {∧, ∨, ¬}, which is truth-functionally complete by the Disjunctive Normal Form Theorem.

Did You Know?

• The Sheffer stroke is also called non-conjunction, alternative denial, or NAND.
• Charles Sanders Peirce discovered the functional completeness of NAND or NOR more than 30 years before Sheffer, using the term ampheck, but never published his finding.
• Sheffer interpreted the stroke as a sign for nondisjunction (NOR) in his 1913 paper, mentioning non-conjunction only in a footnote.
• NAND is commutative but not associative.