Sheffer stroke

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, or 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 or as or as or as 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. 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. The truth table of is as follows. The Sheffer stroke of and is the negation of their conjunction By De Morgan's laws, this is also equivalent to the disjunction of the negations of and Peirce was the first to show the functional completeness of non-conjunction (representing this as ) but didn't publish his result. Peirce's editor added ) for non-disjunction. In 1911, Stamm was the first to publish a proof of the completeness of non-conjunction, representing this with (the Stamm hook) and non-disjunction in print at the first time and showed their functional completeness. In 1913, Sheffer described non-disjunction using and showed its functional completeness. Sheffer also used for non-disjunction. Many people, beginning with Nicod in 1917, and followed by Whitehead, Russell and many others, mistakenly thought Sheffer has described non-conjunction using , naming this the Sheffer Stroke. In 1928, Hilbert and Ackermann described non-conjunction with the operator .