Sheffer's line

Venn diagram from The Sheffer function is the negation of the logical and . In the area marked red, the function is true, i.e. exactly where and is false.

{\ displaystyle A \; \; \! \! | \; \; \! \! B}

The Sheffer stroke (also Sheffer stroke , Sheffer function , Sheffer operator or English Sheffer stroke ; named after Henry Maurice Sheffer ) or NAND ( English n ot and = not and), written as "|", denoted in Boolean Algebra and propositional logic use a Boolean operator or junctor .

The logical operation based on this is equivalent to the negation of the conjunction ( AND operation ) of two Boolean variables , colloquially this corresponds to "not both".

definition

Semantic definition (truth table)

The Sheffersche line denoted by "|" (or sometimes referred to as "↑", "NAND", " "), is a two connective propositional logic that semantically by the following truth table is defined (this is w for true , f for wrong ): ${\ displaystyle {\ overline {\ land}}}$


A.	B.	A \| B.
w	w	f
w	f	w
f	w	w
f	f	w

The overall statement of two statements linked by the Sheffer's line is true if at least one statement is false, or false if both are true.

Syntactic definition

Sheffer's stroke can be defined by negating the conjunction:

{\ displaystyle A \; \; \! \! | \; \; \! \! B: = \ neg (A \ wedge B) \ equiv {\ overline {A \ wedge B}}}

history

The Sheffer's Stroke is named after Henry Maurice Sheffer , who gave a set of five independent axioms for Boolean algebras that only make use of one connective. He himself considered the interpretation of as neither nor (whereby he pointed out that also as not or not possible, which corresponds to today's usage) and showed that negation and disjunction can be expressed by this juncture . Charles Sanders Peirce had recognized more than thirty years earlier that all connectives can be expressed by the Sheffer's line and its dual operator, the Peirce function (NOR). ${\ displaystyle p \; \; \! \! | \; \; \! \! q}$ ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle q}$

Equivalences

The usual connectives in propositional logic can be expressed using the Sheffer's line as follows:

Negation ( complement gate ):

{\ displaystyle \ neg A \ equiv A \; \; \! \! | \; \; \! \! A,}

Conjunction ( AND gate ):

{\ displaystyle A \ wedge B \ equiv (A \; \; \! \! | \; \; \! \! B) \; \; \! \! | \; \; \! \! (A \ ; \; \! \! | \; \; \! \! B),}

Disjunction ( OR gate ):

{\ displaystyle A \ vee B \ equiv (A \; \; \! \! | \; \; \! \! A) \; \; \! \! | \; \; \! \! (B \ ; \; \! \! | \; \; \! \! B),}

material implication , conditional:

{\ displaystyle A \ rightarrow B \ equiv A \; \; \! \! | \; \; \! \! (B \; \; \! \! | \; \; \! \! B) \ equiv A \; \; \! \! | \; \; \! \! (A \; \; \! \! | \; \; \! \! B)}

material equivalence , biconditional (XNOR, XNOR gate ):

{\ displaystyle A \ leftrightarrow B \ equiv (A \; \; \! \! | \; \; \! \! B) \; \; \! \! | \; \; \! \! ((A \; \; \! \! | \; \; \! \! A) \; \; \! \! | \; \; \! \! (B \; \; \! \! | \; \ ; \! \! B))}

Contra-valence , non-equivalence , alternative (XOR, exclusive-or gate ):

{\ displaystyle A \; \; \! \! {\ dot {\ lor}} \; \; \! \! B \ equiv (A \; \; \! \! | \; \; \! \! (A \; \; \! \! | \; \; \! \! B)) \; \; \! \! | \; \; \! \! (B \; \; \! \! | \; \; \! \! (A \; \; \! \! | \; \; \! \! B))}

Properties and special features

The Sheffer's line has the peculiarity that it alone, without further logical operators, forms a functionally complete system of junctions for propositional logic . This property is the basis for the great importance of NAND in modern digital electronics.

The NAND link and all other logical links can be implemented by NAND gates or their interconnection and are therefore considered a standard module in digital technology . In addition, NAND components are often used because they are the cheapest digital components. In this way, memory modules such as NAND flashes are built from NAND modules in a very space-saving manner.

literature

Charles Sanders Peirce : A Boolean Algebra with One Constant. In: C. Hartshorne, P. Weiss (Eds.): The Simplest Mathematics. Harvard University Press, 1880 ( Collected Papers . Volume 4), pp. 12-20.
Henry Maurice Sheffer : A set of five independent postulates for Boolean algebras, with application to logical constants. In: Transactions of the American Mathematical Society. 14, 1913, pp. 481-488.

Web links

Individual evidence

↑ HM Sheffer: A set of five independent postulates for Boolean algebras, with application to logical constants. In: Transactions of the American Mathematical Society. 14, 1913, pp. 481-488.

[1] HM Sheffer: A set of five independent postulates for Boolean algebras, with application to logical constants. In: Transactions of the American Mathematical Society. 14, 1913, pp. 481-488.