In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both". It is also called non-conjunction, alternative denial (since it says in effect that at least one of its operands is false), or NAND ("not and"). In digital electronics, it corresponds to the NAND gate. It is named after Henry Maurice Sheffer and written as <math>\mid</math> or as <math>\uparrow</math> or as <math>\overline{\wedge}</math> or as <math>Dpq</math> in Polish notation by Łukasiewicz (but not as ||, often used to represent disjunction).
Its dual is the NOR operator (also known as the Peirce arrow, Quine dagger or Webb operator). Like its dual, NAND can be used by itself, without any other logical operator, to constitute a logical formal system (making NAND functionally complete). This property makes the NAND gate crucial to modern digital electronics, including its use in computer processor design.
Definition
The non-conjunction is a logical operation on two logical values. It produces a value of true, if — and only if — at least one of the propositions is false.
Truth table
The truth table of <math>A \uparrow B</math> is as follows.
Logical equivalences
The Sheffer stroke of <math>P</math> and <math>Q</math> is the negation of their conjunction
{| style="text-align: center; border: 1px solid darkgray;"
|-
| <math>P \uparrow Q</math>
|   <math>\Leftrightarrow</math>  
| <math>\neg (P \land Q)</math>
|-
| 50px
|   <math>\Leftrightarrow</math>  
| <math>\neg</math> 50px
|}
By De Morgan's laws, this is also equivalent to the disjunction of the negations of <math>P</math> and <math>Q</math>
{| style="text-align: center; border: 1px solid darkgray;"
|-
| <math>P \uparrow Q</math>
|   <math>\Leftrightarrow</math>  
| <math>\neg P</math>
| <math>\lor</math>
| <math>\neg Q</math>
|-
| 50px
|   <math>\Leftrightarrow</math>  
| 50px
| <math>\lor</math>
| 50px
|}
Alternative notations and names
Peirce was the first to show the functional completeness of non-conjunction (representing this as <math>\overline{\curlywedge}</math>) but did not publish his result. Peirce's editor added <math>\overline{\curlywedge}</math>) for non-disjunction. and non-disjunction in print at the first time and showed their functional completeness.
In 1929, Łukasiewicz used <math>D</math> in <math>Dpq</math> for non-conjunction in his Polish notation.
An alternative notation for non-conjunction is <math>\uparrow</math>. It is not clear who first introduced this notation, although the corresponding <math>\downarrow</math> for non-disjunction was used by Quine in 1940.
History
The stroke is named after Henry Maurice Sheffer, who in 1913 published a paper in the Transactions of the American Mathematical Society
Functional completeness
The Sheffer stroke, taken by itself, is a functionally complete set of connectives. This can be seen from the fact that NAND does not possess any of the following five properties, each of which is required to be absent from, and the absence of all of which is sufficient for, at least one member of a set of functionally complete operators: truth-preservation, falsity-preservation, linearity, monotonicity, self-duality. (An operator is truth-preserving if its value is truth whenever all of its arguments are truth, or falsity-preserving if its value is falsity whenever all of its arguments are falsity.)
It can also be proved by first showing, with a truth table, that <math>\neg A</math> is truth-functionally equivalent to <math>A \uparrow A</math>. Then, since <math>A \uparrow B</math> is truth-functionally equivalent to <math>\neg (A \land B)</math>,
</references>
Further reading
- (NB. Edited and translated from the French and German editions: Précis de logique mathématique)
External links
- Sheffer stroke article in the Internet Encyclopedia of Philosophy
- http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
- Implementations of 2- and 4-input NAND gates
- Proofs of some axioms by Stroke function by Yasuo Setô @ Project Euclid