The discovery of the Sheffer Stroke was achieved independently by Henry M. Sheffer in after it had been realized previously by Charles Sanders Peirce, as attested by a fragment written in and, again, in This landmark discovery was hailed by such seminal figures in the history of logic as Ludwig Wittgenstein and Bertrand Russell.
This is examined in detail in the present article. The logical-philosophic significance of the availability of a Sheffer function was taken by Ludwig Wittgenstein in the Tractatus Logico-Philosophicus , to consist in its perspicuous illustration of deeper features of formal logic. Thus, the name Sheffer Stroke is used not simply for the symbol but also for the logical connective itself. This article refers to the logical connective indifferently as the Sheffer Stroke trusting that context removes any ambiguity between the connective and its symbol.
Readers of older Logic textbooks are likely to find the connective called Alternate Denial. The relationship between the Sheffer Stroke and NOR is deep and has profound interest, which will be explored in this article. This article speaks of logical connectives. Strictly speaking, the Sheffer Stroke connective is the semantic analogue of a definable binary Boolean function which can be called the associated Boolean function of the connective. This Boolean function is known as NAND in the theory of electronic or logic gates, where it serves as one of two universal gates; precisely speaking, the physical gate is an instance of implementation of the Boolean function whose propositional-logic interpretation is the Sheffer Stroke.
That interpretation is not examined in the present article. This article focuses only upon propositional logic, unless otherwise indicated. Propositional logic can be considered as the special case of predicate or first-order logic with all predicate constants as being zero-place in its signature.
Propositional logic is bereft of symbolic resources needed for checking many argument forms as valid, for the translation of mathematical statements, and for many other reasons. This article is confined to propositional logic only for the limited purpose of avoiding certain complications while our present interest is in laying out certain basic concepts. Both of these so-called Sheffer functions are binary truth functions with the names also used for the uninterpreted associated Boolean functions ; they both have the remarkable property of being functionally complete—in the sense defined above.
Others use the term regardless of the arity of the functionally complete function. This result holds regardless of the number of truth values over which the connectives are defined. In the standard two-valued propositional logic, there are no unary connectives that are functionally complete but there are exactly two binary connectives that are, and these are called the Sheffer functions of the standard propositional logic. The kind of inquiry that reveals the remarkable properties of the Sheffer Stroke is, properly speaking, metalogical or metatheoretical.
Strictly speaking, those are the associated Boolean functions which are semantically interpreted by the logical connectives. For present purposes, this article does not dwell on this distinction. It speaks consistently about logical connectives. It also traces the historical background of the discovery of these connective. Note that there is inconsistency in the bibliography with respect to both notational variants and terminological jargon.
The logician H. As a logical connective, the Sheffer Stroke stands for a Boolean function defined over the set of two values,. Insofar as the semantic connective Sheffer Stroke is being examined, think of the values as the truth values True and False and denote them respectively by T and F.
It is not unusual to speak interchangeably, or indifferently, of truth functions and logical connectives. Unfortunately, as it was just noted, the bibliography, ranging over several decades in the development of modern logic, is not consistent when it comes to terminological or notational matters. For present purposes, lay down a certain convention: distinguish between logical connectives also called truth functions and their underlying or associated Boolean functions.
The domain of the associated function of the Sheffer Stroke is the Cartesian product. For the sake of completeness, alternative ways of defining this Boolean function will be shown. These, however, should be considered as notational variants; it is the same Boolean function that they all define. It is customary to define logical connectives of logical systems or languages by means of the familiar truth table.
One can also use the familiar truth table to ascertain that the Sheffer Stroke connective receives the same truth value outputs with the negation of conjunction for all possible assignments of truth values to the individual propositional components.
The propositional connective negation, by definition, reverses the truth values of its inputs and the conjunction connective receives the output T only when both of its inputs are T while it receives F for all other possible assignments of truth values to its components.
The logical connective of material equivalence is so defined that it receives the output T if and only if its input values are the same truth values. Making the claim that the Sheffer Stroke connective models such expressions of language means that what is modeled is taken to be truth-functional expressions of a natural language like English. Insofar as one is dealing with truth-functional expressions, the Principle of Compositionality of Meaning applies: the logical meaning of the composite depends uniquely on the specified logical meanings of its parts.
Connecting two propositions by means of the linguistic particle modeled by the Sheffer Stroke asserts the claim that these two propositions are mutual contraries. One can appreciate what contrariety means by checking the truth table above, by means of which the Sheffer Stroke connective is defined: the compound in which the Sheffer Stroke symbol is the principal-connective symbol is false only when the connected propositional components are both true; it is true in every other case or model, which means assignment of truth values to the propositional components or, also called, valuation.
Contrariety or mutual contrariety , then, means that the propositions that are presumed contraries cannot possibly be true together but they can possibly be false together. One should distinguish this from the relationship known as mutual contradictoriness: two propositions are mutual contradictories if and only if they cannot possibly be true together and they cannot possibly be false together. If two propositions p and q are mutual contradictories, then the compound proposition formed by connecting them by means of the exclusive either-or is a logical truth.
On the other hand, based on what has been said, and as can be seen by the truth table above, one has: when two propositions are mutual contraries, then the proposition formed by connecting them by means of the Sheffer Stroke connective is a logical truth.
There are other ways of defining the Sheffer Stroke connective. Its matrix definition is as follows:. Corner brackets are used because there is reference to symbols of the formal object language within the metalanguage , which is a symbolically enhanced fragment of English used to talk about the formal language.
No such brackets are needed also in the case in which the formulas are presented by themselves in space reserved for them. The DNF of a well-formed formula can be obtained from the truth table of by means of the following method: Check the rows, and only the rows, across which receives the truth value T. If an individual or atomic variable receives T on that row, reproduce it as it is, ; if the individual variable receives F on that row, reproduce it as negated.
Next, form the conjunction of the propositional variables so represented which means that one connects them by the connective symbol. Do this for all rows on which receives T. Finally, join all the conjunctions formed in this manner by means of inclusive disjunctions, symbolized by.
Thus, examining the truth table by means of which the Sheffer Stroke was defined, one has: the value T is received on the rows for values of the single propositional variables:. This expression admits of further simplification a subject that is beyond current concerns , to yield a logically equivalent formula:. A method of representation known as the Karnaugh Map is as follows for the Sheffer Stroke. Two different variants of this method are explored.
This is essentially diagrammatic as it allows for simplifications of well-formed formulas that are first transformed into their equivalent normal forms before they are mapped by this type of diagram.
The normal form for the Shefer Stroke is:. The expression to the right is in both Disjunctive and Conjunctive Normal Form. It has exactly two literals, and. Taken as a Disjunctive Normal Form, it has as literals the negations of the two propositional variables: accordingly, we enter into the Karnaugh Map the values T and F in a way we will present now briefly.
Usually, this kind of diagram takes the values as uninterpreted or numerical,. To enter the proper values, we follow the entire row or entire column along which the variable receives the truth value True as shown below. The remaining blocks receive F.
T T An alternative version actually corresponding more closely to the initial design of this diagrammatic method is as follows:. T T In older texts, we find definitions of connectives like the following definition of the Sheffer Stroke.
We consider the propositional variables to be taking truth values in the order:. In textbooks like the one written by Arthur Prior , pp. In the set-theoretic interpretation of Boolean functions, the operation that corresponds to the Sheffer Stroke or NAND is complementation of intersection of sets. The general form can also be represented as follows and, by having recourse to the familiar semantic truth table, we can determine the values of the coefficients which are, in this representation form, the values of the function for the shown pairs i.
It is possible to develop a Gentzen-sequent rule for the Sheffer Stroke. A variable may be shifted from left to right or from right to left by being negated. Repeated variable letters may be deleted by means of a rule known as Contraction and variable letters may be shifted freely or permuted insofar as they stay in the same side of the turnstile.
See History below for symbols used by Sheffer himself and by C. In Polish notation, which uses not infix but prefix placement for connective symbols and neatly dispenses with parentheses, the symbolization for NAND is:. The symbolic variant used for logical gates in electronic circuitry also deploys prefix notation with the symbol of the function written before and not in between the input variables.
As the case usually is with writing out functions, it should be noted that there is ambiguity surrounding the notation used for representing the Boolean function interpreting the Sheffer Stroke: it is not clear if it is the operation that is represented or if a name of the function is given. The notation of the so-called lambda-calculus or -calculus can be used to disambiguate.
Accordingly, to indicate unambiguously that we are giving the name of the underlying function of the NAND or Sheffer Stroke connective, we can write:. We will see in subsequent section what all this amounts to. It so happens that Sheffer used another logical connective which, like the Sheffer Stroke, allows for a reduction of the number of logical connectives that are used.
We will be able to fully appreciate the claims made about the significance of this discovery after we have studied the section on the Properties of the Sheffer Stroke. An entire section, Significance of the Sheffer Stroke for Mathematical Logic, Philosophical Logic, and Philosophy , will be devoted to assessing the importance of this connective.
No other connective or associated function that takes one or two variables as inputs has this property. Standard, two-valued propositional logic has no unary functions that have the property of functional completeness. In subsequent section, we will explore this remarkable logical property in detail. At first blush, availability of this option ensures that economy of resources can be obtained—at least in terms of how many functions or connectives are to be included as undefined.
Unfortunately, there is a trade-off between this gain in economy of symbolic resources and the unwieldy length and rather counterintuitive appearance of the formulas that use only the one connective. Strictly speaking, this is the property of weak functional completeness, given that we disregard whether constants or zero-ary functions like 1 or 0 can be defined.
Peirce subscribed to a Semeiotic view, according to which the fundamental nature and proper tasks of the formal study of logic are defined by the rules set down for the construction and manipulation of symbolic resources. A proliferation of symbols for the various connectives that are admitted into the signature of a logical system suffers from a serious defect on this view: the symbolic grammar fails to match or represent the logical fact of interdefinability of the connectives.
Peirce was willing sometimes to accept constructing a formal signature for two-valued propositional logic by using the two-members set of connectives , which is minimally functionally complete.
This means that these two connectives—or, if we are to stick to an approach that emphasizes the notational character of logical analysis, these two symbols—are adequate expressively: every mathematically definable connective of the logic can be defined by using only these two; and the set is minimally functionally complete in the sense that neither of these connectives can be defined by the other so, as we say, they are both independent relative to each other.
The symbol can be viewed as representing a constant truth function either unary or binary that returns the truth value False for any input or inputs. Or it can be regarded as a constant, which means that it is a zeroary zero-input function, a degenerate function, which refers to the truth value False. Although not using our contemporary terminology, Peirce took the second option. This set has cardinality 2 it has exactly two members but it is not the best we can do.
Thus, either one of the following sets can do. The sets are functionally complete and, because they have only one member each, we say that the connectives themselves have the property of functional completeness.
We stipulate as such, even though we have not introduced our grammar formally. It is important to show, albeit briefly, how these functions can define other functions. Algebraically approached, this is a matter of functional composition but we do not enter into such details here.
We will have more details in subsequent sections. In case one wonders why the satisfaction with defining the connectives of the set that comprises the symbols for negation, inclusive disjunction, and conjunction, namely , there is an explanation: there is an easy, although informal, way to show that this set is functionally complete.
It is not minimally functionally complete because and are inter-definable. But it is functionally complete.
Thus, showing that one can define these functions suffices for achieving functional completeness. Definability should be thought as logical equivalence: one connective can be defined by means of others if and only if the formulas in the definition what is defined and what is doing the defining are logically equivalent. Presuppose the truth-tabular definitions of the connectives. Russell was not aware that Peirce had already made the discovery in the 19 century.
Prompted by this applause and urged on by the weight of renewed expectations, Sheffer, who was not a prolific author, returned to the task of taking further advantage of his discovery, but he did not succeed in advancing beyond his initial contribution. Two other influential authors of an early logic textbook, David Hilbert and Wilhelm Ackermann, regarded this development as a rather unimpressive detail.
No doubt, one reason is that a system that would have only the Sheffer Stroke as its connective would require use of unwieldy formulaic expressions. Abbreviation conventions would be needed, at a minimum. Because one wants to be able to refer to other logical connectives besides the Sheffer Stroke, one actually lays out an expanded variant of SPL, which is called here SPLexp. The next goal is to obtain ML symbols from the OL, and this is done without danger of ambiguity because the context makes clear whether OL or ML is employed.
As is customary, when symbols are mentioned rather than used, they are placed within quotation marks. The formal language SPLexp has symbolic resources for single or atomic propositional variables up to the infinity of the natural numbers , and for logical connectives. It also has auxiliary symbols, and parentheses to be used only for the sake of preventing ambiguity of well-formed expressions. For connectives, the expansive idiom includes symbols for all definable unary and binary connectives of the standard propositional logic.
For present purposes, there is no need to supply names for all the definable connectives denoted by these symbols. Definitions of the connectives are given by means of the familiar truth table. In brief,. N is the set of natural numbers. Symbols from the object language are appropriated, trusting that the context removes ambiguity.
In general, if n is the number of inputs to the connective, the number of mathematically definable n-ary connectives in standard propositional logic is 2 raised to the n power.
An examination of the properties of the Sheffer Stroke begins after having the formal idiom SPLexp in place. Introductory logic textbooks usually omit references to the special properties of the Sheffer Stroke; more advanced logic texts and mathematical logic or metalogic texts always make special mention of this connective and of its dual, the NOR or Peirce Arrow connective.
The student of logic learns that the Sheffer Stroke or NAND, like NOR, has a remarkable characteristic that is called functional completeness or expressive completeness. Forgot password?
Don't have an account? Sign in via your Institution. You could not be signed in, please check and try again. Sign in with your library card Please enter your library card number. Show Summary Details Overview Sheffer's stroke. Subjects: Philosophy. All rights reserved. A set X of truth-functions of 2-valued logic is functionally complete if and only if for each of the five defined classes, there is a member of X which does not belong to that class.
So since is functionally-complete, this means it is not any one of the 5 type of functions listed above, right? But I am not quite seeing how it is not self-dual, it seems like it IS self-dual. Could someone go over the self-dual functions and show the sheffer stroke is not self-dual? Sign up to join this community.
The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Learn more. On the functional-completeness of the sheffer stroke Ask Question. Asked 5 years, 9 months ago. Active 2 years, 6 months ago.
Viewed times.
0コメント