Sheffer stroke

The Sheffer stroke, also known as the NAND (Not AND) operation, is a logical operator with the following meaning: p NAND q is true if and only if not both p and q are true. A common means of writing p NAND q is $\overline{p \cdot q}$ , where the symbol $\cdot$ signifies AND and the line over the expression signifies not, the logical negation of that expression. It is named for Henry M. Sheffer, who proved that all the usual operators of logical calculus (not, and, or, implies) could be expressed in terms of it:

"not p" is equivalent to "p NAND p"	$\overline{p} \equiv \overline{p \cdot p}$
"p and q" is equivalent to "(p NAND q) NAND (p NAND q)"	$p \cdot q \equiv \overline{\overline{(p \cdot q)} \cdot \overline{(p \cdot q)}}$
"p or q" is equivalent to "(p NAND p) NAND (q NAND q)"	$p + q \equiv \overline{\overline{(p \cdot p)} \cdot \overline{(q \cdot q)}}$
"p implies q" is equivalent to "(p NAND q) NAND p"	$p \rightarrow q \equiv \overline{\overline{(p \cdot q)} \cdot p}$

This leads to an alternative axiom system for boolean algebras that needs only one operation.

Digital systems that require use of certain logic circuits take advantage of this property. In complicated logical expressions, normally written in terms of other logic functions such as AND, OR, and NOT, writing these in terms of NAND allows for cheaper construction because in many schemes for implementing such circuits, the NAND gate is more compact than these other gates.

There is another logical operator which is sufficient to express all the others: NOR.

Reference

A set of five independent postulates for Boolean algebras, with application to logical constants. Transactions of the American Mathematical Soc. 14 (1913), pp. 481-488.

Sheffer stroke

Reference

See also