The Sheffer stroke reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Sheffer stroke

The Sheffer stroke, also known as the NAND 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. 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"

"p and q" is equivalent to "(p NAND q) NAND (p NAND q)"

"p or q" is equivalent to "(p NAND p) NAND (q NAND q)"

"p implies q" is equivalent to "(p NAND q) NAND 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 in terms of other logic functions such as AND and OR, writing these in terms of NAND allows for cheaper construction. The 7400 series of integrated circuits contain NAND gates only.

There is another logical operator which is able 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.

See also

• Charles Peirce
• Logic gate

This is the "Sheffer stroke" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.